ML-KEM (FIPS 203): standaryzacja CRYSTALS-Kyber

ML-KEM (mechanizm enkapsulacji klucza oparty na kratach modułowych), standaryzowany w sierpniu 2024 roku jako FIPS 203, jest postkwantowym zamiennikiem wymiany kluczy Diffie-Hellman i RSA. Enkapsuluje klucz symetryczny za pomocą klucza publicznego, tworząc wspólny sekret, którego obie strony mogą używać do szyfrowania symetrycznego. ML-KEM wywodzi się z CRYSTALS-Kyber i zawiera niewielkie modyfikacje zapewniające bardziej przejrzystą specyfikację.

ML-KEM definiuje trzy zestawy parametrów. ML-KEM-512 zapewnia około 128-bitowy poziom bezpieczeństwa klasycznego i 100-bitowy poziom bezpieczeństwa postkwantowego, przy kluczu publicznym o rozmiarze 800 bajtów i szyfrogramie o rozmiarze 768 bajtów. ML-KEM-768 zapewnia 192-bitowy poziom bezpieczeństwa klasycznego (klucz publiczny ma 1184 bajty, a szyfrogram 1088 bajtów). ML-KEM-1024 zapewnia 256-bitowy poziom bezpieczeństwa klasycznego (klucz publiczny i szyfrogram mają po 1568 bajtów). NIST zaleca ML-KEM-768 w większości zastosowań.

Generowanie klucza ML-KEM przebiega następująco: z ziarna za pomocą SHAKE-128 losuje się losową macierz A, mały wektor tajny s i wektor błędu e, a następnie oblicza się t = As + e mod q. Klucz publiczny stanowi para (seed, t), a klucz prywatny — s wraz z wartością skrótu klucza publicznego. Użycie ziarna zamiast przechowywania macierzy A znacznie zmniejsza wymagania dotyczące pamięci i przepustowości.

Aby przeprowadzić enkapsulację, nadawca generuje losową wiadomość m i za pomocą SHA-3 wyprowadza zarówno symetryczny klucz K, jak i losowość r. Szyfrogram składa się z dwóch części: u = Ar + e1 mod q oraz v = t^T r + e2 + encode(m) mod q. Wspólny sekret K wyprowadza się ze skrótu m. Losowość jest deterministycznie wyprowadzana z m, co wiąże szyfrogram z kluczem.

Dekapsulacja odzyskuje m, obliczając v - s^T u i dekodując wynik, a następnie ponownie wyprowadza K z m. Transformacja Fujisakiego-Okamoty dodaje kluczowy krok: ponowne zaszyfrowanie odzyskanego m i sprawdzenie, czy szyfrogram jest zgodny. Jeśli nie jest, zwracana jest pseudolosowa wartość wyprowadzona ze skrótu klucza prywatnego i szyfrogramu. Zapobiega to atakom z wybranym szyfrogramem, ponieważ dekapsulacja staje się deterministyczna i możliwa do zweryfikowania.

ML-KEM zapewnia bezpieczeństwo IND-CCA2 w kwantowym modelu losowej wyroczni (QROM), udowodnione przy założeniu Module-LWE. QROM ma znaczenie, ponieważ przeciwnicy postkwantowi mogą odpytywać funkcje skrótu w superpozycji. Dowód bezpieczeństwa autorstwa Hofheinza, Hovelmannsa i Kiltza (schemat HHK) zapewnia ścisłe redukcje od Module-LWE do bezpieczeństwa ML-KEM w QROM.

ML-KEM znacznie przewyższa RSA pod względem wydajności wymiany kluczy przy równoważnych poziomach bezpieczeństwa. Generowanie klucza ML-KEM-768 na nowoczesnym procesorze trwa około 16 mikrosekund, enkapsulacja 20 mikrosekund, a dekapsulacja 18 mikrosekund. Generowanie klucza RSA-2048 trwa sekundy. Klucze publiczne ML-KEM (1184 bajty) są większe niż klucze ECDH (32–64 bajty), ale znacznie mniejsze niż klucze RSA-2048 (256 bajtów za sam klucz, choć w praktyce całość jest dłuższa).

W okresie przejściowym hybrydowa wymiana kluczy łączy ML-KEM z algorytmem klasycznym (zwykle X25519 lub P-256 ECDH). Wspólny sekret jest skrótem obu wyników KEM: K = Hash(K_classical || K_pqc). Dzięki temu bezpieczeństwo nie może być niższe niż bezpieczeństwo któregokolwiek ze składników. Hybrydowy TLS opisano w dokumencie IETF draft-ietf-tls-hybrid-design, a obsługę zapewniają BoringSSL, OpenSSL 3.x i Rustls.

IETF zdefiniowała X25519ML-KEM-768 jako hybrydowy element wymiany klucza dla TLS 1.3 (draft-ietf-tls-hybrid-design). Chrome dodał obsługę w wersji 124 (kwiecień 2024 roku), a Firefox w wersji 132 (2024 rok). Cloudflare wdrożył ML-KEM w swojej infrastrukturze terminacji TLS. Dzięki szybkiemu przyjęciu tego rozwiązania setki milionów połączeń TLS dziennie obejmują obecnie postkwantową wymianę kluczy.

Ze względu na składniki błędu w LWE istnieje niewielkie prawdopodobieństwo, że dekapsulacja nie powiedzie się nawet bez udziału przeciwnika. Dla ML-KEM-512 prawdopodobieństwo niepowodzenia wynosi około 2^{-139}, a dla ML-KEM-768 — 2^{-164}. Wartości te są znacznie niższe od poziomu mającego jakiekolwiek praktyczne znaczenie (dla porównania, błędy sprzętowe występują znacznie częściej) i nie wpływają na bezpieczeństwo, ale należy je uwzględnić w specyfikacji.

ML-KEM zaimplementowano w licznych bibliotekach open source. Implementacja referencyjna zespołu Kyber jest dostępna w domenie publicznej. PQClean udostępnia oczyszczoną, przenośną implementację w języku C. liboqs (projekt Open Quantum Safe) integruje ML-KEM w ramach opakowania bibliotecznego. AWS-LC (odgałęzienie BoringSSL rozwijane przez Amazon) zawiera ML-KEM na potrzeby punktów końcowych TLS AWS. Standard NIST FIPS 203 zawiera szczegółowy pseudokod wszystkich operacji.

Który zestaw parametrów ML-KEM NIST zaleca w większości zastosowań?

ML-KEM (FIPS 203) to standaryzowany przez NIST postkwantowy KEM oparty na Module-LWE. Trzy zestawy parametrów (512/768/1024) zapewniają odpowiednio 128-, 192- i 256-bitowe bezpieczeństwo klasyczne. Generowanie klucza tworzy zwarty klucz publiczny na podstawie losowego ziarna, enkapsulacja wyprowadza wspólny sekret, a dekapsulacja wykorzystuje transformację FO w celu zapewnienia bezpieczeństwa CCA2. ML-KEM jest znacznie szybszy od RSA i został już wdrożony w Chrome, Firefoxie oraz infrastrukturze TLS Cloudflare.