Исследователи обнаружили новый способ подделки подписей в некоторых реализациях RSA. Для ключей длиной 1024, 2048 и 4096 бит требуемый объём вычислений оценивается соответственно в 265, 290 и 2119 операций. Работа выполнялась вручную, без применения искусственного интеллекта и графических процессоров, поэтому, по словам исследовательницы, дальнейшее использование таких инструментов «почти наверняка» снизит эти показатели.
Метод применим только к RSA со слепыми подписями (blind signature — способ подписания данных без раскрытия их содержимого). Большинство современных систем RSA используют дополнение PKCS или PSS, которое добавляет данные к исходному тексту перед шифрованием, делает шифротекст недетерминированным и защищает его от атак по побочным каналам. Однако некоторые действующие системы по-прежнему работают с так называемым textbook RSA — RSA без такого дополнения.
Одним из наиболее известных примеров остаётся протокол Privacy Pass, позволяющий пользователю подтвердить свою подлинность без раскрытия личности. Его применяют Apple, Cloudflare и другие организации. Как сообщает Ars Technica, для атаки на Privacy Pass злоумышленнику пришлось бы получить доступ к серверу Cloudflare, Apple или другой компании и создать 243 подписи.
Исследовательница Хенингер отметила, что это число «звучит [как] много, но находится примерно в том же порядке величины, что и сетевой трафик, который, по публичным заявлениям Cloudflare, проходит через компанию примерно за день». Регулярная смена ключей в большинстве реализаций Privacy Pass существенно уменьшает вероятность успешной атаки, хотя полностью её не исключает.
В основе техники лежит разновидность алгоритма решета числового поля, созданного в 2007 году. Она используется против «оракула» — уязвимости, которая выдаёт ответы «да» или «нет» на специальные запросы и позволяет постепенно собрать сведения для расшифровки. Для факторизации 1024-битного ключа требуется около 280 операций и от 500 тысяч до 1 млн процессорных лет, тогда как подделка подписи с помощью нового подхода потребовала 265 операций и 1380 процессорных лет.
Авторы исследования и другие криптографы считают, что непосредственная угроза для реальных систем невелика. При этом метод резко снижает прежнюю оценку защищённости textbook RSA и выявляет ранее неизвестный путь атаки. Разработчики криптографических систем уже несколько лет ищут замену алгоритмам, уязвимым для квантовых вычислений, а новая работа усиливает необходимость полного отказа от textbook RSA.