Kyber (Kryptosystem)

Kyber ist ein Schlüsselkapselungsverfahren (KEM), das entwickelt wurde, um gegen kryptanalytische Angriffe mit zukünftigen leistungsfähigen Quantenrechnern resistent zu sein. Es dient der Etablierung eines gemeinsamen Geheimnisses zwischen zwei kommunizierenden Parteien, ohne dass ein (IND-CCA2-)Angreifer im Übertragungssystem im Stande wäre, dieses zu erschließen. Dieses asymmetrische Kryptosystem nutzt eine Variante des mutmaßlich NP-schweren Gitterproblems des Learning with errors als seine grundlegende Falltürfunktion. Es hat mit einigen anderen Verfahren das NIST Auswahlverfahren zum ersten Post-Quanten-Kryptographie-Standard gewonnen.

Eigenschaften

Das Verfahren basiert auf module learning with errors (M-LWE) aus dem Bereich des Maschinellen Lernens, in Verbindung mit Kreisteilungs-Ringen. Neuerdings gibt es auch einen formalen mathematischen Nachweis einer weitestgehenden Gleichwertigkeit des Ring-LWE-Problems zu MLWE (Reduktion). Im Vergleich zu konkurrierenden PQ-Verfahren hat es als Gitter-basiertes Verfahren typische Vorteile, unter anderem bezüglich Laufzeit sowie der Größe der Chiffrate und des Schlüsselmaterials. Es sind Varianten mit unterschiedlichen Sicherheitsstufen definiert: Kyber512 (NIST-Sicherheitsstufe 1, ≈AES 128), Kyber768 (NIST-Sicherheitsstufe 3, ≈AES 192) und Kyber1024 (NIST-Sicherheitsstufe 5, ≈AES 256). Die Angaben der NIST zu den Sicherheitsstufen (zumindest von Kyber512) sind allerdings umstritten. Bei einem Sicherheitsniveau von 161 Bit an Komplexität sind die geheimen Schlüssel 2400, die öffentlichen 1184 und das Chiffrat 1088 Bytes groß. Bei einer entsprechend optimierten Implementierung können für die kryptographischen Operationen 4 Kilobyte an Speicher ausreichend sein. Für ein Anwendungsszenario bei Verschlüsselung von Chat unter Verwendung der liboqs wurden für die Ersetzung des extrem effizienten, nicht quantensicheren ECDH-Schlüsselaustauschs mit Curve25519 eine Erhöhung der Laufzeit um etwa Faktor 2,3 (1,5–7), ein geschätzt 2,3-facher (1,4–3,1) Energieverbrauch und etwa 70-fach (48–92) größere kryptographische Verwaltungsdaten festgestellt. Die internen Streuwertberechnungen machen den Großteil der Laufzeit aus, welche damit potenziell sehr von entsprechender Hardware-Beschleunigung profitieren würde.

Entwicklung

Kyber ist eine Weiterentwicklung eines 2005 von Oded Regev veröffentlichten Verfahrens durch Entwickler aus Europa und Nordamerika, mit finanzieller Förderung von Europäischer Kommission, Schweiz, Niederlanden und Deutschland, die bei verschiedenen staatlichen Hochschulen oder Forschungseinrichtungen oder auch bei Privatfirmen angestellt sind. An der Entwicklung beteiligt waren u. a. Eike Kiltz (Horst-Görtz-Institut der Ruhr-Universität Bochum) und Peter Schwabe (Max-Planck-Institut für Sicherheit und Privatsphäre) im Rahmen des Exzellenzclusters CASA (Cyber Security in the Age of Large Scale Adversaries).

Ergänzend entwickelten sie auch das verwandte Signaturverfahren Dilithium, als weiteren Teil ihrer „Cryptographic Suite for Algebraic Lattices“ (CRYSTALS, etwa „Kryptographie-Paket für algebraische Gitter“). Wie andere PQC-KEM-Verfahren macht Kyber intern reichlich Gebrauch von Streuwertfunktionen. Bei Kyber werden hier Varianten von Keccak (SHA-3/SHAKE) eingesetzt, unter anderem zur Generierung von Pseudozufallszahlen. Das Verfahren wurde 2017 beim National Institute of Standards and Technology (NIST) für dessen öffentlichen Wettbewerb für einen ersten Standard für quantensichere Kryptographie (NISTPQC) eingereicht. Es ist einer der vielversprechendsten Finalisten für den Anfang 2022 erwarteten Standard. Als einer von vier asymmetrischen Verschlüsselungsalgorithmen konkurriert er mit mindestens zwei anderen Verfahren. Das McEliece-Verfahren basiert auf einem anderen Prinzip und könnte zusätzlich standardisiert werden. In der zweiten Phase des Auswahlverfahrens wurden etliche Parameter des Algorithmus’ angepasst und die Komprimierung der öffentlichen Schlüssel abgeschafft. Während die Berechnungskomplexität des Algorithmus’ vergleichsweise hervorragend gering ist, würde das NIST gegebenenfalls als konservativere Option NTRU vorziehen, falls Sicherheitsprobleme oder Patentansprüche für Kyber auftauchen. Die vom französischen Nationalen Zentrum für wissenschaftliche Forschung behauptete Anwendbarkeit seines Patents von Gaborit und Aguilar-Melchor ist umstritten. Zuletzt legte das NIST besonderes Augenmerk auf Kosten hinsichtlich Laufzeit und Komplexität bei Implementierungen, die Laufzeiten maskieren, um entsprechenden Seitenkanalangriffen (SCA) vorzubeugen.

Einsatz

Die Entwickler haben eine gemeinfreie (bzw. unter CC0) Referenzimplementierung veröffentlicht, die in C geschrieben ist. Die Programmbibliothek liboqs des Open Quantum Safe (OQS) Projekts enthält eine darauf basierende Implementierung. OQS pflegt auch einen quantensicheren Entwicklungszweig von OpenSSL, kümmert sich um die Integration in BoringSSL und sein Code wurde auch in WolfSSL integriert. Von Drittentwicklern gibt es eine Handvoll Implementierungen in verschiedenen anderen Programmiersprachen, darunter JavaScript und Java. Es existieren verschiedene (freie) optimierte Hardware-Implementierungen, unter anderem mit Resistenz gegen Seitenkanal-Angriffe. Das BSI strebt Implementierung in Thunderbird an, und in diesem Zusammenhang auch eine Implementierung in der Programmbibliothek Botan und entsprechenden Anpassungen des OpenPGP-Standards. Im September 2023 gab der Messenger Signal bekannt, dass Kyber ab sofort im weitverbreiteten Signal-Protokoll zum Einsatz kommt.

Weblinks

• offizielle Website
• Code-Repository
• ursprüngliches Verfahren von Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC ’05). ACM Press, Baltimore, MD, USA 2005, ISBN 1-58113-960-8, S. 84, doi:10.1145/1060590.1060603 (acm.org). 
• Eine leicht verständliche Zusammenfassung mit Beispielrechnung.