Исследователи нашли новый способ подделки подписей в некоторых реализациях RSA, однако непосредственная угроза для большинства используемых систем остаётся небольшой. Работа затрагивает только RSA со слепыми подписями, который также называют «учебниковым» RSA. Обычные варианты с дополнением PKCS или PSS защищены от этого метода, поскольку делают шифротекст недетерминированным и снижают уязвимость к атакам по побочным каналам.
По оценке команды Хенингера, для ключей длиной 1024, 2048 и 4096 бит уровень безопасности при атаке снижается соответственно до 265, 290 и 2119 операций. Эти показатели могут стать ещё ниже: исследователи писали код вручную и не применяли искусственный интеллект или графические процессоры. По словам учёного, использование таких инструментов «почти наверняка» позволит дополнительно уменьшить требуемые вычислительные затраты.
Метод основан на варианте алгоритма решета числового поля, созданного в 2007 году. Он применяется против так называемого оракула — слабого места в RSA и некоторых других криптосистемах, которое отвечает «да» или «нет» на специальные запросы. Выполнив огромное количество операций, злоумышленник может собрать достаточно данных для расшифровки сообщения.
Для факторизации 1024-битного ключа требуется около 280 операций и от 500 тысяч до 1 млн процессорных лет. Подделка подписи с помощью нового варианта решета потребовала примерно 265 операций и 1380 процессорных лет. При этом PKCS и PSS устраняют используемый оракул, поэтому против RSA с такими дополнениями описанная техника практически не работает.
Слепые подписи всё ещё применяются в некоторых реальных системах. Самым известным примером Хенингер назвал Privacy Pass — протокол, позволяющий подтверждать личность без её раскрытия; его используют Apple, Cloudflare и другие компании. Атака на Privacy Pass потребовала бы получить контроль над сервером одной из таких организаций и создать 243 подписей, что, по словам исследователя, сопоставимо с объёмом сетевого трафика, который Cloudflare, как сообщала ранее, обрабатывает примерно за сутки.
Регулярная смена ключей в большинстве реализаций Privacy Pass существенно уменьшает вероятность успешной атаки, хотя полностью её не исключает. Авторы работы и другие криптографы считают, что практическая опасность нового метода невелика, но он заметно снижает прежние оценки стойкости «учебникового» RSA. Как сообщает Ars Technica, открытие также усиливает необходимость перехода на криптосистемы, устойчивые к атакам с использованием квантовых компьютеров.