Camillo
Aus ProgrammingWiki
Inhaltsverzeichnis |
Post-Quanten-Algorithmen
Einführung
Quantencomputer können gängige Verschlüsselungsmethoden in Zukunft vielleicht einfach angreifen. Deshalb wird in der Kryptografie nach neuen Algorithmen gesucht, denen Quanten-Hacks nichts anhaben können.
Einwegfunktionen
Moderne Verschlüsselungsverfahren basieren häufig auf Einwegfunktionen . Das sind Funktionen, die sich einfach berechnen, jedoch schwer umkehren lassen. $17 \cdot 41 = 697$ kann zum Beispiel relativ einfach mit schriftlicher Multiplikation ermittelt werden, während sich die Bestimmung der Faktoren von $697$ als schwierig gestaltet. Die Funktion wird also zur Verschlüsselung der Information verwendet, die Umkehrung entspräche der Entschlüsselung. Der Empfänger verfügt dabei über eine sogenannte Falltür, eine Zusatzinformation (einen Schlüssel), der die Schwierigkeit der Umkehrung erheblich vermindert. Im Beispiel würde die Kenntnis des Faktors $17$ die Ermittlung des anderen Faktors mit schriftlicher Division erheblich vereinfachen.
Schwächen der üblichen Verschlüsselungsverfahren
Die Stärke der Einwegfunktionen üblicher Verfahren wie RSA oder Verfahren mit elliptischen Kurven ist nicht sicher nachvollziehbar. Sie vertrauen nur darauf, dass bis jetzt keine effiziente Handlungsvorschrift bekannt ist, um ihre Funktionen umzukehren. Bis zum jetzigen Zeitpunkt wurde noch keine bewiesen sichere Einwegfunktion gefunden, es ist sogar nicht einmal bekannt, ob eine solche Funktion überhaupt existiert. Alle gängigen Verschlüsselungsverfahren sind also prinzipiell lösbar, wobei die Komplexität dieser Lösung bei den Verfahren unterschiedlich hoch ist. Bei vielen Verfahren lässt sich die Komplexität jedoch nicht einwandfrei herleiten, weshalb man auf Erfahrungswerte und Schätzungen angewiesen ist, die davon ausgehen, dass der Aufwand der Lösung zu groß ist, um einen Angriff zu ermöglichen.
Bedrohung durch Quantencomputer
Quantencomputer arbeiten statt mit Bits, die die Werte 0 und 1 annehmen können, mit Qubits. Diese können mehrere Zustände gleichzeitig annehmen und sich verschränken und damit mehrere Berechnungen simultan ausführen. Das erlaubt neue Arten von Algorithmen, die schwere Probleme effizient lösen können. Ein Beispiel ist der Shor-Algorithmus, der mit geringem Aufwand Primfaktoren einer Zahl findet. Diese Algorithmen wären in der Lage, Verfahren wie RSA oder elliptische Kurven effizient anzugreifen, diese Verfahren verfügen dann also nicht mehr über starke Einwegfunktionen.
Im Moment existiert noch kein Quantencomputer, der groß genug ist, um den Shor-Algorithmus auszuführen, die US-amerikanische Behörde für Standardisierung (NIST) schätzt jedoch, dass das in 30 bis 50 Jahren der Fall sein könnte. Ab diesem Zeitpunkt ist das RSA-Verfahren anfällig für Angriffe und es muss eine Alternative gefunden werden. Doch Hacker können schon jetzt verschlüsselte Informationen abgreifen und diese später entschlüsseln. Diese Technik ist als harvest now, decrypt later bekannt. Deshalb muss so schnell wie möglich ein Verfahren mit wirklicher Einwegfunktion gefunden werden.
Neue Lösungsansätze
Um die Suche nach neuen Verschlüsselungsalgorithmen zu beschleunigen, organisierte die NIST 2016 einen Wettbewerb für sichere Algorithmen, die als Ersatz für die gängigen Verfahren infrage kommen. In einem langen Prüfungsprozess haben sich folgende Verfahren herauskristallisiert.
Codebasierte Kryptografie
Die codebasierte Kryptografie verwendet Methoden aus der Fehlerkorrektur, die zum Beispiel bei der Rekonstruktion von Daten auf einer Festplatte zum Einsatz kommen. Der Nachricht wird mit Fehlern versehen, die schwer zu korrigieren sind, wenn nicht weitere Informationen über die Art der Fehler vorliegen (die Falltür des Systems). Codebasierte Verfahren gehören erwiesenermaßen zu einer höheren Komplexitätsklasse, sind also schwieriger zu knacken. Sie sind auch im Gegensatz zu anderen präsentierten Verfahren relativ schnell ausführbar, benötigen jedoch viel Speicher und haben einen großen Datenaufwand (z.B. Schlüssel mit Größen im Megabytebereich).
Gitterbasierte Kryptografie
Diese Art der Kryptografie beruht auf dem Gitterproblem, in dem zu einem Knoten in einem Gitter der nächstgelegene Knoten gefunden werden muss. Was für zweidimensionale Gitter einfach ist, gestaltet sich ohne Zusatzinformationen für mehrere hundert Dimensionen als schwierig. Diese Art der Verschlüsselung hat den Wettbewerb gewonnen, unter anderem deshalb, weil sie schon seit mehreren Jahrzehnten bekannt ist und noch kein Weg gefunden wurde, sie effizient anzugreifen. Deshalb gilt sie als relativ sicher. Eine belastbare Begründung dafür gibt es allerdings nicht. Für das Verfahren spricht jedoch, dass es einfach in Computersysteme einsetzbar ist, was die schnelle Umstellung erleichtern könnte.
Isogenienbasierte Kryptographie
Diese Art der Kryptografie ist relativ neu und stellt auch nur einen Ersatzposten in der Liste des NIST. Er basiert auf Abbildungen zwischen elliptischen Kurven und gilt im Gegensatz zu den üblichen elliptischen Kurven als sicher vor Quantenalgorithmen. Praktische Vorteile wären kurze Schlüssel und der Umstand, dass das spätere Aufdecken eines Schlüssels früher codierte Nachrichten nicht entschlüsselt. Da das Verfahren noch sehr jung ist, stehen weitere Prüfungen jedoch noch aus.
Standardisierung der Verfahren
Damit die neuen Verschlüsselungsverfahren großflächig angewendet werden können, müssen Standards geschaffen werden, damit auch organisationsübergreifend mit ihnen kommuniziert werden kann. Bis 2024 will die NIST für die Gewinner des Wettbewerbes einen Standard erarbeiten und empfielt dringend, diesen so schnell wie möglich umzusetzen, damit für die Übergangsphase genug Zeit bleibt.
Quellen
- Manon Bischoff. "Schutz vor Quantenhackern". In: Spektrum der Wissenschaft (Septemper 2022), S. 12
- Erika Klarreich. "Auf der Jagd nach unknackbaren Funktionen". In: Spektrum der Wissenschaft (Oktober 2022), S. 62
- Tobias Nießen. Post-Quanten-Kryptografie: Codebasierte Verfahren. Leibniz-Universität Hannover, 2018
