✔Новая атака снижает стойкость RSA и не требует факторизации - «Новости»
Исследователи разработали новый метод атаки на RSA, который позволяет подделывать цифровые подписи без факторизации RSA-модуля и восстановления приватного ключа. Для 1024-битного RSA такая атака уже практически реализуема, а стойкость ключей длиной 2048 и 4096 бит снижается до уровня, который считается недостаточным по современным стандартам.
До сих пор считалось, что для получения корректной RSA-подписи атакующему сначала придется разложить большое число на простые множители и восстановить приватный ключ, и стойкость RSA к таким атакам определяется сложностью факторизации больших чисел.
«Если выводы авторов этого исследования подтвердятся в ходе рецензирования, это действительно будет концептуальным прорывом. До сих пор считалось, что взломать RSA настолько же сложно, насколько трудно факторизовать большие целые числа. Эта работа показывает, что на практике RSA можно взломать, не взламывая сам ключ», — пояснил изданию Ars Technica известный криптограф Карстен Ноль (Karsten Nohl), глава направления инноваций Allurity.
В основе атаки лежит вариант алгоритма Number field sieve (NFS), предложенный еще в 2007 году. Причем злоумышленнику не нужно факторизовать RSA-модуль и восстанавливать приватный ключ. Вместо этого ему требуется временный доступ к «оракулу» — сервису или интерфейсу, который выполняет операции RSA с приватным ключом над переданными ему данными без паддинга.
Сделав большое количество запросов к такому оракулу и проведя предварительные вычисления, атакующий получает возможность впоследствии подделывать произвольные RSA-подписи офлайн. Иными словами, для подделки подписей атакующему уже не требуется знать приватный ключ.
Новая атака требует примерно 2^65 операций для 1024-битного RSA, и исследователи пишут, что реализовали ее в академическом CPU-кластере за несколько месяцев, а совокупный объем вычислений был эквивалентен примерно 1380 годам непрерывной работы одного процессорного ядра. Для сравнения, факторизация такого же ключа оценивается примерно в 2^80 операций и потребовала бы вычислительных ресурсов, эквивалентных 500 000–1 000 000 лет работы одного ядра.
Для ключей RSA длиной 2048 и 4096 бит криптостойкость снижается примерно до 90 и 119 бит соответственно, что заметно ниже минимального уровня в 128 бит, которого требуют NSA, NIST и ENISA.
При этом авторы работы подчеркивают, что писали весь код вручную, не применяя ИИ, а для вычислений не использовали GPU. Один из соавторов исследования, Надя Хенингер (Nadia Heninger), считает, что применение этих инструментов «почти наверняка» позволит еще сильнее снизить вычислительные затраты на атаку.
Впрочем, большинству распространенных сценариев использования RSA новая атака пока не угрожает. Дело в том, что атакующему понадобится временный доступ к оракулу, выполняющему «сырой» RSA без паддинга, и такой доступ могут предоставлять, например, некоторые реализации слепой RSA-подписи или интерфейсы аппаратных криптографических модулей (HSM). В то же время распространенные схемы RSA-подписи с PKCS#1 v1.5 или RSA-PSS такого оракула не предоставляют, поэтому сами исследователи считают атаку против них непрактичной.
Одним из заметных исключений является Privacy Pass — протокол, который позволяет пользователям проходить проверку без раскрытия своей личности и применяется, в частности, Apple и Cloudflare. Однако для атаки на него злоумышленнику потребуется запросить около 2^43 токенов, и по словам Хенингер, такой объем сопоставим с трафиком, который Cloudflare обычно обрабатывает за сутки. Кроме того, большинство имплементаций Privacy Pass регулярно меняют ключи, что заметно сокращает окно для возможной атаки (хотя не исключает ее полностью).
Авторы работы резюмируют, что в настоящее время практическая угроза невелика. Однако это исследование впервые демонстрирует, что при определенных условиях RSA-подписи можно подделывать без факторизации RSA-модуля и восстановления приватного ключа.
