ML-KEM (FIPS 203) : standardisation de CRYSTALS-Kyber

ML-KEM (mécanisme d’encapsulation de clés fondé sur des réseaux modulaires), normalisé sous le nom de FIPS 203 en août 2024, constitue le remplacement post-quantique de l’échange de clés Diffie-Hellman et RSA. Il encapsule une clé symétrique à l’aide d’une clé publique et produit un secret partagé que les deux parties peuvent utiliser pour le chiffrement symétrique. ML-KEM est dérivé de CRYSTALS-Kyber, avec de légères modifications visant à rendre la spécification plus claire.

ML-KEM définit trois jeux de paramètres. ML-KEM-512 vise environ un niveau de sécurité classique de 128 bits et post-quantique de 100 bits, avec une clé publique de 800 octets et un texte chiffré de 768 octets. ML-KEM-768 vise une sécurité classique de 192 bits (clé publique de 1184 octets, texte chiffré de 1088 octets). ML-KEM-1024 vise une sécurité classique de 256 bits (clé publique de 1568 octets, texte chiffré de 1568 octets). NIST recommande ML-KEM-768 pour la plupart des applications.

La génération de clés de ML-KEM se déroule comme suit : échantillonner une matrice aléatoire A à partir d’une graine au moyen de SHAKE-128, échantillonner un petit vecteur secret s et un vecteur d’erreur e, puis calculer t = As + e mod q. La clé publique est (seed, t) et la clé privée est s, accompagnée du hachage de la clé publique. L’utilisation d’une graine plutôt que le stockage de A permet d’économiser beaucoup de mémoire et de bande passante.

Pour encapsuler, l’expéditeur génère un message aléatoire m et dérive à la fois une clé symétrique K et un aléa r au moyen de SHA-3. Le texte chiffré se compose de deux parties : u = Ar + e1 mod q et v = t^T r + e2 + encode(m) mod q. Le secret partagé K est dérivé du hachage de m. L’aléa est dérivé de manière déterministe de m, ce qui lie le texte chiffré à la clé.

La désencapsulation récupère m en calculant v - s^T u, puis en le décodant, avant de redériver K à partir de m. La transformation de Fujisaki-Okamoto ajoute une étape cruciale : rechiffrer avec le m récupéré et vérifier que le texte chiffré correspond. S’il ne correspond pas, il faut renvoyer une valeur pseudo-aléatoire dérivée du hachage de la clé privée et du texte chiffré. Cela empêche les attaques à texte chiffré choisi en rendant la désencapsulation déterministe et vérifiable.

ML-KEM atteint la sécurité IND-CCA2 dans le modèle de l’oracle aléatoire quantique (QROM), sous l’hypothèse Module-LWE. Le QROM est important, car les adversaires post-quantiques peuvent interroger les fonctions de hachage en superposition. La preuve de sécurité de Hofheinz, Hovelmanns et Kiltz (le cadre HHK) fournit des réductions précises de Module-LWE vers la sécurité de ML-KEM dans le QROM.

ML-KEM surpasse largement RSA pour l’échange de clés à des niveaux de sécurité équivalents. La génération de clés de ML-KEM-768 prend environ 16 microsecondes sur un CPU moderne, l’encapsulation 20 microsecondes et la désencapsulation 18 microsecondes. La génération de clés de RSA-2048 prend plusieurs secondes. Les clés publiques de ML-KEM (1184 octets) sont plus grandes que celles d’ECDH (32 à 64 octets), mais bien plus petites que celles de RSA-2048 (256 octets pour la clé seule, mais davantage en pratique).

Pendant la période de transition, l’échange de clés hybride combine ML-KEM avec un algorithme classique (généralement X25519 ou P-256 ECDH). Le secret partagé est le hachage des sorties des deux KEM : K = Hash(K_classical || K_pqc). Cela garantit que la sécurité ne peut être inférieure à celle de chacun des composants. TLS hybride est spécifié dans le document draft-ietf-tls-hybrid-design de l’IETF et pris en charge par BoringSSL, OpenSSL 3.x et Rustls.

L’IETF a défini X25519ML-KEM-768 comme partage de clé hybride pour TLS 1.3 (draft-ietf-tls-hybrid-design). Chrome a ajouté la prise en charge dans la version 124 (avril 2024), et Firefox dans la version 132 (2024). Cloudflare a déployé ML-KEM dans son infrastructure de terminaison TLS. Cette adoption rapide signifie que des centaines de millions de connexions TLS par jour incluent désormais un échange de clés post-quantique.

En raison des termes d’erreur de LWE, il existe une très faible probabilité que la désencapsulation échoue même en l’absence d’adversaire. Pour ML-KEM-512, la probabilité d’échec est d’environ 2^{-139} ; pour ML-KEM-768, elle est de 2^{-164}. Ces taux sont très en deçà de tout seuil préoccupant en pratique (à titre de comparaison, les erreurs matérielles sont bien plus fréquentes) et n’affectent pas la sécurité, mais doivent être pris en compte dans la spécification.

ML-KEM est implémenté dans de nombreuses bibliothèques à code source ouvert. L’implémentation de référence de l’équipe Kyber est dans le domaine public. PQClean fournit une implémentation C portable et épurée. liboqs (projet Open Quantum Safe) intègre ML-KEM dans une bibliothèque d’encapsulation. AWS-LC (dérivé de BoringSSL développé par Amazon) inclut ML-KEM pour les points de terminaison TLS d’AWS. La norme NIST FIPS 203 comprend un pseudo-code détaillé de toutes les opérations.

Quel jeu de paramètres de ML-KEM NIST recommande-t-il pour la plupart des applications ?

ML-KEM (FIPS 203) est le KEM post-quantique normalisé par NIST, fondé sur Module-LWE. Trois jeux de paramètres (512/768/1024) offrent une sécurité classique de 128/192/256 bits. La génération de clés produit une clé publique compacte à partir d’une graine aléatoire ; l’encapsulation dérive un secret partagé ; la désencapsulation utilise la transformation FO pour assurer la sécurité CCA2. ML-KEM est nettement plus rapide que RSA et est déjà déployé dans les connexions TLS de Chrome, Firefox et Cloudflare.