Какова скорость столкновения для md5?

Какова вероятность конфликта для алгоритма md5? Я считаю, что это крайне низко.


security md5 cryptography hash hash-collision
person Adam Lee    schedule 13.01.2012    source источник

Ответы (2)


arrow_upward
44
arrow_downward

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

Если вы посмотрите на два произвольных значения, вероятность столкновения составляет всего 2-128.

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

Короче говоря, md5 безопасен для целей, не связанных с безопасностью, но не работает во многих приложениях безопасности.

person CodesInChaos    schedule 13.01.2012
comment
2 ^ (n/2), как и предсказывает проблема дня рождения. - person CodesInChaos; 13.01.2012
comment
Исходя из этой информации, подходит ли создание идентификаторов документов для системы, содержащей миллионы документов, на основе их хэша md5 их соответствующего содержимого? @CodesInChaos - person SaidbakR; 07.06.2015
comment
@sємsєм Я бы предпочел использовать SHA256, но MD5 не должен быть проблемой, если документы создаются добросовестной стороной. - person CodesInChaos; 07.06.2015
comment
Я предпочитаю md5 из-за производительности. Я думаю, что md5 намного быстрее, чем SHA256, не так ли? @CodesInChaos - person SaidbakR; 07.06.2015
comment
@sємsєм Это быстрее, но даже SHA-2 и SHA-3 могут обрабатывать несколько сотен МБ / с на настольном процессоре. Если этого все еще недостаточно, вы можете посмотреть на Skein или Blake2, которые почти так же быстры, как MD5, но при этом безопасны. | В качестве альтернативы, если вы можете использовать секретный ключ, HMAC-MD5 по-прежнему относительно безопасен. - person CodesInChaos; 18.09.2015
comment
Отличный ответ, спасибо! - person Boris Burkov; 06.01.2017
comment
@ Альберт, это 1 конфликт каждые X файлов. Вы не можете так сказать, потому что вероятность квадратично зависит от количества файлов. - person CodesInChaos; 18.10.2017

arrow_upward
7
arrow_downward

Он генерирует 128-битное значение. Таким образом, частота случайных конфликтов должна быть 2-64 (из-за парадокса дня рождения).

person Jonathan Leffler    schedule 13.01.2012
comment
Вероятность столкновения значительна около 2 ^ 64 значений, но частота конфликтов для двух произвольных значений составляет всего 2 ^ -128. - person CodesInChaos; 13.01.2012