Factorable: насколько уязвим ваш открытый ключ | OTUS
🔥 Начинаем BLACK FRIDAY!
Максимальная скидка -25% на всё. Успейте начать обучение по самой выгодной цене.
Выбрать курс

Курсы

Программирование
iOS Developer. Basic
-25%
Python Developer. Professional
-25%
Разработчик на Spring Framework
-25%
Golang Developer. Professional
-25%
Python Developer. Basic
-25%
iOS Developer. Professional
-25%
Highload Architect
-25%
JavaScript Developer. Basic
-25%
Kotlin Backend Developer
-25%
JavaScript Developer. Professional
-25%
Android Developer. Basic
-25%
Unity Game Developer. Basic
-25%
Разработчик C#
-25%
Программист С Web-разработчик на Python Алгоритмы и структуры данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Vue.js разработчик VOIP инженер Программист 1С Flutter Mobile Developer Супер - интенсив по Kubernetes Symfony Framework Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-25%
DevOps практики и инструменты
-25%
Архитектор сетей
-25%
Инфраструктурная платформа на основе Kubernetes
-25%
Супер-интенсив «IaC Ansible»
-16%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-25%
Administrator Linux. Professional MS SQL Server Developer Безопасность Linux PostgreSQL Reverse-Engineering. Professional CI/CD VOIP инженер Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Administrator Linux.Basic Супер-интенсив «ELK»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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 комментариев
Для комментирования необходимо авторизоваться
🎁 Максимальная скидка!
Черная пятница уже в OTUS! Скидка -25% на всё!