Artikel kostenlos lesen

Post-Quanten-Kryptografie

Die Entwicklung eines generischen Quantencomputers bedroht die Sicherheit heute gängiger kryptografischer Algorithmen und Protokolle. Die Post-Quanten-Kryptografie widmet sich daher der Entwicklung und Evaluierung von Algorithmen, die auch Angreifern mit Zugang zu Quantencomputern standhalten. Bevor diese neuen Algorithmen Verwendung in Protokollen und IT-Lösungen finden können, sind allerdings noch zahlreiche Herausforderungen zu bewältigen.

Lesezeit 13 Min.

Von Leonie Bruckert, Dresden, und Jörn-Marc Schmidt, Eschborn

Die heute üblichen symmetrischen wie asymmetrischen Krypto-Algorithmen sowie die ihnen zugrunde liegenden mathematischen Probleme haben Informatiker und Mathematiker seit Jahren untersucht – hier sind mit vorliegender Technik keine signifikanten Durchbrüche zu erwarten, welche die Sicherheit gefährden. Durch die Verwendung von Quantencomputern eröffnen sich jedoch neue Möglichkeiten für die Kryptoanalyse.

Die Auswirkungen von Angriffen mit Quantenrechnern unterscheiden sich zwischen symmetrischen und asymmetrischen Algorithmen grundlegend: Der 1996 vorgestellte Quantenalgorithmus von Grover [9] schwächt symmetrische Algorithmen durch eine beschleunigte Schlüsselsuche. Im besten Fall für den Angreifer kann der seinen benötigten Aufwand halbieren. Diese Bedrohung lässt sich daher relativ einfach durch eine Verdopplung der Schlüssellängen abwenden – statt der derzeit empfohlenen 128 Bit also dann 256 Bit.

Asymmetrische Algorithmen, die auf der Faktorisierung oder dem diskreten Logarithmus basieren, können mit dem Quantenalgorithmus von Shor [8] von 1994 angegriffen werden. Dies ist ein weitaus mächtigeres Werkzeug für den Angreifer, da der Aufwand eines Angriffs damit nur noch polynomiell mit der Schlüssellänge wächst – statt wie zuvor sub-exponentiell. Sprich: Bei verbreiteten Verfahren wie RSA würde auch eine signifikante Vergrößerung der heute empfohlenen Schlüssellänge von 3072 Bit kaum etwas bewirken. Viele asymmetrische Algorithmen wären grundsätzlich nicht mehr sicher, falls entsprechende Quantencomputer verfügbar werden, weil damit die zugrunde liegenden mathematischen Probleme plötzlich „einfach“ lösbar werden.

Qubits & Co.

Warum Quantenrechner grundlegend neue Möglichkeiten eröffnen, lässt sich erahnen, wenn man ihre Funktionsweise mit bisherigen Computern vergleicht: Bei konventionellen Rechnern kann die elementare Informationseinheit – das Bit – den Wert 0 oder den Wert 1 annehmen. Im Unterschied dazu kann ein Quantenbit (Qubit) die Werte 0 und 1 zugleich in Form einer gewichteten Kombination darstellen (z. B. 40 % 0 und 60 % 1) – diese Eigenschaft wird als Superposition bezeichnet.

Die Messung eines Qubits zerstört allerdings den Zustand der Superposition und lässt das System auf einen der repräsentierten Werte „zusammenfallen“. Das Ergebnis der Messung hängt vom Zustand des Quantenbits ab – beim Beispiel einer Superposition von 40 % „0“ und 60 % „1“ würde die Messung also in 6 von 10 Fällen „1“ ergeben und sonst „0“ – weitere Messungen würden an dem einmal erfassten Wert nichts mehr ändern. Es ist also nicht möglich zu messen, wie hoch die Wahrscheinlichkeit für ein bestimmtes Ergebnis ist.

Um mehr als ein Qubit zu nutzen, machen sich Quantencomputer das quantenmechanische Phänomen der Verschränkung zunutze: Der Zustand verschränkter Qubits kann nur als ein gesamtes System beschrieben werden, nicht getrennt für die einzelnen Komponenten. In der Folge hat die Messung eines verschränkten Qubits Auswirkungen auf das gesamte System – und zwar unabhängig von der räumlichen Entfernung der Qubits. Dieses Prinzip ist beispielsweise auch die Grundlage für die Quantenkryptografie (siehe etwa [1]).

Mit verschränkten Qubits können aber auch Quantenregister gebildet werden und so einen größeren Werteraum repräsentieren. Beispielsweise können zwei Qubits die Werte 00, 01, 10 und 11 in gewichteter Kombination enthalten. Mit n Qubits kann ein Raum mit 2^n Werten erzeugt werden, wobei die Auftrittswahrscheinlichkeit der Werte von den jeweiligen Gewichten definiert wird.

Superposition und Verschränkung ermöglichen demnach eine Art paralleles Rechnen – mit der Einschränkung, dass Messungen ein zufälliges Ergebnis liefern. Durch gezielte Operationen mit Quantengattern auf den Qubits lässt sich die Wahrscheinlichkeit für das Auftreten bestimmter Messergebnisse steuern. Ziel eines Quantenalgorithmus ist es, dass am Ende der Berechnung mit hoher Wahrscheinlichkeit das korrekte Ergebnis gemessen wird.

Da Superposition und Verschränkung sehr fragil sind, sind Rechnungen auf Qubits meist mit Fehlern behaftet. Um stabile Rechnungen sicherzustellen, benötigt man Mechanismen zur Fehlerkorrektur. Dazu werden Hunderte fehlerhafter, physikalischer Qubits zu einem logischen Qubit zusammengefügt, auf dem dann schließlich fehlerfreie Rechnungen möglich sind.

Bauarten von Quantencomputern

Wissenschaftler verfolgen beim Bau von Quantencomputern verschiedene Ansätze: Beispielsweise werden bei der sogenannten Ionenfalle einige Ionen mithilfe von elektromagnetischen Feldern eingesperrt und heruntergekühlt – durch gezielte Laserstrahlen lassen sich diese Ionen dann verschränken und manipulieren. Einen weiteren vielversprechenden Ansatz stellen supraleitende Qubits dar (Supraleiter sind Materialien, deren elektrischer Widerstand beim Unterschreiten einer gewissen kritischen Temperatur auf null fällt).

Ein Qubit kann man ebenfalls auf verschiedenen Wegen realisieren, etwa durch zwei verschiedene Energieniveaus oder den Spin eines Atoms oder Ions. Generell besteht die Schwierigkeit darin, einen stabilen, fehlertoleranten Ansatz zu finden, der sich auf tausende Qubits hochskalieren lässt. In den Laboren entstehen bereits die ersten kleinen Prototypen, die aber noch zu skalierbaren, fehlertoleranten und vor allem praxistauglichen Quantencomputern ausgebaut werden müssen – dies sei jedoch in erster Linie „Ingenieursarbeit“, meinen einige Fachleute [2].

Erwartete Zeitschiene

Von zukünftigen Quantencomputern erwartet man beträchtliche Vorteile bei der Entwicklung neuer Materialien und Medikamente sowie Fortschritte bei der Lösung von Optimierungsproblemen. Die Kryptoanalyse zählt ebenfalls zu den vielversprechenden Anwendungsgebieten. Allerdings ist davon auszugehen, dass zum Brechen aktuell eingesetzter Kryptoalgorithmen tausende logische Qubits und somit mehrere Millionen physikalische Qubits erforderlich sind. Mit Blick auf den aktuellen Forschungsstand scheint ein solch mächtiger Quantencomputer noch in weiter Ferne, denn derzeit sind nur Quantencomputer mit wenigen Qubits verfügbar (vgl. Abb. 1). Zwar bestehen die von D-Wave entwickelten Rechner aus bis zu 2000 Qubits, diese Systeme gehören jedoch einer speziellen Klasse von Quantencomputern, den sogenannten „Quantum Annealers“, an. Da diese sich nur zur Lösung bestimmter Probleme (beispielsweise aus der Optimierung) eignen, liefern sie keine Fortschritte bei der Kryptoanalyse.

Wann es hinreichend große Quantencomputer geben wird, ist heute nicht absehbar. Typische Schätzungen umfassen einen Zeitraum von 10–20 Jahren. Michele Mosca, Mitbegründer des Instituts für Quantum Computing an der Universität Waterloo (Kanada), schätzte 2015 die Wahrscheinlichkeit, dass RSA-2048 bis 2026 gebrochen wird, auf rund 14 % und bis 2031 auf 50 % [3]. Die US-amerikanische Standardisierungsbehörde NIST nimmt an, dass man 2030 mit einem Investment von einer Milliarde Dollar einen Quantencomputer bauen kann, der RSA mit 2048-Bit-Schlüsseln innerhalb von Stunden brechen kann [4].

Abbildung 1

Abbildung 1: Meilensteine der Entwicklung von Quantencomputern

Auswirkungen auf die Sicherheit

Wie bereits erwähnt, können Quantencomputer mithilfe von Shors Algorithmus Probleme wie die Faktorisierung oder den diskreten Logarithmus lösen. Mit dem Erscheinen entsprechend großer Quantencomputer wären heute übliche asymmetrische Algorithmen wie RSA, Diffie-Hellman und die Kryptografie der elliptischen Kurven (ECC) gebrochen. In der Folge wären somit auch sämtliche Protokolle, Software und Hardwaremodule angreifbar, welche die betroffenen Algorithmen einsetzen.

Um die Auswirkungen zu beurteilen, gilt es das Szenario zu betrachten, in dem diese Protokolle eingesetzt werden: Bei einer Authentisierung, beispielsweise in einem Online-Shop, muss der Prozess an sich sicher gestaltet werden. Erfolgt hier eine Migration auf Post-Quanten-Algorithmen rechtzeitig vor der Entwicklung des ersten Quantencomputers entsprechender Größe, ist dies ausreichend. Sobald solche Dienste rechtzeitig auf neue Verfahren wechseln und ihr Schlüsselmaterial rechtzeitig verlässlich austauschen, können sie der „Bedrohung“ durch Quantencomputer also gelassen entgegensehen. Eine rückwirkende Manipulation wäre für das Authentisierungsprotokoll bedeutungslos.

Im Kontrast dazu stehen jedoch Daten, die längerfristig schützenswert sind. Allem voran staatliche und militärische Dokumente, die heute verschlüsselt werden, müssen unter Umständen auch noch in etlichen Jahren vertraulich bleiben. Heutige Algorithmen können dies jedoch nicht sicherstellen: Verschlüsselte Daten könnten beispielsweise heute in einer Kommunikation mitgelesen und (viel) später entschlüsselt werden.

Für solche Fälle besteht daher schon jetzt akuter Handlungsbedarf! So rät beispielsweise eine Veröffentlichung der NSA dazu, fortan keinen Aufwand mehr in den Umstieg auf Verfahren zu investieren, die elliptische Kurven nutzen. Falls die Migration noch nicht erfolgt ist, solle man vielmehr auf Empfehlungen für zukünftige Post-Quanten-Algorithmen warten [5].

Post-Quanten-Kryptografie

Als Alternative zu heute eingesetzten asymmetrischen Kryptoalgorithmen für die Zeit der Quantencomputer fokussieren sich Wissenschaftler auf die Entwicklung von Verfahren, die auf anderen mathematischen Problemen beruhen – von denen man annimmt, dass sie selbst mit Quantencomputern nicht in angemessener Zeit lösbar sein werden.

Dieses Forschungsgebiet wird als Post-Quanten-Kryptografie bezeichnet und lässt sich in fünf Teilgebiete unterteilen: Jedes Gebiet verfolgt verschiedene Ansätze und dient zum Teil auch unterschiedlichen kryptografischen Zwecken. Ein bedeutender Nachteil der meisten quantencomputerresistenten Algorithmen liegt dabei in sehr großen Schlüsseln und/oder Signaturen.

Codebasierte Kryptografie

Die codebasierte Kryptografie ist der älteste Zweig der Post-Quanten-Kryptografie, der auf eine Arbeit von Robert McEliece von 1978 zurückgeht [15]. Hier macht man sich die Tatsache zunutze, dass es für einige spezielle lineare Codes effiziente Fehlerkorrekturalgorithmen gibt, während das Dekodieren von fehlerbehafteten Codes im allgemeinen Fall praktisch nicht lösbar ist. Die grundlegende Idee besteht darin, eine Nachricht als Codewort darzustellen und mit einem gewissen Fehler zu versehen. Somit wird das Entschlüsseln der Nachricht zu einer praktisch unmöglichen Aufgabe, sofern der Empfänger den Fehlerkorrekturalgorithmus nicht kennt, der nunmehr dem geheimen Schlüssel entspricht.

Hashbasierte Kryptografie

Die hashbasierte Kryptografie liefert ausschließlich Signatursysteme, deren Sicherheit auf der Kollisionsresistenz der verwendeten Hashfunktion basiert (s. S. 60). Eine Hashfunktion besitzt die Eigenschaft der Kollisionsresistenz, wenn es nahezu unmöglich ist, zwei Eingaben zu finden, die den gleichen Hashwert haben. Da Hashfunktionen gründlich untersuchte „kryptografische Primitive“ sind, zählt die hashbasierte Kryptografie zu den vertrauenswürdigsten Teilgebieten der Post-Quanten-Kryptografie.

Multivariate Kryptografie

Das Lösen von multivariaten quadratischen Gleichungen (quadratische Gleichungen in mehreren Variablen) ist im Allgemeinen ein hartes Problem und vermutlich weder mit klassischen noch mit Quantenrechnern effizient lösbar. Damit bildet das sogenannte MQ-Problem eine ideale Grundlage für quantencomputerresistente Kryptosysteme. Für kryptografische Zwecke wird ein solches Gleichungssystem gezielt konstruiert und mit einer Hintertür versehen, sodass es sich mithilfe einer zusätzlichen (geheimen) Information einfach lösen lässt – das entspricht der Entschlüsselung eines Geheimtexts mithilfe des Private Keys asymmetrischer Verfahren.

Gitterbasierte Kryptografie

Die Sicherheit gitterbasierter Kryptoalgorithmen stützt sich auf die Härte sogenannter Gitterprobleme. Dazu zählen beispielsweise das Shortest-Vector-Problem (SVP), bei dem der kürzeste Vektor in einem mehrdimensionalen Gitter gesucht wird, und das Closest-Vector-Problem (CVP), bei dem man nach dem zu einem Zielpunkt nächstgelegenen Gitterpunkt sucht. Aktuell sind weder klassische noch Quantenalgorithmen zur Lösung dieser und weiterer Gitterprobleme bekannt.

Isogeniebasierte Kryptografie

Die isogeniebasierte Kryptografie ist das jüngste Teilgebiet der Post-Quanten-Kryptografie. Im Fokus steht hier besonders eine Variante des Diffie-Hellman-Schlüsselaustauschs, die auf Isogenien (strukturerhaltenden Abbildungen) zwischen elliptischen Kurven basiert.

DH-Ersatz in der Praxis

Durch den testweisen Einsatz im Google-Browser Chrome ist der gitterbasierter Schlüsselaustausch NewHope [6] auch außerhalb der kryptografischen Gemeinschaft bekannt geworden. Allerdings haben bei NewHope die auszutauschenden Nachrichten im Vergleich zum klassischen Diffie-Hellman-Schlüsselaustausch (DHKE) etwa die fünffache Größe. Eine codebasierte Alternative zum DHKE namens CAKE [7] („Code-based Algorithm for Key Encapsulation“) schneidet mit mehr als 20-mal so großen Nachrichten bei einer Sicherheit von 128 Bit gegen Quantencomputer noch wesentlich schlechter ab.

BSI-Empfehlungen für langfristig schützenswerte Informationen

Um ein gewisses Maß an Quantencomputer-Sicherheit zu erreichen, können asymmetrische Verfahren durch die Verwendung zusätzlicher symmetrischer Verfahren (unter Verwendung symmetrischer Langzeitschlüssel) verstärkt werden. Folgende Möglichkeiten hierzu bieten sich beispielhaft etwa an:

  • Üblicherweise wird asymmetrische Kryptografie lediglich benötigt, um ein gemeinsames Geheimnis zwischen den Kommunikationspartnern auszutauschen, aus dem dann symmetrische Sitzungsschlüssel abgeleitet werden. Dabei ist es möglich, in die Schlüsselableitungsfunktion ein kryptografisches Langzeitgeheimnis eingehen zu lassen. Ein Angreifer, der das dem asymmetrischen Verfahren zugrunde liegende mathematische Problem effizient lösen kann, scheitert in diesem Fall an der korrekten Ableitung der Sitzungsschlüssel, solange er den durch die Schlüsselableitung genutzten symmetrischen Schlüssel nicht kennt.
  • Ebenso ist es möglich, einen asymmetrischen Schlüsseltausch mithilfe eines vorverteilten Geheimnisses symmetrisch zu verschlüsseln. In diesem Fall muss jeweils natürlich das Problem der Verteilung der erwähnten Langzeitschlüssel gelöst werden.

Eine weitere Möglichkeit, künftige Angriffe durch Quantencomputer abzuwehren, besteht natürlich in der Anwendung asymmetrischer kryptografischer Verfahren, für die Resistenz gegen Quantencomputer-Angriffe angenommen wird. Die vorliegende Richtlinie (BSI TR-02102-1, Februar 2017 [16]) enthält keine Empfehlungen zu quantencomputerresistenten Verschlüsselungsverfahren, da zumindest innerhalb des Vorhersagezeitraums dieser technischen Richtlinie nicht mit einer Anwendung von Quantencomputern auf die empfohlenen Verfahren gerechnet wird.

Auf lange Sicht ist eine Prognose schwierig, weil verschiedene technologische Grundlagenfragen derzeit noch offen sind. Umgekehrt ist zudem die Wahl der Sicherheitsparameter für die in dieser Richtlinie empfohlenen Verfahren unter der Annahme rein klassischer Attacken durch die Forschung deutlich besser geklärt als es für quantencomputerresistente Verfahren derzeit der Fall ist.

Die Verwendung hybrider Verfahren, die also eine klassische und eine quantencomputerresistente PublicKey-Verschlüsselungsmethode geeignet miteinander kombinieren, eröffnet prinzipiell einen Weg, die Sicherheitsgarantien bewährter klassischer Verfahren gegen klassische Kryptoanalyse mit den Vorteilen quantencomputerresistenter Verfahren zu verbinden. Für die Auswahl und Implementierung geeigneter Post-Quanten-Verfahren sowie eine geeignete Kombination mit klassischen Verfahren und für die Festlegung geeigneter Schlüssellängen sollte unbedingt ein Experte herangezogen werden.

Erwägungen zur langfristigen Stabilität von Sicherheitseigenschaften sind in erster Linie für Verschlüsselungsverfahren relevant, weil für Signaturen zumindest technisch die Möglichkeit einer Übersignatur besteht. Bei der Planung des Einsatzes von Signaturverfahren in kryptografischen Infrastrukturen sollte entsprechend sichergestellt werden, dass eine flächendeckende Durchführung von Übersignaturen (und die flächendeckende Durchführung der notwendigen Schritte bei der Prüfung solcher übersignierter Dokumente) auch tatsächlich möglich sein wird, falls einmal ein kryptografisches Verfahren ausgetauscht werden muss.

Auszug aus Abschnitt 3.1.2 der technischen Richtlinie zu Empfehlungen und Schlüssellängen für kryptografische Verfahren [16] – Abdruck mit freundlicher Genehmigung des BSI.

Herausforderungen

Im Vergleich zur konventionellen Kryptografie ist die Post-Quanten-Kryptografie ein relativ junges Forschungsgebiet. Das Vertrauen in die heutzutage eingesetzten asymmetrischen Kryptoalgorithmen, die auf der Faktorisierung oder dem diskreten Logarithmus basieren, ist über Jahrzehnte gewachsen. Zwar beruht auch deren Sicherheit auf der Annahme, dass keine effizienten Algorithmen zur Lösung dieser Probleme existieren – und einen Beweis hierfür gibt es nicht. Doch RSA, Diffie-Hellman & Co. haben sich bewährt und jahrzehntelang allen Versuchen der Kryptoanalyse standgehalten. Unwesentlich bessere Angriffe und die kontinuierliche Steigerung der verfügbaren Rechenleistung haben lediglich eine Anpassung der Parameter erforderlich gemacht.

Dem gegenüber stehen nun neue Kryptoalgorithmen, die auf anderen mathematischen Problemen basieren, die zum Teil selbst relativ jung und vergleichsweise wenig erforscht sind. Beispielsweise stützen sich viele gitterbasierte Verfahren (darunter der Schlüsselaustausch NewHope) auf das „Learning-with-Errors-over-Rings“- (RLWE)-Problem, das erst 2012 überhaupt definiert wurde.

Ähnliches gilt für andere Teilgebiete der Post-Quanten-Kryptografie: Viele Versuche, die codebasierten Verfahren durch die Verwendung anderer Codes praktikabler zu machen, sind gescheitert. Dies zeigt, dass auch hier noch intensive Forschung nötig ist, und weckt zudem Bedenken, dass möglicherweise einige der kürzlich vorgeschlagenen Algorithmen nicht die versprochene Sicherheit bieten könnten.

Eine ausführliche Prüfung und Bewertung quantencomputerresistenter Kryptoalgorithmen soll ein Auswahlprozess des US-amerikanischen National Institute of Standards and Technology (NIST) sicherstellen. Im Dezember 2016 hat das NIST einen Aufruf an die internationale wissenschaftliche Gemeinschaft gerichtet, quantencomputerresistente Kryptoalgorithmen bis Ende November 2017 einzureichen – nach mehrjähriger Evaluierung sollen voraussichtlich 2025 geeignete Verfahren standardisiert werden.

Darüber hinaus stehen zwei hashbasierte Signaturverfahren bereits kurz vor der internationalen Standardisierung als Request for Comments (RFC) der Internet Engineering Task Force (IETF) – der Beitrag ab Seite 60 geht hierauf detaillierter ein. Auch das European Telecommunications Standards Institute (ETSI) zeigt mit der Gründung einer Arbeitsgruppe großes Engagement im Bereich Post-Quanten-Kryptografie. Auf nationaler Ebene setzt sich das Bundesamt für Sicherheit in der Informationstechnik (BSI) umfassend mit der Thematik auseinander.

Fazit

Ein ausschließlicher Einsatz von quantencomputerresistenten Verfahren ist aus verschiedenen Gründen (Sicherheit, Praktikabilität etc.) zum jetzigen Zeitpunkt nicht zu empfehlen. Da besonders sensible Daten mit hohem Schutzbedarf jedoch heute schon in Gefahr sein können, empfiehlt das BSI beispielsweise den Einsatz von hybriden Verfahren (vgl. Kasten auf S. 57) – wobei „hybrid“ in diesem Kontext die Kombination von konventionellen und quantencomputerresistenten Kryptoalgorithmen bezeichnet.

Es sollte bedacht werden, dass die Migration zu quantencomputerresistenten Kryptoalgorithmen mehrere Jahre beanspruchen kann. Dies schließt eine sorgfältige Evaluierung neuer Kryptoalgorithmen und die Erstellung neuer beziehungsweise die Anpassung vorhandener Standards sowie Implementierungen in Soft- und Hardware ein. Eine besondere Herausforderung stellen dabei die oftmals sehr großen Schlüssel und Signaturen der quantencomputerresistenten Verfahren dar. Von daher sind eine frühzeitige Auseinandersetzung mit der Thematik und vorausschauendes Handeln entscheidend für langfristige Sicherheit.

Leonie Bruckert ist Beraterin, Dr. Jörn-Marc Schmidt Senior Berater bei der secunet Security Networks AG.

Diesen Beitrag teilen: