Post-Quantum-Kryptographie
Der Weg in die Praxis
Beitrag von Dr. Stefan-Lukas Gazdag, Dr. Daniel Loebenberger, genua GmbH – Kirchheim und Dr. Johanna Sepúlveda, Lehrstuhl für Sicherheit in der Informationstechnik, TUM
Public-Key-Kryptographie ist die Grundlage für den Aufbau sicherer Kommunikationskanäle. Allerdings bergen sogenannte Quantencomputer ein Risiko für diese Kommunikationssicherheit. Sobald solche Rechner ausreichend leistungsfähig sind, werden sie in der Lage sein, heute gängige asymmetrische bzw. Public-Key-Verfahren zu brechen und alle heute bekannten und genutzten symmetrischen Techniken zu schwächen. Um dieser Gefahr zu begegnen, werden sogenannte Post-Quantum-Algorithmen benötigt. Wie diese in der Praxis eingesetzt werden und welche Verfahren es gibt.
Grundprinzip der Quantencomputer
Quantencomputer erobern inzwischen selbst die Massenmedien und wissen dabei zu faszinieren. In der Presse werden sie gerne mal als Wundermaschinen dargestellt, die plötzlich alles besser können. Hinter Quantencomputern steckt jedoch keine Magie, sondern Wissenschaft. Das Grundprinzip solcher Computer beruht auf den Eigenschaften subatomarer Teilchen (den Quanten), die zu jedem Zeitpunkt potenziell in mehr als einem Zustand existieren können. Aufgrund der Art und Weise, wie sich diese kleinen Partikel verhalten, können bestimmte Rechenoperationen viel schneller als bei klassischen Computern ausgeführt werden.
Bewährte Verfahren werden angreifbar
Allerdings ist dieser Fortschritt auch mit einem Problem für die Sicherheit verknüpft. Bisher wissen wir dank der Arbeit von Shor [1], dass Quantencomputer effizient faktorisieren können. Das Faktorisieren großer Zahlen ist jedoch auch ein wichtiges mathematisches Problem, auf das sich die aktuelle Public-Key-Kryptographie stützt. Mit anderen Worten: Sobald die Quantencomputer über genug Rechenleistung verfügen, sind Verfahren wie RSA effizient angreifbar. Die Sicherheit symmetrischer Verschlüsselung wie AES ist ebenfalls von Quantencomputern betroffen: sie halbiert sich aus generischer Sicht, also bei Betrachtung ganzer Verfahrensarten, wie die Arbeit von Grover [2] gezeigt hat.
Sicherheit von Anwendungen und Kommunikation
Im konkreten Beispiel würde das wiederum bedeuten, dass Anwendungen wie Online-Banking bzw. sichere Kommunikation über das Internet im Allgemeinen nicht mehr sicher sind, wenn ein Angreifer über einen hinreichend großen Quantencomputer verfügt, siehe Abb. 1. Deswegen ist es nicht überraschend, dass die Forschung schon länger untersucht, wie Sicherheit trotz der Gefahr durch Quantencomputer erreicht werden kann.
Post-Quantum-Kryptographie
Seit mehr als 15 Jahren beschäftigen sich Kryptologen intensiv mit sog. kryptographischen Primitiven, die resistent gegen Quantencomputer sind. Als Ergebnis konnten Algorithmen gefunden werden, die auf harten Problemen im Bereich von Codes, Gittern, multivariaten Gleichungssystemen und Hashfunktionen basieren. Diese Gruppe von Algorithmen wird als Post-Quantum Kryptographie bezeichnet und ist nicht nur gegen klassische, sondern auch gegen Quantencomputer-basierte kryptoanalytische Angriffe resistent.
Die amerikanische Behörde für Standardisierung und Technologien, die NIST, hat deshalb Ende 2017 begonnen, im Rahmen eines Standardisierungsprozesses geeignete Kryptosysteme zu identifizieren, die für den Einsatz im Post-Quantum Zeitalter in Frage kommen. Diese sollen in den folgenden Jahren von Experten analysiert und geeignete Verfahren letztlich dann auch standardisiert und für bestimmte Einsatzszenarien empfohlen werden. Auch andere Gremien verfolgen ein ähnliches Ziel. So verfolgt die für Internetstandards zuständige IETF/IRTF mehrere Standards im Bereich der Post-Quantum Kryptographie, von denen ein erster auch schon im Rahmen von RFC8391 publiziert wurde [4,5].
Umsetzung der Theorie
Um diese Algorithmen in der Praxis nutzen zu können, müssen wir uns schon heute damit auseinandersetzen, wie wir den Weg entsprechend bereiten. Schon bei klassischen Verfahren hat sich gezeigt, dass für neue Verfahren von der theoretischen Beschreibung, über Analysen zur Sicherheit, die Normierung des Verfahrens bis hin zu der tatsächlichen Umsetzung und Verbreitung in der Praxis gerne 15 bis 20 Jahre vergehen, siehe Abb. 2.
Dank der Forschung in den letzten Jahren wächst das Verständnis für die Sicherheit dieser Systeme weiter, aber es gibt noch viel zu tun, sowohl in der Theorie als auch in der Praxis – und die Zeit drängt: Während die Theorie weiterhin die mathematischen Probleme untersucht, rückt potenziell der Tag näher, an dem Angriffe auf die Sicherheit mittels Quantencomputern möglich sind. Und so ist es nötig, dass gleichzeitig daran gearbeitet wird, wie die sichere Theorie auch sicher in die Praxis gebracht werden kann.
Auf dem Weg in die Praxis
Will man Post-Quantum-Verfahren in der Praxis einsetzen, so führt kaum ein Weg daran vorbei, etwaige Beschränkungen in Protokollen und Implementierungen aufzuweichen. Nichtsdestotrotz ist nicht nur die Analyse der Sicherheit, sondern auch die Optimierung der neuartigen Verfahren ein wichtiges Ziel der aktuellen Forschung. Schließlich will man übermäßigen Speicherbedarf und niedrige Geschwindigkeiten vermeiden.
Sowohl der Lehrstuhl für Sicherheit in der Informationstechnik an der TU München als auch die genua GmbH sind dabei, die Post-Quantum-Kryptographie auf ihrem Weg zur Praxis voranzubringen. Dabei wird am Lehrstuhl an Gitterbasierten Verfahren gearbeitet und bei genua werden hashbasierte Verfahren schon jetzt neben den aktuellen Sicherheitsverfahren in der Praxis angewendet.
Gitterbasierte Verfahren
Dieser Ansatz ist einer der vielversprechendsten Post-Quantum-Kandidaten. Mathematische Gitter, im Prinzip die Darstellung von Vektoren in einem mehrdimensionalen Raum, können zum Verschlüsseln, zum Austausch von Schlüsseln und zum Signieren verwendet werden und bieten gleichzeitig einen sehr guten Kompromiss zwischen Sicherheit und Effizienz. Darüber hinaus ist die Größe des Schlüssels und des Geheimtextes klein, wodurch in der Praxis Datenmengen und Ressourcenbedarf eingespart werden können.
Ein Beispiel für ein effizientes Gitterbasiertes Kryptosystem ist das sog. NTRU-Verfahren, das als IEEE 1363.1 standardisiert wurde. Eine mögliche Grundlage für ein Kryptosystem ist das sog. Problem „Learning with Errors“ (LWE), also das Lernen mit Fehlern, bei dem die geheime Nachricht durch das Hinzufügen von zufälligen Fehlern verborgen werden kann.
Der Lehrstuhl für Sicherheit in der Informationstechnik investiert in die Entwicklung von Software- und Hardwarelösungen für eine sichere Post-Quantum-Kryptographie. Es konnten bereits die gegenwärtig kleinste und kompakteste Implementierung von NTRU und mehrere Embedded-Lösungen der verschiedenen, beim NIST-Standardisierungsprozess eingereichten Gitterbasierten Kandidaten entwickelt werden. Diese können z. B. in Industrie 4.0-Geräte integriert werden, einschließlich der Sensoren für drahtlose Netze.
Das Ziel ist es, auch weiterhin an Methoden zum Steigern der Sicherheit und der Effizienz von Gitterbasierter Kryptographie zu forschen.
Hashbasierte Verfahren
Hashfunktionen sind Einwegfunktionen, sind also nicht umkehrbar. Hashbasierte Signaturen sind im Bereich der Post-Quantum-Kryptographie eine hervorragende Wahl. Zur Erstellung solcher digitaler Unterschriften werden dabei viele, in einer Baumstruktur abgelegte Schlüssel eines Einmalsignatur-Verfahrens verwendet. Für eine Illustration eines solchen Verfahrens siehe Abbildung 3.
Diese Konstruktion ist verhältnismäßig gut verstanden und das Sicherheitsniveau solide einschätzbar, da sich die verwendeten Hashfunktionen bezüglich ihrer Sicherheit verträglich mit Quantencomputern verhalten: so kann man zeigen, dass die Verfahren nach aktuellem Kenntnisstand resistent gegenüber generischen Angriffen mithilfe von Quantencomputern sind.
Die Firma genua nutzt bereits das in RFC 8391 von der IETF/IRTF (www.ietf.org) standardisierte Hashbasierte Verfahren XMSS, um einige ihrer Produkte mit einer zusätzlichen Post-Quantum-Signatur auszustatten. Wird auf einem System ein neuer Softwarestand installiert, wird sowohl mit einer klassischen als auch mit einer quantenresistenten Signatur sichergestellt, dass das Softwarepaket tatsächlich von genua stammt.
Solch hybrides Vorgehen ist eine gute Lösung, um erste Erfahrungen mit Post-Quantum-Kryptographie zu sammeln. So kann schon heute auf die Sicherheit beider Kryptosysteme vertraut werden.
Literatur
[1] Shor, Peter W. (1997), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput., 26 (5): 1484–1509
[2] Grover, L. K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
[3] Michele Mosca: Cybersecurity in an era with quantum computers: will we be ready?; November 2015
[4] Andreas Huelsing, Denis Butin, Stefan-Lukas Gazdag, Joost Rijneveld und Aziz Mohaisen: RFC 8391; XMSS: eXtended Merkle Signature Scheme; IETF/IRTF; Mai 2018
[5] D. McGrew, M. Curcio, S. Fluhrer: Hash-Based Signatures; Internet-Draft; April 2018
Erstmals erschienen in: TiB Ausgabe 2018 November/Dezember