La minaccia della fuga dai pattern di accesso

La cifratura dei dati ne protegge il contenuto dalle parti non autorizzate, ma da sola non nasconde i metadati relativi al modo in cui i dati vengono consultati. I pattern di accesso — quali record vengono letti o scritti, quando e con quale frequenza — possono rivelare informazioni sensibili anche quando i dati stessi sono completamente cifrati. Questa differenza tra riservatezza del contenuto e riservatezza degli accessi è la motivazione principale alla base della Oblivious RAM.

L'analisi dei pattern di accesso può rivelare: quali record di un database vengono consultati da un utente, consentendo di dedurre condizioni mediche dai record a cui accede; i pattern delle comunicazioni, ovvero chi contatta chi anche se il contenuto dei messaggi è cifrato; l'attività finanziaria, consentendo di dedurre strategie di trading dai prezzi richiesti da un utente; e i pattern comportamentali, come le abitudini quotidiane ricavate dagli orari e dalla frequenza degli accessi. Queste deduzioni possono essere sensibili quanto il contenuto stesso dei dati.

CryptDB (MIT, 2011) è stato un sistema innovativo per eseguire query su database cifrati. Un lavoro successivo di Grubbs, McPherson, Naveed, Ristenpart e Spooner (2016) ha dimostrato che CryptDB e schemi simili di cifratura che preserva l'ordine espongono i pattern di accesso, consentendo attacchi di inferenza. Disponendo di un dataset ausiliario sulle distribuzioni degli accessi, un aggressore può dedurre i valori in chiaro basandosi esclusivamente sulla frequenza e sull'ordine degli accessi, anche senza violare la cifratura.

Se un servizio di storage cloud cifrato registra quali blocchi di testo cifrato vengono consultati, un avversario può eseguire un'analisi della frequenza. Poiché gli utenti tendono ad accedere più spesso ai file popolari, l'istogramma della frequenza di accesso ai blocchi di testo cifrato rispecchia la distribuzione degli accessi al testo in chiaro. Confrontando l'istogramma della frequenza dei dati cifrati con pattern di accesso noti, è possibile identificare quali file cifrati corrispondono alle categorie di contenuti più popolari.

Nel modello di minaccia honest-but-curious (semi-honest), il cloud provider segue correttamente il protocollo, ma osserva tutti i pattern di accesso ai dati del client. Molti cloud provider registrano legittimamente i pattern di accesso per la fatturazione, il debugging e l'ottimizzazione delle prestazioni. Anche senza intenti malevoli, questi log creano un rischio: un cloud provider compromesso, un dipendente infedele o un'ingiunzione governativa potrebbero esporre pattern di accesso sensibili.

Oblivious RAM (ORAM), introdotta da Goldreich e Ostrovsky (1996), è una primitiva crittografica che nasconde i pattern di accesso al server. In uno schema ORAM, ogni accesso (in lettura o scrittura) a una posizione di memoria genera la stessa distribuzione di operazioni visibili al server, indipendentemente dalla posizione effettivamente consultata. Un avversario che osserva il server vede soltanto pattern di accesso uniformemente casuali.

ORAM ha un'ampia gamma di applicazioni ovunque sia necessaria la privacy dei pattern di accesso: storage cloud sicuro (per nascondere a quali file accede un utente), query oblivious su database (per nascondere quali righe restituisce una query), enclave SGX (per impedire side channel basati sui pattern di accesso alla memoria dell'enclave), private information retrieval (per nascondere quale voce del database recupera un utente) e secure multi-party computation (per nascondere i pattern di accesso allo stato intermedio).

La soluzione ORAM più semplice è banalmente ovvia: per accedere a un singolo blocco, si leggono e si riscrivono tutti i blocchi dell'intero storage. Questo nasconde quale blocco è stato consultato, poiché ogni accesso appare identico, ma comporta un overhead di comunicazione O(n) per ogni accesso logico, rendendo la soluzione del tutto impraticabile per dataset di grandi dimensioni. Gli schemi ORAM reali mirano a ridurre questo overhead a O(polylog n), mantenendo al contempo l'obliviousness perfetta o statistica.

Goldreich e Ostrovsky hanno dimostrato un limite inferiore: qualsiasi ORAM con overhead di storage sul server pari a O(1) deve sostenere un overhead di comunicazione di almeno Omega(log n) per accesso. Questo limite inferiore logaritmico si applica alle ORAM deterministiche. Le costruzioni pratiche puntano a ottenere un overhead di O(log^2 n) o O(log n), vicino a questo minimo teorico. Il limite inferiore dimostra che nascondere perfettamente i pattern di accesso ha un costo inevitabile.

La searchable symmetric encryption (SSE) consente di effettuare ricerche su dati cifrati. Gli schemi SSE di base rivelano i pattern di ricerca, ovvero quali parole chiave vengono cercate, e i pattern di accesso, ovvero quali documenti vengono restituiti. La forward-private SSE nasconde il pattern di ricerca per i nuovi documenti, ma per nascondere anche quali documenti vengono consultati è necessaria ORAM. La combinazione di SSE e ORAM offre la più forte garanzia di privacy, ma comporta un costo significativo in termini di prestazioni.

ORAM non è sempre necessaria. La decisione dipende dal modello di minaccia: l'avversario osserva i pattern di accesso? Per lo storage locale con cifratura dell'intero disco e un avversario remoto, ORAM potrebbe non essere necessaria. Per lo storage cloud, quando il cloud provider non è considerato attendibile, ORAM è appropriata. L'overhead, in genere pari a 20-50x la larghezza di banda, vale la pena quando la fuga di informazioni dai pattern di accesso costituisce una minaccia concreta e la sensibilità dei dati ne giustifica il costo.

La cifratura del contenuto dei dati non nasconde i pattern di accesso, che possono rivelare informazioni sensibili attraverso l'analisi della frequenza e dei tempi. I cloud provider, nei modelli honest-but-curious, osservano quali blocchi di testo cifrato consultano i client. Gli attacchi a CryptDB hanno dimostrato che è possibile effettuare inferenze pratiche basandosi sui pattern di accesso nei database cifrati. ORAM risolve questo problema facendo apparire identici tutti gli accessi al server. La soluzione banale, che legge tutto a ogni accesso, è impraticabile con complessità O(n); le ORAM reali raggiungono un overhead di O(log^2 n).