Уязвимость в RSA: учёные обнаружили способ подделки подписей без доступа к закрытому ключу

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

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

Для разложения 1024-битного ключа требуется около 280 операций, что эквивалентно 500 тысячам до 1 миллиона «ядро-лет» вычислений. В то время как для осуществления атаки на подделку подписи понадобилось выполнить всего 265 операций, что соответствует 1380 ядро-годам вычислений. Для ключей длиной 2048 и 4096 бит требуется соответственно 290 и 2119 операций. Исследователи предполагают, что в будущем эти показатели могут быть улучшены. Алгоритм был реализован без использования графических процессоров и инструментов искусственного интеллекта, которые могли бы упростить выполнение подобных атак в дальнейшем.

Атака применяется только в системах с механизмом слепой подписи, который позволяет подписывать данные без знания их содержания. Однако большинство современных реализаций RSA используют дополнение данных по стандартам PKCS или PSS, что усложняет задачу злоумышленников. Примером использования слепой подписи является протокол Privacy Pass, позволяющий подтверждать полномочия пользователей без раскрытия их личности, который применяют такие компании, как Apple и Cloudflare. Для атаки на систему Privacy Pass потребовалось бы запросить 243 токена, что хотя и является значительным объёмом, вполне сопоставимо с масштабами работы крупных онлайн-сервисов. В ряде систем ключи регулярно обновляются, что дополнительно усложняет атаку, сокращая время для сбора токенов.