Новый метод атаки на RSA позволяет подделывать подписи без ключа

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

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

Эксперимент показал, что для 1024-битного ключа атака требует около 2 в 65 степени операций. На академическом кластере исследователи реализовали её за несколько месяцев, что потребовало значительно меньше ресурсов, чем стандартная факторизация. Для более длинных ключей на 2048 и 4096 бит эффективная криптостойкость снижается до 90 и 119 бит соответственно, что ниже современных минимальных стандартов безопасности.

Авторы работы отмечают, что написали весь код вручную и не задействовали графические ускорители, а применение современных видеокарт или алгоритмов может еще больше упростить задачу. Тем не менее, для большинства популярных сценариев применения RSA угроза пока остается минимальной, так как стандартные протоколы вроде PKCS#1 v1.5 или RSA-PSS не предоставляют уязвимый доступ к «сырым» операциям.

Исключением являются некоторые специфические протоколы, включая Privacy Pass, который используют Apple и Cloudflare. Для атаки на него потребовалось бы обработать огромный массив токенов, сопоставимый с суточным трафиком крупных сервисов, к тому же ключи там регулярно меняются. Тем не менее, это исследование впервые на практике доказывает саму возможность обхода классической парадигмы безопасности RSA.