collisions_probability.tex

\subsection{Вероятность коллизии}
\selectlanguage{russian}

Если $k$-битовая криптографическая хэш-функция имеет равномерное распределение выходных хэш-значений по всем сообщениям, то, согласно парадоксу дней рождений, среди
    \[ n_{1/2} \approx \sqrt{2 \ln 2} \cdot 2^{k/2} \]
случайных сообщений с вероятностью больше $0.5$ найдутся два сообщения с одинаковыми значениями хэш-функций, то есть произойдет коллизия.

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

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

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

Например, для 128-битовой функции MD5\index{коллизия}\index{MD5} Xiaoyun Wang и Hongbo Yu в 2004 г. нашли атаку для нахождения коллизии за $2^{39} \ll 2^{64}$ операций. Это означает, что MD5 взломана и более не может считаться криптографической хэш-функцией.