Почему обнаружение коллизий в криптографической хэш-функции облегчает поиск других коллизий?

Question

Из Википедии я прочитал:

Жу [3] заметил, что 2-коллизии приводят к n-коллизиям: если возможно найти два сообщения с одинаковым хешем MD5,Фактически, не более трудно найти столько сообщений, сколько хочет атакующий с идентичными хэшами MD5.

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

Это просто делает небольшие итерации для обоих первых сообщений о столкновениях и затем отслеживает их изменения, чтобы переназначить их?

Answer 1

Это свойство не всех хеш-функций, но слабость конструкции Меркля – Дамгарда (на которой основаны MD5 и SHA-1), известной как расширение длины, Слабость заключается в том, что вы можете «возобновить» вычисление хеша с помощью специально выбранных добавленных данных. Для получения полной информации о том, как это используется для генерации произвольного количества коллизий, смотрите:

• Мультиколлизии в итерированных хэш-функциях. Приложение к каскадным конструкциям (Антуан Жу)

Для связанной атаки, основанной на этой идее, см .:

• Понимание атак на расширение длины хеша
• Уязвимость Flickr, связанная с подделкой подписей API

Answer 2

Я думаю, что ключом здесь является слово «выполнимо». В крипто-земле «выполнимый» означает «разумное количество времени по сравнению со стоимостью того, что я пытаюсь сломать», или, может быть, «меньше времени, которое потребуется, используя грубую силу», в зависимости от того, как вы смотрите на вещи.

Итак, если я смогу найти 1 столкновение реально, тогда я смогу найти n столкновений, потому что n*small все еще мало.

Там все еще будет некоторое n, где n*small > value of breakage.

Применимо ли это к другим хеш-функциям? Я верю в это, но я могу ошибаться.

Пусть начнется пламя.