Wenn die heutigen Kryptografieprotokolle versagen würden, wäre es unmöglich, Online-Verbindungen zu sichern – um vertrauliche Nachrichten zu senden, sichere Finanztransaktionen durchzuführen oder Daten zu authentifizieren. Jeder konnte auf alles zugreifen; jeder konnte vorgeben, jemand zu sein. Die digitale Wirtschaft würde zusammenbrechen.
Wann (bzw if) ein voll funktionsfähiger Quantencomputer zur Verfügung steht, genau das könnte passieren. Infolgedessen startete das National Institute of Standards and Technology (NIST) der US-Regierung 2017 einen internationalen Wettbewerb, um die besten Wege zu finden, um „Post-Quanten“-Kryptographie zu erreichen.
Im vergangenen Monat wählte die Agentur ihre erste Gruppe von Gewinnern aus: vier Protokolle, die mit einigen Überarbeitungen als Quantenschild eingesetzt werden. Es gab auch vier weitere Kandidaten bekannt, die noch geprüft werden.
Dann, am 30. Juli, enthüllten zwei Forscher, dass sie es getan hatten gebrochen einer dieser Kandidaten in einer Stunde auf einem Laptop. (Seitdem haben andere den Angriff noch schneller gemacht und das Protokoll innerhalb weniger Minuten gebrochen.) „Ein Angriff, der so dramatisch und kraftvoll ist … war ein ziemlicher Schock“, sagte er Steven Galbraith, Mathematiker und Informatiker an der University of Auckland in Neuseeland. Die dem Angriff zugrunde liegende Mathematik war nicht nur überraschend, sondern reduzierte auch die (dringend benötigte) Vielfalt der Post-Quanten-Kryptographie – wodurch ein Verschlüsselungsprotokoll eliminiert wurde, das ganz anders funktionierte als die überwiegende Mehrheit der Schemata im NIST-Wettbewerb.
"Es ist ein bisschen schade", sagte Christoph Peikert, ein Kryptograf an der University of Michigan.
Die Ergebnisse haben die Post-Quanten-Kryptographie-Community sowohl erschüttert als auch ermutigt. Erschüttert, weil dieser Angriff (und ein weiterer aus einer früheren Runde des Wettbewerbs) plötzlich eine digitale Stahltür in nasse Zeitung verwandelte. „Es kam aus heiterem Himmel“, sagte er Dustin Moody, einer der Mathematiker, die die NIST-Standardisierungsbemühungen leiten. Aber wenn ein kryptografisches Schema gebrochen werden soll, ist es am besten, wenn es lange vor seiner Verwendung in freier Wildbahn passiert. „Es gibt viele Emotionen, die durch dich gehen“, sagte er David Jao, ein Mathematiker an der University of Waterloo in Kanada, der zusammen mit einem IBM-Forscher Luca de Feo, schlug das Protokoll 2011 vor. Überraschung und Enttäuschung gehören sicherlich dazu. „Aber auch“, fügte Jao hinzu, „zumindest ist es jetzt kaputt gegangen.“
Geheime Spaziergänge zwischen Kurven
Jao und De Feo hatten eine Gelegenheit für ein kryptografisches System gesehen, das sowohl ähnlich als auch angemessen verschieden von bekannten Protokollen war. Ihr Schema, das als supersinguläres isogenes Diffie-Hellman-Protokoll (SIDH) bezeichnet wird, befasste sich mit elliptischen Kurven – denselben mathematischen Objekten, die in einer der am weitesten verbreiteten Arten der Kryptographie verwendet werden, die heute eingesetzt wird. Aber es nutzte sie auf ganz andere Weise. Es war auch das kompakteste Schema, das NIST in Betracht zog (mit dem Kompromiss, dass es langsamer war als viele der anderen Kandidaten).
Und „mathematisch gesehen ist es wirklich elegant“, sagte Jao. „Damals schien es eine schöne Idee zu sein.“
Nehmen wir an, zwei Parteien, Alice und Bob, wollen heimlich eine Nachricht austauschen, sogar unter den wachsamen Augen eines potenziellen Angreifers. Sie beginnen mit einer Sammlung von Punkten, die durch Kanten verbunden sind, die als Graph bezeichnet werden. Jeder Punkt repräsentiert eine andere elliptische Kurve. Wenn Sie eine Kurve auf eine bestimmte Weise in eine andere umwandeln können (über eine als Isogenie bezeichnete Karte), zeichnen Sie eine Kante zwischen dem Punktpaar. Der resultierende Graph ist riesig und man kann sich leicht darin verirren: Wenn Sie einen relativ kurzen Spaziergang entlang seiner Kanten machen, landen Sie an einem Ort, der völlig zufällig aussieht.
Die Graphen von Alice und Bob haben dieselben Punkte, aber die Kanten sind unterschiedlich – sie sind durch unterschiedliche Isogenien definiert. Alice und Bob beginnen am selben Punkt, und sie hüpfen jeweils entlang zufälliger Kanten auf ihrem eigenen Diagramm, wobei sie ihren Weg von einem Punkt zum anderen verfolgen. Jeder veröffentlicht dann seinen Endort, hält aber seinen Pfad geheim.
Jetzt tauschen sie die Plätze: Alice geht zu Bobs Endpunkt und Bob zu Alices. Jeder wiederholt seinen geheimen Spaziergang. Sie tun dies so, dass sie beide am selben Punkt landen.
Dieser Ort wurde im Geheimen gefunden, sodass Alice und Bob ihn als ihren geheimen Schlüssel verwenden können – Informationen, die es ihnen ermöglichen, die Nachrichten des anderen sicher zu verschlüsseln und zu entschlüsseln. Selbst wenn ein Angreifer die Zwischenpunkte sieht, die Alice und Bob sich gegenseitig senden, kennt er den geheimen Weg von Alice oder Bob nicht, sodass er diesen endgültigen Endpunkt nicht herausfinden kann.
Aber damit SIDH funktioniert, müssen Alice und Bob auch einige zusätzliche Informationen über ihre Wanderungen austauschen. Diese zusätzlichen Informationen führten zum Untergang von SIDH.
Eine neue Variante der alten Mathematik
Thomas Decru nicht darauf aus, SIDH zu brechen. Er versuchte, darauf aufzubauen – die Methode zu verallgemeinern, um eine andere Art von Kryptografie zu verbessern. Das hat nicht funktioniert, aber es hat eine Idee geweckt: Sein Ansatz könnte nützlich sein, um SIDH anzugreifen. Und so näherte er sich Wouter Castryck, sein Kollege an der Katholischen Universität Leuven in Belgien und einer seiner ehemaligen Doktorvater, und die beiden tauchten in die einschlägige Literatur ein.
Dabei stießen sie auf eine Veröffentlichung des Mathematikers Ernst Kani im Jahr 1997. Darin war ein Theorem, das „fast sofort auf SIDH anwendbar war“, sagte Castryck. „Ich denke, als uns klar wurde, dass … der Angriff ziemlich schnell kam, in ein oder zwei Tagen.“
Letztendlich untersuchten Castryck und Decru, um Alices geheimen Gang (und damit den gemeinsamen Schlüssel) wiederzufinden, das Produkt zweier elliptischer Kurven – Alices Startkurve und die Kurve, die sie öffentlich an Bob schickte. Diese Kombination erzeugt eine Art Oberfläche, die als abelsche Oberfläche bezeichnet wird. Dann benutzten sie diese abelschen Flächen, den Satz von Kani (der abelsche Flächen mit elliptischen Kurven in Beziehung setzt) und die zusätzlichen Informationen, die Alice Bob gab, um jeden Schritt aufzudecken, den Alice unternahm.
„Es ist fast wie ein Zielsuchsignal, mit dem Sie [bestimmte abelsche Oberflächen] erfassen können“, sagte Jao. „Und dieses Signal sagt Ihnen, dass dies der Weg ist, den Sie gehen sollten, um den nächsten Schritt zu tun, um den richtigen [geheimen Weg] zu finden.“ Was sie direkt zum gemeinsamen Schlüssel von Alice und Bob führte.
„Es ist ein sehr unerwarteter Ansatz, zu komplizierteren Objekten zu gehen, um Ergebnisse über das einfachere Objekt abzuleiten“, sagte Jao.
„Ich war sehr aufgeregt zu sehen, dass diese Technik verwendet wird“, sagte er Kristin Lauter, ein Mathematiker und Kryptograph bei Meta AI Research, der nicht nur an der Entwicklung isogenetischer Kryptografie mitgewirkt hat, sondern auch an abelschen Oberflächen gearbeitet hat. „So schäme ich mich, dass ich nicht daran gedacht habe, es zu brechen.“
Der Angriff von Castryck und Decru brach die niedrigste Sicherheitsversion des SIDH-Protokolls in 62 Minuten und die höchste Sicherheitsstufe in knapp einem Tag. Dann, kurz darauf, optimierte ein anderer Experte den Angriff so, dass es nur 10 Minuten dauerte, um die Version mit niedriger Sicherheit zu knacken, und ein paar Stunden, um die Version mit hoher Sicherheit zu knacken. Allgemeinere Angriffe in den letzten Wochen gepostet machen es unwahrscheinlich, dass SIDH gerettet werden kann.
„Es war ein besonderes Gefühl“, sagte Castryck, wenn auch ein bittersüßes. „Wir haben eines unserer Lieblingssysteme zerstört.“
Ein Wendepunkt
Es ist unmöglich zu garantieren, dass ein System bedingungslos sicher ist. Stattdessen verlassen sich Kryptografen darauf, dass genügend Zeit vergeht und genügend Leute versuchen, das Problem zu lösen, um sich sicher zu fühlen. „Das bedeutet nicht, dass Sie nicht morgen aufwachen und feststellen, dass jemand einen neuen Algorithmus dafür gefunden hat“, sagte er Jeffrey Hoffstein, Mathematiker an der Brown University.
Daher sind Wettbewerbe wie der von NIST so wichtig. In der vorherigen Runde des NIST-Wettbewerbs entwickelte Ward Beullens, ein Kryptograph bei IBM, einen solchen Angriff brach einen Plan namens Rainbow an einem Wochenende. Wie Castryck und Decru konnte er seinen Angriff erst inszenieren, nachdem er das zugrunde liegende mathematische Problem aus einem anderen Blickwinkel betrachtet hatte. Und wie der Angriff auf SIDH brach dieser ein System, das auf einer anderen Mathematik beruhte als die meisten vorgeschlagenen Post-Quanten-Protokolle.
„Die jüngsten Angriffe waren ein Wendepunkt“, sagte er Thomas Prest, ein Kryptograph beim Startup PQShield. Sie zeigen, wie schwierig Post-Quanten-Kryptographie ist und wie viel Analyse erforderlich sein könnte, um die Sicherheit verschiedener Systeme zu untersuchen. „Ein mathematisches Objekt hat möglicherweise in einer Perspektive keine offensichtliche Struktur und in einer anderen eine verwertbare Struktur“, sagte er. „Das Schwierige ist, die richtige neue Perspektive zu finden.“
