Manchmal ist es erstaunlich einfach, die Cybersecurity-Szene zu überraschen. Im Juli 2022 brauchte es dafür nur einen alten Computer und zehn Minuten Zeit: Mit diesen Zutaten schafften es zwei belgische Mathematiker, ein als besonders sicher geltendes Verschlüsselungsverfahren zu knacken. Eigentlich hätte diese Verschlüsselung einem Angriff künftiger Quantencomputer standhalten sollen – aber irgendwas schienen die Entwickler übersehen zu haben. Denn ein neun Jahre alter klassischer Computer reichte aus, um die angeblich sichere Verschlüsselung der Zukunft innerhalb kürzester Zeit zu brechen.

Dabei habe er nicht wirklich daran geglaubt, dass er es schaffen würde, berichtet Thomas Decru. Der Kryptograf hat den Angriff als Postdoktorand an der Katholischen Universität Leuven in Belgien geplant. »Ich glaube, ich war überraschter als die meisten anderen«, sagt er. Zusammen mit seinem Doktorvater Wouter Castryck hatte er den mathematischen Ansatz zunächst auf einem Whiteboard skizziert. Aber Decru zweifelte, ob er wirklich funktionieren würde – bis die beiden ihn tatsächlich auf einem PC ausprobierten. »Es dauerte eine Weile, bis mir klar wurde, dass wir die Verschlüsselung wirklich gebrochen hatten.«

Das Verschlüsselungsverfahren mit dem Namen SIKE war mit dem ehrgeizigen Ziel entwickelt worden, Geheimnisse auch in Zukunft geheim zu halten. Er war einer von vier Algorithmen, die das US-amerikanische National Institute of Standards and Technology (NIST) im Jahr 2022 im Rahmen des Standardisierungsprozesses für Post-Quanten-Kryptografie ausgewählt hatte. Ziel war es, Algorithmen zu finden, die private Informationen vor der drohenden Gefahr durch Quantencomputer schützen können.

Quantencomputer können all unsere Geheimnisse entschlüsseln

Wer digitale Informationen sicher und vertraulich halten will, ist auf Verschlüsselungen angewiesen. Doch die bisher verbreiteten Verfahren schützen nicht vor Quantencomputern: Festplatten mit medizinischen Daten, Informationen von Militär und Geheimdiensten ebenso wie Online-Kreditkartenzahlungen, digitale Unterschriften, Messwerte von intelligenten Zählern und die Computer in fahrerlosen Autos hängen von Algorithmen ab, die in den 1970er Jahren entwickelt wurden. Und diese halten keinem Quantencomputer stand.

Eine Verschlüsselung verwandelt lesbare Daten in kryptische Chiffren, die nur denjenigen zugänglich sind, die einen »Schlüssel« besitzen. Diese Algorithmen hängen wiederum von mathematischen Funktionen ab, die in eine Richtung einfach zu berechnen sind, sich aber nur sehr schwer umkehren lassen. Das kann man mit dem Braten eines Eis vergleichen: Es ist nicht möglich, ein Spiegelei in seine ursprüngliche Form zurückzuverwandeln.

Wenn nun allerdings irgendwann Quantencomputer für den Praxiseinsatz bereitstehen, werden diese schwer zu lösenden Probleme plötzlich zum Kinderspiel. Verschlüsselungen auf Basis des so genannten RSA-Algorithmus beispielsweise – eines der bekanntesten bisherigen Verschlüsselungsalgorithmen – zu knacken und damit Daten lesbar zu machen, würde mit heutigen Rechnern fast die gesamte Lebensdauer des Universums erfordern. Ein Quantencomputer, schätzen Forscher, könnte die gleiche Aufgabe in nur acht Stunden erledigen.

Der Diffie-Hellman-Schlüsselaustausch, eine andere weit verbreitete kryptografische Methode, die nach ihren beiden Erfindern benannt ist, könnte ebenfalls leicht von einem Quantencomputer gebrochen werden. Gleiches gilt für die »elliptische-Kurven-Kryptografie«, die fast überall Anwendung findet.

Der Vorteil der Quantencomputer hat mit den Informationseinheiten zu tun. Während klassische Computer mit gewöhnlichen digitalen Bits aus Einsen und Nullen arbeiten, verwenden Quantencomputer so genannte Quantenbits oder Qubits. Diese haben quantenmechanische Eigenschaften, unter anderem können sie überlagerte Zustände annehmen. In so einem Fall kann das Qubit gleichzeitig sowohl eine Eins als auch eine Null darstellen – eine Messung des Systems ergibt dann beispielsweise zu 70 Prozent eins und zu 30 Prozent null.

Die Fähigkeit, sich in vielen Zuständen gleichzeitig zu befinden, ermöglicht es einem Quantencomputer, manche mathematischen Operationen viel schneller auszuführen, als es selbst der leistungsfähigste klassische Computer könnte. Durch die enormen Fortschritte bei der Entwicklung von Quantencomputern sind Berechnungen, die bisher quasi die gesamte Lebensdauer des Universums benötigt hätten, nun in realistischere Dimensionen gerückt.

Wann sind Quantencomputer groß genug?

Aktuelle Quantencomputer enthalten meist nur eine Hand voll Qubits – höchstens ein paar hundert – und haben bisher nur begrenzte Fähigkeiten. IBM plant allerdings, 2024 einen Chip mit 1121 Qubits auf den Markt zu bringen, und will bis 2025 einen Computer mit mehr als 4000 Qubits herstellen.

Doch auch das reicht noch nicht aus, um bisherige Verfahren zu überwinden: Eine Forschungsgruppe von Google und der schwedischen Nationalen Behörde für Kommunikationssicherheit schätzte im Jahr 2021, dass 20 Millionen Qubits notwendig sein werden, um einen RSA-Schlüssel mit einer Länge von 2048 Bit (eine häufig verwendete Schlüssellänge) zu knacken. »Die große Frage ist natürlich, ob all die Bemühungen, das Quantencomputing praktikabel zu machen, irgendeinen kryptoanalytischen Nutzen haben werden«, sagt Ronald Rivest, Informatiker am Massachusetts Institute of Technology in Cambridge. Für seinen Namen steht das R in RSA, dem Verfahren, das er zusammen mit seinen Kollegen entwickelt hat, nämlich mit den Informatikern Adi Shamir am Weizmann Institute of Science in Israel und Leonard Adleman an der University of Southern California: »Das ist immer noch eine offene Frage.«

»Ihre Daten könnten schon jetzt für einen zukünftigen Quantencomputer gespeichert werden, auch wenn noch keiner gebaut wurde«Dustin Moody, Mathematiker

Aber selbst wenn praxistaugliche Quantencomputer erst in 20 Jahren gebaut werden, ist das Problem heute schon dringlich, sagen Forschende. »Ihre Daten könnten schon jetzt für einen zukünftigen Quantencomputer gespeichert werden, auch wenn noch keiner gebaut wurde«, erklärt Dustin Moody. Der Mathematiker arbeitet in der Abteilung für Computersicherheit des NIST und leitet das Projekt für Post-Quanten-Kryptografie. Spionageagenturen oder Cyberkriminelle könnten heute verschlüsselte Daten sammeln und einfach warten, bis die Technologie aufholt. Viele Fachleute vermuten, dass Länder wie China und die Vereinigten Staaten das bereits tun.

Für den Fall, dass Quantencomputer irgendwann tatsächlich aktuelle Verschlüsselungsverfahren knacken können, arbeiten Kryptografen und Normungsgremien auf der ganzen Welt daran, neue Verschlüsselungstechniken zu entwickeln, die für einen Quantencomputer ebenso schwer zu durchbrechen sind wie die bestehenden Systeme für klassische Computer. Und natürlich ist es wichtig, diese ausgiebig zu testen, bevor unsere Geheimnisse damit verschlüsselt werden.

Die Entschlüsselung von SIKE brachte Decru und Castryck eine Belohnung von 50 000 US-Dollar von Microsoft ein. Nachdem die beiden Forscher ihre Ergebnisse bekannt gegeben hatten, gelang es anderen Gruppen sogar, den Code noch schneller zu entschlüsseln.

SIKE war nicht der erste Zukunftsalgorithmus des NIST, der scheiterte. Ein weiterer Kandidat namens Rainbow, der auf einem anderen mathematischen Ansatz beruht, war fünf Monate zuvor – an einem einzigen Wochenende – von Ward Beullens geknackt worden, einem Postdoktoranden bei IBM Research Zurich.

Nur drei quantensichere Algorithmen sind übrig

Solche potenziell quantenresistenten Algorithmen bis zur Belastungsgrenze zu testen, ist das Ziel des mehrjährigen Wettbewerbs, den das NIST zur Entwicklung von Post-Quanten-Kryptografieverfahren ausgeschrieben hat. »Der Stärkste wird bleiben«, erwartet Moody. »Manchmal sehen sie zunächst viel versprechend aus, aber im Lauf der Jahre erkennen wir ihre Schwächen und wissen dann, dass wir neue Ideen brauchen.«

Von den ursprünglich 69 Algorithmen-Kandidaten, die das NIST Ende 2017 ausgewählt hat, sind laut Moody zwischen 25 und 30 entweder komplett gescheitert oder hatten massive Schwächen. Ende August 2023 veröffentlichte das NIST den Entwurf von Standards für drei der verbleibenden Algorithmen und forderte die Öffentlichkeit zur Stellungnahme auf. Die Behörde plant, die Standards 2024 fertigzustellen.

Neben der Verschlüsselung von Daten müssen kryptografische Verfahren eine weitere Aufgabe erfüllen: Authentifizierungen. So genannte Signaturen stellen sicher, dass eine Person, die ein Dokument vorlegt, auch wirklich diejenige ist, die sie vorgibt zu sein.

Von den drei übrigen NIST-Kandidaten ist ein Algorithmus – CRYSTALS-Kyber – für die Verschlüsselung und den Austausch von öffentlichen Schlüsseln vorgesehen. Die beiden anderen – CRYSTALS-Dilithium und SPHINCS+ – werden zur Sicherung digitaler Signaturen verwendet. Ein Normentwurf für einen anderen Algorithmus für digitale Signaturen, Falcon, soll ebenfalls 2024 von NIST veröffentlicht werden.

40 weitere Kandidaten für digitale Signaturen wurden im Juli 2023 gesammelt, nachdem die Behörde einen Aufruf für eine neue Runde von Einreichungen verschickt hatte. »Sie senden damit die Botschaft, dass sie mit den drei vorhandenen nicht zufrieden sind«, sagt die Kryptografin Tanja Lange, die die Gruppe für Codierungstheorie und Kryptologie an der Technischen Universität Eindhoven leitet und zu SPHINCS+ beigetragen hat.

Zusätzliche Informationen sind angreifbar

Eine Verschlüsselung ist mehr als nur ein schwer zu lösendes mathematisches Problem. Sie muss auch eine Möglichkeit bieten, Informationen über das Problem mit der Person zu teilen, die es entschlüsseln soll – und das führt zu einer Schwachstelle.

In der Kryptografie braucht man ein schwieriges Problem, auf dem man ein System aufbauen kann, erklärt Castryck, »aber es gibt immer zusätzliche Informationen, die weitergegeben werden müssen, damit das funktioniert«.

Das SIKE-System fußt auf einer so genannten Isogenese: einer Karte, die zeigt, wie Punkte auf einer elliptischen Kurve mit Punkten auf einer anderen solchen Kurve übereinstimmen. Um das SIKE-System zu entschlüsseln, muss man die richtige Karte zwischen zwei zufälligen Kurven aus mindestens 2⁴³⁴ solchen Exemplaren finden – die Zahl ist so groß, dass es im Deutschen kein Wort dafür gibt. Um dem Empfänger einer verschlüsselten Nachricht den Schlüssel mitzuteilen, muss jeder Absender Informationen über zwei Punkte entlang einer der Kurven liefern. Castryck und Decru waren in der Lage, diese Informationen über die Punkte zu nutzen, um die gesamte Karte zu rekonstruieren – und konnten damit den Code knacken, ohne das schwierige mathematische Problem selbst zu lösen.

Die Isogenese als Grundlage für ein kryptografisches System sei zwar nicht tot, aber sie stehe auf wackligen Füßen, meint Decru, der jetzt an der Freien Universität Brüssel lehrt. Der Angriff des belgischen Forscherteams auf SIKE hat keine Auswirkungen auf die NIST-Kandidaten, die andere mathematische Ansätze verwenden.

Zwei davon beruhen auf gitterbasierten Problemen, bei denen man bestimmen muss, wie sich Teile des Gitters zueinander verhalten. SPHINCS+ basiert auf Hash-Funktionen, die eine Zahlenfolge in eine kürzere Zeichenfolge umwandeln – eine Art erkennbarer Fingerabdruck des Originals. Sie lassen sich einfacher berechnen als andere Verfahren, haben aber eine Schwäche: Hash-Funktionen sind nicht umkehrbar. Da sie nur in eine Richtung funktionieren, können sie Signaturen überprüfen, aber keine kryptografischen Schlüssel austauschen.

Sicherheit und Effizienz konkurrieren

Eine weitere Herausforderung für die Sicherung von Daten in der Quantenwelt ist, dass Sicherheit und Effizienz oft miteinander konkurrieren. Längere Schlüssel sind sicherer; sie zu erzeugen und zu übertragen, ist aber aufwändiger. »Die Industrie hat nichts von einem sehr sicheren Kryptosystem, das eine Stunde für einen einzigen Schlüsselaustausch benötigt«, sagt Castryck.

Und es gibt eine weitere Herausforderung: So genannte Seitenkanalangriffe (side-channel attacks) machen Verschlüsselungssysteme zusätzlich unsicher. Dabei sammelt ein Hacker Informationen, die nicht Teil des Schlüssels selbst sind, aber potenziell Hinweise darauf liefern. In der klassischen Datenverarbeitung könnte man beispielsweise aus der Übertragungsdauer einer Nachricht Rückschlüsse darauf ziehen, ob ein bestimmtes Bit einer Eins oder einer Null entspricht. Auch der Stromverbrauch kann je nach Struktur des kryptografischen Schlüssels variieren. Ein Angreifer kann solche Anhaltspunkte nutzen, um eine Verschlüsselung zu knacken.

Im August 2023 veröffentlichte der multinationale Technologieriese Intel einen Firmware-Korrektur für mehrere Chips, die seit 2015 verkauft wurden, nachdem der Google-Sicherheitsforscher Daniel Moghimi die von ihm als Downfall bezeichnete Sicherheitslücke entdeckt hatte. Durch Downfall ließ sich beobachten, wie die Chips Daten sammeln, die in ihrem Speicher verstreut sind. Ein Angreifer, der Zugriff auf den Chip hat, sendet Anfragen zur Verschlüsselung zufälliger Daten und speichert die messbaren Informationen. In diesen kann der Hacker nach Mustern suchen, mit denen sich die vom System genutzte Verschlüsselung überwinden lässt.

Obwohl solche Angriffe je nach Verfahren variieren, sind Post-Quanten-Algorithmen ebenfalls nicht davor gefeit, erklärt Peter Schwabe, Kryptograf am Max-Planck-Institut für Sicherheit und Datenschutz in Bochum. Er untersucht, wie sich kryptografische Methoden gegen Seitenkanalangriffe verteidigen lassen: »Ein Ziel dieses Projekts ist es, herauszufinden, wie wir die neuen Kryptosysteme systematisch gegen diese Art von Angriffen schützen können.«

Wird sich die Welt in der Quantensicherheit einig?

NIST ist nicht die einzige Institution, die an kryptografischen Standards arbeitet. Auch das deutsche Bundesamt für Sicherheit in der Informationstechnik gibt Empfehlungen für Post-Quanten-Systeme. Darunter sind zwei Standards, die es nicht in die Endauswahl des NIST geschafft haben. Der eine ist FrodoKEM, ein gitterbasiertes Schema. Der andere, Classic McEliece, verwendet schwer umkehrbare Fehlerkorrekturcodes. Beide gelten als sicherer als die NIST-Vorschläge, benötigen aber längere Schlüssel und sind daher langsamer in der Anwendung.

Andere Standardisierungsorganisationen werden sich wahrscheinlich ebenfalls einbringen. Die Internet Engineering Task Force zum Beispiel empfiehlt keine bestimmten Kryptografiestandards, wird aber ein Mitspracherecht bei den Protokollen haben, die diese Standards enthalten. Und zwischen 2018 und 2019 veranstaltete die Chinese Association for Cryptologic Research ihren eigenen Wettbewerb für neue Algorithmen. Die Einreichungen enthielten dieselben Familien mathematischer Probleme wie die NIST-Vorschläge. Der Gewinner basierte ebenfalls auf strukturierten Gittern.

Google prescht vor und schafft Fakten

Letztendlich wird es eine kleine Anzahl international vereinbarter Standards geben. »Schließlich müssen bei der Internetkommunikation beide Seiten die gleiche Kryptografie verwenden«, erklärt Schwabe. Und auch große internationale Unternehmen spielen bei der Auswahl eine Rolle. So kündigte Google im August 2023 an, Kyber in den Chrome-Browser einzubauen. »Wenn Google Kyber implementiert, muss jeder, der mit Google reden will, Kyber sprechen – egal, wo auf der Welt er sich befindet«, bekräftigt Schwabe.

»Ob es den Quantencomputer in 20, 30 oder 40 Jahren gibt, wissen wir nicht. Aber wir sollten jetzt keine Zeit verlieren«Thomas Decru, Kryptograf

Es wird einige Zeit dauern, die NIST-Standards zu implementieren und diese oder ähnliche Ansätze in Computersystemen auf der ganzen Welt zu verbreiten. In der Zwischenzeit werden Kryptografen weiterhin versuchen, Algorithmen zu entwickeln und die bereits vorhandenen zu knacken.

Aber die Gefahr, dass Daten jetzt gesammelt und später entschlüsselt werden könnten, macht das Thema dringend. Je eher die Welt die Post-Quanten-Kryptografie einführt, desto besser, meint Decru. »Ob es den Quantencomputer in 20, 30 oder 40 Jahren gibt, wissen wir nicht«, sagt er. »Aber wir sollten keine Zeit verlieren.«