Насколько точен `md5sum`?

27

md5sumНасколько точен процесс при использовании для проверки целостности файла?

Означает ли подтвержденный MD5, что КАЖДЫЙ бит точно такой же, или есть пороговое значение, которое необходимо преодолеть, чтобы двоичное изменение отразилось на MD5?

Любая документация о том, как генерируется md5, также приветствуется.

Коннер Расмуссен
источник
@choroba Если я все это правильно читаю, то вероятность необнаруженного изменения увеличивается с размером проверяемого файла. Однако это все еще вероятность, и 100% -ная уверенность может быть достигнута только с 16-байтовым файлом. Я прав?
Коннер Расмуссен
@Konner Я прочитал твой вопрос, связанный с передачей файлов. Для этой цели это безопасно. Вероятность небольшого повреждения при передаче невелика, и более вероятно, что вы потеряете некоторую часть скопированного файла при передаче, предполагая, что я понял вашу предыдущую ситуацию . MD5 является попыткой эквивалентно сравнению обоих файлов, с некоторым преимуществом в том, что вам не нужно обращаться к обоим файлам одновременно.
Доктор Рейхард
15
«Означает ли подтвержденный MD5, что КАЖДЫЙ бит точно такой же?» Обратите внимание, что это невозможно, благодаря принципу Pigeonhole. en.wikipedia.org/wiki/Pigeonhole_principle
Plutor
3
Я не думаю, что вы получите гарантию на 16-байтовые файлы.
Mooing Duck

Ответы:

65

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

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

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

Дэвид Шварц
источник
Хотя теоретически возможно создать два файла с одинаковым хешем, это практически невозможно. Особенно, если замена файла также должна иметь смысл. Например, если исходный файл представлял собой текст на английском языке, других совпадений, кроме английского, может не быть. Или, если это электронная таблица Excel, ни один из других файлов с таким же хешем не будет действительной электронной таблицей.
Бармар
1
@Barmar: win.tue.nl/hashclash/Nostradamus эти ребята создали несколько PDF-файлов с одинаковым хешем MD5, чтобы доказать, что это практически осуществимо.
Philfr
26

MD5 - это хеш. Он в основном отображает все содержимое файла в небольшую строку длиной 16 байтов IIRC.

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

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

Итай
источник
1
Короче говоря, md5 - это не более чем быстрый и грязный способ проверки целостности файла, и его следует использовать только тогда, когда необнаруженная ошибка не приведет к катастрофическим последствиям ... правильно?
Коннер Расмуссен
3
Лучшее его использование - обнаружение повреждений при передаче или копировании. на самом деле не для безопасности.
Майкл Мартинес
12
@KonnerRasmussen - дело не в степени последствий, а в природе угрозы. Если вы беспокоитесь о том, что два документа могут случайно иметь один и тот же MD5, перестаньте беспокоиться: вероятность того, что ваши компьютеры самопроизвольно загорятся, значительно выше; если вы обеспокоены тем, что интеллектуальный злоумышленник может создать документ, который совпадает с тем, который у вас уже есть, это серьезная проблема, и вам следует получить лучший хэш; если вы обеспокоены тем, что интеллектуальный злоумышленник может создать два документа, которые соответствуют друг другу, не беспокойтесь: это обязательно произойдет.
Мальволио
5
Конечно, хотя теоретически возможно генерирование коллизии хеша MD5, генерация полезного коллизии (например, коллизирующий файл - это файл того же типа, а его содержимое по меньшей мере правдоподобно аутентично) намного сложнее ...
Шадур
6
@Shadur: Раньше это было так, но продолжающиеся исследования в области безопасности обнаружили новые способы генерирования коллизий MD5, которые делают это проще. В частности, если ваш формат файла допускает фрагменты данных «комментариев» произвольного формата, можно сопоставить любой хэш MD5, вставив подходящий комментарий.
MSalters
17

MD5-хэш состоит из 128 бит. Один перевернутый бит в источнике переворачивает (в среднем) 64 бита в хэше.

Вероятность случайного столкновения двух хэшей составляет 1/2 ^ 128, что составляет 1 на 340 унцдиллион 282 дециллионов 366 ниллионов 920 октиллионов 938 септиллионов 463 квинтиллионов 463 квинтиллионов 374 квадриллионов 607 триллионов 431 миллиардов 768 миллионов 211 тысяч 456.

Однако, если вы сохраните все хеши, то благодаря парадоксу вероятность рождения немного выше. Чтобы иметь 50% вероятности столкновения любого хеша, вам нужно 2 ^ 64 хеша. Это означает, что для получения коллизии в среднем вам потребуется хэшировать 6 миллиардов файлов в секунду в течение 100 лет.

Источник: porneL, /programming/201705/how-many-random-elements-before-md5-produces-collisions

Жолт Силаги
источник
8
Так ты говоришь, что еще есть шанс? : p
Холлоуэй
1
Проблема в том, что, хотя вам НУЖНО хэшировать 6 миллиардов файлов в секунду в течение 100 лет, чтобы быть уверенным, что вы обнаружите коллизию; это может произойти в течение первой секунды.
Дероби
Правда, это могло произойти в первую секунду. Но, как всегда, речь идет о причинах баланса. Там могут быть военные приложения, где этот риск не приемлем, но я бы взял напрокат автомобиль, не задумываясь, где датчики подушек безопасности используют MD5. Помните, что есть вероятность, что вас ударит молния несколько раз в ожидании столкновения md5.
Жолт Силаги
Извините, но половина 2 ^ 128 - это 2 ^ 127, а не 2 ^ 64.
fischi
2
@fischi, прочитайте ссылку на парадокс дня рождения, а также en.wikipedia.org/wiki/Birthday_attack - это не просто сокращение вдвое общего числа хэшей. Учитывая пространство поиска H, количество хэшей, которое вы должны сгенерировать до получения 50% -ной вероятности столкновения, составляет приблизительно sqrt ((pi / 2) * H). Если вы сделаете эту математику с 2 ^ 128, вы получите число примерно 2 ^ 64
Пол Диксон