一種高效的基于分治鄰接表的動態(tài)完整性審計方案*

符慶曉, 陳蘭香, 李繼國, 姚志強(qiáng)

福建師范大學(xué) 計算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院 福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室, 福州350117

1 引言

隨著云計算與云存儲的廣泛應(yīng)用, 越來越多的單位及企業(yè)選擇將其數(shù)據(jù)外包至云服務(wù)器. 源于云計算的規(guī)模經(jīng)濟(jì)效應(yīng), 可以為用戶提供更加專業(yè)的數(shù)據(jù)存儲與管理服務(wù), 同時極大地節(jié)約經(jīng)濟(jì)成本與社會能源.當(dāng)用戶將數(shù)據(jù)存儲到遠(yuǎn)程服務(wù)器, 便失去了對數(shù)據(jù)的物理控制權(quán), 而云服務(wù)器往往并不完全可信. 數(shù)據(jù)外包特性及頻繁爆發(fā)的數(shù)據(jù)安全事件, 使得用戶對云存儲服務(wù)的信心不足[1]. 因此需要一種數(shù)據(jù)完整性審計技術(shù), 讓用戶可以隨時隨地驗證其數(shù)據(jù)是否完整與可用. 由于數(shù)據(jù)擁有者無法存儲外包數(shù)據(jù)的本地副本,所以傳統(tǒng)的完整性驗證在云計算中并不適用[2]. 為了解決云計算中外包數(shù)據(jù)的完整性審計問題, 研究者提出了遠(yuǎn)程數(shù)據(jù)完整性審計技術(shù)[3,4], 但現(xiàn)有的數(shù)據(jù)完整性驗證方法需要頻繁地進(jìn)行審計和傳輸, 這樣給審計者造成很大的計算和通信開銷. 在支持外包數(shù)據(jù)動態(tài)更新方面, 現(xiàn)有的遠(yuǎn)程數(shù)據(jù)完整性審計方法采用不同的數(shù)據(jù)結(jié)構(gòu)以支持?jǐn)?shù)據(jù)動態(tài)更新, 比如二叉樹、動態(tài)Hash 表等, 來證明外包數(shù)據(jù)的完整性, 但對于大文件中的少量數(shù)據(jù)塊更新, 基于這些數(shù)據(jù)結(jié)構(gòu)的驗證算法需要重新平衡大量數(shù)據(jù)塊, 會帶來較大的計算開銷[5]. 因此, 針對一些需要頻繁更新的數(shù)據(jù), 需要設(shè)計專門的數(shù)據(jù)完整性審計方法.

近年來, 針對云存儲環(huán)境下的數(shù)據(jù)完整性審計已經(jīng)取得了豐碩的研究成果, 也有大量針對數(shù)據(jù)動態(tài)性的研究方案, 但仍然存在諸如安全與效率的平衡、數(shù)據(jù)的隱私保護(hù)以及實用性等幾方面的問題, 下面本文將介紹相關(guān)的研究工作.

2 相關(guān)工作

2007 年, Ateniese 等[6]最早提出可證明數(shù)據(jù)持有(provable data possession, PDP) 方案, 該方案使用同態(tài)標(biāo)簽來驗證外包數(shù)據(jù)完整性. 隨著云計算與云存儲技術(shù)的廣泛應(yīng)用, 驗證外包數(shù)據(jù)完整性得到研究者的廣泛關(guān)注并取得了一系列的研究成果. 鑒于用戶將數(shù)據(jù)存儲到遠(yuǎn)程云存儲服務(wù)器后, 通常有數(shù)據(jù)更新的需求, 因此, 研究者們提出了支持?jǐn)?shù)據(jù)動態(tài)更新的完整性審計方案.

為了支持外包數(shù)據(jù)動態(tài)更新, 2008 年, Ateniese 等[7]提出了外包數(shù)據(jù)動態(tài)審計方案, 該方案在數(shù)據(jù)更新時, 讓數(shù)據(jù)擁有者重新計算塊標(biāo)簽, 因此會造成較大的計算開銷. 2009 年, Erway 等[8]首次提出基于跳表的動態(tài)外包數(shù)據(jù)審計方案, 但是該方案不支持單個數(shù)據(jù)塊的完整性驗證, 而且數(shù)據(jù)塊對應(yīng)的驗證路徑較長. 2011 年, Wang 等[9]提出基于雙線性聚合簽名與Merkle 哈希樹的動態(tài)審計方案, 該方案實現(xiàn)隱私保護(hù)公共審計和多用戶環(huán)境下的批量驗證. 然而, 該方案會造成外包數(shù)據(jù)審計時的數(shù)據(jù)泄露, 而對于云存儲中大型外包數(shù)據(jù)文件也會帶來較高的計算開銷. 2015 年, 文獻(xiàn)[10] 提出基于雙線性對與Merkle 哈希樹的云存儲動態(tài)數(shù)據(jù)完整性審計方案, 該方案通過將數(shù)據(jù)塊分割成長度更小的數(shù)據(jù)塊, 使得Merkle 哈希樹的每個葉子節(jié)點對應(yīng)多個數(shù)據(jù)塊, 從而有效降低Merkle 哈希樹的高度, 但是該方案在數(shù)據(jù)初始化階段的計算開銷較大.

為了減少審計過程中的計算開銷, 文獻(xiàn)[11] 提出基于代數(shù)簽名(algebraic signature) 的數(shù)據(jù)完整性驗證方案, 可以顯著降低外包數(shù)據(jù)審計過程中數(shù)據(jù)擁有者和云服務(wù)器的計算開銷. 然而該方案無法支持外包數(shù)據(jù)的動態(tài)更新. 為支持動態(tài)數(shù)據(jù)更新,文獻(xiàn)[12]提出基于Merkle 哈希樹的云存儲數(shù)據(jù)審計方案,但是因為Merkle 哈希樹在數(shù)據(jù)更新時需要重新平衡二叉樹, 造成較大的計算開銷. 而且該方案在審計過程中, 數(shù)據(jù)擁有者需要對云存儲中的外包數(shù)據(jù)進(jìn)行完整性驗證, 而不是授權(quán)給第三方審計者(third party auditor,TPA), 從而在外包數(shù)據(jù)審計過程中, 極大地增加了數(shù)據(jù)擁有者和云存儲服務(wù)器的計算開銷.

2014 年, 文獻(xiàn)[13] 提出一個基于代數(shù)簽名的云存儲動態(tài)數(shù)據(jù)審計方案, 該方案引入了第三方審計者TPA, 減輕了審計過程中數(shù)據(jù)擁有者的計算開銷, 并且提出索引表數(shù)據(jù)結(jié)構(gòu)以支持?jǐn)?shù)據(jù)動態(tài)更新, 但是該方案在數(shù)據(jù)更新時的效率比較低. 不久, 文獻(xiàn)[14] 提出一個結(jié)合代數(shù)簽名和分治表的動態(tài)數(shù)據(jù)審計方案,該方案使用代數(shù)簽名對外包數(shù)據(jù)進(jìn)行完整性審計, 同時提出分治表數(shù)據(jù)結(jié)構(gòu)來支持?jǐn)?shù)據(jù)的動態(tài)更新, 使得動態(tài)數(shù)據(jù)更新計算開銷得到顯著降低. 然而該方案使云存儲服務(wù)器在不訪問外包數(shù)據(jù)的情況下可以生成有效的證明, 從而容易造成審計過程中的數(shù)據(jù)隱私泄露并且容易受到重放攻擊. 2018 年, 文獻(xiàn)[15] 也提出一個結(jié)合代數(shù)簽名和分治表的動態(tài)數(shù)據(jù)審計方案, 與文獻(xiàn)[14] 不同的是, 該方案首先對數(shù)據(jù)塊的索引號加密, 然后再生成塊的校驗值和塊標(biāo)記, 這樣可以有效抵抗審計過程中的重放攻擊和數(shù)據(jù)泄露問題. 然而該方案在審計過程中的初始化階段會給數(shù)據(jù)擁有者造成過大的計算開銷. 因此, 文獻(xiàn)[16] 提出一個基于代數(shù)簽名的數(shù)據(jù)完整性驗證方案, 為了減少數(shù)據(jù)審計過程中數(shù)據(jù)擁有者的計算開銷, 該方案引入第三方審計者, 將外包數(shù)據(jù)完整性審計授權(quán)給第三方審計者. 為了保護(hù)外包數(shù)據(jù)并防止審計過程中的數(shù)據(jù)隱私泄露問題, 他們還提出了異或同態(tài)函數(shù)(XOR-homomorphic function) , 可以一定程度上保護(hù)外包數(shù)據(jù)審計時所造成的隱私泄露問題. 最近, 韓靜等[17]提出一種輕量級的支持用戶可動態(tài)撤銷及存儲數(shù)據(jù)可動態(tài)更新的云審計方案, 利用多重單向代理重簽名技術(shù)實現(xiàn)動態(tài)撤銷, 引入虛擬索引實現(xiàn)實時動態(tài)更新. 文獻(xiàn)[18] 利用Fisher-Yates Shuffles 算法構(gòu)造異或同態(tài)函數(shù), 使得算法的時間開銷比較大, 時間復(fù)雜度為O(n2). 在支持外包數(shù)據(jù)更新方面, 他們設(shè)計了記錄表(record table, RTable)數(shù)據(jù)結(jié)構(gòu)以支持外包數(shù)據(jù)動態(tài)更新, 但刪除或者插入數(shù)據(jù)塊(i), 必須移動(n ?1) 個數(shù)據(jù)塊, 因此造成嚴(yán)重的計算負(fù)載.

為了解決數(shù)據(jù)動態(tài)更新過程中計算開銷太大的問題, 本文設(shè)計一種新的分治鄰接表(divide and conquer adjacency table, D&CAT) 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)高效的動態(tài)更新操作. 數(shù)據(jù)的基本審計方案基于代數(shù)簽名, 為了保護(hù)審計過程中的數(shù)據(jù)隱私, 使用Knuth-Durstenfeld Shuffle 算法構(gòu)造異或同態(tài)函數(shù), 相比算法Fisher-Yates Shuffles 的O(n2), 根據(jù)文獻(xiàn)[19] 洗牌算法證明, 該算法的時間復(fù)雜度O(n), 從而可以相應(yīng)減少異或同態(tài)函數(shù)的時間開銷. 分治鄰接表結(jié)構(gòu)在外包數(shù)據(jù)更新操作時, 當(dāng)刪除或者插入數(shù)據(jù)塊(i)時, 只需要修改對應(yīng)數(shù)據(jù)塊的鏈表指針, 從而可以有效提高外包數(shù)據(jù)更新操作的效率.

下文結(jié)構(gòu)組織如下: 第3 節(jié)介紹相關(guān)預(yù)備知識, 包括系統(tǒng)模型、代數(shù)簽名與異或同態(tài)函數(shù); 第4 節(jié)詳細(xì)介紹本文提出的完整性審計方案; 第5 節(jié)對本方案的安全性與性能進(jìn)行分析; 第6 節(jié)總結(jié)全文并指出下一步的研究工作.

3 預(yù)備知識

本節(jié)介紹系統(tǒng)模型、代數(shù)簽名和異或同態(tài)函數(shù)的相關(guān)知識.

3.1 系統(tǒng)模型

本文提出方案的系統(tǒng)模型包括3 個實體: 數(shù)據(jù)擁有者, 云存儲服務(wù)器, 第三方審計者. 其系統(tǒng)模型如圖1 所示.

圖1 外包數(shù)據(jù)審計流程Figure 1 System model

(1) 數(shù)據(jù)擁有者(data owner, DO): 指將數(shù)據(jù)存儲在云存儲服務(wù)器中的企業(yè)或個人, 他們擁有修改、插入、刪除權(quán)限來更新外包數(shù)據(jù).

(2) 云存儲服務(wù)提供者(cloud storage provider, CSP): 負(fù)責(zé)存儲數(shù)據(jù)擁有者的數(shù)據(jù)并生成驗證證據(jù)作為對用戶挑戰(zhàn)的響應(yīng).

(3) 第三方審計者(third party auditor, TPA): 審計外包數(shù)據(jù)并進(jìn)行完整性驗證.

3.2 代數(shù)簽名

代數(shù)簽名(algebraic signature) 是一種具有同態(tài)性的哈希函數(shù), 用于為文件塊生成同態(tài)標(biāo)簽. 代數(shù)簽名的代數(shù)性質(zhì)是指數(shù)據(jù)塊的代數(shù)簽名之和與相應(yīng)數(shù)據(jù)塊之和的代數(shù)簽名相同. 由n個數(shù)據(jù)塊(F[1],F[2],··· ,F[n]) 組成的文件F的代數(shù)簽名計算如下:

其中,γ為有限域的本原元素, 代數(shù)簽名有以下3 個性質(zhì):

性質(zhì)1: 長度為r的數(shù)據(jù)塊F[I] 和F[j] 相連接的代數(shù)簽名計算公式為

性質(zhì)2: 文件F的所有數(shù)據(jù)塊之和的代數(shù)簽名與每個數(shù)據(jù)塊代數(shù)簽名之和相等:

性質(zhì)3: 文件F與文件G之和的代數(shù)簽名與各個代數(shù)簽名之和相等:

3.3 異或同態(tài)函數(shù)

異或同態(tài)函數(shù)(XOR-homomorphic function) 是指具有異或同態(tài)特性的偽隨機(jī)函數(shù), 它可以增強(qiáng)對數(shù)據(jù)的隱私保護(hù). 異或同態(tài)函數(shù)f有以下相應(yīng)的性質(zhì):

性質(zhì)4: 對輸入x1,x2的異或運算等于函數(shù)f對每個輸入的異或運算:

性質(zhì)5: 對于置換密鑰(k1,k2), 則:

3.4 威脅模型

當(dāng)DO 將數(shù)據(jù)外包到云存儲中, 并將數(shù)據(jù)委托給CSP 時, 數(shù)據(jù)的完整性可能面臨以下風(fēng)險:

(1) 由于硬件或管理錯誤, 以及各種內(nèi)部或外部攻擊, CSP 有可能隱藏外包數(shù)據(jù)丟失或受損情況.

(2) 為了節(jié)省資源, CSP 可能會忽略執(zhí)行數(shù)據(jù)所有者要求的數(shù)據(jù)更新操作. 例如, 在挑戰(zhàn)驗證階段, 不誠實的CSP 可能利用以前的合法響應(yīng)或其他信息生成證明, 而不需要檢索實際外包數(shù)據(jù), 以欺騙TPA 通過驗證(重放攻擊) .

針對以上問題, 本文提出一種通過驗證外包數(shù)據(jù)的完整性來檢測CSP 不當(dāng)行為的方法.

4 方案詳細(xì)設(shè)計

本節(jié)首先對方案的幾個算法進(jìn)行形式化描述, 然后對每個算法進(jìn)行詳細(xì)介紹.

4.1 算法形式化描述

本文提出的動態(tài)數(shù)據(jù)完整性審計方案包括兩個部分: 基本的完整性審計方案與動態(tài)數(shù)據(jù)更新方案. 基本的完整性審計方案分為4 個階段: 初始化階段、挑戰(zhàn)階段、回應(yīng)階段與驗證階段, 包括5 個多項式時間算法; 動態(tài)數(shù)據(jù)更新方案包括4 個多項式時間算法. 算法的形式化定義如下.

? Setup (1λ)→(params,sk) : DO 使用Setup 算法以安全參數(shù)λ為輸入, 隨機(jī)輸出公共參數(shù)params 和密鑰sk.

? TagGen(params,sk,F)→(T) : DO 使用TagGen 算法, 以公共參數(shù)params、密鑰sk、文件F為輸入, 輸出每個數(shù)據(jù)塊的標(biāo)簽Ti.

? Challenge (c)→(chal) : TPA 使用Challenge 算法隨機(jī)輸出挑戰(zhàn)消息chal.

? Response(params,F,Ti,chal)→(proof): CSP 使用Response 算法, 以公共參數(shù)params、外包文件F、挑戰(zhàn)消息chal 以及對應(yīng)挑戰(zhàn)塊的標(biāo)簽為輸入, 輸出回應(yīng)消息proof.

? Verify(params,sk,chal,proof)→(1,0): TPA 使用Verify 算法, 以公共參params、密鑰sk 和回應(yīng)消息proof 作為輸入, 輸出結(jié)果1 或0.

動態(tài)數(shù)據(jù)更新方案的4 個多項式時間算法的形式化定義如下.

4.2 算法詳細(xì)設(shè)計

上節(jié)對本方案的算法進(jìn)行了形式化描述, 下面將對以上算法的詳細(xì)過程進(jìn)行描述.4.2.1 基本的完整性審計

基本的完整性審計方案分為4 個階段: 初始化階段、挑戰(zhàn)階段、回應(yīng)階段與驗證階段, 包括5 個多項式時間算法, 分別詳述如下, 其流程如圖2 所示.

圖2 外包數(shù)據(jù)審計流程Figure 2 Audit processs

(1) 初始化算法Setup(1λ)→(params,sk) 的執(zhí)行過程如下.

(1.1) 數(shù)據(jù)擁有者DO 首先通過數(shù)據(jù)分片技術(shù)將文件F分為n個數(shù)據(jù)塊F[1],F[2],··· ,F[n].

云存儲服務(wù)器CSP 接收到TPA 的挑戰(zhàn)消息chal 后執(zhí)行以下計算:

(5) 驗證算法Verify(params,sk,chal,Proof)→(1,0) 的執(zhí)行過程如下.

當(dāng)TPA 接收到CSP 發(fā)送的Proof 消息時, TPA 首先計算TCi=fskt(τi ⊕vi), 然后計算ωi=μi ⊕TCi, 此后TPA 可以通過以下等式驗證外包數(shù)據(jù)塊的完整性:

其正確性證明如下:

4.2.2 基于分治鄰接表的動態(tài)數(shù)據(jù)更新

動態(tài)數(shù)據(jù)更新是數(shù)據(jù)完整性審計中的一個非常重要的特征, 實現(xiàn)不用下載數(shù)據(jù)情況下的外包數(shù)據(jù)的更新. 盡管文獻(xiàn)[16] 提出的RTable 數(shù)據(jù)結(jié)構(gòu)可以支持動態(tài)數(shù)據(jù)更新. 但插入一個數(shù)據(jù)塊需要完成(n ?1)次數(shù)據(jù)塊移動. 為了更好地支持動態(tài)數(shù)據(jù)更新, 本文提出分治鄰接表數(shù)據(jù)結(jié)構(gòu), 在刪除或者插入數(shù)據(jù)塊(i) 時, 只需要修改對應(yīng)數(shù)據(jù)塊的鏈表指針, 不需要移動之后的數(shù)據(jù)塊, 同時, 根據(jù)表頭結(jié)點的LMIN 與LMAX 可以快速定位結(jié)點, 從而可以較好地提高外包數(shù)據(jù)更新操作的效率.

分治鄰接表主要由兩個數(shù)據(jù)結(jié)構(gòu)組成: 表頭數(shù)組與鏈表. 表頭數(shù)組的每個結(jié)點由四個部分構(gòu)成:LMIN 表示對應(yīng)鏈表最小的數(shù)據(jù)塊的索引號, LMAX 表示為對應(yīng)鏈表最大的數(shù)據(jù)塊的索引號, FIRST表示對應(yīng)鏈表的頭指針, REAR 表示對應(yīng)鏈表最后一個結(jié)點指針. 鏈表則由三個部分構(gòu)成: LN 表示數(shù)據(jù)塊的索引號, TIME 表示數(shù)據(jù)塊最后更新的時間, NEXT 表示下一個結(jié)點的指針. 同時為了表述方便, 使用MAX 表示文件最大的邏輯索引號.

數(shù)據(jù)擁有者DO 在上傳外包數(shù)據(jù)到CSP 之前, 為每個文件生成對應(yīng)的D&CAT 數(shù)據(jù)結(jié)構(gòu). 為了實現(xiàn)數(shù)據(jù)的動態(tài)更新, 我們設(shè)計了數(shù)據(jù)修改Modify、數(shù)據(jù)插入Insert、數(shù)據(jù)附加Add 與數(shù)據(jù)刪除Delete 等4個數(shù)據(jù)更新算法.

假設(shè)DO 需要修數(shù)據(jù)塊F[2], 則修改前的分治鄰接表如圖3 所示.

圖3 數(shù)據(jù)修改前的分治鄰接表Figure 3 D&CAT before modification

當(dāng)修改完成后, 分治鄰接表如圖4 所示.

圖4 數(shù)據(jù)修改后的分治鄰接表Figure 4 D&CAT after modification

假設(shè)DO 需要在數(shù)據(jù)塊F[2] 后插入一個新的數(shù)據(jù)塊, 設(shè)新數(shù)據(jù)塊插入前的分治鄰接表如圖4 所示. 而當(dāng)新數(shù)據(jù)塊插入完成后, 其分治鄰接表如圖5 所示.

圖5 插入數(shù)據(jù)塊后的分治鄰接表Figure 5 D&CAT after inserting

(3) 數(shù)據(jù)附加算法Add(F[n+1])→(Tn+1,DCn+1,Noden+1) 的執(zhí)行過程如下.假設(shè)DO 需要將新的數(shù)據(jù)塊F[n+1] 附加到文件F后面, 則DO 將會執(zhí)行以下操作:

(3.1) 找到表頭結(jié)點的最后一個結(jié)點.

(3.2) 創(chuàng)建一個新的鏈表結(jié)點Noden+1, 即LN=MAX,TIME=TIMEn+1, 其中TIMEn+1為當(dāng)前時間, NEXT=∧.

(3.3) 修改表頭結(jié)點的LMAX = LMAX+1, 將對應(yīng)鏈表最后一個結(jié)點域NEXTrear指向新創(chuàng)建的鏈表結(jié)點, 然后將REAR 指向新建的結(jié)點Noden+1.

(3.4) 計算Cn+1=fsko⊕skc⊕skt(F[n+1]⊕rn+1) 和DCn+1=fsko(τn+1⊕rn+1), 其中τn+1=FID‖LN‖TIME, 然后計算Tn+1=Sγ(Cn+1‖τn+1‖rn+1).

(3.5) DO 將{F[n+1],Tn+1,DCn+1}發(fā)送給CSP.

假設(shè)DO 在文件F附加一個新的數(shù)據(jù)塊, 設(shè)新數(shù)據(jù)塊附加前的分治鄰接表如圖5 所示. 而新數(shù)據(jù)塊附加完成后, 其分治鄰接表如圖6 所示.

圖6 附加新數(shù)據(jù)塊后的分治鄰接表Figure 6 D&CAT after adding

(4) 數(shù)據(jù)刪除算法Delete(i)→(1,0) 的執(zhí)行過程如下.

假設(shè)DO 需要將數(shù)據(jù)塊F[i] 刪除, 則DO 將會執(zhí)行以下操作:

(4.1) 根據(jù)F[i] 查找表頭數(shù)組, 若滿足LMIN

(4.2) 若第i個數(shù)據(jù)塊對應(yīng)結(jié)點為鏈表第一個結(jié)點, 則將表頭結(jié)點域FIRST = NEXTi. 若第i個數(shù)據(jù)塊對應(yīng)結(jié)點為鏈表最后結(jié)點, 則直接將表頭結(jié)點域REAR 指向第i ?1 個結(jié)點. 若第i個數(shù)據(jù)塊既不是鏈表對應(yīng)第一個結(jié)點和最后結(jié)點, 則將第i ?1 對應(yīng)的結(jié)點中NEXTi?1=NEXTi, 相應(yīng)表頭結(jié)點LMAX 以及隨后表頭結(jié)點中LMIN 和LMAX 均減1.

(4.3) CSP 刪除對應(yīng)數(shù)據(jù)塊, 刪除完成后, CSP 返回1, 否則返回0.

假設(shè)DO 需要刪除數(shù)據(jù)塊F[2], 設(shè)刪除數(shù)據(jù)塊前的分治鄰接表如圖6 所示. 在刪除數(shù)據(jù)塊完成后,其鄰接表如圖7 所示.

圖7 刪除數(shù)據(jù)塊后的分治鄰接表Figure 7 D&CAT after deleting

5 安全性與性能分析

本節(jié)對方案的安全性與性能進(jìn)行分析.

5.1 安全性分析

本方案的核心是對存儲在云服務(wù)器上的數(shù)據(jù)執(zhí)行完整性審計, 而且由可信第三方審計者TPA 代替數(shù)據(jù)擁有者進(jìn)行不定期審計. 關(guān)于數(shù)據(jù)的機(jī)密性與訪問控制不在本文的討論范圍, 而且在實際系統(tǒng)中, 數(shù)據(jù)可以加密存儲, 本方案仍然適用于作加密數(shù)據(jù)的完整性驗證. 在系統(tǒng)模型三方之間的相互認(rèn)證可以使用已有的認(rèn)證機(jī)制, 相互的通信可以使用保密信道, 比如SSL/TLS.

這里的安全性分析主要考慮的是數(shù)據(jù)完整性審計方案及動態(tài)更新過程中的安全問題, 包括代數(shù)簽名的魯棒性與異或同態(tài)函數(shù)的安全性, 本方案中代數(shù)簽名可取足夠長的簽名長度, 碰撞概率是非常低的, 甚至可以忽略不計. 一個128 bits 的簽名可能發(fā)生的碰撞概率為2?128, 一個256 bits 的代數(shù)簽名可能發(fā)生的碰撞概率則為2?256, 同時代數(shù)簽名的計算效率非常高. 在保護(hù)數(shù)據(jù)隱私泄露方面, 方案使用Knuth-Durstenfeld Shuffle 算法構(gòu)造異或同態(tài)函數(shù)生成隨機(jī)校驗值, 使得TPA 將無法在審計外包數(shù)據(jù)時獲取任何關(guān)于用戶的信息, 卻可以審計外包數(shù)據(jù)完整性.

同時, 因為本方案支持外包數(shù)據(jù)動態(tài)更新, 所以當(dāng)更新數(shù)據(jù)塊時, 也需要相應(yīng)更新對應(yīng)的數(shù)據(jù)塊的標(biāo)簽. 然而, 不誠實CSP 有可能不響應(yīng)DO 更新外包數(shù)據(jù)請求. 所以CSP 可能利用過期的版本的外包數(shù)據(jù)塊和標(biāo)簽欺騙TPA. 為此, 為了抵抗重放攻擊方面, 假設(shè)DO 請求CSP 更新外包數(shù)據(jù), 如果CSP 忽略外包數(shù)據(jù)更新請求, 并在TPA 審計數(shù)據(jù)時發(fā)送舊的數(shù)據(jù)標(biāo)簽, 這時TPA 可以檢測到CSP 的行為. 這是因為分治鄰接表數(shù)據(jù)結(jié)構(gòu)中的參數(shù)TIME 記錄每個數(shù)據(jù)塊相應(yīng)更新時間, 并嵌入對應(yīng)數(shù)據(jù)塊標(biāo)簽中即是τi=FID‖LN‖TIME,Ti=Sγ(Ci‖τi), 所以重放的標(biāo)簽不能以一個不可忽略的概率通過TPA 的驗證.

本文方案相比于文獻(xiàn)[16], 一方面是使用分治鄰接表數(shù)據(jù)結(jié)構(gòu)替代記錄表數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)更加高效的數(shù)據(jù)更新. 另一方面利用Knuth-Durstenfeld Shuffle 算法[18]構(gòu)造異或同態(tài)函數(shù), 實現(xiàn)時間復(fù)雜度從Fisher-Yates Shuffles 算法的O(n2) 下降至O(n). 關(guān)于本文方案的形式化安全性證明可以參考文獻(xiàn)[16].

5.2 篡改概率分析

本方案的外包數(shù)據(jù)驗證采用隨機(jī)抽樣策略, 外包數(shù)據(jù)篡改檢測的概率是基于數(shù)據(jù)塊抽樣. 即將文件F分為n個數(shù)據(jù)塊, 并隨機(jī)選擇c個數(shù)據(jù)塊作為一個質(zhì)詢檢測, 下面對外包數(shù)據(jù)篡改檢測概率進(jìn)行分析.

所以可得外包數(shù)據(jù)篡改檢測的概率范圍為:

假設(shè)DO 將1 GB 文件劃分為125 000 個數(shù)據(jù)塊, 則每個數(shù)據(jù)塊為8 KB, 然后將數(shù)據(jù)上傳至CSP,若PX= 0.9 以及PX= 0.999 99 的概率檢測到外包數(shù)據(jù)篡改時, 不同數(shù)量的篡改數(shù)據(jù)塊與挑戰(zhàn)數(shù)據(jù)塊的關(guān)系如圖8 所示.

由圖8 可知, 若要TPA 檢測概率達(dá)到PX= 0.9, 當(dāng)CSP 篡改數(shù)據(jù)塊比例為10% 時, 則至少需要挑戰(zhàn)質(zhì)詢的數(shù)據(jù)塊個數(shù)為22 塊; 若要TPA 檢測概率達(dá)到PX=0.95, 且在CSP 篡改數(shù)據(jù)塊比例為10% 條件下, 則需要挑戰(zhàn)質(zhì)詢的數(shù)據(jù)塊個數(shù)為30 塊; 若要TPA 檢測概率達(dá)到PX=0.97 在同樣條件下, 則至少需要挑戰(zhàn)的數(shù)據(jù)塊個數(shù)為35 塊; 若要TPA 檢測概率達(dá)到PX= 0.999 99, 則至少需要質(zhì)詢的數(shù)據(jù)塊個數(shù)為110 塊.

5.3 性能分析

關(guān)于外包數(shù)據(jù)完整性審計方案的存儲開銷與通信開銷, 大部分方案都是相似的, 因此本文主要從計算開銷, 即方案的計算效率方面進(jìn)行分析.

實驗利用一臺配置為Intel Core i5-8250U CPU @ 1.6 GHz CPU 以及8 GB RAM 的PC 機(jī), 采用Eclipse 集成開發(fā)工具并使用Java 語言實現(xiàn)本文方案與文獻(xiàn)[9,16] 方案中的數(shù)據(jù)審計與動態(tài)更新算法.

本方案的性能分析主要包括兩個方面:

(1) 基本審計方案的時間開銷: 包括初始化階段, DO 用于生成文件塊標(biāo)簽的計算開銷; 響應(yīng)階段CSP 生成證據(jù)的計算開銷; 驗證階段, TPA 驗證外包數(shù)據(jù)塊完整性的計算開銷.

(2) 動態(tài)更新方案的時間開銷: DO 對外包數(shù)據(jù)執(zhí)行修改、插入、附加和刪除更新操作所需計算開銷.

為了分析基本審計方案中代數(shù)簽名長度和數(shù)據(jù)塊大小對初始化階段時間開銷的影響, 我們選取5 GB的文件, 分別將外包文件的數(shù)據(jù)塊分為8 KB、16 KB、32 KB、64 KB, 并依次選取代數(shù)簽名長度為64、128、256 及512 bits, 分析實驗中初始化階段的時間開銷, 實驗的結(jié)果取10 次測試結(jié)果的平均值, 其時間開銷如圖9 所示.

圖9 初始化階段時間開銷Figure 9 Time overhead of setup phase

由圖9 可知, 在代數(shù)簽名長度相同的情況下, 隨著數(shù)據(jù)分塊大小的增加, 初始化階段計算開銷減少. 在數(shù)據(jù)塊大小相同情況下, 隨著代數(shù)簽名長度的增加, 初始化階段時間開銷也相應(yīng)減少. 實驗結(jié)果表明, 隨著代數(shù)簽名長度和數(shù)據(jù)分塊增加, 初始化階段的開銷相應(yīng)減少, 其原因是簽名長度長, 分塊粒度大, 減少分塊數(shù)量, 從而減少計算時間.

我們設(shè)定將外包文件的數(shù)據(jù)塊分為8 KB, 挑戰(zhàn)外包數(shù)據(jù)塊數(shù)為5000, 并依次選取代數(shù)簽名長度為依次選取代數(shù)簽名長度為128、256 及512 bits, 分析實驗中回應(yīng)階段和驗證階段的時間開銷, 實驗的結(jié)果取10 次測試結(jié)果的平均值, 時間開銷如圖10 所示.

圖10 回應(yīng)階段和驗證階段時間開銷Figure 10 Time overhead of response and verification phase

由圖10 所示可知, 在數(shù)據(jù)分塊大小為8 KB 情況下, 隨著代數(shù)簽名長度的增加, 回應(yīng)階段時間開銷也相應(yīng)減少. 然而, 即使代數(shù)簽名長度增加, 驗證階段的時間開銷始終大約在25 ms 左右. 實驗結(jié)果表明, 隨著代數(shù)簽名的增加, 響應(yīng)階段的時間開銷降低.

為了測試動態(tài)更新方案的時間開銷, 我們將本文所提方案與文獻(xiàn)[9,16] 提出的方案從數(shù)據(jù)修改、插入、附加與刪除操作進(jìn)行比較. 選取5 GB 的文件, 設(shè)分塊大小為8 KB, 代數(shù)簽名長度為512 bits, 更新數(shù)據(jù)塊數(shù)量從1000 到10 000 遞增, 每次更新數(shù)據(jù)塊隨機(jī)抽取. 數(shù)據(jù)修改操作的實驗結(jié)果如圖11 所示.

圖11 不同數(shù)據(jù)塊數(shù)的修改時間開銷Figure 11 Modification time overhead of different number of blocks

與文獻(xiàn)[16] 相比, 當(dāng)修改數(shù)據(jù)塊數(shù)小于5000 時, 兩方案的時間開銷是相似的, 但當(dāng)修改數(shù)據(jù)塊數(shù)繼續(xù)增加時, 本方案的時間開銷高于文獻(xiàn)[16] 方案的開銷. 由于文獻(xiàn)[16] 方案采用RTable 數(shù)據(jù)結(jié)構(gòu), 在查找數(shù)據(jù)塊時速度比較快, 所以在修改數(shù)據(jù)塊時優(yōu)于本文所提方案. 與文獻(xiàn)[9] 相比, 本文方案與文獻(xiàn)[16] 方案的數(shù)據(jù)修改效率均較高.

數(shù)據(jù)插入操作的時間開銷如圖12 所示, 文獻(xiàn)[9] 提出的動態(tài)數(shù)據(jù)插入操作需要重新調(diào)整Merkle 樹,所以會造成較大的計算開銷. 文獻(xiàn)[16] 提出的動態(tài)數(shù)據(jù)插入方案在插入數(shù)據(jù)塊F[i] 時, 需要(n ?i) 次數(shù)據(jù)塊移動操作, 因此會造成較大的時間開銷. 而在本文所提方案中, 插入數(shù)據(jù)塊F[i] 只需要修改對應(yīng)的指針, 即只需移動1 次, 從而可以極大地降低插入操作的時間開銷. 實驗結(jié)果表明本文所提出方案可以顯著降低插入數(shù)據(jù)的計算開銷.

圖12 不同數(shù)據(jù)塊數(shù)的插入時間開銷Figure 12 Inserting time overhead of different number of blocks

數(shù)據(jù)附加操作的時間開銷如圖13 所示, 文獻(xiàn)[9] 提出的動態(tài)數(shù)據(jù)附加方案需要重新調(diào)整Merkle 樹,因此有較高的計算開銷. 在文獻(xiàn)[16] 提出的動態(tài)數(shù)據(jù)附加方案中, 當(dāng)附加數(shù)據(jù)塊F[n+ 1] 時, 需要將RTable 表的長度由n增加為n+1, 此操作的時間開銷較大. 而在本文所提方案中, 附加數(shù)據(jù)塊F[n+1]只需將rear 指針指向新的附加數(shù)據(jù)塊, 因此本文方案的附加操作可以顯著降低計算開銷.

圖13 附加不同數(shù)據(jù)塊數(shù)的時間開銷Figure 13 Addition time overhead of different number of blocks

數(shù)據(jù)刪除操作的時間開銷如圖14 所示, 刪除操作與插入操作正好相反, 即刪除數(shù)據(jù)塊F[i] 時, 文獻(xiàn)[16] 提出的動態(tài)數(shù)據(jù)刪除操作需要移動(n ?i) 次數(shù)據(jù)塊; 文獻(xiàn)[9] 刪除數(shù)據(jù)塊時與動態(tài)插入數(shù)據(jù)一樣,需要動態(tài)調(diào)整Merkle 樹, 因此它們的計算開銷均較大. 本文所提方案只需更改對應(yīng)的指針, 即只需移動1次, 所以本文所提出方案刪除操作可以顯著地降低計算開銷.

圖14 刪除不同數(shù)據(jù)塊數(shù)的時間開銷Figure 14 Deleting time overhead of different number of blocks

表1 主要分析文獻(xiàn)[9,16] 與本方案的外包數(shù)據(jù)更新的計算開銷對比, 其中n代表外包數(shù)據(jù)塊個數(shù),c代表更新的外包數(shù)據(jù)塊個數(shù).

表1 不同方案的數(shù)據(jù)更新操作對比Table 1 Comparison of data updating of different schemes

因此, 四種數(shù)據(jù)更新操作中, 文獻(xiàn)[16] 只有修改操作的時間開銷略低于本文方案, 其余三種更新操作,包括插入、附加與刪除操作的時間開銷都比本文方案高, 文獻(xiàn)[9] 的四種更新操作的時間開銷均是最大.總地來說, 本文方案的計算是最高效的.

6 結(jié)論與未來研究

本文提出一種高效的外包數(shù)據(jù)完整性驗證方案, 采用代數(shù)簽名驗證外包數(shù)據(jù)的完整性, 為了防止審計時造成數(shù)據(jù)隱私泄露問題, 引入了異或同態(tài)函數(shù). 同時為了更好地支持外包數(shù)據(jù)的動態(tài)更新操作, 我們設(shè)計出一種分治鄰接表數(shù)據(jù)結(jié)構(gòu)提供更加高效的數(shù)據(jù)更新. 實驗結(jié)果表明本文方案的可行性和高效性. 下一步工作中, 我們將在此基礎(chǔ)上通過運用輕量級加密技術(shù), 實現(xiàn)更加有效防止外包數(shù)據(jù)泄露的方法, 同時希望將本方案進(jìn)一步擴(kuò)展, 用于分布式云存儲系統(tǒng).