Große Kryptowährungen und etablierte Banken haben Bulletproofs, ein Protokollschema für Beweise über homomorph verschlüsselte Daten, in ihr Zahlungssystem integriert.
Die Entdecker des Schemas, Bünz et al., haben 2023 mit dem Entwurf einer Erweiterung, die sich für anonymisierte Kommunikation einsetzen lässt, nachgelegt.
In meiner Masterarbeit (Englisch)
Dieser Logbucheintrag beleuchtet diese Arbeit aus meiner persönlichen Perspektive. Ich wage einen Blick über den Tellerrand der theoretischen Informatik hinaus und gehe auf meine Motivation und gewonnenen Erkenntnisse ein, die für andere von Nutzen sein können.
Inhalt:
- Forschungsgebiet Kryptographie
- Der nächste Hype? Der Weg hin zu anonymen Nachrichtensystemen
- Irrelevant für den Hype: Funktionsweise
- Mein Beitrag
Forschungsgebiet Kryptographie
Gegenstand der Kryptographie ist der Schutz von Daten vor Manipulation und unbefugtem Lesen. Dafür ist nicht nur die Verschlüsselung, sondern auch die Signierung von Daten erforderlich. In einigen Anwendungsfällen sollen außerdem zugehörige Metadaten wie beispielsweise die Identität von Absender und Empfänger, der Zeitpunkt der Übermittlung und die Datenmenge geheim gehalten werden.
Die Anwendungen von Kryptographie finden sich bereits in der alltäglichen Kommunikation per Text, Telefon und Video oder dem Speichern und Archivieren von Daten. Unverzichtbar ist Kryptographie im Bankenwesen und für verteilte Kassenbücher (Distributed Ledger). Diese wenigen Beispiele zeigen bereits, dass die Kryptographie ein weltumspannender und in sehr viele Lebens- und Geschäftsbereiche hineinragender Markt ist. Ebenso verhält es sich mit dem eng verwandten Gegenspieler der Kryptographie, der Kryptoanalyse, die sich mit dem Knacken und der Manipulation von verschlüsselten Daten beschäftigt.
(Symbolbild mit KI erstellt)
Recht und Relevanz
Haftungsausschluss: Dieser Abschnitt stellt keine Rechtsberatung dar.
Achtung: In vielen Jurisdiktionen wird die Verwendung von Kryptographie gesetzlich eingeschränkt.
In Deutschland sind das Brief-, Post-, und Fernmeldegeheimnis durch Verankerung im Grundgesetz verfassungsrechtlich garantiert. In Anbetracht der technischen Entwicklung seit Inkrafttreten dieser Rechte werden sie mittlerweile auch als Telekommunikationsgeheimnis bezeichnet. Zusätzlich bestehen völkerrechtliche Verträge, die den Schriftverkehr vor willkürlichen oder rechtswidrigen Eingriffen schützen. Aus der Sicht des Staatsbürgers handelt es sich bei diesen Grundrechten nicht nur um Abwehrrechte gegen die Überwachung durch Einzelpersonen, Unternehmen und Institutionen, sondern auch gegen den Staat. Zum Schutzbereich gehören nicht nur die Inhalte ausgetauschter Nachrichten, sondern ebenfalls die bereits erwähnten Metadaten.
Die Geschichte der Rechtsvorschriften zum Schutz der Korrespondenz reicht in Deutschland über 300 Jahre zurück. Zu dieser Geschichte gehört, dass dieser Schutz bis heute durch Gesetze und Behörden eingeschränkt wird — je nach herrschendem Zeitgeist unterschiedlich stark. Zuletzt wurde das Grundgesetz 1968 nach einer langen Debatte als Teil der Notstandsgesetze geändert. Die verantwortlichen Politiker standen damals unter einem hohen Rechtfertigungsdruck, nicht nur durch die dauernden Straßenaufstände in der Zeit der Anbahnung dieser Gesetze. Die vor knapp 60 Jahren hinzugefügten Teile in Artikel 10 des Grundgesetzes sind kursiv markiert:
Steht eine Verletzung des Telekommunikationsgeheimnisses im Raum, muss dies vor Gericht nachgewiesen werden, um tatsächlich Recht zu bekommen. In der Praxis ist das häufig schwierig bis unmöglich. Deshalb ist es für den Einzelnen erstrebenswert, das Grundrecht auf private Korrespondenz durch technische Maßnahmen abzusichern. Zwar ist das Angebot für verschlüsselte Kommunikation heutzutage sehr breit, aber die Metadaten werden meist wenig bis gar nicht geschützt. Letzteres ist nicht nur weit aufwändiger und weniger erforscht als die bloße Verschlüsselung des Inhaltes, sondern es war bis vor kurzer Zeit kein allgemeines Verfahren bekannt, das kryptographisch gegen Manipulationssicherheit geschützt ist und Anonymität garantieren kann. Mit dem Multi-Key Verifiable Shuffle von Bünz (und meinen Ergänzungen) ist es mittlerweile möglich, Sender- und Empfängerdaten zu verschleiern und die kryptographische Sicherheit des Gesamtsystems unter wenigen Grundannahmen zu beweisen.
Nach Rechtsprechung des Bundesverfassungsgerichtes besteht zusätzlich zum Telekommunikationsgeheimnis ein Recht auf informationelle Selbstbestimmung, und zwar als ein Datenschutz-Grundrecht, welches nicht im Grundgesetz erwähnt wird. Auch dieses Grundrecht lässt sich unabhängig von den Gerichten mit Hilfe von Kryptographie realisieren. Ein Beispiel dafür ist die Verschlüsselung von Datenträgern. Dieses Recht spielt für die Anwendung von Multi-Key Shuffles für anonyme Kommunikation jedoch eine untergeordnete Rolle und wird in diesem Logbucheintrag deshalb nicht weiter analysiert.
Der Sicherheitsbegriff in der Kryptographie
Während eine erschöpfende Untersuchung der rechtlichen Rahmenbedingungen von Datensicherheit und Kryptographie sehr kompliziert ist und zusätzlich abhängig von der jeweiligen Jurisdiktion angestellt werden müsste, sind der Sicherheitsbegriff in der Kryptographie und die Kryptographie als Teilgebiet der Mathematik universell gültig und gründen sich auf eine kleine Zahl von Definitionen und Grundannahmen. Diese sind zwar sehr komplex, aber von ihrer Natur sind sie rein mathematisch. Sie können deshalb dazu verwendet werden, die Sicherheit von Verschlüsselungsschemen, zu denen auch die Multi-Key Shuffles gehören, formell zu beweisen.
Um die Sicherheit eines real genutzten Kryptosystems zu untersuchen, ist es erforderlich, den Sicherheitsbegriff um informations- und ingenieurstechnische Kategorien zu erweitern. So lässt sich bei Beachtung der eingesetzten Rechen- und Kommunikationsgeräte für jedes denkbare Angriffsszenario die Sicherheit strikt definieren, vorhersagen und garantieren.
Diese strengen Sicherheitsgarantien sind es, die die Kryptographie zu einem der mächtigsten Werkzeuge der Informatik machen. Kryptographie ist zeitlos und hat bereits eine lange Geschichte hinter sich, die weit über das Computerzeitalter hinausgeht — sie ist fast so alt wie die Schrift selbst. Ihr großes praktisches Potenzial hat sich zuletzt wieder bei der Distributed-Ledger-Technologie gezeigt. Es ist sehr wahrscheinlich, dass die Innovation dort nicht enden, sondern sich auf viele weitere Geschäfts- und Lebensbereiche ausweiten wird.
Der nächste Hype? Der Weg hin zu anonymen Nachrichtensystemen
Die Anforderungen an einen sicheren Nachrichten- und Zahlungsverkehr gleichen sich in vielen Punkten: Bei beiden soll der Inhalt ohne Veränderung durch Dritte, nur für Sender und Empfänger einsehbar und gegebenenfalls auch nicht nachverfolgbar (anonym) übermittelt werden. Es drängt sich der Gedanke auf, dass Konzepte von anonymen Kryptowährungen für anonymisierte Kommunikation angepasst werden könnten.
(Kryptojubel – Symbolbild mit KI erstellt)
Sowohl in der Forschung als auch in der Welt der Kryptowährungen haben Bünz et al. mit der Vorstellung von Bulletproofs gesorgt. Bulletproofs wurden von vielen Kryptowährungen und Banken zügig in ihre Protokolle integriert. Das Bulletproof-Schema ermöglicht es mit hoher Effizienz beim Energie- und Speicherplatzverbrauch, Eigenschaften von verschlüsselten Daten zu beweisen, ohne diese verraten zu müssen (Nullwissen-/Zero-Knowledge-Beweis). Zudem benötigen Bulletproofs keine vertrauenswürdige Initialisierung (trusted setup), wie sie für zk-SNARKs erforderlich sind. Beispielsweise kann ein Kontoinhaber mit einem Zero-Knowledge-Beweis zeigen, dass sein Kontostand für eine Zahlung ausreichend ist, ohne dem Zahlungsdienstleister bzw. Kryptowährungs-Knoten oder dem Empfänger seinen Kontostand offenlegen zu müssen.
Mit Bulletproofs lassen sich aber auch komplexere Bedingungen als ein ausreichender Kontostand beweisen. Zum Beispiel ist es möglich zu zeigen, dass zwei Listen, die die gleichen Zahlen in unterschiedlicher Reihenfolge enthalten, aber unterschiedlich verschlüsselt sind, tatsächlich den gleichen Inhalt haben (Beweis einer Permutation). Und an dieser Stelle wurden viele Kryptographen hellhörig: Könnte man diesen Permutationsbeweis dazu verwenden, eine Liste verschlüsselter Nachrichten zu mischen, während man gleichzeitig die Korrektheit des Mischvorganges, also die Manipulationssicherheit, beweisen kann, ohne die tatsächliche Mischreihenfolge offenzulegen? Würde man mehrere solche Mischer hintereinander schalten, ließe sich daraus ein Mischer-Netzwerk (mix-net) bauen, welches alle Sicherheitseigenschaften, die in Fachkreisen für einen anonymisierten Nachrichtenverkehr verlangt werden, einschließlich der Manipulationssicherheit, erfüllt.
Die Schwierigkeit bei der Umsetzung dieser Idee besteht darin, dass die verschlüsselten Nachrichten beim Mischen neu verschlüsselt werden müssen, damit die Ein- und Ausgaben eines Mischers nicht einander zugeordnet werden können.
Andernfalls ginge die Anonymität verloren.
Damit der Empfänger die für ihn bestimmte Nachricht dennoch lesen kann, müssten Informationen über die Neuverschlüsselung dem Empfänger jedoch sicher und anonym zugestellt werden — ein Zirkelschluss, der mit dem Bulletproofs-Schema von 2017 bisher von niemandem, der mir bekannt wäre, aufgelöst wurde.
Mit einer Modifikation der Bulletproofs, die das Nachrichtensystem und die zugehörige Neuverschlüsselung von Grund auf integriert, lässt sich dies realisieren, wie Bünz et al. in ihrem Paper-Draft von 2023
Irrelevant für den Hype: Funktionsweise
Dieser Abschnitt gibt einen groben Überblick über die Funktionsweise des Multi-Key Shuffle. Für detaillierte Erklärungen verweise ich auf meine Masterarbeit und die Transkripte im Abschnitt Implementierung.
Der Multi-Key Verifiable Shuffle mischt ElGamal-Chiffren mit Nachricht im Exponenten zusammen mit den öffentlichen Schlüsseln des Absenders und des vorgesehenen Empfängers, wobei zusätzlich eine Neuverschlüsselung all dieser Teile der Gesamtnachricht mit dem nur dem Mischer bekannten Faktor s vorgenommen wird. Der Mischer verkündet den zu s passenden öffentlichen Schlüssel g^s, den die Empfänger unter Zuhilfenahme ihres privaten Schlüssels verwenden, um die an sie gerichtete Nachricht in der Ausgabe des Mischers zu identifizieren und zu entschlüsseln. Der mitgesendete öffentliche Schlüssel des Senders erlaubt es dem Empfänger außerdem, eine Antwortnachricht zu verfassen, die durch den Mischer zurückgeleitet und mit dem umgekehrten Faktor 1/s (öffentlicher Schlüssel g^(1/s)) neuverschlüsselt wird. Der Empfänger kann die Nachricht des Senders dann entschlüsseln — und das Spiel beginnt von vorne. Üblicherweise werden zur Verbesserung der Anonymität mehrere Mischer mit nicht konvergenten Interessen hintereinander geschaltet, sodass bereits ein einziger ehrlich agierender Mischer (das heißt er generiert tatsächlich eine zufällige Mischung und ein zufälliges s) genügt, damit die Anonymität der Nachrichten gewährleistet ist.
Die Manipulationssicherheit der Nachrichten wird vom Mischer durch einen Zero-Knowledge-Beweis für die Korrektheit der Mischung (Permutation) und Neuverschlüsselung mit Hilfe eines Beschränkungssystems vom Rang 1 (rank 1 constraint system, R1CS) ähnlich wie bei Bulletproofs gewährleistet:
- Der Mischer legt sich auf die Permutation fest, indem er sie mit kryptographischen Pseudo-Zufallszahlen zu Pedersen-Commitments kombiniert. Auf s legt er sich durch das einfach Commitment g^s fest.
- Die durchgeführte Permutation und Neuverschlüsselung mit s der Nachrichten werden als Beschränkungen durch lineare Gleichungen ausgedrückt und zu einem Hadamard-Produkt umgewandelt. Ein Hadamard-Produkt ist das zeilenweisen Produkt mehrerer Vektoren. Mit einem Polynom-Test werden alle Beschränkungen, die für eine korrekte Permutation und Neuverschlüsselung mit s erfüllt sein müssen, zu einem inneren Produkt von der Größe der Permutation und weiteren (Pedersen-)Commitments zusammengeführt.
- Dieses innere Produkt lässt sich in einen Zero-Knowledge-Beweis von logarithmischer Größe umwandeln. Zusammen mit den zuvor erzeugten Commitments bildet dies den Zero-Knowledge-Beweis für die Korrektheit des Misch- und Neuverschlüsselungsvorganges.
Ein solcher Zero-Knowledge-Beweis wird vom Mischer bei jedem Mischvorgang neu erzeugt und veröffentlicht. Dieser Beweis kann von jedem verifiziert werden, der überprüfen möchte, ob der Mischer korrekt gearbeitet hat.
Zukunftsaussichten
(Schlapphut - Symbolbild mit KI erstellt)
Für die Verschlüsselung von Nachrichteninhalten herrscht heute ein starkes Bewusstsein, während das Problem der Metadatenverschlüsselung unabhängig davon weiterbesteht. Ein System, das Metadaten so sicher wie die kommunizierten Inhalte verschlüsselt, ermöglicht volle Datensouveränität, und verspricht deshalb ein hohes Nutzerpotenzial. Selbst wenn dieser große Markt von Regierungen für Bürger und Unternehmen eingeschränkt werden würde, wären Akteure, die solcher Regulation nicht unterliegen oder ihr entgehen können, mit Sicherheit an diesen Lösungen interessiert.
Multi-Key Shuffles nutzen den diskreten Logarithmus als kryptographische Falltür. Deshalb wären sie nicht sicher vor dem Angriff eines hinreichend starken Quantencomputers. Es wurde bis heute allerdings kein einziger Quantencomputer vorgestellt, der nur annähernd groß genug wäre, damit Shors Algorithmus für diskrete Logarithmen darauf hätte laufen können. Es ist davon auszugehen, dass Multi-Key Shuffles mindestens für die jüngere Zukunft vor Quantencomputern sicher sein werden. Der Multi-Key Shuffle stellt einen großen Fortschritt für anonymisierte Kommunikation dar und macht Hoffnung auf weitere Innovationen.
Mein Beitrag
Der Entwurf von Bünz et al. wurde bisher von den Autoren nicht in einer Endversion veröffentlicht. Er enthielt wenige kleine Ungenauigkeiten, die ich recht schnell beseitigen konnte, aber auch eine größere Auslassung: Es fehlte ein Zero-Knowledge-Hilfsprotokoll, mit dem bewiesen werden kann, dass eine geheime Zahl die n-te Potenz einer anderen geheimen Zahl ist (Potenz-Protokoll). Dieses Protokoll konnte ich auf Grundlage des Bulletproofs Range Proof und des schon bestehenden Multi-Key Shuffle Protokolles entwickeln und integrieren.
Hindernisse und deren Überwindung
Am schwierigsten war es für mich, den Jargon für Korrektheits- und Sicherheitsbeweise in der Kryptographie zu erlernen. Ich wollte nicht nur das Potenz-Protokoll entwickeln, sondern auch seine Sicherheitseigenschaften formell beweisen. Folgende Definitionen musste ich dafür anwenden und in Bezug auf das Potenz-Protokoll beweisen:
- IND-CPA privacy (Vertraulichkeit)
- Perfect Completeness (Jedes tatsächliche n-te-Potenz-Verhältnis zwischen zwei geheimen Zahlen lässt sich mit dem Protokoll beweisen)
- SHVZK under Subversion of the CRS (Ein Potenz-Beweis kann effizient simuliert werden und ist äußerlich ununterscheidbar von einem tatsächlich geführten Potenz-Beweis. Durch einen Potenz-Beweis werden keine Informationen über die geheimen Zahlen offengelegt außer dem tatsächlichen Potenz-Verhältnis zwischen diesen Zahlen.)
- Computational Witness-Extended Emulation (Es ist mit begrenztem Rechenaufwand nicht möglich, einen Beweis für zwei geheime Zahlen, die nicht in einem Potenz-Verhältnis stehen, zu erzeugen. Dies zu zeigen war recht aufwändig.)
Bevor ich diese Beweise geführt habe, wollte ich den Multi-Key Shuffle vollständig, mit gut lesbarem Code, ausführlicher Dokumentation und größtmöglicher Benutzerfreundlichkeit implementiert haben. Ich hatte mit Mathematica bereits Erfahrungen in der Implementierung von Zero-Knowledge-Protokollen gemacht und wollte früheren Code gerne wiederverwenden. Außerdem bot Mathematica Optionen zur Verwendung von mathematischen Symbolen als Variablen und zur Gestaltung von Dokumentation in Notebooks, die es in anderen Programmiersprachen nicht gibt. Ich hielt an Mathematica fest und stelle im Nachhinein fest: Es war für meinen sehr speziellen Anwendungsfall im Bildungsumfeld genau die richtige Entscheidung.
Aus der Perspektive des Softwareentwicklers hätte ich aber eine andere Sprache wählen wollen. Mathematica bietet von Haus aus keine Bibliotheken für Kryptographie, die im Umfeld von Zero-Knowledge-Beweisen benötigt wird. Die Erzeugung von Schnorrprimzahlen habe ich selbst implementiert und für elliptischen Kurven habe ich eine externe Bibliothek angepasst. Für die Abstraktionen von Sigma-Protokollen wie sie im Multi-Key Shuffle und im Potenz-Protokoll benötigt werden, habe ich eine eigene Sammlung von Hilfsfunktionen geschrieben. Dazu gehören eine Konfigurations- und Initialisierungsverwaltung, Ereignisbehandlung, Loglevels, eine Zustandsmaschine für das gesamte Protokoll, Speicherung von Kommunikationsaufwand, Fiat-Shamir-Transformation mit Entropie-Prüfung und Zustandsverwaltung, Nachrichten-Parsing und Funktionen für den Empfang von Nachrichten über TCP/IP.
Die Beschränkungen der Netzwerk-Bibliotheken in Mathematica haben mich dazu gezwungen, mich von der Implementierung einer Peer-To-Peer-Anwendung abzuwenden und stattdessen einen Nachrichtenbroker einzuführen, den ich aufgrund der Vielzahl an verfügbaren Bibliotheken und schnellen Entwicklungszeit für Prototypen in Python geschrieben habe. Wer den Server-Quellcode liest, kann auch erkennen, dass dieser Server mitsamt des Kommunikationsprotokolles bis zum Schluss ein Prototyp geblieben ist - ein robuster Prototyp. Die Einführung des Nachrichtenbrokers als man-in-the-middle hatte den Vorteil, dass die im Protokoll gesendeten Daten für eine schnelle Introspektion auf einem Webserver veröffentlicht werden können. Mit Websockets und Javascript ließ sich eine Netzseite mit Live-Updates über den Protokollstatus einfach und schlank realisieren.
Implementierung
Die Implementierung des Multi-Key Shuffle lässt sich am besten am Beispiel von Protokoll-Transkripten in Mathematica für
- Mischer mit Sender- und Empfänger-Komponenten
- Mischer (Prover, führt den Zero-Knowledge-Beweis)
- Sender (Users)
- Empfänger (Users)
- Beweis-Verifizierer (Verifier) nachvollziehen: