Исследователи из Калифорнийского университета в Сан-Диего и французского INRIA подделали подписи RSA для 1024-битного ключа, хранившегося в аппаратном модуле безопасности (HSM), — устройстве с защитой от несанкционированного доступа, которое институциональные кастодианы используют для хранения криптографических ключей, — не извлекая при этом сам ключ.

Команда описала эту технику в статье, поданной в криптологический архив IACR (Международной ассоциации криптологических исследований) ePrint 20 сентября. Для проведения атаки потребовалось около 2^32 запросов на подпись — примерно 4 млрд — и около 1380 процессорных лет вычислений. Авторы отмечают, что метод, вероятно, не представляет непосредственной угрозы для большинства современных развёртываний RSA, в которых применяется набивка (padding).

Этот результат не является взломом Bitcoin или Ethereum. Bitcoin подписывает транзакции с использованием алгоритма цифровой подписи на эллиптических кривых (ECDSA), а его кривая также поддерживает подписи Schnorr. Ethereum и большинство других крупных блокчейнов используют тот же подход на эллиптических кривых. Исследование направлено на RSA — криптографию Ривеста–Шамира–Адлемана — совершенно иную схему подписи.

Исследователи продемонстрировали технику на аппаратном модуле безопасности — устройстве с защитой от несанкционированного доступа, которое хранит приватные ключи и подписывает данные по запросу. Чтобы сделать атаку возможной, они отключили режим FIPS модуля — конфигурацию, валидированную в соответствии с американскими государственными стандартами обработки информации (Federal Information Processing Standards) для криптографических модулей, — чтобы тот подписывал «сырые», неформатированные числа, и предоставилиный тестовый ключ. Затем они попросили устройство подписать около 4 млрд выбранных ими чисел и применили математический анализ к ответам, чтобы сконструировать поддельные подписи. Криптографы называют такой доступный для запросов объект оракулом — системой, которая отвечает на выбранные злоумышленником входные данные, а её ответы могут скрывать эксплуатируемые закономерности. Иными словами, результат не демонстрирует взлома сертифицированной конфигурации — она сначала должна была быть отключена.

Сценарий напоминает хранилище, которое никогда не открывается, но ставит печать на любой чистый лист, подсунутый под дверь: попросив достаточно много печатей, можно научиться воспроизводить штамп самостоятельно.

Этот результат — стресс-тест того, как на практике защищаются ключи. По данным BitGo, провайдеры институционального кастодиального хранения используют аппаратные модули безопасности именно для того, чтобы приватные ключи никогда не существовали вне устройства. В этой демонстрации ключ не покидал модуль — и тем не менее подписи были подделаны.

Что делает цифровая подпись

Каждый раз, когда пользователь подтверждает транзакцию, кошелёк подписывает её приватным ключом владельца. Эта цифровая подпись доказывает, что владелец ключа одобрил транзакцию и что никто не изменил сообщение по пути.

RSA, разработанная в 1977 году Роном Ривестом, Леонардом Адлеманом и Ади Шамиром — «S» в этой аббревиатуре, — один из способов построения такого доказательства. Её ключевая идея в том, что перемножить два огромных простых числа легко, а вот разложить произведение обратно — задача, известная как факторизация, — чрезвычайно трудно. Авторы пишут, что безопасность RSA обычно считается основанной на этой трудности, хотя взлом RSA так и не был доказан как эквивалентный факторизации. Примечательно, что эта команда ничего не факторизировала.

Кого это затрагивает

Стандартное подписание RSA применяет набивку (padding) — этап перемешивания и форматирования, например PKCS#1 v1.5 или PSS, выполняемый перед математическими операциями, — а подписи с набивкой не создают эксплуатируемого оракула. Длина ключа добавляет ещё один слой дистанции: в демонстрации использовался 1024-битный ключ, тогда как действующие американские стандарты (NIST) считают 2048 бит минимумом для новых ключей RSA. По словам авторов, атака, вероятно, не представляет непосредственной операционной угрозы для большинства современных развёртываний RSA. Статья остаётся препринтом, и её выводы предстоит пройти формальное рецензирование.

Некоторые системы намеренно предоставляют такой оракул. Слепые подписи на основе RSA — техника, описанная в стандарте Internet Engineering Task Force, — позволяют серверу подписать сообщение, никогда его не видя; именно так работает один из вариантов Privacy Pass. По данным Cloudflare, Apple использует версию Privacy Pass, чтобы пользователи могли доказать прохождение проверки, например CAPTCHA, не раскрывая своей личности. Слепые подписи имеют глубокие корни в истории криптографии: Дэвид Чаум применил эту технику, основав DigiCash в 1989 году.

Главная угроза по-прежнему квантовая

Заголовки в духе «RSA взломана» уже имеют свою историю. В январе 2023 года китайские исследователи заявили о квантовом методе, угрожающем RSA, но факторизировали лишь 48-битное число, и эксперты отвергли это заявление. В этот раз демонстрация затрагивает настоящий 1024-битный ключ — хотя со звёздочкой размером с оракул.

Авторы описывают свой результат как классическое свидетельство в пользу отказа от RSA в ходе постквантового перехода — перехода к шифрованию, рассчитанному на устойчивость к квантовым компьютерам. У этого перехода уже есть конкретные вехи: американский орган по стандартизации NIST утвердил первые стандарты постквантовой криптографии в августе 2024 года, дав вендорам и операторам общую цель для миграции.

Для Bitcoin квантовый вопрос касается подписей на эллиптических кривых. Исследователи Caltech в конце марта оценили, что 10 000–20 000 кубитов — квантового аналога бит — может быть достаточно для запуска алгоритма Шора, метода, угрожающего этим подписям. Google, со своей стороны, установила 2029 год как крайний срок завершения миграции собственных систем на постквантовую криптографию.

Этот материал первоначально опубликован Decrypt: RSA attack without stealing key: what it means for crypto.