Warum heutige Krypto-Standards in Zukunft nicht mehr sicher sein werden

IT-Sicherheit basiert zu einem sehr grossen Teil auf zuverlässigen und sicheren kryptographischen Verfahren, welche standardisiert sind und in Sicherheitsanwendungen weltweit eingesetzt werden. Diese Verfahren stützen sich auf der Schwierigkeit der Berechnung von gewissen algebraischen Problemen ab und verwenden Methoden basierend auf komplexen mathematischen Strukturen (Ringe, elliptische Kurven, endliche Körper). Beispielsweise wird der Umstand, dass die Multiplikation von zwei grossen Primzahlen (1’000-stellig) einfach ist, die Zerlegung dieses Produkts in zwei Primfaktoren jedoch auf heutiger Computer-Infrastruktur praktisch unmöglich ist, im bekannten RSA PKI Algorithmus eingesetzt.

Quantencomputer funktionieren fundamental anders als Von Neumann Architekturen und werden in der Lage sein, die heute als «schwierig» geltenden algebraischen Probleme in Zukunft zu lösen, d.h. die aktuell gängigen Verfahren werden nicht mehr sicher sein. Der Shor-Algorithmus wird auf einem Quantencomputer grosse Zahlen in polynomialer Zeit in deren Primfaktoren zerlegen können, und damit die heutigen Public-Private-Key Verfahren knacken können. Gemäss Experten-Schätzungen dürfte dies bereits 2030 der Fall sein.

Quantencomputer basieren auf Quantenmechanik und Quantenbits (Qubit). Ein Qubit kann gleichzeitig die binären Zustände 0 und 1 einnehmen, und erst beim Auslesen wird der Status definitiv bestimmt. Ein Quantum-Byte (8 Bit) kann also gleichzeitig 256 Werte darstellen. Diese «Gleichzeitigkeit» ist die grosse Stärke von Quantencomputern, da so parallel Berechnungen durchgeführt werden können, für die es genau eine Lösung gibt, wie z.B. die Zerlegung in Primfaktoren, die Suche nach einem Element in einer Menge oder generell die Suche nach optimalen Lösungen in mehrdimensionalen Problemen. Heute forschen u.a. IBM, Google und auch die NASA an der Entwicklung von Quantencomputern.


Gitterbasierte Kryptographie und andere Kandidaten für quantensichere Verfahren

Sogenannte quantensichere Kryptographie oder post-quantum cryptography (PQC) muss auf neuen mathematischen Problemen basieren, die auch mit zukünftigen Quantencomputern und entsprechenden Algorithmen nicht gelöst werden können. Es wird aktuell davon ausgegangen, dass es mindestens sechs Arten von Ansätzen oder Suchfeldern für quantensichere Algorithmen gibt: lattice-based, code-based, hash-based, non-commutative, multi-variate und isogeny-basierte Verfahren.

Die meisten der aktuell vielversprechendsten Verfahren finden sich im Bereich der gitterbasierten (lattice-based) Kryptographie. Mathematische Gitter sind ein Teilbereich der Geometrie und werden seit Anfang der 90er-Jahre erforscht. Ein Gitter besteht aus Intersektions-Punkten von äquidistanten Linien und erstreckt sich unendlich in alle Richtungen. Basis-Vektoren mit hoher Anzahl Dimensionen (Hunderte bis Tausende) bestehend aus reinen Ganzzahl-Komponenten spannen das Gitter auf. In diesem Raum gibt es verschiedene Berechnungsprobleme, die auch mit Quantencomputern exponentielle Komplexität, also hohe Berechnungsschwierigkeit aufweisen.

Beispielsweise ist es schwierig, basierend auf einem beliebigen Punkt im N-dimensionalen Raum den nächsten Gitter-Punkt zu finden. Die Schwierigkeit des geometrischen Problems ist dabei direkt abhängig davon, ob man «gute» oder «schlechte» Basis-Vektoren für diesen Raum hat. Dieser Umstand wird z.B. im Goldreich-Goldwasser-Halevi (GGH) Schema verwendet, in dem «gute» Basis-Vektoren als private Schlüssel und «schlechte» Basis-Vektoren als öffentliche Schlüssel verwendet werden. Jedoch wurde bereits 1999 ein Design-Fehler in diesem Verfahren entdeckt, der es erlaubt, ein «schwieriges» Problem in ein «lösbares» Problem umzuwandeln.

«Learning with Errors» (LWE) ist ein anderes (und immer noch als komplex geltendes) Rechenproblem, das sich ebenfalls auf der Schwierigkeit von gitterbasierten Problemen abstützt. Hier werden überspezifizierte Gleichungssysteme verwendet und der private Schlüssel besteht aus der Lösung eines solchen Gleichungssystems, während der öffentliche Schlüssel aus einem Gleichungssystem mit «Fehlern» gebildet wird.


NIST Auswahl- und Standardisierungsprozess

Um die verschiedenen möglichen Ansätze für quantensichere kryptographische Verfahren vertieft zu prüfen und zukünftige Standards festzulegen, hat die US-Behörde NIST (National Institute for Standards and Technology) 2016 einen entsprechenden Auswahlprozess gestartet. Ziel ist es, von mathematischer Theorie zu konkret implementierbaren Standards für Software- und Hardware Lösungen zu gelangen. Dabei müssen auch Aussagen getroffen werden, ob Algorithmen und deren Implementationen mit Quantencomputern zu brechen sind, die heute noch gar nicht existieren.
Im 2017 wurden 69 Algorithmen als Kandidaten von verschiedenen Institutionen eingereicht, die nun über mehrere Runden ausgewertet werden. Aktuell sind noch 4 Finalisten im Bereich PKI (asymmetrische Verfahren) und 3 Finalisten für digitale Signaturen im Rennen. Darunter finden sich auch Verfahren, die am IBM Research Lab in Rüschlikon entwickelt wurden (CRYSTALS-Kyber und CRYSTALS-Dilithium). Diese Finalisten werden nun weiter geprüft und sollen bis 2024 in Standards gegossen werden. Von da an dürfte es dann nochmals ein paar Jahre dauern bis zur Adoption und Verbreitung in der Industrie. Die Zukunft ist jedoch schon teilweise hier: OpenSSH 9.0 verwendet ein hybrides quantensicheres Verfahren für den Schlüsselaustausch (NTRU mit X25519 ECD).