2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вероятность коллизий хешей
Сообщение06.12.2024, 16:50 
Добрый день.

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

 
 
 
 Re: Вероятность коллизий хешей
Сообщение06.12.2024, 16:58 
Аватара пользователя
Как правило используется модель "значения хеша на разных входах - независимые равномерно распределенные на кодомене величины". Дальше комбинаторика.

 
 
 
 Re: Вероятность коллизий хешей
Сообщение06.12.2024, 17:37 
Аватара пользователя
Вероятность коллизии в множестве из $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$) при не очень большом числе девяток должно хватить.

 
 
 
 Re: Вероятность коллизий хешей
Сообщение06.12.2024, 20:58 
Спасибо, тогда получается, что для Md5 вероятность словить коллизию $2^{-64}$. Можно спокойно использовать.

 
 
 
 Re: Вероятность коллизий хешей
Сообщение07.12.2024, 03:01 
BlackEric в сообщении #1663879 писал(а):
Можно спокойно использовать
Вероятности — штука тонкая. «События с вероятностью один на миллион случаются по паре раз в неделю». Если задача хоть сколь-нить важная, ей-богу, прои совпадении хэшей я б таки проверял.

 
 
 
 Re: Вероятность коллизий хешей
Сообщение07.12.2024, 03:56 
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 раза в секунду, всего лишь, во многих приложениях это совсем немного и бывает сильно чаще.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group