ORAM in Cloud-Storage und sicheren Prozessoren

Intel SGX (Software Guard Extensions) stellt hardwareisolierte Enklaven bereit, in denen Code und Daten verschlüsselt und authentifiziert werden. Das Betriebssystem kann jedoch weiterhin beobachten, auf welche Speicherseiten die Enklave zugreift, indem es die Seitentabelleneinträge überwacht. Dieses Zugriffsmuster auf Seitenebene kann in Seitenkanalangriffen ausgenutzt werden. Ein klassischer Angriff ist der von Xu, Cui und Peinado (2015) beschriebene „Controlled-Channel-Angriff“, bei dem RSA-Schlüssel aus den Speicherzugriffsmustern von SGX rekonstruiert wurden.

Neben Zugriffsmustern auf Seitenebene ist SGX anfällig für Cache-Timing-Seitenkanäle. Ein Angreifer, der denselben Prozessor nutzt, kann die von der Enklave verursachten Cache-Treffer und Cache-Fehlzugriffe beobachten und daraus Zugriffsmuster auf feinerer Granularität (auf Cache-Zeilen-Ebene) ableiten. Diese Angriffe sind möglich, weil der CPU-Cache von der Enklave und nicht vertrauenswürdigem Code gemeinsam genutzt wird. Zu den Gegenmaßnahmen gehören Programmierung mit konstanter Laufzeit und ORAM zur Randomisierung der Speicherzugriffsmuster.

ZeroTrace (Sasy, Jha, Kerschbaum, 2018) implementiert Path ORAM innerhalb einer Intel-SGX-Enklave, um zugriffsmusterverdeckte Speicherzugriffe bereitzustellen. Das nicht vertrauenswürdige Host-Betriebssystem stellt den ORAM-Server (den Binärbaum aus Buckets) bereit, während die SGX-Enklave als ORAM-Client fungiert. ZeroTrace fügt eine SGX-spezifische Optimierung hinzu: Die Positionskarte wird innerhalb der Enklave (im vertrauenswürdigen Speicher) gehalten, wodurch rekursives ORAM für die Positionskarte entfällt.

Graphene-SGX (jetzt Gramine) und SCONE sind SGX-Container-Frameworks, mit denen sich unveränderte Linux-Anwendungen innerhalb von Enklaven ausführen lassen. Beide Frameworks wurden um ORAM-Unterstützung erweitert, um Zugriffsmuster vor dem Betriebssystem zu verbergen. Die ORAM-Integration in SCONE ermöglicht die zugriffsmusterverdeckte Ausführung von Python-, Go- und Java-Programmen in SGX ohne Codeänderungen. Dadurch steht ORAM auch Anwendungen ohne manuelle Integration zur Verfügung.

Shroud (Volos, Jaleel, Emer, Burtscher, Forlin, 2018) implementiert zugriffsmusterverdeckte Varianten grundlegender Datenstrukturen (Arrays, Stapel, Warteschlangen und Maps) für den Einsatz innerhalb von SGX-Enklaven. Shroud kombiniert ORAM mit datenunabhängigen Algorithmen, um sicherzustellen, dass die Speicherzugriffsmuster der Enklave nicht von den Datenwerten abhängen. Dies ist effizienter, als den gesamten Anwendungsspeicher mit ORAM zu versehen, da nur sensible Datenstrukturen geschützt werden.

AWS Nitro Enclaves stellen isolierte Rechenumgebungen für die Verarbeitung hochsensibler Daten bereit, etwa Zahlungskartennummern oder Gesundheitsdaten. Anders als SGX isolieren Nitro Enclaves auf Ebene der virtuellen Maschine und nicht auf Prozessebene. AWS stellt in Nitro Enclaves standardmäßig kein ORAM bereit, die Vertraulichkeitsgarantien erstrecken sich jedoch auf den Speicherinhalt. Für den Schutz der Zugriffsmuster müssen Anwendungen, die in Nitro Enclaves ausgeführt werden, bei Bedarf ihr eigenes ORAM implementieren.

ARM TrustZone stellt eine vertrauenswürdige Ausführungsumgebung (Secure World) bereit, die vom normalen Betriebssystem isoliert ist. Wie SGX verbirgt TrustZone Speicherzugriffsmuster nicht von sich aus. Forschungssysteme wie TrustORAM (Brasser, Dmitrienko, Sadeghi, Crane, Larsen, Franz) implementieren ORAM innerhalb von TrustZone, um den Zugriff auf sensible Daten in mobilen Geräten und IoT-Systemen zu schützen. TrustZone ist auf allen modernen ARM-Prozessoren vorhanden, wodurch sich TrustZone mit ORAM-Unterstützung breit einsetzen lässt.

ObliDB (Eskandarian und Boneh, 2017) ist eine zugriffsmusterverdeckte Datenbank, die Zugriffsmuster für standardmäßige SQL-Abfragen verbirgt. Für Punktanfragen verwendet sie ORAM und für Bereichsanfragen zugriffsmusterverdecktes Sortieren. Opaque führt SQL-Abfragen mithilfe von Intel SGX und ORAM zugriffsmusterverdeckt über Apache Spark aus. Opaque zeigt, dass Datenanalysen im Produktionsmaßstab mit Millionen von Datensätzen trotz des ORAM-Overheads realisierbar sind.

Private Information Retrieval (PIR) ist ein verwandtes Grundelement zur Verbergung von Zugriffsmustern bei schreibgeschützten Zugriffen. PIR ermöglicht es einem Client, ein Datenbankelement abzurufen, ohne dass der Server erfährt, welches Element abgerufen wurde. Computational PIR (cPIR) erreicht dies mit einem serverseitigen Speicher-Overhead von O(1) und einer Kommunikation von O(sqrt(n)) oder O(polylog n). PIR ist für schreibgeschützte Workloads effizienter als ORAM, kann jedoch keine zugriffsmusterverdeckten Schreibvorgänge unterstützen.

Bei schreibgeschützten Zugriffen ist PIR hinsichtlich der Kommunikation effizienter als ORAM: Single-Server-cPIR benötigt eine Kommunikation von O(n^epsilon), während ORAM pro Zugriff O(log n) Blöcke benötigt. PIR erfordert jedoch eine serverseitige Berechnung (bei Single-Server-PIR linear zur Datenbankgröße), während ORAM die gesamte Berechnung auf dem Client ausführt. Multi-Server-PIR (mit zwei nicht kolludierenden Servern informationstheoretisch sicher) ist sehr effizient und eignet sich für CDN-Bereitstellungen.

Zu den Forschungsrichtungen bei ORAM gehören: die Reduzierung des Kommunikations-Overheads in Richtung der theoretischen unteren Schranke O(log n) (OptORAMa erreicht dies asymptotisch), ORAM für Quantum RAM (QRAM), differentiell privates ORAM (das verbirgt, ob zweimal auf denselben Block zugegriffen wurde) und ORAM in der homomorphen Verschlüsselung (FHE-ORAM für ausgelagerte Berechnungen). Die Integration von ORAM in hardwarebasierte vertrauenswürdige Ausführungsumgebungen bleibt die praktisch wirkungsvollste Forschungsrichtung.

Intel SGX gibt Zugriffsmuster auf Seiten- und Cache-Ebene preis und ermöglicht dadurch Controlled-Channel- und Cache-Timing-Angriffe. ZeroTrace implementiert Path ORAM innerhalb von SGX, um diese Datenlecks zu beseitigen. Graphene-SGX und SCONE bieten eine ORAM-Integration auf Containerebene. ObliDB und Opaque zeigen zugriffsmusterverdeckte SQL-Abfragen über ORAM im Produktionsmaßstab. PIR ist eine effiziente Alternative für schreibgeschützte Zugriffe. Die ORAM-Forschung arbeitet weiterhin an der unteren Schranke von log n für die Kommunikation und an der Integration in die homomorphe Verschlüsselung.