Der Q-Day ist kein apokalyptisches Szenario, das sich Verschwörungstheoretiker ausgedacht haben. Selbst Fachleute sind überzeugt, dass er in den kommenden Jahren eintreten wird: der Tag, an dem Quantencomputer weit genug ausgereift sind, um aktuelle Verschlüsselungen zu knacken. Damit wären alle unsere Daten gefährdet.

Deshalb haben sich Forscherinnen und Forscher aus der Informatik und der Mathematik zusammengetan, um neue kryptografische Methoden auszuarbeiten, die selbst den leistungsfähigsten Quantencomputern standhalten sollen. Um herauszufinden, welcher Ansatz am vielversprechendsten ist, hat die US-amerikanische Behörde National Institute of Standards and Technology (kurz: NIST) 2016 eine weltweite Ausschreibung für so genannte Post-Quanten-Algorithmen getsartet, die Quantencomputern standhalten.

Ein Jahr später reichten zahlreiche Institute, Unternehmen und Einzelpersonen ihre Ideen ein, die von anderen Entwicklerinnen und Entwicklern geprüft wurden – sie versuchten die Verschlüsselungen auf allerlei Arten zu knacken. Nun hat das NIST mehrere Empfehlungen ausgesprochen und kryptografische Methoden auserkoren, auf die man in Zukunft setzen sollte: so genannte gitterbasierte Verfahren sowie hashbasierte Kryptografie sind die Gewinner der Ausschreibung.

Um zu verstehen, was es damit auf sich hat, sprechen wir mit der Mathematikerin und Informatik-Professorin Juliane Krämer von der Universität Regensburg. Sie leitet dort die Arbeitsgruppe zur Datensicherheit und Kryptografie.

»Spektrum.de«: Das NIST hat heute das kryptografische Verfahren bekannt gegeben, mit denen man sich vor möglichen Angriffen von Quantencomputern schützen möchte. Aber wie realistisch ist die Bedrohung eigentlich? Wird es den Q-Day tatsächlich geben?

Juliane Krämer: Ich sehe keinen Grund, warum es nicht irgendwann ausreichend große Quantencomputer geben sollte, die unsere jetzigen Verschlüsselungsmechanismen angreifen können. Ich denke daher, der Q-Day wird kommen.

Und wann könnte es so weit sein?

Das ist schwer zu beurteilen. Denn letztendlich kann man sich da nur auf Aussagen von Unternehmen, die Quantencomputer entwickeln, verlassen – und da ist sehr viel Marketing dabei. Es gibt viele Probleme, die noch zu lösen sind: Es geht nämlich nicht nur um die reine Anzahl der Qubits, sondern sie müssen auch stabil laufen. Dafür müsste es so genannte Fehlerkorrekturen geben, die sehr aufwändig sind. Ich schätze mal, dass es noch mindestens 20 Jahre dauern wird, bis der Q-Day eintritt.

Einige befürchten, dass Hacker jetzt schon Daten sammeln, um diese in Zukunft zu hacken. Halten Sie das für wahrscheinlich?

Ja, auf jeden Fall. Man muss sich nur überlegen, welche Daten in 20 oder 30 Jahren noch interessant sein könnten, etwa private Inhalte wie Whatsapp-Gespräche oder vielleicht Staatsgeheimnisse. Wenn man genug Speicherkapazität hat, kann man diese Daten jetzt schon abgreifen und später entschlüsseln, frei nach dem Motto: »harvest now, decrypt later«. Aus Sicht eines Geheimdienstes spricht nichts dagegen, das zu tun, da Speicherplatz billig geworden ist.

Haben Sie da Beispiele im Kopf?

Es gibt zum Beispiel in Utah ein sehr großes Datencenter, das die NSA betreibt. Man weiß nicht so genau, wie viel Speicherplatz da wirklich vorhanden ist – aber es ist auf jeden Fall sehr viel. Schätzungen belaufen sich auf etwa ein Gigabyte pro Person der Weltbevölkerung. Wenn man sich jetzt auf bestimmte Länder konzentriert, deren Daten man möchte, oder einzelne Menschen, dann ist das enorm viel Platz.

Könnte man die Verschlüsselungen womöglich jetzt schon knacken, wenn man einen heutigen Quantencomputer lange genug laufen lässt?

Nein. Denn die entscheidende Fähigkeit von Quantencomputern besteht darin, dass Qubits durch quantenmechanische Überlagerungen viele Operationen gleichzeitig ausführen. Für die aktuellen Schlüsselgrößen, die man knacken möchte, braucht man extrem viele Qubits. Deshalb kann man bisher nur sehr kleine Zahlen faktorisieren.

Wären mit Eintreten des Q-Day alle unsere aktuellen Verschlüsselungssysteme gefährdet?

Jein. Es gibt zwei unterschiedliche Arten der Kryptografie, die asymmetrische Public-Key-Kryptografie und die symmetrische Secret-Key-Kryptografie. Letztere ist die Art von Verschlüsselung, die man sich als Kind vorstellt, wenn man geheime Botschaften austauschen möchte: Zwei Parteien einigen sich auf einen geheimen Code und nutzen ihn sowohl zur Ver- als auch zur Entschlüsselung – deswegen symmetrisch.

Bei der Public-Key-Kryptografie verwendet man hingegen zwei unterschiedliche Schlüssel, wobei einer davon öffentlich einsehbar ist. Dafür müssen sie aber irgendwie zusammenhängen. Das erreicht man mit Hilfe einer mathematischen Basis, die beide verbindet, zum Beispiel zwei Primteiler einer Zahl. Die Public-Key-Kryptografie basiert also immer auf mathematischen Annahmen. Und die, die wir aktuell nutzen, kann ein Quantenalgorithmus, den Peter Shor 1994 veröffentlicht hat, knacken.

»Aus Sicht eines Geheimdienstes spricht nichts dagegen, Daten schon jetzt abzugreifen«

Und die symmetrische Kryptografie? Ist sie auch durch Shors Algorithmus bedroht?

Nein, aber es gibt einen anderen Quantenalgorithmus von Lov Grover. Er greift die symmetrische Kryptografie an, ist aber weniger mächtig: Er halbiert nur ungefähr die bisherige Bit-Sicherheit. Das heißt, man kann Quantenalgorithmen in diesem Fall begegnen, indem man die Schlüssellänge verdoppelt.

Das sind doch gute Nachrichten, oder?

Nicht ganz. Aktuell nutzt man die symmetrische Kryptografie immer in Verbindung mit Public-Key-Verfahren: Mit Letzterem lässt sich ein Schlüssel austauschen, über den man dann sicher kommunizieren kann. Wenn es nur eine symmetrische Kryptografie gäbe, müssten sich zwei Parteien irgendwie auf einen gemeinsamen geheimen Schlüssel einigen – etwa, indem man sich trifft. Das ist natürlich nicht umsetzbar.

Außerdem kann man mit symmetrischer Kryptografie nur verschlüsseln. Für viele Anwendungen braucht man aber so etwas wie digitale Signaturen. Zum Beispiel, wenn man ein Software-Update installiert. Dabei handelt es sich um einen Code, den der Hersteller bereitstellt und an die Geräte schickt. Man muss jedoch sicherstellen, dass die Software auf dem Übertragungsweg nicht verändert wurde. Dafür sorgen digitale Signaturen.

Wie funktioniert die Public-Key-Kryptografie?

Man braucht dafür ein mathematisches Problem, von dem man ausgeht, dass Computer es nur schwer lösen können. Das RSA-Verfahren basiert zum Beispiel auf der Faktorisierung großer Zahlen in ihre Primteiler – was für große Zahlen extrem schwierig ist. Ein anderes Verfahren ist die elliptische Kurvenkryptografie, die Operationen auf elliptischen Kurven berechnen. Während gewöhnliche Rechner an beiden Problemen scheitern, könnten Quantencomputer die Verfahren komplett brechen.

Was heißt »komplett brechen«?

Das bedeutet, Shors Algorithmus läuft in Polynomialzeit. Wenn der Schlüssel also größer wird, braucht das Programm zwar auch länger, aber eben nur vielleicht doppelt so lange – und nicht exponentiell viel mehr Zeit. Dementsprechend wird das Verfahren nicht sicherer, wenn man einfach nur die Schlüssellänge vergrößert, wie es aktuell der Fall ist.

»Theoretisch könnten andere Quantenalgorithmen die Post-Quanten-Verfahren brechen«

Gibt sonst noch andere Public-Key-Verfahren, die Quantencomputer nicht brechen könnten?

In der klassischen Kryptografie nicht. Deshalb forschen wir an so genannten Post-Quanten-Verfahren, die auch angesichts künftiger Quantencomputer sicher sind.

Ist bei diesen Ansätzen sichergestellt, dass Quantencomputer sie nicht knacken können? Oder kennt man bisher einfach keinen Code, der das kann?

Leider ist der Schutz nicht sichergestellt. Das ist einer der Kritikpunkte an unserer Forschung: Wir würden uns momentan zu sehr auf die Algorithmen von Shor und Grover konzentrieren. Theoretisch könnten andere Quantenalgorithmen die neuen Verfahren brechen. Fairerweise muss man aber sagen, dass bei RSA und elliptischen Kurven auch nicht klar ist, ob es nicht möglicherweise einen effizienten klassischen Algorithmus für herkömmliche Rechner gibt, der die Verfahren bricht.

Also muss man wohl hoffen, dass sich auch weiterhin keine Möglichkeit eröffnet, die neuen Verfahren anzugreifen. Welche Post-Quanten-Ansätze gibt es?

Weil es sich um Public-Key-Verfahren handelt, basieren alle auf mathematischen Problemen, die sich in fünf Kategorien teilen lassen. Am etabliertesten ist die Gitterkryptografie. Dann gibt es noch multivariante Verfahren, die Polynomen mit mehreren Unbekannten behandeln; codebasierte Kryptografie, die auf fehlerkorrigierenden Codes aufbaut; und hashbasierte Kryptografie, die mit der Nutzung so genannter Hashfunktionen zusammenhängt. Die letzte und jüngste Gruppe ist die Isogenien-Kryptografie, die auf Abbildungen zwischen elliptischen Kurven basiert.

Haben alle Verfahren das gleiche Potenzial?

Nein, die fünf Familien haben unterschiedliche Vor- und Nachteile. Zum Beispiel, wie gut sie studiert sind. An der gitterbasierten Kryptografie wurde schon sehr viel gearbeitet, sie ist ungefähr 20 Jahre alt. Wenn sich viele Menschen damit beschäftigen, steigt das Vertrauen, dass die Methode sicher ist. Die fünfte Gruppe wurde hingegen erst vor wenigen Jahren entwickelt. Dementsprechend ist das Vertrauen in die Isogenien noch nicht so groß.

Zudem lassen sich einige Ansätze, etwa die hashbasierten Funktionen, nicht für alle Anwendungsbereiche nutzen. Man kann zwar digitale Signaturen realisieren, aber keine Verschlüsselungen. Auch da haben gitterbasierte Verfahren einen Vorteil: Es scheint, als könnte man mit dieser Art der Kryptografie wirklich alle Funktionen umsetzen, die wir aktuell in IT-Systemen nutzen.

Nicht umsonst hat das NIST ein Empfehlung zu Gitterverfahren ausgesprochen. Gibt es ein einfaches Beispiel, um das zu Grunde liegende mathematische Problem zu beschreiben?

Ein Beispiel ist das »closest vector problem«. Ein Gitter besteht aus Kreuzungspunkten von Linien. Wenn man nun die Koordinaten eines zufälligen Punkts erhält, der nicht auf dem Gitter liegt, kann man versuchen, den nächstgelegenen Gitterpunkt zu ermitteln. In zwei oder drei Dimensionen ist die Aufgabe sehr einfach, doch wenn man etwa ein 512-dimensionales Gitter betrachtet, tun sich Computer sehr schwer mit der Aufgabe. Auch hier darf man aber – genauso wenig wie bei den anderen Post-Quantum-Ansätzen – nicht außer Acht lassen, dass sich die Idee effizient umsetzen lässt. Das heißt, die Signaturen, die Schlüsseltexte oder die Schlüssel sollten nicht zu groß werden.

Ist das entscheidend? Wir haben ja inzwischen große Bandbreiten und viel Speicherplatz.

Da kommt es stark auf die Anwendung an. Wenn man etwa Daten auf einer Festplatte verschlüsselt, um sie langfristig zu sichern, ist es egal, wenn es lange dauert. Vernetzte Geräte im IoT-Bereich haben aber manchmal nur kleine Speicher. Und auch wenn man an das autonome Fahren denkt, ist die Dauer der Prozesse entscheidend: Die Autos müssen schnell miteinander kommunizieren können.

Das NIST hat nun mehrere Gewinner gekürt. Wie wahrscheinlich ist es, dass die Empfehlung großflächig umgesetzt wird?

Ich gehe davon aus, dass die NIST-Standards sehr breit übernommen werden – zumindest in Nordamerika, Europa, Australien und in Teilen Asiens. Weil es auch chinesische Standardisierungsbemühungen gibt, würde ich China vielleicht ausklammern. Aber NIST ist eine Organisation, die über die Grenzen hinaus ernst genommen wird und der vertraut wird. Das deutsche Bundesamt für Sicherheit in der Informationstechnik (BSI) verfolgt deren Empfehlungen und übernimmt meist die Standards.

»Es scheint, als könnte man mit gitterbasierter Kryptografie alle Funktionen umsetzen, die wir aktuell in IT-Systemen nutzen«

Das NIST hatte ja bereits einen Wechsel auf elliptische Kurvenkryptografie empfohlen. Warum wurde RSA damals abgelöst?

Elliptische Kurvenkryptografie ist wesentlich effizienter. Doch dann kam die Bedrohung durch Quantencomputer. Unter anderem hat die NSA daher jenen geraten, die ihre Systeme noch nicht umgestellt hatten, auf den Post-Quanten-Standard zu warten. Das heißt, man hat zwar den Übergang von RSA zu elliptischen Kurven begonnen, aber er wurde nie ganz vollzogen.

Warum sollte man lieber auf Post-Quanten-Standards warten?

Der Übergang von einer Art der Kryptografie auf eine andere ist in der Regel sehr kompliziert. Möchte man Daten auf einer Festplatte verschlüsseln, kann man die Algorithmen einfach gegeneinander austauschen. Doch bei komplexeren Anwendungen muss man die neuen Verfahren effizient in alle möglichen Plattformen implementieren. Gerade für große IT-Infrastrukturen mit vielen Abhängigkeiten, wie es etwa bei Microsoft- oder Google-Produkten der Fall ist, wird die Aufgabe schwierig. Manche IT-Systeme wurden beispielsweise so programmiert, dass ein Schlüssel immer nur 2048 Bits beträgt, weil das bei RSA so ist – und niemand davon ausging, das irgendwann ändern zu müssen. Deshalb gab es die Empfehlung, den Wechsel auf elliptische Kurven zu überspringen und den Aufwand nur einmal zu betreiben.

»Ich kann mir nicht vorstellen, dass sich hybride Verfahren durchsetzen«

Wie motiviert sind Unternehmen, sich um neue kryptografische Methoden zu bemühen?

Wenn ich mit Firmen spreche, erlebe ich ein gewisses – teilweise sogar ein großes – Interesse. Doch alle sind sich einig, mit der Umsetzung zu warten, bis es NIST-Standards gibt. Das zeigt, wie ernst die Organisation genommen wird.

Häufig hört man, man könnte für die Übergangszeit die neuen Post-Quanten-Standards mit alten Verfahren verbinden.

Das hängt wieder einmal stark von der Anwendung ab. Prinzipiell ist das möglich. Es gibt hybride Ansätze, die ein klassisches mit einem Post-Quanten-Problem kombinieren, etwa die Primzahlfaktorisierung und ein Gitterverfahren. Gerade bei Hochsicherheitsanwendungen empfohlen und sogar gefordert, das zu tun, auch um die Post-Quanten-Kryptografie überhaupt schon mal in die Praxis zu bringen. Aber diese Methoden sind ziemlich ineffizient.

Müsste man später dann den Aufwand betreiben, von hybriden Systemen auf Post-Quanten-Verfahren umzustellen?

Ja, genau. Deshalb kann ich mir nicht vorstellen, dass sich hybride Verfahren durchsetzen. Es sei denn, man würde sehr effiziente hybride Lösungen finden, so dass man später gar nicht mehr umstellen müsste. Aber die Verfahren, die jetzt standardisiert werden, sind reine Post-Quanten-Verfahren.

Nun hat NIST einen Gewinner veröffentlicht. Wie lange wird es dauern, bis es erste Anwendungen findet?

Zuerst muss das NIST die konkreten Standards entwickeln. Bisher hat es nur bekannt gegeben, welche Verfahren es standardisieren will. Es muss aber noch ermitteln, wie bestimmte Dinge implementiert werden müssen, welche Parameter man einstellen muss und so weiter. Diese Informationen erwartet man erst 2023 oder 2024.

Und dann? Wie lange dauert es, bis Firmen das umsetzen können?

Es kommt natürlich auf die spezielle Anwendung an und wie viel sich die Unternehmen bereits mit dem Thema beschäftigt haben. Man kann jetzt schon einiges vorbereiten. Aber ich denke, man muss mit drei bis fünf Jahren Entwicklungsarbeit rechnen.

»Um Post-Quanten-Algorithmen wird man in Zukunft nicht herumkommen«

Das ist ganz schön lang.

Ja. Und wenn man sich zum Beispiel die Autoindustrie anschaut, erkennt man weitere Probleme. Fahrzeuge werden mehrere Jahre lang entwickelt, über längere Zeit gefahren und anschließend häufig in andere Länder exportiert, wo sie dann ebenfalls in Gebrauch sind. Wenn man davon ausgeht, dass ein Auto insgesamt vielleicht 25 Jahre auf den Straßen unterwegs ist und vorher 10 Jahre lang geplant wurde, macht das insgesamt 35 Jahre. Man müsste also jetzt schon Post-Quanten-Kryptografie einbauen – oder die Systeme flexibel genug gestalten, damit sich die Algorithmen ersetzen lassen. Das wird allerdings kaum gemacht.

Man liest immer wieder von Durchbrüchen im Bereich der Quantenkommunikation. Halten Sie es für möglich, dass Post-Quanten-Algorithmen übersprungen werden und man nur noch darauf setzt, über nicht hackbare Quantensysteme Schlüssel auszutauschen?

Nein, das wird meiner Meinung nach nicht passieren. In dem Bereich muss man wieder vorsichtig sein, weil viele Werbeversprechen dahinterstecken. Die Idee hinter den Quantentechnologien ist, über diesen sicheren Kanal einen Schlüssel auszutauschen, mit dem man dann über ein symmetrisches Verfahren kommuniziert. Zum Beispiel, wenn zwei Regierungen streng geheime Inhalte austauschen. Aber symmetrische Kryptografie allein reicht ja nicht für alle Anwendungen aus. Wir brauchen Public-Key-Verschlüsselungen, zum Beispiel für digitale Signaturen. Viele Kryptografen nehmen die Quantentechnologien in dem Bereich daher gar nicht richtig ernst. Es ist sicherlich technologisch interessant und findet vielleicht auch einzelne Anwendungen, aber eben nicht großflächig. Um Post-Quanten-Algorithmen wird man in Zukunft nicht herumkommen.