Исследователи создали способ атаки на RSA, позволяющий подделывать цифровые подписи без разложения RSA-модуля на множители и без знания приватного ключа. Для 1024-битного RSA такая атака уже близка к практической реализации, а для ключей длиной 2048 и 4096 бит криптостойкость падает ниже допустимых норм.
Раньше считалось, что единственный способ получить корректную RSA-подпись — факторизовать большое число и восстановить приватный ключ. Стойкость RSA определялась сложностью этой факторизации.
Метод основан на модификации алгоритма Number field sieve (NFS) из 2007 года. Злоумышленнику не нужна факторизация. Вместо этого требуется временный доступ к «оракулу» — сервису, выполняющему операции RSA с приватным ключом над переданными данными без защитного паддинга.
После множества запросов к такому оракулу и предварительных вычислений атакующий может подделывать RSA-подписи офлайн, не зная приватного ключа.
Новая атака требует примерно 2^65 операций для 1024-битного RSA. Исследователи реализовали её в CPU-кластере за несколько месяцев, что эквивалентно примерно 1380 годам работы одного процессорного ядра. Взлом через факторизацию того же ключа потребовал бы 500 000–1 000 000 лет вычислений.
Для ключей длиной 2048 и 4096 бит криптостойкость составляет примерно 90 и 119 бит соответственно — это ниже минимума в 128 бит, установленного NSA, NIST и ENISA.
Авторы подчеркивают, что писали код вручную без ИИ и не использовали GPU. По мнению соавтора Надии Хенингер, применение этих инструментов позволит ещё снизить затраты на атаку.
Однако практическая угроза пока ограничена. Атаке требуется доступ к оракулу, выполняющему «чистый» RSA без паддинга. Такой доступ могут предоставлять некоторые реализации слепой подписи или интерфейсы аппаратных криптомодулей, но обычные схемы RSA с PKCS#1 v1.5 или RSA-PSS его не предоставляют.
Исключение — протокол Privacy Pass, используемый Apple и Cloudflare. Для атаки на него потребуется около 2^43 токенов, что сопоставимо с суточным трафиком Cloudflare. Большинство реализаций Privacy Pass регулярно меняют ключи, сокращая окно для атаки.
Авторы резюмируют: угроза на данный момент невелика. Но исследование впервые доказывает, что при определённых условиях RSA-подписи можно подделывать без факторизации модуля и восстановления приватного ключа.
