ML-KEM (FIPS 203): стандартизация CRYSTALS-Kyber

ML-KEM (механизм инкапсуляции ключей на основе модульных решёток), стандартизированный в августе 2024 года как FIPS 203, является постквантовой заменой обмену ключами Diffie-Hellman и RSA. Он инкапсулирует симметричный ключ с использованием открытого ключа, создавая общий секрет, который обе стороны могут использовать для симметричного шифрования. ML-KEM основан на CRYSTALS-Kyber и содержит небольшие изменения, упрощающие спецификацию.

ML-KEM определяет три набора параметров. ML-KEM-512 обеспечивает примерно 128-битовую классическую и 100-битовую постквантовую стойкость, используя открытый ключ размером 800 байт и шифротекст размером 768 байт. ML-KEM-768 обеспечивает 192-битовую классическую стойкость (открытый ключ — 1184 байта, шифротекст — 1088 байт). ML-KEM-1024 обеспечивает 256-битовую классическую стойкость (открытый ключ — 1568 байт, шифротекст — 1568 байт). NIST рекомендует ML-KEM-768 для большинства приложений.

Генерация ключей ML-KEM выполняется следующим образом: случайная матрица A выбирается на основе начального значения с помощью SHAKE-128, затем выбираются небольшой секретный вектор s и вектор ошибок e, после чего вычисляется t = As + e mod q. Открытый ключ — это (начальное значение, t), а закрытый ключ — это s вместе с хешем открытого ключа. Использование начального значения вместо хранения A значительно экономит память и пропускную способность.

Для инкапсуляции отправитель создаёт случайное сообщение m и с помощью SHA-3 получает симметричный ключ K и случайность r. Шифротекст состоит из двух частей: u = Ar + e1 mod q и v = t^T r + e2 + encode(m) mod q. Общий секрет K получается из хеша m. Случайность детерминированно выводится из m, связывая шифротекст с ключом.

При декапсуляции m восстанавливается вычислением v - s^T u с последующим декодированием, после чего K заново выводится из m. Преобразование Фудзисаки—Окамото добавляет важный шаг: повторно зашифровать восстановленное m и проверить совпадение шифротекста. Если совпадения нет, возвращается псевдослучайное значение, полученное из хеша закрытого ключа и шифротекста. Это предотвращает атаки с выбранным шифротекстом, делая декапсуляцию детерминированной и проверяемой.

ML-KEM обеспечивает стойкость IND-CCA2 в квантовой модели случайного оракула (QROM), доказанную при предположении Module-LWE. QROM важна потому, что постквантовые противники могут запрашивать хеш-функции в суперпозиции. Доказательство стойкости, предложенное Хофхайнцем, Ховельманнсом и Кильтцем (подход HHK), даёт точные редукции от Module-LWE к стойкости ML-KEM в QROM.

ML-KEM значительно превосходит RSA при обмене ключами на сопоставимых уровнях стойкости. На современном CPU генерация ключей ML-KEM-768 занимает около 16 микросекунд, инкапсуляция — 20 микросекунд, а декапсуляция — 18 микросекунд. Генерация ключей RSA-2048 занимает секунды. Открытые ключи ML-KEM (1184 байта) больше ключей ECDH (32–64 байта), но гораздо меньше ключей RSA-2048 (256 байт только для ключа, хотя на практике данные длиннее).

В переходный период гибридный обмен ключами сочетает ML-KEM с классическим алгоритмом (обычно X25519 или P-256 ECDH). Общий секрет является хешем обоих выходов KEM: K = Hash(K_classical || K_pqc). Это гарантирует, что стойкость не будет ниже стойкости любого из компонентов. Гибридный TLS описан в документе IETF draft-ietf-tls-hybrid-design и поддерживается в BoringSSL, OpenSSL 3.x и Rustls.

IETF определил X25519ML-KEM-768 как гибридный вариант обмена ключами для TLS 1.3 (draft-ietf-tls-hybrid-design). Chrome добавил поддержку в версии 124 (апрель 2024 года), а Firefox — в версии 132 (2024 год). Cloudflare внедрил ML-KEM в свою инфраструктуру завершения TLS-сеансов. Благодаря такому быстрому распространению теперь сотни миллионов TLS-соединений в день включают постквантовый обмен ключами.

Из-за слагаемых ошибок в LWE существует небольшая вероятность сбоя декапсуляции даже при отсутствии противника. Для ML-KEM-512 вероятность сбоя составляет примерно 2^{-139}, а для ML-KEM-768 — 2^{-164}. Эти значения намного ниже любого практически значимого уровня (для сравнения, аппаратные ошибки происходят гораздо чаще) и не влияют на безопасность, но их необходимо учитывать в спецификации.

ML-KEM реализован во множестве библиотек с открытым исходным кодом. Эталонная реализация команды Kyber находится в общественном достоянии. PQClean предоставляет очищенную переносимую реализацию на C. liboqs (проект Open Quantum Safe) интегрирует ML-KEM в оболочку библиотеки. AWS-LC (форк BoringSSL от Amazon) включает ML-KEM для конечных точек TLS в AWS. Стандарт NIST FIPS 203 содержит подробный псевдокод для всех операций.

Какой набор параметров ML-KEM NIST рекомендует для большинства приложений?

ML-KEM (FIPS 203) — это постквантовый KEM, стандартизированный NIST и основанный на Module-LWE. Три набора параметров (512/768/1024) обеспечивают классическую стойкость уровня 128/192/256 бит. Генерация ключей создаёт компактный открытый ключ из случайного начального значения; инкапсуляция получает общий секрет; декапсуляция использует преобразование FO для обеспечения стойкости CCA2. ML-KEM значительно быстрее RSA и уже применяется в TLS-инфраструктуре Chrome, Firefox и Cloudflare.