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

Question

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

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

Я нахожу большинство примеров MD5 "сломанной" менее интересно. Даже известный взлом сертификата CA была атака столкновения, означавшая, что доказано, что партия генерировала ХОРОШИЕ и ЗЛО сертификаты одновременно. Это означает, что, если ЗЛО СА появилось в дикой природе, можно утверждать, что оно просочилось от человека, у которого был хороший СА, и, таким образом, ему все равно доверяли.

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

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

Answer 1

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

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

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

Answer 2

Мы не знаем.

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

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

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

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

Answer 3

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

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

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