Столкновение Атаки, Дайджесты сообщений и возможное решение

Question

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

Из того, что я могу сказать в случае атаки postScript, были сгенерированы конкретные данные, которые были встроены в заголовок файла postscript (который игнорируется во время рендеринга), что привело внутреннее состояние md5 к состоянию, так что измененная формулировка документа приведет к окончательному значению MD, эквивалентному исходному файлу postscript. В X.509 использовался аналогичный подход, когда данные вводились в разделы комментария / пробела в сертификате.

Итак, вот мой вопрос, и я не могу найти никого, кто задает этот вопрос:

1. Почему длина ТОЛЬКО потребляемых данных не добавляется как последний блок к вычислению MD?

2. В случае X.509 - Почему пробел и комментарии учитываются как часть MD?

Разве простых процессов, таких как один из следующих, будет недостаточно для разрешения предложенных атак на столкновения:

1. MD (M + | M |) = xyz
2. MD (M + | M | + | M | * magicseed_0 +... + | M | * magicseed_n) = xyz

где:

1. М: это сообщение
2. |M|: размер сообщения
3. MD: функция дайджеста сообщения (например, md5, ша, джакузи и т. Д.)
4. xyz: является сопряжением актуального значения дайджеста сообщения для сообщения M и | M |. <М, | M |>
5. magicseed_ {i}: набор случайных значений, созданных с помощью seed на основе внутреннего состояния перед добавлением размера.

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

Короче говоря, уровень сложности, связанный с генерацией сообщения о столкновении, такой, что:

1. Он не только генерирует тот же MD
2. Но также является приемлемым / понятным / совместимым
3. а также тот же размер, что и оригинальное сообщение,

это очень сложно, если не почти невозможно. Обсуждается ли когда-либо этот подход? Любые ссылки на документы и т. Д. Было бы хорошо.

Следующий вопрос: Какова нижняя граница для коллизий сообщений общей длины для хэш-функции H, выбранной случайным образом из U, где U - множество универсальных хеш-функций?

Это 1/N (где N 2^(|M|)) или больше? Если оно больше, это означает, что имеется более 1 сообщения длиной N, которое будет отображаться в одно и то же значение MD для данного H.

Если это так, насколько практично найти эти другие сообщения? bruteforce будет иметь значение O(2^N), есть ли метод временной сложности, меньший, чем bruteforce?

Answer 1

Не могу ответить на остальные вопросы, но первый довольно прост - добавление данных о длине на вход md5, на любой стадии процесса хеширования (1-й блок, N-й блок, последний блок) просто изменяет вывод хэш. Вы не могли получить эту длину из выходной строки хеша впоследствии. Также немыслимо, что коллизия не может быть произведена из другой строки с точно такой же длиной, поэтому говорить "исходная строка была 17 байтов" не имеет смысла, потому что сталкивающаяся строка также может быть 17 байтов.

например

md5("abce(17bytes)fghi") = md5("abdefghi<long sequence of text to produce collision>")

все еще возможно.

Answer 2

В частности, в случае сертификатов X.509 "комментарии" не являются комментариями в смысле языка программирования: это просто дополнительные атрибуты с OID, который указывает, что их следует интерпретировать как комментарии. Подпись на сертификате определяется как представление МЭД всего tbsCertificate ("быть подписанным" сертификатом) структура, которая включает в себя все дополнительные атрибуты.

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

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

РЕДАКТИРОВАТЬ: включение длины сообщения в последний блок хеш-функции будет эквивалентно добавлению длины всего, что было до этого, к входному сообщению, поэтому нет реальной необходимости изменять хеш-функцию, чтобы сделать это самостоятельно; скорее, укажите это как часть использования в данном контексте. Я вижу, где это может затруднить осуществление некоторых типов атак столкновений, поскольку, если вы измените длину сообщения, появится измененное поле "вниз по течению" от области, измененной атакой. Однако это не обязательно будет препятствовать атаке промежуточного CA X.509, поскольку длина tbsCertificate не изменяется