Все новости от 18 августа 2004 г.

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

Замешательство началось в четверг с объявления о том, что французский специалист Антуан Жу обнаружил слабину в популярном алгоритме 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. «Теперь ясно, что этот алгоритм слаб, — сказал он. — Прежде чем будет совершена реальная атака, надо постараться уйти от него».

 В продолжение темы:

Обсуждение и комментарии

	Yuri 18 Aug 2004 2:47 PM
Насчет подделки писем - это полная туфта, т.к. никакого _разумного_ поддельного письма с той же хэш-функцией создать точно не получится. А вот создать программу с "закладкой" и тем же хэшем при нынешних размерах файлов действительно вполне реально. Но мне всегда казалось, что разумные люди никогда и не полагались на md5-суммы как на 100% надежный способ защиты от преднамеренных атак.
	zdfrp 18 Aug 2004 6:27 PM
> разумные люди никогда и не полагались на md5-суммы как на 100% надежный способ защиты от преднамеренных атак У вас есть другие предложения?
	нц 18 Aug 2004 9:46 PM
Если не ошибаюсь, но после ликвидации взлома в прошлом году ftp.gnu.org советовали сверить md5 суммы ;)
	В.К. - 001pvti.ru 19 Aug 2004 9:22 AM
Наверное, многие забыли способ взлома, показанный в статье двухгодичной давности в журнале "Управление защитой информации". Не обязательно колоть хэш, ЭЦП и так может упасть, в смысле, не сложно добиться, что бы два документа имели одинаковые подписи. Даю ссылку http://www.vniipvti.ru/archiv/n310302.htm
	xfs 19 Aug 2004 10:37 AM
2нц. не разбираетесь - не лезть в обсуждение. gpg --verify blah.tar.gz.sig blah.tar.gz а md5 это проверять что фильмы при переноски на ненадежных носителях не попортились.
	fi 19 Aug 2004 1:26 PM
2 xfs не разбираетесь - не лезть в обсуждение. -)))) А что по твоему использует gpg для подписи? Хотя бы это прочитай: --force-v4-certs Always use v4 key signatures even on v3 keys. This option also changes the default hash algorithm for v3 RSA keys from MD5 to SHA-1.
	нц 20 Aug 2004 4:45 PM
2 fi спасибо другими словами, подтверждение подлинности исходников не возможно на 100%.
	Finch - osipovnewyork.ru 20 Aug 2004 9:59 PM
В общем остался только наш "любимый" OpenBSD BlowFish невзломанным... Или его тоже взломали? А то у меня /etc/master.pswd на всех серваках шифруется BlowFish'ом :)
	нц 20 Aug 2004 11:36 PM
2 Finch тссссссс!!! слово *BSD здесь не популярно! ;)
	XXX 15 Dec 2004 9:04 AM
А в чем собственно, проблема? Очевидно, что любая хэш-функция имеет коллизии. Чем короче сигнатура, тем их больше. Надо просто увеличить длину сигнатуры и использовать несколько разных хеш-функций.
	славик 16 Dec 2004 4:54 PM
ослик тоже по мд5 качает можно кучу вирусов в программы насовать