Исследователи обнаружили способ подделывать RSA-подписи без разложения ключа на множители — это ставит под сомнение казавшуюся незыблемой основу безопасности одной из самых распространённых криптосистем интернета.
Уязвимость касается только систем со слепой подписью, известной как «RSA по учебнику», которая позволяет подписывать данные, не зная их содержания. Большинство рабочих реализаций RSA используют дополнение по стандартам PKCS или PSS и атаке не подвержены.
Пример практического применения слепой подписи — протокол Privacy Pass, который используют Apple и Cloudflare для анонимного подтверждения полномочий пользователей. Для атаки эмитенту пришлось бы запросить 243 токена — объём, сопоставимый с нагрузкой крупного онлайн-сервиса. Регулярная смена ключей усложняет, но не устраняет риск полностью.
Метод основан на модифицированном алгоритме решета числового поля и использовании оракула, применяемого в некоторых протоколах слепой подписи. Собирая огромное количество ответов на запросы, злоумышленник может накопить данные, достаточные для генерации валидной подписи без факторизации ключа.
Атака практически применима к устаревшим 1024-битным ключам и снижает оценку надёжности 2048- и 4096-битных ключей в уязвимых системах. Для сравнения: факторизация 1024-битного ключа требует около 2^80 операций и до 1 млн ядро-лет, а атака на подпись — 2^65 операций, или 1380 ядро-лет.
Для ключей длиной 2048 и 4096 бит показатели составляют 2^90 и 2^119 операций соответственно. Исследователи не применяли GPU или инструменты ИИ, которые, по их мнению, почти наверняка упростят подобные атаки в будущем.