Неожиданные события последних дней в криптоанализе хэш-функц
Неожиданные события последних дней в криптоанализе хэш-функций.
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, а проблема возникла в другой части протокола.
Sorry – Rijmen не давал интервью, это кто-то другой.
Уже слухи и домыслы стали появляться :-)
Время все расставит по своим местам конечно. Пока это "Breaking news"...
Но убедиться в коллизиях каждый может уже на своем компьютере по примерам из ссылок
комментариев: 11558 документов: 1036 редакций: 4118
Стараюсь по мере возможностей и неугасающего интереса к этой теме
Watch history being made
This year, the CRYPTO 2004 Rump session, including the aforementioned paper on MD5, will be webcast live.
Телесериал с прямой трансляцией из Санта-Барбары: :-)
http://www.iacr.org/conferences/crypto2004/rump.html
http://www.rtfm.com/movabletype/archives/2004_08.html
Фантазии на тему:The effect of a break in SHA-1
Кажется, вся Санта-Барбара только об этом и говорит.
комментариев: 11558 документов: 1036 редакций: 4118
http://www.rtfm.com/movabletype/archives/2004_08.html
...and at the end of his full talk this morning Eli Biham said "we're not close to breaking SHA-1 with this"...
^ За достоверность вышеприведенных слов не ручаюсь... Это так, для поддержания интереса к событиям.
Пока что это слухи, надо ждать официальных заявлений.
Вероятно подмножество коллизий ограничено и непрактично в реальных ситуациях.
Но теперь, по-крайней мере md5 не может считаться криптостойкой...
RIPEMD была спроектирована с двойной независимой обработкой данных в раунде и тоже, вероятно,
уязвима. Целый класс даже конструктивно разных функций уязвим к новым методам криптоанализа.
И какой быстрый прогресс за один месяц!
... А область применения хэш-функций велика – и разворачивание подключей в SSL, и проверка подлинности ключей PGP...
Ждем дальнейшего развития событий и комментариев криптографов.
http://zdnet.ru/?ID=455410
комментариев: 11558 документов: 1036 редакций: 4118
[quote:330967b894="Jon Callas at CRYPTO'2004 rump session"]I'm still at Crypto. SHA-1 is still safe. There have been a lot of
unconfirmed reports about all sorts of things.
The bottom line is that SHA-1 is the most analyzed, still-safe hash
function we have. That is also the bad news. There needs to be a lot
more work on hash functions. However, none of the attacks we learned of
this week apply to SHA-1.
]>
Antoine Joux (DCSSI Crypto Lab) пытается привести доказательство ненадежности и возможной подделки значений во ВСЕХ современных алгоритмов хэширования.
Если для нахождения коллизии в одном блоке и придется затратить 2^(n/2) операций, то для подделки
следующего блока их нужно будет всего 2*(2^(n/2)), а не 2^(n*3/4) как для истинно случайных функций.
Использование сложений разных хэшей H(x) = SHA1(x) || RIPEMD160(x) не усиливает стойкости!
(на этот подход надеялись разработчики OpenSSL и HMAC).
Суммарная стойкость отанется (160/2) бит, а не (320/2), как считалось ранее. А если SHA1 будет иметь реальную стойкость < заявленной?
Пока работы не опубликованы, споры кипят...
functions. Application to cascaded constructions"
SHA {224, 256, 384, 512} тоже могут быть уязвимы! Первая работа по их криптоанализу:
"On Corrective Patterns for the SHA-2 Family"
in any way, merely that further study of the data expansion function is
necessary.
http://eprint.iacr.org/2004/207.pdf
Большая длина выходного блока не является панацеей в плане криптозашиты хэш-функций, если их
конструкция несовершенна.
"Multicollisions in iterated hash
functions. Application to cascaded constructions"
Собственно, здесь была представлена эта работа, только 18 августа.
http://www.unixwiz.net/techtip.....e-crypto-hashes.html
P. S.
В общем, пока техники нахождения таких коллизий, не затрагивают ни HMAC, ни SSL, ни PGP...
комментариев: 11558 документов: 1036 редакций: 4118
Why new isn't necessarily better when it comes to encryption