Неожиданные события последних дней в криптоанализе хэш-функц
Неожиданные события последних дней в криптоанализе хэш-функций.
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, а проблема возникла в другой части протокола.
комментариев: 510 документов: 110 редакций: 75
Можно ли в качестве специально сформированных данных рассматривать к примеру осмысленные блоки текста на определенном языке (как частный случай) и пытаться найти одинаковый хеш-выход для другого осмысленного текста? По видимому это много труднее, чем найти неосмысленную коллизию, но ведь именно это уже произошло с MD5? Насколько может быть далека такая перспектива для SHA-1?
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
http://eprint.iacr.org/2006/105.pdf
Описание: http://cryptography.hyperlink.cz/2006/trick.txt
Из трёх файлов можно получить три других с таким же MD5-хэшем за минуту.
Если их упаковать получаем два архива с разными файлами и одним хэшем.
комментариев: 232 документов: 17 редакций: 99
Взлом хэш-функции подразумевает решение задачи: "нахождение файла по заданому хэшу".
комментариев: 9796 документов: 488 редакций: 5664
Атака первого прообраза: нахождение такого m, что hash(m)=h при известном h и неизвестном m.
Атака втрого прообраза: нахождение такого m2, что hash(m2)=hash(m1) при известном и наперёд заданном (фиксированном) m1 и неизвестном m2.
Это отличается от описанных выше атак коллизий: нахождение случайной (из заранее неизвестных m1 и m2) произвольной пары: hash(m2)=hash(m1)
Ваш случай – это атака первого прообраза, одна из наиболее сложных и наименее вероятных.
комментариев: 1515 документов: 44 редакций: 5786
прорыв в архивации ;)
Можно показать что это невозможно в общем случае. Количество информации в md5
и в исходном файле разное потому что. Это так же как нельзя в литровую банку воды заархивировать 2 литра воды...
комментариев: 11 документов: 0 редакций: 0
p.s. конечно тут всё зависит от длины исходного файла. 4байта элементарно восстановить из их md5, а 1mb нереально.
А по поводу коллизий- я в общем не силён в комбинаторике, но по логике рассуждая: количество всех различных вариантов hash 64байта меньше(можно посчитать насколько, но лень :) ), чем количесво всех вариаций даже килобайтного файла(1024!(факториал) ), а раз так, то какие-то вариации этого самого килобайтного файла дают один хеш( (1024-64)!(факториал) )) )......но коллизии то в любом хеше могут быть, он же в общем случаее меньше исходного документа. Вопрос в их вероятности возникновения и их применимости. Вряд ли 2 осмысленных(или тем более зашифрованных) теста могут дать один хеш, вот если условие в том, что можно на любых наборах байтов проверять, то когда-нибудь такую коллизию найдут, но в этом ничего такого нет. Вот если бы нашли к осмысленному тексту другой осмысленный( хотя может есть тут практический толк и от бессмысленного набора байт, то и его тоже) текст, которые дают один хеш, тогда это был бы провал ЦП.
p.p.s. я мог(а так он видимо и есть) полностью неправилно написать вычисление комбинаций, поправьте меня, но ведь в общем то вывод правильный? Хеш подразумевает коллизии?
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 1515 документов: 44 редакций: 5786
©http://forum.insidepro.com/viewtopic.php?t=1048
На том форуме много подобных примеров. Я совсем запутался, так что, всё уже? Даже сложные 10-тизначные пароли восстанавливают нахаляву по хэшу?
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 1515 документов: 44 редакций: 5786
комментариев: 9796 документов: 488 редакций: 5664
Только возможно для ваших целей не совсем то. Это оба файла должны быть заготовлены одним и тем же человеком. У них будет одинаковый первый блок.
Кроме того все поддельные хэши можно выявить по известным дифференциалам (правда периодически находят новые)