Метод атаки, значительно сокращающий ресурсы для подделки цифровых подписей RSA

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

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

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

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

Используя специальный метод решета числового поля (SNFS) исследователям удалось свести сложность компрометации ключей RSA-1024 до 265 операций, что позволяет осуществлять практические атаки на современных кластерах. Для 2048-разрядных ключей RSA сложность атаки оценивается в 290, что теоретически осуществимо крупными корпорациями или спецслужбами. Для 4096-разрядных ключей сложность атаки составляет 2119 операций, что на практике пока недостижимо, но ниже минимума 2128, рекомендуемого АНБ, Национальным институтом стандартов и технологий и Европейским агентством по сетевой и информационной безопасности.

Источник: opennet.ru