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

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

Комментарии [скрыть комментарии/форму]

—	sentaus (15/02/2012 14:25, исправлен 15/02/2012 14:25) профиль/связь <#> комментариев: 1060 документов: 16 редакций: 32

Если при анализе RSA выявлены 12720 уязвимых ключей сертификатов и десятки тысяч кластеров с общими модулями,

Было бы крайне интересно собрать статистику, какие программы использовались для генерации уязвимых ключей. Интересно, возможно ли это для x.509?

для PGP повторение модулей выявлено лишь в 28 случаях использования RSA.

По предпочтениям на ключе можно ведь приблизительно установить программу и её версию, которая использовалась для генерации.

—	unknown (15/02/2012 14:45, исправлен 15/02/2012 14:46) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Выявить конкретные причины было бы интересно. Возможно нахождение дыры, сравнимой с Debian OpenSSL.

Вполне может также оказаться, что росту проблем с ГПСЧ (и соответственно) с ключами сильно поспособствовали виртуализация и виртуальные/облачные хостинги: расклонировали один образ и нагенерили сертификатов на сотни виртуальных хостов. Одинаковое (сходное) состояние ГПСЧ тоже склонировалось, прямого доступа к железу у виртуалок нет.

Понятно, что в случае (Open)PGP, где ключи генерят не массово, редко и чаще всего индивидуально, такие фэйлы маловероятны.

—	SATtva (15/02/2012 21:11) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Возможно нахождение дыры, сравнимой с Debian OpenSSL.

Могло быть вызвано этим: http://web.archive.org/web/200.....oft/pgp/bugs.shtml#8 Проще было бы отследить источник конкретных проблем по датам генерации ключей.

—	sentaus (15/02/2012 22:28) профиль/связь <#> комментариев: 1060 документов: 16 редакций: 32

Могло быть вызвано этим: http://web.archive.org/web/200.....oft/pgp/bugs.shtml#8

Насколько я помню, в 5.0 не было RSA-ключей, они снова появились только в 6.x – там с патентами проблемы были.

—	SATtva (15/02/2012 22:53) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Да, верно.

—	spinore (16/02/2012 03:58) профиль/связь <#> комментариев: 1515 документов: 44 редакций: 5786

< При этом из 6.6 миллионов различных RSA-ключей PGP и сертификатов < X.509 обнаружилось, что 0.27 миллионов (4%) имеют общие RSA-модули.
Сравнивали ключи, не взирая на то, откуда они взялись (из SSL-сертификатов или PGP)? Насколько это осмысленно?< По отношению к 6.4 млн. различающимся RSA-модулям, 71052 (1.1%) встречаются < более одного раза, некоторые из них — тысячи раз.
Один и тот же RSA-модуль мог встретиться в PGP-ключе и в сертификате сервера? Что бы это могло значить?< практический уровень безопасности среди наиболее распространённых 1024-битных < ключей составил лишь 99.8%.
Что это значит? 99.8% ключей не получится факторизовать на практике? Или под взломом/безопасностью понималось что-то другое?< 12720 различных RSA-модулей оказались слабыми и не обеспечивающими никакой < безопасности, любой желающий может вычислить по ним закрытый ключ.
Были ли такие среди PGP-ключей?< Ключи DH-группы, несмотря на их меньшее распространение, оказались < менее подверженными фатальным уязвимостям.
Подозреваю, что, при прочих равных, это может быть объяснено следующим: по умолчанию на самом растространённом софте стояло RSA, а те, кто использовали другой тип ключей, либо пользовались другим софтом, либо меняли умолчальные опции, где и то и это обсуловлено более высокой квалификацией пользователей. Т.е. дело либо в софте, либо в окружении ОС, где более опытные могут сделать правильно даже на не самой надёжной ОС/окружении. < 12720 уязвимых ключей сертификатов и десятки тысяч кластеров с общими модулями
"Общими модулями" — совпадали оба модуля между сравниваемыми ключами (p₁ = p₂ и q₁ = q₂), или ключи имели общий только один модуль? Насколько я понимаю, если у меня и моего противника только один общий модуль в секретном ключе (выполнено только одно из вышенаписанных равенств), я не смогу восстановить его ключ. Я прав?< В случае алгоритма Эль-Гамаля было проанализировано 2 546 752 ключей. < Из них 82 содержали составное число p вместо простого, что привело к разного рода < ошибкам — невозможности генератора сгенерировать группу/подгруппу, ошибкам в тестах < принадлежности к группе и т.д.
Как так могло получиться, что число оказалось не простым? Ошибка в реализации софта? Ведь число перед использованием проходит тест на простоту, не так ли? Используемые тесты на простоту при генерации SSL-сертификатов и PGP-ключей вероятностные, как это было по старинке, или детерминистичные, типа AKS? Можно ли объяснить % таких ключей — (82/2546752*100)% — как ошибки вероятностного теста, или же это обсусловлено иными причинами? Если исследователям не удалось "сгенерировать группу/подгруппу", то значит ли это, что и использовать такие ключи не получилось бы, и они "были сформированы с экспериментальными целями"?< Лишь шесть ключей Эль-Гамаля оказались содержащими совместно используемые < параметры и только два из них принадлежади разным владельцам. Среди раздельных < совпадений параметров было зафиксировано 93 повторения p.
Не очень понятно, как 93 соотносится с вышеупоминаемым 6 и может быть больше него.
< Могло быть вызвано этим
Есть ли ссылка на сайт без web-архива? Там очень интересный обзор по атакам — его уже нет здесь на сайте?

Было бы очень хорошо разделить текст новости на 2 части, где в одной была бы рассмотрена ситуация только с сертификатами, а в другой — только с ключами PGP. Как можно сравнивать настолько разные реализации?

⊰〈 Квантовая часть 〉⊱

< Обнаружены связи между одинаковыми параметрами ключей для разных компаний, < что связано с некачественной инициализацией генераторов псевдослучайных чисел. < ... < Вполне может также оказаться, что росту проблем с ГПСЧ (и соответственно) с ключами < сильно поспособствовали виртуализация и виртуальные/облачные хостинги: расклонировали < один образ и нагенерили сертификатов на сотни виртуальных хостов. Одинаковое (сходное) < состояние ГПСЧ тоже склонировалось, прямого доступа к железу у виртуалок нет.
[очень примерно, как-то так]
Как мне было объяснено, промышленное QRNG, которое сейчас пытаются пустить в производство, как раз и мотивировалось защитой от подобных атак. Предполагается, что раз у виртуальной машины нет полноценного пула случайности, единственное, что она может делать в случае нехватки энтропии — запрашивать его у внешней реальной машины (назовём её условно "подкачкой"). Атакующий может попытаться запросить операции, которые вытянут "всю энтропию" из нужной виртуалки, а затем и из "подкачки". Когда энтропия кончается, машина перезагружается, при этом можно спрогнозировать, что будет иметься в качестве её пула случайности, и провести атаку.
[/очень примерно, как-то так]

—	SATtva (16/02/2012 09:25) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

А тем временем в жёлтой прессе: Сенсация! Шок! Исследователи взломали систему шифрования банковских тразакций.

Есть ли ссылка на сайт без web-архива? Там очень интересный обзор по атакам — его уже нет здесь на сайте?

Да что-то так и не перенесли. Завтра будет свободное время, исправлю это упущение.

—	unknown (16/02/2012 10:39, исправлен 16/02/2012 13:16) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

сравнивали ключи, не взирая на то, откуда они взялись (из SSL-сертификатов или PGP)? Насколько это осмысленно?

Похоже, считали всё вместе, хотя 400000 RSA-PGP-ключей — это около 6%:

Information on the affected X.509 certificates and PGP keys is given in the full version of this paper, cf. below. Overall, over the data we collected 1024-bit RSA provides 99.8% security at best (but see Appendix A).

Ждём полной версии:

Affected RSA moduli and certificates. Overall, this led to the factorization of 12720 n-values of 1024 bits. More details, also about affected X.509 certificates and PGP keys, are given in the full version of this paper.

Конкретно в этой работе RSA сравнивали по отдельности похоже только в кластерах из общих модулей n = pq (ключей): как раз дальше интересные (хотя и закономерные) выводы, что даже с пересчётом на разное процентное соотношение RSA-X.509 и RSA-PGP, непосредственно в PGP таких фэйлов мало (в процентном отношении к общему числу в PGP, ещё раз).

DSA тоже сранивали по отдельности, но среди сертификаторв таких ключей всего 141, а в PGP — половина, так что про сертификаты ничего существенного сказать нельзя. Эль-Гамаль вообще бывает только в PGP.

Один и тот же RSA-модуль мог встретиться в PGP-ключе и в сертификате сервера? Что бы это могло значить?

Такие случаи там тоже упомянуты, но подробно не раскрыты. Не стал приводить их в переводе.

The n-value that occurs in five PGP keys also occurs twice among the X.509 certificates, and all seven occurrences refer to the same owner. For some of the other 27 multiple occurrences of n-values unique ownership of the RSA keys was harder to assess.

— как такое получилось, у самих исследователей возможно внятных объяснений нет.

Joining the two sets resulted in 6 386 984 distinct values, with the 129 n-values contained in both sets occurring in 204 X.509 certificates and in 137 PGP keys: as mentioned, some PGP keys are X.509-certified as well (though we have not tried to establish unique or conflicting ownerships, as this already proved to be infeasible for keys shared just among X.509 certificates). In order not to make it easier to re-derive our results, most information below refers to the joined set of unique values, not distinguishing between X.509 and PGP ones.

Т.е., возможно некоторые ключи и сертификаты намеренно так создавались и для чего-то (для перекрёстной сертификации) это делается, но не все случаи этим объясняются.

Что это значит? 99.8% ключей не получится факторизовать на практике? Или под взломом/безопасностью понималось что-то другое?

Это значит, что для них не удалось выявить явного фэйла. Факторизовать можно ещё меньшую часть из этих оставшихся. Под взломом действительно понимаются масса других сценариев. Например, владелец закрытого ключа одного из сертификатов в этой базе может найти чужой сертификат в этой же базе с похожим модулем и ему будет проще его факторизовать. Например, эти ключи генерились на виртуальном хостинге для разных узлов и состояние ГПСЧ было схоже. Или оба ГПСЧ одинаковым образом сбойнули: откатились к какому-то дефолтному малоэнтропийному состоянию из-за невыявленного бага (даже и на разных хостингах).

>Насколько я понимаю, если у меня и моего противника только один общий модуль в секретном ключе (выполнено только одно из вышенаписанных равенств), я не смогу восстановить его ключ. Я прав?

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

12720 различных RSA-модулей оказались слабыми и не обеспечивающими никакой безопасности, любой желающий может вычислить по ним закрытый ключ.
Были ли такие среди PGP-ключей?

Явно не указано (возможно, что у них ничего не вышло конкретно с PGP и войдёт только в полную версию работы), возможно, что также как и в DH только частичные уязвимости — отдельные общие параметры.

>Как так могло получиться, что число оказалось не простым?

>детерминистичные, типа AKS

Точно не скажу, но AKS не применяется, кажется для больших чисел он не подходит по скорости, а вероятностные тесты должны давать при правильной работе (P)RNG и всего остального 2^-128 — 2^-256 ошибок.

>Не очень понятно, как 93 соотносится с вышеупоминаемым 6 и может быть больше него.

Не стал разбирать статистику для этого случая, хотя авторы привели подробный расклад и на столь малом числе ключей. Там забавные ошибки, но их очень мало и они очень специфичные. Например, в ряде случаев такие ключи будут работать, хотя и с сомнительной стойкостью.

>в одной была бы рассмотрена ситуация только с сертификатами, а в другой — только с ключами PGP. Как можно сравнивать настолько разные реализации?

С PGP всё (почти?) хорошо. Достаточно было в новости отразить именно это. Статистика по PGP-ключам довольно скучная.

>Не очень понятно, как 93 соотносится с вышеупоминаемым 6 и может быть больше него.

Уязвимости (условно) можно поделить на три группы:

Слабый ключ
Общий модуль или другой набор параметров для DH (полностью общие параметры, практически возможность восстановить чужой ключ, если есть такие же параметры).
Частично общие параметры, это когда отсюда: 93 соотносится с вышеупоминаемым 6 и может быть больше него. Например, в Эль-Гамале это только общие генераторы или простые числа. Во многих случаях они и должны быть таковыми и только в некоторых свидетельствуют, что генератор отработал неправильно (например при совпадении для ключей с разным размером). Из этого напрямую не получить общий ключ (п.2), и (п.1) (хотя возможно владельцу одного из таких ключей), но это может свидетельствовать о плохой работе ГПСЧ, что для DH-алгоритмов фатально: при каждом шифровании или подписи утечка состояния ГПСЧ помогает вскрывать закрытый ключ.

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

Насчёт QRNG, совершенно верно. Где-то была реклама (или пруф-концепт?): в стойку ставится QRNG-сервер, который по обычному шифрованному каналу (канал здесь играет второстепенную роль, скорее для аутентификации; даже если с ним что-то не так, главное, что повторяющихся значений в энтропии не будет) раздаёт энтропию на все остальные серверы и драйвера виртуалок тоже берут необходимую часть от этого потока.

—	unknown (17/02/2012 09:39, исправлен 17/02/2012 12:27) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

(p₁ = p₂ и q₁ = q₂), или ключи имели общий только один модуль? Насколько я понимаю, если у меня и моего противника только один общий модуль в секретном ключе (выполнено только одно из вышенаписанных равенств), я не смогу восстановить его ключ. Я прав?

Итак, общий модуль — это в разделе 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 они что-то подобное замутили и построили граф таких кластеров:

each consisting of a single edge connecting two unidentified and supposedly unidentifiable primes. This turned out not to be the case: it took a matter of hours on a single core to find 1995 connected components that each consists of at least two edges.

Но подробности в явном виде не разжёвывают:

Much larger datasets can be handled without trouble. We chose not to describe the details of our calculation or how well it scales — sapienti sat. On a 1.8GHz i7 processor the straightforward approach would require about ten core-years and would not scale well.

Подозреваю, что они делили ключи перебором p'•q' / (p•q) или считали наибольший общий делитель (GCD) и на основе знания примерного соотношения p и q при создании ключа, искали остатки при сокращении или статистически обрабатывали какие-то более сложные зависимости. Там где один из множителей совпадает — должно быть отклонение по какому-то параметру.

Там же они и указывают правило, что по построенному графу можно посмотреть в каком положении по отношению к рёбрам/вершинам находятся эти n и в зависимости от положения их действительно можно факторизовать.

Вот и другое подозрительное место:

In order not to make it easier to re-derive our results, most information below refers to the joined set of unique values, not distinguishing between X.509 and PGP ones.

Not to make? Авторы всё-таки что-то темнят? Что-то с намёками во взаимоотношении PGP/X.509, чтобы их результаты было не так легко воспроизвести и использовать во вред раньше времени или предъявить претензии.

—	spinore (20/02/2012 05:39, исправлен 20/02/2012 05:42) профиль/связь <#> комментариев: 1515 документов: 44 редакций: 5786

< С PGP всё (почти?) хорошо. Достаточно было в новости отразить именно это. 
< Статистика по PGP-ключам довольно скучная.

Остаётся совершенно не понятным, где сидит ключевое отличие PGP от генерации сертификатов. Честно сказать, я без понятия как их генерируют, но это, наверное, OpenSSL. Неужели у него такие фатальные проблемы с безопасностью? Или это проблемы с окружением, в котором он исполняется? Действительно, создаётся впечатление, что где-то зияет страшная дыра, про которую никто не подозревает.
< 1. Слабый ключ
Что именно под этим подразумевается? Я бы пункты 2 и 3 тоже по формальным критериям отнёс к "слабым ключам".

Much larger datasets can be handled without trouble. We chose not to describe the details of our calculation or how well it scales — sapienti sat.

[...] not to make it easier to re-derive our results

Шок! В криптографии в научных публикациях разве не требуется full disclosure?! Такое могут принять в журнал к печати? Или с такими "sapienti sat" ("умному — достаточно") заявлениями можно отослать заявку на конференционный доклад? Признаться, я слабо представляю как устроен "иакр" изнутри, и что именно там публикуется. В архиве, за исключением PhD-диссеров, книг и редких исключений всё является либо препринтами статей, либо публикаций в трудах конференций, потому full disclosure необходимо. Те, кто сильно боятся, могут долго тянуть время до тех пор, пока работа не будет сделана полностью, но опубликуют её уже с полным раскрытием всего.

P.S.: новость, конечно, очень интересная. Спасибо за подробные разъяснения и за то, что нашли время перевести.

—	unknown (20/02/2012 10:23, исправлен 20/02/2012 11:02) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

>Честно сказать, я без понятия как их генерируют, но это, наверное, OpenSSL.

В GnuPG используется Libgcrypt.

< 1. Слабый ключ

Что именно под этим подразумевается? Я бы пункты 2 и 3 тоже по формальным критериям отнёс к "слабым ключам".

Справедливо. Совсем слабый. Факторизуется даже без поиска общих модулей. Кроме злополучных дебиановских модулей это ещё и Primality, small factors, and other tests, из-за которых

About 25% of the remaining 165 composites were fully factored after a modest search for small factors using the implementation from [29] of the elliptic curve method (ECM, cf. [16])

>Шок! В криптографии в научных публикациях разве не требуется full disclosure?!

Авторы известные и с репутацией (двое-трое из них точно), поэтому могут позволить себе и повыёжываться даже в официальной публикации. И, возможно, с не очень уместными шуточками и не до конца прояснёнными заявлениями. Основная причина скорее в том, что это очень неполный препринт, предназначенный только для того, чтобы застолбить тему, а полная версия будет представлена к CRYPTO-2012, т.е. к августу только.

Ошибка скорее в окружении (но это на уровне домыслов). И вывод в том, что слабый PRNG даёт слабые RSA ключи (причём один общий множитель хуже, чем оба — в первом случае возможна факторизация, во втором — просто расшаренный между двумя сторонами ключ). В этом "Рон проигрывает Виту". Но RSA-ключи, за счёт этого, проще проверить на вшивость. Что там скрывается в DH-based, если можно покопаться, прицельно зная уязвимости конкретного PRNG — тоже большое поле для фантазии.

—	*Гость* (20/02/2012 10:53) <#>

Где-то раньше была дыра буквально такого типа: функция

get_random_number() { return 2; }

И ГПСЧ винды тут ни причем — там уязвимости скорее теоретические, и до практического использования, как до Луны пешком. А бывали дыры и покруче, вплоть до того, что использовался сишный ранд или prng нициализировался константой. Одним словом, тупорылых реализаций хватает, а раньше их было еще больше. Стоит ли потому удивляться, что есть некоторое количество сертификатов сгенеренных с крупными косяками?

RNG может быть какой угодно, и софт может черпать энтропию откуда угодно — нет никаких «по-умолчанию». Разработчиков никто не заставляет использовать CryptGenRandom (более того, 90% тупых макак про него даже не слышали — пользуются сишным rand и инициализируют его временем, в лучшем случае). Отсюда и и дыры огромного размера в таком софте... А бывает, что не удосуживаются даже временем инициализировать: тупо юзают сишный ранд. Он тогда выдает одинаковую последовательность всегда и везде, и генерит одинаковые ключи (сид для ранда задается функцией srand и имеет размер 32 бита; обычно делают srand(time(NULL)), где time возвращает число секунд от unix-эпохи).

По уму надо использовать CryptGenRandom — стандартный RNG от CryptoAPI. Начиная с висты, появился CNG API — BCryptGenRandom. Софт же, защищенный RSA, очень часто оказывается сделан на основе ключей, сгенерированых от сишного ранда. Говорят, что есть даже крякерская тулза, которая берет ключ и прогоняет его через набор тестов, это определяющих.

Обычно же как делают? Ищут в гугле «как сделать то-то» и копипастят код к себе, а там что попалось, то попалось. Один и тот же насквозь кривой и неправильный код часто кочует через сотни форумов, являясь прямо-таки стандартом говнокодинга. Если исключить антивирусы и прочий софт крупных производителей, останется over 9000 всяких мелких программок, которые сразу понятно, что говно, прям из описания. Представления разработчиков зачастую совсем далеки от реальности :-(

—	unknown (20/02/2012 11:11) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Гость, спасибо, что приземлили дискуссию к реальности. Похоже на правду.

—	unknown (20/02/2012 12:09) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

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

—	SATtva (22/02/2012 18:06) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Таких сертификатов якобы нет ни на одном вэб-сайте и они якобы относятся только к роутерам ...

Раз исходные данные брались из SSL Observatory, стало быть эти рутеры благополучно висят в общедоступной сети. Интересно, сколько из них — в сетях крупных компаний? Так что считать проблему незначительной тоже вряд ли стоит.

Ваша оценка документа [показать результаты]