Каковы шансы, что два сообщения имеют один и тот же дайджест 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)

Так

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

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

---

РЕДАКТИРОВАТЬ

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

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

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

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

п! ≈ sqrt(2πn) * (н / д)ⁿ

Итак (S!)/(S^N * (S - N)!) ≈ sqrt(2πS)/sqrt(2π(SN)) * (S / e)^S/ ((SN) / e)^SN/ S^N

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

= sqrt (1 + α) * (1 + α)^SN * e^-N, где α = N/(SN) мало.

Аппроксимация (1 + a / n)^nx ≈ e^ax выполняется при n → ∞ (или, по крайней мере, становится очень большой)

** так что это означает (1+(N/(SN)))^SN ≈ e^N для SN >> N.

Так что я ожидаю, что

(S!)/(S^N * (S - N)!) ≈ 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

Обычно, когда выбирают 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-хеш сталкивается для двух входов, уже очень мала.

Answer 5

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

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/ сек).