CRYSTALS-Kyber.

CRYSTALS-Kyber ist ein Schlüsselkapselungsverfahren (KEM), dessen Sicherheit sich auf das Module-Learning-With-Errors-Problem (MLWE) über strukturierten Gittern zurückführen lässt. NIST wählte es 2022 als primäres PQC-KEM aus und finalisierte es im August 2024 als FIPS 203 (ML-KEM). Der Standard definiert drei Parametersätze – ML-KEM-512, ML-KEM-768 und ML-KEM-1024 – die auf die NIST-Sicherheitsklassen 1, 3 und 5 abzielen, mit öffentlichen Schlüsseln von rund 800, 1184 und 1568 Bytes und Chiffraten vergleichbarer Größe.

Intern wird ein IND-CPA-sicheres Public-Key-Verfahren mittels einer Fujisaki-Okamoto-Transformation zu einem IND-CCA2-sicheren KEM gehärtet: Die Dekapselung verschlüsselt die zurückgewonnene Nachricht erneut und weist jede Abweichung zurück, sodass ein manipuliertes Chiffrat einen pseudozufälligen „Implicit-Reject"-Schlüssel liefert, statt Geheimnisse preiszugeben. Da ein Store-now-decrypt-later-Angreifer den heutigen Datenverkehr für einen künftigen Quantencomputer archivieren könnte, wird Kyber im Hybrid-Modus eingesetzt (zum Beispiel X25519MLKEM768), bei dem ein Angreifer sowohl die klassische als auch die post-quantenkryptografische Hälfte brechen muss.

Die Implementierungssicherheit ist ebenso wichtig wie die Mathematik. Die KyberSlash-Offenlegung (2024) zeigte, dass eine geheimnisabhängige ganzzahlige Division durch den Modulus q = 3329 auf vielen CPUs mit variabler Laufzeit ausgeführt wurde; durch Timing der Dekapselung gefälschter Chiffrate ließen sich Schlüsselbits zurückgewinnen. KyberSlash1 und KyberSlash2 wurden im Referenzcode (Dezember 2023) behoben, indem Divisionen durch Multiplikationen ersetzt wurden, und die Korrekturen verbreiteten sich in liboqs, PQClean, CIRCL, AWS-LC und Botan.

flowchart LR
  KG[Schlüsselerzeugung] --> PK[Öffentlicher Schlüssel pk]
  KG --> SK[Geheimer Schlüssel sk]
  PK --> ENC[Kapselung: m wählen, K und Chiffrat c ableiten]
  ENC --> C[Chiffrat c]
  ENC --> KS1[Gemeinsames Geheimnis K]
  C --> DEC[Dekapselung mit sk und FO-Neuverschlüsselungsprüfung]
  SK --> DEC
  DEC -->|Übereinstimmung| KS2[Gleiches gemeinsames Geheimnis K]
  DEC -->|Abweichung| REJ[Implicit Reject: pseudozufälliger Schlüssel]