Factorable: насколько уязвим ваш открытый ключ
Проект Factorable создан криптографами из Мичиганского университета и университета Сан Диего.
Цель 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.
Для исследуемого количества модулей N вычисление заняло порядка нескольких часов. Оно позволило получить секретные значения для 0.5 % ключей TLS. Причина всё в том же: недостаток энтропии при генерации значений p и q;
При выполнении алгоритма подписи DSA дважды использовался один и тот же эфемерный ключ
В этом случае, элементарные вычисления позволяют получить секретный ключ DSA при наличии двух сообщений, подписанных одним DSA-ключом. Таким образом, были получены порядка 300 секретных DSA ключей. Здесь опять виновато недостаточное количество энтропии при генерации подписи;
Открытый ключ RSA N имеет несколько малых простых делителей
Таких нашлось аж 12 штук.
Вывод
Если результаты этого исследования покажутся вам пессимистичными, не стоит сильно расстраиваться: большинство уязвимых хостов, как сообщают исследователи, принадлежали так называемым «встраиваевым устройствам» (embedded devices) или системам без устройства ввода/вывода (роутеры, firewalls и другие сетевые устройства), которые, как правило, генерируют ключи автоматически при первой загрузке и имеют лимитированные генераторы случайных значений.
На этом пока всё, задать вопросы можно в комментариях!
