Введение
Феномен хеш-функций
В информатике, хеш-коллизия или коллизия хешей – это ситуация, когда две различные единицы данных в хеш-таблице имеют одно и то же хеш-значение. В этом случае хеш-значение вычисляется хеш-функцией, которая принимает на вход данные и возвращает строку фиксированной длины. Хотя хеш-алгоритмы разрабатываются с целью устойчивости к коллизиям, они все же могут иногда отображать разные данные в одно и то же хеш-значение (в силу принципа Дирихле). Злоумышленники могут использовать это для имитации, получения доступа или изменения данных. В связи с возможными негативными последствиями хеш-коллизий в управлении данными и компьютерной безопасности (особенно в криптографических хеш-функциях), предотвращение коллизий стало важной задачей в области компьютерной безопасности.
Предыстория
Хеш-коллизии могут быть неизбежны в зависимости от количества объектов в наборе и от того, достаточно ли длинна битовая строка, в которую они отображаются. Когда имеется набор из n объектов, если n больше, чем |R|, где R – диапазон значений хеша, вероятность хеш-коллизии равна 1, то есть она гарантированно произойдет. Другая причина, по которой хеш-коллизии вероятны в какой-то момент времени, связана с идеей парадокса дней рождения в математике. Эта задача рассматривает вероятность того, что у двух случайно выбранных людей совпадает день рождения из числа n человек. Эта идея привела к так называемой атаке в стиле "дня рождения". Суть этой атаки заключается в том, что сложно найти день рождения, который конкретно соответствует вашему или заданному дню рождения, но вероятность найти пару людей с совпадающими днями рождения значительно возрастает. Злоумышленники могут использовать этот подход, чтобы упростить поиск хеш-значений, которые коллидируют с любым другим хеш-значением, вместо поиска конкретного значения. Влияние коллизий зависит от области применения. Когда хеш-функции и отпечатки используются для идентификации схожих данных, таких как гомологичные последовательности ДНК или похожие аудиофайлы, функции разрабатываются таким образом, чтобы максимизировать вероятность коллизии между различными, но похожими данными, используя такие методы, как локально-чувствительное хеширование. Контрольные суммы, напротив, предназначены для минимизации вероятности коллизий между похожими входными данными, не принимая во внимание коллизии между сильно отличающимися входными данными. Случаи, когда злоумышленники пытаются создать или найти хеш-коллизии, известны как коллизионные атаки. На практике, в приложениях, связанных с безопасностью, используются криптографические хеш-алгоритмы, которые разработаны таким образом, чтобы быть достаточно длинными для минимизации вероятности случайных совпадений, достаточно быстрыми для использования в любом месте и достаточно надежными, чтобы поиск коллизий был чрезвычайно сложен.
CRC-32
CRC 32 представляет наибольший риск возникновения коллизий хеша. Эта хеш-функция обычно не рекомендуется к использованию. Если в концентраторе содержится 77 163 хеш-значений, вероятность возникновения коллизии составляет 50%, что крайне высоко по сравнению с другими методами.
MD5
MD5 — наиболее часто используемый алгоритм, и по сравнению с двумя другими хеш-функциями он занимает промежуточное положение с точки зрения вероятности коллизий. Для достижения 50% вероятности возникновения коллизии хеша, в системе должно быть более 5,06 миллиарда записей. Метод открытой адресации также известен как метод закрытой хеш-таблицы.
Отдельная цепь
Эта стратегия позволяет "связывать" более одной записи с ячейками хеш-таблицы. Если две записи попадают в одну и ту же ячейку, обе они помещаются в эту ячейку в виде связного списка. Это эффективно предотвращает возникновение коллизии хешей, поскольку записи с одинаковыми хеш-значениями могут быть помещены в одну и ту же ячейку, но у этого подхода есть свои недостатки. Поддерживать такое большое количество списков сложно, и это может значительно замедлить работу используемого инструмента.
Резолюция столкновения с кэшем
Хотя этот метод используется значительно реже, чем два предыдущих, в 2005 году был предложен способ разрешения коллизий, учитывающий особенности кеша. Он основан на схожей идее с методами раздельного связывания, однако технически не предполагает использование связных списков. Вместо связных списков хеш-значения представляются в виде непрерывного списка элементов. Этот подход лучше подходит для строковых хеш-таблиц, а его применение для числовых значений пока не изучено.