Факторизация RSA-ключей с множеством нулей

Вышло интересное исследование, посвященное новому классу слабых RSA-ключей: тем, которые содержат большое количество нулей. Оказалось, что такие уязвимые ключи активно используются в реальном мире.

Проект badkeys, являющийся сервисом с открытым исходным кодом для проверки публичных ключей на известные уязвимости, собрал огромный массив реальных ключей из различных общедоступных источников. Среди них были логи прозрачности сертификатов (Certificate Transparency logs), результаты сканирования TLS и SSH в интернете, PGP-ключи и многие другие. Анализируя этот набор данных в поисках необычно разреженных RSA-модулей, исследователи обнаружили значительное количество ключей, используемых в реальных системах, которые соответствовали определенным паттернам.

Были идентифицированы два основных паттерна. Оба включали несколько регулярно расположенных блоков, полностью состоящих из нулей, чередующихся с, казалось бы, случайными данными. Паттерн 1 был замечен в логах прозрачности сертификатов, выданных нескольким крупным организациям, включая Yahoo и Verizon, а также на некоторых устройствах, использующих программное обеспечение NetApp. К счастью, эти сертификаты уже истекли. Паттерн 2 встречается на SSH-хостах, работающих под управлением программного обеспечения CompleteFTP от EnterpriseDT. Эта уязвимость затрагивает RSA-ключи, сгенерированные в версиях 10.0.0–12.0.0 (декабрь 2016 – март 2019), и DSA-ключи, сгенерированные в версиях 10.0.0–23.0.4 (декабрь 2016 – декабрь 2023).

Хотя эти уязвимости затрагивают относительно небольшое количество хостов в интернете, более важный вывод заключается в том, что независимые криптографические реализации потерпели неудачу схожим образом. Это предполагает, что аналогичные ошибки могут быть присущи и другим реализациям, что делает целесообразным адаптировать криптоаналитические алгоритмы для этого конкретного типа сбоев.

В оригинальной статье нет предположений, но я позволю себе выдвинуть гипотезу. Это вполне может быть преднамеренно разработанный бэкдор, о которых я писал еще в 2013 году. Можно представить, как какое-либо правительственное агентство находит способ взломать этот класс RSA-ключей, а затем убеждает различных поставщиков распространять их среди пользователей.