Wer den Zufall beherrscht, hat die Macht. Vom Münzwurf, der entscheidet, welche Sportmannschaft den Ball bekommt, bis hin zu den zufällig erzeugten Schlüsseln, die Geldtransfers absichern: Der Zufall lässt uns Entscheidungen treffen, die fair und nicht vorhersehbar sind.

Bei vielen Computeranwendungen ist es jedoch schwierig, geeignete Zufallszahlen zu erzeugen. Deshalb verlassen sich Fachleute oft auf sogenannte Hashfunktionen, die Daten durcheinanderwirbeln und so aufbereiten, dass eine zufällig wirkende Zeichenfolge entsteht. Seit Jahrzehnten geht man davon aus, dass sich die Ausgaben geeigneter Hashfunktionen praktisch nicht von echten Zufallszahlen unterscheiden lassen - eine Annahme, die als Zufallsorakel-Modell bekannt ist (Englisch: random oracle model). »Es ist schwer, heute eine kryptografische Anwendung zu finden, deren Sicherheitsanalyse nicht auf diesem Modell beruht«, sagt Computerwissenschaftler Ran Canetti von der Boston University.

Doch Anfang des Jahres 2025 hat eine Veröffentlichung diese Annahme erschüttert. Dmitry Khovratovich von der Ethereum Foundation, Ron Rothblum von der Firma Succinct und dem Technion in Haifa und Lev Soukhanov vom Start-up [[alloc] init] haben eine Methode gefunden, mit der man ein System dazu bringen kann, falsche Aussagen zu verifizieren - und das, obwohl es gemäß des Zufallsorakel-Modells nachweislich sicher ist. »Ich hatte das Gefühl, dass mir jemand den Boden unter den Füßen wegzieht«, sagt Eylon Yogev von der Bar-Ilan-Universität in Israel.

»Es geht dabei um eine Menge Geld«Eylon Yogev, Informatiker

Die betroffenen Systeme sind unter anderem für Blockchains unerlässlich, da sie Berechnungen von externen Servern bestätigen. »Es geht dabei um eine Menge Geld«, sagt Yogev. »Bei Blockchain-Beweisprotokollen haben Angreifer eine große Motivation, die Sicherheit des Systems zu brechen.« Deswegen haben Yogev und andere Informatiker sofort versucht, die offengelegten Schwachstellen zu beheben. Aber das Problem sei noch lange nicht gelöst. Canetti ist der Meinung, dass man das gesamte Zufallsorakel-Modell überdenken muss.

Wie man einen Hörsaal voller Menschen überzeugt

Bei vielen digitalen Anwendungen geht es darum, eine Gruppe von Fremden davon zu überzeugen, dass man eine Berechnung korrekt durchgeführt hat. Häufig wird dafür die sogenannte Fiat-Shamir-Transformation eingesetzt. Man findet sie nicht nur bei Blockchains und Cloud Computing, sondern auch bei kryptografischen Anwendungen wie dem Schlüsselaustausch, der Webtransaktionen sichert und Textnachrichten verschlüsselt. Diese Transformation steht durch die neue Arbeit unter Beschuss.

Die Fiat-Shamir-Transformation ermöglicht es, eine »interaktive« Beweismethode - die in der Praxis nur schwer umsetzbar ist - in eine nichtinteraktive umzuwandeln. Um das zu verstehen, hilft ein Beispiel: Angenommen, eine Professorin gibt einem Studenten 100 Hausaufgaben auf, möchte aber nicht jedes einzelne Ergebnis prüfen müssen. Um seine Leistung dennoch zu bewerten, kann sie zehn Aufgaben zufällig auswählen. Wenn die Antworten auf diese zehn Aufgaben richtig sind, kann die Professorin davon ausgehen, dass auch die meisten anderen Aufgaben korrekt gelöst wurden.

Bei der Fiat-Shamir-Transformation geht es nicht nur darum, eine Person zu überzeugen, sondern viele unabhängige. Daher kann man das obige Szenario etwas abwandeln: Der Student will nicht nur seine Professorin von der Richtigkeit seiner Hausaufgaben überzeugen, sondern einen ganzen Hörsaal voller Menschen. Der Student könnte dafür seine Lösungen in separate Briefumschläge packen. Dann zieht die Professorin zehn Zahlen aus einem Hut, der Zettel mit Zahlen von 1 bis 100 umfasst. Der Student öffnet dann die dazugehörigen zehn Umschläge und die Professorin bewertet den Inhalt.

Diese Prozedur wird aber vielleicht nicht alle Menschen im Hörsaal überzeugen. Es könnte ja sein, dass der Student die Professorin bestochen hat, damit sie nur bestimmte Zahlen in den Hut wirft - und nicht alle von 1 bis 100. Oder der Student könnte die Briefumschläge mit Schlitzen versehen haben, sodass ein Komplize hinter den Kulissen die Aufgaben eilig lösen kann und die Antworten unbemerkt in die richtigen Umschläge steckt, bevor sie geöffnet werden. Um solche Betrugsfälle auszuschließen, müsste jede Person im Hörsaal selbst mit dem Studenten interagieren, um wirklich überzeugt zu sein. Doch die Fiat-Shamir-Transformation schafft Abhilfe - und greift dafür auf Hashfunktionen zurück.

Ein mathematischer Mixer

Eine Hashfunktion ist wie ein mathematischer Mixer: Sie wirbelt Daten gemäß einer ausgewählten Reihe von Operationen durcheinander und gibt dann einen kleinen Teil davon aus. Für kryptografische Zwecke bieten Hashfunktionen zwei Vorteile. Erstens geben sie ein zufällig erscheinendes Kauderwelsch aus, das in keinem offensichtlichen Zusammenhang mit der ursprünglichen Eingabe steht. Und zweitens lässt sich eine Hashfunktion schnell ausführen, ist aber schwer umkehrbar. Wenn Ihnen jemand eine Ausgabe zeigt, ist es praktisch unmöglich, die dazugehörige Eingabe zu finden - umgekehrt lässt sich die Ausgabe aber schnell berechnen.

Im genannten Beispiel mit den Hausaufgaben kann der Student den Zuhörern versichern, dass die Umschläge keine Schlitze enthalten, indem er sie mit einer Hashfunktion verschließt: Dazu erzeugt er zu jeder seiner 100 Antworten den »Hash« (die Ausgabe einer Hashfunktion) und schreibt das Ergebnis auf den entsprechenden Umschlag. Wenn ein Komplize versuchen würde, den Inhalt des Umschlags im Nachhinein zu ändern, stimmt das Ergebnis nicht mit dem Hash überein: Da sich Hashfunktionen schnell berechnen lassen, können das die Personen im Hörsaal leicht überprüfen.

1986 schlugen Amos Fiat und Adi Shamir vor, mit Hashfunktionen auch den anderen Betrugsfall auszuräumen: dass der Student die Professorin bestechen könnte, um nur bestimmte Umschläge auszuwählen. Im Fiat-Shamir-Protokoll zieht die Professorin keine Zahlen aus einem Hut, sondern erzeugt die zufälligen Zahlen mit einer Hashfunktion. Zunächst übergibt sie einen generierten Hash, der auf einem Briefumschlag des Studenten steht, in eine Hashfunktion, um eine neue Zeichenfolge zu erhalten. Dann wandelt sie diese mithilfe einer zuvor vereinbarten Formel in eine Zahl zwischen 1 und 100 um. Diese bestimmt, welchen Umschlag sie zuerst öffnet. Dann wiederholt sie den Vorgang: Die Professorin übergibt sowohl den Hash als auch die Antwort aus dem ersten Umschlag der Hashfunktion, um den zweiten Briefumschlag auszuwählen und so weiter.

Dieser Ansatz macht die Interaktion zwischen dem Studenten und der Professorin (oder einem anderen Zuhörer im Hörsaal) überflüssig. Der Student kann mit der Hashfunktion selbstständig die Zufallsaufgaben auswählen - und jeder im Publikum kann sich davon überzeugen, dass er das korrekt und ohne Betrug getan hat.

Die Fiat-Shamir-Transformation wandelt also interaktive in nichtinteraktive Beweise um. Damit können Computer Beweise führen, die jeder Nutzer jederzeit prüfen kann, ohne sich mit dem Beweisführer austauschen zu müssen. Das bietet enorme Vorteile, weshalb die Transformation praktisch überall eingesetzt wurde. Aber ist sie wirklich sicher? Oder lässt sie sich ausnutzen, um Menschen von einer falschen Aussage zu überzeugen?

Wie man eine Lüge beweist

1996 bewiesen David Pointcheval und Jacques Stern, dass Fiat-Shamir im Zufallsorakel-Modell sicher ist: Wenn man davon ausgeht, dass die Ausgaben von Hashfunktionen rein zufällige Werte erzeugen, ist die Transformation nicht angreifbar. Aber reale Hashes sind nicht wirklich zufällig. Fachleute befürchteten daher, dass ein cleverer Angreifer die Sicherheit von Fiat-Shamir brechen könnte, indem er die Details einer bestimmten Hashfunktion ausnutzt.

In den frühen 2000er Jahren zeigtenInformatiker, wie das gelingen kann. Sie entwickelten interaktive Beweisprotokolle, die so speziell sind, dass sie unter einer Fiat-Shamir-Transformation versagen. »Aber niemand, der bei Verstand ist, würde ein Protokoll auf diese Weise entwerfen«, sagt Canetti. Viele Programmierer gingen deshalb davon aus, dass kein reales Protokoll für einen solchen Angriff anfällig sein könnte - und integrierten die Fiat-Shamir-Transformation in die Informationsaustauschsysteme im Internet. Es war ein Vertrauensvorschuss, erklärt Canetti.

Doch einige Fachleute hatten ernsthafte Vorbehalte dagegen. Ron Rothblum zum Beispiel versucht schon lange, ein reales Protokoll anzugreifen. Im Oktober 2024 erhielt er eine E-Mail von der Ethereum Foundation, einer Blockchain-Organisation, welche die weitverbreitete Kryptowährung Ether hostet.

Die Blockchains, die Kryptowährungen zugrunde liegen, haben einen unausweichlichen Nachteil: Sie sind sehr langsam. Um den hohen Datenverkehr bei Finanztransaktionen zu bewältigen, muss eine Blockchain die meisten Berechnungen an externe Computer auslagern. Da man nicht davon ausgehen kann, dass diese Computer vertrauenswürdig sind, stellt das Fiat-Shamir-Protokoll die Gültigkeit ihrer Berechnungen sicher. Wenn jemand mit dem Fiat-Shamir-Verfahren eine Aussage wie »Person A hat Person B eine Million US-Dollar geschickt« beweisen könnte, obwohl sie falsch ist, würde das gesamte Währungssystem zusammenbrechen.

Da so viel von diesen Beweisprotokollen abhängt, beschloss die Ethereum Foundation, deren Sicherheit zu testen. Sie wollte ein Preisgeld für die Person ausschreiben, die das Fiat-Shamir-Verfahren für ein beliebiges Beweisprotokoll mit einer beliebten Hashfunktion namens Poseidon angreifen kann. Vor der Ankündigung des Wettbewerbs lud die Stiftung Rothblum ein, den Entwurf der Ausschreibung zu prüfen.

Rothblum erklärte, die Stiftung habe die Bedingungen zu locker formuliert. Schließlich wissen Kryptografen seit Jahrzehnten, dass konstruierte Beweisprotokolle anfällig sind - unabhängig von der gewählten Hashfunktion. Doch Rothblum stellte überrascht fest, dass viele der Ethereum-Entwickler nicht mit diesen Arbeiten vertraut waren. Daraufhin begann der Informatiker, sich tiefergehender mit Khovratovich und Soukhanov, die damals bei Ethereum arbeiteten, in die früheren Arbeiten zu vertiefen.

Soukhanov schlug vor, ein Fiat-Shamir-Beweissystem zu untersuchen, das auf dem GKR-Protokoll basiert, das Rothblums Bruder Guy Rothblum mitentwickelt hat (er steht für das R in GKR). Das Protokoll bestätigt die Ausgabe eines Computerprogramms, das diese nur dann erzeugt, wenn es eine bestimmte geheime Eingabe erhält. Wenn Sie zum Beispiel ein Programm zur Bewertung von Hausaufgaben haben, könnte ein Student dieses Protokoll verwenden, um zu beweisen: Wenn man die richtigen Antworten in das Bewertungsprogramm eingibt, gibt das Programm die Ausgabe »richtig« aus.

Um eine solche Behauptung zu überprüfen, erzeugt das GKR-Protokoll zunächst den Hash des Programms (zum Beispiel des Bewertungsprogramms). Auf diese Weise kann der Student später nicht heimlich ein anderes Programm anwenden. Als Nächstes führt das Protokoll weitere Hashes durch, um zufällige Tests zu machen - Schritte in der Programmausführung, die das Protokoll überprüft.

Doch Rothblum, Khovratovich und Soukhanov fanden heraus, dass dieses Protokoll Schwachstellen hat. Sie entwickelten ein Programm, zu dem sie den eigenen Hash berechneten. Daraus war es in der Lage, die zufälligen Tests und die internen Abläufe so zu gestalten, dass sie immer die Überprüfung bestehen. Es gäbe keinen Zweifel daran, dass das Programm wirklich das ausgibt, was behauptet wird - auch wenn das gar nicht stimmt.

Und wie die drei Forscher gezeigt haben, lässt sich dieses bösartige Programm in eine beliebige Aufgabe einbetten. Wenn man zum Beispiel fälschlicherweise beweisen will, dass man eine Hausaufgabe gelöst hat, kann man das Bewertungsprogramm durch ein neues ersetzen, welches das Schadprogramm enthält. Das neue Programm ist immer noch ein gültiges Bewertungsprogramm: Es erzeugt genau die gleichen Bewertungen wie das ursprüngliche - und doch kann man es mit einer Reihe falscher Antworten füttern und dann das GKR-Protokoll verwenden, um jeden davon zu überzeugen, dass das Programm »richtig« ausgibt, obwohl es in Wirklichkeit »falsch« anzeigt.

Ein unsicheres Verfahren

Die Firma Polyhedra bietet eine Version des von den Forschern angegriffenen Beweissystems unter dem Namen Expander an. Als die Informatiker Ende Januar 2025 kurz davorstanden, ihre Arbeit online zu veröffentlichen, benachrichtigten sie Polyhedra. Sie hatten während ihrer Forschung eine Modifikation des Fiat-Shamir-Protokolls gefunden, um den Angriff abzuwenden. Diese hat Polyhedra genutzt, um einen Patch für die Software zu veröffentlichen. Einen Monat später fanden Yogev und Gal Arnon vom Simons Institute for the Theory of Computing eine weitere Möglichkeit, das Fiat-Shamir-Verfahren anzupassen, um es gegen den neuen Angriff zu schützen.

Beide Änderungen nutzen die Tatsache, dass das bösartige Programm den Code für die Hashfunktion enthalten muss, um die zufälligen Tests zu berechnen. Die modifizierten Versionen erfordern daher, dass das zu prüfende Programm weniger komplex ist als der Hash, damit es das Schadprogramm nicht enthalten kann.

Aber nicht alle Anwendungen können diese Anforderung erfüllen. Und selbst wenn einige Protokolle auf eine modifizierte Version von Fiat-Shamir umsteigen, heiße das nicht, dass es keinen weiteren Angriff gibt, warnt Rothblum. »Das macht uns als Kryptografen sehr unglücklich.«

Der Informatiker Justin Thaler von der Georgetown University sorgt sich aktuell mehr über mögliche Fehler in den bestehenden Fiat-Shamir-Implementierungen als über den neuen Angriff. Doch solange es keine Klarheit über die Gefährlichkeit des neuen Angriffs gibt, »werde ich nachts nicht gut schlafen können«, ergänzt er.

»Der Angriff könnte leicht dazu benutzt werden, um tatsächlich Geld zu stehlen«Eylon Yogev, Informatiker

Andere Forscher zeigen sich alarmierter. Laut Canetti ist es üblich, dass Programmierer ihren Code anpassen, damit er auf verschiedenen Betriebssystemen funktioniert. Komplexer Code kann schwer zu überprüfen sein, wodurch ein Angreifer in der Lage sein könnte, das bösartige Programm unbemerkt einzuschleusen. »Ich denke, dass es sich um eine ernstzunehmende Bedrohung handelt«, sagt er.

Yogev stimmt dem zu. »Wenn man erst einmal eine Lücke gefunden hat, weiß man, dass das System undicht ist«, sagt er. »Ich glaube, der Angriff könnte leicht dazu benutzt werden, um tatsächlich Geld zu stehlen.« Selbst wenn dieser Fall nicht eintritt, hat der Angriff das Vertrauen der Kryptografen in das Fiat-Shamir-Protokoll und in das Zufallsorakel-Modell im Allgemeinen erschüttert. »Vielleicht ist es an der Zeit, viele andere Dinge, von denen wir glauben, dass wir sie bewiesen haben, zu überdenken und zu revidieren«, so Canetti.