Die Bedrohung durch das Offenlegen von Zugriffsmustern

Die Verschlüsselung von Daten schützt deren Inhalte vor unbefugten Parteien, verbirgt jedoch nicht allein die Metadaten darüber, wie auf die Daten zugegriffen wird. Zugriffsmuster – also welche Datensätze gelesen oder geschrieben werden, wann und wie häufig – können sensible Informationen offenlegen, selbst wenn die Daten selbst vollständig verschlüsselt sind. Diese Lücke zwischen dem Schutz der Inhalte und dem Schutz der Zugriffe ist die zentrale Motivation für Oblivious RAM.

Die Analyse von Zugriffsmustern kann Folgendes offenlegen: welche Datenbankdatensätze ein Benutzer abfragt (wodurch sich aus den abgerufenen Datensätzen medizinische Erkrankungen ableiten lassen), Kommunikationsmuster (wer wen kontaktiert, selbst wenn der Nachrichteninhalt verschlüsselt ist), finanzielle Aktivitäten (wodurch sich aus den vom Benutzer abgefragten Kursen Handelsstrategien ableiten lassen) und Verhaltensmuster (etwa tägliche Routinen anhand von Zugriffszeitpunkten und -häufigkeiten). Diese Rückschlüsse können genauso sensibel sein wie die Dateninhalte selbst.

CryptDB (MIT, 2011) war ein einflussreiches System zum Abfragen verschlüsselter Datenbanken. Nachfolgende Arbeiten von Grubbs, McPherson, Naveed, Ristenpart und Spooner (2016) zeigten, dass CryptDB und ähnliche ordnungserhaltende Verschlüsselungsverfahren Zugriffsmuster preisgeben, die Inferenzangriffe ermöglichen. Ein Angreifer mit einem zusätzlichen Datensatz über Zugriffsverteilungen kann allein anhand der Zugriffshäufigkeit und -reihenfolge Klartextwerte ableiten, ohne die Verschlüsselung zu brechen.

Wenn ein verschlüsselter Cloud-Speicherdienst protokolliert, auf welche Chiffretextblöcke zugegriffen wird, kann ein Angreifer eine Frequenzanalyse durchführen. Da Nutzer dazu neigen, auf beliebte Dateien häufiger zuzugreifen, spiegelt das Histogramm der Zugriffshäufigkeiten von Chiffretextblöcken die Zugriffverteilung des Klartexts wider. Durch den Abgleich des verschlüsselten Häufigkeitshistogramms mit bekannten Zugriffsmustern lässt sich feststellen, welche verschlüsselten Dateien beliebten Inhaltskategorien entsprechen.

Im Bedrohungsmodell „honest-but-curious (semi-honest)“ befolgt der Cloud-Anbieter das Protokoll korrekt, beobachtet jedoch alle Zugriffsmuster auf die Daten des Kunden. Viele Cloud-Anbieter protokollieren Zugriffsmuster legitimerweise für die Abrechnung, die Fehlersuche und die Leistungsoptimierung. Auch ohne böswillige Absicht stellen diese Protokolle ein Risiko dar: Ein kompromittierter Cloud-Anbieter, ein illoyaler Mitarbeiter oder eine staatliche Vorladung könnte vertrauliche Zugriffsmuster offenlegen.

Oblivious RAM (ORAM), eingeführt von Goldreich und Ostrovsky (1996), ist ein kryptografisches Primitive, das Zugriffsmuster vor dem Server verbirgt. In einem ORAM-Verfahren erzeugt jeder Zugriff (Lesen oder Schreiben) auf eine beliebige Speicherstelle unabhängig davon, auf welche Stelle tatsächlich zugegriffen wird, dieselbe Verteilung der für den Server sichtbaren Operationen. Ein Angreifer, der den Server beobachtet, sieht nur gleichverteilte zufällige Zugriffsmuster.

ORAM hat ein breites Anwendungsspektrum überall dort, wo der Schutz von Zugriffsmustern erforderlich ist: sicherer Cloud-Speicher (Verbergen, auf welche Dateien ein Nutzer zugreift), oblivious Datenbankabfragen (Verbergen, welche Zeilen eine Abfrage zurückgibt), SGX Enclaves (Verhindern von Seitenkanälen durch Zugriffsmuster auf den Enclave-Speicher), Private Information Retrieval (Verbergen, welchen Datenbankeintrag ein Nutzer abruft) und sichere Mehrparteienberechnung (Verbergen von Zugriffsmustern auf Zwischenzustände).

Die einfachste ORAM-Lösung ist unmittelbar offensichtlich: Um auf einen beliebigen Block zuzugreifen, werden alle Blöcke des gesamten Speichers gelesen und erneut geschrieben. Dadurch wird verborgen, auf welchen Block zugegriffen wurde (jeder Zugriff sieht identisch aus), der Kommunikationsaufwand von O(n) pro logischem Zugriff macht das Verfahren für große Datensätze jedoch völlig unpraktisch. Reale ORAM-Verfahren versuchen, diesen Aufwand bei gleichzeitiger perfekter oder statistischer Obliviousness auf O(polylog n) zu reduzieren.

Goldreich und Ostrovsky bewiesen eine untere Schranke: Jedes ORAM mit einem Speicher-Overhead von O(1) auf dem Server muss mindestens einen Kommunikations-Overhead von Omega(log n) pro Zugriff verursachen. Diese logarithmische untere Schranke gilt für deterministische ORAMs. Praktische Konstruktionen streben einen Overhead von O(log^2 n) oder O(log n) an und liegen damit nahe am theoretischen Minimum. Die untere Schranke zeigt, dass das vollständige Verbergen von Zugriffsmustern unvermeidbare Kosten verursacht.

Searchable Symmetric Encryption (SSE) ermöglicht die Suche in verschlüsselten Daten. Grundlegende SSE-Verfahren geben Suchmuster (nach welchen Schlüsselwörtern gesucht wird) und Zugriffsmuster (welche Dokumente zurückgegeben werden) preis. Forward-private SSE verbirgt das Suchmuster für neue Dokumente, aber zusätzlich zum Verbergen der Zugriffe auf die Dokumente wird ORAM benötigt. Die Kombination von SSE und ORAM bietet die stärkste Datenschutzgarantie, verursacht jedoch erhebliche Leistungskosten.

ORAM ist nicht immer erforderlich. Die Entscheidung hängt vom Bedrohungsmodell ab: Beobachtet der Angreifer die Zugriffsmuster? Für lokalen Speicher mit vollständiger Festplattenverschlüsselung und einem entfernten Angreifer ist ORAM möglicherweise nicht erforderlich. Für Cloud-Speicher, bei dem dem Cloud-Anbieter nicht vertraut wird, ist ORAM angemessen. Der Overhead (typischerweise der 20- bis 50-fache Bandbreitenbedarf) lohnt sich, wenn das Durchsickern von Zugriffsmustern eine tatsächliche Bedrohung darstellt und die Sensibilität der Daten die Kosten rechtfertigt.

Welche der folgenden Aussagen beschreibt richtig, warum Zugriffsmuster auch bei verschlüsselten Daten vertraulich sind?

Die Verschlüsselung des Dateninhalts verbirgt keine Zugriffsmuster, die durch Frequenzanalyse und Zeitmessungen vertrauliche Informationen offenlegen können. Cloud-Anbieter beobachten in honest-but-curious-Modellen, auf welche Chiffretextblöcke Kunden zugreifen. Angriffe auf CryptDB zeigten, dass sich aus Zugriffsmustern in verschlüsselten Datenbanken praktisch Informationen ableiten lassen. ORAM löst dieses Problem, indem alle Zugriffe für den Server identisch aussehen. Die triviale Lösung (bei jedem Zugriff alles lesen) ist mit O(n) unpraktisch; reale ORAM-Verfahren erreichen einen Overhead von O(log^2 n).