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