ADMIN

2023

03

2023-02-28T12:00:00

Hybrid Cloud

RUBRIKEN

97

Forschungslabor

Aus dem Forschungslabor Folge 51

Endgültig sicher

von John Pardey

Veröffentlicht in Ausgabe 03/2023 - RUBRIKEN

Das Verschlüsseln geheimer Inhalte ist kein Phänomen unserer Zeit – Kryptografen erfinden und knacken Codes schon seit Jahrtausenden. Erstaunlicherweise können Fachleute bis heute nicht abschließend sagen, ob eine unknackbare Verschlüsselung existiert. Woran das liegt und welche neuen Hinweise es auf eine komplett sichere Codierung gibt, verrät unser Forschungslabor.

 Vor etwa 50 Jahren zeigten Mathematiker erstmalig, dass es durchaus möglich ist, nachweislich sichere Chiffren zu erstellen. Die Voraussetzung dafür ist die sogenannte "Einwegfunktion", die leicht auszuführen, aber nicht oder zumindest nur sehr schwer umzukehren ist. Seitdem wurde eine breite Palette solcher Funktionen entwickelt, die auf einfacher Multiplikation basieren oder komplizierte geometrische sowie logarithmische Verfahren nutzen und sich aus heutiger Sicht nicht in absehbarer Zeit umkehren lassen. Internetprotokolle wie TLS hängen davon ab und erlauben, vertrauliche Daten sicher zu übermitteln.
Doch für keines der derzeit verwendeten Verfahren lässt sich endgültig beweisen, dass es sich tatsächlich um eine Einwegfunktion handelt. Schlimmer noch: Es ist nicht einmal bekannt, ob echte Einwegfunktionen existieren. Sollte das nicht der Fall sein, ist jede Art der Kryptografie im Prinzip angreifbar. Denn wenn ein Verschlüsselungsverfahren aktuell als sicher gilt, ist dies lediglich ein Erfahrungswert.
Sicherheit mit Einwegfunktionen
Rafael Pass und Yanyi Liu von der Cornell University fragten sich daher: "Gibt es ein Schlüsselargument, das uns verrät, ob sichere Kryptografie möglich ist?" Darauf haben die beiden nun eine eindeutige Antwort gefunden: Ja. Ob echte Einwegfunktionen existieren, so bewiesen sie, hängt von einem der ältesten und zentralsten Probleme eines anderen Bereichs der Computerwissenschaft ab, der Komplexitätstheorie.
 Vor etwa 50 Jahren zeigten Mathematiker erstmalig, dass es durchaus möglich ist, nachweislich sichere Chiffren zu erstellen. Die Voraussetzung dafür ist die sogenannte "Einwegfunktion", die leicht auszuführen, aber nicht oder zumindest nur sehr schwer umzukehren ist. Seitdem wurde eine breite Palette solcher Funktionen entwickelt, die auf einfacher Multiplikation basieren oder komplizierte geometrische sowie logarithmische Verfahren nutzen und sich aus heutiger Sicht nicht in absehbarer Zeit umkehren lassen. Internetprotokolle wie TLS hängen davon ab und erlauben, vertrauliche Daten sicher zu übermitteln.
Doch für keines der derzeit verwendeten Verfahren lässt sich endgültig beweisen, dass es sich tatsächlich um eine Einwegfunktion handelt. Schlimmer noch: Es ist nicht einmal bekannt, ob echte Einwegfunktionen existieren. Sollte das nicht der Fall sein, ist jede Art der Kryptografie im Prinzip angreifbar. Denn wenn ein Verschlüsselungsverfahren aktuell als sicher gilt, ist dies lediglich ein Erfahrungswert.
Sicherheit mit Einwegfunktionen
Rafael Pass und Yanyi Liu von der Cornell University fragten sich daher: "Gibt es ein Schlüsselargument, das uns verrät, ob sichere Kryptografie möglich ist?" Darauf haben die beiden nun eine eindeutige Antwort gefunden: Ja. Ob echte Einwegfunktionen existieren, so bewiesen sie, hängt von einem der ältesten und zentralsten Probleme eines anderen Bereichs der Computerwissenschaft ab, der Komplexitätstheorie.
Dabei geht es um die so genannte Kolmogorow-Komplexität, die ein Maß dafür darstellt, wie schwer es ist, zufällige Zahlenfolgen zu identifizieren. Wer sich für die Mathematik dahinter und die Details interessiert, wird unter [1] fündig. Die Forscher zeigten: Ist eine bestimmte Version der Komplexität schwer zu berechnen, existieren echte Einwegfunktionen. Wenn sie sich hingegen leicht bestimmen lässt, sind Einwegfunktionen ausgeschlossen – und damit auch sichere Verschlüsselungsverfahren.
Was ist eigentlich zufällig?
Die Kolmogorow-Komplexität entstand in den 1960er Jahren als eine Art Maß für Zufälligkeit. Und bereits 2004 stieß Pass als Doktorand auf den möglichen Zusammenhang zwischen Einwegfunktionen und besagter Zufälligkeit. Zwar kam er dabei fast 20 Jahre kaum voran, blieb dem Feld aber treu und traf schließlich Liu, mit dem er sich gemeinsam Fragen der Zufälligkeit widmete.
Zwar hat jeder eine Vorstellung davon, was mit Zufälligkeit gemeint ist. Dennoch ist das Phänomen schwer zu fassen. Ein Beispiel: Es ist nicht möglich, die Behauptung zu widerlegen, die beiden Zahlenfolgen 99999999 und 03729563 seien zufällig erzeugt. Dennoch fühlt sich die zweite zufälliger an. Um zufällige Zahlenfolgen besser zu verstehen, beschloss der sowjetische Mathematiker Andrei Kolmogorow in den 1960er Jahren, sich nicht auf den Prozess zu konzentrieren, der die Zahlen erzeugt, sondern auf die Art, sie zu beschreiben. Er definierte die Komplexität einer Folge als die Länge des kürzesten Algorithmus, der sie erzeugt.
Der Beweis
Eine Variante der Kolmogorow-Komplexität ermöglicht es dann zu berechnen, wie das effizienteste Programm aussieht, das eine zufällige Zeichenfolge erzeugt. Nun stellte sich den Wissenschaftlern die Frage: Wie einfach lässt sich die Komplexität berechnen? Wie Liu und Pass herausgefunden haben, ist genau das der Schlüssel zum Beweis der Existenz von Einwegfunktionen. Dabei ist nicht einmal notwendig, die Komplexität für alle denkbaren Zeichenketten zu bestimmen. Ist dies für einen Großteil möglich, kann es keine sichere Kryptografie geben. Ist dies hingegen unmöglich, existieren gemäß Pass und Liu echte Einwegfunktionen.
Dies hat eine regelrechte Flut von Forschungsarbeiten an der Schnittstelle zwischen Kryptografie und Komplexitätstheorie ausgelöst. Kryptografen haben gute Gründe zu glauben, dass es Einwegfunktionen gibt. Damit kämen wir einer absolut sicheren Kommunikation ein Stückchen näher.
Link-Codes Aufsatz von Pass und Liu n3s61