Ein fortgeschrittener Verschlüsselungsalgorithmus, der der Entschlüsselung durch leistungsstarke Quantencomputer in der Zukunft standhalten sollte, wurde von einem Computer mit Intel Xeon CPU in einer Stunde trivial geknackt.
Es handelt sich um den Algorithmus SIKE – kurz für Supersingular Isogeny Key Encapsulation – der es in die vierte Runde des Standardisierungsprozesses für Post-Quantum-Kryptografie (PQC) des National Institute of Standards and Technology (NIST) des US-Handelsministeriums geschafft hat.
„Der angehängte Magma-Code bricht die Microsoft SIKE-Herausforderungen $IKEp182 und $IKEp217 in etwa 4 Minuten bzw. 6 Minuten, wenn er auf einem einzigen Kern ausgeführt wird“, schreiben die KU Leuven-Forscher Wouter Castryck und Thomas Decru in einem neuen Papier.
„Ein Durchlauf der SIKEp434-Parameter, von denen bisher angenommen wurde, dass sie die NIST-Quantensicherheitsstufe 1 erfüllen, dauerte etwa 62 Minuten, ebenfalls auf einem einzigen Kern.
Der Code wurde auf einer Intel Xeon CPU E5-2630v2 mit 2,60 GHz ausgeführt, die 2013 mit der Ivy Bridge Mikroarchitektur des Chip-Herstellers auf den Markt kam, so die Wissenschaftler weiter.
Die Ergebnisse kommen zu einem Zeitpunkt, an dem das NIST Anfang Juli die erste Reihe von quantenresistenten Verschlüsselungsalgorithmen bekannt gab: CRYSTALS-Kyber für allgemeine Verschlüsselung und CRYSTALS-Dilithium, FALCON und SPHINCS+ für digitale Signaturen.
„SIKE ist eine isogenie-basierte Schlüsselkapselungs-Suite, die auf pseudo-zufälligen Spaziergängen in supersingulären Isogenie-Graphen basiert“, heißt es in der Beschreibung der Algorithmus-Autoren.
Microsoft, das an dem Algorithmus maßgeblich beteiligt ist, sagt, dass SIKE „arithmetische Operationen auf elliptischen Kurven, die über endlichen Feldern definiert sind, verwendet und Karten, sogenannte Isogenien, zwischen solchen Kurven berechnet“.
„Die Sicherheit von SIDH und SIKE beruht auf der Schwierigkeit, eine bestimmte Isogenie zwischen zwei solchen elliptischen Kurven zu finden, oder anders ausgedrückt, einen Pfad zwischen ihnen im Isogenie-Graphen zu finden“, erklärt das Forschungsteam des Technologieriesen.
Quantenresistente Kryptografie ist ein Versuch, Verschlüsselungssysteme zu entwickeln, die sowohl gegen Quanten- als auch gegen herkömmliche Rechensysteme sicher sind und gleichzeitig mit bestehenden Kommunikationsprotokollen und -netzwerken zusammenarbeiten.
Damit soll sichergestellt werden, dass Daten, die heute mit aktuellen Algorithmen wie RSA, Elliptic Curve Cryptography (ECC), AES und ChaCha20 verschlüsselt werden, in Zukunft nicht durch Brute-Force-Angriffe angreifbar werden, wenn Quantencomputer aufkommen.
„Jedes dieser Systeme beruht auf einer Art mathematischem Problem, das in der einen Richtung leicht zu lösen ist, in der anderen aber schwer“, sagte David Jao, einer der Miterfinder von SIKE, gegenüber The Hacker News. „Quantencomputer können die schwierigen Probleme, die RSA und ECC zugrunde liegen, leicht lösen, was etwa 100 % des verschlüsselten Internetverkehrs betreffen würde, wenn man Quantencomputer bauen würde.“
Obwohl SIKE als einer der vom NIST benannten PQC-Anwärter positioniert war, wird der Algorithmus durch die neuesten Forschungen praktisch außer Kraft gesetzt.
„Die Arbeit von Castryck und Decru bricht SIKE“, sagte Jao. „Genauer gesagt bricht sie SIDH [Supersingular Isogeny Diffie-Hellman], das ‚harte‘ Problem, auf dem SIKE basiert (ähnlich wie die ganzzahlige Faktorisierung das harte Problem ist, auf dem RSA basiert).“
„Neben SIKE gibt es noch andere isogeny-basierte Kryptosysteme. Einige von ihnen, wie B-SIDH, basieren ebenfalls auf SIDH und werden durch den neuen Angriff ebenfalls gebrochen. Einige von ihnen, wie CSIDH und SQIsign, basieren nicht auf SIDH und sind, soweit wir wissen, nicht direkt von dem neuen Angriff betroffen.“
Was die nächsten Schritte angeht, so sagte Jao, dass SIDH zwar aktualisiert werden kann, um die neue Angriffslinie zur Wiederherstellung von Schlüsseln zu beheben, dies aber bis zu weiteren Untersuchungen aufgeschoben werden soll.
„Es ist möglich, dass SIDH gepatcht oder repariert werden kann, um den neuen Angriff zu verhindern, und wir haben einige Ideen dafür, aber wir müssen den neuen Angriff noch weiter analysieren, bevor wir eine Aussage über mögliche Korrekturen machen können“, sagte Jao.