8.6. Коллизии в хеш-функциях

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

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

в приложении), среди

случайных сообщений с вероятностью больше $1/2$ найдутся два сообщения с одинаковыми значениями хеш-функций, то есть произойдёт коллизия.

Криптографические хеш-функции должны быть равномерными по выходу, насколько это можно проверить, чтобы быть устойчивыми к коллизиям. Следовательно, для нахождения коллизии нужно взять группу из примерно $2^{k/2}$ сообщений.

Например, для нахождения коллизии в 96-битовой хеш-функции, которая, в частности, используется в имитовставке ${\textrm{MAC}}$ в протоколе IPsec, потребуется группа из $2^{48}$ сообщений, 3072 Тбайт памяти для хранения группы и время на $2^{48}$ операций хеширования, что достижимо.

Если значения хеш-функции имеют неравномерное распределение, то размер группы с коллизией меньше, чем $n_{1/2}$. Если для поиска коллизии достаточно взять группу с размером, много меньшим $n_{1/2}$, то хеш-функция не является устойчивой к коллизиям.

Например, для 128-битовой функции MD5 в 2005 году Ван Сяоюн и Ю Хунбо (пиньинь Wáng Xiǎoyún и Yú Hóngbō) представили атаку для нахождения коллизии за $2^{39} \ll 2^{64}$ операций [106]. Это означает, что MD5 взломана и более не может считаться надёжной криптографической хеш-функцией.

8.6.2. Комбинации хеш-функций

Для иллюстрации свойств устойчивости к коллизиям исследуем следующий пример комбинирования двух хеш-функций. Рассмотрим две хеш-функции $f$ и $g$. Известно, что одна из этих функций не противостоит коллизиям, но какая именно – неизвестно. Тогда имеют место следующие утверждения:

• Функция $h(x) = f(g(x))$ не устойчива к коллизиям, если $g(x)$ имеет коллизии.
• Функция $h(x) = f(g(x)) ~\|~ g(f(x))$ не устойчива, например, если $g(x) = \textrm{const}$.
• Функция $h(x) = f(x) ~\|~ g(x)$ устойчива к коллизиям.