Quantum-Angriff auf Gitternetz-Verschlüsselung: Panik oder noch viel Arbeit für Kryptoanalytiker?

Ein kürzlich veröffentlichtes wissenschaftliches Dokument mit dem Titel “Quantum Algorithms for Lattice Problems” hat in der Kryptografie-Gemeinschaft erhebliches Aufsehen erregt. Der darin beschriebene Quantencomputer-Algorithmus oder Angriff hat das Potenzial, gitternetzbasierte Verschlüsselungsverfahren zu entschlüsseln. Nun liegt es an den Kryptoanalytikern, herauszufinden, ob dies tatsächlich der Fall ist.

Verschlüsselungsverfahren wie das Elliptic Curve Digital Signature Algorithm (ECDSA) oder das Rivest-Shamir-Adleman (RSA) Verfahren sind langfristig anfällig für Angriffe durch Quantencomputer. Der Grund dafür liegt in dem 1992 von Peter Shor entwickelten Algorithmus, der die mathematischen Probleme hinter diesen Verfahren besonders effizient lösen kann. Angesichts der Tatsache, dass leistungsfähige Quantencomputer derzeit noch nicht existieren, hat das National Institute of Standards and Technology (NIST) der Vereinigten Staaten im Jahr 2016 ein Auswahlverfahren initiiert, um Verschlüsselungsverfahren und digitale Signaturen zu identifizieren, die gegen Quantencomputer beständig sind.

Nach einer mehrjährigen Auswahlprozedur hat das NIST im Jahr 2022 die Verschlüsselung Crystals-Kyber sowie die Signaturen Crystals-Dilithium, Falcon und SPHINCS als Gewinner gekürt. Diese Verfahren basieren auf mathematischen Problemen in Gitternetzen, die auch für Quantencomputer als besonders schwierig anzusehen sind.

Das jüngst veröffentlichte Paper vom 10. April wirft jedoch Zweifel auf: Yilei Chen hat einen Algorithmus entwickelt, der das Shortest-Independent-Vector-Problem (SIVP) und das Decisional-Shortest-Vector-Problem (GapSVP) effizient lösen kann. Unter bestimmten Parametern scheint dieser Algorithmus die Grundlagen von gitternetzbasierten Verfahren zu bedrohen. Allerdings betont Chen in seinem Paper, dass dieser Angriff nicht gegen die von NIST gekürten Verfahren Kyber oder Dilithium funktionieren würde.

Matthew Green, ein Kryptograf und Professor an der Johns-Hopkins-Universität, weist in seinem ersten Überblick über das Paper darauf hin, dass man sich nicht zu sicher fühlen sollte, da Kryptografen oft dazu neigen, Angriffe zu verbessern. Es ist jedoch noch zu früh für eine realistische Einschätzung, ob dieses Verfahren tatsächlich eine Bedrohung für aktuelle Post-Quantum-Projekte darstellt. Derzeit sind Kryptoanalysten dabei, den Algorithmus zu überprüfen.

Bereits jetzt gibt es erste Hinweise auf einen Fehler in dem Paper, den der Autor schnell auf seiner Webseite korrigiert hat. Angesichts der Komplexität des Angriffs gibt es derzeit keine einfachere Lösung, als den Experten die Arbeit zu überlassen. Es ist eine bekannte Tatsache, dass neu veröffentlichte Angriffe oft nur unter bestimmten Bedingungen wirksam sind oder möglicherweise gar nicht funktionieren. Darüber hinaus handelt es sich bei diesem Angriff bisher nur um eine theoretische Annahme, die in der Praxis noch bewiesen werden muss, falls sie tatsächlich erfolgreich ist. Solange das Paper nicht verifiziert wurde, besteht kein Grund zur Panik. Die Kryptoanalyse-Community wird weiterhin die Sicherheit von Post-Quantum-Verschlüsselungsmethoden erforschen und verbessern, um zukünftige Bedrohungen durch Quantencomputer zu bewältigen.

Schlagwörter: NIST + Quantum + Chen

Wie bewerten Sie den Schreibstil des Artikels?