Migration zur Post-Quanten-Kryptografie : Ein Überblick über den Stand der Dinge
Nach aktuellen Prognosen und Forschungsergebnissen sind viele der nach heutigem Stand der Technik verwendeten kryptografischen Verfahren durch Quantencomputer gefährdet. Seit Jahren wird weltweit an Lösungen gearbeitet.
Die Post-Quanten-Kryptografie ist ein Teilgebiet der Kryptografie und umfasst kryptografische Verfahren, die auch vor leistungsstarken Quantencomputern sicher zu sein scheinen. Der Begriff ist nicht zu verwechseln mit der Quantenkryptografie, die sich auf Verfahren beschränkt, die ebenfalls robust gegenüber Quantencomputer sind, aber auf physikalischen Gesetzen beruhen. Post-Quanten-Kryptografie-(PQC)-Verfahren basieren dagegen auf schwer lösbaren mathematischen Problemen (z. B. „Learning with Errors“). Da die Quantenkryptografie aufgrund der hohen Anforderungen an die Hardware sehr aufwendig ist, konzentriert sich die Forschung vor allem auf die Entwicklung und Einführung von PQC-Verfahren. Hier gibt es fünf Teilbereiche: gitterbasierte, codebasierte, hashbasierte, multivariate und isogeniebasierte Verfahren.
- Gitterbasierte Verfahren basieren auf mathematischen Gittern, die in der Zahlentheorie sowie in der linearen Algebra definiert sind und aus einer periodischen Anordnung von Punkten in einem Raum bestehen. Auf diesen Gittern gibt es verschiedene schwer zu lösende mathematische Probleme, wie zum Beispiel das „Learning with Errors“-Problem (LWE), das sich mit dem Lösen linearer Gleichungssysteme befasst, die einen Fehlervektor beinhalten, der unbekannt ist. Das LWE-Problem gilt als schwer zu lösen, wenn sowohl die Anzahl der Gleichungen als auch die Fehlervektoren in dem linearen Gleichungssystem ausreichend groß sind. Diese Schwierigkeit nutzt man in der gitterbasierten Kryptografie aus, um verschiedene kryptografische Primitive wie Verschlüsselungsverfahren, digitale Signaturen und Schlüsselaustauschprotokolle zu konstruieren.
- Die Grundlage der codebasierten Kryptografie bildet die Codierungstheorie. Hier dienen fehlerkorrigierende Codes zur nachträglichen Korrektur von Übertragungsfehlern. Für spezielle lineare Codes gibt es effiziente Fehlerkorrekturalgorithmen, die unumkehrbar sind. Genau diese Einwegeigenschaft nutzt man bei der Anwendung in der Kryptografie aus.
- Hashbasierte Verfahren gelten als vielversprechend, da sie auf den bereits etablierten Prinzipien der Hashfunktionen aufbauen. Sie sind jedoch im alltäglichen Einsatz schwierig, da der Berechnungsaufwand sehr groß ist. Darüber hinaus sind die Übertragungskosten hoch, da der öffentliche Schlüssel und die erzeugte Signatur recht groß sind. SPHINCS+ verwendet One-time-Signatures (Einmal-Signaturen), was bedeutet, dass für jede Nachricht ein neuer Schlüssel und eine neue Signatur generiert werden müssen.
- Multivariate Verfahren basieren auf der Verwendung mathematischer Gleichungssysteme, die als multivariate quadratische Gleichungen (MQ) bezeichnet werden. Das grundlegende Konzept ist die Schwierigkeit des Lösens von Gleichungssystemen in algebraischer Form, die hochgradig nichtlinear und somit schwer zu lösen sind.
- IsogeniebasierteVerfahren basieren auf isogenen Abbildungen. Isogenien sind spezielle mathematische Abbildungen zwischen elliptischen Kurven. Es gilt als schwierig, Isogenien zwischen elliptischen Kurven zu berechnen.
Auf der Suche nach neuen Verfahren
Da bisher alle zulässigen asymmetrischen Verschlüsselungen durch Quantencomputer gefährdet sind, sind neue Verfahren für unterschiedliche Einsatzzwecke notwendig. Das NIST hat diese Problematik frühzeitig erkannt und bereits im Jahr 2016 einen Standardisierungsprozess für Post-Quanten-Kryptografie-Verfahren gestartet. Die eingereichten Verfahren wurden hinsichtlich ihres Sicherheitsniveaus, ihrer Leistungsfähigkeit und weiterer technischer Aspekte geprüft. Alle, die es in die weiteren Runden geschafft haben, wurden auf der NIST-Webseite zusammen mit allen Dokumentationen der Forschenden veröffentlicht. Das NIST gab zudem der breiten Öffentlichkeit die Möglichkeit zur öffentlichen Kommentierung und berücksichtigte die Rückmeldungen im Entscheidungsprozess.
Mitte 2022 war die dritte Runde des Standardisierungsprozesses beendet: Zur Verschlüsselung (PKE) und Schlüsselentkapselung (KEM) wurde das gitterbasierte Verfahren Crystals Kyber ausgesucht. Für die Erstellung digitaler Signaturen wurden die ebenfalls gitterbasierten Verfahren Crystals-Dilithium und Falcon sowie das hashbasierte Verfahren SPHINCS+ ausgewählt. Für die vierte Runde qualifizierten sich außerdem noch vier weitere: Classic McEliece, BIKE, HQC und SIKE. Die ersten drei sind codebasiert, SIKE hingegen ist isogeniebasiert. Allerdings wurde es Anfang August innerhalb von 62 Minuten auf einem Laptop gebrochen. Das gleiche Schicksal ereilte das multivariate Rainbow-Signaturverfahren. Auch hier schaffte man es, eine Angriffsmethode zu entwickeln, die die Berechnung des privaten Schlüssels ermöglicht.
Somit ist es gelungen, innerhalb von sechs Monaten zwei Verfahren zu brechen – was die Herausforderungen und die Risiken bei der Entwicklung von PQC-Verfahren unterstreicht. Es zeigt auch, wie anspruchsvoll die Forschung in diesem Bereich ist, da die Sicherheit der Verfahren von komplexen mathematischen Problemen abhängt. Aufgrund dieser Unwägbarkeiten ist es von entscheidender Bedeutung, dass Post-Quanten-Kryptografie-Verfahren sorgfältig erforscht, geprüft und überwacht werden, um zu gewährleisten, dass sie die erforderlichen Sicherheitsstandards erfüllen.
Für quantensichere Signaturen stehen nur noch gitterbasierte und hashbasierte Verfahren zur Verfügung. Das ist problematisch, da hashbasierte PQC-Verfahren aufgrund der hohen Anforderungen ungeeignet für den alltäglichen Einsatz sind. Ihre Anwendung ist in einigen Bereichen weniger praktisch, besonders in rechenintensiven oder ressourcenbeschränkten Umgebungen.
Darüber hinaus sind auch die klassischen kryptografischen Signaturalgorithmen (z. B. das RSA-Signaturverfahren) durch die rasche Weiterentwicklung der Quantencomputer gefährdet. Davon ausgenommen sind einige auf Hashfunktion basierende Signaturalgorithmen wie zum Beispiel „eXtended Merkle Signature Scheme“ (XMSS). Das Verfahren ist jedoch problematisch, da die Gesamtzahl der Signaturen für ein Schlüsselpaar begrenzt ist. Allerdings muss man für jeden Anwendungsbereich genau prüfen, ob es geeignet ist. Auch bei dem neuen hashbasierten Signaturverfahren SHINCS+ ist das schwierig. Aus diesen Gründen startete das NIST einen weiteren Aufruf zur Einreichung quantensicherer Verfahren zur Erstellung von digitalen Signaturen. Insgesamt sind nun 40 Verfahren im Rennen; eins davon ist isogeniebasiert. Auch das Bundesamt für Sicherheit in der Informationstechnik (BSI) hat sich zu diesem Thema geäußert und Handlungsempfehlungen veröffentlicht [1]. Aus Sicht des BSI entwickeln sich PQC-Verfahren langfristig zum neuen Standard – unabhängig davon, ob und wann es relevante Quantencomputer geben wird.
Grundlagen
Bei der symmetrischen Verschlüsselung werden Daten mithilfe eines kryptografischen Schlüssels ver- und entschlüsselt. Gemäß des kerckhoffschen Prinzips basiert die Sicherheit des Verfahrens nicht auf der Geheimhaltung des Algorithmus, sondern auf der Geheimhaltung des kryptografischen Schlüssels.
Bei der asymmetrischen Verschlüsselung werden Daten mithilfe eines kryptografischen Schlüsselpaares ver- und entschlüsselt. Benutzer oder auch IT-Systeme erhalten ein Schlüsselpaar, welches aus einem öffentlichen und privaten Schlüssel besteht. Beide Schlüssel sind mathematisch miteinander verknüpft. Der öffentliche Schlüssel darf unverschlüsselt ausgetauscht werden, da es nicht möglich ist, über ihn auf den privaten Schlüssel zu schließen. Es muss aber sichergestellt werden, dass der Schlüssel während der Kommunikation nicht manipuliert wurde. Das geschieht über die Public-Key-Infrastruktur. Um Daten verschlüsselt an einen Benutzer zu übermitteln, werden diese mit dessen öffentlichen Schlüssel verschlüsselt. Der Benutzer kann mit seinem privaten Schlüssel die Daten wiederum entschlüsseln. Die asymmetrische Verschlüsselung gehört wie die digitale Signatur zum Bereich der Public-Key-Kryptografie. Mithilfe von digitalen Signaturen können beispielsweise Nachrichtenabsender authentifiziert werden. Der Benutzer kann mit seinem privaten Schlüssel eine digitale Signatur erstellen. Diese kann dann mit dem öffentlichen Schlüssel verifiziert werden.
Das wohl bekannteste asymmetrische Verschlüsselungsverfahren ist das RSA-Verfahren, das auf der Schwierigkeit der Faktorisierung großer Primzahlen beruht. Ein weiteres sehr bekanntes Public-Key-Verfahren ist das Diffie-Hellman-Schlüsselaustauschverfahren, welches auf dem mathematischen Problem des Lösens des diskreten Logarithmus basiert, um einen gemeinsamen geheimen Schlüssel zwischen zwei Parteien auszutauschen. Diese mathematischen Probleme werden als schwer bezeichnet, da sie mit klassischen Computern nicht in polynomialer Zeit lösbar sind. Ein Quantencomputer hingegen kann die Möglichkeit der Quantenüberlagerung und der Quantenverschränkung nutzen, um viele Berechnungen gleichzeitig durchzuführen. Die beiden erwähnten mathematischen Probleme können mithilfe der Quantenalgorithmen von Shor gelöst werden. Hierfür wird jedoch ein Quantencomputer mit einer ausreichenden Anzahl von Qubits benötigt.
Neben den asymmetrischen Verfahren sind ebenfalls auch die symmetrischen Verfahren durch den Quantenalgorithmus von Grover gefährdet. Der Grover-Algorithmus kann die Laufzeit für die Suche in einer unsortierten Datenbank quadratisch beschleunigen. Daraus folgt, dass das symmetrische Verschlüsselungsverfahren AES mit der Schlüssellänge von 128 Bit nicht mehr als sicher gilt, sobald die Quantencomputer dazu in der Lage sind. Dieses Problem lässt sich aber recht einfach lösen, da AES auch eine Schlüssellänge von 256 Bit anbietet.
Ziel Kryptoagilität
Um auf alle denkbaren Entwicklungen reagieren zu können, will man zukünftig bei Neu- und Weiterentwicklungen von Anwendungen darauf achten, dass ein System nahtlos an neue kryptografische Algorithmen angepasst werden kann, ohne dass eine grundlegende Neugestaltung oder Änderung des Systems erforderlich ist [2]. Diese als Kryptoagilität bezeichnete Eigenschaft stellt allerdings eine weitere Herausforderung dar. So muss man nun Anforderungen definieren, nach denen sich feststellen lässt, ob ein System schnell und effektiv auf neue kryptografische Algorithmen oder Schlüssel migrieren kann. Die Entwicklung und Implementierung kryptoagiler Systeme erfordert somit eine umfassende Planung.
Der Wunsch nach einem grundlegenden Konzept der Kryptoagilität hat in letzter Zeit an Bedeutung gewonnen. Das Thema hat an sich nichts mit dem PQC-Standardisierungsprozess zu tun. Es kann nämlich immer passieren, dass ein Algorithmus ein als sicher angenommenes kryptografisches Verfahren bricht und man es ersetzen muss. Angesichts der Bedrohung durch Quantencomputer will man kryptografische Lösungen jedoch in umfassende agile Lösungen umwandeln. Der Begriff Kryptoagilität wurde erstmals 2009 von Bryan Sullivan verwendet. Laut Kerry McKay vom NIST umfasst Kryptoagilität einerseits die Eigenschaft von Maschinen, ihre Sicherheitsalgorithmen in Echtzeit und auf der Grundlage ihrer kombinierten Sicherheitsfunktionen auszuwählen und andererseits die Fähigkeit, neue kryptografische Merkmale oder Algorithmen zu vorhandener Hard- und Software hinzuzufügen, was zu neuen, verstärkten Sicherheitsmerkmalen führt. Darüber hinaus umfasst Kryptogilität die Fähigkeit, kryptografische Systeme, die entweder verwundbar oder veraltet sind, in den Ruhestand zu versetzen.
Reifegradmodell
Doch wie stellt man fest, ob ein IT-System kryptoagil ist? Zu diesem Zweck wurde das Reifegradmodell „Crypto-Agility Maturity Model“ (CAMM) entwickelt, das aus fünf Stufen besteht [2]. Den niedrigsten Reifegrad drückt Stufe 0 „Initial / not possible“ aus, die standardmäßig gesetzt ist. Den höchsten Reifegrad „Sosphisticated“ erreichen IT-Systeme, die fortgeschrittene Fähigkeiten in Bezug auf die Kryptoagilität implementieren. Sie zeichnet sich dadurch aus, dass die Kompatibilität nicht auf ein bestimmtes System beschränkt ist, sondern in einer breiteren Infrastruktur angewendet wird. Dieser Reifegrad sollte vor allem das Ziel von Bibliotheken und Frameworks sein, die im Kontext von Kryptoagilität im Einsatz sind.
Damit ein untersuchtes IT-System eine bestimmte Stufe erreichen kann, muss es vorgegebene Anforderungen erfüllen. Ein Beispiel dafür auf der Reifegradstufe 1 ist „Systemknowledge“ („Systemkenntnis“). Um die Anforderungen an die Kryptoagilität effektiv bewerten zu können, sind detaillierte Kenntnisse über das betroffene IT-System und seine Umgebung vonnöten. Ohne ausreichendes Wissen lassen sich keine Aussagen über die Kryptoagilität treffen. Zudem sind auch die notwendigen Berechtigungen erforderlich, um wichtige Systemupdates durchführen zu können. Das wird in der Anforderung „Updateability“ („Aktualisierbarkeit“) ebenfalls auf der Reifegradstufe 1 gefordert. Für die höchste Stufe müssen beispielsweise die Änderungen an kryptografischen Funktionen im Produktionssystem so schnell wie möglich aktiv sein. Das bedeutet, dass hinzugefügte Kryptografie-Implementierungen innerhalb einer definierten Zeitspanne zuverlässig einsatzbereit sein müssen. Das ist beispielsweise realisierbar, indem die Kryptografie als externe, redundante Komponente ausgelagert wird, sodass kryptografische Aufgaben dynamisch an verschiedene Implementierungen weitergegeben werden können.
Workaround
Darüber hinaus fordert das Bundesamt für Sicherheit in der Informationstechnik (BSI) die Verwendung von PQC-Verfahren in Kombination mit klassischen kryptografischen Verfahren. Der Grund dafür ist die Tatsache, dass die neuen Algorithmen noch nicht so umfangreich erforscht sind wie die klassischen (z. B. RSA), sodass die Post-Quanten-Kryptografie-Verfahren weniger Vertrauen genießen. Die zeitnahe Migration ist jedoch aufgrund des Fortschritts in der Entwicklung der Quantencomputer dringend notwendig. So ist das „Store-now-decrypt-later“- Vorgehen beispielsweise ein großes Problem: Dabei speichern Cyberkriminelle oder Geheimdienste schon jetzt verschlüsselte Daten und warten auf die Quantencomputer, um sie entschlüsseln zu können. Um das zu verhindern, müssen Unternehmen und Behörden ihre Informationen so schnell wie möglich mit einem resistenten kryptografischen Verfahren verschlüsseln.
Dazu sollen die Daten nach dem Willen des BSI sowohl mit einem klassischen als auch mit einem Post-Quanten-Kryptografie-Verfahren verschlüsselt werden. Diese Vorgehensweise bezeichnet man als hybrid oder Komposition. In vielen Veröffentlichungen sprechen die Autoren eher von einer hybriden Vorgehensweise, obwohl der Begriff eigentlich bereits vergeben ist. Denn traditionell bedeutet er, dass der symmetrische Schlüssel mit einem asymmetrischen Verfahren ausgetauscht wird.
Die nächste Herausforderung für viele kryptografische Protokolle (wie z. B. TLS) ist der Entwurf eines solchen hybriden Verfahrens. Dafür muss die Logik der kryptografischen Protokolle angepasst werden. Bei TLS beispielsweise werden je nach Anwendungszweck verschiedene, bisher klassische kryptografische Verfahren ausgehandelt. Nun müssen in jedem Schritt mindestens zwei Verfahren ausgehandelt werden – ein klassisches und ein quantenresistentes. Sobald man sich für zwei Verfahren entschieden hat, ist es wichtig, dass diese so miteinander kombiniert werden, dass die Sicherheit des Protokolls weiterhin erhalten bleibt, solange mindestens eins der verwendeten Verfahren noch sicher ist.
Handlungskonzept
Als Reaktion auf die Risiken hat die Bundesregierung das „Handlungskonzept Quantentechnologien“ verabschiedet [3]: Bis 2026 will sie die Migration zu quantensicherer Kryptografie in Deutschland vorantreiben, besonders in kritischen Infrastrukturen. Eigentlich sind die Erfolgsaussichten dafür in Deutschland sehr gut, denn es hat als Forschungsland im Bereich der Quantentechnologie eine gute Position. Bei den Publikationen belegt Deutschland weltweit den vierten Platz und weist die meisten Veröffentlichungen aller europäischen Länder auf.
Über die Migration hinaus fördert die Bundesregierung ebenfalls die Entwicklung von quantenresistenten kryptografischen Systemen und will deren Qualität durch Standards sichern. Neben der Post-Quanten-Kryptografie unterstützt der Staat auch die Quantenkryptografie – sie soll als komplementäre Technologie eingesetzt werden.
Doch wie sieht die Lage in den Unternehmen in Deutschland aus? Dazu hat das BSI zusammen mit KPMG eine Umfrage durchgeführt [4]. Demnach schätzen über 95 Prozent der Teilnehmenden die generelle Relevanz von Quantencomputern für die Sicherheit kryptografischer Verfahren als „hoch“ oder „eher hoch“ ein. Sie erwarten im Mittel, dass aktuell verwendete Verfahren in zehn Jahren gebrochen werden. Trotzdem berücksichtigen nur 25 Prozent der Teilnehmenden die Gefährdungen der Kryptografie durch Quantencomputer im Risikomanagement ihrer Organisation. Ebenfalls erwarten rund 89 Prozent der Befragten, dass die Umstellung ihrer Organisation zu quantensicherer Kryptografie nicht rechtzeitig abgeschlossen sein wird. Die Ergebnisse sind ein Grund dafür, warum die Sensibilisierung in den Unternehmen heute schon sehr wichtig ist.
Fazit
Die Migration zu Post-Quanten-Kryptografie-Verfahren sollten besonders Betreiber kritischer Infrastrukturen bereits heute schon auf dem Schirm haben. Zu beachten ist hier jedoch, dass es sich bei diesem Thema noch um ein sehr aktives Forschungsgebiet handelt und weitere Entwicklungen möglich sind. Während der Migration können Unternehmen und Behörden mit Kryptoexperten zusammenarbeiten, um auf dem aktuellen Stand der Forschung zu bleiben und neue Erkenntnisse richtig einzuschätzen.
Barbara Grutzig ist Beraterin der HiSolutions AG im Bereich Security Consulting in Berlin.
Literatur
[1] BSI, Migration zu Post-Quanten-Kryptografie – Handlungsempfehlungen des BSI, August 2020, www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/PostQuanten-Kryptografie.pdf?__blob=publicationFile&v=1
[2] Julian Hohm, Andreas Heinemann, Alexander Wiesmaier, Towards a maturity model for crypto-agility assessment, Februar 2022, https://arxiv.org/pdf/2202.07645.pdf
[3] Bundesministerium für Bildung und Forschung, Handlungskonzept Quantentechnologien der Bundesregierung, April 2023, www.bmbf.de/SharedDocs/Downloads/de/2023/230426-handlungskonzept-quantentechnologien.html
[4] BSI, KMPG, Marktumfrage Kryptografie und Quantencomputing, April 2023, www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Krypto/Marktumfrage_Kryptografie_Quantencomputing.pdf?__blob=publicationFile&v=9