SABER

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

SABER ist ein Schlüsselkapselungsverfahren, das entwickelt wurde, um gegen kryptanalytische Angriffe mit leistungsfähigen Quantenrechnern resistent zu sein, die in wenigen Jahren möglich sein könnten. Es dient der Etablierung eines gemeinsamen Geheimnisses zwischen zwei kommunizierenden Parteien, ohne dass ein mitlesender Angreifer in der Leitung 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 gilt als vielversprechender Kandidat für einen ersten Post-Quanten-Kryptographie-Standard.

Das Verfahren basiert auf module learning with rounding (M-LWR) aus dem Bereich des Maschinellen Lernens in Verbindung mit Kreisteilungs-Ringen.[1] Eine kleine Anpassung im Rahmen des NIST-Auswahlverfahrens ermöglicht nunmehr einen formalen mathematischen Nachweis einer dem MLWR-Problem gleichwertigen Komplexität (Reduktion).[2] 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.[3] Es sind Varianten mit unterschiedlichen Sicherheitsstufen definiert: LightSABER (NIST-Sicherheitsstufe 1, ≈AES 128), SABER (NIST-Sicherheitsstufe 3, ≈AES 192) und FireSABER (NIST-Sicherheitsstufe 5, ≈AES 256).[4] Bei einem Sicherheitsniveau von 180 Bit an Komplexität sind die geheimen Schlüssel 2304 und die öffentlichen 992 Bytes groß.[5] Bei einer entsprechend optimierten Implementierung können für die kryptographischen Operationen 6,2 Kilobyte an Speicher ausreichend sein.[6] 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 10 (5–30), ein geschätzt 2,4-facher (1,3–3,6) Energieverbrauch und etwa 65-fach (44–87) größere kryptographische Verwaltungsdaten festgestellt.[7]

SABER wurde entwickelt von Mitgliedern der Forschungsgruppe Computer Security and Industrial Cryptography (COSIC) der Katholieke Universiteit Leuven, Belgien, mit verschiedener staatlicher und privater Förderung und Unterstützung von anderen Universitäten.[8][5] 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.[9] 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.[4] 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 SABER auftauchen. Die vom französischen Nationalen Zentrums für wissenschaftliche Forschung behauptete Anwendbarkeit seines Patents von Gaborit und Aguilar-Melchor ist umstritten.[10] Obwohl 2020 keine konkreten Sicherheitsprobleme bekannt waren, empfahl das NIST dennoch weitere Untersuchungen, besonders im Hinblick auf Anfälligkeit für Seitenkanalangriffe (SCA), bestimmten Optimierungen der algorithmischen Komplexität und Komplexitätsunterschiede zwischen MLWR und WLWE.[2] In der Folge wurden SCA-resistente Varianten entwickelt, die Laufzeiten maskieren, allerdings auf Kosten von Laufzeit und Komplexität.[11]

Die Entwickler haben eine gemeinfreie Referenzimplementierung veröffentlicht, die in C und Assemblersprache geschrieben ist.[12] Die Programmbibliothek liboqs des Open Quantum Safe (OQS) Projekts enthält eine darauf basierende[13] Implementierung.[7] OQS pflegt auch einen quantensicheren Entwicklungszweig von OpenSSL,[14] kümmert sich um die Integration in BoringSSL und sein Code wurde auch in WolfSSL integriert.[15]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. What was NIST thinking? (PDF-Datei)
  2. a b Status Report on the Second Round of the NIST PQC Standardization Process (PDF-Datei)
  3. Lattice-based cryptography and SABER – Andrea Basso (PDF; 2,0 MB)
  4. a b Overview of NIST Round 3 Post-Quantum cryptography Candidates (PDF; 157 kB)
  5. a b Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren: Saber: 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]).
  6. Angshuman Karmakar, Jose Maria Bermudo Mera, Sujoy Sinha Roy, Ingrid Verbauwhede: Saber on ARM: CCA-secure module lattice-based key encapsulation on ARM. In: IACR Transactions on Cryptographic Hardware and Embedded Systems. 14. August 2018, ISSN 2569-2925, S. 243–266, doi:10.13154/tches.v2018.i3.243-266 (iacr.org).
  7. a b Ines Duits: The Post-Quantum Signal Protocol: Secure Chat in a Quantum World. Hrsg.: University of Twente. 5. Februar 2019 (englisch, utwente.nl [PDF]).
  8. SABER-Website: Acknowledgements. Abgerufen am 5. November 2021.
  9. Sarah Henderson: NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’. 22. Juli 2020, abgerufen am 5. November 2021 (englisch).
  10. non-app-KyberSaber (PDF-Datei)
  11. Abubakr Abdulgadir, Kamyar Mohajerani, Viet B. Dang, Jens-Peter Kaps, Kris Gaj: A Lightweight Implementation of Saber Resistant Against Side-Channel Attacks. In: Computer Security Resource Center, NIST (Hrsg.): Third PQC Standardization Conference. 9. Juni 2021 (nist.gov [PDF]).
  12. SABER/LICENSE at master · KULeuven-COSIC/SABER · GitHub
  13. Saber – Open Quantum Safe
  14. Post-Quantum TLS. In: Microsoft Research. Abgerufen am 5. November 2021 (amerikanisches Englisch).
  15. wolfSSL and libOQS Integration. In: wolfSSL-Website. 1. September 2021, abgerufen am 5. November 2021 (amerikanisches Englisch).