Проводится ли какое-либо опубликованное исследование о том, что нападения на MD5 на предизайне неизбежны?

Я продолжаю читать на SO, что MD5 сломан, перебор, устарел и никогда не будет использоваться. Это меня злит.

Дело в том, что атаки на столкновение на MD5 теперь довольно просты. У некоторых людей есть атаки на столкновение до искусства, и даже мы можем использовать их для предсказывать выборы.

Я нахожу большинство примеров MD5 "брокерство" менее интересным. Даже известный хакерский сертификат CA был атакой на столкновение, означающей, что его доказательство того, что сторона одновременно выдала сертификаты GOOD и EVIL. Это означает, что, если EVIL CA попадает в дикую природу, это доказывает, что он просочился от человека, у которого был хороший СА, и, таким образом, ему все равно доверяли.

То, что было бы намного больше связано с preimage или второй атакой на прообраз.

Насколько вероятна атака на MD5? Есть ли какие-либо текущие исследования, чтобы указать, что это неизбежно? Является ли тот факт, что MD5 уязвим для атак на столкновение, более вероятно, что он подвергнется атаке с помощью предпросмотра?

Ответ 1

В криптографии рекомендации обычно не делаются путем прогнозирования будущего, поскольку это невозможно сделать. Скорее криптографы пытаются оценить то, что уже известно и опубликовано. Чтобы адаптироваться к потенциальным будущим атакам, криптосистемы, как правило, разработаны таким образом, что существует некоторый запас прочности. Например. криптографические ключи обычно выбираются немного дольше, чем это абсолютно необходимо. По той же причине алгоритмы устраняются, когда обнаруживаются слабые места, даже если эти недостатки являются только сертификационными.

В частности, RSA Labs рекомендовал отказаться от MD5 для подписей уже в 1996 году после того, как Доббертин обнаружил столкновения в функции сжатия. Столкновения в функции сжатия не означают, что столкновений в хэш-функции существует, но мы не можем найти столкновений для MD5, если мы не можем найти столкновений для его функции сжатия. Таким образом, RSA Labs решили, что у них больше нет уверенности в сопротивлении столкновения MD5.

Сегодня мы находимся в подобной ситуации. Если мы уверены, что хеш-функция устойчива к столкновению, мы также можем быть уверены, что хеш-функция устойчива к прообразу. Но MD5 имеет значительные недостатки. Следовательно, многие криптографы (включая таких людей, как Арьен Ленстра) считают, что MD5 больше не имеет необходимого запаса прочности, который можно использовать даже в приложениях, которые полагаются только на сопротивление пропозиции и, следовательно, рекомендуют больше не использовать его. Криптографы не могут предсказать будущее (так что не ищите документы, которые делают именно это), но они могут рекомендовать разумные меры предосторожности против потенциальных атак. Рекомендация не использовать MD5 больше не является одной из таких разумных мер предосторожности.

Ответ 2

Мы не знаем.

Такое продвижение, как правило, приходит "внезапно" - кто-то делает теоретический прорыв и находит метод, который в 2 ^ 10 (или в любом другом) раз лучше предыдущего.

Кажется, что атаки на проприетар могут все еще быть немного далекими; a недавняя статья утверждает сложность 2 ^ 96 для прообраза на уменьшенной 44-раундовой версии MD5. Тем не менее, это не вопрос вероятности, а скорее ли кто-то достаточно умен, чтобы пойти на этот последний шаг и внести сложность для реальной сделки в реалистичную маржу.

Тем не менее, поскольку атаки на столкновение очень реальны (одна минута на типичном ноутбуке), а атаки с прообразом могут (или не могут ) быть не за горами, он, как правило, считал разумным переключиться на что-то более сильное, пока не стало слишком поздно.

Если столкновения не являются проблемой для вас, у вас может быть время подождать конкурс NIST SHA-3, чтобы придумать что-то новое. Но если у вас есть вычислительная мощность и запасные части, использование SHA-256 или аналогичных устройств, вероятно, является разумной мерой предосторожности.

Ответ 3

Криптографически устойчивое предварительное изображение MD5 уже нарушено, см. этот документ от Eurocrypt 2009. В этом формальном контексте "сломанный" означает быстрее, чем атаки грубой силы, т.е. Атаки со сложностью меньше (2 ^ 128)/2 в среднем. Сасаки и Аоки представили атаку со сложностью 2 ^ 123.4, которая, безусловно, является только теоретической, но каждая практическая атака основывается на менее сильной теоретической атаке, поэтому даже теоретический разрыв вызывает серьезные сомнения в ее среднесрочной безопасности. Интересно также, что они повторно используют много исследований, которые вступили в столкновения на MD5. Это красиво иллюстрирует Accipitridae, указывающие на то, что маржа безопасности MD5 при сопротивлении предварительного изображения исчезла с атаками столкновения.

Еще одна причина, по которой использование MD5 в 2009 году было, и теперь использование SHA1 сильно обескуражено для любого приложения, так это то, что большинство людей не понимают, какое точное свойство полагается на безопасность их использования. Вы, к сожалению, доказали мою точку зрения в своем вопросе, заявив, что атака CA в 2008 году не опиралась на провал сопротивления столкновению, как заметило caf.

Чтобы разработать бит, каждый раз, когда доверенный CA подписывает сертификат, он также подписывает, возможно, вредоносные данные, поступающие от клиента в форме запроса на подпись сертификата (CSR). Теперь в большинстве случаев все данные, которые будут подписаны, могут быть предварительно рассчитаны из CSR и некоторых внешних условий. Это приводит к фатальному побочному эффекту, в котором состояние хеш-функции будет находиться, когда оно будет хешировать, ненадежные данные, выходящие из CSR, полностью известны злоумышленнику, что облегчает атаку столкновения. Таким образом, злоумышленник может прекомпопировать CSR, который заставит ЦС хэш и подписать данные, которые имеют столкновение с теневым сертификатом, только известным злоумышленнику. ЦС не может проверить предварительные условия теневого сертификата, который он обычно проверяет перед подписанием (например, что новый сертификат не утверждает, что он является корневым сертификатом), поскольку он имеет доступ только к законным CSR, предоставленным злоумышленниками. Вообще говоря, как только у вас есть атаки на столкновение, а часть ваших данных контролируется злоумышленником, вы больше не знаете, что еще вы можете подписывать рядом с данными, которые вы видите.