Der NIST-PQC-Wettbewerb: Ablauf und Kriterien

NIST startete 2016 das Standardisierungsprojekt für Post-Quanten-Kryptografie (PQC) als direkte Reaktion auf die Bedrohung durch Quantencomputer. Shors Algorithmus kann RSA und elliptische-Kurven-Kryptografie auf einem ausreichend großen Quantencomputer in Polynomialzeit brechen. NIST erkannte, dass die Umstellung kryptografischer Infrastrukturen Jahrzehnte dauert, und begann den Prozess lange bevor Quantencomputer eine unmittelbare Bedrohung darstellen.

NIST veröffentlichte im Dezember 2016 eine Aufforderung zur Einreichung und erhielt bis November 2017 insgesamt 82 vollständige Einreichungen. Nach der ersten Prüfung wurden 69 als Kandidaten der ersten Runde angenommen. Die Einreichungen deckten ein breites Spektrum mathematischer Annahmen ab: Gitterprobleme, Hashfunktionen, codebasierte Kryptografie, isogeniebasierte Kryptografie und multivariate Polynome. Die Vielfalt der Annahmen war ein zentrales Ziel, damit nicht alles auf eine einzige Karte gesetzt wurde.

In der 1. Runde führten NIST und die gesamte Kryptografie-Community eine intensive Analyse aller 69 Kandidaten durch. Zu den Kriterien gehörten Sicherheit (Widerstandsfähigkeit gegen klassische und Quantenangriffe), Leistung (Schlüssel- und Chiffretextgrößen, Berechnungsgeschwindigkeit), Flexibilität (Parametersätze für unterschiedliche Sicherheitsstufen) und Einfachheit der Implementierung. Bis Januar 2019 kamen 26 Kandidaten in die 2. Runde.

Die 26 Kandidaten der 2. Runde wurden einer umfassenderen Kryptoanalyse und Leistungsbewertung unterzogen. Mehrere Verfahren wurden in dieser Runde gebrochen oder geschwächt, darunter Rainbow (multivariat) und SIKE (isogeniebasiert, obwohl SIKE erst in der 3. Runde gebrochen wurde). Bis Juli 2020 kamen 15 Kandidaten in die 3. Runde. Sie wurden in 7 Finalisten und 8 Alternativkandidaten gegliedert.

Die 7 Finalisten der 3. Runde waren Kyber, NTRU und SABER (KEMs) sowie Dilithium, FALCON, Rainbow und SPHINCS+ (Signaturen). SIKE war ein Alternativkandidat, wurde aber 2022 spektakulär gebrochen. NIST wählte Kyber aufgrund seines klaren Designs, seiner starken Sicherheitsbeweise und seiner hervorragenden Leistung für die KEM-Standardisierung aus. Dilithium, FALCON und SPHINCS+ wurden für Signaturen ausgewählt.

NIST wählte bewusst Algorithmen aus, die auf unterschiedlichen mathematischen Problemen beruhen, um sich gegen künftige Durchbrüche abzusichern. ML-KEM und ML-DSA beruhen auf Module-LWE (Gittern). FALCON beruht auf NTRU-Gittern und Gaußscher Stichprobenziehung. SLH-DSA beruht ausschließlich auf der Sicherheit von Hashfunktionen. Sollte es einen Durchbruch bei Gitterproblemen geben, bliebe SLH-DSA sicher und würde dadurch für algorithmische Vielfalt in der standardisierten Suite sorgen.

Im Jahr 2022 eröffnete NIST eine vierte Runde, in der gezielt zusätzliche Signaturkandidaten gesucht wurden. Anlass war der Wunsch nach größerer Vielfalt bei Signaturen über gitterbasierte Verfahren hinaus. Zu den Kandidaten gehörten MAYO, CROSS, UOV und weitere Verfahren, die auf multivariaten und codebasierten Annahmen beruhen. Dieser Prozess lief parallel zur Fertigstellung der drei ersten Standards (FIPS 203, 204 und 205).

NIST veröffentlichte im August 2024 die endgültigen PQC-Standards: FIPS 203 (ML-KEM, basierend auf Kyber), FIPS 204 (ML-DSA, basierend auf Dilithium) und FIPS 205 (SLH-DSA, basierend auf SPHINCS+). FIPS 206 (FN-DSA, basierend auf FALCON) soll voraussichtlich folgen. Diese Standards müssen von US-Bundesbehörden nun zwingend berücksichtigt werden und beeinflussen über ISO, ETSI und IETF die Standardisierung weltweit.

Die IETF band PQC rasch in Protokolle ein. RFC-Entwürfe für ML-KEM in TLS 1.3, SSH und X.509-Zertifikaten waren bis 2024 in Arbeit. Cloudflare, Google und Amazon kündigten an, ML-KEM in ihren TLS-Stacks einzusetzen. Apple kündigte PQ3 für iMessage an, das ML-KEM für ratchet-basierte Post-Quanten-Vorwärtssicherheit verwendet und auf mehr als einer Milliarde Geräten bereitgestellt wurde.

Der NIST-PQC-Wettbewerb hat gezeigt, dass eine offene, gemeinschaftliche Standardisierung in der Kryptografie wirksam funktioniert. Mehrere hoch angesehene Verfahren wurden während des Prozesses gebrochen, darunter GeMSS, SIKE und Rainbow. Damit bestätigte sich die Bedeutung einer umfassenden öffentlichen Kryptoanalyse. Der Wettbewerb förderte außerdem die Entwicklung effizienter Hardwareimplementierungen und von Open-Source-Bibliotheken wie liboqs und PQClean, wodurch die Einführung beschleunigt wurde.

Die Post-Quanten-Standardisierung ist noch nicht abgeschlossen. NIST bewertet weiterhin zusätzliche Signaturverfahren, um die Vielfalt zu erhöhen. Das Finanzstandardisierungsgremium X9 entwickelt PQC-Standards für das Bankwesen. ETSI und ISO stimmen ihre Standards mit den NIST-FIPS ab. Für bestimmte Sektoren werden Migrationsleitfäden entwickelt: das Gesundheitswesen (Auswirkungen von HIPAA), das Verteidigungswesen (NSA-CNSA-2.0-Suite) und die Telekommunikation (3GPP für 5G/6G).

Wie viele Kandidaten gelangten von den ursprünglichen Einreichungen in Runde 2 des NIST-PQC-Wettbewerbs?

NIST startete das PQC-Standardisierungsprojekt 2016 und erhielt 69 vollständige Einreichungen. In drei Bewertungsrunden wurde das Feld anhand von Sicherheit, Leistung und Vielfalt eingegrenzt. Als endgültige Auswahl wurden Kyber (ML-KEM, FIPS 203), Dilithium (ML-DSA, FIPS 204), SPHINCS+ (SLH-DSA, FIPS 205) und FALCON (FN-DSA, FIPS 206) bestimmt. Der Wettbewerb bestätigte den Wert offener Kryptanalyse und führte zu breit eingesetzten Standards, die nun in TLS-, SSH- und Messaging-Protokolle integriert werden.