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

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

http://eprint.iacr.org/2004/253.pdf

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

unknown:

http://www.rtfm.com/movabletype/archives/2004_08.html

Фантазии на тему:The effect of a break in SHA-1

Кажется, вся Санта-Барбара только об этом и говорит.

Хотелось бы узнать мнение сообщества (на русском :)) по поводу практических последствий реального(?) взлома MD5 и очень вероятного потенциального взлома SHA-1.

MD5 – это практически все пароли (в ОС в том числе) и цифровые подписи. Например, цифровая подпись и парольная защита секретного ключа во внутренней реализации OpenPGP в составе Bat'а.

SHA-1 – это цифровая подпись в последних версиях оригинального PGP и GnuPG. Насчёт парольной защиты секретного ключа – не знаю, но предполагаю.

Вообще, насколько надёжна парольная защита секретного ключа в PGP?

Какие последствия для протоколов шифрования трафика TLS/SSL/SSH ?

Хотелось бы узнать мнение сообщества (на русском Smile) по поводу практических последствий реального(?) взлома MD5 и очень вероятного потенциального взлома SHA-1.

Ответ о последствиях взлома можно дать, только определившись, что понимается под "взломом". Взлом хэш-функции может проходить по двум направлениям: получение коллизий и восстановление прообраза. Свободное получение коллизий означает полный крах современной системы ЭЦП. Свободное восстановление прообразов — крах систем аутентификации, основанных на хэшированных паролях. Всё, что известно на данный момент, касается только коллизий. О свободе выработки речи не идёт — удаётся получать идентичных хэш для некоторых одиночных входных блоков.

Вообще, насколько надёжна парольная защита секретного ключа в PGP?

http://www.pgpru.com/faq/tech.htm#pgptech_6

Какие последствия для протоколов шифрования трафика TLS/SSL/SSH ?

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

1). Коллизии сами по себе не такие уж безобидные явления. Многие криптоаналитические атаки на блочные шифры основаны на отыскании (пред) коллизий среди хотя бы нескольких раундов. Если мы можем сгенерировать два разных подобранных открытых текста, которые через несколько раундов дают нам похожее значение на выходе функции шифрования, мы можем начать отыскивать раундовые подключи. А если ключевое расписание шифра слабое, тогда мы на основании этих данных можем определять некоторые биты основного ключа.

Атаки такого рода относятся к категории "sqare root based", потому что они помогают сократить число подобранных вариантов на квадратный корень. Одно дело, когда мы просто пассивно полагаемся на существование коллизий, другое дело, когда их можно создавать целенаправленно.

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

2). В протоколах, аналогичных SSL, код аутентичности сообщения вычисляется через HMAC (эта функция в свою очередь основана на комбинации SHA-1 и MD5).

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

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

3) Насчет "спуфинга" и атак "человек посредине". Все относительно. Да, сейчас проще взломать сервер через дыры в программном обеспечении, неправильные настройки, плохие пароли и т.д. Поэтому никто с такого рода атаками и не заморачивается.

Но то, что такие атаки сложные – это заблуждение. Уже давно существуют (и даже входят в состав некоторых Линукс-дистрибутивов) такие "админско-хакерские" утилиты как dsniff, sshmitm, webmitm. Примеры использования таких утилит разобраны на соотвествующих сайтах. Можете сами потренироваться в локальной сети и увидеть, как легко быть в роли Мэллори.

Хотелось бы узнать мнение сообщества (на русском Smile) по поводу практических последствий реального(?) взлома MD5 и очень вероятного потенциального взлома SHA-1.

Это конечно не "мнение сообщества на русском", но здесь частично воспроизведена и исследована технология, которую использовал 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 от теоретических могут быстро перейти к катастрофическим.

Finally, we point out the consequences
resulting from such attack for signature schemes based on MD5 message digest
on an example using GPG.

The paper is available at the following link:
http://cryptography.hyperlink.cz/2004/collisions.htm
Vlastimil Klima

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

Потихоньку дело движется в сторону криптоанализа SHA-1

http://eprint.iacr.org/2004/364/

Cryptology ePrint Archive: Report 2004/364

Finding good differential patterns for attacks on SHA-1

Krystian Matusiewicz and Josef Pieprzyk

Abstract. In this paper we describe a method of finding differential patterns that may be used to attack reduced versions of SHA-1. We show that the problem of finding optimal differential patterns for SHA-1 is equivalent to the problem of finding minimal weight codeword in a linear code. Finally, we present a number of patterns of different lengths suitable for finding collisions and near-collisions and discuss some bounds on minimal weights of them.

Category / Keywords. hash functions, cryptanalysis, SHA-1, collisions, linear code

Date: received 19 Dec 2004

Contact author: kmatus at ics mq edu au

NIST начинает процедуру по выведению SHA-1 из употребления. Процесс должен завершиться к 2010 году. На время перехода к новому стандарту рекомендуется использование алгоритмов семейства SHA-2.

Что же будет после :?: Более стойких аналогов мало и с быстродействием у них проблемы. К примеру Whirlpool очень медленная.

... И ещё, как это повлияет на существующие стандарты и протоколы, прежде всего в государственном секторе? Ведь тот же DSS может работать только с SHA-1.

Если бы в ближайшее время NIST объявил открытый конкурс, что-то вроде ASH — Advanced Hash Standard, то успел бы закончить как раз к намеченному сроку.

http://eprint.iacr.org/2005/067.pdf

Коллизии в MD5 и фальшивые подписи для сертификатов.

Интересно. Я просто наблюдаю за развитием событий и обнаруживаю такую вещь. Вот к примеру есть алгоритм DES, хотя не только он конечно, который до сих пор так и не взломали (атаку грубой силой я не рассматриваю, знаю, что ей он уже открываем за пару дней на каком-нибудь Крее). А вот с хешами все как-то слабее получается, md5, Sha0, sha1... Это неудачное стечение обстоятельств или все таки объяснимо какими то закономерностями (например сложнее хеш хороший написать или что то еще)?
Мне думается – с шифрованием все таки понятно – это просто гигантское количество ключей… А с хешами? Есть алгоритм, который можно изучить, и даже не имея возможности из хеша восстановить начальное значение можно найти определенные закономерности по поиску определенных условий из блоков начальных данных, хотя бы примерно приближающий результат функции к искомому значению. Алгоритм то всегда один, а в шифровании ключи всегда разные и при выборе ключа качественный алгоритм выбирает действительно абсолютно случайный ключ.
Вот возьмем однонаправленную функцию. Я нахожусь на вершине горы, форма которой есть алгоритм hash-функции. Я кинул вниз камень (запустил хеш функцию). Этот камень ударился о другой камень, далее эти два камня ударились в следующие камни (провожу аналогию – на вход хеш функции поступили следующие строки текста) и через некоторое время и расстояние вниз полетела уже целая лавина разных камней, больших и маленьких, которые ударяясь друг о друга и о поверхность горы, организовали огромное число различных случайных комбинаций, действующих в свое время одна на другую в дико накопительной прогрессии. Это однонаправленная функция? Исходя из полученной в результате картины определить точно сам первый камень и куда я его бросил невозможно (возможно конечно, если сделать несоразмерное гигантское количество обратных вычислений по построенным моделям отскоков камней друг от друга, где начальными условиями будет являться местоположение камней после схода лавины и т.п. но это супер сложно и требует сильнейшей математической и исследовательской в данном случае по физическим свойствам камней подготовки, или же полным перебором разных вариантов), хотя результат очевиден, и этот результат получился по вполне очевидным причинам – камни вниз летели и ударялись друг о друга по законам физики, известным со школы, провожу аналогию – хеш считает то же по определенному алгоритму. Если бы лавина летела вниз на другой день, то и результат бы был другой, к примеру потому, что была бы другая температура окружающего воздуха (а значит другая упругость и крепость камней, соответственно другие отскоки камней друг от друга и т.п.), провожу аналогию – в тексте изменили одну букву.
Теперь о том, к чему я все это писал. Мы имеем совершенно определенную картину после схода лавины. Можно ли повторить эту картину. В точности нет, однако изучив общие закономерности полета камней можно построить хотя бы приближенную картину, и такие модели по видимому (по крайней мере я так думаю) существуют. Таким образом получаем, что для поиска коллизий нет смысла работать полным перебором, достаточно построить определенную модель работы функции, существенно сужающую количество начальных условий, по аналогии о нашей горе – построив определенную модель можно без большого труда определить зимой шла лавина или летом, поскольку начальные условия сильно отличны, а при более детальной проработке может определить и время суток к примеру.

//В целом для лучшего представления я конечно привел слишком упрощенную картину, можно было бы расписать все немного подробнее, например так, хотя это тоже упрощенно:
Количество камней на склонах горы – разрядность выходного значения hash функции (пусть к примеру у нас будет 1000 камней, для легкости представления можно представить, что это камни весом более 100 кГ, но остальные камни то же принимают участие в процессе)
Высота горы и ее форма – алгоритм hash функции,
Запуск функции – падение первого камня с определенным весом с высоты 100 метров точно на вершину горы, или куда-нибудь вблизи от нее.
Все остальное – входные параметры для hash функции (температура, плотность и влажность воздуха, неоднородность нагрева склонов горы солнечной энергией, данный параметр можно рассматривать не как один, а разложив его на многократные градации по поверхности, упругость и прочность пород, состояние растительности в различные промежутки времени года, наличие и вид атмосферных осадков и т.д, таких параметров может быть очень очень много).//