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

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

Атакующим не нужно полностью взламывать закрытый ключ

RSA остаётся одной из наиболее известных криптографических систем. В разных вариантах она применяется для цифровых подписей, аутентификации и других криптографических операций.

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

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

Новая работа демонстрирует другой сценарий. Для некоторых схем добиться возможности создавать допустимые подписи можно, не проходя весь путь восстановления закрытого ключа.

Как устроен новый метод

Исследователи задействовали разновидность специального решета числового поля в сочетании с доступом к оракулу подписи, присутствующему в определённых протоколах слепых RSA-подписей.

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

Таким образом, задача меняется принципиально: вместо полного решения проблемы факторизации злоумышленник использует особенности конкретного протокола и взаимодействует с легитимным механизмом подписания.

Именно поэтому результаты исследования не следует трактовать как универсальный способ взлома RSA.

Для 1024-битного RSA атака заметно дешевле факторизации

Особенно интересным оказалось сравнение вычислительных затрат.

По оценкам исследователей, факторизация 1024-битного RSA-модуля потребовала бы порядка 2^80 операций и от 500 тыс. до 1 млн ядро-лет процессорного времени.

Предложенная атака на подпись оценивается примерно в 2^65 операций. В пересчёте на использованные авторами оценки вычислительных ресурсов это соответствует приблизительно 1380 ядро-годам.

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

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

Что происходит с RSA-2048 и RSA-4096

Исследователи рассмотрели и более длинные ключи. Для 2048-битного RSA оценочная сложность предложенного подхода составляет около 2^90 операций, а для 4096-битного — примерно 2^119.

Это колоссальные значения, поэтому говорить о простом практическом взломе современных RSA-ключей нельзя.

Авторы работы при этом допускают возможность дальнейшей оптимизации метода. Представленная реализация не использовала вычисления на графических процессорах и методы на основе искусственного интеллекта.

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

Обычным RSA-подписям атака напрямую не угрожает

Важнейшее ограничение нового метода заключается в требованиях к атакуемой системе.

Он рассчитан на определённые схемы слепой подписи, использующие очень простой вариант RSA, который иногда называют «учебным» или textbook RSA.

Слепая подпись позволяет получить криптографическое подтверждение для данных таким образом, чтобы сторона, выполняющая операцию подписания, не обязательно знала содержимое исходного сообщения.

Такие свойства востребованы в системах, где одновременно необходимо подтвердить определённое право пользователя и сохранить конфиденциальность его действий.

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

Поэтому описанный исследователями механизм нельзя непосредственно перенести на большинство современных систем, использующих корректно реализованные стандартизированные RSA-подписи.

В зоне внимания оказался Privacy Pass

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

Подобные технологии применяются в инфраструктуре крупных интернет-компаний, включая Apple и Cloudflare.

По расчётам исследователей, для реализации описанного подхода против соответствующего варианта такой системы потребовалось бы запросить у эмитента порядка 2^43 токенов.

Это чрезвычайно большое количество запросов. Однако исследование обращает внимание на то, что при масштабах крупнейших интернет-платформ оценивать подобные числа следует не так, как в случае с небольшой локальной системой.

Серьёзным препятствием для злоумышленника становится регулярная ротация криптографических ключей. Если эмитент часто заменяет ключ, атакующему приходится успеть собрать необходимый объём информации до завершения срока его использования.

Ротация ключей существенно усложняет практическую атаку

В реальных системах срок жизни криптографического ключа может оказаться не менее важным фактором, чем математическая сложность самой атаки.

Если для накопления необходимого материала требуются миллиарды или триллионы запросов, но ключ заменяется раньше, собранные данные могут потерять практическую ценность.

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

Тем не менее само наличие подобного класса атак представляет интерес для разработчиков криптографических протоколов.

RSA не оказался внезапно взломан

Главный результат исследования заключается не в появлении универсального инструмента для взлома RSA. Современные реализации с корректными схемами формирования подписей непосредственно под действие предложенного метода не попадают.

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

Именно поэтому безопасность криптографической системы определяется не только длиной ключа и стойкостью лежащей в её основе математической задачи. Не менее важны конкретный протокол, формат подписи, правила работы с ключами и ограничения, предусмотренные практической реализацией.