Коллизии хэш-функций и парадокс дней рождения / forpes.ru

Главная
Коллизии хэш-функций и парадокс дней рождения

Коллизии хэш-функций и парадокс дней рождения +17

22.09.2025 09:01

alizar 0 1000 Источник

Как работает хэш-функция? На вход подаются произвольные данные — слово, веб-сайт, файл или ДНК человека — а на выходе она выдаёт 16-теричное число (hex). Очень удобно, чтобы стандартизировать различные объекты, присвоить им уникальные ID, цифровые отпечатки.

К сожалению, отпечатки иногда получаются одинаковыми — происходят коллизии.

Коллизии хэш-функций похожи на парадокс дней рождения, который недавно снова вызвал бурные дебаты на Хабре и на HN. Почему люди так горячо спорят? Наверное, потому что человеческая интуиция иногда не совпадает с математическими формулами. Другими словами, язык математики ≠ человеческому.

Интересно сравнить разные хэш-функции с математической точки зрения. Насколько часты «парадоксы»?

Хэш-функции используются во многих компьютерных задачах, например:

Проверка корректности данных при передаче, обнаружение ошибок. Например, есть удобные утилиты HashCheck и OpenHashTab, которая поддерживает 28 алгоритмов для вычисления хэшей файлов.

Идентификация объектов. Вычисление хэша позволяет быстро убедиться, что файл не повреждён при загрузке или копировании. У каждого файла или блока данных своя сигнатура, ID (хэш), что также используется в P2P-сетях, антивирусных базах и др.
Генерация адресов для хранения данных (бэкапы, файловые системы и проч.) Удобно хранить объект по адресу, который соответствуют хэшу этого объекта. Это свойство применяется в хэш-таблицах и хэш-ключах для индексации баз данных. Хэш-таблицы гарантируют доступ к элементу за времени, независимо от размера базы.
Приватность. Вместо хранения конфиденциальных данных (имена, пароли, бюллетени голосования) хранятся их хэши (с солью).
Криптография. Цифровая подпись — это хэш документа, зашифрованный приватным ключом.

Есть и более креативные применения. Например, изобретатель может заранее опубликовать хэш своей работы до оформления патента, чтобы зафиксировать приоритет идеи, не раскрывая её содержание.

Коллизии

Хэш-коллизии происходят, когда наша функция присваивает одинаковый ID разным объектам. Это неприятное событие в продакшне, потому что система тогда может перепутать пользователей, заказы, файлы или ещё что-нибудь.

Математики и программисты постоянно разрабатывают новые и более совершенные хэш-функции. Можно выбирать подходящую для каждого конкретного варианта использования, учитывая её производительность, вероятность коллизии и другие характеристики.

Поскольку хэш-функция уменьшает количество энтропии, то никогда нельзя полностью исключить вероятность коллизии. Например, взять известную хэш-функцию CRC32. Если передать ей две строки «plumless» и «buckeroo», то она сгенерирует одинаковое значение:

Можно вычислить математическую вероятность коллизии для разных функций. По сути, это просто общая форма математического парадокса дней рождений. Ответ в такой задаче не всегда очевиден, потому что интуитивно его тяжело угадать.

Парадокс дней рождения

Напомним парадокс дней рождения:

В группе из 23 или более человек вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50%.

Например, если в классе 23 ученика, то более вероятно совпадение ДР у какой-то пары одноклассников, чем существование у всех учеников уникальных ДР.

График зависимости вероятности совпадения дней рождения хотя бы у двух человек от количества людей

Парадокс дней рождения можно свести к коллизиям хэш-функций, потому что вероятность такого события вычисляется примерно одинаково. В приложении на хэш-функции он звучит так:

Если вычислять хэши 500 книг и помещать каждую книгу в соответствующую ячейку в ряду из 100 000 ячеек, какова вероятность того, что хотя бы две книги окажутся в одной и той же ячейке? (~71,3%).

Или так:

Когда вы случайным образом раскладываете 50 шаров по 100 вёдрам, какова вероятность того, что хотя бы два шара окажутся в одном ведре? (~99,99997%).

См. калькулятор коллизий.

Вероятность коллизии

Если предположить, что хэш-функция достаточно хороша и равномерно распределяет хэш-значения по доступному диапазону, то в этом случае генерация хэш-значений для набора входных данных очень похожа на генерацию набора случайных чисел. Таким образом, вопрос сводится к следующему:

Учитывая случайно сгенерированных значений, где каждое значение является неотрицательным целым числом, меньшим , какова вероятность того, что как минимум два из них равны?

Задачу проще решить, если сформулировать обратный вопрос: какова вероятность того, что все сгенерированные значения уникальны? Затем вычесть ответ из единицы. Сделаем это по старой инструкции.

Учитывая пространство из возможных значений хэша, предположим, мы выбрали одно значение. После этого остаётся уникальных значений. Таким образом, вероятность случайного выбора двух целых чисел, отличающихся друг от друга, равна .

Теперь осталось уникальных значения (из возможных ), так что вероятность случайной генерации трёх различных целых чисел равна $\frac{N-1}{N}\times\frac{N-2}{N}$ . (каждое генерирование случайного числа является независимым событием, поэтому перемножаем вероятности).

В общем случае вероятность случайной генерации целых чисел, все из которых являются уникальными, равна:

$\frac{N-1}{N}\times\frac{N-2}{N}\times\dots\times\frac{N-(k-2)}{N}\times\frac{N-(k-1)}{N}$

Что можно примерно приравнять к более оптимальной для вычисления формуле:

$e^{\frac{-k(k-1)}{2N}}$

Скрипт для сравнения результата формул, чтобы оценить качество аппроксимации:

import math
N = 1000000
probUnique = 1.0
for k in xrange(1, 2000):
    probUnique = probUnique * (N - (k - 1)) / N
    print k, 1 - probUnique, 1 - math.exp(-0.5 * k * (k - 1) / N)

После вычитания этого значения из единицы мы получаем вероятность коллизии:

$1 - e^{\frac{-k(k-1)}{2N}}$

Такая аппроксимация снижает сложность вычислений с до .

Вот как выглядит график для $N = 2^{32}$ :

Вероятность коллизии для 32-битных хэшей. Здесь вероятность 50% возникает при количестве хэшей 77163. Также стоит отметить, что у графика одинаковая S-образная форма при любом значении N

На самом деле можно упростить экспоненциальную аппроксимацию:

$\frac{k(k-1)}{2N}$

И ещё более упростить:

$\frac{k^2}{2N}$

На графике ниже показаны относительные погрешности экспоненциальной аппроксимации (exp), упрощённой (simple) и ещё более упрощённой версии (simple-square):

Минимизация коллизий

В некоторых приложениях (например, для ID) очень важно избегать коллизий. Вот почему интереснее всего посмотреть на условия, которые минимизируют вероятность такого события.

В следующей таблице представлены диапазоны малых вероятностей коллизий для хэшей 32, 64 и 160 бит. Для простоты понимания в таблицу включены несколько реальных вероятностей, например, шансы выиграть в лотерею:

Сравнение функций

Существует много разных хэш-функций, это по-прежнему активная область исследований. Некоторые из них отличаются производительностью (скоростью вычисления хэша), другие более равномерно распределяют хэш-значения по доступному диапазону. Если вас интересует производительность известных хэш-функций в реальных условиях, вот программный код для некоторых бенчмарков, которые можно провести повторно и проверить результаты.

Для примера, ниже результаты тестирования некоторых старых хэш-функций на процессоре Core i5. Задача включает добавление нескольких ключей в таблицу, а затем поиск их в том же порядке, в котором они добавлялись. Время замерялось инструкцией RDTSC. В качестве набора данных использовались список слов английского языка (words в таблице), список Win32 и др.

Первая цифра в каждой ячейке соответствует времени выполнения, а в квадратных скобках указано количество коллизий.

	Words	Win32	Numbers	Prefix	Postfix	Variables	Sonnets	UTF-8	Ipv4	Avg
iSCSI CRC	65 [105]	329 [415]	36 [112]	84 [106]	83 [92]	280 [368]	408 [584]	1964 [2388]	322 [838]	1.01 [1.78]
Meiyan	64 [102]	328 [409]	45 [125]	87 [106]	85 [112]	274 [350]	411 [588]	1972 [2377]	353 [768]	1.05 [1.87]
Murmur2	72 [103]	378 [415]	48 [104]	109 [106]	106 [111]	315 [383]	450 [566]	2183 [2399]	399 [834]	1.21 [1.74]
XXHfast32	78 [110]	372 [420]	57 [102]	88 [103]	88 [106]	315 [347]	473 [491]	2323 [2494]	463 [838]	1.23 [1.71]
SBox	70 [91]	389 [431]	46 [116]	124 [108]	123 [91]	304 [347]	430 [526]	2182 [2442]	377 [836]	1.23 [1.78]
Larson	72 [99]	401 [416]	34 [16]	143 [99]	141 [105]	312 [366]	451 [583]	2230 [2447]	349 [755]	1.25 [1.10]
XXHstrong32	79 [109]	385 [429]	58 [102]	93 [102]	92 [112]	321 [355]	474 [491]	2332 [2496]	464 [838]	1.25 [1.72]
Sedgewick	73 [107]	417 [414]	36 [48]	143 [103]	143 [103]	319 [348]	446 [570]	2246 [2437]	349 [782]	1.26 [1.33]
Novak unrolled	76 [113]	404 [399]	43 [90]	127 [118]	125 [113]	322 [342]	459 [581]	2284 [2430]	379 [969]	1.26 [1.68]
CRC-32	70 [101]	429 [426]	40 [64]	146 [107]	143 [94]	320 [338]	443 [563]	2231 [2400]	357 [725]	1.28 [1.41]
Murmur3	78 [101]	391 [380]	54 [104]	108 [103]	107 [105]	331 [334]	492 [555]	2360 [2376]	433 [783]	1.28 [1.69]
x65599	74 [111]	407 [382]	45 [203]	144 [107]	144 [122]	316 [379]	449 [560]	2221 [2373]	349 [846]	1.29 [2.45]
FNV-1a	74 [124]	408 [428]	47 [108]	144 [94]	144 [105]	309 [374]	440 [555]	2193 [2446]	376 [807]	1.30 [1.77]
Murmur2A 79	[114]	410 [433]	53 [102]	117 [112]	114 [109]	337 [365]	494 [544]	2377 [2369]	429 [772]	1.31 [1.73]
Fletcher	71 [131]	352 [406]	80 [460]	104 [127]	100 [108]	312 [507]	481 [1052]	2477 [4893]	388 [1359]	1.31 [4.62]
K&R	73 [106]	429 [437]	47 [288]	149 [94]	149 [106]	324 [360]	450 [561]	2266 [2365]	343 [831]	1.32 [3.00]
Paul Hsieh	80 [114]	410 [420]	54 [118]	123 [101]	121 [100]	336 [341]	496 [600]	2351 [2380]	433 [847]	1.33 [1.83]
Bernstein 75	[114]	428 [412]	49 [288]	150 [100]	150 [102]	324 [353]	460 [572]	2312 [2380]	351 [703]	1.34 [2.99]
x17 unrolled	78 [109]	446 [415]	43 [24]	156 [113]	153 [102]	344 [368]	472 [589]	2361 [2392]	373 [829]	1.37 [1.19]
lookup3	83 [101]	459 [412]	55 [97]	140 [101]	137 [95]	359 [361]	526 [550]	2480 [2392]	427 [834]	1.42 [1.65]
MaPrime2c	79 [103]	459 [426]	50 [106]	155 [91]	155 [106]	349 [349]	486 [550]	2493 [2406]	406 [865]	1.42 [1.73]
Ramakrishna	80 [108]	513 [409]	44 [91]	189 [125]	186 [103]	370 [360]	483 [528]	2565 [2383]	380 [840]	1.51 [1.66]
One At Time	85 [105]	562 [421]	58 [110]	221 [97]	220 [103]	392 [364]	511 [545]	2659 [2346]	459 [795]	1.72 [1.75]
Arash Partow	83 [101]	560 [435]	71 [420]	215 [98]	212 [85]	392 [355]	507 [570]	2638 [2372]	407 [779]	1.72 [3.88]
Weinberger	87 [104]	590 [422]	37 [100]	254 [111]	273 [117]	398 [364]	541 [712]	2734 [2547]	419 [744]	1.78 [1.75]
Hanson	73 [118]	417 [649]	45 [112]	123 [118]	1207 [499]	318 [435]	448 [592]	2324 [2890]	370 [833]	2.70 [2.46]

Сравнение производительности с помощью утилиты SMhasher определяет такой список самых быстрых хэш-функций, у которых нет проблем с качеством:

rapidhash (улучшенная wyhash),
xxh3low,
wyhash,
umash,
ahash64,
t1ha2_atonce,
a5hash,
komihash,
FarmHash,
halftime_hash128,
Spooky32,
pengyhash,
nmhash32,
mx3,
MUM/mir,
fasthash32.

Новые функции

Практически каждый год становится известно о разработке новых хэш-функций, в том числе специализированных, которые созданы для решения конкретных задач. Например, в тестировании выше лучше всех проявил себя алгоритм хэширования rapidhash, который оптимизирован на максимальную производительность (скорость хэширования): более 70 ГБ/с на процессоре M4. Семейство включает три хэш-функции: rapidhash, rapidhashMicro и rapidhashNano.

Комментарии (0)

xFFFF
22.09.2025 10:07
#28867134
Алгоритм CRC и криптографические хэш-функции — это хоть и похожие алгоритмы, но придуманы для разных задач. CRC — линейный код, созданный для обнаружения случайных ошибок передачи/хранения, и он не должен быть уникальным для всех возможных сообщений, потому что при разумной длине CRC вероятность ошибки, при которой тег не изменится, пренебрежимо мала в модели случайных ошибок. При умышленных или специально подобранных искажениях CRC непригоден.