Хеш функциясының қақтығысы және компьютерлік қауіпсіздік
Hash collision
Хеш-функциялардың қақтығысы: деректерді салыстыру кезінде бірдей хеш-мәнді алу құбылысы. Қауіпсіздік пен деректерді басқаруда маңызды аспекті. Хеш-алгоритмдер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Хеш функциясы құбылысы
Hash function phenomenon
Компьютер ғылымында, хэш-соқтығысу немесе хэш-қақтығыс – хэш-кестедегі екі әртүрлі деректің бірдей хэш-мәніне ие болуы. Бұл жағдайда хэш-мәні деректерді қабылдайтын және белгілі бір ұзындықтағы биттерді қайтаратын хэш-функциядан шығарылады. Хэш-алгоритмдер соқтығысуға төзімді болу үшін жасалғанмен, олар кейде әртүрлі деректерді бірдей хэшке шамалай алады (көгершін принципіне сәйкес). Зардап шектірушілер осы мүмкіндікті пайдаланып, деректерді құпиялап, қол жеткізуге немесе өзгертуге тырысуы мүмкін. Хэш-соқтығысудың деректерді басқару және компьютерлік қауіпсіздікте (әсіресе, криптографиялық хэш-функцияларда) болуы мүмкін теріс салдарына байланысты, соқтығысудан сақтану компьютерлік қауіпсіздікте маңызды мәселе болып табылады.
In computer science, a hash collision or hash clash is when two distinct pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Although hash algorithms have been created with the intent of being collision resistant, they can still sometimes map different data to the same hash (by virtue of the pigeonhole principle). Malicious users can take advantage of this to mimic, access, or alter data. Due to the possible negative applications of hash collisions in data management and computer security (in particular, cryptographic hash functions), collision avoidance has become an important topic in computer security.
Өмірбаян
Хеш-соқтығысулар жиынтықтағы нысандардың санына және оларға сәйкестендірілген биттік тізбектің жеткілікті ұзындығына байланысты туындауы мүмкін. Егер n нысаннан тұратын жиынтық болса, және n саны хэш-мәнінің диапазоны R-ден үлкен болса, онда хэш-соқтығысуының ықтималдығы 1-ге тең, яғни оның болуы кепілді. Хэш-соқтығысулардың кез келген уақытта пайда болуының тағы бір себебі – математикадағы туған күн парадоксының идеясы. Бұл мәселе n адамның арасынан кездейсоқ таңдалған екі адамның бірдей туған күніне ие болу ықтималдығын қарастырады. Осы идея туған күнге жасалған шабуыл деп аталатын нәрсенің пайда болуына әкелді. Бұл шабуылдың мәні – нақты сіздің туған күніңізге немесе белгілі бір туған күніне сәйкес туған күнді табу қиын, бірақ кез келген екі адамның туған күндері сәйкес келу ықтималдығы артады. Зардап шегушілер осы тәсілді нақты мәнді іздеудің орнына, кез келген басқа хэш-мәнімен соқтығысатын хэш-мәндерін табуды жеңілдету үшін пайдалана алады. Соқтығысудың әсері қолданылған салаға байланысты. Хэш-функциялар мен сақтандырғыштар гомологты ДНК тізбектері немесе ұқсас аудио файлдар сияқты ұқсас деректерді анықтау үшін қолданылғанда, функциялар жергілікті сезімтал хэштеу сияқты әдістерді пайдаланып, ерекше бірақ ұқсас деректер арасындағы соқтығысу ықтималдығын арттыруға бағытталған. Ал тексеру сомалары ұқсас кірістер арасындағы соқтығысу ықтималдығын азайту үшін жасалған, әртүрлі кірістер арасындағы соқтығысуларға назар аудармай. Зардап шегушілер хэш-соқтығысуларын жасауға немесе табуға тырысатын жағдайлар соқтығысу шабуылдары деп аталады. Іс жүзінде, қауіпсіздікке қатысты қолданыстар криптографиялық хэш-алгоритмдерін пайдаланады, олар кездейсоқ сәйкестіктердің болу ықтималдығын азайту үшін жеткілікті ұзын, кез келген жерде қолдануға болатын жылдам және соқтығысуларды табудың өте қиын болуын қамтамасыз ететін қауіпсіз болып жасалған.
Hash collisions can be unavoidable depending on the number of objects in a set and whether or not the bit string they are mapped to is long enough in length. When there is a set of n objects, if n is greater than |R|, which in this case R is the range of the hash value, the probability that there will be a hash collision is 1, meaning it is guaranteed to occur. Another reason hash collisions are likely at some point in time stems from the idea of the birthday paradox in mathematics. This problem looks at the probability of a set of two randomly chosen people having the same birthday out of n number of people. This idea has led to what has been called the birthday attack. The premise of this attack is that it is difficult to find a birthday that specifically matches your birthday or a specific birthday, but the probability of finding a set of any two people with matching birthdays increases the probability greatly. Bad actors can use this approach to make it simpler for them to find hash values that collide with any other hash value – rather than searching for a specific value. The impact of collisions depends on the application. When hash functions and fingerprints are used to identify similar data, such as homologous DNA sequences or similar audio files, the functions are designed so as to maximize the probability of collision between distinct but similar data, using techniques like locality sensitive hashing. Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs. Instances where bad actors attempt to create or find hash collisions are known as collision attacks. In practice, security related applications use cryptographic hash algorithms, which are designed to be long enough for random matches to be unlikely, fast enough that they can be used anywhere, and safe enough that it would be extremely hard to find collisions.
CRC-32
CRC 32 хэш-соқтығысулары үшін ең жоғары тәуекел тудырады. Бұл хэш-функцияны қолдану көбінесе ұсынылмайды. Егер хабта 77 163 хэш-мәні болса, хэш-соқтығысу пайда болу ықтималдығы 50% құрайды, бұл басқа әдістермен салыстырғанда өте жоғары деңгей.
CRC 32 poses the highest risk for hash collisions. This hash function is generally not recommended for use. If a hub were to contain 77,163 hash values, the chance of a hash collision occurring is 50%, which is extremely high compared to other methods.
MD5
MD5 – ең көп қолданылатын және басқа екі хэш-функциясымен салыстырғанда, хэш-тұрастыру қаупі тұрғысынан орташа деңгейде болып табылады. Хэш-тұрастырудың 50% мүмкіндігін тудыру үшін хабта 5,06 миллиардтан астам жазба болуы керек. Ашық адрестеу – жабық хэштеу деп те аталады.
MD5 is the most commonly used and when compared to the other two hash functions, it represents the middle ground in terms of hash collision risk. In order to get a 50% chance of a hash collision occurring, there would have to be over 5.06 billion records in the hub. Open Addressing is also known as closed hashing.
Бөлек тізбектеу
Бұл стратегия бірнеше жазбаны хэш-кестенің ұяшықтарына "тізбектеуге" мүмкіндік береді. Егер екі жазба бір ұяшыққа бағытталса, екеуі де сол ұяшыққа байланысты тізім түрінде орналасады. Бұл хэш-соқтығысудың алдын алуға көмектеседі, себебі бірдей хэш-мәні бар жазбалар бір ұяшыққа түсе алады, бірақ бұның да кемшіліктері бар. Ондай көптеген тізімдерді қадағалау қиын, және қолданылып жатқан құралдың жұмысы өте баяулау болуы мүмкін.
This strategy allows more than one record to be "chained" to the cells of a hash table. If two records are being directed to the same cell, both would go into that cell as a linked list. This efficiently prevents a hash collision from occurring since records with the same hash values can go into the same cell, but it has its disadvantages. Keeping track of so many lists is difficult and can cause whatever tool that is being used to become very slow.
Кэшке бейімделген соқтығысуды шешу
Алдыңғы екеуінен гөрі әлдеқайда сирек қолданылса да, 2005 жылы кэшті ескеретін соқтығысуды шешу әдісі ұсынылды. Бұл бөлек тізбектеу әдістеріне ұқсас идея, бірақ ол техникалық тұрғыдан тізбекті тізімдерді қамтымайды. Оның орнына, хэш-мәндер элементтердің үздісіз тізімінде көрсетіледі. Бұл әдіс мәтіндік хэш-кестелерге жақсырақ сай келеді, ал сандық мәндер үшін қолданылуы әлі белгісіз.
Although much less used than the previous two, has proposed the cache conscious collision resolution method in 2005. It is a similar idea to the separate chaining methods, although it does not technically involve the chained lists. In this case, instead of chained lists, the hash values are represented in a contiguous list of items. This is better suited for string hash tables and the use for numeric values is still unknown.