Erste Erfolge: Post-Quantum Kryptografie

Erste Erfolge: Post-Quantum Kryptografie

Quantencomputer könnten die heute genutzte Kryptografie schwächen und teils sogar brechen. Dadurch wäre es etwa nicht mehr möglich, sichere Kommunikation über das Internet oder das Installieren nicht-manipulierter Software auf Endgeräten zu gewährleisten. Derzeit arbeiten Universitäten, Behörden und Unternehmen intensiv daran, eine Krypto-Apokalypse abzuwenden.

Quantencomputer: Neue Chancen, neue Risiken

Quantencomputer faszinieren. So sehr, dass inzwischen sogar Massenmedien regelmäßig zu diesem Thema berichten. Im Gegensatz zu heutigen Computern nutzen diese Maschinen im Rahmen ihrer Datenverarbeitung Effekte der Quantenmechanik. Dabei ist ein Quantencomputer in der Lage, alle Berechnungen durchzuführen, die auch klassische Rechner vollziehen. Dies gilt allerdings auch andersherum: Quantencomputer können auch heute schon – wenn auch in beschränktem Umfang – simuliert werden. Die Frage ist nur, welche Rechenoperationen welchen Aufwand und damit auch Energie und Zeit benötigen.

Gerade bezüglich mancher Optimierungsaufgaben können Quantencomputer Aufgaben in kurzer Zeit lösen, die selbst auf modernen Supercomputern Jahrtausende benötigten. Dies hat auch Auswirkungen auf unsere IT-Sicherheit: In den 1990ern hat sich gezeigt, dass mithilfe von Quantenalgorithmen, wie den Methoden von Shor [1] und Grover [2], heute verwendete kryptografische Verfahren – die sog. symmetrische Kryptografie – geschwächt und alle praxisrelevanten Public-Key-Verfahren – die sog. asymmetrische Kryptografie – gar komplett gebrochen werden können.

In den frühen 2000ern begann man deshalb, sich mit Verfahren zu beschäftigen, die nicht nur resistent gegenüber klassischen Attacken, sondern auch sicher vor dieser neuen Art von Angriffen sind. Im Folgenden sollen einige Grundlagen der Kryptografie und die Vorgänge im Bereich der sog. Post-Quantum Kryptografie – PQC, teils auch als Quantum-Safe Cryptography (QSC) oder Quantum-Resistant Cryptography (QRC) bezeichnet – dargelegt werden.

Die Sicherheit von Kryptosystemen basiert auf schweren mathematischen Problemen, oft als "Falltüren" bezeichnet. Es muss eine vergleichsweise einfache Möglichkeit geben, um Daten ver- bzw. entschlüsseln oder signieren zu können, sofern man alle dafür nötigen Informationen (den Schlüssel) zur Verfügung hat. Ist dies nicht der Fall, d. h. stehen die nötigen Schlüssel nicht zur Verfügung, so muss es möglichst schwer sein, Informationen entschlüsseln oder im Falle von Signaturen manipulieren zu können. Um quantenresistente Verfahren zu ermöglichen, benötigt man also mathematische Probleme, die sich eignen, um Kryptosysteme zu bauen, für die man weder klassische Möglichkeiten, noch Quantenalgorithmen kennt, die diese Aufgaben für einen Angreifer mit akzeptablem Aufwand lösen können.

Ein weiter Weg für Forschung und Praxis

Die mathematischen Grundlagen, die man diesbezüglich untersucht, sind zumeist nicht neu, allerdings fanden viele bisher keine Anwendung in der Kryptografie oder wurden in diesem Kontext lange Zeit nicht näher beachtet, weil beispielsweise der benötigte Speicherbedarf und die Rechenleistung zur Zeit ihrer Erfindung oft nicht verfügbar waren.

Auch heute haben diese Verfahren noch einen weiten Weg vor sich. Teils ist weitere Forschung nötig, um die Verfahren zu verbessern oder ihre Eigenschaften sowie ihre Sicherheit ausreichend zu verstehen. Möglichst viele Experten sollten sie untersuchen und testen. Die Verfahren müssen normiert und implementiert werden. Des Weiteren muss Praxiserfahrung gesammelt werden. Der Prozess, bis sich neue Verfahren in der Praxis etabliert haben, kann sich über einen langen Zeitraum von zehn bis 15 Jahren oder mehr ziehen.

Experten gehen davon aus, dass die Chancen relativ gut stehen, zwischen 2030 und 2040 über Quantencomputer von praktikabler Größe zu verfügen. Daher muss man bereits jetzt damit beginnen, sich um die Integration von quantenresistenten Verfahren in die heutigen Infrastrukturen zu kümmern. Dabei sind nicht nur die Verfahren selbst zu betrachten. In der Praxis werden viele Protokolle zur Kommunikation, z. B. über das Internet verwendet. Auch diese müssen den Bedürfnissen und Eigenheiten der neuen Verfahrensarten angepasst werden, da z. B. der Speicher- und Rechenbedarf in der Regel größer sind, als bei klassischen Verfahren.

Die Sicherheit neuer Verfahren nachweisen

Gegenüber Neuerungen gibt es gerade im sicherheitskritischen Umfeld eine durchaus gesunde Skepsis. Es bleibt uns allerdings keine Alternative, als endlich neue kryptografische Verfahren einzusetzen, denn auch Angriffe mit den heutigen Möglichkeiten werden immer besser bzw. die verfügbare Rechenleistung wird immer größer.

Doch warum sind die neuen Verfahren sicher? Und warum sind die aktuell verwendeten Verfahren sicher, zumindest bei Verwendung ausreichend starker Schlüssel? Die Antwort ist dieselbe: Weil wir derzeit keinen öffentlich bekannten Weg kennen, diese Verfahren mit akzeptablem Aufwand zu knacken. Ein wichtiges Merkmal für die Sicherheit von Verfahren sind daher die besten, bekannten Angriffe. Diese können sehr spezifisch auf bestimmte Algorithmen abzielen, sowohl auf die Theorie des Verfahrens selbst, als auch auf die Implementierungen, z. B. über sog. Seitenkanäle. Eine häufige Betrachtungsweise zielt hingegen auf ganze Verfahrensarten ab und ist damit generisch.

Heutzutage versucht man, die Sicherheit konkreter Verfahren meist mit mathematischen Beweisen zu untermauern. Dies ist allerdings diffizil. Beweise zu führen ist eine Kunst für sich, doch die verschiedenen Modelle können die Realität auch nur bedingt abbilden. Daher kann es etwa vorkommen, dass ein Verfahren in einem Beweismodell als sicher anzusehen ist, jedoch Angriffe gefunden werden können, die von diesem Modell einfach nicht abgedeckt werden. Sind alle bekannten Angriffe auf ein Verfahren handhabbar, so gilt es als in der Praxis sicher.

Für die neuen Post-Quantum Verfahren fehlt uns leider die Erfahrung, sowohl in der Beweisführung für Quantenmodelle, als auch zur Sicherheit der verwendeten, neuen Primitive bzw. kryptografischen Basisbausteine. Daher arbeiten derzeit hunderte Kryptologen weltweit daran, das Wissen und das Verständnis bezüglich dieser neuen Verfahren zu verbessern. Das amerikanische National Institute of Standards and Technology (NIST) hat deshalb einen Standardisierungsprozess ausgerufen, der inzwischen in vollem Gange ist. Dort konnten 2017 Verfahren eingereicht werden, die nun detailliert untersucht und bei positiver Eignung standardisiert und für bestimmte Anwendungsfälle empfohlen werden sollen.

Ein Beispiel aus der Praxis

Auch wenn es weitere Ideen gibt, beschäftigt man sich im Bereich der Post-Quantum Kryptografie derzeit überwiegend mit fünf Kategorien:

  • Gitter
  • fehlerkorrigierende Codes
  • multivariate Gleichungssysteme
  • Isogenien supersingulärer Kurven
  • Hash-Funktionen

Eine sehr interessante Verfahrensart sind zuletzt genannte Hash-basierte Signaturen, denn die Sicherheit dieser ist bereits heute relativ gut verstanden, insbesondere die generischen Angriffe auf das verwendete Kryptoprimitiv bzw. den Basisbaustein: Hash-Funktionen.

Sichere UpdatesUpdates für Lösungen von genua sind trotz der Gefahr von Quantencomputern sicher

Mithilfe Hash-basierter Verfahren, wie dem in RFC8391 spezifiziertem eXtended Merkle Signature Scheme (XMSS) [3] lassen sich ausschließlich Signaturen erstellen. Ein dafür prädestiniertes Anwendungsszenario sind Update-Signaturen. Bereits in den 1970ern entwickelte Ralph Merkle die Grundlagen [4], doch die Anforderungen an Speicher und Leistung schienen für die damaligen Computer noch  unpraktikabel.

Anfang der 2000er nahmen sich Akademiker des Wissens an und verbesserten diese Verfahrensart immer weiter. Vor allem an der TU Darmstadt wurden am Lehrstuhl von Prof. Johannes Buchmann große Fortschritte erzielt und die Verfahren immer weiter verbessert. Das Ergebnis war das Verfahren XMSS. In einem dreijährigen Forschungsprojekt mit der genua GmbH konnten letzte Fragen zum korrekten und sicheren Einsatz des Verfahrens geklärt werden.

Im Projekt wurde auch der Prozess für eine Veröffentlichung als RFC der IETF/IRTF gestartet und konnte in einer Kooperation mit der TU Eindhoven im Jahre 2018 erfolgreich abgeschlossen werden. Inzwischen liefert genua neben klassischen Signaturen für ihre Softwareupdates zusätzlich eine quantenresistente Alternative in Form einer XMSS-Signatur mit aus. Ein System kann mithilfe dieses hybriden Vorgehens zwei Signaturen prüfen und sowohl einem altbekannten Verfahren, als auch einem neuen Post-Quantum Algorithmus vertrauen. Updates lassen sich so trotz der Gefahr von Quantencomputern sicher verteilen.

[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, arXiv:quant-ph/9508027v2

[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] Andreas Huelsing, Denis Butin, Stefan-Lukas Gazdag, Joost Rijneveld und Aziz Mohaisen: RFC 8391; XMSS: eXtended Merkle Signature Scheme; IETF/IRTF; Mai 2018; https://rfc-editor.org/rfc/rfc8391.txt

[4] Ralph C. Merkle: A Certified Digital Signature; Advances in Cryptology – Crypto ‚89; 9th Annual International Cryptology Conference; pp. 218-238; August 1989; Springer

 

Bildquelle: © kras99, Igor - Fotolia.com


Lesen Sie auch

Diskutieren Sie mit

Sie können diesen Artikel sofort ohne Registrierung als Gast-User kommentieren.

Registrieren Sie sich jetzt! Mit einem User Account genießen Sie Vorteile:
Ihr Kommentar wird sofort im genublog veröffentlicht und Sie werden über Reaktionen auf Ihre Kommentare informiert.

Bereits registrierte User gelangen hier zum Login.



Registrieren Sie sich jetzt! Mit einem User Account genießen Sie Vorteile:
Ihr Kommentar wird sofort im genublog veröffentlicht und Sie werden über Reaktionen auf Ihre Kommentare informiert.

Bereits registrierte User gelangen hier zum Login.

Um für Sie unsere Webseite zu optimieren, verwenden wir Cookies.
Klicken Sie auf "Cookies zulassen", falls Sie der Nutzung von diesen Cookies zustimmen.
Weitere Informationen dazu finden Sie in unserer Datenschutzerklärung, in der Sie auch jederzeit Ihre Cookie-Einstellungen einsehen und anpassen können.
Datenschutz Cookies akzeptieren