李紅衛(wèi),古春生,白鳳娥
(1.江蘇理工學(xué)院 計算機工程學(xué)院,江蘇 常州 213001;2.江蘇理工學(xué)院 云計算與智能信息處理常州市重點實驗室,江蘇 常州 213001)
隨著云存儲技術(shù)的發(fā)展,越來越多的客戶將數(shù)據(jù)存儲在云服務(wù)器上,數(shù)據(jù)的安全也越來越受到重視。數(shù)據(jù)加密技術(shù)可以保護數(shù)據(jù)的內(nèi)容,但無法隱藏客戶對數(shù)據(jù)的訪問模式,攻擊者通過分析數(shù)據(jù)的訪問模式可能獲得存儲數(shù)據(jù)的信息。例如,攻擊者獲知醫(yī)生在診斷患者患有某種疾病時需要訪問某些記錄,當(dāng)某人就診時,醫(yī)生對這些記錄進行了訪問,攻擊者即可推斷出該人患有某種疾病。為了保護客戶的隱私,需要隱藏客戶對存儲系統(tǒng)的訪問模式,實現(xiàn)數(shù)據(jù)訪問的無關(guān)性(obliviousness)。所謂數(shù)據(jù)訪問的無關(guān)性是指對任意兩次數(shù)據(jù)訪問(不管是讀還是寫),所訪問的存儲位置的序列是等同的[1]。一種最簡單的解決方法就是每訪問一個數(shù)據(jù)時讀寫所有數(shù)據(jù)。每讀一個數(shù)據(jù)時先解密,寫回時再加密,每次加密所用的密鑰均不相同,使得攻擊者無法識別寫回的數(shù)據(jù)是原數(shù)據(jù)還是修改后的數(shù)據(jù)。但該方法的代價太大,因此,GOLDREICH O提出了無關(guān)RAM模型機(Oblivious RAM,簡稱O-RAM)[2]并解決這一問題。隨著云計算的飛速發(fā)展,在數(shù)據(jù)外包中O-RAM的應(yīng)用有著重要作用。
[1]提出最有效的隱藏訪問模式是采用分層結(jié)構(gòu)算法。在分層結(jié)構(gòu)算法中,如果洗牌算法采用AKS網(wǎng)絡(luò)排序[3]算法,則平均時間復(fù)雜度為O(c log4N),其常數(shù)項c大約為6 000。當(dāng)采用巴切排序網(wǎng)絡(luò)算法[4]時平均時間復(fù)雜度為O(c log4N),其常數(shù)項c大小較為合理[5]。
許多學(xué)者在參考文獻(xiàn)[1]的基礎(chǔ)上又提出了一些新的結(jié)構(gòu)[5-9]。其中參考文獻(xiàn)[5-6]在平均時間復(fù)雜度方面進行了深入的研究。若客戶端存儲容量為O(1)時,參考文獻(xiàn)[5]得到的平均時間復(fù)雜度為O(log2N),但一些研究人員已經(jīng)發(fā)現(xiàn)參考文獻(xiàn)[5]所提的結(jié)構(gòu)存在安全問題[6]。在參考文獻(xiàn)[6]所提出的結(jié)構(gòu)中,當(dāng)客戶端存儲量為O(1)時,獲得最好的平均時間復(fù)雜度為O(log2N);若客戶端存儲容量為時,可獲得的平均時間復(fù)雜度O(log N)。參考文獻(xiàn)[7-9]在最壞時間復(fù)雜度方面做了研究。參考文獻(xiàn)[7]得出最壞時間復(fù)雜度為,但其平均時間復(fù)雜度也是。參考文獻(xiàn)[8]提出一種新的O-RAM結(jié)構(gòu),當(dāng)客戶提供存儲空間時,其平均時間復(fù)雜度為O(log2N),最壞時間復(fù)雜度為。參考文獻(xiàn)[9]的最壞時間復(fù)雜度為O(log3N)。
以上所提算法均由兩個階段構(gòu)成,即訪問階段和洗牌階段,算法的瓶頸就在洗牌階段。在洗牌時,客戶與服務(wù)器之間需要進行大量的數(shù)據(jù)交換,使得客戶無法忍受洗牌過程占用的大量時間。如果能把洗牌過程分解到每次訪問操作中,對服務(wù)器的訪問時間保持在常數(shù)量級,這樣就能將理論應(yīng)用于實踐中。因此,本文提出一種新的結(jié)構(gòu),在需要少量客戶端存儲空間和線性級服務(wù)器存儲容量的情況下,使得每次操作的代價為O(1)。典型算法的性能比較[9]如表1所示。
表1 幾種典型算法的性能比較
本文假設(shè)客戶端可信而服務(wù)器端不可信。O-RAM的目標(biāo)就是對服務(wù)器完全隱藏數(shù)據(jù)訪問模式,即從服務(wù)器角度觀察,客戶端每次讀或?qū)憯?shù)據(jù)塊請求將產(chǎn)生一個完全隨機的數(shù)據(jù)訪問序列。
假設(shè)客戶的數(shù)據(jù)大小為N塊,每塊大小為L字節(jié),在云存儲中,L的典型值一般為64 KB~256 KB。本方案需要占用服務(wù)器存儲容量為3N塊,利用均勻隨機函數(shù)將N個數(shù)據(jù)塊均勻隨機地分布到3N個存儲塊中,其余2N個存儲塊存放啞元塊。
在客戶端設(shè)置一個緩存隊列Q、兩張數(shù)據(jù)表SerMap和PosMap。
緩存隊列Q用來管理從服務(wù)器讀取的數(shù)據(jù)塊,本文假定最多可存儲32個數(shù)據(jù)塊。對緩存隊列的操作有:Q.in(b)將數(shù)據(jù)塊b插入隊尾;Q.out()從隊首移出數(shù)據(jù)塊;Q.remove(b)將數(shù)據(jù)塊b從緩存隊列中移出;Q.getLen()返回緩存隊列中存放的數(shù)據(jù)塊數(shù);Q.getSit(b)返回數(shù)據(jù)塊b在緩存隊列中的位置;Q.getSitF()返回隊首數(shù)據(jù)塊的塊號。
SerMap[3N]用來表示存儲在服務(wù)器上各數(shù)據(jù)塊的存儲位置,它有3個域,分別是FlData、FlAcc和Fresh。Fl-Data表示存儲類型,其值為1表示該塊為數(shù)據(jù)塊,否則為啞元塊;FlAcc表示其對應(yīng)的存儲塊最近是否被訪問過。當(dāng)讀/寫存儲塊后,該變量的值設(shè)置為1。在查找一個啞元塊時,若其值為0則選中該塊,若其值為1則改為0,繼續(xù)查找下一個啞元塊;Fresh表示服務(wù)器存儲塊的新鮮度,在對服務(wù)器的每次讀操作后都會使該變量的值增1,以保證相同數(shù)據(jù)在加密后結(jié)果不一樣。
PosMap[N]用來表示用戶數(shù)據(jù)塊在服務(wù)器中存放的位置映射,包括flag和blockAdd兩個域。flag表示數(shù)據(jù)塊存放在服務(wù)器/本地的標(biāo)志,若其值為1時,則表示數(shù)據(jù)塊存放在服務(wù)器端,否則存放在Q中;blockAdd指數(shù)據(jù)塊在SerMap/Q中的位置。
定義1:設(shè)客戶對服務(wù)器的操作為(op,u,data),其中,op表示read(u)或者write(u,data)操作,u表示將要讀或?qū)懙臄?shù)據(jù)塊標(biāo)識,data表示要寫的數(shù)據(jù)塊。
無論op是讀操作還是寫操作,其訪問服務(wù)器的序列由Lookup算法決定。
2.2.1 Lookup算法
Lookup算法描述如下:
Lookup(op,u,data*);
1:Random read n(n<=6)blocks from server;
2:if(PosMap[u].flag=0)then{//所讀塊在Q中
3:ReadDummy(); //隨機讀一啞元塊
4:Q.remove(u);Q.in(u); //將該塊從Q中移出再插入隊尾
5:}else
6:ReadBlock(u); //從服務(wù)器端讀數(shù)據(jù)塊u并插入Q中
7:Random read 6-n blocks from server;
8:if(op=write)then
9:Q.bufs[PosMap[u].blockAdd]←data*;//將要寫的數(shù)據(jù)保存在Q中相應(yīng)的緩沖區(qū)中
10:Evict(); //為避免Q溢出,將部分?jǐn)?shù)據(jù)塊寫入服務(wù)器
11:return(PosMap[u].blockAdd);
在該算法中第1行和第7行共讀服務(wù)器6次,其中隨機讀取2個數(shù)據(jù)塊和4個啞元塊,需要把所讀的數(shù)據(jù)塊保存在Q中。第2行至第6行讀取指定的數(shù)據(jù)塊u并保存在Q中。如果數(shù)據(jù)塊u已在Q中,則隨機讀一啞元塊。根據(jù)程序局部性原理可知,最近訪問的數(shù)據(jù)塊在最近的將來仍有可能再被訪問到,因此對Q的管理并不按照嚴(yán)格意義上的先進先出策略,而是當(dāng)訪問的數(shù)據(jù)塊在Q中時,將該塊從Q中移出并放到隊尾,以保證從Q中踢出的數(shù)據(jù)塊是不常用的數(shù)據(jù)塊。
當(dāng)op是寫操作時,將要寫的內(nèi)容覆蓋Q中保存數(shù)據(jù)塊u的緩沖區(qū)(第9行)。在每一次Lookup調(diào)用中,不停地有數(shù)據(jù)塊存入Q中,Q總會變滿,因此需要定期將Q中的數(shù)據(jù)塊寫入服務(wù)器以防止Q溢出,第10行是調(diào)用Evict將Q中的最久未用的數(shù)據(jù)塊寫入服務(wù)器。
2.2.2 Evict算法
Q中最多可存放32個數(shù)據(jù)塊,調(diào)用一次Lookup最多有3個數(shù)據(jù)塊進入Q中。因此,在Evict算法中,當(dāng)Q的長度超過29時,則將超出的數(shù)據(jù)塊寫入服務(wù)器以保證Q在下一次Lookup操作時不會溢出。Evict算法描述如下:
Evict() //寫數(shù)據(jù)塊或啞元塊到服務(wù)器
1∶m←0
2∶while(Q.getLen()>29)do{
3∶WriteBlock(); //將Q中隊首數(shù)據(jù)塊寫入服務(wù)器
4∶m←m+1
5∶}
6∶for i=m+1 to 6 do
7∶WriteDummy(); //隨機寫啞元塊到服務(wù)器中
8∶return;
第1行至第5行將數(shù)據(jù)塊寫入服務(wù)器。Evict踢出算法每次寫6次服務(wù)器,先將緩存隊列中的數(shù)據(jù)塊寫入服務(wù)器,然后用啞元塊補足6塊(第6行至第7行)。
每執(zhí)行一次Lookup都會將任意兩個數(shù)據(jù)塊讀入Q中,當(dāng)Q長度超過29時,就將超出的數(shù)據(jù)塊寫到服務(wù)器端的任意位置,實現(xiàn)洗牌操作,這樣可將整個洗牌操作分?jǐn)偟矫看蜭ookup中,避免了集中洗牌造成的突發(fā)訪問。
假定存儲塊大小為64 KB,參考文獻(xiàn)[9]與本文性能對比如表2所示。當(dāng)數(shù)據(jù)文件小于等于16 TB時,所用客戶存儲空間小于參考文獻(xiàn)[9],當(dāng)數(shù)據(jù)文件大于16 TB時,所需客戶存儲量超過參考文獻(xiàn)[9]。本文算法的優(yōu)勢在于所需服務(wù)器存儲空間較少,實際性能恒定。參考文獻(xiàn)[9]采用集中洗牌,當(dāng)洗牌時需要大量的數(shù)據(jù)交換,當(dāng)客戶在讀寫操作時,若正好遇上洗牌操作,則需要等待很長時間。
表2 參考文獻(xiàn)[9]與本文性能對比
定義2:設(shè)y=((op1,u1,data1),(op2,u2,data2),…,(opM,uM,dataM))是客戶請求訪問數(shù)據(jù)塊的一個序列,其長度為M。設(shè)A(y)表示存取訪問模式,當(dāng)客戶的請求序列是y時,用A(y)表示存取訪問服務(wù)器的序列。如果對于任何兩個客戶訪問序列y和y′,只要其長度相等,對任何人(除客戶本人)來說A(y)和A(y′)都是計算上不可區(qū)分的,則稱該O-RAM結(jié)構(gòu)是安全的。
在Lookup中,數(shù)據(jù)塊u在服務(wù)器上的存儲位置是隨機分布的,讀取u和6次隨機讀數(shù)據(jù)塊操作混在一起,攻擊者很難猜到哪一塊是真實的塊,并且攻擊者很難知道下一次它將存放在哪一個位置。
在訪問服務(wù)器的過程中可能出現(xiàn)剛被淘汰出的數(shù)據(jù)塊又要被訪問的情況。這種情況下,攻擊者仍然無法獲取有用的信息,因為至少有2/3的數(shù)據(jù)塊是隨機選取讀到Q中的,最多有1/3的數(shù)據(jù)塊是客戶所讀的數(shù)據(jù)塊,但Evict算法采用最久未用塊淘汰策略,攻擊者無法知道所讀的塊是否為所需的數(shù)據(jù)塊,也無法知道什么時間該塊會寫入服務(wù)器,即攻擊者從被踢出后又要被訪問的數(shù)據(jù)塊中無法獲取有用的信息,因此系統(tǒng)是安全的。
本文提出的常量級訪問模式僅需占用線性級服務(wù)器存儲量就可實現(xiàn)無關(guān)訪問服務(wù)器,但它需要占用客戶端存儲空間,當(dāng)文件長度超過16 TB時,比參考文獻(xiàn)[9]的算法占用更大的客戶端存儲空間。下一步工作將在減少占用客戶端存儲空間方面進行研究,找到一個需求客戶空間更少的算法。
參考文獻(xiàn)
[1]GOLDREICH O,OSTROVSKY R.Software protection and simulation on oblivious RAMs[J].Journal of the ACM,1996,43(3):431-473.
[2]GOLDREICH O.Towards a theory of software protection and simulation by oblivious RAMs[C].New York:STOC,1987.
[3]AJTAI M,KOLMOS J,SZEMEREDI E.An O(nlogn)sorting network[C].Boston:STOC,1983.
[4]BATCHER K.Sorting networks and their applications[C].NJ:AFIPS Spring Joint Computing Conference.1968.
[5]PINKAS B,REINMAN T.Oblivious ram revisited[C].California:CRYPTO.2010.
[6]GOODRICH M T,MITZENMACHER M.Privacy-preserving access of outsourced data via oblivious ram simulation[J].Automata,Languagesand Programming,2011(6756):576-587.
[7]BONEH D,MAZIERES D,POPA R A.Remote oblivious storage:Making oblivious ram practical[EB/OL].[2011-3-30].http://dspace.mit.edu/bitstream/handle/1721.1/62006/MITCSAIL-TR-2011-018.pdf.
[8]STEFANOV E,SHI E,SONG D.Towards practical oblivious ram[C].California∶NDSS,2012.
[9]SHI E,CHAN T H H,STEFANOV E,et al.Oblivious RAM with o((logn)3)worst-case cost[C].Seoul:ASIACRYPT,2011.