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

Я провел предварительное исследование в области дайджестов сообщений. В частности, коллизионные атаки криптографических хэш-функций, таких как 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, sha, whirlpool и т. Д.)
  4. xyz: это пара значений фактического профиля сообщения для сообщения M и | 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?


cryptography math hash-collision message-digest
person Community    schedule 14.01.2011    source источник
comment
Поскольку это исследовательский / теоретический вопрос, вы можете перенести его на cstheory.stackexchange.com.   -  person Jeffrey Hantin    schedule 14.01.2011
comment
Только для 5 лучших альтернативных сайтов, к сожалению, cstheory не входит в их число. Но у меня есть для вас половина ответа.   -  person Jeffrey Hantin    schedule 14.01.2011

Ответы (2)


arrow_upward
0
arrow_downward

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

e.g.

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

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

person Marc B    schedule 14.01.2011

arrow_upward
0
arrow_downward

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

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

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

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

person Jeffrey Hantin    schedule 14.01.2011
comment
@Dominar: та же конструкция работает для случая X.509, где атрибуты, более или менее содержащие двоичные строки случайного мусора, могут быть включены в tbsCertificate - нераспознанные расширения будут игнорироваться большинством процессоров, если они не содержат флаг «должен понимать» , и этот флаг "должен понимать" является частью записи атрибута в сертификате, поэтому, конечно, злоумышленник не будет устанавливать этот флаг. - person Jeffrey Hantin; 15.01.2011
comment
@Dominar: Кроме того, принципиальная идея состоит в том, чтобы показать, что явное включение длины данных в хеш - не панацея. - person Jeffrey Hantin; 15.01.2011
comment
@Dominar: Это было бы равносильно добавлению длины сообщения к сообщению, не так ли? Следовательно, вам не придется изменять определение самой хеш-функции, а только ее использование. Я вижу, как это затруднит выполнение некоторых атак с коллизией: если вы измените длину сообщения, изменится входной поток ниже того, где вы настраиваете состояние хэша. Такое изменение не повлияет на атаку X.509, поскольку длина tbsCertificate не изменилась - см. win.tue.nl/hashclash/rogue-ca раздел 5.3. - person Jeffrey Hantin; 18.01.2011