Zagrożenie wyciekiem wzorców dostępu

Szyfrowanie danych chroni ich zawartość przed nieuprawnionymi stronami, ale samo szyfrowanie nie ukrywa metadanych dotyczących sposobu uzyskiwania dostępu do danych. Wzorce dostępu — które rekordy są odczytywane lub zapisywane, kiedy i jak często — mogą ujawniać poufne informacje, nawet gdy same dane są całkowicie zaszyfrowane. Ta luka między prywatnością zawartości a prywatnością dostępu stanowi główną motywację dla Oblivious RAM.

Analiza wzorców dostępu może ujawnić: które rekordy bazy danych użytkownik odczytuje (co pozwala wnioskować o jego stanie zdrowia na podstawie uzyskiwanych rekordów medycznych), wzorce komunikacji (kto kontaktuje się z kim, nawet jeśli treść wiadomości jest zaszyfrowana), aktywność finansową (wnioskowanie o strategiach handlowych na podstawie cen, o które użytkownik pyta) oraz wzorce zachowań (codzienne zwyczaje na podstawie godzin i częstotliwości dostępu). Takie wnioski mogą być równie wrażliwe jak sama zawartość danych.

CryptDB (MIT, 2011) był wpływowym systemem do wykonywania zapytań na zaszyfrowanych bazach danych. Późniejsze prace Grubbsa, McPhersona, Naveeda, Ristenparta i Spoonera (2016) wykazały, że CryptDB oraz podobne schematy szyfrowania zachowującego kolejność ujawniają wzorce dostępu, co umożliwia ataki wnioskowania. Atakujący dysponujący pomocniczym zbiorem danych na temat rozkładów dostępu może wywnioskować wartości tekstu jawnego wyłącznie na podstawie częstotliwości i kolejności dostępu, nawet bez złamania szyfrowania.

Jeśli usługa szyfrowanego przechowywania w chmurze rejestruje, które bloki szyfrogramu są odczytywane, przeciwnik może przeprowadzić analizę częstotliwości. Ponieważ użytkownicy mają tendencję do częstszego otwierania popularnych plików, histogram częstotliwości dostępu do bloków szyfrogramu odzwierciedla rozkład dostępu do tekstu jawnego. Dopasowanie zaszyfrowanego histogramu częstotliwości do znanych wzorców dostępu może ujawnić, które zaszyfrowane pliki odpowiadają popularnym kategoriom treści.

W modelu zagrożeń uczciwego, lecz ciekawskiego (honest-but-curious, semi-honest) dostawca chmury prawidłowo wykonuje protokół, ale obserwuje wszystkie wzorce dostępu do danych klienta. Wielu dostawców chmury zgodnie z prawem rejestruje wzorce dostępu na potrzeby rozliczeń, debugowania i optymalizacji wydajności. Nawet bez złośliwych zamiarów dzienniki te stwarzają ryzyko: przejęcie dostawcy chmury, nieuczciwy pracownik lub nakaz sądowy mogą ujawnić poufne wzorce dostępu.

Oblivious RAM (ORAM), wprowadzony przez Goldreicha i Ostrovsky’ego (1996), jest prymitywem kryptograficznym, który ukrywa wzorce dostępu przed serwerem. W schemacie ORAM każdy dostęp (odczyt lub zapis) do dowolnej lokalizacji pamięci generuje taki sam rozkład operacji widocznych dla serwera, niezależnie od tego, do której lokalizacji faktycznie następuje dostęp. Przeciwnik obserwujący serwer widzi wyłącznie jednostajnie losowe wzorce dostępu.

ORAM ma szeroki zakres zastosowań wszędzie tam, gdzie wymagana jest prywatność wzorców dostępu: bezpieczne przechowywanie w chmurze (ukrywanie, do których plików uzyskuje dostęp użytkownik), nieujawniające zapytania do baz danych (ukrywanie, które wiersze zwraca zapytanie), enklawy SGX (zapobieganie wyciekom wzorców dostępu do pamięci enklawy przez kanały boczne), prywatne wyszukiwanie informacji (ukrywanie, który wpis w bazie danych pobiera użytkownik) oraz bezpieczne obliczenia wielostronne (ukrywanie wzorców dostępu do stanu pośredniego).

Najprostsze rozwiązanie ORAM jest oczywiste: aby uzyskać dostęp do dowolnego bloku, należy odczytać i ponownie zapisać każdy blok w całej pamięci. Ukrywa to informację o tym, do którego bloku uzyskano dostęp (każdy dostęp wygląda tak samo), ale powoduje narzut komunikacyjny O(n) dla każdego logicznego dostępu, przez co jest całkowicie niepraktyczne dla dużych zbiorów danych. Rzeczywiste schematy ORAM dążą do zmniejszenia tego narzutu do O(polylog n) przy zachowaniu doskonałego lub statystycznego ukrywania wzorców dostępu.

Goldreich i Ostrovsky udowodnili dolną granicę: każdy ORAM o narzucie pamięci serwera O(1) musi ponosić co najmniej Omega(log n) narzutu komunikacyjnego na dostęp. Ta logarytmiczna dolna granica dotyczy deterministycznych ORAM-ów. Konstrukcje praktyczne mają osiągać narzut O(log^2 n) lub O(log n), zbliżony do tego teoretycznego minimum. Dolna granica pokazuje, że doskonałe ukrywanie wzorców dostępu wiąże się z nieuniknionym kosztem.

Szyfrowanie symetryczne z możliwością wyszukiwania (SSE) umożliwia wyszukiwanie w zaszyfrowanych danych. Podstawowe schematy SSE ujawniają wzorce wyszukiwania (jakie słowa kluczowe są wyszukiwane) oraz wzorce dostępu (jakie dokumenty są zwracane). Forward-private SSE ukrywa wzorzec wyszukiwania dotyczący nowych dokumentów, ale do ukrycia informacji o tym, do których dokumentów uzyskiwany jest dostęp, potrzebny jest również ORAM. Połączenie SSE z ORAM zapewnia najsilniejszą gwarancję prywatności, ale wiąże się ze znacznym kosztem wydajności.

ORAM nie zawsze jest konieczny. Decyzja zależy od modelu zagrożeń: czy przeciwnik obserwuje wzorce dostępu? W przypadku pamięci lokalnej z szyfrowaniem całego dysku i przeciwnikiem zdalnym ORAM może nie być potrzebny. W przypadku przechowywania w chmurze, gdy dostawca chmury jest niezaufany, zastosowanie ORAM jest właściwe. Narzut (zwykle 20–50 razy większe zużycie pasma) jest uzasadniony, gdy wyciek wzorców dostępu stanowi rzeczywiste zagrożenie, a poufność danych usprawiedliwia ten koszt.

Szyfrowanie zawartości danych nie ukrywa wzorców dostępu, które mogą ujawniać poufne informacje za pośrednictwem analizy częstotliwości i czasu. Dostawcy chmury w modelu uczciwego, lecz ciekawskiego obserwują, do których bloków szyfrogramu uzyskują dostęp klienci. Ataki na CryptDB wykazały, że na podstawie wzorców dostępu można w praktyce wnioskować o danych w zaszyfrowanych bazach. ORAM rozwiązuje ten problem, sprawiając, że wszystkie dostępy wyglądają dla serwera tak samo. Rozwiązanie trywialne (odczytywanie wszystkiego przy każdym dostępie) jest niepraktyczne przy O(n); rzeczywisty ORAM osiąga narzut O(log^2 n).