Исследователи нашли способ подделывать цифровые подписи RSA без вычисления закрытого ключа. Метод сокращает объём вычислений для атаки, но затрагивает только системы, использующие слепые подписи. Большинство реализаций RSA, по данным исследователей, устроены иначе.
Атака использует вариант специального метода решета числового поля, предложенный в 2007 году, и «оракул». Так называют свойство некоторых криптографических протоколов отвечать на запросы так, что атакующий может извлечь из ответов полезную информацию. После большого числа запросов и вычислений исследователи смогли подделать подпись, не разлагая число из открытого ключа на множители.
Для ключа RSA длиной 1024 бита такое разложение, по оценке исследователей, требует около 2^80 операций и от 500 тысяч до 1 миллиона процессорных лет. Подделка подписи потребовала 2^65 операций и 1380 процессорных лет. Для ключей длиной 2048 и 4096 бит исследователи оценили сложность атаки в 2^90 и 2^119 операций соответственно. Программу команда написала вручную, не применяя ИИ и графические процессоры. Исследовательница Надя Хенингер считает, что с этими инструментами затраты на атаку «почти наверняка» удастся дополнительно снизить.
Метод работает только против реализаций RSA со слепой подписью, которые также называют textbook RSA. Подавляющее большинство систем использует дополнение данных в форматах PKCS или PSS. Для них исследователи не видят практической угрозы от этой техники, поскольку такие системы предоставляют атакующему другой тип оракула.
Один из примеров применения слепых подписей, по словам Хенингер, — протокол Privacy Pass. Он позволяет пользователю подтвердить право доступа, не раскрывая свою личность; протокол используют в том числе Apple и Cloudflare. Для атаки на Privacy Pass злоумышленнику понадобилось бы запросить у организации 2^43 токенов. В большинстве реализаций протокола ключи регулярно меняют: это сильно снижает вероятность успеха, хотя и не исключает её полностью.
