15.02 // Практические уязвимости открытых ключей или почему Рон проигрывает Виту

Исследователи Arjen K. Lenstra, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, Christophe Wachter (EPFL IC LACAL, Station 14, CH-1015 Лозанна, Швейцария) и James P. Hughes изучили наборы открытых ключей, публично доступных в интернете. Их исследование опирается как на данные проекта The EFF SSL Observatory по сбору сведений о ключах сертификатов, так и на изучение наборов (Open)PGP-ключей. Исследованию подверглись ключи RSA (основанные на алгоритмах трудности факторизации) и ElGamal, DSA, ECDSA (основанные на проблеме нахождения дискретного логарифма). Первую, более многочисленную группу, исследователи условно связали с именем Рона Райвиста, а вторую — с Витом Диффи (по имени одних из изобретателей алгоритмов, положивших начало асимметричной криптографии).

Все открытые ключи были подвергнуты тестам на принадлежность к группам и подгруппам, простоту и др. Так было выявлено некоторое количество недействительных ключей, связанных с уже широкоизвестной ошибкой Debian OpenSSL и др. Но наиболее важной особенностью является изучения требования об уникальности параметров, использованных в генерации ключей. Это подразумевает использование стойкого и корректно работающего генератора (псевдо)случайных чисел, на основе данных которого созданы ключи с неповторяющимися исходными параметрами.

При этом из 6.6 миллионов различных RSA-ключей PGP и сертификатов X.509 обнаружилось, что 0.27 миллионов (4%) имеют общие RSA-модули. По отношению к 6.4 млн. различающимся RSA-модулям, 71052 (1.1%) встречаются более одного раза, некоторые из них — тысячи раз. Более серьёзным является то, что практический уровень безопасности среди наиболее распространённых 1024-битных ключей составил лишь 99.8%. 12720 различных RSA-модулей оказались слабыми и не обеспечивающими никакой безопасности, любой желающий может вычислить по ним закрытый ключ.

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

Ошибки исполнения оказались более распространёнными (в процентном соотношении) для ключей RSA-группы. Ключи DH-группы, несмотря на их меньшее распространение, оказались менее подверженными фатальным уязвимостям. Интересно, что ранее было распространено (и подтверждалось отдельными случаями) противоположное мнение: для DH-алгоритмов требуются более строгие требования к генераторам псевдослучайных чисел, ГПСЧ используются не только при создании ключа, но и при работе алгоритма. Возможно, это в последствии побудило разработчиков более внимательно отнестись к релизации. Другая причина связана с использованием нескольких секретов при генерации RSA-ключа и только одного при генерации DH и (EC)DSA ключей. Авторы отмечают, что использование RSA-модулей pq вида q = [(2^2k-1 + p – (2^2k-1 mod p)) / p] для k-битового простого p могло бы решить эту проблему.

Всего к ноябрю 2011 было собрано 6 185 372 различных сертификатов и 5 481 332 ключей PGP ( 11 666 704 открытых ключей). Из всех сертификатов большинство — RSA, лишь 141 относился к DSA и 1 (один) оказался относящимся к ECDSA (криптографии на эллиптических кривых). 77% сертификатов имело алгоритм создания отпечатка на основе хэш-функции SHA-1 или лучшей (5287 x SHA256, 24 x SHA384, 525 x SHA512), 22.3% использовало MD5 (122 x MD2, 30 x GOST, 14 x MD4, и 9 x RIPEMD160).

Среди PGP-ключей наблюдается обратная картина по асимметричным алгоритмам: 2 546 752 (46.5%) — ключи Эль-Гамаля, 2 536 959 (46.3%) — DSA и только 397 621 (7.3%) RSA.

Если при анализе RSA выявлены 12720 уязвимых ключей сертификатов и десятки тысяч кластеров с общими модулями, то для PGP повторение модулей выявлено лишь в 28 случаях использования RSA. Как известно, стойкость алгоритма RSA опирается на то, что RSA-модуль составлен из двух простых чисел, ни разу никем не использовавшихся ранее. Исследования показывают, что на практике это требование во многих случаях не соблюдается, вероятно из-за ошибок в работе ГПСЧ.

В случае алгоритма Эль-Гамаля было проанализировано 2 546 752 ключей. Из них 82 содержали составное число p вместо простого, что привело к разного рода ошибкам — невозможности генератора сгенерировать группу/подгруппу, ошибкам в тестах принадлежности к группе и т.д. Лишь шесть ключей Эль-Гамаля оказались содержащими совместно используемые параметры и только два из них принадлежади разным владельцам. Среди раздельных совпадений параметров было зафиксировано 93 повторения p.

Среди 2 536 893 PGP DSA ключей только два случая совместного использования параметров: один двойной (с одинаковым владельцем) и один тройной (с возможно разными владельцами). Совпадение отдельных параметров из набора p, q, g также было зафиксировано в единичных случаях.

Исследователи делают вывод о том, что случаи с DSA и ElHamal ключами не выявляют существенного распространения одинаковых ключей (даже в процентном отношении), а возможная часть из них была сформирована с экспериментальными целями. В то время как широко используемые и действительные сертификаты используют общие RSA-ключи (что может быть использовано для подмены), значительное количество общих параметров (что может облегчить взлом), а часть из них сгенерирована на основе слабых параметров и может быть взломана. Это показывает слабость программной реализации RSA во многих реальных условиях использования.

Исследователи считают, что их работа может также пролить свет на то, почему НИСТ США в 1991 году предпочёл выбрать алгоритм DSA (разработанный в АНБ) вместо RSA для стандарта подписи, несмотря на то что такой выбор вызвал массу кривотолков. Можно предположить, что службы безопасности знали о практических уязвимостях реализации при массовом разворачивании и внедрении государственного стандарта для инфраструктуры цифровой подписи и схожих областей применения асимметричных алгоритмов. И в данном случае они, возможно, пытались избежать возможных проблем.

12 февраля исследователи получили новую порцию ключей от EFF, теперь их база выросла с 6.2 до 7.2 миллионов сертификатов. Количество RSA-модулей снизилось с 4.7M до 3.7M. Пять тысяч ключей с уязвимыми модулями было отозвано (или истёк срок их действия). Однако появилось 13019 новых уязвимых RSA-модулей, теперь их вместе с оставшимися старыми насчитывается 20251 штук. Тезис о 99.8% практической безопасности RSA-сертификатов подтверждается. Факторизовать итак устаревающие 1024-битные RSA-ключи такого рода будет легко, а простой переход на 2048-битные не решит проблему. Часть владельцев сертификатов с 2048-битными ключами предупреждена участниками исследования в особом порядке.

Источник: Cryptology ePrint Archive