SABER

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 Lernens mit Fehlern 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]