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

Question

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

Из того, что я могу сказатьв случае атаки постскриптума, конкретные данные были сгенерированы и встроены в заголовок файла 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. M: это сообщение
2. | M |: размер сообщения
3. MD: функция дайджеста сообщения (например, md5, sha, гидромассажная ванна и т. д.)
4. xyz: спаривание значения дайджеста текущего сообщения для сообщения 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

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

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

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

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

Answer 2

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

, например

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

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