Криптографы показали практическую подделку RSA‑подписей без факторизации ключа

Новое исследование представило ^[1] метод, использующий классические вычислительные мощности для снижения текущего уровня безопасности RSA до неприемлемо низкого предела. Применение атаки к устаревшим 1024-битным ключам заняло всего несколько месяцев на академическом кластере процессоров.

Отмечается, что это значительно меньше, чем требовалось согласно прежним оценкам для факторизации 1024-битных ключей — задачи, для решения которой были нужны ресурсы, доступные лишь государствам или крупнейшим корпорациям. При этом широко распространённые реализации RSA остаются в безопасности.

Тем не менее, результаты исследования стали неожиданностью для криптографов, поскольку они открывают возможность подделки цифровых подписей — новый способ взлома RSA без факторизации ключа. Не менее важно и то, что этот метод на порядки снижает объём необходимых вычислительных ресурсов.

«Если этот результат подтвердится в ходе экспертной оценки, это действительно станет концептуальным прорывом, — отметил Карстен Ноль, эксперт по криптографии и руководитель отдела инноваций компании Allurity. — Считалось, что взломать RSA так же сложно, как разложить на множители большие целые числа. Теперь же исследователи показывают, что RSA можно практически взломать, не вскрывая сам ключ».

Надя Хенингер, профессор Калифорнийского университета в Сан‑Диего и соавтор исследования, пояснила: «Криптографы полагали, что единственный способ сформировать корректную цифровую подпись RSA — это сначала вычислить закрытый ключ путём факторизации, а затем использовать его для создания подписи. Для 1024-битного RSA эта задача считалась очень затратной, хотя и выполнимой при наличии вычислительных мощностей уровня крупных технологических компаний или АНБ (стоимость машинного времени для взлома одного ключа исчислялась бы десятками миллионов долларов). Что касается 2048-битного RSA, то такая задача казалась совершенно невыполнимой».

Разработанный Хенингер и её коллегами метод атаки, позволяющий подделывать ключи, уже вполне применим на практике для 1024-битных ключей RSA. Даже для ключей длиной 2048 и 4096 бит этот метод снижает уровень безопасности RSA до неприемлемых значений. Агентство национальной безопасности (АНБ) США, Национальный институт стандартов и технологий (NIST) и Агентство Европейского союза по кибербезопасности (ENISA) требуют, чтобы криптосистема обеспечивала уровень безопасности не ниже 128 бит (то есть требовала выполнения более 2¹²⁸ операций).

Данная атака, направленная на подделку подписей, снижает ^[2] эти показатели до 2⁶⁵, 2⁹⁰ и 2¹¹⁹ для ключей длиной 1024, 2048 и 4096 бит соответственно. Эти уровни могут снизиться ещё больше, поскольку команда Хенингер выполняла все операции по программированию вручную, не задействуя искусственный интеллект ^[3] или графические процессоры. Исследовательница отметила, что использование таких инструментов «почти наверняка» приведёт к дальнейшему снижению уровня безопасности.

Атака применима только к реализациям RSA, использующим схему слепой подписи. В подавляющем большинстве современных систем применяется дополнение (padding) по стандартам PKCS или PSS — формат, при котором к открытому тексту перед шифрованием добавляются дополнительные данные. Это предотвращает детерминированность шифротекста и снижает уязвимость к атакам по сторонним каналам и другим подобным угрозам. Тем не менее, в некоторых реальных системах по‑прежнему используется RSA со слепой подписью (также известный как «учебный» или «базовый» RSA). По словам Хенингер, самым известным примером является протокол Privacy Pass, позволяющий пользователям проходить аутентификацию без раскрытия своей личности. Privacy Pass используется такими компаниями, как Apple и Cloudflare.

Для проведения атаки на Privacy Pass злоумышленнику потребовалось бы запросить токены у Cloudflare, Apple или другой организации 2⁴³ раз.

Хенингер отметила, что это требование «кажется внушительным, но сопоставимо по порядку величины с объёмом сетевого трафика, который, по публичным заявлениям Cloudflare, компания обрабатывает примерно за сутки». В большинстве реализаций Privacy Pass ключи регулярно обновляются; эта мера значительно снижает вероятность успеха атаки, хотя и не исключает её полностью. В данном методе реализована разновидность алгоритма «решето числового поля», разработанная в 2007 году. Это так называемое «специальное решето числового поля» используется в сочетании с «оракулом» — компонентом некоторых криптографических протоколов, выдающим ответы на определённые запросы. Выполняя огромное количество операций, злоумышленники могут собрать достаточно информации для расшифровки зашифрованного текста. Если для факторизации 1024-битного ключа требуется, по оценкам, $2^{80}$ операций и от 500 тысяч до 1 миллиона «ядро‑лет» вычислений, то для подделки подписи с помощью данного метода решета понадобилось всего $2^{65}$ операций и 1380 «ядро‑лет».

Авторы работы и другие исследователи подчёркивают, что новая атака практически не представляет реальной угрозы — по крайней мере, на данный момент. Тем не менее, она существенно снижает оценочный уровень безопасности RSA, причём делает это способом, о котором ранее не было известно.

Криптографы в последние годы вели активную работу над созданием альтернативных криптосистем, устойчивых к атакам с использованием квантовых вычислений. Новый метод атаки делает полный отказ от данной криптосистемы ещё более неотложной задачей.

Ранее команда квантовых физиков из Калифорнийского технологического института представила ^[4] проект квантового компьютера, способного взламывать шифрование RSA и ECC всего лишь с помощью десятков тысяч кубитов, и заявила о создании компании для его разработки. Между тем исследователи из Google объявили о разработке реализации алгоритма Шора, которая в десять раз эффективнее лучшего из предыдущих методов.