collisions_probability.tex

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

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

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

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

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

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