Ein Quantum Leitfaden : Kryptografie quantensicher gestalten

Die Kryptografie befindet sich im Umbruch. Während sie lange Zeit hauptsächlich in Spezialanwendungen, etwa im staatlichen Bereich, eine Rolle spielte, ist sie inzwischen allgegenwärtig und ihre Verwendung nimmt immer weiter zu. Kryptografie wird nicht nur benötigt, um sensible Daten zu schützen, sondern ist in vielen Anwendungen zwingend notwendig, um die sichere Funktionsfähigkeit und Verfügbarkeit zu gewährleisten – man denke nur an Internet, IoT, langlebige Industrieanlagen oder kritische Infrastrukturen.

Gleichzeitig hat die sogenannte „zweite Quantenrevolution“ begonnen: Physikalische Prinzipien, die vor ungefähr 100 Jahren entdeckt wurden, werden industriell beherrschbar. Es entwickeln sich Produkte und Anwendungen wie Quantencomputer, Quantenkryptografie, Quantensensoren und Quantensimulatoren, die Auswirkungen auf die Gestaltung sicherer kryptografischer Systeme haben werden.

Die Sicherheit digitaler Infrastrukturen beruht heute zu einem großen Teil auf Public-Key-Kryptografie (asymmetrische Kryptografie). Diese wiederum hängt wesentlich von der angenommenen Schwierigkeit bestimmter mathematischer Probleme ab. Aus diesen mathematischen Problemen lassen sich Einwegfunktionen ableiten, das heißt Funktionen, die leicht zu berechnen, aber schwer umzukehren sind.

Für die Public-Key-Kryptografie sind das Faktorisierungsproblem und das Diskrete-Logarithmus-Problem (DLP) grundlegend. Beim Faktorisierungsproblem soll eine natürliche Zahl in ihre Primfaktoren zerlegt werden. Die zugehörige Funktion, von der man vermutet, dass es sich um eine Einwegfunktion handelt, ist die schnell durchführbare Multiplikation von zwei sehr großen Primzahlen. Bisher ist kein effizienter klassischer Algorithmus bekannt, der ein solch großes Produkt wieder in seine beiden Primfaktoren zerlegen kann. Diese Beobachtung ist die Basis für das nach seinen Entwicklern Rivest, Shamir und Adleman benannte RSA-Verfahren, das sowohl zur Verschlüsselung als auch für digitale Signaturen eingesetzt wird. Auf Basis des DLP lassen sich beispielsweise Verfahren zum Schlüsselaustausch konstruieren.

Quantencomputer bedrohen heute eingesetzte Kryptografie

Üblicherweise vereinbart man mit einem Public-Key-Verfahren kryptografische Schlüssel, um anschließend Nachrichten mit einem symmetrischen Algorithmus wie dem „Advanced Encryption Standard“ (AES) zu verschlüsseln. Mit klassischen Computern sind die gängigen Public-Key-Verfahren nach heutigem Kenntnisstand nicht zu brechen. Die Situation ändert sich allerdings grundlegend, wenn universelle Quantencomputer ausreichender Leistungsfähigkeit verfügbar sind. Denn bereits 1994 wurden von Peter Shor Quantenalgorithmen vorgestellt, welche die oben genannten mathematischen Probleme effizient lösen können.

Mit der Entwicklung eines Quantencomputers, auf dem die Algorithmen von Shor für ausreichend große Eingabegrößen implementiert werden können, würde somit der heutigen Public-Key-Kryptografie die Grundlage entzogen werden. Dabei ist zu beachten, dass ein Angreifer auch heute schon Kommunikation aufzeichnen kann, um später an ihre Inhalte zu gelangen („store now, decrypt later“). Für symmetrische Algorithmen würde sich durch den Algorithmus von Grover die effektive Schlüssellänge immerhin noch halbieren. Zudem könnte man Quantencomputer auch einsetzen, um klassische kryptografische Angriffe zu beschleunigen. Ebenso ist es denkbar, dass Seitenkanalangriffe auf Implementierungen kryptografischer Mechanismen mithilfe von Quantensensoren verbessert werden können.

Bisher ist noch kein Quantencomputer verfügbar, der zum Brechen kryptografischer Verfahren geeignet wäre. Die US-amerikanische National Security Agency (NSA) hat dennoch im Jahr 2015 eindringlich vor der drohenden Gefährdung aktueller Public-Key-Kryptografie durch die Entwicklung von Quantencomputern gewarnt. Um eine fundierte Einschätzung zum aktuellen Entwicklungsstand beziehungsweise der potenziellen zukünftigen Verfügbarkeit eines Quantencomputers zu erhalten, wurde im Auftrag des BSI von 2017 bis 2020 die Studie „Entwicklungsstand Quantencomputer“ durchgeführt (siehe www.bsi.bund.de/qcstudie). Die Studie wird derzeit fortgeführt und aktualisiert. Großunternehmen wie Google und IBM haben ambitionierte Roadmaps zur Verfügbarkeit von Quantencomputern veröffentlicht.

Quantensichere Kryptografie

In der kryptografischen Forschung entwickelte sich parallel zu den Fortschritten bei der Entwicklung von Quantentechnologie ein neues Arbeitsgebiet: die Post-Quanten-Kryptografie. Diese beschäftigt sich mit der Entwicklung und Untersuchung von kryptografischen Verfahren, von denen man annimmt, dass sie auch mit Quantencomputern nicht gebrochen werden können. Die entsprechenden Verfahren beruhen auf mathematischen Problemen, für deren Lösung heute weder effiziente klassische Algorithmen noch effiziente Quantenalgorithmen bekannt sind.

Eine alternative Lösung, zumindest für quantensicheren Schlüsselaustausch, bietet die „Quantum Key Distribution“ (QKD): Sie nutzt quantenmechanische Effekte, um Sicherheit für kryptografische Anwendungen zu erreichen. QKD soll informationstheoretisch sicher sein, also auch von Angreifern mit unbeschränkter Rechenleistung nicht gebrochen werden können. In realen Implementierungen ist dieses Versprechen allerdings kaum einlösbar. Zudem sind bei QKD einige praktische Einschränkungen wie beschränkte Reichweiten zu beachten, welche die Zahl geeigneter Anwendungen stark reduzieren. Aus Sicht des BSI ist die Migration zu Post-Quanten-Verfahren deshalb klar zu priorisieren. Dennoch findet QKD immer mehr Interesse; und eine Vielzahl von Projekten zur Realisierung von QKD ist zu beobachten.

Neben Forschung und Entwicklung haben verschiedene Standardisierungsaktivitäten zur Post-Quanten-Kryptografie begonnen, um die Verfahren für industrielle Anwendungen zur Verfügung zu stellen. Zu den bekanntesten zählt der Standardisierungsprozess „Post-Quantum Cryptography“ (siehe https://csrc.nist.gov/Projects/Post-Quantum-Cryptography) des US-amerikanischen National Institute of Standards and Technology (NIST), an dessen Ende eine Auswahl von Post-Quanten-Schlüsseleinigungs- und Signaturverfahren zur Verfügung stehen soll.

Wie viel Zeit bleibt für die Migration?

Um abzuschätzen, wann die Migration zu quantencomputerresistenter Kryptografie notwendig ist, ist die folgende Überlegung des theoretischen Physikers Michele Mosca sehr anschaulich. Sei dafür

• x die Anzahl der Jahre, welche die zu schützenden Daten abgesichert bleiben müssen,
• y die Anzahl der Jahre, die man benötigt, um das entsprechende System auf quantencomputerresistente Kryptografie umzustellen, sowie
• z die Anzahl der Jahre, die es noch dauert, bis Quantencomputer existieren, welche die aktuell verwendete
  Kryptografie gefährden.

Dann gilt: Falls x + y > z ist, haben Sie ein Problem!

Diese Aussage ist als „Moscas Theorem“ bekannt geworden, auch wenn sie natürlich sofort einsichtig ist. Sie soll im Folgenden ein wenig konkretisiert werden:

Wenn die Migration zu quantencomputerresistenter Kryptografie heute begonnen wird, ist die Umstellung erst nach y Jahren abgeschlossen. Wie groß y ist, hängt von verschiedenen Faktoren ab, beispielsweise in welchem Umfang Systeme betroffen sind sowie von der Verfügbarkeit quantencomputerresistenter Alternativen. Ein wichtiger erster Schritt ist daher eine Bestandsaufnahme und die Entwicklung eines Migrationsplans.

Die letzten Daten, die noch mit den alten Methoden verschlüsselt wurden, werden somit in y Jahren erzeugt und sollen dann noch x Jahre abgesichert sein. Im Fall von Echtzeitkommunikation kann diese Zeitdauer x verschwindend gering sein. Im Gegensatz dazu sollten zum Beispiel Patienteninformationen mehrere Jahrzehnte gesichert bleiben.

Angenommen, es gilt x + y > z. Dann können die letzten Daten, die noch nicht quantencomputerresistent abgesichert sind, abgefangen und noch innerhalb der Zeit entschlüsselt werden, in der sie gesichert sein sollten. Somit muss mit der Migration zu quantencomputerresistenter Kryptografie so früh begonnen werden, dass noch x + y < z für alle zu schützenden Daten gilt. Aber wie groß ist z?

Für den Hochsicherheitsbereich handelt das BSI nach der Arbeitshypothese, dass Anfang der 2030er-Jahre kryptografisch relevante Quantencomputer zur Verfügung stehen werden. Dabei ist zu betonen, dass diese Aussage nicht als Prognose zur Verfügbarkeit von Quantencomputern zu verstehen ist, sondern einen Richtwert für die Risikobewertung darstellt. Das BSI hat daher im Einklang mit dem Rahmenprogramm „Quantentechnologien – von den Grundlagen zum Markt“ (siehe www.quantentechnologien.de) den Wechsel zu quantensicherer Kryptografie eingeleitet.

Auch in der kürzlich veröffentlichen „Cybersicherheitsstrategie für Deutschland 2021“ (siehe www.bmi.bund.de/SharedDocs/pressemitteilungen/DE/2021/09/cybersicherheitsstrategie-2021.html) des Bundesministeriums des Innern und für Heimat (BMI) wird das Ziel „IT-Sicherheit durch Quantentechnologie gewährleisten“ mit einer Reihe von Messgrößen hinterlegt, beispielsweise der „Migration zu quantensicherer Kryptografie im Hochsicherheitsbereich“.

Migration zu quantensicheren Verfahren: Ein langer Weg

Die Migration zu quantensicherer Kryptografie ist ein langer Prozess und sollte deshalb so schnell wie möglich angegangen werden. Mit der Entwicklung und Standardisierung neuer Algorithmen beziehungsweise Verfahren allein ist es nämlich nicht getan: Zum einen passen die Algorithmen nicht ohne Weiteres in bestehende kryptografische Protokolle wie beispielsweise das Transport-Layer-Security-Protokoll (TLS). Zum anderen sind mögliche Schwachstellen, die sich erst durch die konkrete Implementierung eines neuen Algorithmus ergeben, noch nicht genauso gut untersucht, wie dies bei den schon länger verwendeten Algorithmen der Fall ist.

Daher sollten die quantensicheren Verfahren – zumindest in einer Übergangszeit – nicht alleine eingesetzt werden, sondern nur „hybrid“, also in Kombination mit einem klassischen Verfahren. Dafür müssen Protokolle entsprechend geändert beziehungsweise ergänzt werden. Zusätzlich müssen beispielsweise auch Public-Key-Infrastrukturen angepasst werden: Auch hier stellt sich die Frage, ob eine Signatur mit einem Post-Quanten-Verfahren ausreichend ist oder ob „hybride Zertifikate“ benötigt werden. Viele dieser Fragestellungen sind (weitestgehend) unabhängig von der Auswahl konkreter Algorithmen und werden daher schon jetzt angegangen.

Da die Sicherheit von kryptografischen Verfahren oder die Eignung von Schlüssellängen nicht auf lange Zeit garantiert werden kann, entsteht ein großer Bedarf nach sogenannten kryptoagilen Lösungen, die den sicheren und leichten Austausch von kryptografischen Verfahren oder sogar Protokollen und Implementierungen ermöglichen. Um das Ziel „Kryptoagilität“ auf Dauer zu erreichen, ist auch die permanente Nutzung hybrider Lösungen ein wichtiger Baustein. Ebenso sollten quantensichere Lösungen zum Softwareupdate wo möglich mit vorgesehen werden. Diese und andere Empfehlungen zur „Migration zu Post-Quanten-Kryptografie“ hat das BSI im März 2020 veröffentlicht.

BSI-Leitfaden

Diese Handlungsempfehlungen sind allerdings sehr knapp gehalten und inzwischen nicht mehr auf dem aktuellen Stand. Ferner haben sie sich auf Empfehlungen zu Post-Quanten-Kryptografie beschränkt. Die schnellen Entwicklungen und große Förderung im Bereich QKD machen es aber erforderlich, QKD als mögliche Lösung für quantensichere Verfahren genauer einzuordnen und ausführlichere Empfehlungen für einen möglichen Einsatz zu geben.

Der im Dezember 2021 veröffentlichte Leitfaden „Kryptografie quantensicher gestalten“ des BSI soll diese Lücke schließen (www.bsi.bund.de/PQ-Migration). Er gibt einen Überblick über die aus Sicht der IT-Sicherheit wichtigsten Entwicklungen im Bereich der Quantentechnologie sowie Handlungsempfehlungen zur Migration auf quantensichere Kryptografie. Der Wechsel zu quantensicherer Kryptografie führt zu zahlreichen offenen Fragen, beispielsweise zur Auswahl geeigneter Algorithmen und zu notwendigen Anpassungen bei Protokollen und Standards, die in diesem Dokument diskutiert werden. Als Grundlage für diese Diskussion werden zunächst grob die Möglichkeiten und der Entwicklungsstand von Quantencomputern beschrieben. Danach geht das Dokument ausführlich auf Post-Quanten-Kryptografie und QKD ein und grenzt diese beiden sich gegenseitig ergänzenden Vorschläge voneinander ab.

Fazit

Wegen der rasant fortschreitenden Entwicklung im Bereich der Quantentechnologie ist ein Wechsel zu quantensicheren kryptografischen Verfahren dringend erforderlich. Bereits jetzt können Maßnahmen ergriffen werden, um eine Migration vorzubereiten. Der BSI-Leitfaden gibt Handlungsempfehlungen für die Migration und zeigt offene Fragen auf. Er ist damit gleichzeitig ein aktueller Beitrag und eine Anregung für weitere Diskussion über Sicherheit im Quantenzeitalter.

Von Dr. Stephan Ehlen, Dr. Heike Hagemeier, Dr. Tobias Hemmert, Dr. Stavros Kousidis, Dr. Manfred Lochter, Stephanie Reinhardt, BSI

Kontakt: quantum@bsi.bund.de