Три гудка в тумане

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

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

Точнее, скомпрометирована не теория вообще, а конкретного вида функции SHA и MD5, широко применяемые во множестве популярных криптографических приложений.

Хэш-функция (иначе именуемая односторонней функцией) — это такое математическое преобразование, которое, грубо говоря, берет файл произвольной длины и вычисляет для него своего рода дайджест (или хэш), то есть уникальную последовательность фиксированной, сравнительно небольшой длины. Криптографическая хэш-функция должна обладать двумя важнейшими свойствами: 1) чтобы по дайджесту было практически невозможно восстановить исходные данные, на основе которых он сгенерирован; 2) чтобы практически невозможно было отыскать коллизию, то есть два разных файла, имеющих один и тот же дайджест.

Криптографические хэш-функции весьма удобны при формировании цифровой подписи файла, поскольку изменение единственной буквы и даже всего лишь бита в документе приводит к генерации хэша совершенно иного вида. Хэш-функции применяются ныне повсеместно и лежат в основе электронной коммерции и вообще едва ли не всех широко распространенных криптографических протоколов, включая защиту веб-соединений (SSL) и электронной почты (PGP).

Самой сильной и (вероятно, как следствие) самой популярной является хэш-функция SHA-1, в свое время разработанная в недрах Агентства национальной безопасности США. В принципе же все хэш-функции устроены примерно одинаково — как большая последовательность итераций (циклов) некоторого хитрого преобразования, постепенно ужимающего файл до длины дайджеста с одновременным перемешиванием битов содержимого. Поэтому, считают криптографы, серьезная компрометация даже одного из криптоалгоритмов хэширования заставляет усомниться и в надежности его собратьев.

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

Так, французский математик-компьютерщик Антуан Жюс (Antoine Joux) продемонстрировал коллизию, которую он нашел для алгоритма SHA-0. Это исходная, менее сильная версия алгоритма SHA, предложенная АНБ первоначально. Некоторое время спустя аналитики американской спецслужбы сами нашли слабость в своем алгоритме и, не объясняя причин, заменили прежний метод хэширования на новый, более сильный, который получил название SHA-1 и стал федеральным стандартом. Старый же, таким образом, стал именоваться SHA-0, а ныне Антуан Жюс показал, в чем заключается его слабость.

Китайские криптографы Ван, Фен, Лай и Ю (Wang, Feng, Lai, Yu) из университета Шаньдуна продемонстрировали целое семейство коллизий в алгоритме MD5, а также сообщили, что их универсальный метод способен эффективно отыскивать коллизии (за 240 шагов) в SHA-0, не говоря уже о более слабых алгоритмах MD4, RIPEMD и HAVAL-128.

Наконец, в докладе израильтян Эли Бихама и Рафи Чена (Eli Biham, Rafi Chen) приведены совсем свежие результаты анализа SHA-1, включая отыскание коллизий для сокращенной версии алгоритма. Полная версия SHA-1 содержит восемьдесят циклов перемалывания данных. Бихам и Чен пока сумели взломать работу алгоритма на сорока циклах, но уверены, что атаку можно продолжить (правда, заметил Бихам в кулуарах, он сомневается, что удастся преодолеть больше сорока шести циклов).

Таким образом, компрометация популярнейших хэш-функций оказалась все же не столь драматичной, как обещали пущенные в канун криптоконференции слухи. Тем не менее, уже ясно, что слабость MD5 является фатальной и всем серьезным программам, на нее опирающимся, пора подыскивать замену (с помощью MD5, например, удостоверяется целостность и аутентичность исходных кодов серверного ПО Apache). SHA-1 пока вышел сухим из воды, но охотники уже обложили его со всех сторон. Поэтому ожидается, что вскоре начнется постепенная миграция криптоприложений к чему-то более сильному.

Впрочем, выбор возможных альтернатив представляется делом весьма туманным. Не исключено, что на помощь мировому сообществу опять придет американское Агентство национальной безопасности, ибо SHA, как ни крути, — федеральный криптостандарт США и забота о поддержании его надежности является непосредственной задачей спецслужбы.