Path ORAM: Ukrywanie Wzorów Dostępów Pamięci

Układ drzewny i mapa pozycji

Path ORAM przechowuje N logicznych bloków wewnątrz drzewa binarnego z około N liśćmi, gdzie każdy węzeł drzewa jest koszem zdolnym do przechowywania niewielkiej stałej liczby bloków, powszechnie czterech, plus padding (dodatkowe bloki wypełniające) gdy kosz nie jest pełny. Klient utrzymuje mapę pozycji, tabelę wierszową łączącą każdy identyfikator logicznego bloku z losowym liściem, co oznacza, że klient zawsze wie, do którego liścia przypisano blok, nawet jeśli dokładna pozycja kosza w ścieżce od korzenia do tego liścia może się różnić. Ponieważ sama mapa pozycji może być duża dla dużych zbiorów danych, praktyczne implementacje rekurencyjnie przechowują ją w mniejszym ORAM-ie, zmniejszając metadane klienta do wartości mieszczącej się wygodnie w pamięci lokalnej. Ta struktura drzewa sprawia, że Path ORAM jest wydajny w porównaniu z wcześniejszymi konstrukcjami kwadratowymi pierwiastka i hierarchicznymi ORAM, ponieważ zamiast przesuwać cały zestaw danych podczas każdego dostępu potrzebuje jedynie dotknąć pojedynczej ścieżki, której długość jest tylko logarytmiczna względem całkowitej liczby bloków.

Protokół dostępu: odczyt, usuwanie, przekierowywanie

Każda operacja, niezależnie czy jest to logiczny odczyt, czy logiczne zapisywanie, odbywa się zgodnie z tą samą, trzyetapową choreografią, a ta jednolitość właśnie ukrywa, czy operacja była odczytem, czy zapisem. Po pierwsze, klient wyszukuje aktualny liście dla bloku docelowego w swoim mapie pozycji i pobiera wszystkie kontenery (bucket) wzdłuż ścieżki od korzenia do tego liścia, dekryptując je lokalnie, aby znaleźć blok docelowy wśród prawdziwych i fałszywych wpisów. Po drugie, klient aktualizuje blok, jeśli był to zapis, lub po prostu pozostawia jego wartość bez zmian, jeśli był to odczyt. Po trzecie, przed przesłaniem czegokolwiek do serwera, klient przypisuje odwiedzonemu blokowi nowy, losowy liście i następnie ponownie szyfruje całą ścieżkę, żagając wszystkie kontenery, które aktualnie posiada, w tym te pobrane z wcześniejszych dostępu, aż do głębokości, na jaką to pozwala jego przypisany ścieżka, zanim zapisze całą ścieżkę z powrotem do serwera. Ponieważ każda pojedyncza operacja pobiera i przesyła ponownie pełną ścieżkę kontenerów z nowym szyfrowaniem, niezależnie od tego, który logiczny blok został zażądany, podsłuchujący obserwując adresy kontenerów widzi jedynie jednolity losowy liście w każdej operacji, bez korelacji do odwiedzonego bloku lub czy operacja była odczytem, czy zapisem.

Dlaczego przekierowywanie do losowej gałęzi liścia zapobiega wyciekowi wzorców

Najważniejszym trikiem w Path ORAM jest to, że dostępny blok zawsze otrzymuje świeżą, niezależnie losowaną gałąź liścia natychmiast po jego dotknięciu, zanim wróci do serwera. Oznacza to, że nawet jeśli klient poprosi o tę samą logiczną blokę dwa razy pod rząd, oba dostępy dotkną dwie niezależnie losowe ścieżki przez drzewo, ponieważ mapa pozycji wskazuje teraz zupełnie nowy punkt po pierwszym dostępie. Bez tego kroku przekierowywania, powtarzające się dostępy do popularnej bloki wyrysują tę samą ścieżkę wielokrotnie, pozwalając pasywne obserwatorowi natychmiast rozpoznać, która blok jest gorąca, nawet bez odszyfrowywania niczego. Dowód bezpieczeństwa Path ORAM formalizuje to, pokazując, że sekwencja pobranych i przesłanych ścieżek jest obliczeniowo nierozróżnialna od sekwencji losowych ścieżek wybranych niezależnie od rzeczywistego wzorca dostępu klienta, co jest dokładnie definicją kryptograficznej obojętności, której schemat dąży.

Zapasy: sieć bezpieczeństwa dla przeciążonych bloków

Ponieważ pojemność kosza jest ustalona i niewielka, nie ma gwarancji, że każdy blok aktualnie posiadanego przez klienta może zostać w całości przesunięty z powrotem wzdłuż przypisanej mu ścieżki podczas wyłaniań, zwłaszcza gdy wiele bloków na nakładających się ścieżkach rywalizuje o te ograniczone sloty koszy. Path ORAM rozwiązuje to dzięki lokalnym zapasom po stronie klienta – niewielkiemu buforowi tymczasowemu, który przechowuje bloki, które nie mogły zostać umieszczone z powrotem w drzewie podczas bieżącego wyłaniań. Podczas kolejnego dostępu te zapasowe bloki stają się ponownie dostępne do przesunięcia wzdłuż dowolnej nowej ścieżki, która jest odczytywana, a dzięki strategii grabieżowej, z czasem rozmiar zapasu pozostaje bardzo mały, przy czym rygorystyczna analiza pokazuje, że prawdopodobieństwo to jest ogromne, o ile wielkość kosza jest odpowiednio dobrana, zwykle cztery rzeczywiste sloty na kosz. Ten zapas stanowi cenę za utrzymanie logarytmicznej przepustowości: zamiast wymuszania idealnego sukcesu dla każdego wyłaniania, protokół umożliwia tymczasowe opóźnienie, które naturalnie rozwiązuje się w miarę kolejnych dostępu dotykających nakładających się ścieżek.

Koszty, zastosowania i miejsce Path ORAM

Obciążenie wynikowe Path ORAM zdominowane jest przez długość ścieżki: każdy logiczny dostęp przenosi O(log N) puszek, każda z nich przechowuje niewielką stałą liczbę bloków, co skutkuje ogólnym wzrostem przepustowości o współczynnik O(log N) razy wielkość bloku zamiast O(N) współczynnika dla podejścia "zmieść wszystko", albo wyższych wielopoli-logarytmicznych czynników w wcześniejszych hierarchicznych schematach ORAM. Ta wydajność uczyniła go głównym narzędziem wykorzystywanym w projektach bezpiecznych procesorów, takich jak kontrolery pamięci bezobsługowych opartych na Intel SGX, systemach zarchiwizowania w chmurze szyfrowanych, które chcą ukryć wzorce zapytań przed dostawcą przechowywania, oraz protokołach obliczeń wielopartyjnych, które potrzebują pamięci bezobsługowej jako elementu budulcowego. Rozważania są realne: występuje rzeczywisty narzut przepustowości i opóźnień w porównaniu z dostępem bez szyfrowania, klient musi utrzymywać niepokojąco złożony stan lokalny, taki jak mapa pozycji i stash, a naiwne rekurencje dla mapy pozycji wymagają ostrożności, aby uniknąć zamieniając się na wąskie gardło. Mimo to, w scenariuszach, w których wyciek wzorców dostępu jest niedopuszczalny, takich jak zapytania prywatnych baz danych, szyfrowane wyszukiwanie lub wykonywanie bezobsługowego kodu, Path ORAM pozostaje jednym z najbardziej praktycznych i szeroko stosowanych rozwiązań dostępnych.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Path ORAM: Hiding Memory Access Patterns i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.