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 = [(22k-1 + p – (22k-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
комментариев: 1060 документов: 16 редакций: 32
Было бы крайне интересно собрать статистику, какие программы использовались для генерации уязвимых ключей. Интересно, возможно ли это для x.509?
По предпочтениям на ключе можно ведь приблизительно установить программу и её версию, которая использовалась для генерации.
комментариев: 9796 документов: 488 редакций: 5664
Выявить конкретные причины было бы интересно. Возможно нахождение дыры, сравнимой с Debian OpenSSL.
Вполне может также оказаться, что росту проблем с ГПСЧ (и соответственно) с ключами сильно поспособствовали виртуализация и виртуальные/облачные хостинги: расклонировали один образ и нагенерили сертификатов на сотни виртуальных хостов. Одинаковое (сходное) состояние ГПСЧ тоже склонировалось, прямого доступа к железу у виртуалок нет.
Понятно, что в случае (Open)PGP, где ключи генерят не массово, редко и чаще всего индивидуально, такие фэйлы маловероятны.
комментариев: 11558 документов: 1036 редакций: 4118
Могло быть вызвано этим: http://web.archive.org/web/200.....oft/pgp/bugs.shtml#8 Проще было бы отследить источник конкретных проблем по датам генерации ключей.
комментариев: 1060 документов: 16 редакций: 32
Насколько я помню, в 5.0 не было RSA-ключей, они снова появились только в 6.x – там с патентами проблемы были.
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 1515 документов: 44 редакций: 5786
Было бы очень хорошо разделить текст новости на 2 части, где в одной была бы рассмотрена ситуация только с сертификатами, а в другой — только с ключами PGP. Как можно сравнивать настолько разные реализации?
Как мне было объяснено, промышленное QRNG, которое сейчас пытаются пустить в производство, как раз и мотивировалось защитой от подобных атак. Предполагается, что раз у виртуальной машины нет полноценного пула случайности, единственное, что она может делать в случае нехватки энтропии — запрашивать его у внешней реальной машины (назовём её условно "подкачкой"). Атакующий может попытаться запросить операции, которые вытянут "всю энтропию" из нужной виртуалки, а затем и из "подкачки". Когда энтропия кончается, машина перезагружается, при этом можно спрогнозировать, что будет иметься в качестве её пула случайности, и провести атаку.
[/очень примерно, как-то так]
комментариев: 11558 документов: 1036 редакций: 4118
Да что-то так и не перенесли. Завтра будет свободное время, исправлю это упущение.
комментариев: 9796 документов: 488 редакций: 5664
Похоже, считали всё вместе, хотя 400000 RSA-PGP-ключей — это около 6%:
Ждём полной версии:
Конкретно в этой работе RSA сравнивали по отдельности похоже только в кластерах из общих модулей n = pq (ключей): как раз дальше интересные (хотя и закономерные) выводы, что даже с пересчётом на разное процентное соотношение RSA-X.509 и RSA-PGP, непосредственно в PGP таких фэйлов мало (в процентном отношении к общему числу в PGP, ещё раз).
DSA тоже сранивали по отдельности, но среди сертификаторв таких ключей всего 141, а в PGP — половина, так что про сертификаты ничего существенного сказать нельзя. Эль-Гамаль вообще бывает только в PGP.
Такие случаи там тоже упомянуты, но подробно не раскрыты. Не стал приводить их в переводе.
— как такое получилось, у самих исследователей возможно внятных объяснений нет.
Т.е., возможно некоторые ключи и сертификаты намеренно так создавались и для чего-то (для перекрёстной сертификации) это делается, но не все случаи этим объясняются.
Это значит, что для них не удалось выявить явного фэйла. Факторизовать можно ещё меньшую часть из этих оставшихся. Под взломом действительно понимаются масса других сценариев. Например, владелец закрытого ключа одного из сертификатов в этой базе может найти чужой сертификат в этой же базе с похожим модулем и ему будет проще его факторизовать. Например, эти ключи генерились на виртуальном хостинге для разных узлов и состояние ГПСЧ было схоже. Или оба ГПСЧ одинаковым образом сбойнули: откатились к какому-то дефолтному малоэнтропийному состоянию из-за невыявленного бага (даже и на разных хостингах).
Но если прослеживается кластер с общим простым множителем, значит легче будет факторизовать его ключ, зная, что PRNG имел схожее состояние.
Явно не указано (возможно, что у них ничего не вышло конкретно с PGP и войдёт только в полную версию работы), возможно, что также как и в DH только частичные уязвимости — отдельные общие параметры.
Точно не скажу, но AKS не применяется, кажется для больших чисел он не подходит по скорости, а вероятностные тесты должны давать при правильной работе (P)RNG и всего остального 2-128 — 2-256 ошибок.
Не стал разбирать статистику для этого случая, хотя авторы привели подробный расклад и на столь малом числе ключей. Там забавные ошибки, но их очень мало и они очень специфичные. Например, в ряде случаев такие ключи будут работать, хотя и с сомнительной стойкостью.
С PGP всё (почти?) хорошо. Достаточно было в новости отразить именно это. Статистика по PGP-ключам довольно скучная.
Уязвимости (условно) можно поделить на три группы:
На самом деле, там ещё больше случаев, масса всякой статистики, таблиц, графиков, выбрал только то, что посчитал важным.
Насчёт QRNG, совершенно верно. Где-то была реклама (или пруф-концепт?): в стойку ставится QRNG-сервер, который по обычному шифрованному каналу (канал здесь играет второстепенную роль, скорее для аутентификации; даже если с ним что-то не так, главное, что повторяющихся значений в энтропии не будет) раздаёт энтропию на все остальные серверы и драйвера виртуалок тоже берут необходимую часть от этого потока.
комментариев: 9796 документов: 488 редакций: 5664
Итак, общий модуль — это в разделе shared moduli — общий n = p•q.
Второй случай — это Moduli with shared factors.
Достаточно знания одного множителя. Поскольку n = p•q — открытый ключ, то p' / n = p' / (p•q) при p' = p мы находим второй множитель q.
На уровне спекуляций, можно даже представить, что существует некий алгоритм, который проверяет какие-то свойства из соотношения n к n' статистически, чтобы выявить ключи с общим множителем и на основании этих данных облегчает нахождение множителей, даже если заранее неизвестен ни один из них. Так что, ни в какой ситуации создавать ключи с общими множителями не стоит. Даже если ни один из них "не будет известен" противнику.
Точнее, всё ещё проще (и хуже в плане безопасности): факторизация n и n' при общем множителе p возможна путём вычисления наибольшего общего делителя (что не является трудной задачей). Что можно сделать и для многих ключей сразу. Так что это даже хуже, чем иметь общий ключ: НОД может посчитать и не владелец этого ключа и факторизовать оба ключа.
Собственно, в разделе Moduli with shared factors они что-то подобное замутили и построили граф таких кластеров:
Но подробности в явном виде не разжёвывают:
Подозреваю, что они делили ключи перебором p'•q' / (p•q) или считали наибольший общий делитель (GCD) и на основе знания примерного соотношения p и q при создании ключа, искали остатки при сокращении или статистически обрабатывали какие-то более сложные зависимости. Там где один из множителей совпадает — должно быть отклонение по какому-то параметру.
Там же они и указывают правило, что по построенному графу можно посмотреть в каком положении по отношению к рёбрам/вершинам находятся эти n и в зависимости от положения их действительно можно факторизовать.
Вот и другое подозрительное место:
Not to make? Авторы всё-таки что-то темнят? Что-то с намёками во взаимоотношении PGP/X.509, чтобы их результаты было не так легко воспроизвести и использовать во вред раньше времени или предъявить претензии.
комментариев: 1515 документов: 44 редакций: 5786
Шок! В криптографии в научных публикациях разве не требуется full disclosure?! Такое могут принять в журнал к печати? Или с такими "sapienti sat" ("умному — достаточно") заявлениями можно отослать заявку на конференционный доклад? Признаться, я слабо представляю как устроен "иакр" изнутри, и что именно там публикуется. В архиве, за исключением PhD-диссеров, книг и редких исключений всё является либо препринтами статей, либо публикаций в трудах конференций, потому full disclosure необходимо. Те, кто сильно боятся, могут долго тянуть время до тех пор, пока работа не будет сделана полностью, но опубликуют её уже с полным раскрытием всего.
P.S.: новость, конечно, очень интересная. Спасибо за подробные разъяснения и за то, что нашли время перевести.
комментариев: 9796 документов: 488 редакций: 5664
В GnuPG используется Libgcrypt.
Справедливо. Совсем слабый. Факторизуется даже без поиска общих модулей. Кроме злополучных дебиановских модулей это ещё и Primality, small factors, and other tests, из-за которых
Авторы известные и с репутацией (двое-трое из них точно), поэтому могут позволить себе и повыёжываться даже в официальной публикации. И, возможно, с не очень уместными шуточками и не до конца прояснёнными заявлениями. Основная причина скорее в том, что это очень неполный препринт, предназначенный только для того, чтобы застолбить тему, а полная версия будет представлена к CRYPTO-2012, т.е. к августу только.
Ошибка скорее в окружении (но это на уровне домыслов). И вывод в том, что слабый PRNG даёт слабые RSA ключи (причём один общий множитель хуже, чем оба — в первом случае возможна факторизация, во втором — просто расшаренный между двумя сторонами ключ). В этом "Рон проигрывает Виту". Но RSA-ключи, за счёт этого, проще проверить на вшивость. Что там скрывается в DH-based, если можно покопаться, прицельно зная уязвимости конкретного PRNG — тоже большое поле для фантазии.
RNG может быть какой угодно, и софт может черпать энтропию откуда угодно — нет никаких «по-умолчанию». Разработчиков никто не заставляет использовать CryptGenRandom (более того, 90% тупых макак про него даже не слышали — пользуются сишным rand и инициализируют его временем, в лучшем случае). Отсюда и и дыры огромного размера в таком софте... А бывает, что не удосуживаются даже временем инициализировать: тупо юзают сишный ранд. Он тогда выдает одинаковую последовательность всегда и везде, и генерит одинаковые ключи (сид для ранда задается функцией srand и имеет размер 32 бита; обычно делают srand(time(NULL)), где time возвращает число секунд от unix-эпохи).
По уму надо использовать CryptGenRandom — стандартный RNG от CryptoAPI. Начиная с висты, появился CNG API — BCryptGenRandom. Софт же, защищенный RSA, очень часто оказывается сделан на основе ключей, сгенерированых от сишного ранда. Говорят, что есть даже крякерская тулза, которая берет ключ и прогоняет его через набор тестов, это определяющих.
Обычно же как делают? Ищут в гугле «как сделать то-то» и копипастят код к себе, а там что попалось, то попалось. Один и тот же насквозь кривой и неправильный код часто кочует через сотни форумов, являясь прямо-таки стандартом говнокодинга. Если исключить антивирусы и прочий софт крупных производителей, останется over 9000 всяких мелких программок, которые сразу понятно, что говно, прям из описания. Представления разработчиков зачастую совсем далеки от реальности :-(
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 11558 документов: 1036 редакций: 4118
Раз исходные данные брались из SSL Observatory, стало быть эти рутеры благополучно висят в общедоступной сети. Интересно, сколько из них — в сетях крупных компаний? Так что считать проблему незначительной тоже вряд ли стоит.