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

5241
Konner Rasmussen

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

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

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

27
http://en.wikipedia.org/wiki/MD5 choroba 10 лет назад 12
@choroba Если я все это правильно читаю, то вероятность необнаруженного изменения увеличивается с размером проверяемого файла. Однако это все еще вероятность, и 100% -ная уверенность может быть достигнута только с 16-байтовым файлом. Я прав? Konner Rasmussen 10 лет назад 0
@Konner Я прочитал твой вопрос, связанный с передачей файлов. Для этой цели это безопасно. Вероятность небольшого повреждения при передаче невелика, и более вероятно, что вы потеряете некоторую часть скопированного файла при передаче, предполагая, что я понял [вашу предыдущую ситуацию] (http://superuser.com/q/741747 / 228536). MD5 является попыткой эквивалентно сравнению обоих файлов, с некоторым преимуществом в том, что вам не нужно обращаться к обоим файлам одновременно. Doktoro Reichard 10 лет назад 0
Если я действительно хочу убедиться, что два файла идентичны, я сделаю "cmp -l" .... Просто позвольте вам знать, Michael Martinez 10 лет назад 0
@MichaelMartinez, для которого потребуется две копии файла, что может оказаться неразумным, если файл слишком велик. Более того, мне известна команда `cmp`. я ценю вклад хотя ... =) Konner Rasmussen 10 лет назад 0
«Означает ли подтвержденный MD5, что КАЖДЫЙ бит точно такой же?» Обратите внимание, что это невозможно, благодаря принципу Pigeonhole. http://en.wikipedia.org/wiki/Pigeonhole_principle Plutor 10 лет назад 15
Я не думаю, что вы получите гарантию на 16-байтовые файлы. Mooing Duck 10 лет назад 3

3 ответа на вопрос

65
David Schwartz

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

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

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

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

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

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

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

Короче говоря, md5 - это не более чем быстрый и грязный способ проверки целостности файла, и его следует использовать только тогда, когда необнаруженная ошибка не приведет к катастрофическим последствиям ... правильно? Konner Rasmussen 10 лет назад 1
Лучшее его использование - обнаружение повреждений при передаче или копировании. на самом деле не для безопасности. Michael Martinez 10 лет назад 3
@KonnerRasmussen - Верно. Например, вы можете проверить резервную копию с помощью MD5, но может случиться так, что ошибка пройдет незамеченной. Itai 10 лет назад 0
@KonnerRasmussen - дело не в степени последствий, а в природе угрозы. Если вы обеспокоены тем, что два документа могут случайно иметь один и тот же MD5, перестаньте беспокоиться: вероятность того, что ваши компьютеры самопроизвольно загорятся, значительно выше; если вы обеспокоены тем, что интеллектуальный злоумышленник может создать документ, который совпадает с тем, который у вас уже есть, это серьезная проблема, и вам следует получить лучший хэш; если вы обеспокоены тем, что интеллектуальный злоумышленник может создать два документа, которые соответствуют друг другу, не беспокойтесь: это, безусловно, произойдет. Malvolio 10 лет назад 12
Конечно, хотя теоретически возможно создание коллизии хеша MD5, генерация * полезного * коллизии (например, коллизирующий файл - это файл того же типа, а его содержимое, по крайней мере, правдоподобно аутентично) намного сложнее ... Shadur 10 лет назад 5
@Shadur: Раньше это было так, но продолжающиеся исследования в области безопасности обнаружили новые способы генерирования коллизий MD5, которые делают это проще. В частности, если ваш формат файла допускает фрагменты данных «комментариев» в произвольном формате, можно сопоставить любой хэш MD5, вставив подходящий комментарий. MSalters 10 лет назад 6
17
Zsolt Szilagy

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

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

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

Источник: porneL, https://stackoverflow.com/questions/201705/how-many-random-elements-before-md5-produces-collisions

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

Похожие вопросы