Kryptographie Wo schwierige Probleme hilfreich sind
Alle Welt verlässt sich auf einen bestimmten Signaturstandard. 25 Jahre lang hat man ihm blind vertraut.
Sichere Webseiten, E-Mail-Verschlüsselung, Online-Banking, Kryptowährungen wie Bitcoin – überall im Internet arbeitet der Signaturstandard ECDSA (Elliptic Curve Digital Signature Algorithm). Seit seiner Einführung 1992 ist er nahezu unverändert im Einsatz. Erst 25 Jahre später haben Mathematiker der RUB seine Sicherheit belegen können.
„Wir waren selbst überrascht, dass sich noch nie jemand eingehend mit dem Thema befasst hatte“, sagt Manuel Fersch, der seine Doktorarbeit am Lehrstuhl für Kryptographie schreibt. Ein Jahr Arbeit investierten er, sein Doktorvater Prof. Dr. Eike Kiltz und Dr. Bertram Poettering in die Prüfung des Signaturverfahrens, das wie eine digitale Unterschrift funktioniert. Sie weist die Identität eines Akteurs nach, ist untrennbar mit dem signierten Dokument verwoben und kann nicht auf andere Dokumente übertragen werden, und sie ist durch jeden überprüfbar. Herzstück des Ganzen ist ein Algorithmus, also eine festgelegte Abfolge definierter Rechenschritte.
Ein schwieriges Problem
Wie kann man nun beweisen, dass ein solches Verfahren sicher ist? „Auf formale Art wurde ECDSA noch nie gebrochen“, so Manuel Fersch. Aber das heißt nicht, dass das nicht theoretisch möglich ist.
Um die Sicherheit zu belegen, betrachten die Mathematiker den Algorithmus als eine abstrakte mathematische Konstruktion. Das Brechen des Algorithmus muss mindestens so schwer sein wie das Lösen eines gut untersuchten, schwierigen mathematischen Problems, dann gilt er als sicher.
Ein solch schwieriges Problem ist zum Beispiel die sogenannte Faktorisierung von Zahlen in Primfaktoren: Bis heute ist kein effizientes Verfahren bekannt, das es ermöglicht, zu einer gegebenen Zahl eine kleinere Zahl zu finden, die diese teilt.
Gedachter Angreifer will fälschen
Die Forscher denken sich nun einen hypothetischen beliebigen Angreifer aus, der den Algorithmus brechen will. Er verfügt über heute übliche Ressourcen, das heißt bestimmte Rechenkapazitäten und eine begrenzte Laufzeit, außerdem über den öffentlichen Schlüssel des ECDSA-Algorithmus. Als zusätzliche Insiderinformation darf er den Signaturalgorithmus bei der Arbeit beobachten: Er sieht also in ausgewählten Fällen, was signiert werden soll und die zugehörige Signatur.
Gelingt es ihm, am Ende der Laufzeit eine Nachricht mit gültiger Signatur auszugeben, hat er eine gelungene Fälschung erzeugt und somit das Signaturverfahren gebrochen.
Als nächster Schritt des Sicherheitsbeweises muss das schwierige Problem ins Spiel kommen, und somit ein weiterer Algorithmus, den die Forscher konstruieren. Dieser neue Algorithmus enthält den Angreifer, und er muss zugleich das schwierige Problem lösen. „Dieser Algorithmus, die sogenannte Reduktion, ist unsere eigentliche Arbeit“, erklärt Manuel Fersch. „Er muss möglichst effizient sein und eine enge Beziehung zwischen dem Angreifer und dem mathematischen Problem herstellen.“
Allgemeiner Sicherheitsbeweis für mehrere Verfahren
Was am Schluss dabei herauskommt, ist eine Erfolgswahrscheinlichkeit. Idealerweise entspricht die Erfolgswahrscheinlichkeit für die Lösung des schwierigen Problems derjenigen des Angreifers, das Verfahren zu brechen – dann ist der Algorithmus dazwischen gut konstruiert und die Sicherheit des Verfahrens ist belegt. Gemeinsam mit Eike Kiltz und Bertram Poettering ist das Manuel Fersch gelungen.
In zwei Publikationen – einer bei der führenden internationalen Sicherheitskonferenz CCS 2016, und einer bei einer Konferenz über theoretische Kryptographie, der TCC 2017 – berichteten sie von ihrer Arbeit.
Inzwischen hat Fersch die Verallgemeinerung des Sicherheitsbeweises ins Auge gefasst. „Es gibt verschiedene andere Signaturstandards, zum Beispiel einen russischen und einen chinesischen, die im Prinzip dem ECDSA sehr ähnlich sind. Der Rumpf ist nahezu gleich“, erklärt er. Mittlerweile gelang ihm ein allgemeiner Sicherheitsbeweis, der für alle diese Standards gilt.
Der wunde Punkt
„Der wunde Punkt ist das schwierige mathematische Problem, das dem Beweis zugrunde liegt“, sagt Manuel Fersch. „Wenn das effizient lösbar ist, gerät alles ins Wanken. Dann ist kein kryptographisches Verfahren, dessen Sicherheit auf diesem Problem beruht, mehr sicher.“ Mit Blick auf mögliche Quantencomputer, die die Leistung heutiger Rechner bei weitem übertreffen würden, ist das für die Zukunft nicht unwahrscheinlich. Daher forschen Mathematiker schon heute an Verfahren, die auf Problemen beruhen, von denen man annimmt, dass auch Quantencomputer sie nicht effizienter lösen können als klassische Computer.
