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

Ответ 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, поэтому я не думаю, что вам есть о чем беспокоиться. Коллизии не очень вероятны.

Ответ 2

добавление к сообщению Welbog:

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

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

So (S!)/(S ^ N * (S - N)!) & асимптотика; SQRT (2 & пи; S)/SQRT (2 & пи; (SN)) * (S/е) ^S/((SN),/е) ^SN/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 & асимп. e ^ax выполняется как n → & INFIN; (или, по крайней мере, становится очень большим)

**, поэтому это означает (1+ (N/(S-N))) ^S-N & асимп. e ^N для S-N → N.

Поэтому я ожидал бы, что

(S!)/(S ^ N * (S - N)!) & асимптотика; sqrt (1 + N/(SN)) * e ^N * e ^-N= sqrt (1 + N/(SN)) для SN → N....

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

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

Ответ 3

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

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

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

Ответ 5

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

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

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

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

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

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

Теперь вы спрашиваете:

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

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

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

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