Какое-либо опубликованное исследование указывает на неизбежность атак с прообразом на MD5?

Question

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

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

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

Что может быть гораздо более важным, это прообраз или вторая прообразная атака.

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

Мы не знаем.

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

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

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

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