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

[BlackEric]

Добрый день.

Есть где-то документация как можно посчитать вероятность коллизий хешей на произвольных данных? В смысле, что их не будут специально ломать, а использовать для проверки на уникальность.
Или чему она равна?
Особенно интересуют Md5, Sha-1, Sha-256.

[mihaild]

Как правило используется модель "значения хеша на разных входах - независимые равномерно распределенные на кодомене величины". Дальше комбинаторика.

[worm2]

Вероятность коллизии в множестве из $M$ элементов, каждый из которых является случайным натуральным числом, равновероятно выбранным из интервала $[1, N]$, где $N>M$ (предполагаю, что криптографические хеши можно считать такими), равна

$$1-\frac{N!}{(N-M)! N^M}=1-\left(1-\frac 1N\right)\left(1-\frac 2N\right)\dots\left(1-\frac {M-1}N\right).$$

Для MD5 $N=2^{128}$
Для SHA-1 $N=2^{160}$
Для SHA-256 $N=2^{256}$
$M$ — это число различных хешей, для которых вычисляется вероятность коллизии.
В практических целях мы не можем пользоваться формулой с факториалами, т.к. они уж очень большие. Но и для формулы со скобками тоже нужны вычисления с длинными (256-битными, как минимум) числами, причём если $M$ большое, то и она тоже непригодна. В ряде случаев формула Стирлинга для факториала даёт хорошие приближения:

$$1-\frac{N!}{(N-M)! N^M} \approx 1- \left(1-\frac MN\right)^{M-N-0.5}e^{-M}.$$

Во всяком случае, для расчёта квантилей (когда вероятность достигнет $0.0\dots1$; $0.5$; $0.9$; $0.99\dots9$) при не очень большом числе девяток должно хватить.

[BlackEric]

Спасибо, тогда получается, что для Md5 вероятность словить коллизию $2^{-64}$. Можно спокойно использовать.

[iifat]

BlackEric в сообщении #1663879 писал(а):

Можно спокойно использовать

Вероятности — штука тонкая. «События с вероятностью один на миллион случаются по паре раз в неделю». Если задача хоть сколь-нить важная, ей-богу, прои совпадении хэшей я б таки проверял.

[Dmitriy40]

BlackEric
Вообще-то для $M=2$ вероятность коллизии MD5 равна $1/N=2^{-128}$, а не $2^{-64}$. Это легко понять даже без формул: чтобы второй хеш совпал с первым он должен быть ему равен, а это всего лишь одно из $N$ равновероятных значений для второго хеша.
Вот для $M=3$ вероятность будет $\frac{1.5}{2^{64}}$ (с точностью до членов порядка $1/N$).
Вообще для случая $M \ll N$, когда можно пренебречь членами порядка $1/N^2$ и меньше, вероятность считается легко (достаточно раскрыть скобки и отбросить всё меньше порядка $1/N$):

$$1-\left(1-\frac 1N\right)\left(1-\frac 2N\right)\dots\left(1-\frac {M-1}N\right)\approx\frac{1}{N} \sum\limits_{k=1}^{M-1} k=\frac{1}{N}\frac{M(M-1)}{2}$$

.

Ну а чтобы пару раз в неделю происходило событие с вероятностью $10^{-6}$ достаточно генерить возможности для него со скоростью примерно 3 раза в секунду, всего лишь, во многих приложениях это совсем немного и бывает сильно чаще.