Ding, ding. Fight!
Post-Quantum-Kryptografie: Wie es mit dem NIST-Auswahlverfahren weitergeht
Seit sechs Jahren sucht die US-Standardisierungsbehörde NIST nach quantencomputerresistenten Verschlüsselungsverfahren. Währenddessen knackten Kryptoanalytiker plötzlich vielversprechende Kandidaten und das NIST wurde verklagt. Aber nun sind die ersten vier Verfahren standardisiert – ein Überblick über die wichtigsten Ereignisse im Auswahlprozess und die Empfehlungen anderer Behörden.
Ein typisches Szenario aus Dutzenden Blockbustern: Hacker sitzen in schwach beleuchteten Räumen vor Monitoren und brechen in wenigen Minuten ins Pentagon ein, schleusen Gelder um und knacken verschlüsselte Mails. In der Realität funktioniert das fast nie so, wie es im Film dargestellt wird. Gängige Verschlüsselungsverfahren wie RSA [1] oder ECDSA schützen Kommunikationskanäle nicht nur vor Hackern, sondern auch vor jeglicher Art von Supercomputer.
Quantencomputer dagegen sind eine andere Geschichte. Der bereits 1992 von Peter Shor entwickelte Algorithmus knackt zum Beispiel im Handumdrehen die oben genannten Verfahren. Vorausgesetzt in Zukunft gibt es solch große leistungsstarke Quantencomputer, die den Algorithmus ausführen können, wären tatsächlich hollywoodreife Szenarien möglich.
Das Problem ist den Kryptologen bewusst: 2006 tagte die erste Post-Quanten-Kryptografie-Konferenz, die sich anschaute, welche Verfahren von Quantencomputern bedroht sind. Knapp 10 Jahre später startete das US-amerikanische National Institute of Standards and Technology (NIST) ein rundenbasiertes Auswahlverfahren, um neue Verschlüsselungen, Signaturen und Schlüsselaustauschverfahren zu finden, die Angriffen eines Quantencomputers trotzen können (siehe Infografik „NIST-Auswahlverfahren“ auf Seite 134) – sogenannte quantencomputerresistente Verfahren.
Bereits vergangenes Jahr sprachen wir in [2] von den unterschiedlichen Kandidaten und Finalisten, die sich im Laufe der Jahre hervorgetan haben. Einige von ihnen hat das NIST mittlerweile standardisiert, andere wiederum sind Kryptoanalytikern zum Opfer gefallen. Dieser Artikel beleuchtet die größten Veränderungen in der Welt der Post-Quantum-Kryptografie (PQC) und wie es mit dem Auswahlverfahren weitergeht.
Das Auswahlverfahren …
Nach vier Runden und sechs Jahren hat das NIST im Juli dieses Jahres die ersten Verfahren standardisiert: die Verschlüsselung CRYSTALS-Kyber und die digitalen Signaturen CRYSTALS-Dilithium, Falcon und SPHINCS+. Vier weitere Verschlüsselungen ziehen eine Runde weiter. Die Bedenkzeit zahlte sich bereits aus, denn Kryptologen haben für eines der Verfahren einen effizienten Angriff gefunden. Dazu später mehr.
Bei den CRYSTALS-Verfahren und Falcon handelt es sich um sogenannte gitternetzbasierte Verfahren (ein detailliertes Beispiel für deren Funktionsweise haben wir in [2] beschrieben). Die mathematischen Probleme wie Shortest-Vector-Problem (SVP) oder Closest-Vector-Problem (CVP), die sich aus Gitternetzen ergeben, sind gut erforscht und gelten als sicher. Die CRYSTALS-Verfahren zum Beispiel benutzen beide CVP als mathematisches Problem. Falcon dagegen verwendet SVP. NIST nahm Falcon mit in die Liste auf, weil Dilithium sehr große Signaturen erstellt, aber kürzere Signaturen schnelle Anwendungen begünstigen würden (Falcon: 5000 Bit, Dilithium: 20.000 Bit).
SPHINCS+ dagegen benutzt klassische Hashes [3] wie SHAKE256, SHA-256 und Haraka. Das NIST entschied sich, eine Alternative zu den gitternetzbasierten Verfahren zu standardisieren, damit eine größere Auswahl an Verfahren mit unterschiedlichen mathematischen Problemen zur Verfügung steht.