В Сан-Диего снизили цену подделки подписи RSA без закрытого ключа

В Калифорнийском университете в Сан-Диего описали усовершенствованную атаку на RSA, при которой цифровую подпись можно подделать, не раскладывая модуль на простые множители и не восстанавливая закрытый ключ. Для ключа длиной 1024 бита нужные ресурсы оценили в 1380 лет работы одного процессорного ядра. На университетском кластере параметры, без которых фиктивные подписи не собрать, определили за пять месяцев.

В расчёте не участвовали графические процессоры и ускорители для искусственного интеллекта; с ними, отмечают авторы, срок мог бы заметно сжаться. Классическая факторизация для восстановления закрытого ключа RSA-1024, по той же оценке, занимает от 500 тысяч до миллиона лет на одном ядре. Разница и есть смысл работы: компрометация подписи отделена от задачи, которая до сих пор считалась главным барьером для ключей этой длины.

Атака невозможна вслепую. Нужно многократно просить систему подписать данные, которые формирует сам атакующий, например через сервис авторизации или аппаратный модуль HSM. Для RSA-1024 хватает 232 таких запросов.

Для ключей RSA-2048, которые применяются в протоколе Privacy Pass, оценка вырастает до 243 запросов. Дальше начинается долгий счёт. Для RSA-1024 речь идёт примерно о 265 операциях.

Когда параметры получены, подпись можно ставить уже под произвольные данные, но каждая такая подделка всё ещё стоит около 180 часов на одном ядре. Это не мгновенный обход, а смещение границы: сначала дорогой подготовительный этап, затем повторяемая, хотя и недешёвая, подделка. Ограничение метода важнее самой цифры.

Он работает только там, где перед шифрованием не применяют форматирование и добавочное заполнение, padding. Уязвимы реализации слепой подписи, в том числе схема внутри Privacy Pass. Распространённые варианты PKCS#1 v1.5 и RSA-PSS, на которых держатся TLS и SSH, заполнение используют и этой атаке не подвержены.

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

Новая техника не отменяет эту конструкцию, а показывает, что для подписи без padding секретные множители знать не обязательно. Опора — исследование 2007 года. Тогда было показано, что извлечь корень указанной в открытом ключе степени из зашифрованного сообщения, не имея секретных множителей, дешевле, чем факторизовать эти множители.

В Сан-Диего довели эту идею до оценок, которые уже можно сопоставлять с реальным кластером. Специальный вариант решета числового поля, SNFS, снизил сложность компрометации RSA-1024 до 265 операций — уровня, на котором атака на современных кластерах перестаёт быть чисто теоретической. Для 2048-разрядных ключей сложность оценили в 290.

Такой объём, по мнению исследователей, теоретически по силам крупным корпорациям или спецслужбам, но не рядовому злоумышленнику с одним сервером. Для ключей RSA-4096 оценка составляет 2119 операций. На практике это пока недостижимо, однако цифра уже ниже порога 2128, который как минимум рекомендуют АНБ, Национальный институт стандартов и технологий и Европейское агентство по сетевой и информационной безопасности.

Для тех, кто ещё выпускает подписи без padding, длина ключа сама по себе этот путь не закрывает, а распространённые протоколы с заполнением в описанной работе остаются вне зоны риска.