Исследователи из Калифорнийского университета в Сан-Диего разработали усовершенствованную технику атаки на алгоритм RSA, позволяющую подделывать цифровые подписи без факторизации лежащих в основе RSA простых чисел и без необходимости восстановления закрытого ключа. Ресурсы, необходимые для совершения атаки на 1024-разрядный ключ RSA, оценены в 1380 лет вычислений на одном процессорном ядре, что на имеющемся университетском кластере позволило за 5 месяцев определить параметры, необходимые для формирования фиктивных RSA-подписей (в эксперименте не использовались AI-ускорители и GPU, при их применении время вычислений может существенно сократиться). Для сравнения классический метод факторизации требует для воссоздания закрытого ключа RSA-1024 от 500 тысяч до миллиона лет вычислений на одном процессором ядре.

Для проведения атаки требуется наличие возможности многократно отправлять запросы на подписание формируемых атакующим данных, например, обращаясь к сервису авторизации или HSM-модулю. Для определения параметров RSA-1024 достаточно отправить 2³² подобных запросов, а для атаки на ключи RSA-2048, используемые в протоколе Privacy Pass, - 2⁴³. После получения массива подписанных данных запускается длительный процесс вычисления параметров (для RSA-1024 примерно 2⁶⁵ операций), после получения которых атакующий может создавать фиктивные подписи для любых данных, затрачивая на каждую подпись примерно 180 часов вычислений на одном ядре.

Метод применим только для RSA-подписей, в которых не используется форматирование и добавочное заполнение перед шифрованием (padding). Атаке подвержены реализации слепой подписи, в том числе используемые в протоколе Privacy Pass. Большинство находящихся в обиходе реализаций RSA, включая PKCS#1v1.5 и RSA-PSS (используются в TLS и SSH), применяют добавочное заполнение и атаке не подвержены.

В основе шифрования RSA лежит операция возведения в степень по модулю большого числа. В открытом ключе содержится модуль и степень. Модуль формируется на основании двух случайных простых чисел, которые известны только владельцу закрытого ключа. Предложенный метод основан на опубликованном в 2007 году исследовании, доказавшем, что извлечение корня в указанной в открытом ключе степени из зашифрованного сообщения без информации о секретных множителях является менее ресурсоёмкой операцией, чем факторизация самих множителей.

Используя специальный метод решета числового поля (SNFS) исследователям удалось свести сложность компрометации ключей RSA-1024 до 2⁶⁵ операций, что позволяет осуществлять практические атаки на современных кластерах. Для 2048-разрядных ключей RSA сложность атаки оценивается в 2⁹⁰, что теоретически осуществимо крупными корпорациями или спецслужбами. Для 4096-разрядных ключей сложность атаки составляет 2¹¹⁹ операций, что на практике пока недостижимо, но ниже минимума 2¹²⁸, рекомендуемого АНБ, Национальным институтом стандартов и технологий и Европейским агентством по сетевой и информационной безопасности.