- In Local-First-Software werden homomorphe Verschlüsselung (Homomorphic Encryption) und CRDTs kombiniert, um die Sicherheit kollaborativer Dokumente zu wahren
- Ende-zu-Ende-Verschlüsselung allein erlaubt es dem Server nicht, Daten zusammenzuführen, wodurch Einschränkungen bei Synchronisierung und Effizienz von Updates entstehen
- Homomorphe Verschlüsselung ist eine Technik, die die Ausführung von Programmen ermöglicht, sodass ein Server CRDT-Updates zusammenführen kann, ohne den Inhalt zu kennen
- Aufgrund der grundlegenden Grenzen homomorpher Verschlüsselung (Leistungseinbußen, höherer Speicher- und Rechenaufwand, Notwendigkeit des Worst-Case-Verhaltens im Code) gibt es bei der praktischen Anwendung erhebliche Schwierigkeiten
- Es wird an verschiedenen Ansätzen geforscht, um CRDTs und sichere Berechnungen zusammenzubringen; eine vollständige Lösung gibt es bislang nicht
Local-First und die Herausforderungen sicherer Zusammenarbeit
- Bei Remote-Zusammenarbeit werden Dokumente im Local-First-Ansatz als CRDT gespeichert und per Synchronisierung gemeinsam bearbeitet
- Wenn es Sicherheitsanforderungen gibt, bei denen Dokumentinhalte niemals Dritten wie etwa App-Entwicklern offengelegt werden dürfen, wird häufig Ende-zu-Ende-Verschlüsselung eingesetzt
- Ende-zu-Ende-Verschlüsselung ist zwar einfach im Verhalten, doch weil der Sync-Server die Daten nicht zusammenführen kann, entsteht bei langer asynchroner Arbeit ineffiziente Datenkommunikation
Was ist homomorphe Verschlüsselung?
- Homomorphe Verschlüsselung ist ein spezielles Verschlüsselungsverfahren, das die direkte Ausführung von Algorithmen auf verschlüsselten Daten ermöglicht
- Damit kann ein Synchronisierungsserver CRDT-Updates zusammenführen, ohne den Inhalt der Daten zu kennen
- Je nach den unterstützten Operationen wird zwischen partiell homomorph (nur Addition oder Multiplikation), etwas/leveled homomorph (beides nur begrenzt oft) und voll homomorph (ohne Einschränkung) unterschieden
- Mit zunehmender Zahl von Operationen sammelt sich Rauschen im Chiffretext an, was die Entschlüsselung erschwert und fortgeschrittene Techniken wie Bootstrapping erforderlich macht
- Auf der Ebene verschlüsselter Bits (0/1) lassen sich allgemeine boolesche Schaltungen allein durch Kombination grundlegender Gatter wie XOR und AND umsetzen
Praxisbeispiel einer homomorph verschlüsselten CRDT-Implementierung
- Mit der Rust-basierten Bibliothek TFHE-rs wurde eine typische CRDT namens Last Write Wins Register homomorph verschlüsselt implementiert
- Die Felder und Methoden (Verschlüsselung/Entschlüsselung) der Klartext- und der verschlüsselten Struktur sind fast identisch, doch in der eigentlichen Merge-Logik treten wichtige Unterschiede auf
- Da Verzweigungen im Ausführungspfad wie
if/else oder match Hinweise auf die Entschlüsselung von Chiffretexten geben können, ist in verschlüsselten Umgebungen ein Ansatz nötig, bei dem alle Verzweigungen und Schleifen sofort ausgewertet werden
- Zentrale Bedingungsvergleiche und Merge-Operationen werden vollständig über bitweise FheBool-Operatoren und Methoden wie
select verarbeitet, sodass von außen nicht erkennbar ist, unter welcher Bedingung sich ein Wert geändert hat
Grundlegende Grenzen homomorpher Verschlüsselung
- Ungleichgewicht zwischen Schlüssel- und Datengröße: Im Beispiel werden für 32 Byte Daten 123 MB Serverschlüssel benötigt (selbst komprimiert noch 27 MB), was zu gravierender Speicherineffizienz führt
- Leistungseinbruch: Das Merge einer homomorph verschlüsselten CRDT wurde mit rund 1 Sekunde gemessen und ist damit etwa 2 Milliarden Mal langsamer als ohne Verschlüsselung
- Wenn sich Schleifen und Verzweigungen je nach Eingabewert ändern, kommt es zu Informationslecks; deshalb müssen Rechenaufwand und Speicherverbrauch immer am Worst Case ausgerichtet werden
- Bei einem Last-Write-Wins-Map mit spärlichen Key-Value-Daten müssen zum Beispiel trotzdem alle Schlüssel in fester Größe vollständig aufgefüllt zusammengeführt werden, was die praktische Skalierbarkeit verschlechtert
- Die Struktur des Chiffretexts und die Änderungshistorie müssen so gestaltet sein, dass ein externer Beobachter nicht ableiten kann, ob sich Werte verändert haben oder welcher Teil aktualisiert wurde
Fazit und Ausblick
- CRDTs und homomorphe Verschlüsselung lassen sich theoretisch gut kombinieren, praktisch gibt es jedoch bei Speicher- und Zeiteffizienz sowie der Programmstruktur schwerwiegende Einschränkungen
- Derzeit gibt es noch keine vollständig praktikable Lösung, aber auch CRDTs selbst sind eine vergleichsweise junge Technologie, zu der kontinuierlich geforscht wird
- Für innovative Lösungen, die in Local-First-Kollaborations-Apps Sicherheit und Nutzbarkeit in Einklang bringen, besteht weiterhin Potenzial
1 Kommentare
Hacker-News-Kommentare
Es stimmt zwar, dass Fully Homomorphic Encryption ein wirklich langsames und ineffizientes Feld ist, aber man sollte erwähnen, dass dieses Gebiet selbst ein vergleichsweise junger Bereich ist, der erst 2009 aufkam. Der Fortschritt in den letzten 15 Jahren ist wirklich enorm: Die ersten homomorphen Verschlüsselungsschemata benötigten Schlüssel im TB-/PB-Bereich, und Bootstrapping (eine in der homomorphen Verschlüsselung unverzichtbare Operation, wenn viele Multiplikationen anfallen) dauerte Tausende Stunden. Heute liegen die Schlüssel bei etwa 30 MB, und Bootstrapping ist in unter 0,1 Sekunden möglich. Ich hoffe, dass sich das weiter verbessert und irgendwann praktisch nutzbar wird.
Auch frühe CRDTs (CRDT: Conflict-free Replicated Data Type) waren wie WOOT extrem unpraktisch, aber moderne CRDT-Datenbanken haben heute bei der Performance gegenüber einem typischen LSM keinen allzu großen Nachteil mehr. RDX-CRDTs arbeiten zum Beispiel mit einem Algorithmus ähnlich Merge Sort und sind alle O(N). Auch der Metadaten-Overhead ist in den meisten Implementierungen gut kontrolliert. Siehe WOOT, librdx, go-rdx.
Aufgrund der Architektur von CRDTs sind sie zwangsläufig langsam, und selbst die besten Algorithmen sind strukturell teuer. Wenn man dann noch homomorphe Verschlüsselung hinzufügt, wird die Herausforderung deutlich größer. Es ist wirklich beeindruckend, aber ich frage mich, ob das in der Praxis brauchbar ist. Als Beleg für diese Behauptung wird die Erklärung zitiert: „Damit der Server eine neue Map berechnen kann, muss er alle Schlüssel einzeln zusammenführen und anschließend die gesamte Map an jeden Peer senden — aus Sicht des Servers ist die gesamte Map jedes Mal anders.“
CRDT steht für Conflict-free Replicated Data Type, also einen speziellen Datentyp, mit dem verteilte Synchronisation ohne Konflikte möglich ist. Siehe CRDT-Wikipedia-Link.
Im Artikel wird erwähnt, dass die Performance unzureichend sei. Tatsächlich dauert das Mergen eines Last-Write-Wins-Registers auf einem M4 MacBook Pro in einer normalen Ausführung 0,52 Nanosekunden, während die homomorph verschlüsselte Version 1,06 Sekunden benötigt. Das heißt, die Rechengeschwindigkeit unterscheidet sich um den Faktor 2 Milliarden. Das ist wirklich schockierend.
FHE (Full Homomorphic Encryption) ist wirklich langsam, aber seit 2009 gab es erstaunliche Fortschritte. Allein die Bootstrapping-Geschwindigkeit ist um zig Millionen Mal schneller geworden. Mit tfhe-rs wurde bereits sogar AES-128 auf Basis homomorpher Verschlüsselung demonstriert. Ich denke, dass die Möglichkeit eines Echtzeit-Einsatzes von FHE für KI-Inferenz und -Training zunehmend realistischer wird. Siehe tfhe-aes-128 GitHub-Link.
Ich kann der Aussage nicht zustimmen, dass der Server die Änderungen der Clients nicht mehr verstehen könne. Der Server schickt den Nutzern nur die Änderungen, die sie noch nicht gesehen haben, und die Nutzer entschlüsseln und mergen diese, um die neueste Version des Dokuments zu erstellen. Homomorphe Verschlüsselung ist zwar interessant, aber in Situationen, in denen vernünftige Performance oder Bandbreite nötig sind, ist sie fast nie geeignet. Ich habe früher einmal ein Paper über vollständig vertrauliches Computing auf Basis homomorpher Verschlüsselung gesehen, bei dem eine benutzerdefinierte CPU+RAM kryptografisch codiert und pro Taktsignal genau eine Instruktion verarbeitet wurde. Es funktioniert tatsächlich, aber nur in einer Größenordnung von einer virtuellen CPU-Instruktion pro Sekunde. Wenn man mit solchem Tempo und solchen Kosten leben kann, ist es klüger, es einfach lokal auszuführen — oder, wenn man wirklich reich ist, die Hardware selbst zu kaufen und es lokal zu betreiben.
Informatik- und Kryptografie-Paper behandeln oft Forschung, die weit von der Praxis entfernt ist, etwa absurd unrealistische Arbeiten wie die Reduktion der Angriffskomplexität von 2^250 auf 2^230. Solche Forschung ist trotzdem sinnvoll für echte R&D oder um den Bereich des Machbaren zu erweitern.
Wenn der Server den Inhalt nicht direkt verarbeiten kann, kann er CRDT-Dokumente nicht zusammenführen und muss jedes Mal den gesamten Zustand des CRDT empfangen und wieder versenden. Wenn dein Freund gleichzeitig online ist, kann man Operationen schicken und in Echtzeit mergen, aber andernfalls ist das sehr ineffizient.
Ich frage mich, ob es vertrauenswürdig wäre, wenn Studierende mit FHE verschlüsselten WASM- oder JS-Bewertungscode auf ihren Chromebooks direkt mit einer Kombination aus JupyterLite und ottergrader ausführen. Ich frage mich auch, wie sich das zu Codesigning und dem SETI@home-Screensaver verhält.
THFE-rs sollte man besser nicht verwenden, da Zama dafür außerhalb von Prototyping-Zwecken eine kommerzielle Lizenz verlangt. Die Lizenzbedingungen sind umständlich. Stattdessen würde ich die Bibliotheken openFHE (C++) und lattigo (golang) empfehlen, die beide kommerziell frei nutzbar sind.
Ich denke, FHE ist hier grundsätzlich das falsche Werkzeug. FHE eignet sich für Daten, die einem zentralen Server gehören oder die dieser kennt. Hier müssen jedoch mehrere Nutzer gemeinsam verteilte Daten verarbeiten, daher ist MPC (Multi-Party Computation: eine Methode, bei der mehrere Teilnehmer mit jeweils geheimen Daten gemeinsam Berechnungen durchführen, etwa Summen bilden) deutlich effizienter.
Ich verstehe die im Artikel präsentierte Annahme nicht ganz. Ich kenne die Konzepte von CRDTs und homomorpher Verschlüsselung, aber ich frage mich, warum beide Seiten zum Synchronisieren gleichzeitig online sein müssen. Mit einem asynchronen „Store-and-Forward“-Modell könnte man Updates doch austauschen, während die Daten unterwegs verschlüsselt bleiben. Warum muss der Server überhaupt den Zustand halten — noch dazu verschlüsselt — und warum muss er so modifiziert werden, wie vorgeschlagen?
Die Kombination aus der Langsamkeit und Ineffizienz von FHE mit der Platzverschwendung von CRDTs wirkt auf mich irgendwie amüsant.