Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 <p>Проект<a>Factorable</a>создан криптографами из Мичиганского университета и университета Сан Диего. Эта заметка - сжатый рассказ о статье<a>"Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices"</a>, опубликованной на USENIX Security Symposium'12.</p>

2 <p><strong>Цель Factorable</strong>- выявление уязвимых открытых ключей<a>RSA</a>и<a>DSA</a>, сгенерированных и используемых в протоколах TLS/SSH.</p>

3 <p><strong>Суть</strong>проекта заключается в следующем: сканируются IP-адреса на наличие открытого TLS/SSH соединения, используя, например,<strong>nmap</strong>. Далее выполняется попытка осуществления соединения по соответствующему протоколу, в процессе которого, как и положено, стороны обмениваются открытыми ключами. Так, в результате успешного соединения за достаточно короткое время можно собрать большое количество открытых ключей. В этом исследовании за несколько дней было собрано порядка 6 миллионов открытых ключей, используемых в TLS, и столько же в результате SSH-соединений.</p>

4 <p>В теории, корректно сгенерированный открытый ключ криптосистемы не позволяет (за разумное время) узнать что-либо о соответствующем секретном ключе.</p>

5 <p>Так ли это на практике?</p>

6 <h2>Результаты исследования</h2>

7 <p>Почти так. Порядка 5% открытых ключей протокола HTTPS и 10 % ключей SSH попали под категорию "уязвимых" (это только говорит о возможности атаки). Более серьёзно пострадали 0.5% ключей TLS и 1% SSH-ключей: для них был эффективно восстановлен секретный ключ. О том, насколько эти величины вызывают опасения, каждый судит сам для себя.</p>

8 <p>Поговорим подробнее о классификации ключей в категорию уязвимых/сломанных. В данном исследовании, открытый ключ получил красный флаг, если: - он повторился у<em>не связанных</em>между собой хостов; - для ключа RSA N нашёлся другой ключ RSA N' с одинаковым делителем; - при выполнении алгоритма подписи DSA дважды использовался один и тот же эфемерный ключ; - открытый ключ RSA N имеет несколько малых простых делителей.</p>

9 <h3>Ключ повторился у<em>не связанных</em>между собой хостов</h3>

10 <p>Само по себе повторение открытого ключа не является уязвимостью: такой сценарий логичен, если несколько (одинаковых) ключей принадлежат одному большому провайдеру или же одной организации (пример: TLS-хосты на google.com имеют разные сертификаты с одним открытым ключом). В этом случае ключ не является уязвимым.</p>

11 <p>Другое дело, если два независимых хоста имеют одинаковый открытый ключ. А значит, их секретные ключи эквивалентны при дешифровании RSA. Зная о существовании такого "брата-близнеца", можно использовать свой секретный ключ для получения конфиденциальны данных его соединений. Естественно, это работает и в обратную сторону.</p>

12 <p>Одна из причин появления таких уязвимых ключей лежит в некорректном алгоритме генерации секретных ключей: малое количество энтропии (случайных бит) при генерации простых чисел p и q;</p>

13 <h3>Для ключа RSA N нашёлся другой ключ RSA N' с одинаковым делителем</h3>

14 <p>То есть если N = p<em>q, то N' = p</em>q'. В таком случае, факторизация N и N' превращается из трудной задачи в элементарную, достаточно лишь посчитать наибольший общий делитель для N и N': gcd(N,N') = p, а значит, q = N/p, q' = N'/p.</p>

15 <p>Задача становится менее тривиальной, если надо посчитать<strong>gcd</strong>сразу для нескольких миллионов значений N, но и для этой задачи уже давно существует эффективный алгоритм. Он носит название<strong>batch-gcd</strong>и имеет древовидную структуру. На рисунке ниже, взятом из<a>оригинальной статьи</a>, показан пример подсчета<strong>gcd</strong>для всевозможных пар 4-х значений N.</p>

16 <p>Для исследуемого количества модулей N вычисление заняло порядка нескольких часов. Оно позволило получить секретные значения для 0.5 % ключей TLS. Причина всё в том же: недостаток энтропии при генерации значений p и q;</p>

17 <h3>При выполнении алгоритма подписи DSA дважды использовался один и тот же эфемерный ключ</h3>

18 <p>В этом случае, элементарные вычисления позволяют получить секретный ключ DSA при наличии двух сообщений, подписанных одним DSA-ключом. Таким образом, были получены порядка 300 секретных DSA ключей. Здесь опять виновато недостаточное количество энтропии при генерации подписи;</p>

19 <h3>Открытый ключ RSA N имеет несколько малых простых делителей</h3>

20 <p>Таких нашлось аж 12 штук.</p>

21 <h2>Вывод</h2>

22 <p>Если результаты этого исследования покажутся вам пессимистичными, не стоит сильно расстраиваться: большинство уязвимых хостов, как сообщают исследователи, принадлежали так называемым<em>"встраиваевым устройствам"</em>(embedded devices) или системам без устройства ввода/вывода (роутеры, firewalls и другие сетевые устройства), которые, как правило, генерируют ключи автоматически при первой загрузке и имеют лимитированные генераторы случайных значений.</p>

23 <p><em>На этом пока всё, задать вопросы можно в комментариях!</em></p>