PQC: Neuer Quantencomputer-Algorithmus bedroht gitternetzbasierte Verfahren

Ein kürzlich erschienenes Paper mit dem Titel "Quantum Algorithms for Lattice Problems" von Yilei Chen zieht in der Kryptografie-Szene einiges an Aufmerksamkeit auf sich. Der im Paper beschriebene Quantencomputer-Algorithmus beziehungsweise Angriff könnte gitternetzbasierte Verfahren knacken. Ob das stimmt, müssen jetzt Kryptoanalysten herausbekommen.

Hintergrund

Gängige Verschlüsselungsverfahren wie ECDSA oder RSA sind langfristig Quantencomputern ausgeliefert. Schuld daran ist der 1992 entwickelte Algorithmus von Peter Shor, der die mathematischen Probleme hinter den Verfahren besonders effizient angeht. Dafür braucht es große Quantencomputer, die es aber (noch) nicht gibt.

Damit man im Ernstfall gewappnet ist, rief das US-amerikanische National Institute of Standards and Technology (NIST) 2016 ein Auswahlverfahren aus, um Quantencomputer-resistente Verschlüsselungsverfahren und digitale Signaturen zu finden. Nach mehrjährigem Aussieben kürte das NIST 2022 die Verschlüsselung Crystals-Kyber sowie die Signaturen Crystals-Dilithium, Falcon und SPHINCS⁺ zu den Gewinnern. Verfahren wie Kyber oder Dilithium basieren auf mathematischen Problemen in Gitternetzen, von denen man ausgeht, sie seien besonders schwer zu brechen – selbst für Quantencomputer.

Funktionsfähigkeit ungewiss

Das Paper vom 10. April stellt das nun infrage: Für bestimmte Parameter hat der Autor Yilei Chen einen Algorithmus formuliert, der das Shortest-Independent-Vector-Problem (SIVP) und das Decisional-Shortest-Vector-Problem (GapSVP) effizient auflöst. Der Autor betont allerdings in seinem Paper, dass der Angriff nicht gegen Kyber oder Dilithium klappen würde. Doch wie Matthew Green, Kryptograf und Professor an der Johns-Hopkins-Universität, in seinem ersten Überblick über das Paper festhält: So ganz in Sicherheit sollte man sich nicht wiegen, denn häufig tendieren Kryptografen dazu, Angriffe zu verbessern.

Für eine realistische Einschätzung, ob von diesem Verfahren wirklich Gefahr für aktuelle Post-Quantum-Projekte ausgeht, ist es aber viel zu früh. Denn dafür muss der Algorithmus funktionieren – das versuchen Kryptoanalysten gerade zu prüfen. So merkte der Kryptograf Omri Shmueli bereits einen Fehler im Paper an, was der Autor flott auf seiner Webseite beantworten konnte. Da der Angriff sehr kompliziert ist, existiert gerade kein schnellerer Weg, als die Experten ihre Arbeit machen zu lassen. Es stellt sich nicht selten heraus, dass frisch publizierte Angriffe nur in speziellen Szenarien oder vielleicht gar nicht funktionieren. Zudem ist dieser Angriff bisher reine Theorie und muss sich – wenn er denn funktioniert – in der Praxis beweisen. Solange das Paper nicht bestätigt wurde, gibt es also keinen Grund, in Panik zu verfallen.

(wid)