王瑞錦,張鳳荔,王馨云,陳學勤,羅 昊,秦圣智
(電子科技大學信息與軟件工程學院 成都 610054)
隨著計算機技術和互聯(lián)網的不斷發(fā)展,在網絡中傳輸的信息出現(xiàn)了爆炸式的增長,海量的數據量給存儲能力和成本帶來了巨大的壓力[1]。在這種情況下云存儲技術應運而生,云存儲基于云計算,利用分布式計算和集群應用等技術,將大量設備整合起來,為用戶提供數據存儲和訪問功能[2]。云存儲具有成本低廉、不受地理位置限制的資源訪問、易于管理和擴充等優(yōu)點[3],被視為IT企業(yè)的下一代數據存儲模型[4]。
用戶使用云存儲服務將文件提交到云服務提供商(cloud service provider, CSP)進行在線存儲,在減輕本地存儲壓力的同時,也失去了對數據的物理控制能力[5],因此數據的安全問題[6-8]是一個不容忽視的問題。CSP可能是不誠實的[9],會為了自身的利益威脅到用戶的數據安全,例如當CSP的存儲設備容量不足時,CSP可能會選擇刪除一些用戶長時間沒有訪問過的數據或者將這些數據移動到廉價的離線存儲介質中以節(jié)省開支[10],這會造成用戶數據的永久或暫時不可訪問。另外在遭遇拜占庭失敗時CSP可能會為了維護自己的信譽而試圖向用戶隱瞞數據丟失的情況[11]。
目前已經出現(xiàn)了多種針對云存儲環(huán)境的數據完整性驗證方案。一個實用的云存儲完整性驗證算法應該具有較小的網絡開銷,并且沒有驗證次數的限制,另外由于用戶存在對云端的數據進行操作的需求,因此一個實用的完整性驗證方案還要能支持動態(tài)操作。文獻[12]提出了兩種針對云存儲的完整性驗證算法,然而這兩種方法均不能對文件的動態(tài)操作提供支持;文獻[13]提出了一種基于Diffie-Hellman體制的完整性驗證方法,該方法對驗證次數沒有限制,但是不能支持數據塊的插入操作并且計算開銷較大;文獻[10]提出了一種基于merkel hash tree(MHT)的完整性認證方案,在該方案中,CSP為產生一次完整性驗證需要讀取所有的數據塊以得到Merkel哈希樹,當用戶數據較大或數據塊較小時,會使得Merkel哈希樹的深度過深而消耗較多的計算資源,影響CSP的服務質量;文獻[14]提出了一種基于改進的Merkel哈希樹和雙線性對的完整性審計方案,在該方案中按照兩個層級對用戶數據進行劃分,使Merkel哈希樹中的每一個葉子結點對應多個數據塊,從而降低Merkel哈希樹的深度,提高構造效率,同時該方案也能夠支持數據塊的動態(tài)操作。然而在極端情況下,例如用戶不斷在文件的末尾追加數據塊,則會出現(xiàn)文獻[14]中提到的樹不平衡的情況,從而使根結點到某個葉子節(jié)點的路徑過長,效率將會在很大程度上降低。
為了解決文獻[14]中提出的方案在上述情況下的效率問題,本文基于改進的跳表和短簽名技術,提出一種能夠支持動態(tài)操作的完整性驗證協(xié)議。本文對跳表中的結點提出一種新的定義方式,該定義方式可以在邏輯上消除跳表中的環(huán)狀結構,從而降低跳表中結點的依賴關系數量,在生成跳表、更新跳表和進行驗證時降低計算開銷;同時本文在跳表中引入可達范圍計數,使得在發(fā)生數據塊的插入和刪除時,跳表中需要更新的結點數量更少,從而更有效地對動態(tài)操作提供支持。最后對該方案進行了理論分析和實驗驗證,證明該方案是高效的。
針對云存儲的完整性驗證系統(tǒng)通??梢苑譃閮煞侥P秃腿侥P停渲袃煞侥P椭邪脩?Client)和云存儲服務提供商(CSP),三方模型在兩方模型的基礎上引入了一個可信的第三方驗證者(TPA),TPA用于為用戶承擔驗證任務,代替用戶周期性的對存儲在CSP中的數據和文件進行完整性驗證。本文提出的方案基于兩方模型,如圖1所示。
圖中用戶指有著數據在線存儲需求的云存儲服務用戶;云存儲服務器是由云存儲服務提供商管理的一組服務器,具有海量的存儲能力和強大的計算能力,對外提供數據存儲和訪問功能。在本文提出的方案中,用戶在對文件進行訪問時,同時獲取與之對應的輔助認證信息,使用輔助認證信息對正在訪問的文件進行完整性驗證。本文中對文件的分塊處理與文獻[14]類似,即按照固定的塊大小對文件進行劃分,產生認證數據的基本單位是數據塊。
圖1 兩方模型
在本文提出的協(xié)議中,用戶將數據提交到云端進行在線存儲前,首先需要在本地對文件進行一些處理工作,包括文件的塊劃分、摘要生成、跳表生成、簽名等,完成上述步驟后,用戶將文件和輔助認證信息一并提交到云端進行保存,之后用戶便刪除本地的文件副本和輔助驗證信息副本,以減輕本地的存儲壓力。用戶在訪問存儲在云端的文件時,獲取需要訪問的部分以及該部分對應的輔助認證信息,使用輔助認證信息對該部分的文件內容進行驗證,以便確定該部分文件內容是否正確和完整。
跳表(skip lists)是一種能夠快速進行查找、刪除和插入的數據結構,跳表的結構如圖2所示。
圖2 跳表的結構
跳表包含若干層,其中每一層均由鏈表構建,跳表中的每一個結點均包含一個指向右邊結點的指針和一個指向下方結點的指針,跳表中最左邊一列和最右邊一列的結點被稱為哨兵結點。跳表中的底層鏈表有序地存儲所有元素,對于某一層Si和Si的上一層Si+1,出現(xiàn)在Si中的非哨兵結點將以某個概率出現(xiàn)在上一層中,即以一定概率在Si+1層中生成對應結點,并且哨兵結點所在列的層數不小于任何非哨兵結點所在列。
在跳表中進行查找,從左上角的結點開始,用p表示指向當前結點的指針,p只能向右或者向下移動,查找某個結點的算法描述如下:
查找過程結束時,p指向目標結點或者小于目標結點的最大結點。
在跳表中插入一個結點時,例如需要插入的結點編號為x,則首先執(zhí)行查找x的操作,得到一個指向小于x的最大結點的指針,此時再將x結點插入到p所指向的結點的后面,并概率性地產生x結點的上層結點。
執(zhí)行刪除操作時,首先執(zhí)行查找操作找到小于目標結點的最大結點所在位置,之后刪除目標結點以及目標結點所在列的所有結點,該過程與在鏈表中刪除一個結點類似。
標準的哈希函數只有一個輸入參數,可交換哈希函數是一種包含多個輸入參數的哈希函數,并且當輸入參數均保持不變時,任意交換各個參數的輸入順序,函數的輸出是一致的。包含2個輸入參數的可交換哈希函數滿足下述性質:
式中,EH是可交換哈希函數,本文使用的可交換哈希函數包含3個輸入參數。
在云存儲系統(tǒng)中,由于云存儲服務器是半可信的,因此用戶存儲在云端的文件面臨著損壞、篡改甚至被云存儲服務提供商有意刪除等風險,而云存儲服務提供可能會為了維護其自身利益而向用戶隱瞞并且試圖在文件的完整性被破壞后通過某種方法使得用戶不能發(fā)現(xiàn)文件的完整性已經被破壞,所以該系統(tǒng)中可能會出現(xiàn)如下形式的攻擊:
1)偽造數據塊的攻擊。用戶在訪問某個存儲在云服務器中的數據塊時,如果云服務器發(fā)現(xiàn)該數據塊存在丟失、部分丟失或被篡改的情況,云服務器可能會通過某種技術手段偽造一個數據塊提供給用戶,從而使得用戶不能發(fā)現(xiàn)完整性已被破壞。
2)偽造輔助認證信息的攻擊。用戶在訪問某個存儲在云服務器中的數據塊時,如果該數據塊或對應的輔助認證信息存在丟失、部分丟失或者被篡改的情況,云服務器可能會偽造一對對應的數據塊和輔助認證信息提供給用戶,從而使得用戶不能發(fā)現(xiàn)完整性已被破壞。
本文對跳表的改進主要有3點:
定義 1定義跳表中的子結點。對于跳表中的結點i,定義其左邊的結點j和下面的結點k為結點i的子結點,如果結點j是所在列的頂層結點,則稱j是i的實子結點,否則稱j是i的虛子結點。
定義 2跳表中的底層非哨兵結點存儲2個哈希值,分別稱為contentHash和nodeHash。跳表中的其他結點只存儲nodeHash,其中contentHash直接通過使用哈希函數對數據塊計算摘要得到。
定義 3跳表中的結點不再存儲對應的數據塊的索引,而是存儲以該結點為祖先結點的底層結點數量。
根據定義1可知本文所使用的跳表的根結點為右邊哨兵結點的頂層結點,該跳表的結構如圖3所示,其中虛線框代表的是虛子結點,虛線箭頭為父結點指向虛子結點的指針,方框內“+”和“-”為哨兵結點。
圖3 改進的跳表結構
在該跳表中,底層結點中的contentHash用于存儲數據塊的摘要值。假設當前結點是i,i的左子結點是j,i的下子結點是k,計算i結點的nodeHash時,根據下面所定義的依賴關系進行。
1)若k==null,即i是底層結點。
①如果i是哨兵結點,并且j是虛子結點:
②如果i是哨兵結點,并且j是實子結點:
③如果i不是哨兵結點,并且j是虛子結點:
④如果i不是哨兵結點,并且j是實子結點:
2)若k!=null,即i是非底層結點。
①如果j是虛子結點:
②如果j是實子結點:
式中,φ是一個特定的字符串。根據上述依賴關系可知,在本文所使用的跳表中,信息的流向所構成的結構為樹狀結構,并且該樹狀結構的根結點為跳表的右上方結點。
根據定義3,本文使用的跳表中不記錄數據塊在文件中的索引,而使用可達范圍計數來確定跳表結點與數據塊的對應關系,因此在某個位置新加入一個結點后,不需要對該結點之后的每一個結點進行修改,只需要修改從新加入結點到根結點這一條路徑上所經過的結點的可達范圍計數,該路徑的平均長度為log(n),因此能夠更高效的對動態(tài)操作提供支持。使用可達范圍計數標識數據塊與結點對應關系的跳表結構如圖4所示。其中橢圓型框圖代表數據塊,其中的數字代表數據塊索引;跳表中各個結點中的數字代表可達范圍計數。對于結點i以及其左子結點j和下子結點k,如果j是虛子結點,則i的計數等于k的計數;如果j是實子結點,則i的計數等于j與k的計數之和。
圖4 使用可達范圍計數的跳表結構
在圖4所示的跳表中進行查找某個數據塊對應的結點時,指針p開始時指向根結點,查找算法如下:if(p.reachableCount<target)
在執(zhí)行查找操作時,可以使用棧來記錄過程中經過的結點路徑,使用該路徑可以得到目標結點對應的輔助認證信息。在該跳表中執(zhí)行數據塊的插入和刪除操作時,首先執(zhí)行查找操作,其余部分與基礎跳表的操作方法類似,在此不再贅述。
假設用戶需要提交到云服務器進行保存的文件是M,M包含n個數據塊,即M={m1,m2,…,mn},基本方案由3個步驟組成。
1)SetUp(1λ)→(H,EH,sk,pk)。用戶選擇隨機數得到用戶私鑰sk=(x,g),其中g是群G的生成元,G是基于橢圓曲線構造的乘法循環(huán)群,G的階數為p。用戶根據私鑰計算公鑰pk=(y,g),其中y=gx,根據雙線性對的性質[15],有等式e(y,g)=e(g,g)x=e(g,y)成立。同時用戶還需要選擇在協(xié)議中使用的哈希函數和可交換哈希函數;
2)GenSL(M,H,EH,sk)→(SL,σ)。用戶對文件M進行分塊處理,得到數據塊集合M={m1,m2,…,mn},并產生跳表SL,SL的底層結點數量為n+2,包含2個哨兵結點和n個非哨兵結點。之后用戶使用哈希函數H計算數據塊集合中每一個元素的摘要指,并將摘要值按順序寫入跳表底層非哨兵結點的contentHash中。最后用戶使用可交換哈希函數EH計算SL中每一個結點的nodeHash值,并使用私鑰sk對根節(jié)點r的nodeHash值進行簽名,得到簽名值σ。完成上述步驟后,用戶將(SL,σ)和文件M提交到云存儲服務器進行在線存儲;
3)Verify(mi,ηi,σ,H,EH,pk)→true/false 。當用戶訪問數據塊集合中的某個數據塊mi時,云存儲服務器一并向用戶返回數據塊mi、輔助驗證信息ηi和根結點的簽名σ。輔助驗證信息是一個集合,包含從mi所對應的跳表結點到根節(jié)點所在路徑上的所需nodeHash,根據跳表的性質,該集合的大小平均為log(n),因此根據2.1節(jié)中定義的依賴關系,可以使用mi和輔助驗證信息ηi計算出根節(jié)點r'。用戶計算出r'后,使用數字簽名σ驗證r'的合法性,如果驗證通過則系統(tǒng)返回true,否則返回false。
在本方案中,動態(tài)操作包括3種類型:數據塊的修改(update)、插入(insert)和刪除(delete)。假設認證結構SL和簽名σ已經生成并提交到云存儲服務器中進行保存,下面介紹動態(tài)操作過程。
1)用戶產生操作消息。用戶執(zhí)行算法GenOPMsg(),下面對不同的操作類型進行描述。
修改操作:假設用戶對索引為x的數據塊進行修改,得到新數據塊m′x,則用戶產生消息(update,x),并將消息發(fā)送至云存儲服務器。
插入操作:假設用戶需要在文件中的x位置新插入一個數據塊mx,則用戶使用特定概率計算新插入數據塊在跳表中對應的結點所在列的層數L,并將消息(insert,x,L)發(fā)送至云存儲服務器。
刪除操作:假設用戶需要刪除文件中的第x個數據塊,則用戶產生消息(delete,x)并發(fā)送至云存儲服務器。
2)更新SL與簽名。云存儲服務器在接收到用戶的動態(tài)操作請求后,根據消息內容返回所需的輔助認證信息,以便用戶對SL進行更新和對新的SL簽名,下面詳細介紹其過程。
修改操作:云存儲服務器返回原數據塊mx所對應的輔助認證信息ηx。用戶接收到ηx后,使用m′x計算摘要值并將其作為第x個跳表結點的contentHash,再根據輔助認證信息ηx計算得到根節(jié)點的nodeHash,并對其簽名。
插入操作:云存儲服務器在SL中的第x個位置新插入一列結點,該列的高度為L。此時新插入結點的contentHash和nodeHash均為空值,然后執(zhí)行查找算法find(x)并得到輔助認證信息ηx,云存儲服務器將ηx返回給用戶,用戶使用mx計算摘要值并將其作為第x個跳表結點的contentHash,再根據輔助認證信息ηx計算得到根節(jié)點的nodeHash,并對其簽名。
刪除操作:云存儲服務器將目標結點x所在列刪除,目標結點后面的結點將占據第x個位置。此時云存儲服務器執(zhí)行算法find(x)得到第x個節(jié)點的輔助認證信息ηx,并將ηx與刪除第x個數據塊后、在文件中的索引變更為x的數據塊mx返回給用戶。用戶根據mx和ηx計算得到SL根結點的nodeHash并對其簽名。
3)提交更改。如果用戶執(zhí)行的是修改操作,則向云存儲服務器提交(m′x,σ′);如果執(zhí)行的是插入操作,則向云存儲服務器提交(mx,σ′);如果執(zhí)行的刪除操作,則向云存儲服務器提交(σ′)。
本協(xié)議的攻擊類型主要有數據塊偽造攻擊和輔助認證信息偽造攻擊兩種,下面分別對其進行簡要的安全性分析。
1)數據塊偽造攻擊。假設在用戶對數據塊mx進行完整性驗證時,云存儲服務器偽造了一個數據塊并且云存儲服務器向用戶返回假設該三元組能夠通過驗證,則等價于云存儲服務器有能力找到m1≠m2,使得Hash(m1)=Hash(m2),但根據哈希函數的單向性和抗碰撞性,這個問題是一個困難問題,因此上述三元組不能以不可忽略的概率通過用戶的驗證,本協(xié)議能夠抵抗數據塊偽造攻擊。
2)輔助認證信息偽造攻擊。假設云存儲能夠用不合法的數據塊m′x代替合法數據塊mx計算出非法的SL根節(jié)點nodeHash并對其簽名,并且該非法簽名和非法的SL根結點nodeHash能夠通過用戶的公鑰驗證,則等價于云存儲服務器能夠在沒有私鑰的情況下產生合法簽名,根據數字簽名的定義,可知該問題是一個困難問題,因此云存儲服務器無法以不可忽略的概率產生合法簽名,本協(xié)議能夠抵抗輔助認證信息偽造攻擊。
將本文算法與另外3種針對云存儲環(huán)境的數據完整性驗證方案進行性能對比,之后將本文的方案與文獻[14]的方案進行模擬分析實驗。本文所提出的協(xié)議與文獻[14]中所提出的方案在初始化階段均需生成輔助認證信息,而產生輔助認證信息的時間復雜度均為O(n),且產生的認證結構中所包含的節(jié)點數量的期望值均為文件塊數量的2倍,因此該部分不做性能測試。
設n代表用戶需要存儲在云服務器中的文件包含的數據塊數量,本文與PDP方案、文獻[10]和文獻[14]方案的性能分析對比結果如表1所示。
表1 性能分析比較
為支持動態(tài)操作,需要使用能夠支持動態(tài)操作的認證性數據結構,本文方案使用的是前面介紹的跳表。在驗證時,從根結點到目標結點的平均路徑長度是logn,因此驗證時的計算復雜度是O(logn),如表1所示。
下面將本文的方案與文獻[14]中的方案進行模擬對比實驗。實現(xiàn)環(huán)境的配置為:主頻為3.2 GHz的雙核CPU臺式計算機,8 GB內存,64位Windows 7操作系統(tǒng),編碼所用的開發(fā)語言為Java,使用的密碼學工具庫為jPBC v2.0.0。
對于日志文件,在文件的尾部追加內容是一種常態(tài)操作。本文測試的場景為連續(xù)向文件尾部追加數據塊,測試開始前用大小為1 GB的文件產生認證結構,文件塊的大小設置為8 KB,通過在文件的尾部追加不同數量的文件塊以造成認證結構出現(xiàn)不同程度的不平衡。測量在不同程度的不平衡狀態(tài)下,為每一個追加的文件塊進行結構調整所消耗的平均時間,測試結果如圖5所示。
從理論分析而言,本文所提出的協(xié)議在執(zhí)行尾部追加操作時,為每一個追加的文件塊進行結構調整的平均時間復雜度為O(logn)。從上述測試結果可知,在向文件尾部進行連續(xù)追加文件塊的場景中,本文提出的協(xié)議性能優(yōu)于文獻[14]中的方案。
測試向文件中隨機插入文件塊,測試前先用1 GB大小的文件產生認證結構,文件塊的大小設置為8 KB,測試在文件中隨機插入不同數量的文件塊后,平均插入每一個文件塊時,調整認證結構所消耗的時間,測試結果如圖6所示。測試結果顯示本文方案與文獻[14]中的方案性能相近。
圖5 連續(xù)在末尾追加數據塊
圖6 在隨機位置插入數據塊
圖7 對尾部數據塊進行完整性驗證
測試不平衡狀態(tài)下驗證的時間消耗,首先在云端存儲大小為1 GB的文件塊和對應的認證結構,文件塊的大小設置為8 KB,通過在原始文件尾部追加不同數量的文件塊以造成認證結構出現(xiàn)不同程度的不平衡后,對最后一個文件塊進行完整性驗證以觀察在不同程度的不平衡下,驗證所需要的時間,測試結果如圖7所示。從測試結果可知,在不平衡狀態(tài)下,本文所提出的方案在驗證時的性能優(yōu)于文獻[14]中的方案。
云存儲中的數據安全問題是不可回避的問題,而數據的完整性驗證是保護數據安全的重要手段之一,因此面向云存儲和量子存儲的完整性驗證方法和協(xié)議成為了近幾年的研究熱點之一[15-16]。本文基于改進的跳表提出一種適用于兩方模型的云存儲數據完整性驗證協(xié)議,理論分析和模擬實驗證明該協(xié)議具有較高的效率,但該方案沒有考慮驗證任務的代理問題,今后的工作將是對驗證任務的代理問題進行研究。
[1]耿紀昭. 云存儲中數據完整性驗證機制的研究與實現(xiàn)[D].成都: 電子科技大學, 2013.GENG Ji-zhao. Research and implementation of data integrity verification mechanism cloud storag[D]. Chengdu:University of electronic science and technology of china,2013.
[2]蘇蘭. 面向云計算的數據完整性檢驗方法研究與實現(xiàn)[D].成都: 電子科技大學, 2013.SU Lan. Research and implementation of data integrity verification method for cloud computing[D]. Chengdu:University of electronic science and technology of china,2013.
[3]鄧曉鵬, 馬自堂, 高敏霞. 一種基于雙線性對的云數據完整性驗證算法[J]. 計算機應用研究, 2013, 30(7):2124-2127.DENG Xiao-peng, MA Zi-tang, GAO Min-xia. Integrety verifying algorithm for cloud data based on bilinear pairings[J]. Application research of computers, 2013, 30(7):2124-2127.
[4]WANG Cong, WANG Qian, REN Kui. Ensuring data storage security in Cloud Computing[C]//17th International Workshop on Charleston: Quality of Service (IWQoS).Charleston: IEEE, 2009.
[5]WANG Cong, WANG Qian, REN Kui. Privacy-preserving public auditing for data storage security in cloud computing[C]//2010 Proceedings IEEE INFOCOM. San Diego: IEEE,2010.
[6]傅穎勛, 羅圣美, 舒繼武. 安全云存儲系統(tǒng)與關鍵技術綜述[J]. 計算機研究與發(fā)展, 2013, 50(1): 136-145.FU Ying-xun, LUO Sheng-mei, SHU Ji-wu. Survey of cloud storage system and key technologies[J]. Journal of Computer Research and Development, 2013, 50(1): 136-145.
[7]李暉, 孫文海, 李鳳華. 公共云存儲服務數據安全及隱私保護技術綜述[J]. 計算機研究與發(fā)展, 2014, 51(7): 1397-1409.Li Hui, Shun Wen-hai, Li Feng-hua. Secure and privacy preserving data storage service in public cloud[J]. Journal of Computer Research and Development, 2014, 51(7): 1397-1409.
[8]BEHL A, BEHL K. An analysis of cloud computing security issues[C]//2012 World Congress on Trivandrum:Information and Communication Technologies (WICT).Trivandrum: IEEE, 2012.
[9]YANG Kan, JIA Xiao-hua. An efficient and secure dynamic auditing protocol for data storage in cloud computing[J].IEEE Transactions on Parallel and Distributed Systems,2013, 24(9): 1717-1726.
[10]WANG Cong, WANG Qian, REN Kui. Enabling public auditability and data dynamics for storage security in cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(5): 847-859.
[11]ATENIESE G, BURNS R, CURTMOLA R, et al. Provable data possession at untrusted stores[C]//ACM CCS’07.Alexandria: ACM, 2007.
[12]DESWARTE Y, QUISQUATER J J, SAIDANE A. Remote integrity checking[C]//Proc of Conference on Integrity and Internal Control in information Systems(IICIS’03). Boston:Springer, 2003.
[13]SEBE F, MARTNEZ-BALLESTE A, DESWARTE Y.Efficient remote data possession checking in critical information infrastructures[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(8): 1034-1038.
[14]秦志光, 王士雨, 趙洋. 云存儲服務的動態(tài)數據完整性審計方案[J]. 計算機研究與發(fā)展, 2015, 52(10):2192-2199.QIN Zhi-guang, WANG Shi-yu, ZHAO Yang. An auditing protocol for data storage in cloud computing with data dynamics[J]. Journal of Computer Research and Ddevelopment, 2015, 52(10): 2192-2199.
[15]LI Dong-fen, WANG Rui-jin, ZHANG Feng-li, et al. A noise immunity controlled quantum teleportation protocol[J]. Quantum Information Processing, 2016, 15(11): 4819-4837.
[16]LI Dong-fen, WANG Rui-jin, ZHANG Feng-Li, et al.Quantum information splitting of arbitrary two-qubit state by using four-qubit cluster state and Bell-state[J]. Quantum Information Processing, 2015, 14(3): 1103-1116.