Path ORAM: Bellek Erişimini Gizleme

Stefanov, van Dijk, Shi, Fletcher, Ren, Yu ve Devadas (2013) tarafından önerilen Yol ORAM, uygulamada en etkili ORAM yapısıdır. Sunucu depolamasını, her yaprağın bir veri bloğu için bir konuma karşılık geldiği ikili kovalardan oluşan bir ağaç olarak düzenler. Yol ORAM, temel biçiminde erişim başına O(log^2 N) iletişim ek yüküne ulaşır ve birkaç yüz satır kodla uygulanabilecek kadar basittir.

Konum haritası, her mantıksal blok adresini ikili ağaçtaki bir yaprak düğümüne eşleyen istemci taraflı bir veri yapısıdır. Yüksekliği L = log N olan bir ağaçtaki N bloktan oluşan bir veritabanı için konum haritası, N yaprak indisinden oluşan bir dizidir. İstemci, b bloğuna erişmeden önce konum haritasında bloğun o anda atanmış olduğu yaprağı arar ve ona yeni, rastgele bir yaprak atar. Eski yaprağın yolu sunucudan okunur ve sunucuya geri yazılır.

Geçici depo, sunucudan okunmuş ancak henüz geri yazılmamış blokları geçici olarak tutan, istemci taraflı küçük bir arabellektir (genellikle 20-40 blok). Bir blok okunduğunda yolundan çıkarılır ve geçici depoya yerleştirilir. Bloğa erişildikten ve gerekirse değiştirildikten sonra, geçici depodaki yeni yola yerleştirilebilen tüm bloklar geri yazılır. Bir yola sığamayan bloklar geçici depoda kalır.

Sunucu depolaması, L+1 seviyeden oluşan tam bir ikili ağaçtır (L = log N). Her düğüm (kova) Z blok tutar (genellikle Z = 5). Yapraklar veri bloklarının konumlarına karşılık gelir. N yaprak düğümü bulunduğundan toplam 2N-1 düğüm ve O(NZ) toplam sunucu depolaması vardır. Her yapraktan köke uzanan yol log N düğüm içerir ve Z*log N blok tutabilir; bu da yol çıkarma stratejisi için gerekli kapasiteyi sağlar.

b bloğunu okumak için: (1) konum haritasında b için geçerli yaprak l'yi arayın; (2) b bloğuna yeni, rastgele bir yaprak l' atayın ve konum haritasını güncelleyin; (3) l yaprağından köke uzanan yoldaki tüm kovaları okuyun (log N kova); (4) b bloğunu okunan yolda veya geçici depoda bulun; (5) yeni l' yoluna atanabilen tüm blokları geri yazın ve kalan kova yuvalarını sahte bloklarla doldurun. Sunucu her seferinde rastgele bir yol okunduğunu görür.

Yol ORAM, hangi bloğa erişildiğinden bağımsız olarak her erişimde tam olarak bir kökten yaprağa yolu okuyup yazdığı için gözlemlenemezliği korur. Yol, blok içeriği veya adresi tarafından değil, eş olasılıklı rastgele bir yaprak ataması tarafından belirlenir. Her yolun aynı sayıda dolu yuvaya sahip olması için boş kova yuvaları sahte bloklarla doldurulur. Sunucuyu gözlemleyen bir saldırgan yalnızca rastgele yol erişimleri görür.

Her Yol ORAM erişimi, kökten yaprağa uzanan tek bir yolun okunmasını ve yazılmasını gerektirir: her biri Z blok içeren O(log N) kova. Blok boyutu B ve kova boyutu Z olduğunda, her erişim O(Z * log N * B) bit aktarır. Tipik parametrelerle (N = 2^20, Z = 5, B = 4KB) bu, açık metin erişimindeki 4KB'ye kıyasla erişim başına yaklaşık 400KB'dir; yani 100 kat ek yüktür. Özyinelemeli konum haritaları bunu blok cinsinden O(log^2 N) iletişime indirir.

Basit konum haritası, istemcide depolanan N girdi gerektirir; bu da tüm veritabanı kadar büyük, O(N) istemci depolaması demektir. Özyinelemeli konum haritası, konum haritasının kendisini daha küçük bir ORAM içinde özyinelemeli olarak depolayarak istemci depolamasını O(log^2 N) değerine düşürür. ORAM, geçici depoya sığacak kadar küçüldüğünde özyineleme sona erer. Bu, Yol ORAM'ı büyük veri kümeleri için uygulanabilir kılan standart tekniktir.

Yol ORAM'da bloklar, yol çakışmaları nedeniyle atanmış oldukları yollara çıkarılamazsa geçici depo boyutu büyür. Stefanov ve diğerleri, geçici deponun R bloğu aşma olasılığının R'ye göre üstel olarak küçüldüğünü kanıtlamıştır; standart analize göre bu olasılık en fazla 14 * (0.6002)^R değerindedir. R = 40 seçildiğinde başarısızlık olasılığı yaklaşık 2^{-38} olur ve bu sonuç, saldırgan tarafından seçilenler de dâhil olmak üzere tüm erişim dizileri için geçerlidir.

Yol ORAM'dan önce, uygulamadaki en iyi ORAM yapıları O(log^3 N) ek yüküne sahipti (Shi ve diğerleri, 2011, "O((log N)^3) En Kötü Durum Maliyetine Sahip Gözlemlenemez RAM"). Yol ORAM, çok daha basit bir yapıyla bunu O(log^2 N) değerine düşürdü. Sonraki çalışmalar (Devre ORAM, OptORAMa) sabitleri ve asimptotik sınırları daha da iyileştirmiştir, ancak Yol ORAM basitliği nedeniyle hâlâ en yaygın biçimde uygulanan yapıdır.

Yol ORAM, onlarca araştırma ve üretim sisteminde uygulanmıştır. ZeroTrace (Intel SGX + Yol ORAM), Obladi (bulut depolama üzerinde Yol ORAM) ve Opaque (Apache Spark üzerinde Yol ORAM) dikkate değer uygulamalardır. Stanford güvenli hesaplama grubu, açık kaynaklı bir C++ Yol ORAM uygulamasını sürdürmektedir. AWS, gizliliği koruyan veri analizi için araştırma prototipleri olan Nitro Enclaves'in bir parçası olarak Yol ORAM sunar.

Yol ORAM'da konum haritasının rolü nedir?

Yol ORAM, sunucu depolamasını ikili bir ağaç olarak düzenler ve her erişimde kökten yaprağa uzanan tek bir yolu okur veya yazar. Konum haritası her bloğun o anda atanmış olduğu yaprağı izler; geçici depo ise yakın zamanda erişilmiş blokları arabelleğe alır. Her erişim, yeni ve rastgele yaprak konumları atanarak rastgeleleştirilir; böylece sunucunun gördüğü tüm erişimler aynı dağılıma sahip olur. İletişim ek yükü erişim başına O(Z * log N) değerindedir. Özyinelemeli konum haritaları istemci depolamasını O(log^2 N) değerine düşürür. Yol ORAM, en yaygın biçimde uygulanan ORAM yapısıdır.