Factorable: насколько уязвим ваш открытый ключ | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Backend-разработчик на PHP Алгоритмы и структуры данных Team Lead Архитектура и шаблоны проектирования Разработчик IoT C# Developer. Professional HTML/CSS
-11%
C# ASP.NET Core разработчик
-5%
Kotlin Backend Developer
-8%
iOS Developer. Professional
-8%
Symfony Framework Unity Game Developer. Basic JavaScript Developer. Professional Android Developer. Basic JavaScript Developer. Basic Java Developer. Professional Highload Architect Reverse-Engineering. Professional Java Developer. Basic Web-разработчик на Python Framework Laravel Cloud Solution Architecture Vue.js разработчик Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив "Tarantool" PHP Developer. Basic
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK Administrator Linux. Professional Дизайн сетей ЦОД Разработчик IoT PostgreSQL Экспресс-курс "Версионирование и командная работа с помощью Git"
-30%
Microservice Architecture Highload Architect MS SQL Server Developer Разработчик программных роботов (RPA) на базе UiPath и PIX Разработчик голосовых ассистентов и чат-ботов Administrator Linux. Advanced Infrastructure as a code Супер-практикум по использованию и настройке GIT Administrator Linux.Basic Экспресс-курс «IaC Ansible» Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» Основы Windows Server
Корпоративные курсы
Безопасность веб-приложений IT-Recruiter Дизайн сетей ЦОД Компьютерное зрение Разработчик IoT Вебинар CERTIPORT Machine Learning. Professional
-6%
NoSQL Пентест. Практика тестирования на проникновение Java QA Engineer. Базовый курс Руководитель поддержки пользователей в IT
-8%
SRE практики и инструменты Cloud Solution Architecture Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Infrastructure as a code Супер-практикум по использованию и настройке GIT Промышленный ML на больших данных Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» BPMN: Моделирование бизнес-процессов Основы Windows Server
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться