一種帶權單鏈表多分支樹云數據完整性驗證方案

朱 彧，陳 越，嚴新成，王曉晶

1(戰略支援部隊 信息工程大學，鄭州 450001)

2(陸軍參謀部附屬單位，北京 100042)

E-mail:619717409@qq.com

1 引 言

云計算作為時下熱門的信息技術，通過共享自己的強大集中的資源為用戶提供服務，根據用戶需求分配資源來完成用戶的計算或存儲任務，因此越來越多的用戶選擇使用云計算服務.云存儲服務是云計算的核心服務之一，云服務提供商(CSP,Cloud Service Provider)搭建具有強大存儲能力的云系統并向用戶提供數據存儲服務.云存儲服務具有低成本、高擴展性、易于運行維護和訪問不受時間地點約束等優點.但近年來發生的安全事故表明，其也存在著嚴重安全隱患.2017年1月31日，Gitlab由于遭受到DDoS攻擊，運維人員在修復過程中，執行了錯誤的命令，導致約300GB的用戶數據被刪除，近6個小時的用戶數據丟失.2018年8月，騰訊云的客戶清博數據科技有限公司所屬的“前沿數控”平臺的一塊操作系統云盤發生故障，致其文件系統數據損壞.

這些事故使得用戶擔心自己存儲在云系統中數據的安全，因為一旦數據被存儲到云系統上，用戶就無法像管理本地數據那樣管理云端數據了.云系統可能因為軟硬件故障導致數據丟失或損壞，惡意的攻擊者可能會破壞或篡改用戶數據，云服務提供商也可能丟棄那些長時間未被訪問或很少被訪問的數據以達到節省存儲空間的目的.但云服務提供商出于維護自身聲譽或者避免賠償等目的隱瞞這些事故，并向用戶聲稱數據仍然被完整地存儲在云系統中.如何高效靈活地驗證存儲在云端數據的完整性是亟待研究的問題[1]，而數據完整性驗證方案可以很好的解決這個問題.

2 相關工作

數據完整性驗證方案根據存儲數據是否可恢復分為數據持有性證明(Provable Data Possession,PDP)[2]和數據可恢復證明(Proofs of Retrievability,PoR)[3].PDP能夠快速判斷數據是否損毀，效率較高.而POR可以在一定程度上恢復損壞的數據，但效率較低.本文的研究主要關注PDP的效率等問題.Ateniese等提出了一種采用概率性策略完整性驗證方案[2]，利用RSA簽名機制的同態特性將證據聚集成一個小的值，降低了驗證過程中的通信開銷，但其不能支持動態更新操作.為了支持用戶對存儲在云系統上的數據進行動態更新操作，研究者們引進動態數據結構組織數據.Erway等引入跳表來組織數據，實現了支持塊級全動態更新操作[4]；Wang等采用Merkle哈希樹來保證數據塊在位置上的正確性，使得方案支持數據的動態更新[5].然而采用動態數據結構會由于數據塊的增多消耗很多的時間和空間，在驗證過程中需要傳遞很多的輔助驗證信息，增加了通信帶寬的開銷.為了提高驗證效率和減少驗證開銷，王瑞錦等將跳表數據結構進行改進，引入可達范圍記數，以便高效地支持數據塊在任意位置的更新操作[6]；Merkle哈希樹每個節點對應兩個子節點，而李勇等采用的多分支樹(large branching tree，LBT)中每個節點對應多個子節點，有效降低了樹的高度，簡化了數據動態更新過程[7]；方欣等對多分支路徑樹進行改進，降低了樹的高度，優化了存儲空間，但并沒有考慮到用戶多次更新后樹的不平衡問題，且采取線性組合計算證據導致用戶數據有被不可信第三方獲取的風險[8].針對上述問題，本文提出了采用帶權單鏈表多分支樹的云數據完整性驗證方案(weighted single linked list large branching tree scheme，WSLBTS),以進一步提高驗證效率并保護用戶數據隱私.其主要貢獻如下：1)相對于多分支樹，WSLBT將葉節點設置為鏈表，使得每一葉節點對應多個數據塊，進一步降低了樹的高度，縮短了構造時間和生成證據的長度；2)提出一種再平衡機制，可維持葉節點鏈表長度的平衡，提高了節點更新效率；3)采用了隨機掩碼技術[9]，使得第三方審計(Third Patry Auditor)無法從證據中得到數據的有關信息.

3 相關預備知識

3.1 雙線性對

假設G1,G2,GT都是素數階為p的乘法循環群，g1和g2分別是G1和G2的生成元，則雙線性對定義如下：

e:G1×G2→GT，

1)雙線性：?x∈G1,y∈G2?e(xa,yb)=e(x,y)ab；

2)非退化性：e(g1,g2)≠1；

3)可計算性：e能夠被高效地計算.

3.2 數據完整性驗證模型

為了減輕用戶端的負擔，數據完整性驗證方案一般引入具有很強計算和存儲能力的第三方審計，采用公開驗證的方法[10].數據完整性驗證方案驗證模型構成一般由三個實體構成，分別是用戶端、云系統和第三方審計(TPA).

用戶端將自己的數據上傳到云系統中，并且會在需要的時候向云系統發出請求將自己的數據取回.用戶端可以委托第三方審計(TPA)代替自己向云系統發出挑戰來驗證自己數據的完整性，因而需要向第三方審計提供必要的信息.

云系統能夠以經濟的價格為用戶提供持續的存儲服務，當用戶訪問或取回數據時，及時響應用戶的請求，并保證用戶數據的完整性和可用性；當在第三方審計發起完整性挑戰時，其應能夠誠實的計算證據并返回.

第三方審計是經過用戶認可的，擁有較強計算能力和存儲能力.在獲得用戶數據足夠的信息后，能夠代替用戶向云系統發起數據完整性驗證，根據云系統返回的證據計算判斷用戶數據是否被完整的存儲，并向用戶反饋結果.

數據完整性驗證方案一般包括密鑰生成算法、數據塊簽名算法、證據產生算法和證據驗證算法四個算法，具體描述如下：

密鑰生成算法(KeyGen)由用戶端運行，生成用于數據塊簽名的公鑰與私鑰.

數據塊簽名算法(TagGen)由用戶端運行，用上一算法生成的私鑰對用戶數據進行簽名并生成數據塊標簽.

證據生成算法(GenPro)由云系統運行，利用第三方審計發送過來的挑戰信息生成挑戰證據并返回.

證據驗證算法(VerPro)由第三方審計運行，根據云系統返回的證據計算驗證等式是否成立，并輸出驗證結果

3.3 隨機掩碼技術

4 WSLBTS構造

4.1 帶權單鏈表多分支樹(WSLBT)

Merkle哈希樹(Merkle Hash Tree，MHT)是滿二叉樹，僅在葉子節點存儲數據信息，每個中間層節點和根節點都有兩個子節點.在一般的完整性驗證方案中，每個葉子結點對應一個數據塊的哈希值，而每個父節點的值是由它的子節點的哈希值鏈接之后再次哈希得到，以此類推，得到根結點root的值.相比于Merkle哈希樹，多分支樹(large branching tree，LBT)中每個節點擁有多個子節點，子節點的個數被稱為多分支樹的出度，每個葉節點對應一個數據塊的哈希值.帶權單鏈表多分支樹(weighted single linked list large branching tree，WSLBT)中，葉子結點對應的不是單個數據塊的哈希值，而是鏈表，而每個結點上存儲的值為(rx,h(x)).其中rx表示從該節點開始能夠訪問到的數據塊數量，若x不是葉節點，則h(x)是x的子節點哈希值鏈接之后再次進行哈希運算得到的，若x是葉節點，則h(x)是x對應鏈表內所有數據塊的哈希值鏈接之后再次進行哈希運算得到.以此類推就可以計算得到根節點R的hroot值.

圖1 WSLBT數據結構

圖1是一個簡單的高度為3出度為3的WSLBT，其中葉節點D,E,F和非葉節點A及根節點R的值依次可由以下公式可得，B,C節點計算方式與A節點相似.

節點D=h(h(f1)||h(f2)…||(h(f10))

節點E=h(h(f11)||h(f12)…||(h(f20))

節點F=h(h(f21)||h(f22)…||(h(f30))

節點A=h(h(D)||h(E)||h(F))

節點R=h(h(A)||h(B)||h(C))

4.2 基本方案構造

構造的方案由以下幾個步驟構成.

4.2.1 初始化

4.2.2 發起挑戰

4.2.3 返回證據

運行算法GenPro.云系統收到挑戰信息后，根據索引值找到數據塊所在節點，并對WSLBT進行回溯，找到該節點到根節點之間路徑上所有兄弟節點，將兄弟節點值匯聚成一個集合作為輔助信息{Ωi}s1≤i≤sc.計算證據如公式(1)所示：

(1)

將證據Pro={h(Fi),S,P,{Ωi}s1≤i≤sc,Sigsk(hroot)}發送給挑戰方.

4.2.4 證據檢驗

用戶或第三方收到證據后，運行算法VerPro，進行以下驗證.

1)根據(h(Fi))和{Ωi}s1≤i≤se，用戶或第三方審計重新計算根結點值hroot′.

4.3 數據的動態更新

在實際應用中，用戶需要更新存儲在云系統中的數據，例如修改、插入、刪除等操作.當用戶更新數據時，需要向云系統提供更新數據塊的信息，如數據塊的位置和新標簽值等.云系統在收到信息后，對WSLBT進行更新，更新數據塊所在葉節點的值，并重新計算該葉節點到樹根節點上所有兄弟節點的值.和Merkle哈希樹及LBT相比，WSLBT的數據塊查詢效率要更高效，在同樣高度的情況下，可以存儲更多的數據塊.

4.3.1 修改

若用戶需要將數據塊F12更新為F12′，則發送更新消息{modify,12,F12′,T12′}到云系統.云系統收到更新消息，解析到這是個修改請求，將第12個數據塊改為F12′，并將相應的數據塊標簽改為T12′.此時需要將WSLBT一并更新，將該數據塊所在葉節點的值重新計算，并重新計算該葉節點到樹根節點上所有節點的值.

4.3.2 刪除

若用戶需要刪除數據塊F12，則向云系統發送更新消息{delete,12}.云系統解析到這是一個刪除消息，將數據塊F12及其標簽T12一并刪除，重新計算相應節點并更新WSLBT,結果如圖2所示.

圖2 刪除數據塊F12

4.3.3 插入

若用戶需要在數據塊F19和F20之間插入Fi，則發送更新消息{insert,19,Fi,Ti}到云系統.云系統解析到這是一個插入消息，將數據塊Fi插入到鏈表中F19和F20之間，重新計算鏈表對應的葉節點的值，并更新該葉節點到樹根節點上所有節點的值，需要重新計算的節點與刪除操作所更新節點相似.

4.4 樹的再平衡

在多次更新之后，WSLBT中葉節點對應鏈表的長度可能差距比較大，有些鏈表由于插入操作比較多導致鏈表長度很長，有些鏈表則由于刪除操作比較多長度會很短，這就造成了WSLBT的不平衡.當樹的不平衡十分嚴重的時候，查詢效率就會受到很大的影響，若要操作的數據塊在較長的鏈表中，那么就會需要很長的查詢時間.同時鏈表過長也導致葉節點值的計算開銷增大，因此需要一種機制來維持樹的平衡.

在用戶對數據進行多次更新后，WSLBT的葉節點所對應的鏈表長度可能不等.在WSLBT中，每個節點上存儲的信息(rx,h(x))不僅有節點哈希值h(x)，而且有該節點下數據塊的數目rx.如圖3所示，節點x,y,z的值分別為rx,ry,rz，假設rx>ry>rz，當最大的rx與最小的rz值相差大于閾值δ時，則稱節點x,y,z不平衡.此時需對該節點進行再平衡，計算所有節點r值的平均值r=[(rx+ry+rz)/3]，d=(rx+ry+rz)mod3.將前d個節點的數據塊值調整為r+1,其余節點的數據塊值調整為r，至此節點x,y,z之間實現了平衡.從根節點向下，對每一對兄弟節點進行再平衡，使得其節點之間r值最大最小之差小于閾值δ，從而實現WSLBT的平衡，平衡后的WSLBT如圖4所示.閾值δ選擇比較關鍵，如果過大，那么節點之間即便數據塊差距比較大也不會進行再平衡，如果閾值δ過小，那么WSLBT就會頻繁更新，造成系統資源的浪費.

圖3 不平衡狀態下的WSLBT

圖4 WSLBT的再平衡

5 正確性與安全性分析

5.1 正確性分析

(2)

5.2 安全性分析

在將數據存儲到云系統之后，用戶主要面臨的數據完整性驗證威脅有重放攻擊、丟失攻擊和篡改攻擊.

重放攻擊是云系統由于數據損壞、丟失或篡改之后無法提供有效證據時，將以前提供過的證據重復提供給用戶以期掩蓋數據不可用事實的行為.假設某些數據塊由于云系統的責任而不可用，那么在用戶發起完整性挑戰的時候，云系統可能將以前通過完整性驗證的證據再次返回以期通過驗證.但是由于隨機數vi參與證據的生成，同一批數據生成的證據S和P也是不同的.故云系統無法通過重放證據來通過驗證，隱瞞自己的失職行為.

丟失攻擊是云系統有意或無意將用戶數據丟失后，計算偽造證據并希望通過完整性驗證的行為.假設云系統丟失了數據塊Fi，那么就要偽造一個數據塊的標簽Ti=(H(Fi)uFi)x才能通過完整性挑戰.但是由于云系統并不知道私鑰x，不能偽造出正確的數據標簽通過完整性驗證，從而無法欺騙用戶.

篡改攻擊是云系統在用戶數據被篡改后，無法通過正常計算得出證據時，提供偽造證據的行為.假設數據塊Fi被非法篡改為Fi′，那么云系統同樣需要偽造出數據塊標簽才能通過驗證.但是由于哈希函數的抗碰撞性，不存在H(Fi)=H(Fi′)的情況.所以在數據塊被非法篡改的情況下，云系統是無法偽造出數據塊標簽的，也就不能通過完整性驗證的.

6 性能分析

6.1 根節點計算復雜度和通信效率分析

本方案與Wang[5]的基于Merkle哈希樹的方案和李勇[7]的基于多分支樹的方案相比，比較結果如表1所示，可以看出本方案在計算和通信開銷方面有所降低.

表1 方案性能比較

Table 1 Comparison for performance

方案支持公開驗證全動態操作根節點計算復雜度通信復雜度Wang否否O(log2N)O(log2N)李勇是是O(lognN)O(lognN)本文方案是是 O(logn(N/m))O(logn(N/m))

用戶要存儲的文件經初始化可以分為N個數據塊，用出度為n的多分支樹LBT來組織這些數據，那么葉節點的個數就為N，樹的高度為lognN.用WSLBT來組織數據，假設鏈表初始長度為m，出度為n，那么葉節點個數為N/m，樹的高度變為logn(N/m).可以看出，在數據塊總數和樹的出度相同的情況下，WSLBT有著更低的高度，根節點計算所需時間也就更短.為了進行效率分析，在Windows系統中用Java語言實現了方案基本功能.實驗環境為：CPU是Pentium(R)Dual-Core,內存為4GB.實驗將100M的文件劃分為10000個大小為10kb的數據塊，分別為其構造LBT和鏈表長度為50的WSLBT(當出度為2時，LBT樹可視為Merkle哈希樹)，結果如圖5所示.從圖中可以看出，在出度相同的情況下，WSLBT根節點計算時間總是要小于LBT的.

在完整性驗證的過程中，用戶需要和云系統進行信息的交互.云系統向用戶返回證據是帶寬開銷最大的過程.在這一過程中，云系統需要向用戶返回證據Pro={h(Fi),S,P,{Ωi}s1≤i≤sc,Sigsk(hroot)}，其中輔助信息{Ωi}s1≤i≤sc的長度是影響帶寬開銷最大的因素.實驗對比文獻[7]和本文方案在驗證單個數據塊時所生成證據中輔助信息Ω的大小(本文方案中鏈表長度設置為30)，得出結果見圖6.從圖中可以看出，在樹出度相同的情況下，本文方案產生證據中的輔助信息Ω要比文獻[7]小，證據更短，驗證時通信效率更高.

圖5 LBT與WSLBT構造時間對比

圖6 LBT與WSLBT生成證據中輔助信息大小對比

6.2 隱私保護與證據生成效率

本方案與文獻[8]相比，引入了隨機掩碼技術對數據塊進行簽名保護了用戶隱私，并且提出了再平衡機制來維持樹結構的平衡.

文獻[8]采用BLS簽名，對分塊后的數據Fi用公式Ti=(H(Fi)uFi)x來計算標簽.在驗證過程中，若第三方重復地對{s1,…,sc}位置上的數據進行檢測，每次挑戰請求為 chalj={si,vi(j)}，其中1≤i≤c,1≤j≤c，vi(j)表示第j次挑戰中第i數據塊對應的隨機數，經過c次挑戰后，就可以得到方程組(3):

(3)

文獻[8]采用的數據結構是單鏈表多分支樹(Single Linked List Large Branching Tree,SLBT)，將葉節點設置為單向鏈表，降低了樹的高度.該方案支持數據全動態更新，但在插入和刪除數據塊時鏈表長度會發生變化，WSLBT會出現不平衡狀態.葉節點對應鏈表長度過長時，重新計算該葉節點的值就會需要較長的時間.本方案所提出的再平衡機制可以保證WSLBT的平衡，避免出現葉節點對應鏈表過長的情況，提高了葉節點總體更新效率.實驗對比圖3和圖4狀態下(即平衡狀態和不平衡狀態)WSLBT葉節點更新所用時間，得出結果見圖7.從圖中可以看出，平衡狀態下的WSLBT在葉節點更新時所用的時間更少，更新效率更高.

圖7 WSLBT平衡與不平衡狀態下葉節點更新時長對比

7 結束語

隨著越來越多的用戶選擇將數據移植到云中，云存儲服務的安全成為保證用戶資源對服務忠誠度重要指標[11].數據完整性是云存儲服務安全中的重要組成部分，因而確保用戶數據完整性是最近研究的一個熱點.本文提出了基于帶權單鏈表多分支樹的數據完整性驗證方案，能高效地支持數據全動態操作，并保證多次動態操作后節點更新效率，適用于用戶數據頻繁更新的場景；引入隨機掩碼技術，保證了在第三方審計不可信時用戶數據的隱私安全.在下一步的工作中，如果能夠利用WSLBT的中間節點來存儲數據，方案效率會得到更進一步的提高.