Специалисты по криптографии встревожены уязвимостью алгоритмов

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

Замешательство началось в четверг с объявления о том, что французский специалист Антуан Жу обнаружил слабину в популярном алгоритме MD5, который часто применяется для цифровых подписей. Затем четверо китайских ученых выпустили документ, в котором предлагают способ обойти еще один алгоритм, SHA-0. Хотя их результаты предварительны, со временем эти открытия могут облегчить злоумышленникам введение необнаруживаемых лазеек в компьютерный код или подделку электронных подписей - если не будет применяться другой, более надежный алгоритм.

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

Ученые из Израильского технологического института Эли Бихам и Рафи Чен первоначально планировали представить работу о способах взлома алгоритма Secure Hash Algorithm (SHA-0), несовершенство которого общеизвестно. Однако в своем докладе Бихам привел некоторые ранние результаты работы, выявляющей уязвимости и в алгоритме SHA-1, считавшимся надежным. Доклад носил очень предварительный характер, но он может поставить под вопрос долгосрочное будущее широко применяемого алгоритма SHA-1 и заставить специалистов искать альтернативы.

Рассматриваемый в настоящее время как золотой стандарт алгоритмов своего класса, SHA-1 применяется в таких популярных программах, как PGP и SSL. Он сертифицирован Национальным институтом стандартов и технологии (NIST) и является единственным алгоритмом, утвержденным для использования «Стандартом цифровой подписи» правительства США. SHA-1 выдает 160-битный код, который длиннее 128-битного кода, выдаваемого алгоритмом MD5, и считается более надежным.

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

Уникальные отпечатки пальцев

«Если у двух контрактов окажется одна и та же электронная подпись, один можно будет заменить другим, и в суде будет по крайней мере трудно определить, какой из них подлинный, - пояснил в интервью по телефону Хьюз, старший партнер StorageTek. - Это очень серьезная опасность».

Специалисты называют алгоритмы MD5, SHA-0 и SHA-1 хэш-функциями. Ими можно обрабатывать все от сообщений e-mail до ядра операционной системы, получая код, который считается уникальным «отпечатком пальцев». Изменение единственной буквы во входных данных приводит к генерации абсолютно нового кода.

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

Ученым давно известно, что ни один из практически применяемых алгоритмов шифрования не может быть абсолютно надежным, и они пытались создать такие алгоритмы, которые для получения дублирующих «отпечатков пальцев» требовали бы слишком длительного времени. Считается, что SHA-1 достаточно надежен, так как хэш-коллизию невозможно получить известными методами. Этот алгоритм основан на том, что компьютер, пытаясь создать уникальный код, выполняет программу 80 раз. Бихам утверждает, что ему удалось получить дублирующий код в 36 циклах из этих 80.

Если уязвимости, аналогичные выявленным в SHA-0, обнаружатся в SHA-1, это будет означать, что время создания хэш-коллизии сократится почти в 500 млн раз - что делает эту операцию теоретически доступной для сети из быстродействующих ПК.

Слабость алгоритма MD5 представляет еще более непосредственную угрозу. Веб-сервер с открытым исходным кодом Apache использует хэш-коды MD5, чтобы гарантировать, что ПО, установленное на десятках сайтов-зеркал, остается в целости и сохранности. Ту же роль играет программа Solaris Fingerprint Database от Sun Microsystems, которая, как утверждает компания, «гарантирует, что в состав дистрибутива входят правильные двоичные файлы, а не их измененные версии, что угрожало бы безопасности системы».

Выявленные за последние дни уязвимости MD5 означают, что злоумышленник на стандартном ПК может создавать одну хэш-коллизию за несколько часов. Правда, чтобы создать копию ПО с лазейкой и получить для него такую хэш-коллизию, потребуется гораздо больше времени. И все же Хьюз убежден, что программистам следует отказаться от MD5. «Теперь ясно, что этот алгоритм слаб, - сказал он. - Прежде чем будет совершена реальная атака, надо постараться уйти от него».