Новость об атаке на RSA звучит так, будто факторизация модуля перестала быть нужна, а подписи подделываются «просто так». Механика здесь другая: атака не трогает сам примитив RSA и не восстанавливает приватный ключ. Она эксплуатирует доступ к сервису, который выполняет «сырые» операции RSA с приватным ключом над произвольными данными без паддинга. Разберём, какие числа заявлены, что именно требуется от атакующего и почему распространённые схемы подписи при этом остаются вне удара.
Какие цифры заявлены
Для ключей RSA длиной 2048 и 4096 бит криптостойкость снижается примерно до 90 и 119 бит соответственно. Эти значения сравниваются с минимальным уровнем в 128 бит, которого требуют NSA, NIST и ENISA, — то есть оказываются заметно ниже порога.
Для 1024-битного RSA атака требует примерно 2^65 операций, тогда как факторизация такого же ключа оценивается примерно в 2^80 операций. Атака была реализована в академическом CPU-кластере за несколько месяцев, а совокупный объём вычислений эквивалентен примерно 1380 годам непрерывной работы одного процессорного ядра.
Что именно подделывается
Атакующему не нужно факторизовать RSA-модуль и восстанавливать приватный ключ. Вместо этого ему требуется временный доступ к оракулусервису или интерфейсу, который выполняет операции RSA с приватным ключом над переданными ему данными без паддинга и возвращает результат такой операции. Сделав большое количество запросов к такому оракулу и проведя предварительные вычисления, атакующий получает возможность впоследствии подделывать произвольные RSA-подписи офлайн — то есть подделка возможна для произвольного сообщения, а не только для выбранного.
Речь идёт именно о снижении сложности, а не о полном обнулении стойкости: 2^65 против 2^80 для 1024-битного ключа, 90 и 119 бит для 2048 и 4096 бит.
Модель угроз и границы применимости
Ключевое предположение — временный доступ к оракулу, выполняющему «сырой» RSA без паддинга. Такой доступ могут предоставлять, например, некоторые реализации слепой RSA-подписисхемы, в которой подписывающий применяет приватный ключ к замаскированным данным, не видя их содержимого или интерфейсы аппаратных криптографических модулей (HSM)устройств, хранящих ключи и выполняющих криптооперации изолированно от основной системы. Атакующий делает большое количество запросов к оракулу и проводит предварительные вычисления, после чего подделывает произвольные подписи офлайн.
Схемы RSA-подписи с PKCS#1 v1.5 или RSA-PSS такого оракула не предоставляют, поэтому сами исследователи считают атаку против них непрактичной. Исключение — Privacy Pass: для атаки на него потребуется запросить около 2^43 токенов, но большинство реализаций регулярно меняют ключи, что заметно сокращает окно атаки (хотя не исключает её полностью).
В RFC 8017 определены две схемы подписи с приложением: RSASSA-PSSсхема подписи RSA с рандомизированным кодированием, требуемая в новых приложениях и RSASSA-PKCS1-v1_5схема подписи RSA с детерминированным кодированием, включённая только для совместимости с существующими приложениями.
Математическая механика
Задача поиска подписи формулируется через два примитива. RSASP1примитив, который по закрытому ключу и числу, представляющему сообщение, вычисляет число, представляющее подпись по закрытому ключу K и представителю сообщения m (целому от 0 до n-1) выдаёт представитель подписи s (целое от 0 до n-1). RSAVP1примитив, который по открытому ключу и числу, представляющему подпись, восстанавливает число, представляющее сообщение по открытому ключу (n, e) и представителю подписи s восстанавливает представитель сообщения m. Представитель сообщения — это целое число от 0 до n-1, в которое отображается сообщение перед операцией с ключом; представитель подписи — такое же целое, в которое отображается подпись. Эти примитивы нужны, чтобы свести подпись и её проверку к арифметике по модулю n.
При первой форме ключа (n, d) подпись вычисляется как:
s = m^d mod nПри второй форме ключа (p, q, dP, dQ, qInv) вычисляются s_1 = m^dP mod p и s_2 = m^dQ mod q, затем h = (s_1 - s_2) qInv mod p и s = s_2 + q h. Здесь p и q — простые множители модуля n, dP и dQ — заранее вычисленные показатели для операций по модулям p и q соответственно, а qInv — величина, обратная к q по модулю p; вместе они позволяют считать подпись быстрее, чем по одной формуле с d. Проверка в RSAVP1 состоит в вычислении m = s^e mod n.
Подделка подписи без знания закрытого ключа предполагается вычислительно неосуществимой при условии, что вычисление e-х корней по модулю n невыполнимо. Противник, ищущий сообщение с той же подписью, что и ранее подписанное, должен найти коллизии конкретной используемой хэш-функции. Атака обходит именно это допущение: она не ищет e-й корень, а опирается на доступ к оракулу, который эти корни считает за атакующего.
Роль кодирования EMSA-PSS и EMSA-PKCS1-v1_5
EMSA-PSSметод кодирования, отображающий сообщение в закодированное сообщение с добавлением случайной соли и EMSA-PKCS1-v1_5детерминированный метод кодирования, отображающий сообщение в закодированное сообщение фиксированной структуры — это методы кодирования, которые отображают сообщение M в закодированное сообщение EM; они обеспечивают связь между схемами подписи и примитивами RSA.
В верификаторе RSASSA-PSS после восстановления m и EM запускается проверка кодирования EMSA-PSS: она сверяет закодированное сообщение с самим сообщением M и с длиной модуля за вычетом одного бита (modBits-1) — столько битов занимает EM, потому что один бит модуля уходит на знак при преобразовании в целое. Подпись принимается только при результате 'consistent'. Проверка сверяет длину M, вычисляет mHash = Hash(M), проверяет emLen ≥ hLen+sLen+2, наличие 0xbc в последнем октете, нулевые старшие биты maskedDB, восстанавливает DB = maskedDB xor MGF(H, emLen-hLen-1) и обнуляет старшие биты DB.
В верификаторе RSASSA-PKCS1-v1_5 после восстановления EM = I2OSP(m,k) вычисляется EM' = EMSA-PKCS1-V1_5-ENCODE(M,k) и сравниваются EM и EM'.
Эти проверки ослабляют связь между m и подписью, поскольку верификатор не требует, чтобы m было детерминированной функцией от M: для PSS кодирование рандомизировано, и разные применения кодирования к одному сообщению дают разные EM, а для PKCS1-v1_5 верификатор лишь перекодирует M и сравнивает результат с EM.
Детерминированное против рандомизированного кодирования
При детерминированном кодировании (например, EMSA-PKCS1-v1_5) проверка подписи может просто применить операцию кодирования сообщения и сравнить полученное закодированное сообщение с ранее извлечённым: при совпадении подпись считается действительной.
При рандомизированном кодировании (например, EMSA-PSS) проверка обычно сложнее: она извлекает случайную соль и хэш-выход из закодированного сообщения и проверяет согласованность хэш-выхода, соли и сообщения, причём хэш-выход является детерминированной функцией от сообщения и соли.
EMSA-PSS параметризуется выбором хэш-функции, функции генерации маски и длины соли; эти параметры должны быть фиксированы для данного ключа RSA, за исключением того, что длина соли может быть переменной. Типичные длины соли в октетах — hLen (длина выхода хэш-функции) и 0; в обоих случаях безопасность RSASSA-PSS может быть тесно связана со сложностью инвертирования RSAVP1. Использование рандомизации в схемах подписи, например значения соли в EMSA-PSS, может создавать «скрытый канал» для передачи информации помимо подписываемого сообщения.
Пограничные случаи
Поведение атаки описано только для низкого показателя e = 3. Атака работает на низкоэкспонентном RSA, когда шифруются похожие сообщения одним и тем же открытым ключом, а именно когда два входа в RSAEPпримитив шифрования RSA, который по открытому ключу и представителю сообщения вычисляет представитель шифртекста совпадают по большой доле битов (8/9). Против этого рекомендуется генерировать псевдослучайные октеты независимо для каждого шифрования, поскольку это помогает thwart an attack due to Coppersmith et al.
Для больших e и для многопростых ключей (u > 2) описание поведения атаки отсутствует.
Что видит верификатор
Подделанная подпись отличается тем, что не проходит проверки соответствующей схемы и в итоге даёт «invalid signature».
Для RSASSA-PSS сначала проверяется длина: если длина подписи S не равна k октетам, верификатор сразу выдаёт «invalid signature» и останавливается. Затем S преобразуется в целое и через RSAVP1 получается представитель сообщения; если RSAVP1 сообщает «signature representative out of range», результат — «invalid signature». Далее m кодируется в EM длины emLen = ceil((modBits - 1)/8), и при ошибке I2OSP «integer too large» также выдаётся «invalid signature». После этого выполняется EMSA-PSS-VERIFYпроцедура проверки подписи RSASSA-PSS, которая по сообщению и закодированному сообщению EM подтверждает или отвергает подпись, где проверяются длина, крайний правый октет EM (должен быть 0xbc), нулевые старшие биты maskedDB и восстановление DB; при несоответствии результат «inconsistent», иначе «valid signature».
Для RSASSA-PKCS1-v1_5 подпись должна иметь ровно k октетов, затем EM сравнивается с заново вычисленным EM' = EMSA-PKCS1-V1_5-ENCODE(M, k): если они совпадают — «valid signature», иначе — «invalid signature».
Артефакты, которые могут выдать подделку: неверная длина S (не k), выход за диапазон при RSAVP1, слишком большой m при I2OSP, отсутствие 0xbc в последнем октете EM, ненулевые старшие биты maskedDB, а также несовпадение EM и EM'.
Сведений о наблюдаемых признаках в логах или на стороне подписывающего, по которым можно было бы распознать такую атаку, нет. Описано лишь, что атакующему нужен временный доступ к оракулу и что, сделав большое количество запросов к нему, атакующий затем может подделывать подписи офлайн.
Почему конструкции выбраны именно так
EMSA-PSS выбран как рандомизированная схема кодирования, параметризуемая хеш-функцией, MGF и длиной соли, причём эти параметры должны фиксироваться для ключа, кроме длины соли. Его стойкость доказуема: при условии вычислительной неосуществимости извлечения корня e-й степени по модулю n и надлежащих свойств хеш- и mask-функций RSASSA-PSS обеспечивает безопасные подписи, причём границы доказательства практически точные — вероятность успеха и время работы лучшего фальсификатора очень близки к соответствующим параметрам лучшего алгоритма инверсии RSA.
В отличие от RSASSA-PKCS1-v1_5, в EMSA-PSS идентификатор хеш-функции не встраивается в закодированное сообщение, что теоретически позволяет подменить хеш-функцию. Для детерминированной EMSA-PKCS1-v1_5 проверка проще: к сообщению применяют кодирование и сравнивают результат с ранее полученным закодированным сообщением.
Компромисс с совместимостью виден в отличиях от исходной схемы Bellare–Rogaway: девять фиксированных битов и trailer-октет 0xbc введены для совместимости с IFSP-RWпримитивом подписи на основе факторизации с использованием схемы Рабина–Вильямса в IEEE 1363 и соответствующим примитивом в ISO/IEC 9796-2:2010.
При этом уязвимость связана не с самими EMSA-PSS или EMSA-PKCS1-v1_5, а с доступом к оракулу «сырого» RSA без паддинга: распространённые схемы RSA-подписи с PKCS#1 v1.5 или RSA-PSS такого оракула не предоставляют, поэтому сами исследователи считают атаку против них непрактичной.
Какие меры снижают эффект
RFC 8017 снижает эффект атак, рекомендуя для новых приложений только SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256, поскольку для них лучшие известные коллизионные атаки имеют сложность 2^(L/2), а коллизия напрямую превращается в подделку подписи. Поэтому длина вывода хеша L/2 должна быть не меньше желаемого уровня стойкости подписи, а для RSAES-OAEPсхемы шифрования RSA с оптимальным асимметричным шифрованием и дополнением длина seed рекомендуется вдвое больше желаемого уровня стойкости.
MD2 и MD5 объявлены криптографически сломанными и подлежащими удалению из существующих приложений, поддерживаются только для обратной совместимости. SHA-1 рекомендуется только для совместимости, так как его стойкость существенно снижена, но недостаточно для удаления. Для EMSA-PKCS1-v1_5 рекомендуются SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256 для новых приложений, а MD2, MD5 и SHA-1 — только для совместимости.
В EMSA-PSS длина salt может быть переменной, типичные значения — hLen и 0; при этих значениях стойкость RSASSA-PSS тесно связана со сложностью инверсии RSAVP1, и доказательства дают нижние границы для salt длиной от 0 до hLen. Использование рандомизации (salt) в схемах подписи может создавать скрытый канал для передачи посторонней информации.
Какие версии затронуты
RFC 3447 — это PKCS #1 версии 2.1, а RFC 8017 — PKCS #1 версии 2.2. Версия 2.1 ввела multi-prime RSAвариант RSA, в котором модуль строится из более чем двух простых множителей, а не из привычной пары простых чисел и схему подписи RSASSA-PSS с приложением, продолжая поддерживать схемы версии 2.0. Версия 2.0, в свою очередь, ввела схему шифрования RSAES-OAEP и продолжала поддерживать схемы шифрования и подписи версии 1.5, но хеш-алгоритм MD4 больше не допускался.
В существующих развёртываниях нужно учитывать, что распространённые схемы RSA-подписи с PKCS#1 v1.5 или RSA-PSS не предоставляют оракула «сырого» RSA без паддинга, поэтому новая атака против них считается непрактичной. Исключением является Privacy Pass, для атаки на который потребуется около 2^43 токенов, но большинство его реализаций регулярно меняют ключи, что сокращает окно атаки.
Что из этого следует на практике
Атака не ломает RSA как примитив и не делает факторизацию ненужной в общем случае. Она эксплуатирует конкретную конфигурацию: наличие сервиса или интерфейса, который применяет приватный ключ к произвольным данным без паддинга. Если такого оракула в развёртывании нет, атака неприменима.
Схемы RSASSA-PSS и RSASSA-PKCS1-v1_5 из RFC 8017 сами по себе такого оракула не предоставляют — именно поэтому исследователи считают атаку против них непрактичной. Опасность сосредоточена в реализациях слепой RSA-подписи и в интерфейсах HSM, допускающих «сырые» операции с приватным ключом.
Заявленные 90 и 119 бит для ключей 2048 и 4096 бит — это снижение относительно требуемых 128 бит, но оно относится к сценарию с доступом к оракулу. Для 1024-битного RSA атака требует примерно 2^65 операций против примерно 2^80 для факторизации.
Единственный названный конкретный протокол под угрозой — Privacy Pass, где атака требует около 2^43 токенов, а регулярная смена ключей в большинстве реализаций заметно сокращает окно атаки, хотя и не исключает её полностью.
