Неожиданные события последних дней в криптоанализе хэш-функц
Неожиданные события последних дней в криптоанализе хэш-функций.
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
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, а проблема возникла в другой части протокола.
комментариев: 9796 документов: 488 редакций: 5664
Хэши на основе блочных шифров – скорее редкое исключение. В качестве "ключа" используют всякие функции от исходного текста "длину", "свертки" и т.д.
комментариев: 11558 документов: 1036 редакций: 4118
Для третьего варианта предлагаю анимацию Flash. Или видео в mpeg-формате.
комментариев: 9796 документов: 488 редакций: 5664
Музыкальный видеоклип. Или голливудский блокбастер с мировым прокатом. Русский перевод: "Сталкивающий цифровые миры".
комментариев: 11558 документов: 1036 редакций: 4118
События фильма происходят в недалёком будущем, когда Китай, претендуя на нынешнюю роль США единственной сверхдержавы засылает в Штаты кибертеррористку, исвестную лишь под прозвищем "Ван". Китайское коммунистическое правительство ставит перед ней одну партийную задачу: развалить порождение Америки — интернет — и лишить страну доходов от высокотехнологической отрасли. Агенты АНБ отважно противостоят этим коварным планам и используют секретную атаку Нострадамуса, чтобы выяснить, с какого компьютера она внедрит в интернет свой разрушительный вирус MD5 и схватить её в последние минуты фильма. Злодеи повержены, хорошие парни победили, ура!
комментариев: 9796 документов: 488 редакций: 5664
Спрашивается, а мы чем хуже?
комментариев: 1 документов: 0 редакций: 0
ЗЫ: если на то пошло, то матрица по Гибсону сделана...
комментариев: 9796 документов: 488 редакций: 5664
http://www.links.org/?p=19
Новый метод поиска по заявлениям авторов позволяет осуществить более быстрое и простое нахождение коллизий.
комментариев: 32 документов: 0 редакций: 0
Насколько я понял, там не столько поиск коллизий сколько "подгонка" существующих под конкретные нужды (дискредитация Diffie-Hellman).
А вот здесь выложены сорцы на C для поиска коллизий в MD4 и MD5 по заданному IV: MD5 Collision Generation.
Как утверждается, коллизия в MD5 находится всего лишь за 45 минут на 1.6 GHz P4.
комментариев: 11558 документов: 1036 редакций: 4118
С сайта проекта HashClash можно загрузить реализацию нового алгоритма поиска MD5 Collision Generator (в исходном коде и скомпилированную для Win32). Статья, описывающая теоретическую часть работы, должна появится в Cryptology ePrint Archive в ближайшее время.
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 32 документов: 0 редакций: 0
комментариев: 510 документов: 110 редакций: 75
Идем далее, для подтверждения слабости хеш-функции необходимо провести некоторое количество испытаний, число которых должно быть не менее некоторого значения, позволяющего применить теорию вероятности и на основе испытаний сделать вывод о том, что коллизий существует большее количество, чем должно быть (здесь возможно ошибаюсь). Либо, что еще лучше, математически обнаружить пробел в устройстве функции, позволяющий с достаточной уверенностью сказать – данная функция не соответствует критериям криптостойкости и с высокой подтверждаемостью находить коллизии на единичных примерах испытаний ранее, чем через 2^n/2 операций.
SHA-1 была взломана вторым методом? Насколько подтверждены эти данные (если это требуется) в случае испытаний большого количества случайных примеров нецеленаправленным методом поиска (обычным перебором)?
комментариев: 11558 документов: 1036 редакций: 4118
Да. Приведено математическое доказательство. Непосредственно попыток его подтверждения мне неизвестно. Но Вы должны учесть логичность математической теории. В отличие от физики, она обычно не требует подтверждения доказательств опытным путём. Зачастую это просто невозможно.
В остальном Ваши рассуждения верны. Общее пространство ключей (или хэш-значений) определяет верхний предел ресурсозатрат, необходимых для полного перебора всех вариантов. Но ничто не мешает, ткнув пальцем в небо, угадать искомый вариант в первую минуту поиска. В то же время, вероятность такого исхода равносильна тому, что Вы, читая эти слова, будете убиты молнией и задавлены метеоритом: она существует, но ничтожно мала.
комментариев: 9796 документов: 488 редакций: 5664
Да, но речь не о статистических испытаниях, а о целенаправленных атаках, не со случайными, а со специально сформированными данными. Речь об атаках, основанных на знании дефектов внутреннего устройства функции.
Хорошо бы подтвердить, но атака на SHA-1 на грани практических вычислительных возможностей. Это убедительный теоретический взлом, пока что не более.
Еще раз повторюсь – это не статистическая атака и она не требует статистического подтверждения. Для нахождения коллизий используются не случайные пары данных, а специально сформированные, с учётом знания констант и раундовых функций.
Если известно, как искать коллизии, то уже не важно статистически идеальна функция или нет.
Неважно, насколько случайно, непредсказуемо и статистически равномерно заложены мины в поле, если у вас есть хороший миноискатель. Ведь с ним в руках вы уже не будете искать их методом случайного тыка?
Грубо говоря, найдена конструкция такого "миноискателя", который немного лучше, чем "случайный тык", "грубая сила", но для его испытаний всё равно потребуется нереально много машинного времени.
Теория построения псевдослучайных функций была изложена Goldreich, Goldwasser и Micali ещё в 1986 году и к моменту создания SHA-1 была хорошо известна и использовалась для моделирования хэш-функций в том числе.
SHA-1 была вскрыта на основе развития дифференциального криптоанализа, а не прямым доказательством того, что она не является псевдослучайной функцией.