© Maksim_Kabakou / 123RF.com

Viele heute eingesetzte Sicherheitsmechanismen können in absehbarer Zeit Angriffen mit Quantencomputern nichts mehr entgegensetzen. Deshalb wird schon heute an einer Post-Quantum-Kryptographie geforscht.

Die Entwicklung des Internets ist kaum mit grauer Theorie vereinbar. Oft schaffen große Firmen wie Google bereits Fakten, bevor in den entsprechenden Standardisierungsgremien ein Konsens gefunden wird. Umgekehrt kämpfen manche Änderungen mit Abhängigkeiten von Altlasten, um etwa die Abwärtskompatibilität zu wahren. So kommt es, dass sich das Internet-Protokoll in der Version 6 (IPv6) erst jetzt durchzusetzen beginnt, obwohl es ursprünglich Probleme der 1990er-Jahre lösen sollte. Vieles hat sich seitdem grundlegend gewandelt, auch die ausgetauschte Datenmenge hat sich vervielfacht. Um in diesem Tohuwabohu sicher kommunizieren zu können, schützen unterschiedliche Protokolle den Datenverkehr.

Verschlüsselung schützt

Manche dienen dem Aufbau von Virtual Private Networks (VPNs), etablieren also virtuelle, geschützte Datenkanäle, die entfernte Kommunikationspartner verbinden. Das Ziel: Ein Beobachter oder Angreifer mag zwar die übertragenen Daten einsehen können, doch verschlüsselt bleiben sie für ihn nutzlos. Andere Protokolle ermöglichen es zu überprüfen, ob ein Update unverändert ist und wirklich vom Hersteller stammt.

Die Sicherheit in solchen Szenarien gewährleisten kryptografische Verfahren, die sowohl Daten verschlüsseln als auch die Kommunikationspartner authentifizieren und die versendeten Daten signieren. In der Praxis sichert man einen Tunnel mit schnellen symmetrischen Verschlüsselungsverfahren wie dem Advanced Encryption Standard (AES). Doch dafür muss auf beiden Seiten ein gemeinsamer Schlüssel oder ein Passwort vorliegen. Wer diese nicht vorab persönlich aushändigen will (was aufwendig wäre), der benutzt zusätzlich vergleichsweise langsame asymmetrische Verfahren. Sie ermöglichen es, Schlüsselmaterial sicher auszutauschen. Wenn Kommunikation eher selten stattfindet, wie etwa beim Versenden von Software-Updates, dienen meist ausschließlich asymmetrische Verfahren zum Signieren der Daten.

In der Praxis haben sich nur wenige als sicher geltende Verfahren verbreitet. Selbst mit heutigen Supercomputern wäre der Aufwand zu hoch, um sie zu brechen, sofern man sie korrekt und mit ausreichend langen Schlüsseln verwendet. Quantencomputer dagegen erlauben aufgrund ihres andersartigen Rechenmodells effizientere Angriffe.

Abbildung 1 zeigt links ein klassisches Bit mit den beiden Zuständen Null oder Eins. Ein Quantenbit oder kurz Qubit (rechts, dargestellt durch eine Bloch-Kugel) kann in einer sogenannten Superposition auch etwas dazwischen darstellen, etwa mit 65 Prozent Wahrscheinlichkeit eine Eins und zu 35 Prozent Wahrscheinlichkeit eine Null. Verschränkt man mehrere Qubits, sodass sie sich gegenseitig beeinflussen, können verschiedene Ergebnisse mit jeweils einer bestimmten Wahrscheinlichkeit vorkommen. Für manche mathematischen Aufgaben lässt sich so mithilfe eines Quantencomputers schneller eine Lösung finden.

Abbildung 1: Klassische Bits (links) versus Quantenbits (rechts).

Angriff der Quantencomputer

Der effizienteste generische Angriff von Quantencomputern auf symmetrische Verfahren ist der von Lov Grover 1996 vorgestellte und nach ihm benannte Grover-Algorithmus. Er beschleunigt das stupide Prüfen aller möglichen Schlüssel, den sogenannten Brute-Force-Angriff. Klassisch besagt die Wahrscheinlichkeitsrechnung, dass man im Schnitt die Hälfte aller möglichen Schlüssel testen muss. Der Grover-Algorithmus benötigt jedoch selbst im schlechtesten Fall nicht mehr Tests als die Quadratwurzel aus der Anzahl aller Möglichkeiten.

Dadurch halbiert sich die sogenannte Bit-Sicherheit: 128-Bit-Schlüssel bieten in einem Quantenkontext lediglich das Sicherheitsniveau von 64 Bit. Verdoppelt man die Schlüssellänge, so erreicht man wieder das ursprüngliche Sicherheitsniveau – unschön, aber technisch nicht schwer umzusetzen. Für die Praxis bedeutet das, dass überall dort, wo etwa AES-128 zum Einsatz kommt, ein Upgrade auf AES-256 beziehungsweise bei Hash-Verfahren von SHA-256 auf SHA-512 ansteht.

Die Sicherheit asymmetrischer Verfahren dagegen beruht auf komplexen mathematischen Problemen wie der Faktorisierung großer Zahlen oder dem Finden von diskreten Logarithmen. Bei ausreichend großen Zahlen lässt sich das mithilfe klassischer Computer praktisch nicht lösen, eine gegebene Lösung ist aber relativ effizient überprüfbar (siehe Kasten “Primfaktoren”). Für die beiden genannten Probleme bietet der von Peter Shor im Jahr 1997 vorgestellte und nach ihm benannte Shor-Algorithmus auf einem Quantencomputer eine exponentielle Beschleunigung. Das ermöglicht das Berechnen von Schlüsseln mit faktisch beliebiger Länge in praktikabler Zeit und macht alle verbreiteten asymmetrischen Algorithmen wie RSA, Diffie-Hellman (DH), DSA und Varianten der beiden Letzteren auf Basis elliptischer Kurven (ECDH, ECDSA) angreifbar.

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Neueste Schätzungen gehen davon aus, dass es rund 20 Millionen sogenannter Qubits bedarf, um einen RSA-Schlüssel der Größe 2048 Bit zu brechen. Die momentan leistungsfähigsten Quantencomputer arbeiten mit etwa 70 Qubits, und selbst optimistische Schätzungen erwarten höchstens 1000 Qubits innerhalb der nächsten drei bis fünf Jahre. Quantencomputer arbeiten also derzeit noch nicht annähernd leistungsfähig genug, um aktuelle Verschlüsselungsalgorithmen zu brechen. Es ist unklar, ob und wann es einen kryptografisch relevanten Quantencomputer geben könnte.

Sollte sich jedoch die in den letzten Jahren beobachtete Geschwindigkeit bei der Entwicklung von Quantencomputern weiter fortsetzen, besteht eine realistische und große Gefahr für die sichere Kommunikation. Einige staatliche Nachrichtendienste speichern bereits heute Unmengen an unverschlüsselten wie verschlüsselten Daten und könnten Letztere entziffern, sobald es Fortschritte in der Kryptanalyse gibt (bessere Angriffe oder das Bekanntwerden von Programmier- beziehungsweise Anwendungsfehlern) oder sobald ausreichend gute Quantencomputern zur Verfügung stehen. Dann trüge das Konzept “store now, decrypt later” Früchte.

Deshalb benötigt man schon heute andere mathematische Probleme, bei denen weder klassische noch auf Quantencomputern basierende effiziente Angriffe greifen (siehe Kasten “Quantenresistente Alternativen”). Einer breiten Anwendung solcher exotischer neuer Verfahren stehen bislang noch mangelnde Erfahrung und entsprechend geringes Vertrauen entgegen. Außerdem arbeiten die Verfahren oft langsamer als die heute genutzten Äquivalente oder benötigen größere Datenmengen als Schlüsselmaterial.

Abbildung 2: Mehrdimensionale Gitter können als Ausgangspunkt quantenresistenter Verschlüsselungsverfahren dienen.

Noch mehr Probleme

Doch selbst wenn man solche quantenresistenten Alternativen gefunden hat, gilt es, noch andere Probleme zu lösen. Heutige Sicherheitsprotokolle sind meist für ein bestimmtes Verfahren optimiert, zum Beispiel einen bestimmten Schlüsselaustausch wie den sogenannten Diffie-Hellman-Schlüsselaustausch. Es war nie vorgesehen, dieses Verfahren auszutauschen; das Protokoll wurde daher auch nicht entsprechend modular gestaltet. Die Optimierungen steigern einerseits die Effizienz der Kommunikation und schließen andererseits auch einige Angriffe implizit aus.

Möchte man diese Protokolle um zusätzliche quantenresistente Alternativen erweitern, steht man meist vor dem Problem, dass das resultierende Protokoll nur bedingt kompatibel zur klassischen Variante ist. Zusätzlich soll die Nutzung verschiedener Verfahren hybrid erfolgen: Man nutzt idealerweise also mehrere der Verfahren parallel, sodass die Sicherheit des Gesamtsystems auf allen genutzten Verfahren beruht. Dadurch verteilt sich das Risiko, wenn eines der Verfahren klassisch oder durch Quantencomputer gebrochen wird. Man spricht in diesem Kontext von Kryptoagilität. Das umfasst den einfachen Austausch von Verfahren, eine einfache Möglichkeit, auf Sicherheitsvorfälle reagieren zu können, sowie die entsprechende Abmilderung von Vorfällen etwa durch hybrides Nutzen mehrerer Verfahren.

Im Zug von Software-Updates erscheint das relativ einfach umzusetzen. Man modifiziert dazu den Update-Mechanismus derart, dass er neben einer klassischen Signatur auch mindestens eine zweite, quantenresistente Signatur prüft. Der Overhead beschränkt sich dann auf die zusätzlichen Signaturen und Verifikationszeiten. In den meisten Update-Szenarien ließe sich das ohne große Probleme umsetzen.

Die im Umfeld von VPNs verbreiteten Protokolle dagegen sind auf Angriffe durch Quantencomputer nicht vorbereitet. Als Extrembeispiel müsste man für das als quantenresistent geltende Verfahren von McEliece Schlüsselmaterial von rund 1 MByte Umfang übertragen, also rund 2000 Mal mehr als mit heutigen Verfahren. Das beeinflusst auch die Software-Entwicklung – ein Programmierer kann nicht beliebig viel Speicher auf einem System reservieren. So kann es passieren, dass Software, die für die heute (oder früher) üblichen Datengrößen geschrieben wurde, nun für die neuen Verfahren angepasst werden muss.

Um eine Adaption der bestehenden Infrastruktur mit all ihren Protokollen und der Software auf unterschiedlichsten Systemen zu ermöglichen, beschäftigen sich Standardisierungsgremien bereits mit dem Problem. Hier gilt es, einen Konsens zu finden, wie man die Protokolle erweitern kann, um in Zukunft sowohl praktikabel als auch sicher zu kommunizieren. Es bedarf teils neuer Konzepte, insbesondere, da nun der Fokus auf Modularität der Mechanismen und eine hybride Anwendung der Verfahren liegt.

Das Problem lässt sich durchaus lösen. Das amerikanische National Institute of Standards and Technology (NIST) durchläuft derzeit einen Standardisierungsprozess [1], auch das deutsche Bundesamt für Sicherheit in der Informationstechnik (BSI) rät zu einer Migration und empfiehlt erste quantenresistente Algorithmen [2]. Bis zur Verabschiedung der Standards und ihrer Etablierung in der Praxis dürften aber noch Jahre vergehen. Für hochsensible Anwendungsfälle kann das bereits zu spät sein.

Im Bereich des VPN-Protokolls IPsec besteht beispielsweise breiter Konsens, dass man – solange kein entsprechend leistungsfähiger Quantencomputer existiert – als quantenresistent geltende Verfahren lediglich hinzufügt, die klassischen Verfahren aber noch nicht ersetzt. Darauf aufbauend wurden für das in IPsec verbreitete Schlüsselaustauschprotokoll IKEv2 bereits erste Lösungen besprochen und in Form zweier derzeit diskutierter Internet-Drafts niedergelegt. Sie spezifizieren, wie sich im Protokoll zusätzliche Nachrichten austauschen lassen: Die Schlüssel der meisten quantenresistenten Alternativen fallen zu groß aus, um sie zusammen mit dem zugrundeliegenden Diffie-Hellman-Austausch (DH) in einer Nachricht auszutauschen, ohne die maximale Größe der initialen Nachricht zu überschreiten. Diese ist letztlich nicht nur durch das Protokoll bedingt, sondern auch durch externe Parameter des Netzwerks wie etwa die Maximum Transmission Unit (MTU).

Deshalb will man zwischen dem initialen Handshake, ab dem die Verbindung mithilfe eines aus dem DH abgeleiteten Session Keys für AES abgesichert wird, und dem Authentifizierungsschritt mehrere Nachrichten für zusätzliche Schlüsselvereinbarungen einfügen. So könnte man mithilfe eines quantenresistenten Verfahrens (oder mehrerer) zusätzliche Geheimnisse austauschen und den verwendeten symmetrischen Schlüssel aktualisieren. Die Verbindung wäre im Folgenden mit mindestens zwei Verfahren gesichert und damit auch quantenresistent.

Doch selbst das löst noch nicht alle Probleme. Die maximale Größe einer IKEv2-Nachricht beträgt 64 KByte – zu klein für manche Verfahren, unter anderem für einige McEliece-Konfigurationen. Deshalb müsste man den Schlüssel selbst auf mehrere Nachrichten verteilen und beim Empfänger mittels eines internen Zählers wieder zusammensetzen. Auch mögliche Lösungen für dieses Problem sind derzeit in Arbeit, deren Sicherheit ist aber noch nicht abschließend geklärt.

Es stellen sich aber nicht nur protokolltechnische, sondern auch methodische Fragen. Der Diffie-Hellman-Schlüsselaustausch, der heute in fast allen gängigen Protokollen zum Einsatz kommt, lässt beide Kommunikationspartner gleichberechtigt und mit gleichem Kommunikationsaufwand an der Erstellung des finalen symmetrischen Schlüssels mitwirken. Bei den im Bereich der Post-Quantum-Kryptografie häufig vorkommenden Key-Encapsulation-Mechanismen (KEM) ist das nicht immer der Fall, denn hier wird der Schlüssel von einem Kommunikationspartner zum anderen übertragen. Für McEliece bedeutet dies etwa, dass sehr viele Daten in eine Richtung wandern und nur sehr wenige in die andere. Dieses für bisherige Protokolle ungewöhnliche Verhältnis lässt sich unter Umständen auch ohne einen Quantencomputer von Angreifern ausnutzen. Ebenso gilt es, zu klären, wie man mithilfe von KEMs in Protokollen oder Anwendungsfällen am besten Eigenschaften wie Forward Secrecy erreicht.

All diese Probleme verursachen verschiedene Änderungen an Protokollen, die eigentlich bewusst für wenige Verfahren optimiert beziehungsweise deren Komplexität vergleichsweise niedrig gehalten wurde, um verschiedene Angriffe auszuschließen oder deren Effekt zu minimieren. Das Umsetzen von hybriden oder kryptoagilen Lösungen konterkariert diese Vorgehensweise, denn durch die Erweiterung von Kommunikationsprotokollen um quantenresistente Lösungen steigt die Komplexität. Zudem ergeben sich neue Probleme, wie beispielsweise einfachere Denial-of-Service-Attacken. Nun muss man – zum Beispiel durch Managementlösungen – in der Software überprüfen, ob etwa ein Angreifer versucht, den Speicher des Empfängers mit möglichst vielen als Schlüsselmaterial getarnten Daten zu füllen.

Fazit

Alles in allem handelt es sich um lösbare Probleme, aber bereits jetzt steht außer Zweifel, dass die Alternativen niemals so effizient und schlicht ausfallen können wie die klassischen etablierten Verfahren. Außerdem müssen wir uns von der Vorstellung einer Universallösung verabschieden, wie sie RSA jahrzehntelang geboten hat. Die Auswahl geeigneter quantenresistenter Verfahren oder neuer Sicherheitsmechanismen in Protokollen muss anhand ihrer Vor- und Nachteile für bestimmte Anwendungsfälle getroffen werden.

Bei der Migration zu quantenresistenter IT gilt es daher, vorab zu klären, an welchen Stellen im eigenen Unternehmen oder in den eigenen Produkten Kryptografie zum Einsatz kommt. Anschließend kann man überprüfen, in welchem Maß und in welcher Form sich diese austauschen lassen. Hier werden immer Abhängigkeiten auftauchen, die bedeuten, dass Produkthersteller oder Open-Source-Projekte entsprechende Anpassungen vornehmen müssen. So stellt sich beispielsweise die Frage, ob sich verwendete Kryptobibliotheken durch die quantenresistenten Alternativen ersetzen lassen oder ob hohe Sicherheitsanforderungen bereits Übergangslösungen erzwingen. Manche Standardisierungsgremien versuchen zumindest, die Möglichkeit zu bieten, bereits heutige Kommunikation ohne den Einsatz von Postquantum-Kryptografie gegen Quantencomputer abzusichern, etwa mithilfe von Pre-Shared Keys. Dann würde es genügen, erst später auf wirklich gute und vor allem praktikable Lösungen umzusteigen.

Die Vielzahl von Anforderungen macht eine allgemeingültige Empfehlung unmöglich. Nur der Einsatz von Experten und ein breiter Wissensaustausch vermögen, Insellösungen zu vermeiden, wie sie in der Vergangenheit leider oft entstanden. Daneben gilt es, eine möglichst breite Palette von Anwendungsfällen mit einer möglichst kleinen Zahl von Standardlösungen abzudecken. Dabei sind die Krypto- und IT-Sicherheits-Experten auf das Domänenwissen von Software- und Hardware-Entwicklern sowie Administratoren kleiner und großer Netze angewiesen. Nur sie können neue Verfahren, Bibliotheken und Protokolle auf ihrer jeweiligen Infrastruktur mit größeren Datenmengen austesten und somit Schwachstellen erkennen. Die Behörden, Standardisierungsgremien und die Krypto-Community benötigen genau diesen Input und freuen sich über unser aller Beteiligung, um die digitale Welt von morgen auf die Anforderungen von übermorgen vorzubereiten. (jcb/jlu)