Ein neuer Angriff hat einen potenziellen Verschlüsselungsalgorithmus leicht außer Gefecht gesetzt

Apr 14, 2023

Dan Goodin, Ars Technica

Im Rahmen der laufenden Kampagne der US-Regierung zum Schutz von Daten im Zeitalter von Quantencomputern verdeutlicht ein neuer und mächtiger Angriff, bei dem ein einziger traditioneller Computer verwendet wurde, um einen Kandidaten der vierten Runde vollständig zu zerstören, die Risiken, die mit der Standardisierung der nächsten Generation von Verschlüsselungsalgorithmen verbunden sind.

Diese Geschichte erschien ursprünglich auf Ars Technica, einer vertrauenswürdigen Quelle für Technologienachrichten, Analysen der Technologiepolitik, Rezensionen und mehr. Ars gehört der Muttergesellschaft von WIRED, Condé Nast.

Letzten Monat wählte das US-amerikanische National Institute of Standards and Technology (NIST) vier Post-Quanten-Computing-Verschlüsselungsalgorithmen aus, um Algorithmen wie RSA, Diffie-Hellman und Elliptic Curve Diffie-Hellman zu ersetzen, die Angriffen von Quanten nicht standhalten können Computer.

Im gleichen Schritt entwickelte das NIST bis zu weiteren Tests vier weitere Algorithmen als potenzielle Ersatzalgorithmen, in der Hoffnung, dass einer oder mehrere davon auch geeignete Verschlüsselungsalternativen in einer Post-Quanten-Welt sein könnten. Der neue Angriff bricht SIKE, einen der letzten vier zusätzlichen Algorithmen. Der Angriff hat keine Auswirkungen auf die vier vom NIST als anerkannte Standards ausgewählten PQC-Algorithmen, die alle auf völlig anderen mathematischen Techniken als SIKE basieren.

SIKE – kurz für Supersingular Isogeny Key Encapsulation – ist nun wahrscheinlich aus dem Rennen, dank einer Studie, die am Wochenende von Forschern der Gruppe Computersicherheit und industrielle Kryptographie an der KU Leuven veröffentlicht wurde. Das Papier mit dem Titel „An Efficient Key Recovery Attack on SIDH (Preliminary Version)“ beschrieb eine Technik, die komplexe Mathematik und einen einzigen herkömmlichen PC nutzt, um die Verschlüsselungsschlüssel wiederherzustellen, die die SIKE-geschützten Transaktionen schützen. Der gesamte Vorgang erfordert nur etwa eine Stunde Zeit. Diese Leistung berechtigt die Forscher Wouter Castryck und Thomas Decru zu einer Belohnung von 50.000 US-Dollar vom NIST.

„Die neu aufgedeckte Schwachstelle ist eindeutig ein schwerer Schlag für SIKE“, schrieb David Jao, Professor an der University of Waterloo und Miterfinder von SIKE, in einer E-Mail. „Der Angriff kommt wirklich unerwartet.“

Das Aufkommen der Public-Key-Verschlüsselung in den 1970er Jahren war ein großer Durchbruch, da es Parteien, die sich noch nie zuvor getroffen hatten, den sicheren Austausch verschlüsselter Materialien ermöglichte, die von einem Gegner nicht geknackt werden konnten. Die Verschlüsselung mit öffentlichen Schlüsseln basiert auf asymmetrischen Schlüsseln, wobei ein privater Schlüssel zum Entschlüsseln von Nachrichten und ein separater öffentlicher Schlüssel zum Verschlüsseln verwendet wird. Benutzer stellen ihren öffentlichen Schlüssel allgemein zur Verfügung. Solange ihr privater Schlüssel geheim bleibt, bleibt das System sicher.

In der Praxis kann sich die Public-Key-Kryptographie oft als unhandlich erweisen, weshalb viele Systeme auf Schlüsselkapselungsmechanismen basieren, die es Parteien, die sich noch nie zuvor getroffen haben, ermöglichen, sich über ein öffentliches Medium wie das Internet gemeinsam auf einen symmetrischen Schlüssel zu einigen. Im Gegensatz zu Algorithmen mit symmetrischen Schlüsseln können heute verwendete Schlüsselkapselungsmechanismen von Quantencomputern leicht gebrochen werden. Vor dem neuen Angriff ging man davon aus, dass SIKE solche Schwachstellen durch die Verwendung einer komplexen mathematischen Konstruktion vermeiden sollte, die als supersingulärer Isogeniegraph bekannt ist.

Der Grundstein von SIKE ist ein Protokoll namens SIDH, kurz für Supersingular Isogeny Diffie-Hellman. Das am Wochenende veröffentlichte Forschungspapier zeigt, wie anfällig SIDH für ein Theorem namens „Glue-and-Split“ ist, das 1997 vom Mathematiker Ernst Kani entwickelt wurde, sowie für Werkzeuge, die von seinen Mathematikkollegen Everett W. Howe, Franck Leprévost und Bjorn entwickelt wurden Poonen im Jahr 2000. Die neue Technik baut auf dem sogenannten adaptiven GPST-Angriff auf, der in einem Artikel aus dem Jahr 2016 beschrieben wurde. Die Mathematik hinter dem jüngsten Angriff ist für die meisten Nicht-Mathematiker garantiert undurchschaubar. Hier ist ungefähr so ​​nah, wie Sie kommen werden:

„Der Angriff nutzt die Tatsache aus, dass SIDH Hilfspunkte hat und dass der Grad der geheimen Isogenie bekannt ist“, erklärte Steven Galbraith, Mathematikprofessor an der University of Auckland und das „G“ im adaptiven GPST-Angriff, in einem kurzen Artikel zum neuen Angriff. „Die Hilfspunkte in SIDH waren schon immer ein Ärgernis und eine potenzielle Schwachstelle, und sie wurden für Fehlerangriffe, den adaptiven GPST-Angriff, Torsionspunktangriffe usw. ausgenutzt.“

Lauren Goode

Lauren Goode

Julian Chokkattu

Will Knight

Wichtiger als das Verständnis der Mathematik schrieb Jonathan Katz, IEEE-Mitglied und Professor am Department of Computer Science der University of Maryland, in einer E-Mail: „Der Angriff ist völlig klassisch und erfordert überhaupt keine Quantencomputer.“

SIKE ist der zweite vom NIST benannte PQC-Kandidat, der in diesem Jahr für ungültig erklärt wurde. Im Februar veröffentlichte IBM-Postdoc-Forscher Ward Beullens Forschungsergebnisse, die laut Cryptomathic Rainbow, ein kryptografisches Signaturschema, mit seiner Sicherheit brachen, „die auf der Härte des Problems beruhte, ein großes System multivariater quadratischer Gleichungen über einem endlichen Feld zu lösen“.

Die PQC-Ersatzkampagne des NIST läuft seit fünf Jahren. Hier ist eine kurze Geschichte:

Rainbow fiel in Runde 3. SIKE hatte es bis Runde 4 geschafft.

Katz fuhr fort:

Es ist vielleicht ein wenig besorgniserregend, dass dies das zweite Beispiel in den letzten sechs Monaten für ein Schema ist, das es in die dritte Runde des NIST-Überprüfungsprozesses geschafft hat, bevor es mithilfe eines klassischen Algorithmus vollständig gebrochen wurde. (Das frühere Beispiel war Rainbow, das im Februar gebrochen wurde.) Drei der vier PQC-Systeme basieren auf relativ neuen Annahmen, deren genaue Schwierigkeit noch nicht genau verstanden ist. Der jüngste Angriff deutet also darauf hin, dass wir möglicherweise immer noch vorsichtig/konservativ sein müssen mit dem weiteren Standardisierungsprozess.

Ich fragte Jao, den SIKE-Miterfinder, warum die Schwäche erst jetzt, in einem relativ späten Entwicklungsstadium, ans Licht gekommen sei. Seine Antwort war aufschlussreich. Er sagte:

Es stimmt, dass der Angriff auf Mathematik zurückgreift, die in den 1990er und 2000er Jahren veröffentlicht wurde. In gewisser Weise erfordert der Angriff keine neue Mathematik; es hätte jederzeit bemerkt werden können. Ein unerwarteter Aspekt des Angriffs besteht darin, dass er Kurven der Gattung 2 verwendet, um elliptische Kurven (die Kurven der Gattung 1 sind) anzugreifen. Ein Zusammenhang zwischen den beiden Kurventypen ist völlig unerwartet. Um ein Beispiel zu nennen, das verdeutlicht, was ich meine: Seit Jahrzehnten versuchen Menschen, die reguläre Kryptografie mit elliptischen Kurven anzugreifen, darunter auch einige, die versucht haben, Ansätze zu verwenden, die auf Kurven der Gattung 2 basieren. Keiner dieser Versuche war erfolgreich. Für diesen Versuch, im Bereich der Isogenien erfolgreich zu sein, handelt es sich also um eine unerwartete Entwicklung.

Im Allgemeinen gibt es in der mathematischen Literatur viele tiefgreifende Mathematikveröffentlichungen, die von Kryptographen jedoch nicht gut verstanden werden. Ich zähle mich zu den vielen Forschern, die in der Kryptographie arbeiten, aber nicht so viel Mathematik verstehen, wie wir eigentlich sollten. Manchmal genügt also jemand, der die Anwendbarkeit bestehender theoretischer Mathematik auf diese neuen Kryptosysteme erkennt. Genau das ist hier passiert.

Die an NIST übermittelte SIKE-Version erforderte einen einzigen Schritt zur Generierung des Schlüssels. Eine mögliche Variante von SIKE könnte zweistufig aufgebaut sein. Jao sagt, es sei möglich, dass diese letztere Variante nicht anfällig für die Mathematik sei, die diesen Bruch verursacht habe. Vorerst ist SIKE jedoch tot, zumindest im aktuellen Rennen. Der Zeitplan für die verbleibenden drei Kandidaten ist derzeit nicht bekannt.

Diese Geschichte erschien ursprünglich auf Ars Technica.