Circuit ORAM und praktische Leistung

Circuit ORAM, vorgeschlagen von Wang, Chan und Shi (2015), wurde entwickelt, um den Bandbreiten-Overhead zu minimieren und zugleich einfach in Frameworks für sichere Berechnungen (garbled circuits und secret sharing) implementierbar zu sein. Die wichtigste Neuerung besteht darin, die Bucket-Größe auf Z = 2 Blöcke zu reduzieren (im Vergleich zu Z = 5 bei Path ORAM), wodurch die Bandbreite halbiert und gleichzeitig eine vernachlässigbare Fehlerwahrscheinlichkeit beibehalten wird. Das Eviction-Verfahren wurde so umgestaltet, dass es sich als kleine boolesche Schaltung darstellen lässt.

Bei Path ORAM mit Z = 5 wird die Wahrscheinlichkeit eines Stash-Überlaufs dadurch kontrolliert, dass mehrere Blöcke pro Bucket vorhanden sind, um die zufällige Zuweisung von Blöcken zu Pfaden aufzunehmen. Circuit ORAM beweist, dass Z = 2 ausreicht, wenn statt einer zufälligen Verdrängung ein deterministisches Eviction-Verfahren (deep-first eviction) verwendet wird. Dadurch werden der Serverspeicher und der Kommunikations-Overhead gegenüber Path ORAM bei denselben Sicherheitsparametern halbiert.

Circuit ORAM wurde speziell für ein Eviction-Verfahren entwickelt, das sich als effiziente boolesche Schaltung darstellen lässt. In Protokollen für sichere Berechnungen (garbled circuits, SPDZ) muss der ORAM-Zugriff selbst oblivious ausgewertet werden – der Server, der die Berechnung durchführt, darf nicht erfahren, auf welche Speicherstelle zugegriffen wird. Die einfache deterministische Eviction-Schaltung von Circuit ORAM lässt sich wesentlich effizienter in eine Garbled Circuit überführen als das Eviction-Verfahren von Path ORAM.

Für eine Datenbank mit N Blöcken der Größe B Byte benötigt Circuit ORAM 2 * log N * B Byte pro Zugriff (Lesen und Schreiben eines Pfads mit Z = 2 Blöcken pro Bucket). Für N = 2^20 Blöcke mit jeweils 4KB ergibt dies 160KB pro Zugriff, verglichen mit 400KB bei Path ORAM (Z=5). Der Bandbreiten-Overhead gegenüber Klartext beträgt bei typischen Parametern etwa 40x statt 100x bei Path ORAM.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) verwendet Circuit ORAM, um oblivious Varianten höherer Datenstrukturen zu erstellen: oblivious Linked Lists, oblivious Maps (Hash-Tabellen) und oblivious Priority Queues. Diese Strukturen ermöglichen oblivious Berechnungen auf dynamischen Daten, ohne Zugriffsmuster offenzulegen. Oblix läuft innerhalb von Intel SGX Enclaves und ist auf Secure Private Set Intersection sowie private Datenbankabfragen ausgerichtet.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) erweitert Path ORAM um Unterstützung für asynchrone Zugriffe mit hohem Durchsatz, indem mehrere ORAM-Anfragen parallel verarbeitet und Pfadverdrängungen gebündelt werden. Durch das Zusammenfassen von Zugriffen auf denselben Pfad erreicht TaoStore einen deutlich höheren Durchsatz (Anfragen pro Sekunde) als synchrone ORAM-Konstruktionen und eignet sich dadurch für Cloud-Speicherserver mit vielen gleichzeitig zugreifenden Clients.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) baut ein vollständiges Transaktionsspeichersystem auf Path ORAM auf. Obladi unterstützt ACID-Transaktionen über verschlüsselten Speicher, der Zugriffsmuster verbirgt. Das System führt eine verzögerte Ausführung ein: Transaktionen werden zu Epochen gebündelt und so ausgeführt, dass verborgen bleibt, auf welche konkreten Datensätze innerhalb der jeweiligen Epoche zugegriffen wurde. Obladi fungiert als vertrauenswürdiger Proxy zwischen den Clients und einem nicht vertrauenswürdigen Cloud-Speicher-Backend.

Bei einem 1-GB-ORAM (262.144 Blöcke zu je 4 KB), das auf AWS bereitgestellt ist und bei dem ein Client über das Internet auf Blöcke zugreift, beträgt die Latenz von Path ORAM pro Zugriff ungefähr 50–200 ms. Sie wird hauptsächlich durch die Round-Trip-Zeit für die log N = 18 Bucket-Zugriffe bestimmt. Durch das parallele Abrufen der Buckets lässt sich dieser Wert reduzieren. Bei lokalen SGX-Anwendungen mit einem im RAM liegenden ORAM liegt die Latenz bei 1–10 ms pro Zugriff und ist damit für viele Anwendungen zur sicheren Berechnung akzeptabel.

Der Bandbreiten-Overhead von ORAM hängt stark von den Zugriffsmustern ab. Bei einem ORAM für 1 TB Cloud-Speicher mit 1-MB-Blöcken werden pro Zugriff ungefähr 25 MB übertragen (25-facher Overhead bei log N = 25 Ebenen). Bei kleinen Blöcken (4 KB) ist der Overhead pro Zugriff in absoluten Byte geringer, relativ gesehen jedoch höher. Organisationen, die ORAM einsetzen, müssen eine 20- bis 50-fache Bandbreitenverstärkung einplanen und sicherstellen, dass ihre Netzwerkverbindungen und die Kosten für den Cloud-Datenausgang dies berücksichtigen.

Eine Alternative zu ORAM für den Schutz der Zugriffsdaten ist vertrauenswürdige Hardware: Intel SGX oder AMD SEV stellt eine vertrauenswürdige Ausführungsumgebung bereit, in der selbst das Host-Betriebssystem die Berechnung oder die Speicherzugriffsmuster nicht beobachten kann, sofern geeignete Schutzmaßnahmen eingesetzt werden. SGX ohne ORAM gibt weiterhin Zugriffsmuster auf Seitenebene an die Hardware preis, daher ist ORAM innerhalb von SGX für einen vollständigen Schutz erforderlich. Im Vergleich zu reinem ORAM reduziert vertrauenswürdige Hardware den Bandbreiten-Overhead, erfordert jedoch Vertrauen in den Hardwarehersteller und die Lieferkette.

ORAM ist geeignet, wenn: ein Angreifer die serverseitigen Zugriffsmuster beobachtet (etwa ein Cloud-Anbieter oder ein Mitmieter), die Sensibilität der Daten einen 20- bis 50-fachen Bandbreiten-Overhead rechtfertigt und das Zugriffsmuster selbst vertrauliche Informationen offenlegen würde. Für die meisten Anwendungen reicht eine Standardverschlüsselung mit sorgfältiger Schlüsselverwaltung aus. ORAM ist ein spezialisiertes Werkzeug für Szenarien mit hohen Sicherheitsanforderungen, etwa die Analyse medizinischer Daten, privates maschinelles Lernen, Finanzhandelssysteme und Datenbanken von Strafverfolgungsbehörden.

Welche Bucket-Größe verwendet Circuit ORAM, und warum stellt dies eine Verbesserung gegenüber Path ORAM dar?

Circuit ORAM reduziert die Bucket-Größe auf Z=2 (gegenüber Z=5 bei Path ORAM) und halbiert durch deterministische Verdrängung nach dem Deep-First-Verfahren den Bandbreitenbedarf. Es wurde für den Einsatz innerhalb einer sicheren Berechnung mit Garbled Circuits entwickelt. Der praktische Overhead beträgt bei typischen Parametern das 40-Fache der Bandbreite. Zu den Produktionssystemen gehören Oblix (SGX + zugriffsmusterverdeckte Datenstrukturen), TaoStore (ORAM mit hohem Durchsatz und gebündelten Zugriffen) und Obladi (transaktionales ORAM). ORAM innerhalb von SGX ist erforderlich, weil SGX allein Zugriffsmuster auf Seitenebene preisgibt.