Path ORAM: Speicherzugriffe verbergen

Path ORAM, vorgeschlagen von Stefanov, van Dijk, Shi, Fletcher, Ren, Yu und Devadas (2013), ist die praktisch einflussreichste ORAM-Konstruktion. Dabei wird der Serverspeicher als binärer Baum aus Buckets organisiert, wobei jedes Blatt einer Position für einen Datenblock entspricht. Path ORAM erreicht in seiner Grundform einen Kommunikations-Overhead von O(log^2 N) pro Zugriff und ist einfach genug, um in wenigen hundert Codezeilen implementiert zu werden.

Die Positionsabbildung ist eine clientseitige Datenstruktur, die jede logische Blockadresse einem Blattknoten im Binärbaum zuordnet. Für eine Datenbank mit N Blöcken und einem Baum der Höhe L = log N ist die Positionsabbildung ein Array aus N Blattindizes. Vor dem Zugriff auf Block b schlägt der Client das aktuell zugewiesene Blatt in der Positionsabbildung nach und weist ihm ein neues zufälliges Blatt zu. Der Pfad des alten Blatts wird vom Server gelesen und wieder auf ihn geschrieben.

Der Stash ist ein kleiner clientseitiger Puffer (typischerweise 20–40 Blöcke), der vorübergehend Blöcke enthält, die vom Server gelesen, aber noch nicht zurückgeschrieben wurden. Beim Lesen eines Blocks wird dieser aus seinem Pfad entfernt und im Stash abgelegt. Nach dem Zugriff darauf und einer möglichen Änderung werden alle Blöcke im Stash, die auf dem neuen Pfad untergebracht werden können, zurückgeschrieben. Blöcke, die nicht auf einen Pfad passen, verbleiben im Stash.

Der Serverspeicher ist ein vollständiger Binärbaum mit L+1 Ebenen (L = log N). Jeder Knoten (Bucket) enthält Z Blöcke (typischerweise Z = 5). Die Blätter entsprechen den Positionen der Datenblöcke. Es gibt N Blattknoten, also insgesamt 2N-1 Knoten und einen gesamten Serverspeicher von O(NZ). Jeder Pfad vom Blatt zur Wurzel enthält log N Knoten und kann Z*log N Blöcke aufnehmen. Dadurch steht die erforderliche Kapazität für die Pfadverdrängungsstrategie bereit.

Zum Lesen von Block b: (1) das aktuelle Blatt l für b in der Positionsabbildung nachschlagen; (2) b ein neues zufälliges Blatt l' zuweisen und die Positionsabbildung aktualisieren; (3) alle Buckets auf dem Pfad vom Blatt l zur Wurzel lesen (log N Buckets); (4) Block b im gelesenen Pfad oder im Stash suchen; (5) alle Blöcke zurückschreiben, die dem neuen Pfad l' zugewiesen werden können, und die übrigen Bucket-Slots mit Dummy-Blöcken füllen. Der Server sieht bei jedem Zugriff das Lesen eines zufälligen Pfads.

Path ORAM gewährleistet Obliviousness, weil bei jedem Zugriff unabhängig davon, auf welchen Block zugegriffen wird, genau ein Pfad von der Wurzel zu einem Blatt gelesen und geschrieben wird. Der Pfad wird durch eine gleichverteilte zufällige Blattzuweisung bestimmt, nicht durch den Inhalt oder die Adresse des Blocks. Dummy-Blöcke füllen leere Bucket-Slots, sodass jeder Pfad dieselbe Anzahl belegter Slots aufweist. Ein Angreifer, der den Server beobachtet, sieht nur zufällige Pfadzugriffe.

Jeder Path-ORAM-Zugriff erfordert das Lesen und Schreiben eines Pfads von der Wurzel zu einem Blatt: O(log N) Buckets mit jeweils Z Blöcken. Bei einer Blockgröße B und einer Bucket-Größe Z überträgt jeder Zugriff O(Z * log N * B) Bit. Für typische Parameter (N = 2^20, Z = 5, B = 4KB) sind dies etwa 400KB pro Zugriff, verglichen mit 4KB bei einem Klartextzugriff – ein 100-facher Overhead. Rekursive Positionsabbildungen reduzieren dies auf O(log^2 N) Kommunikation, ausgedrückt in Blöcken.

Die naive Positionsabbildung erfordert N Einträge, die auf dem Client gespeichert werden, also einen clientseitigen Speicher von O(N) – so viel wie die gesamte Datenbank. Die rekursive Positionsabbildung reduziert den clientseitigen Speicher auf O(log^2 N), indem die Positionsabbildung selbst rekursiv in einem kleineren ORAM gespeichert wird. Die Rekursion endet, sobald das ORAM klein genug ist, um in den Stash zu passen. Dies ist die Standardtechnik, um Path ORAM für große Datensätze praktikabel zu machen.

Die Größe des Stash in Path ORAM wächst, wenn Blöcke aufgrund von Pfadkonflikten nicht auf ihre zugewiesenen Pfade verdrängt werden können. Stefanov et al. bewiesen, dass der Stash mit exponentiell kleiner Wahrscheinlichkeit R Blöcke überschreitet – gemäß der Standardanalyse höchstens mit 14 * (0.6002)^R. Für R = 40 ergibt sich eine Fehlerwahrscheinlichkeit von etwa 2^{-38}; dies gilt für alle Zugriffsequenzen, einschließlich solcher, die von einem Angreifer gewählt wurden.

Vor Path ORAM hatten die besten praktischen ORAM-Konstruktionen einen Overhead von O(log^3 N) (Shi et al. 2011, „Oblivious RAM with O((log N)^3) Worst-Case Cost“). Path ORAM reduzierte diesen Wert mit einer deutlich einfacheren Struktur auf O(log^2 N). Nachfolgende Arbeiten (Circuit ORAM, OptORAMa) verbesserten die Konstanten und asymptotischen Schranken weiter, doch Path ORAM bleibt aufgrund seiner Einfachheit die am weitesten verbreitete implementierte Konstruktion.

Path ORAM wurde in Dutzenden Forschungs- und Produktivsystemen implementiert. ZeroTrace (Intel SGX + Path ORAM), Obladi (Path ORAM über Cloud-Speicher) und Opaque (Path ORAM über Apache Spark) sind bemerkenswerte Implementierungen. Die Forschungsgruppe für sichere Berechnung an der Stanford University pflegt eine Open-Source-Implementierung von Path ORAM in C++. AWS bietet Path ORAM als Teil seiner Forschungsprototypen für Nitro Enclaves zur datenschutzfreundlichen Datenanalyse an.

Welche Funktion hat die Positionsabbildung in Path ORAM?

Path ORAM organisiert den Serverspeicher als Binärbaum, wobei bei jedem Zugriff ein Pfad von der Wurzel zu einem Blatt gelesen und geschrieben wird. Die Positionsabbildung verfolgt die aktuelle Blattzuweisung jedes Blocks; der Stash puffert kürzlich verwendete Blöcke. Jeder Zugriff wird durch die Zuweisung neuer zufälliger Blattpositionen randomisiert, sodass alle für den Server sichtbaren Zugriffe dieselbe Verteilung aufweisen. Der Kommunikations-Overhead beträgt O(Z * log N) pro Zugriff. Rekursive Positionsabbildungen reduzieren den clientseitigen Speicher auf O(log^2 N). Path ORAM ist die am weitesten verbreitete implementierte ORAM-Konstruktion.