面向公有云的數據完整性公開審計方案

繆俊敏,馮朝勝,2,李 敏,劉 霞

(1.四川師范大學 計算機科學學院,成都 610101; 2.電子科技大學 信息與軟件工程學院,成都 610054)(*通信作者電子郵箱csfenggy@126.com)

0 引言

云存儲已引起學術界以及其他各行各業的廣泛關注,但這種新的數據存儲模式也帶來了許多安全挑戰[1],其中之一就是如何確保在半可信服務器上的用戶數據完整性。數據審計是確保云數據完整性的重要方法,現有方案分為公開審計和私有審計兩大類。私有審計因為由數據所有者負責,故不存在隱私泄漏給第三方審計者(Third Party Audit, TPA)的問題,不足是審計時要求數據所有者在線且需要消耗其主機資源;而公開審計無需數據所有者在線且不會占用其資源,但需考慮數據泄漏給第三方的問題。另外,由于用戶及TPA都未保存原數據,所以需要一個有效的方法判斷審計過程中云存儲服務器(Cloud Storage Server, CSS)是否按照要求計算返回對應數據塊的相關數據。

本文基于MHT-PA(Merkle Hash Tree-Public Auditing)方案[2-3]提出了一種面向公有云的數據完整性公開審計方案,該方案在支持動態更新和批量審計的基礎下實現了針對第三方審計者的隱私保護，并避免了針對CSS的替代攻擊。

1 相關研究

Deswarte等[4]在2003年提出了第一個基于RSA(Rivest-Shamir-Adleman)的遠程數據審計方案,幾年后,Ateniese等[5]使用同態可驗證標簽技術[6]首次提出支持公開審計的可證明數據持有(Provable Data Possession, PDP)方案并在文獻[7]中進行改進，提出了可擴展PDP模型，以支持動態操作；但該方案并不支持數據塊插入。次年,Erway等[8]首次探索動態PDP方案架構,提出了基于等級的認證跳表(Rank-based Authenticated Skip List, RASL)概念,并在之前的可擴展PDP模型基礎上廢除了標簽索引信息以實現支持包括數據插入的完全數據更新操作的PDP方案；但該方案不支持批量審計和數據隱私保護。由于PDP方案僅支持驗證數據的完整性,不能保證數據的可恢復性。Juels等[9]提出了一個專注于大文件靜態存儲的可恢復證明(Proof of Retrievability, PoR)方案,但挑戰次數有限。Shacham等利用BLS(Boneh、 Lynn和Shacham)簽名[10]在文獻[11]中提出了一個支持公開審計的緊湊PoR方案,但該方案同樣只支持靜態數據且容易泄露用戶隱私信息。

Wang等利用同態可驗證標簽技術和數據分段技術先后在文獻[2,12-13]中引入TPA提出了云數據完整性公開審計方案,以克服以上方案的不足，他們在文獻[12]中提出了在分布式情況下考慮動態數據存儲且能定位錯誤數據的云存儲安全性方案；后在文獻[2]中引進Merkle哈希樹(Merkle Hash Tree, MHT)提出了新的改進方案,其可應用在PDP或PoR方案中,支持完全數據更新操作,且TPA能高效進行數據完整性批量審計，但該方案引入了新的隱私泄漏問題。雖然文獻[13-14]利用同態密鑰隨機掩碼技術解決了此問題,但本文中的哈希值混淆法在解決問題的基礎上減少了對應審計階段的TPA計算量。文獻[15]在文獻[2]基礎上通過改進MHT實現了支持細粒度更新數據的功能,文獻[16]則將多個副本的MHT合并成一個MHT以提高效率；但這些方案都會帶來CSS在數據不完整的情況下仍可偽造應答證據欺騙審計的安全問題,本文利用基于MHT的覆蓋樹加強了審計過程，避免了半可信的CSS發起此偽造攻擊。

2 MHT-PA方案

2.1 方案概要

MHT-PA方案[2]如圖1所示。客戶端首先將文件預處理后化分成多個數據分塊,對每一個數據分塊進行簽名得到簽名集合,再創建一棵Merkle哈希樹,并對根節點簽名。最后將原文件、簽名集合、根節點簽名值及一些附加信息一并存入CSS。客戶端做了審計委托后當TPA需要審計時,由TPA選取部分數據塊,并為每個數據塊選取一個隨機數,組成一個挑戰請求發送給CSS。CSS收到挑戰請求之后通過塊索引找到相應數據塊及其標簽,計算出證據返回給TPA。TPA隨后驗證收到的證據從而判斷云數據的完整性。

圖1 MHT-PA方案基礎架構Fig. 1 Basic architecture of MHT-PA

其方案具體實現過程如下:

構建雙線性映射e:G×G→GT,其中G和GT是乘法循環群,生成元為g,大素數階為p,令一個映射到G的散列函數H(·):{0,1}*→G,一個映射成定長字符串的散列函數h(·)。

1)初始化階段。客戶端首先將文件F預處理后化分成n個數據分塊mi(i∈[1,n]),其中mi∈Zp。選擇一個隨機數α∈Zp,并計算出υ←gα,再另外隨機選擇一對簽名公私鑰(spk,ssk),形成最終的公私鑰對,其中私鑰為sk=(α,ssk),公鑰為pk=(υ,spk)。在G中隨機選擇一個元素u,結合文件名name,文件塊數n及對其的簽名得到文件標簽t=(name‖n‖u‖ssigssk(name‖n‖u)),對文件的每個數據塊進行簽名σi=(H(mi)·umi)α,得到文件簽名集φ={σi|1≤i≤n}。同時創建以{h(H(mi))|1≤i≤n}為葉子節點的MHT,用私鑰α對根節點R進行簽名得到sigR=(H(R))α。最后,客戶端將{F,t,φ,sigR}發送給CSS,并將本地存儲刪除。

2.2 方案的不足

MHT-PA方案支持第三方公開審計協議以及完全動態數據更新操作,用戶利用私鑰對數據塊進行簽名后,TPA利用公鑰即可完成審計工作。相對于Juels等[9]提出的方案,該方案的驗證次數不受限制。方案中使用的簽名標簽具有同態特性,使得云服務器生成證據時,能夠將多個值聚合成一個值,從而減少通信開銷。但是MHT-PA方案存在兩個問題：一方面由于MHT-PA方案沒考慮數據的隱私保護,用戶的隱私信息可能會泄漏給TPA；另一方面,為了支持完全動態數據操作,去除了文獻[9]和文獻[11]方案中簽名的索引信息,用H(mi)替換h(v‖i)和H(name‖i),使得TPA不能通過自身保存的索引號{s1,s2,…,sc}驗證返回的證據正確性,因而云存儲服務端由于各種原因可以不按要求,而根據已有數據偽造應答證據,而偽證據不能被MHT-PA方案的審計策略所識別,依然能通過驗證。

2.2.1 泄漏用戶隱私

半可信的TPA對相同的數據塊發起多次審計請求后會收到CSS返回的多條審計證據,通過分析并處理這些證據信息可以恢復出用戶的數據信息,具體過程分析如下。

(1)

由于方程(1)的系數行列式不重復且不為零,TPA可以通過拉格朗日插值法或高斯消元法計算得到{mx1,mx2,…,mxc}的值,從而獲取用戶信息,致使用戶數據信息不安全。

2.2.2 CSS證據替代

MHT-PA方案中,TPA自身保存的索引號失去了驗證CSS返回數據正確性的作用后,數據塊信息mi在脫離原始文件后也不再為用戶所知,而用戶和TPA都未保存,且TPA也不能獲取mi,無法計算出H(mi),因此必須交由CSS計算,且沒有一種有效的方式驗證其是否按正確的順序返回正確的H(mi)。在源文件增、刪、改后,所創建MHT的樹結構不一定為簡單的滿二叉樹且用戶和第三方都未保存,只能由CSS返回。然而,半可信的云服務提供商可以利用這些優勢操控MHT以及H(mi)和mi,用其他數據塊作替代,偽造證據欺騙驗證者。

假設CSS保存的文件MHT如圖2所示。TPA想要通過驗證數據塊m1和m2來檢查文件的完整性。若文件完整且云存儲服務端正常返回,則順利通過驗證并返回TRUE,但當云存儲服務端中m1和m2數據不完整或其他某種原因時,便可用已有的正確數據如m3和m4來計算得到證據返回給驗證者TPA。

圖2 文件的MHT示例Fig.2 Example of MHT authentication of data elements

首先,若CSS正常返回,TPA通過返回的H(m3)和H(m4)以及伴隨節點信息h(b)和h(d)構造出圖3(a)的樹得出正確的R通過第一步驗證,但由于各種原因,CSS把已有的數據H(m3)和H(m4)以及伴隨節點信息h(b)和h(e)發送給TPA,TPA收到這些數據過后,無法判斷數據正確與否,按照CSS的想法構造出圖3(b)的樹且同樣能得出正確的根節點R的值,進而順利通過第一步驗證:e(sigR,g)=e(H(R),gα)。

圖3 替代攻擊示例Fig. 3 Example of alternative attack

(2)

式(2)左邊:

e((H(m3)·um3)ν1·(H(m4)·um4)ν2,gα)=

e((H(m3)ν1·uν1m3)·(H(m4)ν2·uν2m4),υ)

式(2)右邊:

e(H(m3)ν1·H(m4)ν2·uμ′,υ)=

e(H(m3)ν1·H(m4)ν2·uν1m3+ν2m4,υ)=

e((H(m3)ν1·uν1m3)·(H(m4)ν2·uν2m4),υ)

可見,式(2)成立,第二步驗證也同樣通過。因此,云存儲服務端通過偽造的證據成功欺騙了TPA。

3 本文公開審計方案

3.1 改進策略

圖4 TPA和CSS所得覆蓋樹示例Fig. 4 Examples of overlay trees calculated by TPA and CSS

采取如下步驟和措施防止CSS操控MHT和H(mi)進行審計替代:1)TPA在發起正式驗證挑戰前先向CSS請求壓縮后的文件MHT樹結構。解壓后簡單判斷樹的葉子節點數與文件數據塊數目是否相等,若不等則直接返回FALSE。2)根據文件的MHT樹結構選取要驗證的數據塊,由這些數據塊序號和MHT樹結構得到覆蓋樹(即能從所選葉子節點出發由下往上涉及最少節點數得到根節點的樹，其為MHT的子結構)的樹結構T(如圖4(a)所示)并保存待用。3)CSS接收到TPA挑戰請求后亦由這些數據塊序號和MHT得到覆蓋樹T′(如圖4(b)所示)作為證據的一部分返回。4)TPA在接收到證據后首先匹配兩棵覆蓋樹的結構，匹配成功后方才將{H(mi)|x1≤i≤xc}依次取出存儲,并計算出對應的{h(H(mi))|x1≤i≤xc},進而求得R進行下面的驗證。

3.2 方案描述

3.2.1 初始化階段

令雙線性映射函數e:G×G→GT,其中G和GT是乘法循環群,且生成元為g,大素數階為p。令H(·)是映射到G域的散列函數{0,1}*→G,f(·)是映射到Zp域的單向散列函數:{0,1}*→Zp,h(·)是基于安全哈希算法(Secure Hash Algorithm, SHA)的散列函數[17]。

1) 生成公私鑰對KeyGen(1k)→(sk,pk)。

由客戶端執行,生成方案基本參數。根據輸入的安全參數1k選擇一個隨機數α∈Zp作為主私鑰,計算出公鑰υ=gα,再隨機產生一個附加簽名公私鑰對(spk,ssk),形成最終的私鑰sk=(α,ssk)以及公鑰pk=(υ,spk)。

2)生成同態簽名集SigGen(sk,F)→(φ,sigR)。

由客戶端執行,生成數據塊的簽名及驗證元數據,并將其傳入CSS中存儲。首先將文件F用里德所羅門編碼(Reed-Solomon Codes)[18]預處理,劃分成n塊數據塊mi(i∈[1,n])∈Zp。在G中隨機選擇一個元素u,結合文件標識FName和文件數據塊總塊數n,再用附加私鑰ssk對這三元組做簽名得到文件標簽t=FName‖n‖u‖sigssk(FName‖n‖u)。利用私鑰α和元素u對每個數據塊mi進行簽名得到σi=(H(mi)·u(mi f(mi)) mod p)α∈G,構成同態簽名集合φ={σi|1≤i≤n}。構建以數據塊哈希值{h(H(mi))|1≤i≤n}為葉子節點的MHT,對樹的根節點簽名得到sigR=(H(R))α,最后把元組{F,t,φ,sigR}發送CSS并將本地文件存儲刪除。

3)云存儲初始化CSSInit(F,t,φ,sigR)。

由CSS執行,做相關初始化操作。接收到用戶的源文件和簽名信息等數據后,先做相應存儲,當第一次接收到用戶增刪改請求或TPA的審計請求時構建以數據塊哈希值{h(H(mi))|1≤i≤n}為葉子節點的MHT,并將其結構或部署策略保存。

4)審計委托AudDel(FName)。

由客戶端執行,把需第三方審計的文件標識告知給TPA,作審計委托。

3.2.2 審計階段

1)驗證準備PreChal(pk,t,tree)→(I,T)。

由TPA執行,為發起正式審計挑戰做基礎檢查及相關準備。TPA先向云存儲服務端獲取文件標簽t以及壓縮后的MHT樹結構tree,并用附加公鑰驗證標簽,若驗證通過則取出文件塊數n及驗證時需用的元素u。根據得到的文件結構樹tree,判斷其根節點數,即文件塊數是否等于n,若不等則直接返回FALSE中止審計,反之分析樹結構,從數據塊索引[1,n]中選取需要驗證的c個最優元素,構成有序的索引子集I={s1,s2,…,sc},其中s1≤s2≤…≤sc。根據tree及序號集I計算出覆蓋樹T(節點不含值)并保存。

2)發起挑戰StatGen(1k)→(chal)。

?OECD，Competitive Neutrality:Maintaining a level playing field between public and private business，Paris:OECD Publishing，2012，p．53．

由驗證者TPA執行,向CSS發起正式的審計挑戰。對集合I中每一個值i,選擇一個隨機數νi∈Zp,形成一個挑戰請求chal={(i,νi)|i∈I}發送給CSS。

3)生成證據ProofGen(F,φ,chal)→proof。

4)驗證證據ProofVerify(pk,proof,T,chal)。

由TPA接收到CSS傳回來的證據后執行,驗證證據返回TRUE或FALSE。第一步,判斷CSS端返回的覆蓋樹T′和自身計算的覆蓋樹T的樹結構是否相同,若有異則直接返回FALSE;反之,從覆蓋樹T′中提取{H(mi)|s1≤i≤sc}另存后,計算出{h(H(mi))|s1≤i≤sc}替換對應值,若各葉子節點完整則可計算出根節點R。第二步,驗證式(3)判斷根節點R的值是否正確,若驗證失敗,說明返回的{H(mi)|s1≤i≤sc}數據有誤或者其他挑戰驗證外的數據塊信息錯誤,直接返回FALSE。第三步,檢驗式(4)是否成立,其中{H(mi)|s1≤i≤sc}已在第一步中得到。

e(sigR,g)=e(H(R),gα)

(3)

(4)

3.2.3 動態更新

本文方案支持完全動態更新操作,由于更新操作不涉及第三方,所以不存在對TPA的隱私保護問題。方案增加修改刪除數據塊操作與MHT-PA方案相同,具體操作請參看文獻[2]。

4 安全性及性能分析

4.1 安全性分析

本文方案的安全性基于CDH問題(Computational Diffie-Hellman problem)難以求解,且經過里德所羅門編碼后的文件可以在可忽略不計的差錯下恢復出原始文件,以上兩點在文獻 [2] 中已經證明,由于篇幅所限,本文不再贅述具體證明過程。本文方案的正確性及安全性,主要提供兩方面的證明:1)TPA在審計云數據過程中無法獲取或分析得到用戶數據信息；2)CSS無法用其他手段偽造證據欺騙TPA。

定理1 基于所提出的公開審計方案,TPA在審計云數據過程中無法獲取或分析得到用戶數據信息。

(5)

由于TPA未從云服務端獲取f(mi),也不能從已知信息中提取出f(msc),所以不能通過方程組(5)恢復出具體的{ms1,ms2,…,msc},從而保護了用戶隱私。

定理2 所提出的公開審計方案能防止CSS進行替代攻擊。

證明 CSS不能通過已保存的數據塊替代所要求的數據塊,偽造出能通過第三方審計的應答證據。假設文件經過客戶端數據增刪改更新操作請求并執行后的MHT結構如圖5所示,CSS無法重建一棵擁有相同節點數、相同根節點值且滿足任意數據塊組合挑戰的MHT,只得把正確的MHT樹結構發送給TPA。

圖5 更新過的文件MHT示例Fig. 5 Example of modified MHT

表1 云數據完整性審計方案的對比Tab. 1 Comparison of different remote data integrity checking schemes

TPA得到MHT樹結構后,想要通過驗證m3、m4和m6數據塊判斷文件完整性,并得出如圖6的覆蓋樹樹結構T。當收到TPA審計挑戰請求后,CSS必須返回同T結構的覆蓋樹T′。基于SHA不會將不同字符串哈希成相同結果的假設,CSS必須得擁有正確的H(m3)、H(m4)和H(m6)且按正確的順序返回才能讓TPA計算出對應正確的節點h(H(m3))、h(H(m4))和h(H(m6)),且h(c)和h(d)合并計算出的哈希值與h(d)和h(c)合并計算出的哈希值不一樣,避免對稱值替代攻擊。結合T′中伴隨節點h(c)、h(H(m5))和h(e)的正確值,才能從下至上計算出正確的根節點值,使得e(sigR,g)=e(H(R),gα)通過第二步驗證。證明過程如下:

e(sigR,g)=e(H(R)α,g)=e(H(R),gα)

(6)

圖6 安全性分析中覆蓋樹示例Fig. 6 Example of overlay tree in security analysis

基于SHA不會將不同字符串哈希成相同結果的假設,且h(c)和h(d)合并計算出的哈希值與h(d)和h(c)合并計算出的哈希值不一樣,不支持交換,所以保障了H(mi)順序正確,也防止了對稱值替代。

4.2 性能分析

通過分析本文方案與現有幾種具備代表性的云數據完整性審計方案,對比了其特征及性能,其中檢測率表示對于出錯率為θ的文件,抽樣審計c個數據塊,至少一個數據塊被檢測到的概率為1-(1-θ)c。結果如表1所示。

從表1中可知,本文方案在支持公開審計和完全動態數據更新操作的基礎上,更具隱私保護和防止CSS替代攻擊特征,在計算開銷、通信開銷和存儲開銷的性能上,與大多方案具有相同復雜度數量級,即相似的性能。

5 實驗結果分析

本文方案在理論分析的基礎上進行了仿真測試實驗。操作系統為macOS 10.13.1,處理器為2.7 GHz Intel Core i5,8 GB 1 867 MHz DDR3存儲器的環境下利用python語言實現,相關密碼運算基于pythia-pyrelic三方庫[19],采用Barreto Naehrig 曲線[20]和SHA256哈希算法,以80比特安全參數及256比特曲線大素數階為基礎參數,所有測試結果均為18次實驗的平均值。

本文選擇了MHT-PA方案和文獻[15]方案與本文方案做對比實驗,比較了其在相同文件下以1 024字節劃分數據塊,挑戰驗證不同數據塊數目的計算開銷與通信開銷。不同挑戰驗證塊數下三種方案的CSS計算時間和TPA計算時間如圖7所示。從圖7可看出，CSS和TPA的計算時間與驗證的數據塊數目緊密相關,隨著所需驗證的數據塊數目增多,TPA和CSS的計算時間都會相應增加。

圖7 挑戰驗證不同數據塊數目下計算開銷Fig. 7 Computation costs with different verification data blocks

圖8表示同樣大小的文件在驗證不同數據塊數目下的通信開銷,由圖8可知,本文方案相比另外兩種方案增加了一些通信開銷,此即為挑戰前TPA向CSS所請求的一個樹結構。從整體角度看,這個開銷可忽略不計。

圖8 挑戰驗證不同數據塊數目下的通信開銷Fig. 8 Communication costs with different verification data blocks

表2 三種方案挑戰驗證320和460個數據塊下的性能比較Tab. 2 Performance comparison of three schemes for verifying 320 and 460 data blocks

由于文獻[21]已經證明在文件數據塊出錯率為1%的情況下,若要達到99%或95%的驗證準確率,則隨機抽取460個或320個數據塊即可,因此本文詳細分析比較了在驗證320個和460個數據塊下的性能，實驗結果如圖9所示。從圖9中可知,在驗證相同數據塊數目時,本文方案的CSS計算時間略高于另外兩種方案,TPA計算時間幾乎相同,但從整體來看,三種方案計算開銷的差距可忽略不計。

圖9 挑戰驗證320和460個數據塊下的計算開銷Fig. 9 Computation costs for verifying 320 and 460 data blocks

表2綜合展示了MHT-PA方案、文獻[15]方案與本文方案在95%和99%的驗證準確率下，即TPA分別挑戰驗證320個數據塊和460個數據塊，三項性能指標，即TPA計算時間、CSS計算時間和通信開銷的結果對比，表中各項值均為18次實驗的平均值。

綜上所述，在以TPA挑戰驗證的數據塊數目為唯一變量的前提下，以上三種方案的計算開銷和通信開銷都會隨著此變量的增大而增加。在TPA驗證相同數據塊數目下，本文方案的計算開銷和通信開銷相比另外兩種方案有些許增加，其中CSS的計算開銷增加率相對高一點。而當TPA審計需達到的準確率越高時，本文方案的計算開銷增加率和通信開銷增加率將會越低。

6 結語

本文在MHT-PA方案基礎上提出了一個新的面向公有云的數據完整性公開審計方案,利用哈希值混淆方法更改了文件的同態認證標簽，使TPA無法從CSS返回的證據信息中計算得出用戶數據信息，從而解決了用戶隱私泄露給TPA的問題；其次，提出覆蓋樹概念，調整了審計策略，讓TPA在正式審計前先進行基于MHT的覆蓋樹結構匹配,解決了半可信的CSS發起替代審計攻擊的問題,通過理論和實驗分析測試了方案的性能,驗證了該方案的正確性和有效性。