Курсы

Курсы в разработке Подготовительные курсы
Работа в компаниях Компаниям Блог +7 499 110-61-65

Factorable: насколько уязвим ваш открытый ключ

Crypto_Deep_29.4_site-5020-02de85.png

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

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

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

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

Так ли это на практике?

Результаты исследования

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

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

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

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

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

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

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

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

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

BatchFactoring-36085-d0999b.png

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

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

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

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

Таких нашлось аж 12 штук.

Вывод

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

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

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться