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

ML-KEM (modulgitterbasierter Schlüssel-Kapselungsmechanismus), im August 2024 als FIPS 203 standardisiert, ist der postquantenkryptografische Ersatz für den Diffie-Hellman- und RSA-Schlüsselaustausch. Dabei wird ein symmetrischer Schlüssel unter einem öffentlichen Schlüssel gekapselt, wodurch ein gemeinsames Geheimnis entsteht, das beide Parteien für symmetrische Verschlüsselung verwenden können. ML-KEM wurde aus CRYSTALS-Kyber abgeleitet und für eine klarere Spezifikation geringfügig angepasst.

ML-KEM definiert drei Parametersätze. ML-KEM-512 zielt auf ungefähr 128 Bit klassische und 100 Bit postquantenkryptografische Sicherheit ab, mit einem öffentlichen Schlüssel von 800 Byte und einem Chiffrat von 768 Byte. ML-KEM-768 zielt auf 192 Bit klassische Sicherheit ab (öffentlicher Schlüssel: 1184 Byte, Chiffrat: 1088 Byte). ML-KEM-1024 zielt auf 256 Bit klassische Sicherheit ab (öffentlicher Schlüssel: 1568 Byte, Chiffrat: 1568 Byte). NIST empfiehlt ML-KEM-768 für die meisten Anwendungen.

Die Schlüsselerzeugung in ML-KEM läuft wie folgt ab: Aus einem Seed wird mithilfe von SHAKE-128 eine zufällige Matrix A erzeugt. Anschließend werden ein kleiner geheimer Vektor s und ein Fehlervektor e erzeugt und t = As + e mod q berechnet. Der öffentliche Schlüssel ist (Seed, t), während der private Schlüssel aus s zusammen mit dem Hash des öffentlichen Schlüssels besteht. Die Verwendung eines Seeds anstelle der Speicherung von A spart erheblichen Speicherplatz und Bandbreite.

Für die Kapselung erzeugt der Sender eine zufällige Nachricht m und leitet mithilfe von SHA-3 sowohl einen symmetrischen Schlüssel K als auch den Zufallswert r ab. Das Chiffrat besteht aus zwei Teilen: u = Ar + e1 mod q und v = t^T r + e2 + encode(m) mod q. Das gemeinsame Geheimnis K wird aus dem Hash von m abgeleitet. Der Zufallswert wird deterministisch aus m abgeleitet, wodurch das Chiffrat an den Schlüssel gebunden wird.

Bei der Dekapselung wird m durch die Berechnung von v - s^T u und anschließendes Decoding wiederhergestellt. Danach wird K erneut aus m abgeleitet. Die Fujisaki-Okamoto-Transformation fügt einen entscheidenden Schritt hinzu: Das Chiffrat wird mit dem wiederhergestellten m erneut verschlüsselt und auf Übereinstimmung geprüft. Falls es nicht übereinstimmt, wird ein pseudoras­cher Wert zurückgegeben, der aus dem Hash des privaten Schlüssels und des Chiffrats abgeleitet wird. Dadurch werden Chosen-Ciphertext-Angriffe verhindert, weil die Dekapselung deterministisch und überprüfbar ist.

ML-KEM erreicht IND-CCA2-Sicherheit im Quanten-Zufallsorakelmodell (QROM), und zwar unter der Annahme von Module-LWE. Das QROM ist wichtig, weil Postquantenangreifer Hashfunktionen in Superposition abfragen können. Der Sicherheitsnachweis von Hofheinz, Hovelmanns und Kiltz (das HHK-Framework) liefert im QROM enge Reduktionen von Module-LWE auf die Sicherheit von ML-KEM.

ML-KEM übertrifft RSA beim Schlüsselaustausch auf vergleichbaren Sicherheitsstufen deutlich. Die Schlüsselerzeugung für ML-KEM-768 dauert auf einer modernen CPU etwa 16 Mikrosekunden, die Kapselung 20 Mikrosekunden und die Dekapselung 18 Mikrosekunden. Die Schlüsselerzeugung für RSA-2048 dauert Sekunden. Öffentliche ML-KEM-Schlüssel (1184 Byte) sind größer als ECDH-Schlüssel (32–64 Byte), aber deutlich kleiner als RSA-2048-Schlüssel (256 Byte allein für den Schlüssel, in der Praxis jedoch länger).

Während der Übergangsphase kombiniert ein hybrider Schlüsselaustausch ML-KEM mit einem klassischen Algorithmus (typischerweise X25519 oder P-256 ECDH). Das gemeinsame Geheimnis ist der Hash beider KEM-Ausgaben: K = Hash(K_classical || K_pqc). Dadurch kann die Sicherheit nicht schlechter sein als die einer der beiden Komponenten. Hybrides TLS ist im IETF-Entwurf draft-ietf-tls-hybrid-design spezifiziert und wird von BoringSSL, OpenSSL 3.x und Rustls unterstützt.

Die IETF hat X25519ML-KEM-768 als hybriden Key Share für TLS 1.3 definiert (draft-ietf-tls-hybrid-design). Chrome fügte die Unterstützung in Version 124 (April 2024) hinzu, Firefox in Version 132 (2024). Cloudflare hat ML-KEM in seiner TLS-Terminierungsinfrastruktur eingesetzt. Durch diese schnelle Einführung enthalten nun täglich Hunderte Millionen TLS-Verbindungen einen postquantenkryptografischen Schlüsselaustausch.

Aufgrund der Fehlerterme in LWE besteht eine winzige Wahrscheinlichkeit, dass die Dekapselung auch ohne Angreifer fehlschlägt. Für ML-KEM-512 beträgt die Fehlerwahrscheinlichkeit ungefähr 2^{-139}, für ML-KEM-768 2^{-164}. Diese Raten liegen weit unterhalb jeder praktischen Relevanz (zum Vergleich: Hardwarefehler treten deutlich häufiger auf) und beeinflussen die Sicherheit nicht, müssen aber in der Spezifikation berücksichtigt werden.

ML-KEM ist in zahlreichen Open-Source-Bibliotheken implementiert. Die Referenzimplementierung des Kyber-Teams ist gemeinfrei. PQClean stellt eine bereinigte, portable C-Implementierung bereit. liboqs (das Open Quantum Safe-Projekt) integriert ML-KEM in einen Bibliotheks-Wrapper. AWS-LC (Amazons Fork von BoringSSL) enthält ML-KEM für AWS-TLS-Endpunkte. Der NIST-Standard FIPS 203 enthält detaillierten Pseudocode für alle Operationen.

Welchen ML-KEM-Parametersatz empfiehlt NIST für die meisten Anwendungen?

ML-KEM (FIPS 203) ist ein von NIST standardisiertes postquantenkryptografisches KEM auf Grundlage von Module-LWE. Drei Parametersätze (512/768/1024) bieten 128/192/256 Bit klassische Sicherheit. Die Schlüsselerzeugung erstellt aus einem zufälligen Seed einen kompakten öffentlichen Schlüssel, die Kapselung leitet ein gemeinsames Geheimnis ab und die Dekapselung verwendet die FO-Transformation für CCA2-Sicherheit. ML-KEM ist deutlich schneller als RSA und wird bereits in Chrome, Firefox und der TLS-Infrastruktur von Cloudflare eingesetzt.