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

Question

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

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

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

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

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

бы не

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

1. MD (M + | M |) =
XYZ
2. MD (M + | M | + | M | * magicseed_0 + ... + | M | * magicseed_n) = хуг

где:

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

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

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

1. Это не только порождает тот же MD
2. Но также приемлем/parsible/совместимый
3. , а также того же размера, что и исходное сообщение,

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

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

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

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

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, который указывает, что они должны интерпретироваться как комментарии. Подпись в сертификате определяется как над представлением DER всей структуры tbsCertificate (сертификат «быть подписанным»), который включает все дополнительные атрибуты.

Конструкция хэш-функции - довольно глубокая теория, и ее можно было бы лучше обслуживать на the Theoretical CS Stack Exchange.

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

EDIT: Включение длины сообщения в конечный блок хэш-функции будет эквивалентно прилагая длину всего, что было раньше в сообщение ввода, так что нет никакой реальной необходимости изменить хэш-функцию, чтобы сделать это само по себе; скорее, укажите его как часть использования в данном контексте. Я могу видеть, что это может привести к тому, что некоторые типы конфликтов столкновения будут сложнее, так как если вы измените длину сообщения, появится измененное поле «ниже по течению» области, измененной атакой. Однако это не обязательно будет препятствовать X.509 intermediate CA forgery attack, поскольку длина tbsCertificate не изменяется.