Каковы шансы, что два сообщения имеют одинаковый дайджест MD5 и один и тот же дайджест SHA1?

Question

Учитывая два разных сообщения, A и B (может быть 20-80 символов текста, если размер имеет значение), какова вероятность того, что дайджест MD5 для A такой же, как дайджест MD5 для B SHA1-дайджест A такой же, как SHA1-дайджест B? То есть:

(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))

Не допускайте злонамеренных намерений, т. Е. Что сообщения не отбираются с целью обнаружения конфликта. Я просто хочу знать шансы, что это произойдет естественным путем.

Я думаю, что шансы "астрономически низки", но я не уверен, как это проверить.

Дополнительная информация: размер пула возможных сообщений ограничен, но велик (несколько сотен миллионов). Парадокс дня рождения - это именно то, о чем я беспокоюсь.

Answer 1

Предполагая равномерный разброс в диапазоне хэшей MD5 и SHA-1 для случайных строк (что не так), и предполагая, что мы говорим только о двух строках, а не о пуле строк (поэтому мы избегаем сложность типа дня рождения-парадокса):

Хэш MD5 имеет ширину 128 бит, а SHA-1 - 160. С учетом вышеизложенных допущений две строки A и B имеют вероятность коллизии P, если оба хеша сталкиваются. Итак

P(both collide) = P(MD5 collides) * P(SHA-1 collides)

А

P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)

So

P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87

Опять же, если у вас есть пул строк, и вы пытаетесь определить вероятности столкновений с пулом, вы находитесь в области парадокса дня рождения , и эту вероятность я вычислил здесь не относится. Это и хеши не так однородны, как должны быть. В действительности у вас будет гораздо более высокая частота столкновений, но она все равно будет крошечной.

---

EDIT

Поскольку вы имеете дело с парадоксом дня рождения, примените ту же логику, что и в решении парадокса дня рождения. Давайте посмотрим на это с точки зрения только одной хеш-функции:

N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)

Давайте представим, что у нас есть хорошее четное число хешей, например 2 ^ 29 (примерно 530 миллионов).

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

Короче, я даже не хочу думать о расчете этого числа. Я даже не уверен, как вы можете оценить это. Вам по крайней мере понадобится калькулятор произвольной точности, который может обрабатывать огромные факториалы, не умирая.

Обратите внимание, что вероятности будут следовать кривой, которая начинается с 0, когда N = 1 or 2, и достигает 1, когда N >= 2^288, по форме похожа на фигуру на странице Википедии для парадокса дня рождения.

Парадокс дня рождения достигает P = .5, когда N = 23. Другими словами, вероятность столкновения составляет 50%, когда N составляет 6% от S. Если это масштабируется (я не уверен, что так и будет), это означает, что вероятность столкновения будет 50%, если у вас есть 6% из 2 ^ 288 хешей. 6% от 2 ^ 288 составляет около 2 ^ 284. Ваше значение N (несколько сотен миллионов) близко к этому. Это практически незначительно по сравнению с вашим S, так что я не думаю, что вам есть о чем беспокоиться. Столкновения не очень вероятны.

Answer 2

приложение к сообщению Велбога:

Соотношения больших факториалов можно вычислить без использования арифметики произвольной точности, используя приближение Стирлинга :

п! & Asymp; sqrt (2 & pi; n) * (н / д) ⁿ

Итак (S!) / (S ^ N * (S - N)!) & Asymp; SQRT (2 & пи; S) / SQRT (2 & пи; (SN)) * (S / R) ^S / ((SN), / е) ^{SN * +1014 * / S N}

= sqrt (S / (S-N)) * (S / (S-N)) ^S-N * e ^-N

= sqrt (1 + & alpha;) * (1 + & alpha;) ^S-N * e ^-N где & alpha; = N / (S-N) мало.

Аппроксимация (1 + a / n) ^nx & asymp; e ^ax сохраняется как n & rarr; & INFIN; (или, по крайней мере, становится очень большим)

**, значит, (1+ (N / (S-N))) ^S-N & asymp; e ^N для S-N >> N.

Так что я бы ожидал, что

(S!) / (S ^ N * (S - N)!) & Asymp; sqrt (1 + N / (SN)) * e ^N * e ^-N = sqrt (1 + N / (SN)) для SN >> N ....

за исключением того, что это больше, чем 1 ... так что одно из приближений недостаточно. : Р

(** предостережение: N / S должно быть небольшим: для N = 22, S = 365 это значение отключается с коэффициентом 2)

Answer 3

Если размер сообщения не ограничен, вероятность приближается к 100% асимптотически, поскольку существует бесконечное число возможных сообщений и конечное число возможных хешей.

(примечание: редактирование вопроса делает это менее актуальным)

Answer 4

Выбранный ответ неверен, потому что он использует неправильные вероятности. Я потратил значительную часть сегодняшнего дня, исследуя это (вы можете увидеть мой мыслительный процесс в комментариях к этому ответу), и считаю, что реальный ответ следующий (для атаки на день рождения чуть больших сообщений, чем те, о которых вы говорите) :

2 ^ -61 * 2 ^ -18 = столкновение один раз за 2 ^ 79.

И это нормально, если просто умножить эти вероятности (я не уверен в этом).

Это возможно на суперкомпьютерах сегодня (менее пары месяцев и каждый год сбрасывается).

Обратите внимание, что это основано на достаточно больших пулах сообщений (чтобы придать смысл парадоксу дня рождения). Это также сценарий, который, как вы сказали, вас беспокоит.

Теперь другая ситуация - обнаружение коллизии для пары хешей (SHA1 и MD5) специфического сообщения . Это уводит вас с территории парадокса bday и на несколько порядков сложнее. Я не уверен, что это 2 ^ (- 61 * 2) * 2 ^ (- 18 * 2) или что-то еще. Если кто-то знает, что это такое, пожалуйста, оставьте комментарий к этому ответу (будет очень признателен!).

Теперь вы спросите:

С учетом двух разных сообщений, A и B (может быть 20-80 символов текста, если размер имеет значение)

Да, размер имеет значение. Нажмите на ссылку с цифрой 2 ^ -18, и вы увидите, что это значение для двух входных блоков. В MD5 входной блок составляет 512 байт. 20-80 символов текста слишком мало для этого, а значение для одного блока составляет 2 ^ 41.

Таким образом, для этого количества данных вы получите 2 ^ -61 (я думаю) * 2 ^ -41 = 2 ^ -102.

Так что для этого размера он кажется безопасным (ссылка содержит цифру в два раза превышающую текущую биткойну SHA256: 46626,93 TH / сек).

Answer 5

Обычно, когда выбирают N элементов случайным образом, легче вычислить ожидаемое количество столкновений, чем вероятность столкновения. Поскольку ожидаемое количество столкновений не может быть меньше вероятности столкновения, его часто можно использовать в качестве подходящей верхней границы.

Предположим, что p - это вероятность столкновения двух случайно выбранных элементов. Если мы выберем N случайных элементов, то будет N * (N-1) / 2 пары элементов и, следовательно, ожидаемое количество столкновений равно

p * N * (N-1) /2.

Например, если мы предположим, что вероятность столкновения для MD5 и SHA1 равна p = 2 ^-288 , то даже после случайного выбора 2 ¹⁰⁰ элементов мы все еще ожидаем только около 2 ^{-89 ​​} столкновения.

Другой пример: если мы выберем 2 ³⁰ случайных элементов и вычислим только MD5. Предполагая, что коллизия между двумя хэшами MD5 равна p = 2 ^-128 , это дает ожидаемое число 2 ^-59 для количества коллизий. Следовательно, даже вероятность того, что хэш MD5 столкнется для двух входов, уже очень мала.