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 Lernens mit Fehlern 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). 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). 

Einzelnachweise

1. Dustin Moody: Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. NIST IR 8413. National Institute of Standards and Technology, Gaithersburg, MD 2022, S. NIST IR 8413, doi:10.6028/nist.ir.8413 (nist.gov [PDF; abgerufen am 6. Juli 2022]). 
2. What was NIST thinking? (PDF-Datei)
3. Status Report on the Second Round of the NIST PQC Standardization Process (PDF-Datei)
4. Chris Peikert, Zachary Pepin: Algebraically Structured LWE, Revisited. In: Theory of Cryptography. Band 11891. Springer International Publishing, Cham 2019, ISBN 978-3-03036029-0, S. 1–23, doi:10.1007/978-3-030-36030-6_1 (umich.edu [PDF]). 
5. Lattice-based cryptography and Kyber – Andrea Basso (PDF; 2 MB)
6. Overview of NIST Round 3 Post-Quantum cryptography Candidates (PDF; 157 kB)
7. Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren: Kyber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM. In: Progress in Cryptology – AFRICACRYPT 2018 (= Lecture Notes in Computer Science). Springer International Publishing, Cham 2018, ISBN 978-3-319-89339-6, S. 282–305, doi:10.1007/978-3-319-89339-6_16 (bham.ac.uk [PDF]). 
8. https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf
9. Leon Botros, Matthias J. Kannwischer, Peter Schwabe: Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4. In: Progress in Cryptology – AFRICACRYPT 2019 (= Lecture Notes in Computer Science). Springer International Publishing, Cham 2019, ISBN 978-3-03023696-0, S. 209–228, doi:10.1007/978-3-030-23696-0_11 (kannwischer.eu [PDF]). 
10. Ines Duits: The Post-Quantum Signal Protocol: Secure Chat in a Quantum World. Hrsg.: University of Twente. 5. Februar 2019 (englisch, utwente.nl [PDF]). 
11. https://pq-crystals.org/
12. [1], Official Kyber Website, 27. September 2022
13. Sarah Henderson: NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’. 22. Juli 2020, abgerufen am 5. November 2021 (englisch). 
14. non-app-KyberSaber (PDF-Datei)
15. Kyber/LICENSE at master · pq-crystals/kyber · GitHub
16. (Memento des Originals vom 20. April 2021 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/openquantumsafe.org
17. Post-Quantum TLS. In: Microsoft Research. Abgerufen am 5. November 2021 (amerikanisches Englisch). 
18. wolfSSL and libOQS Integration. In: wolfSSL-Website. 1. September 2021, abgerufen am 5. November 2021 (amerikanisches Englisch). 
19. https://github.com/fisherstevenk/kyberJCE
20. https://github.com/antontutoveanu/crystals-kyber-javascript
21. (Memento des Originals vom 28. Juli 2021 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/git.schwanenlied.me
22. B. Dang, Kamyar Mohajerani, K. Gaj: High-Speed Hardware Architectures and Fair FPGA Benchmarking. 2021 (nist.gov [PDF]). 
23. Arpan Jati, Naina Gupta, A. Chattopadhyay, S. Sanadhya: A Configurable Crystals-Kyber Hardware Implementation with Side-Channel Protection. In: IACR Cryptol. ePrint Arch. 2021 (iacr.org [PDF]). 
24. https://www.evergabe-online.de/tenderdetails.html?id=397181
25. Quantum Resistance and the Signal Protocol. Abgerufen am 21. September 2023 (englisch).