Рекурсивный MD5 и вероятность столкновения

Интересно, «безопасно» ли хешировать кучу хеш-значений MD5 вместе, чтобы создать новый хеш, или это каким-либо образом увеличит вероятность коллизий.

Предыстория: у меня есть пара файлов с зависимостями. С каждым файлом связано хеш-значение, которое рассчитывается на основе его содержимого. Назовем это "однофайловым" хеш-значением. В дополнение к этому, файл также должен иметь хеш-значение, которое включает все зависимые файлы, хеш-значение «многофайлового».

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

В качестве альтернативы, могу ли я объединить однофайловые хеш-значения вместе, чтобы сгенерировать многофайловое хеш-значение, или это, вероятно, приведет к большему количеству конфликтов?


md5 hash-collision
person Janick Bernet    schedule 18.09.2011    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Похоже, вам нужно Дерево Меркель

person James    schedule 18.09.2011
comment
Спасибо, интересно смотрится :) - person Janick Bernet; 18.09.2011
comment
Хотя он на самом деле не ответил на мой вопрос о MD5, в частности, это решает мою проблему, так как сейчас я собираюсь использовать хеши Tiger, которые, кажется, идеально подходят для моей цели :) - person Janick Bernet; 19.09.2011

arrow_upward
1
arrow_downward

У MD5 много проблем с коллизиями, см. запись MD5 в Википедии.

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

Или, если еще не поздно, переключитесь на SHA-1.

person squadette    schedule 18.09.2011
comment
Насколько я понимаю, проблемы коллизий в основном актуальны при предположении об активном злоумышленнике, единственной целью которого является спровоцировать коллизию, но не то, что случайные коллизии значительно более вероятны, чем при использовании SHA-1. Поскольку он предназначен исключительно для создания уникального идентификатора, а не в целях безопасности, активные злоумышленники не являются проблемой, а производительность является основной проблемой. - person Janick Bernet; 18.09.2011
comment
Для контрольных сумм (и это довольно очевидно из вопроса, что именно это делает OP) поддельные коллизии не имеют значения. Только последняя часть второго предложения вообще касается вопроса, и она определенно нуждается в уточнении - как вы пришли к такому выводу? - person ; 18.09.2011
comment
Я считаю, что тогда ты должен быть в полной безопасности. Вы сопоставляете файлы с точками в пространстве 2 ^ 128. Затем вы сопоставляете другой небольшой файл (соединение) с другой точкой в ​​пространстве 2 ^ 128. Если вы доверяете MD5 единообразному хешированию ваших файлов - вы должны доверять ему хэширование ваших конкатенаций так же равномерно. - person squadette; 18.09.2011
comment
@squadette: Возможно (особенно учитывая, что его легко искусственно создать коллизии), что сам хеш MD5 имеет некоторые свойства, которые делают их плохими базами для хеширования снова с использованием MD5. Например, может быть теоретически, что бесконечное применение хешей MD5 сходится к определенному хеш-значению. - person Janick Bernet; 18.09.2011

arrow_upward
1
arrow_downward

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

person Gerben    schedule 18.09.2011
comment
Я тоже думаю. :) Однако лучше перестраховаться, чем потом сожалеть и постоянно сталкиваться с кучей столкновений :) - person Janick Bernet; 18.09.2011
comment
Все дело в хешировании. Если вы хотите быть уверены на 100%, не используйте хеши. Просто знайте, что хэши предназначены для максимально случайного распределения, чтобы вероятность коллизий очень близка к 1 / hashsize (1/2 ^ 128 для md5). Вы не получите тонны коллизий, но ваш код не должен ломаться, иногда возникает коллизия. - person Gerben; 18.09.2011
comment
Я не боюсь вероятности столкновения 1: 1 ^ 128, но, как я писал в squadette, теоретически рекурсивное применение MD5 может сходиться к определенному хэш-значению, кого я должен знать. Поэтому я хотел бы получить некоторую информацию от людей, знающих алгоритм, есть ли у него такие проблемы или нет. - person Janick Bernet; 18.09.2011
comment
Сначала вы не хешируете хеш, а хешируете строку объединенных хешей. Во-вторых, вы углубляетесь только на 2 уровня, а не на повторение 1000 раз. Схождения не произойдет уже через 2 раунда. - person Gerben; 18.09.2011
comment
Правда, в моем примере я углубляюсь только на один уровень, возможно, мне стоит обобщить вопрос более подробно. Но если бы они сходились, углубление на один уровень определенно увеличило бы вероятность столкновений, вопрос только в том, насколько. Как я уже сказал, я не считаю, что это проблема, но я все же хотел бы получить некоторые математические факты или, по крайней мере, некоторые внутренние знания людей, знающих внутреннюю работу MD5, что можно использовать его таким образом. - person Janick Bernet; 18.09.2011