Неожиданные события последних дней в криптоанализе хэш-функц
Неожиданные события последних дней в криптоанализе хэш-функций.
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, а проблема возникла в другой части протокола.
Ссылки
[link1] http://www.unixwiz.net/techtips/iguide-crypto-hashes.html
[link2] http://www.pgp.com/resources/ctocorner/hashes.html
[link3] http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp
[link4] http://www.pgpru.com/forum/viewtopic.php?t=858
[link5] http://www.cits.rub.de/MD5Collisions/
[link6] http://www.cryptopro.ru/CryptoPro/doc/SHA-1_collision.pdf
[link7] http://www.stachliu.com/collisions.html
[link8] http://www.win.tue.nl/hashclash/
[link9] http://www.win.tue.nl/hashclash/fastcoll.pdf
[link10] http://eprint.iacr.org/
[link11] http://cryptography.hyperlink.cz/2006/tunnels.pdf
[link12] http://cryptography.hyperlink.cz/2006/program.zip
[link13] http://www.cs.colorado.edu/~jrblack/md5toolkit.tar.gz
[link14] http://www.cs.colorado.edu/~jrblack/papers/md5e-full.pdf
[link15] http://www.pgpru.com/comment3806
Sorry – Rijmen не давал интервью, это кто-то другой.
Уже слухи и домыслы стали появляться :-)
Время все расставит по своим местам конечно. Пока это "Breaking news"...
Но убедиться в коллизиях каждый может уже на своем компьютере по примерам из ссылок
Спасибо, unknown. Вы в курсе событий, держите и нас в них. Происходящее действительно заслуживает внимания.
Стараюсь по мере возможностей и неугасающего интереса к этой теме
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
Кажется, вся Санта-Барбара только об этом и говорит.
unknown, не могли бы Вы оставить какие-нибудь координаты для связи вне форума? Мои адреса есть в Контактах.
2004.08.18 "Bad day at the hash function factory"
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
Комментарий непосредственного участника презентативной сессии CRYPTO и CSO PGPCorp Джона Калласа:
[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.
]>
2004.08.20
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 будет иметь реальную стойкость < заявленной?
Пока работы не опубликованы, споры кипят...
Эта работа называется "Multicollisions in iterated hash
functions. Application to cascaded constructions"
2004.08.22
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
Большая длина выходного блока не является панацеей в плане криптозашиты хэш-функций, если их
конструкция несовершенна.
http://www.iacr.org/conferences/crypto2004/program.html
"Multicollisions in iterated hash
functions. Application to cascaded constructions"
Собственно, здесь была представлена эта работа, только 18 августа.
красивые картинки...для интересующихся.
http://www.unixwiz.net/techtip.....e-crypto-hashes.html[link1]
P. S.
В общем, пока техники нахождения таких коллизий, не затрагивают ни HMAC, ни SSL, ни PGP...
В поддверждение P. S. unknown — статья Джона Калласа (в представлении, надеюсь, не нуждается), посвящённая итогам rump session и оценке событий применительно к PGP.
Why new isn't necessarily better when it comes to encryption[link2]
Возможно, разработчики SHA-224 и SHA-348 использовали кое-что, чтобы защитить их от ставших недавно известными методов криптоанализа. Удвоение функции сжатия в одном раунде не просто увеличивает размер выхода хэш-функции, но и делает ее более стойкой к отысканию внутренних коллизий.
(Вот что значит закрытый дизайн по критериям проектирования, хотя код и открыт – спросить не с кого, все только ломают голову над тем, чтобы это все значило?).
http://eprint.iacr.org/2004/253.pdf
Хотелось бы узнать мнение сообщества (на русском :)) по поводу практических последствий реального(?) взлома MD5 и очень вероятного потенциального взлома SHA-1.
MD5 – это практически все пароли (в ОС в том числе) и цифровые подписи. Например, цифровая подпись и парольная защита секретного ключа во внутренней реализации OpenPGP в составе Bat'а.
SHA-1 – это цифровая подпись в последних версиях оригинального PGP и GnuPG. Насчёт парольной защиты секретного ключа – не знаю, но предполагаю.
Вообще, насколько надёжна парольная защита секретного ключа в PGP?
Какие последствия для протоколов шифрования трафика TLS/SSL/SSH ?
Ответ о последствиях взлома можно дать, только определившись, что понимается под "взломом". Взлом хэш-функции может проходить по двум направлениям: получение коллизий и восстановление прообраза. Свободное получение коллизий означает полный крах современной системы ЭЦП. Свободное восстановление прообразов — крах систем аутентификации, основанных на хэшированных паролях. Всё, что известно на данный момент, касается только коллизий. О свободе выработки речи не идёт — удаётся получать идентичных хэш для некоторых одиночных входных блоков.
http://www.pgpru.com/faq/tech.htm#pgptech_6
Как было сказано, если будет предложен способ свободного нахождения коллизий, то для подпротоколов аутентификации последствия будут самыми плачевными. На шифровании, как таковом, это едва ли скажется. Таким образом, даже при самом пессимистичном развитии событий большого риска не возникает. Спуфинг и атаки "человек в середине" для трафика реального времени не видятся мне первостепенными угрозами просто из-за сложности их проведения.
1). Коллизии сами по себе не такие уж безобидные явления. Многие криптоаналитические атаки на блочные шифры основаны на отыскании (пред) коллизий среди хотя бы нескольких раундов. Если мы можем сгенерировать два разных подобранных открытых текста, которые через несколько раундов дают нам похожее значение на выходе функции шифрования, мы можем начать отыскивать раундовые подключи. А если ключевое расписание шифра слабое, тогда мы на основании этих данных можем определять некоторые биты основного ключа.
Атаки такого рода относятся к категории "sqare root based", потому что они помогают сократить число подобранных вариантов на квадратный корень. Одно дело, когда мы просто пассивно полагаемся на существование коллизий, другое дело, когда их можно создавать целенаправленно.
На основе хэш-функций было создано некоторое количество шифров, возможно они окажутся менее стойкими, чем ожидалось. Правда такие шифры особого распространения не получили.
2). В протоколах, аналогичных SSL, код аутентичности сообщения вычисляется через HMAC (эта функция в свою очередь основана на комбинации SHA-1 и MD5).
Но кроме этого, используется еще и аналогичная функция PRF, для получения псевдослучайных значений, из которых, например, генерируются сеансовые ключи. Если создать некоторую сложную коллизию, то значения выхода такой функции будут неслучайными.
Практического значения это вроде не имеет, ведь исходные случайные значения выбирает сам пользователь. Но для последующего криптоанализа это может пригодится.
3) Насчет "спуфинга" и атак "человек посредине". Все относительно. Да, сейчас проще взломать сервер через дыры в программном обеспечении, неправильные настройки, плохие пароли и т.д. Поэтому никто с такого рода атаками и не заморачивается.
Но то, что такие атаки сложные – это заблуждение. Уже давно существуют (и даже входят в состав некоторых Линукс-дистрибутивов) такие "админско-хакерские" утилиты как dsniff, sshmitm, webmitm. Примеры использования таких утилит разобраны на соотвествующих сайтах. Можете сами потренироваться в локальной сети и увидеть, как легко быть в роли Мэллори.
Это конечно не "мнение сообщества на русском", но здесь частично воспроизведена и исследована технология, которую использовал Wang для нахождения коллизий. Даны оценки сложности проведения реальных аттак.
Рассмотрены и атаки на HMAC с известным и неизвестным ключом.
Примерный результат такой, что подмножество коллизий очень ограничено, продемонстрированные блоки обладают определенной, специально сконструированной структурой и использовать их для того, чтобы вставить в какие-нибудь реальные файлы (документы или ключи) пока представляется мало возможным.
Пока этот взлом носит чисто лабораторный, сертификационный характер. Но для постепенного отказа от алгоритмов близких к MD5, этого конечно уже достаточно .
http://eprint.iacr.org/2004/264
Cryptology ePrint Archive: Report 2004/264
Musings on the Wang et al. MD5 Collision
Philip Hawkes and Michael Paddon and Gregory G. Rose
А они все пишут и пишут... Про нахождение прообразов. Вот и до подделки ключей недалеко. И про то, что сам метод, лежащий в основе SHA-подобных функций оказался уязвим и не соответствует необходимым теоретическим моделям.
Хотя все атаки конечно же чисто теоретические... Но впомним как быстро от недавних теоретических атак MD5 дело перешло к практике.
http://eprint.iacr.org/2004/304/
!!(green) Cryptology ePrint Archive: Report 2004/304
Second Preimages on n-bit Hash Functions for Much Less than 2^n Work
John Kelsey and Bruce Schneier
!!
http://eprint.iacr.org/2004/304.pdf
Анализ практических последствий взлома MD5:
http://www.doxpara.com/md5_someday.pdf
Подписи дистрибутивов, пароли, аудит файлов и много других протоколов с этой функцией становятся все более и более уязвимыми.
Авторы заявляют, что последствия взлома MD5 от теоретических могут быстро перейти к катастрофическим.
Скоро можно будет переименовать тему в "долгожданные события в криптоанализе хэш-функций"
Потихоньку дело движется в сторону криптоанализа SHA-1
http://eprint.iacr.org/2004/364/
NIST начинает процедуру[link3] по выведению SHA-1 из употребления. Процесс должен завершиться к 2010 году. На время перехода к новому стандарту рекомендуется использование алгоритмов семейства SHA-2.
Что же будет после :?: Более стойких аналогов мало и с быстродействием у них проблемы. К примеру Whirlpool очень медленная.
... И ещё, как это повлияет на существующие стандарты и протоколы, прежде всего в государственном секторе? Ведь тот же DSS может работать только с SHA-1.
Если бы в ближайшее время NIST объявил открытый конкурс, что-то вроде ASH — Advanced Hash Standard, то успел бы закончить как раз к намеченному сроку.
http://eprint.iacr.org/2005/067.pdf
Коллизии в MD5 и фальшивые подписи для сертификатов.
Побочная ветка о взломе SHA-1[link4]
Интересно. Я просто наблюдаю за развитием событий и обнаруживаю такую вещь. Вот к примеру есть алгоритм DES, хотя не только он конечно, который до сих пор так и не взломали (атаку грубой силой я не рассматриваю, знаю, что ей он уже открываем за пару дней на каком-нибудь Крее). А вот с хешами все как-то слабее получается, md5, Sha0, sha1... Это неудачное стечение обстоятельств или все таки объяснимо какими то закономерностями (например сложнее хеш хороший написать или что то еще)?
Мне думается – с шифрованием все таки понятно – это просто гигантское количество ключей… А с хешами? Есть алгоритм, который можно изучить, и даже не имея возможности из хеша восстановить начальное значение можно найти определенные закономерности по поиску определенных условий из блоков начальных данных, хотя бы примерно приближающий результат функции к искомому значению. Алгоритм то всегда один, а в шифровании ключи всегда разные и при выборе ключа качественный алгоритм выбирает действительно абсолютно случайный ключ.
Вот возьмем однонаправленную функцию. Я нахожусь на вершине горы, форма которой есть алгоритм hash-функции. Я кинул вниз камень (запустил хеш функцию). Этот камень ударился о другой камень, далее эти два камня ударились в следующие камни (провожу аналогию – на вход хеш функции поступили следующие строки текста) и через некоторое время и расстояние вниз полетела уже целая лавина разных камней, больших и маленьких, которые ударяясь друг о друга и о поверхность горы, организовали огромное число различных случайных комбинаций, действующих в свое время одна на другую в дико накопительной прогрессии. Это однонаправленная функция? Исходя из полученной в результате картины определить точно сам первый камень и куда я его бросил невозможно (возможно конечно, если сделать несоразмерное гигантское количество обратных вычислений по построенным моделям отскоков камней друг от друга, где начальными условиями будет являться местоположение камней после схода лавины и т.п. но это супер сложно и требует сильнейшей математической и исследовательской в данном случае по физическим свойствам камней подготовки, или же полным перебором разных вариантов), хотя результат очевиден, и этот результат получился по вполне очевидным причинам – камни вниз летели и ударялись друг о друга по законам физики, известным со школы, провожу аналогию – хеш считает то же по определенному алгоритму. Если бы лавина летела вниз на другой день, то и результат бы был другой, к примеру потому, что была бы другая температура окружающего воздуха (а значит другая упругость и крепость камней, соответственно другие отскоки камней друг от друга и т.п.), провожу аналогию – в тексте изменили одну букву.
Теперь о том, к чему я все это писал. Мы имеем совершенно определенную картину после схода лавины. Можно ли повторить эту картину. В точности нет, однако изучив общие закономерности полета камней можно построить хотя бы приближенную картину, и такие модели по видимому (по крайней мере я так думаю) существуют. Таким образом получаем, что для поиска коллизий нет смысла работать полным перебором, достаточно построить определенную модель работы функции, существенно сужающую количество начальных условий, по аналогии о нашей горе – построив определенную модель можно без большого труда определить зимой шла лавина или летом, поскольку начальные условия сильно отличны, а при более детальной проработке может определить и время суток к примеру.
//В целом для лучшего представления я конечно привел слишком упрощенную картину, можно было бы расписать все немного подробнее, например так, хотя это тоже упрощенно:
Количество камней на склонах горы – разрядность выходного значения hash функции (пусть к примеру у нас будет 1000 камней, для легкости представления можно представить, что это камни весом более 100 кГ, но остальные камни то же принимают участие в процессе)
Высота горы и ее форма – алгоритм hash функции,
Запуск функции – падение первого камня с определенным весом с высоты 100 метров точно на вершину горы, или куда-нибудь вблизи от нее.
Все остальное – входные параметры для hash функции (температура, плотность и влажность воздуха, неоднородность нагрева склонов горы солнечной энергией, данный параметр можно рассматривать не как один, а разложив его на многократные градации по поверхности, упругость и прочность пород, состояние растительности в различные промежутки времени года, наличие и вид атмосферных осадков и т.д, таких параметров может быть очень очень много).//
Никому не интересно? Было бы интересно почитать Ваши мнения.
Поскольку меня долго не было на форуме, попытаюсь ответить только сейчас.
В научно-популярных книгах по атомной физике электроны и орбитали часто представляют
в виде шариков или облачков. Но это просто наглядная модель для облегчения
понимания, на основе таких моделей никаких серьезных выводов делать нельзя.
Мне кажется, что представлять себе хэш-функцию как гору катящихся камней не вполне
продуктивно и может привести к необоснованным выводам. В криптографии такого рода
попытки были (привлекать физические, биологические и прочие аппараты и все они провалились).
Теории хаоса, которыми пытались моделировать лавины тоже кстати в криптографии как-то не прижились.
Зато все верно замеченные Вами тенденции вполне укладываются в рамки обычного криптоанализа.
"Взлом" хэш-функций произошел вполне традиционными методами дифференциального криптоанализа и
совсем не потому, что в хэшах "нет ключей", а потому что условие "коллизионной стойкости" слишком
строгое и трудно достижимое. О сомнительной коллизионной стойкости функции раунда было известно
еще в середине девяностых.
Хотя, в чем-то Ваши рассуждения интуитивно сходятся даже с серьезными работами в области криптографии
(насколько я могу об этом судить).
Например, создать стойкий потоковый шифр, намного сложнее, чем блочный.
Из-за того, что что ограниченную энтропию ключа пытаются использовать для выработки очень длинных
последовательностей, эти последовательности получаются не совсем случайными. Не с точки зрения
статистики, а сточки зрения криптоанализа можно доказать отличие такой последовательности
от случайной для многих потоковых шифров (random distinguisher attack) и с этим приходится мириться
(хотя шифр получается теоретически нестойким),
в то время как для блочных такие предварительные атаки намного сложнее.
В блочном шифре энтропия ключа и отчасти текста как-бы перемножаются.
Но текст обладает плохой энтропией и может себя выдать плюс всякие подобранные тексты и т.д.
В поточном работает только энтропия ключа.
В хэшах работает только энтропия текста, но зато выход хэша ограничен.
В каждом предложении описаны противодействующие друг другу факторы.
В каждом виде криптографического примитива есть свойства и облегчающие и затрудняющие
криптоанализ и вот-так умозрительно сказать, что перевесит в каждом конкретном случае трудно.
Можно сделать вывод на основе предшествующих научных исследований, мнений ведущих специалистов, дать прогноз на будущее.
Но однозначно на основе какой-то одной модели строить выводы нельзя. Тем более такой отвлеченной, как
гора камней. Мне еще встречались методы анализа криптопротоколов на основе "теории игр", но
это уже на грани "приемлемого". А если специалистам показать работу где хэш-функция будет
рассматриваться на основе хотя-бы математического описания физичесого процесса... Вроде
горы катящихся камней или лавины. Ну тут уж
надо быть или гением или идиотом (шутка :-), не принимайте слишком серьезно)
Вроде бы не новость (нашёл в предпоследнем выпуске шнайеровской Crypto-Gram), но в форуме не упоминалась. Исследователи из немецкого Института криптографии и ИТ-безопасности создали[link5] два разных документа Postscript с осмысленным содержанием, производящих идентичные хэш-значения MD5.
Вспомнил анекдот:
Экзамен в техническом ВУЗЕ. В чем измеряется сила тока? Вольтах, амперах или омах?
Экзамен в гуманитарном ВУЗЕ? А не в амперах ли измеряется сила тока? Да, нет, может быть.
Экзамен в военном училище? В чем измеряется сила тока? Да, нет, так точно.
Товарищи, если имеем дело с математикой, давайте забудим про философию.
Все гениальное просто, но не все простое гениально.
:-)
ГОСТ непобедим ?:
http://www.cryptopro.ru/Crypto...../SHA-1_collision.pdf[link6]
Действительно у ГОСТ-хэша больший запас прочности, но ... наличие S-блоков не гарантирует невозможности проведения DCA-атаки. Тогда уж предпочтительнее WHIRLPOOL, где есть метод точного расчета дифф. характеристик.
Тема развивается уже год, а ещё встречаются такие проявления бреда:
http://www.securitylab.ru/news/239725.php
"До свидания MD5"? Как говориться, здравствуй дерево!
Пароли с одинаковым хэшем на passcraking.com? "споры о целесообразности использования криптографических хеш функций."?
Ну еще парочка ляпов, но не так уж кошмарно. Было и хуже. Все таки пишут, что Шнайера читали.
Значит не даром была поднята тема о введении алгоритма ГОСТ в PGP.
Доброго времени суток!!!
Где то читал, что при помощи методов взлома хешей взламывают пароли, это писали про мд5. Не пойму, как это возможно, если пароль изначально не известен?
ГОСТ-хэш или ГОСТ-шифр? Я думаю они пока оба как "неуловимый Джо", которого никто не ловит. Конструкции, превращающие любой блочный шифр в хэш давно известны и не авторами ГОСТа скорее всего изобретены. Думаете все так просто? Никто не догадался взять стойкий блочный шифр и сделать из него стойкий хэш?
Чего ж тогда криптографы уже больше года что-то новое изобретают, когда все-так просто? От безделья наверное.
Все сообщения, которые мне лично пападались были безграмотными. Пока только можно подобрать коллизию, но не второй прообраз или инверсию хэша. Или взломщики паролей оказались умнее криптографов? Или кто-то путает простой bruteforce и поиск коллизий.
Не удивлюсь, если и это ненадолго.
Новый класс атак на хэш-функции – атака Нострадамуса при помощи бриллиантовых структур (не сойдите с ума в процессе чтения, буквально "крышу сносит") Можете превратится в Нострадамуса и похитителя кредитов на изобретения:
http://eprint.iacr.org/2005/281
Кому нужны тематические обои для рабочего стола (или еще куда)?
http://www.shmoo.com/md5-collision.html
"Предложите способ более быстрого поиска коллизий в MD5, и в подарок вы получите футболку с изображением внутреннего состояния алгоритма для коллизирующих блоков".
Так и представляю себе эту китаянку в футболке
http://www.infosec.sdu.edu.cn/people/wangxiaoyun.htm
Где-то я читал, что хеши строятся на основе обычных криптоалгоритмов. Как так получается, в алгоритме есть вход – открытый текст, выход – закрытый текст и ключ, т.е. 3 составляющие, а в хеше только 2 составляющие, вход и выход. Что подразумевается в случае хешей под третьей составляющей, если они строятся на основе известных шифров?
Могут строиться (ГОСТ), а могут и не строиться (md5, SHA).
Хэши на основе блочных шифров – скорее редкое исключение. В качестве "ключа" используют всякие функции от исходного текста "длину", "свертки" и т.д.
Ещё одна визуализация коллизии MD5:
Для третьего варианта предлагаю анимацию Flash. Или видео в mpeg-формате.
Музыкальный видеоклип. Или голливудский блокбастер с мировым прокатом. Русский перевод: "Сталкивающий цифровые миры".
События фильма происходят в недалёком будущем, когда Китай, претендуя на нынешнюю роль США единственной сверхдержавы засылает в Штаты кибертеррористку, исвестную лишь под прозвищем "Ван". Китайское коммунистическое правительство ставит перед ней одну партийную задачу: развалить порождение Америки — интернет — и лишить страну доходов от высокотехнологической отрасли. Агенты АНБ отважно противостоят этим коварным планам и используют секретную атаку Нострадамуса, чтобы выяснить, с какого компьютера она внедрит в интернет свой разрушительный вирус MD5 и схватить её в последние минуты фильма. Злодеи повержены, хорошие парни победили, ура!
А что, сценарий к "Матрице" кажется написали "по приколу" двое каких-то людей, которые 15 лет до этого работали малярами-штукатурами.
Спрашивается, а мы чем хуже?
давайте не будем сильно от темы отклоняться...
ЗЫ: если на то пошло, то матрица по Гибсону сделана...
Новый метод поиска коллизий в MD5
http://www.links.org/?p=19
Новый метод поиска по заявлениям авторов позволяет осуществить более быстрое и простое нахождение коллизий.
Насколько я понял, там не столько поиск коллизий сколько "подгонка" существующих под конкретные нужды (дискредитация Diffie-Hellman).
А вот здесь выложены сорцы на C для поиска коллизий в MD4 и MD5 по заданному IV: MD5 Collision Generation[link7].
Как утверждается, коллизия в MD5 находится всего лишь за 45 минут на 1.6 GHz P4.
Продолжая развивать и оптимизировать методику поиска коллизий в MD5, предложенную Wang, студент университета TUE Marc Stevens сделал возможным нахождение пары блоков за время от нескольких секунд до нескольких минут на обычном ПК.
С сайта проекта HashClash[link8] можно загрузить реализацию нового алгоритма поиска MD5 Collision Generator (в исходном коде и скомпилированную для Win32). Статья[link9], описывающая теоретическую часть работы, должна появится в Cryptology ePrint Archive[link10] в ближайшее время.
В то же самое время известный криптограф Властимил Клима опубликовал собственную новую работу "Tunnels in Hash Functions: MD5 Collisions Within a Minute"[link11] с соответствующим программным кодом[link12]. "Коллизии" случаются и у исследователей, а не только у хэш-функций. :)
Ну и до кучи: MD5 Toolkit[link13] для нахождения коллизий в MD5 и освоения технологии как таковой от John Black, Martin Cochran и Trevor Highland. Теория изложена в их статье "A Study of the MD5 Attacks: Insights and Improvements"[link14].
К примеру у хеш-функции нашли коллизию ранее, чем через 2^n/2 проведенных проверок, где n разрядность выходного значения функции. Вопрос вот в чем. Как известно каждая хеш-функция имеет обязательное множество коллизий. Значит есть вероятность того, что коллизия может встретится ранее, чем через 2^n/2 проведенных проверок так же должна существовать. Ведь и при поиске нужного ключа для расшифровки информации можно найти его ранее (если повезет), чем через n^2 количества проверок, где n-разрядность ключа. Теория вероятности применима к множеству случаев, среднее значение которых является результатом ее функций в том или ином случае, в то же время множество частных случаев может сильно отличаться от последнего.
Идем далее, для подтверждения слабости хеш-функции необходимо провести некоторое количество испытаний, число которых должно быть не менее некоторого значения, позволяющего применить теорию вероятности и на основе испытаний сделать вывод о том, что коллизий существует большее количество, чем должно быть (здесь возможно ошибаюсь). Либо, что еще лучше, математически обнаружить пробел в устройстве функции, позволяющий с достаточной уверенностью сказать – данная функция не соответствует критериям криптостойкости и с высокой подтверждаемостью находить коллизии на единичных примерах испытаний ранее, чем через 2^n/2 операций.
SHA-1 была взломана вторым методом? Насколько подтверждены эти данные (если это требуется) в случае испытаний большого количества случайных примеров нецеленаправленным методом поиска (обычным перебором)?
Да. Приведено математическое доказательство. Непосредственно попыток его подтверждения мне неизвестно. Но Вы должны учесть логичность математической теории. В отличие от физики, она обычно не требует подтверждения доказательств опытным путём. Зачастую это просто невозможно.
В остальном Ваши рассуждения верны. Общее пространство ключей (или хэш-значений) определяет верхний предел ресурсозатрат, необходимых для полного перебора всех вариантов. Но ничто не мешает, ткнув пальцем в небо, угадать искомый вариант в первую минуту поиска. В то же время, вероятность такого исхода равносильна тому, что Вы, читая эти слова, будете убиты молнией и задавлены метеоритом: она существует, но ничтожно мала.
Да, но речь не о статистических испытаниях, а о целенаправленных атаках, не со случайными, а со специально сформированными данными. Речь об атаках, основанных на знании дефектов внутреннего устройства функции.
Хорошо бы подтвердить, но атака на SHA-1 на грани практических вычислительных возможностей. Это убедительный теоретический взлом, пока что не более.
Еще раз повторюсь – это не статистическая атака и она не требует статистического подтверждения. Для нахождения коллизий используются не случайные пары данных, а специально сформированные, с учётом знания констант и раундовых функций.
Если известно, как искать коллизии, то уже не важно статистически идеальна функция или нет.
Неважно, насколько случайно, непредсказуемо и статистически равномерно заложены мины в поле, если у вас есть хороший миноискатель. Ведь с ним в руках вы уже не будете искать их методом случайного тыка?
Грубо говоря, найдена конструкция такого "миноискателя", который немного лучше, чем "случайный тык", "грубая сила", но для его испытаний всё равно потребуется нереально много машинного времени.
Теория построения псевдослучайных функций была изложена Goldreich, Goldwasser и Micali ещё в 1986 году и к моменту создания SHA-1 была хорошо известна и использовалась для моделирования хэш-функций в том числе.
SHA-1 была вскрыта на основе развития дифференциального криптоанализа, а не прямым доказательством того, что она не является псевдослучайной функцией.
Можно ли в качестве специально сформированных данных рассматривать к примеру осмысленные блоки текста на определенном языке (как частный случай) и пытаться найти одинаковый хеш-выход для другого осмысленного текста? По видимому это много труднее, чем найти неосмысленную коллизию, но ведь именно это уже произошло с MD5? Насколько может быть далека такая перспектива для SHA-1?
SHA и MD близки по конструкции. Методы криптоанализа для SHA были применены похожие, правда более сложные. И результат не такой практичный получился. Вот и делайте выводы о перспективах.
Обновление статьи
http://eprint.iacr.org/2006/105.pdf
Описание: http://cryptography.hyperlink.cz/2006/trick.txt
Из трёх файлов можно получить три других с таким же MD5-хэшем за минуту.
Если их упаковать получаем два архива с разными файлами и одним хэшем.
А можно ли получить файл имеющий наперёд заданный хэш? Например, есть хэш bbe2922d82c5e6e0eb00b12776c6c649 надо найти файл имеющий такой же хэш? Это возможно?
Взлом хэш-функции подразумевает решение задачи: "нахождение файла по заданому хэшу".
https://www.pgpru.com/Comment2419
Атака первого прообраза: нахождение такого m, что hash(m)=h при известном h и неизвестном m.
Атака втрого прообраза: нахождение такого m2, что hash(m2)=hash(m1) при известном и наперёд заданном (фиксированном) m1 и неизвестном m2.
Это отличается от описанных выше атак коллизий: нахождение случайной (из заранее неизвестных m1 и m2) произвольной пары: hash(m2)=hash(m1)
Ваш случай – это атака первого прообраза, одна из наиболее сложных и наименее вероятных.
Да если научаться восстанавливать исходный документ из md5(и др.) за приемлимое время – это же будет прорыв в архивации ;)
прорыв в архивации ;)
Можно показать что это невозможно в общем случае. Количество информации в md5
и в исходном файле разное потому что. Это так же как нельзя в литровую банку воды заархивировать 2 литра воды...
Я же там смайлик поставил!! В общем конечно нет смысла беспокоиться за подобный вид атаки, очень, очень врядли научаться восстанавливать исходный документ по hash. А то получиться, что строчка на обрывке бумажки может содержать восстановимые 5Гб текст/звука/видео и пр.
p.s. конечно тут всё зависит от длины исходного файла. 4байта элементарно восстановить из их md5, а 1mb нереально.
А по поводу коллизий- я в общем не силён в комбинаторике, но по логике рассуждая: количество всех различных вариантов hash 64байта меньше(можно посчитать насколько, но лень :) ), чем количесво всех вариаций даже килобайтного файла(1024!(факториал) ), а раз так, то какие-то вариации этого самого килобайтного файла дают один хеш( (1024-64)!(факториал) )) )......но коллизии то в любом хеше могут быть, он же в общем случаее меньше исходного документа. Вопрос в их вероятности возникновения и их применимости. Вряд ли 2 осмысленных(или тем более зашифрованных) теста могут дать один хеш, вот если условие в том, что можно на любых наборах байтов проверять, то когда-нибудь такую коллизию найдут, но в этом ничего такого нет. Вот если бы нашли к осмысленному тексту другой осмысленный( хотя может есть тут практический толк и от бессмысленного набора байт, то и его тоже) текст, которые дают один хеш, тогда это был бы провал ЦП.
p.p.s. я мог(а так он видимо и есть) полностью неправилно написать вычисление комбинаций, поправьте меня, но ведь в общем то вывод правильный? Хеш подразумевает коллизии?
/Comment3806[link15]
©http://forum.insidepro.com/viewtopic.php?t=1048
На том форуме много подобных примеров. Я совсем запутался, так что, всё уже? Даже сложные 10-тизначные пароли восстанавливают нахаляву по хэшу?
Скорее расчёт производился по рэйнбоу-таблицам (на том же сайте, который Вы сейчас рекламируете, есть такой сервис). Восстановить прообраз по хэш-значению профессионального алгоритма (не говорю стойкого — тут факторов должно быть соблюдено слишком много) невозможно.
Да, спасибо, я уже разобрался. Там перебор фактически был.
Ребята, поделитесь программкой, которая делала на используя коллизий md5 разные zip-файлы с одним хэшем. Она как-то пробегала на pgpru.com
http://cryptography.hyperlink.cz/MD5_collisions.html
Только возможно для ваших целей не совсем то. Это оба файла должны быть заготовлены одним и тем же человеком. У них будет одинаковый первый блок.
Кроме того все поддельные хэши можно выявить по известным дифференциалам (правда периодически находят новые)