Миру уже десятилетиями известно, что дни криптосистемы RSA сочтены. Как только квантовые вычисления станут практичными (оценки варьируются от 3 до 20 и более лет), фундаментальная безопасность, которую она обеспечивает, прекратит существовать. Новое исследование выявило новый метод, который с помощью классических вычислений снижает текущий уровень безопасности RSA до неприемлемо низкого порога.
Практический риск ограничен, но всё же значителен. Применение атаки против устаревшего использования 1024‑битных ключей заняло несколько месяцев на академическом вычислительном кластере — существенно меньше, чем текущие оценки взлома 1024‑битного факторинга, требующие ресурсов, которыми обладают лишь государства или компании с огромными возможностями. Широко используемые реализации RSA также остаются безопасными.
Тем не менее исследование удивило криптографов, потому что вводит подделку подписи — новый способ сломать RSA без факторизации. Не менее важно, что этот новый метод снижает требуемые вычислительные ресурсы на порядки.
«Если этот результат выдержит рецензию, это будет действительно концептуальный прорыв», — сказал Карстен Ноль, эксперт по криптографии и руководитель отдела инноваций в Allurity, в интервью. «RSA считали столь же трудным для взлома, как и факторизацию больших целых чисел, по крайней мере так нам думалось. Исследователь утверждает, что на практике можно сломать RSA, не раскалывая его ключ».
Надя Хенингер, профессор Калифорнийского университета в Сан‑Диего и соавтор, пояснила:
Криптографы думали, что единственный способ получить действительные цифровые подписи RSA — сначала вычислить закрытый ключ через факторизацию, а затем использовать закрытый ключ для вычисления подписей. Для 1024‑битного RSA это считалось очень дорогостоящим, хотя, возможно, осуществимым при наличии вычислительных ресурсов крупных технологических компаний или АНБ — в пределах десятков миллионов долларов вычислительного времени для одного ключа. Для 2048‑битного RSA это считалось совершенно недостижимым.
Атака подделки ключа, разработанная Хенингер и другими исследователями, сейчас полностью практична для 1024‑битного RSA. Даже для 2048‑ и 4096‑битных ключей метод снижает безопасность RSA до неприемлемых уровней. Агентство национальной безопасности США (NSA), Национальный институт стандартов и технологий (NIST) и Агентство Европейского союза по сетевой и информационной безопасности требуют, чтобы любая криптосистема обеспечивала уровень не менее 128 бит, то есть операции, необходимые для взлома, должны превышать 2^128.
Атака подделки снижает эти уровни до 2^65, 2^90 и 2^119 для ключей 1024, 2048 и 4096 бит соответственно. Эти уровни могут ещё снизиться, потому что команда Хенингер писала весь код вручную и не использовала ИИ или графические процессоры при выполнении подделок. Исследователь утверждает, что эти инструменты «почти наверняка» ещё уменьшат уровни безопасности.
Атака работает только против реализаций RSA с «слепой» подписью. Подавляющее большинство используемого сегодня RSA применяет паддинг PKCS или PSS — формат, который добавляет данные к открытому тексту перед шифрованием. Это предотвращает детерминированность шифротекста и делает систему менее уязвимой к утечкам через побочные каналы и подобным атакам. Тем не менее некоторые реальные системы продолжают использовать «слепой» или так называемый учебник‑вариант RSA. Наиболее известный пример, по словам Хенингер, — протокол Privacy Pass, позволяющий пользователям аутентифицироваться, не раскрывая своей личности. Privacy Pass используется, в частности, Apple и Cloudflare, среди многих других.
Атака на Privacy Pass потребовала бы от злоумышленника запроса 2^43 токенов у Cloudflare, Apple или другой организации.
Хенингер отметила, что это «кажется большим числом, но находится в том же порядке величины, что и сетевой трафик, который Cloudflare публично заявляла, что обрабатывает примерно за день». Большинство реализаций Privacy Pass регулярно меняют ключи — мера, которая значительно снижает, но не автоматически устраняет, шансы успеха атакующего.
Техника реализует вариант алгоритма решета числовых полей, изобретённого в 2007 году. Это «особое» решето числовых полей используется вместе с «оракулом» — свойством некоторых криптографических протоколов, которое даёт ответы на запрошенные входные данные. Выполнив огромное количество операций, атакующие могут собрать достаточно информации, чтобы расшифровать шифротекст. (Эта техника, по-видимому, не представляет практической угрозы для RSA с паддингом PKCS или PSS, поскольку они обеспечивают другой тип оракула.) В то время как факторизация 1024‑битного ключа требует оценочно 2^80 операций и 500 000–1 000 000 ядеро‑лет CPU, использование решета для подделки подписи заняло всего 2^65 операций и 1 380 ядеро‑лет.
Авторы статьи и другие исследователи подчёркивают, что новая атака пока представляет небольшую реальную угрозу, по крайней мере в настоящее время. Тем не менее она резко снижает ожидаемый уровень безопасности RSA и делает это способом, о котором ранее никто не знал.
В последние годы криптографы энергично работали над разработкой альтернативных криптосистем, невосприимчивых к квантовым атакам. Новая атака ещё более ускорит необходимость полного отказа от данной криптосистемы.
Автор(ы) статьи также подготовили более доступное объяснение результатов.
Статья обновлена, чтобы исправить личность ведущего автора. Это Лаура Ши, также из Калифорнийского университета в Сан‑Диего.
UT Austin: более 5 000 GPU (NVIDIA Blackwell, TACC).
Seoul National University: 4 000 GPU (NVIDIA H200).
Harvard University: 1 144 GPU (Kempner Institute).
Indiana University: 616 GPU (NVIDIA A100).
Посчитаем с текущими технологиями. Никакой научной фантастики.
1 380 ядеро‑лет соответствует примерно 12,09 миллионам ядеро‑часов, что переводится примерно в 63 000–94 500 часов реального времени на одном современном высокоплотном CPU‑сокете, или примерно 200–600 часов на одном современном высокопроизводительном GPU.
При оптимизированном CUDA‑пайплайне (дающем консервативное преимущество по пропускной способности в 250×–500× по сравнению со стандартным одним ядром CPU) один высокопроизводительный GPU завершил бы вычисление примерно за 24 000–48 000 часов.
Современный кластер GPU с всего лишь 64–128 стоек (по сути большой выделенный этаж в подвале), содержащий 4 000 GPU, завершил бы это примерно за 6–12 часов.
Такие вычислительные мощности имеются в университетах. Если позволить занять несколько дней, пул доступных ресурсов ещё расширится.