ML-KEM (FIPS 203): standardizzazione di CRYSTALS-Kyber

ML-KEM (Module-Lattice-based Key Encapsulation Mechanism), standardizzato come FIPS 203 nell'agosto 2024, è il sostituto post-quantistico dello scambio di chiavi Diffie-Hellman e RSA. Incapsula una chiave simmetrica usando una chiave pubblica e produce un segreto condiviso che entrambe le parti possono utilizzare per la cifratura simmetrica. ML-KEM deriva da CRYSTALS-Kyber, con piccole modifiche per ottenere una specifica più chiara.

ML-KEM definisce tre set di parametri. ML-KEM-512 offre circa 128 bit di sicurezza classica e 100 bit di sicurezza post-quantistica, con una chiave pubblica di 800 byte e un testo cifrato di 768 byte. ML-KEM-768 offre 192 bit di sicurezza classica, con una chiave pubblica di 1184 byte e un testo cifrato di 1088 byte. ML-KEM-1024 offre 256 bit di sicurezza classica, con una chiave pubblica di 1568 byte e un testo cifrato di 1568 byte. NIST raccomanda ML-KEM-768 per la maggior parte delle applicazioni.

La generazione delle chiavi di ML-KEM funziona nel modo seguente: si campiona una matrice casuale A da un seed usando SHAKE-128, quindi si campionano il vettore segreto s e il vettore degli errori e, e si calcola t = As + e mod q. La chiave pubblica è (seed, t), mentre la chiave privata è costituita da s insieme all'hash della chiave pubblica. Usare un seed invece di memorizzare A consente di risparmiare una quantità significativa di memoria e larghezza di banda.

Per incapsulare, il mittente genera un messaggio casuale m e ricava sia una chiave simmetrica K sia la casualità r tramite SHA-3. Il testo cifrato è composto da due parti: u = Ar + e1 mod q e v = t^T r + e2 + encode(m) mod q. Il segreto condiviso K viene ricavato dall'hash di m. La casualità viene derivata in modo deterministico da m, associando il testo cifrato alla chiave.

Il decapsulamento recupera m calcolando v - s^T u e decodificando il risultato, quindi ricava nuovamente K da m. La trasformazione Fujisaki-Okamoto aggiunge un passaggio fondamentale: cifrare nuovamente il messaggio m recuperato e verificare che il testo cifrato corrisponda. In caso contrario, restituisce un valore pseudocasuale derivato dall'hash della chiave privata e del testo cifrato. Questo impedisce gli attacchi a testo cifrato scelto rendendo il decapsulamento deterministico e verificabile.

ML-KEM raggiunge la sicurezza IND-CCA2 nel modello dell'oracolo casuale quantistico (QROM), sulla base dell'assunzione Module-LWE. Il QROM è importante perché gli avversari post-quantistici possono interrogare le funzioni hash in sovrapposizione. La dimostrazione della sicurezza di Hofheinz, Hovelmanns e Kiltz (il framework HHK) fornisce riduzioni strette da Module-LWE alla sicurezza di ML-KEM nel QROM.

ML-KEM supera nettamente RSA nello scambio di chiavi a livelli di sicurezza equivalenti. Su una CPU moderna, la generazione delle chiavi di ML-KEM-768 richiede circa 16 microsecondi, l'incapsulamento 20 microsecondi e il decapsulamento 18 microsecondi. La generazione delle chiavi di RSA-2048 richiede alcuni secondi. Le chiavi pubbliche di ML-KEM (1184 byte) sono più grandi di quelle di ECDH (32-64 byte), ma molto più piccole di quelle di RSA-2048 (256 byte considerando solo la chiave, anche se nella pratica sono più lunghe).

Durante il periodo di transizione, lo scambio di chiavi ibrido combina ML-KEM con un algoritmo classico, in genere X25519 o ECDH P-256. Il segreto condiviso è l'hash di entrambe le uscite dei KEM: K = Hash(K_classical || K_pqc). In questo modo, la sicurezza non può essere inferiore a quella offerta da nessuno dei due componenti. TLS ibrido è specificato in IETF draft-ietf-tls-hybrid-design ed è supportato da BoringSSL, OpenSSL 3.x e Rustls.

IETF ha definito X25519ML-KEM-768 come condivisione ibrida della chiave per TLS 1.3 (draft-ietf-tls-hybrid-design). Chrome ha aggiunto il supporto nella versione 124 (aprile 2024), mentre Firefox lo ha aggiunto nella versione 132 (2024). Cloudflare ha implementato ML-KEM nella propria infrastruttura di terminazione TLS. Questa rapida adozione significa che centinaia di milioni di connessioni TLS al giorno includono ora lo scambio di chiavi post-quantistico.

A causa dei termini di errore in LWE, esiste una probabilità molto ridotta che il decapsulamento fallisca anche in assenza di un avversario. Per ML-KEM-512, la probabilità di errore è circa 2^{-139}; per ML-KEM-768 è 2^{-164}. Questi tassi sono molto al di sotto di qualsiasi soglia di interesse pratico (per fare un confronto, gli errori hardware sono molto più frequenti) e non influiscono sulla sicurezza, ma devono essere considerati nella specifica.

ML-KEM è implementato in numerose librerie open source. L'implementazione di riferimento del team Kyber è di pubblico dominio. PQClean fornisce un'implementazione C ripulita e portabile. liboqs (il progetto Open Quantum Safe) integra ML-KEM in un wrapper di libreria. AWS-LC (il fork di BoringSSL realizzato da Amazon) include ML-KEM per gli endpoint TLS di AWS. Lo standard NIST FIPS 203 contiene pseudocodice dettagliato per tutte le operazioni.

Quale set di parametri di ML-KEM raccomanda NIST per la maggior parte delle applicazioni?

ML-KEM (FIPS 203) è il KEM post-quantistico standardizzato da NIST e basato su Module-LWE. I tre set di parametri (512/768/1024) offrono rispettivamente 128/192/256 bit di sicurezza classica. La generazione delle chiavi produce una chiave pubblica compatta a partire da un seed casuale; l'incapsulamento ricava un segreto condiviso; il decapsulamento usa la trasformazione FO per garantire la sicurezza CCA2. ML-KEM è significativamente più veloce di RSA ed è già implementato in Chrome, Firefox e TLS di Cloudflare.