Неожиданные события последних дней в криптоанализе хэш-функц

Неожиданные события последних дней в криптоанализе хэш-функций.

1996 г. – Доббертин открыл частичные коллизии MD5 c измененным вектором
инициализации (атака не имеет практического значения, но свидетельствует
о некоторой нестойкости).

2004.07.12 – обещают премию 10000$ за нахождение полной коллизии MD5
http://www.certainkey.com/news/?12

2004.07.22 – Бихам находит значительные предколлизии в sha0
(sha1 отличается только одним циклическим сдвигом)
http://eprint.iacr.org/2004/146
Статья наделала много шума...

2004.08.12 – Antoine Joux(*) (DCSSI Crypto Lab)
Patrick Carribault (Bull SA)
Christophe Lemuet, William Jalby
(Universit'e de Versailles/Saint-Quentin en Yvelines)

http://www.md5crk.com/sha0col/

находят коллизию для sha0 за 2^50 операций и 50000
часов машинного времени.

2004.08.16
создатель AES-Rijndael в специальном интервью предупреждает о серьезных
проблемах, если
взлом хэш-функций подвердится – цифровые подписи, сертификаты,
многие банковские протоколы будут недействительны.
(эту ссылку я где-то потерял :-(.

http://www.freedom-to-tinker.com/archives/000661.html

2004.08.16 – Китайцы нашли способ найти коллизии в MD5 за 15 сек – 5 мин
на PC
file http://eprint.iacr.org/2004/199.pdf

За 2^6 операций "взламывается" HAVAL и RIPEMD.
MD4 "взламывается" на калькуляторе или на бумаге.

http://www.tcs.hut.fi/~mjos/md5/
http://www.freedom-to-tinker.com/archives/000662.html

2004.08.18 – китайцы выкладывают исправленную версию статьи выступают
на конференции rump Crypto-session. Идет прямая трансляция в Интернете.
Обещают "взломать" SHA-1 – нужно только незначительно переделать алгоритм.
http://www.iacr.org/conferences/crypto2004/rump.html

Простите за некоторые неточности и сумбурность обзора – все события интересны тем, что
происходят в реальном времени.

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

На основе SHA был создан шифр SHACAL, который прошел конкурс крипто-NESSI.
Какова будет теперь судьба некоторых блочных (и потоковых) шифров, если
у считавшихся стойкими хэш-функций найдены дифференциальные характеристики,
распространяющиеся через все раунды?

Но если дело так и дальше пойдет... то можно будет легко подделывать
цифровые сертификаты, ключи PGP, подписи.

Все боялись краха RSA, а проблема возникла в другой части протокола.

На страницу: 1, 2, 3, 4, 5 След.

Комментарии

—	*Гость* (31/08/2005 19:14) <#>

Где-то я читал, что хеши строятся на основе обычных криптоалгоритмов. Как так получается, в алгоритме есть вход – открытый текст, выход – закрытый текст и ключ, т.е. 3 составляющие, а в хеше только 2 составляющие, вход и выход. Что подразумевается в случае хешей под третьей составляющей, если они строятся на основе известных шифров?

—	unknown (01/09/2005 08:57) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Могут строиться (ГОСТ), а могут и не строиться (md5, SHA).
Хэши на основе блочных шифров – скорее редкое исключение. В качестве "ключа" используют всякие функции от исходного текста "длину", "свертки" и т.д.

—	SATtva (01/09/2005 15:33) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Ещё одна визуализация коллизии MD5:

Для третьего варианта предлагаю анимацию Flash. Или видео в mpeg-формате.

—	unknown (01/09/2005 15:48) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Или видео в mpeg-формате.

Музыкальный видеоклип. Или голливудский блокбастер с мировым прокатом. Русский перевод: "Сталкивающий цифровые миры".

—	SATtva (11/09/2005 13:56) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Или голливудский блокбастер с мировым прокатом. Русский перевод: "Сталкивающий цифровые миры".

События фильма происходят в недалёком будущем, когда Китай, претендуя на нынешнюю роль США единственной сверхдержавы засылает в Штаты кибертеррористку, исвестную лишь под прозвищем "Ван". Китайское коммунистическое правительство ставит перед ней одну партийную задачу: развалить порождение Америки — интернет — и лишить страну доходов от высокотехнологической отрасли. Агенты АНБ отважно противостоят этим коварным планам и используют секретную атаку Нострадамуса, чтобы выяснить, с какого компьютера она внедрит в интернет свой разрушительный вирус MD5 и схватить её в последние минуты фильма. Злодеи повержены, хорошие парни победили, ура!

—	unknown (11/09/2005 20:12) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

А что, сценарий к "Матрице" кажется написали "по приколу" двое каких-то людей, которые 15 лет до этого работали малярами-штукатурами.
Спрашивается, а мы чем хуже?

—	JUmPER (28/09/2005 10:49) профиль/связь <#> комментариев: 1 документов: 0 редакций: 0

давайте не будем сильно от темы отклоняться...
ЗЫ: если на то пошло, то матрица по Гибсону сделана...

—	unknown (25/10/2005 22:17) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Новый метод поиска коллизий в MD5

http://www.links.org/?p=19

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

—	RElf (10/03/2006 09:15) профиль/связь <#> комментариев: 32 документов: 0 редакций: 0

unknown:
Новый метод поиска коллизий в MD5

http://www.links.org/?p=19

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

Насколько я понял, там не столько поиск коллизий сколько "подгонка" существующих под конкретные нужды (дискредитация Diffie-Hellman).

А вот здесь выложены сорцы на C для поиска коллизий в MD4 и MD5 по заданному IV: MD5 Collision Generation.
Как утверждается, коллизия в MD5 находится всего лишь за 45 минут на 1.6 GHz P4.

—	SATtva (18/03/2006 08:13) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Продолжая развивать и оптимизировать методику поиска коллизий в MD5, предложенную Wang, студент университета TUE Marc Stevens сделал возможным нахождение пары блоков за время от нескольких секунд до нескольких минут на обычном ПК.

С сайта проекта HashClash можно загрузить реализацию нового алгоритма поиска MD5 Collision Generator (в исходном коде и скомпилированную для Win32). file

Статья, описывающая теоретическую часть работы, должна появится в Cryptology ePrint Archive в ближайшее время.

—	SATtva (19/03/2006 21:29) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

В то же самое время известный криптограф Властимил Клима опубликовал собственную новую работу file

"Tunnels in Hash Functions: MD5 Collisions Within a Minute" с соответствующим file

программным кодом. "Коллизии" случаются и у исследователей, а не только у хэш-функций. :)

—	RElf (21/03/2006 21:46) профиль/связь <#> комментариев: 32 документов: 0 редакций: 0

Ну и до кучи: file

MD5 Toolkit для нахождения коллизий в MD5 и освоения технологии как таковой от John Black, Martin Cochran и Trevor Highland. Теория изложена в их статье file

"A Study of the MD5 Attacks: Insights and Improvements".

—	Вий (26/03/2006 16:02) профиль/связь <#> комментариев: 510 документов: 110 редакций: 75

К примеру у хеш-функции нашли коллизию ранее, чем через 2^n/2 проведенных проверок, где n разрядность выходного значения функции. Вопрос вот в чем. Как известно каждая хеш-функция имеет обязательное множество коллизий. Значит есть вероятность того, что коллизия может встретится ранее, чем через 2^n/2 проведенных проверок так же должна существовать. Ведь и при поиске нужного ключа для расшифровки информации можно найти его ранее (если повезет), чем через n^2 количества проверок, где n-разрядность ключа. Теория вероятности применима к множеству случаев, среднее значение которых является результатом ее функций в том или ином случае, в то же время множество частных случаев может сильно отличаться от последнего.
Идем далее, для подтверждения слабости хеш-функции необходимо провести некоторое количество испытаний, число которых должно быть не менее некоторого значения, позволяющего применить теорию вероятности и на основе испытаний сделать вывод о том, что коллизий существует большее количество, чем должно быть (здесь возможно ошибаюсь). Либо, что еще лучше, математически обнаружить пробел в устройстве функции, позволяющий с достаточной уверенностью сказать – данная функция не соответствует критериям криптостойкости и с высокой подтверждаемостью находить коллизии на единичных примерах испытаний ранее, чем через 2^n/2 операций.
SHA-1 была взломана вторым методом? Насколько подтверждены эти данные (если это требуется) в случае испытаний большого количества случайных примеров нецеленаправленным методом поиска (обычным перебором)?

—	SATtva (26/03/2006 17:01) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

SHA-1 была взломана вторым методом?

Да. Приведено математическое доказательство. Непосредственно попыток его подтверждения мне неизвестно. Но Вы должны учесть логичность математической теории. В отличие от физики, она обычно не требует подтверждения доказательств опытным путём. Зачастую это просто невозможно.

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

—	unknown (26/03/2006 18:34) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Либо, что еще лучше, математически обнаружить пробел в устройстве функции, позволяющий с достаточной уверенностью сказать – данная функция не соответствует критериям криптостойкости и с высокой подтверждаемостью находить коллизии на единичных примерах испытаний ранее, чем через 2^n/2 операций.
SHA-1 была взломана вторым методом?

Да, но речь не о статистических испытаниях, а о целенаправленных атаках, не со случайными, а со специально сформированными данными. Речь об атаках, основанных на знании дефектов внутреннего устройства функции.

Насколько подтверждены эти данные (если это требуется)

Хорошо бы подтвердить, но атака на SHA-1 на грани практических вычислительных возможностей. Это убедительный теоретический взлом, пока что не более.

в случае испытаний большого количества случайных примеров нецеленаправленным методом поиска (обычным перебором)?

Еще раз повторюсь – это не статистическая атака и она не требует статистического подтверждения. Для нахождения коллизий используются не случайные пары данных, а специально сформированные, с учётом знания констант и раундовых функций.

Если известно, как искать коллизии, то уже не важно статистически идеальна функция или нет.

Неважно, насколько случайно, непредсказуемо и статистически равномерно заложены мины в поле, если у вас есть хороший миноискатель. Ведь с ним в руках вы уже не будете искать их методом случайного тыка?

Грубо говоря, найдена конструкция такого "миноискателя", который немного лучше, чем "случайный тык", "грубая сила", но для его испытаний всё равно потребуется нереально много машинного времени.

Теория построения псевдослучайных функций была изложена Goldreich, Goldwasser и Micali ещё в 1986 году и к моменту создания SHA-1 была хорошо известна и использовалась для моделирования хэш-функций в том числе.
SHA-1 была вскрыта на основе развития дифференциального криптоанализа, а не прямым доказательством того, что она не является псевдослучайной функцией.

На страницу: 1, 2, 3, 4, 5 След.

Ваша оценка документа [показать результаты]