Достаточно ли хороша MD5 для однозначной идентификации файлов?

142

Считается ли хеширование файла MD5 достаточно хорошим методом для его однозначной идентификации, учитывая все нарушения алгоритма MD5, проблемы безопасности и т. Д.? Безопасность здесь не является моей главной задачей, но важна уникальная идентификация каждого файла.

есть идеи?

Ранхиру Джуд Курай
источник
2
На самом деле в настоящее время я сам использую его в одном из своих приложений, и, насколько мне известно, он достаточно хорош, чтобы однозначно идентифицировать файлы.
Недоступно
2
Вы, вероятно, найдете этот вопрос: stackoverflow.com/questions/862346/… полезным.
Sharptooth
Сколько файлов вам нужно идентифицировать? Он выводит 128 бит, поэтому, если вы пытаетесь идентифицировать несколько тысяч файлов, все в порядке. Но если вы пытаетесь указать намного больше, вы можете столкнуться с коллизиями / парадоксом дня рождения.
Марчин
Это будут файлы изображений в формате jpg, png и gif. И да, я думаю, предел будет несколько тысяч ... Но сколько файлов, как вы примерно думаете, доставят мне неприятности?
Ranhiru Jude Cooray
Связанный: stackoverflow.com/questions/14973197/…
NeDark

Ответы:

89

Да. MD5 был полностью взломан с точки зрения безопасности, но вероятность случайного столкновения все еще исчезающе мала. Просто убедитесь, что файлы создаются не кем-то, кому вы не доверяете и который может иметь злой умысел.

Марсело Кантос
источник
2
@none: Первый вопрос смотрите здесь . Боюсь, я не понимаю других вопросов.
Марсело Кантос,
9
@ 0xA3: Ни вы, ни я понятия не имеем, к каким файлам относится OP, или какой ущерб может нанести компрометация. Насколько мы знаем, это может быть коллекция детских фотографий их детей. Моя цель - предоставить факты; то, что с ними делают другие, - их дело. Также учтите, что Брюс Шнайер рекомендует записать свой пароль; не все нужно хранить в Форт-Ноксе. Некоторые вещи прекрасно сохранятся под цветочным горшком.
Марсело Кантос,
3
@Marcelo Cantos, я думаю, здесь не хватает дифференциации или распаковки термина «безопасность». Очевидно, люди предполагают «безопасность» для любого использования работы с контрольными суммами, но Марсело, вероятно, означает «в лаборатории».
hpavc
5
Я категорически не согласен. Другое значение хеш-функции говорит о том, что файлы разные. Но для равного хеш-значения: вы не можете сказать «весьма вероятно, что оба они одинаковы», если хеш-значения одинаковы: вы можете сравнивать только побайтно. Хэш на много порядков меньше, чем количество различных значений для всего файла, поэтому существует много, много, много возможных конфликтов для каждого значения хеша. Только в случае копирования известного файла (с известным хешем) идентичное значение хеш-функции «вероятно, означает», что второй был скопирован правильно (даже в этом случае это не на 100% уверено, но весьма вероятно).
Оливье Дюлак
3
Хорошо, моя математика - отстой. GUID имеют около 122 бит энтропии, поэтому вероятность столкновения в любом месте миллиарда файлов составляет примерно 2 ^ (2 * 30 - 122) = 2 ^ -62. Хотя это намного выше моих первоначальных расчетов, оно все еще ничтожно - примерно одна из 4 квинтиллионов.
Марсело Кантос
32

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

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

Stapeluberlauf
источник
16
@Ranhiru. Нет. Хэш дает вам «сводное» значение, которое (для MD5) составляет всего 16 байт. Чтобы гарантировать идентичность файлов, вам нужно будет выполнить побайтовую проверку. Это верно независимо от того, какой алгоритм хеширования вы выберете, всегда есть вероятность коллизии.
PaulG
6
@Ranhiru. Перечитайте этот ответ, его, по-моему, самый полный здесь. Хеширование можно использовать в качестве первого шага, который дает вам 99,99% уверенности в том, что файлы идентичны, но если вы хотите быть абсолютно уверенным на 100% , вам нужно будет выполнить побайтовую проверку. Это верно независимо от того, используете ли вы MD5, SHA или любой другой алгоритм.
PaulG
7
Это неверный ответ. Предотвращение взлома и проверка уникальности - одно и то же. Кроме того, хотя хеширование не гарантирует уникальности, ни фактическое сравнение не гарантирует. Фактически, вероятность случайного столкновения хэша на самом деле ниже, чем вероятность неудачного сравнения из-за сбоев в процессоре, вызванных нормальным солнечным гамма-излучением. И не забывайте, что часто единственный источник файла находится на другом конце света внутри веб-сервера, а единственная независимая часть информации, которая у вас есть для сравнения, - это хэш.
Марсело Кантос,
8
@ Марсело. Логично предположить, что случайное столкновение менее вероятно, чем случайное переключение битов (при побайтовом сравнении). У вас все еще есть такой же шанс битового переворота при построении хэша (и, возможно, больше, поскольку требуется больше времени на обработку). @Thomas поднял точку первоначально , чтобы предположить , что там не гарантируется способ определения уникальности, хотя влияние бит переворачивается является весьма спорным. Самая пессимистичная оценка - 1 переворот на ГБ / час, и ОЗУ ECC удалит даже это.
PaulG
2
«Вероятность случайного столкновения хэша на самом деле ниже, чем вероятность неудачного сравнения из-за сбоев в процессоре, вызванных нормальным солнечным гамма-излучением»
Эндолит
20

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

Поскольку знание того, применимы ли известные слабые стороны MD5 к данному контексту, является тонким вопросом, рекомендуется не использовать MD5. Безопасный ответ - использование устойчивой к коллизиям хэш-функции (SHA-256 или SHA-512). Кроме того, использование MD5 является плохим пиаром (если вы используете MD5, будьте готовы оправдываться; никто не будет сомневаться в том, что вы используете SHA-256).

Томас Порнин
источник
2
Этот ответ может ввести в заблуждение, если читатель не слишком знаком с хешированием. В SHA нет ничего волшебного, предотвращающего хэш-коллизии, просто они более устойчивы к атакам хеш-коллизий . Если вы хотите быть более чем на 99,999% уверенности, что файлы идентичны, вам все равно потребуется побайтовая проверка.
PaulG
7
На самом деле побайтовое сравнение может потерпеть неудачу из-за небольшого переворота космических лучей (например, преобразования a return 0;в a return 1;). Это маловероятно, но риск столкновения с SHA-256 еще меньше. Математически вы не можете быть уверены, что два файла с одинаковым значением хэша идентичны, но вы не можете быть уверены в этом, сравнивая сами файлы, если вы используете компьютер для сравнения. Я имею в виду, что бессмысленно выходить за рамки 99,999 ... 9% уверенности, а SHA-256 уже обеспечивает большее.
Томас Порнин
2
Что, вы не используете память ECC? ;). Хороший комментарий, очень интересные мысли.
PaulG
1
Не забудьте шляпу из фольги! Если серьезно, откуда вы знаете эти фактоиды о столкновениях и проверили ли вы это каким-то образом?
Джеймс П.
@ThomasPornin Битовые перевороты космических лучей также повлияют на метод MD5, так что это еще хуже.
Эндолит
9

MD5 может вызывать коллизии. Теоретически, хотя это маловероятно, миллион файлов подряд может дать один и тот же хэш. Не испытывайте удачу и проверяйте наличие коллизий md5 перед сохранением значения.

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

Вы можете прочитать о принципе «ящика» .

Афилина
источник
6

Я бы не рекомендовал это. Если приложение будет работать в многопользовательской системе, может быть пользователь, у которого будет два файла с одинаковым хешем md5 (он может быть инженером и играть с такими файлами или просто любопытствовать - их легко загрузить с http: / /www2.mat.dtu.dk/people/S.Thomsen/wangmd5/samples.html , я сам при написании этого ответа скачал два образца). Другое дело, что некоторые приложения могут хранить такие дубликаты по какой-либо причине (я не уверен, есть ли такие приложения, но возможность существует).

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

тач
источник
2

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

hpavc
источник
0

MD5 не работает, вместо этого вы можете использовать SHA1 (реализовано на большинстве языков)

Гийом Лебуржуа
источник
Это отличный ответ. MD5 неприемлем для использования в сфере права и бухгалтерского учета в Европе с мая 2018 года.
Берт Синнема
@BertSinnema, не могли бы вы указать мне источник, который определяет, какие хэш-функции приемлемы и т. Д., Пожалуйста?
Березовский
@GregSchmit, возможно, потому, что OP не заботился о криптографической стойкости как таковой. Я понял вопрос как «Я уже использую MD5 в контексте, не связанном с безопасностью, нужно ли мне тратить время на обновление кода?» Такие вещи. И в этом контексте ответ, вероятно, был неправильным, и с тех пор SHA1 тоже был сломан.
Березовский
0

При хешировании коротких (<несколько K?) Строк (или файлов) можно создать два хэш-ключа md5, один для фактической строки, а второй для обратной строки, соединенных с короткой асимметричной строкой. Пример: md5 (обратный (строка || '1010')). Добавление дополнительной строки гарантирует, что даже файлы, состоящие из серии одинаковых битов, сгенерируют два разных ключа. Пожалуйста, поймите, что даже при этой схеме существует теоретическая вероятность того, что два хеш-ключа будут идентичны для неидентичных строк, но вероятность кажется чрезвычайно малой - что-то порядка квадрата вероятности одиночного столкновения md5 и экономии времени может быть значительным, когда количество файлов растет. Можно также рассмотреть более сложные схемы создания второй струны,

Чтобы проверить наличие коллизий, можно запустить этот тест на уникальность хэш-ключей md5 для всех бит_векторов в базе данных:

выберите md5 (bit_vector), count (*), bit_and (bit_vector) из db с
группой bit_vector по md5 (bit_vector), bit_vector, имеющим bit_and (bit_vector) <> bit_vector

Марко Поло
источник
Умная идея. Если «злоумышленник» создает фальшивый файл с тем же хешем md5, это не поможет, если он не знает вашего «соления», и изменение содержимого приведет к созданию другого хеша. Использование 2 таких ключей md5 значительно снизит шансы. Если его просто предотвратить «атаку» с помощью соли перед локальным расчетом будет достаточно.
Wolf5
0

Мне нравится думать о MD5 как о индикаторе вероятности при хранении большого количества файловых данных.

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

Шимми Вайцхандлер
источник