王瑞錦，張鳳荔，王馨云，陳學(xué)勤，羅 昊，秦圣智

(電子科技大學(xué)信息與軟件工程學(xué)院 成都 610054)

隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)的不斷發(fā)展，在網(wǎng)絡(luò)中傳輸?shù)男畔⒊霈F(xiàn)了爆炸式的增長，海量的數(shù)據(jù)量給存儲(chǔ)能力和成本帶來了巨大的壓力[1]。在這種情況下云存儲(chǔ)技術(shù)應(yīng)運(yùn)而生，云存儲(chǔ)基于云計(jì)算，利用分布式計(jì)算和集群應(yīng)用等技術(shù)，將大量設(shè)備整合起來，為用戶提供數(shù)據(jù)存儲(chǔ)和訪問功能[2]。云存儲(chǔ)具有成本低廉、不受地理位置限制的資源訪問、易于管理和擴(kuò)充等優(yōu)點(diǎn)[3]，被視為IT企業(yè)的下一代數(shù)據(jù)存儲(chǔ)模型[4]。

用戶使用云存儲(chǔ)服務(wù)將文件提交到云服務(wù)提供商(cloud service provider, CSP)進(jìn)行在線存儲(chǔ)，在減輕本地存儲(chǔ)壓力的同時(shí)，也失去了對(duì)數(shù)據(jù)的物理控制能力[5]，因此數(shù)據(jù)的安全問題[6-8]是一個(gè)不容忽視的問題。CSP可能是不誠實(shí)的[9]，會(huì)為了自身的利益威脅到用戶的數(shù)據(jù)安全，例如當(dāng)CSP的存儲(chǔ)設(shè)備容量不足時(shí)，CSP可能會(huì)選擇刪除一些用戶長時(shí)間沒有訪問過的數(shù)據(jù)或者將這些數(shù)據(jù)移動(dòng)到廉價(jià)的離線存儲(chǔ)介質(zhì)中以節(jié)省開支[10]，這會(huì)造成用戶數(shù)據(jù)的永久或暫時(shí)不可訪問。另外在遭遇拜占庭失敗時(shí)CSP可能會(huì)為了維護(hù)自己的信譽(yù)而試圖向用戶隱瞞數(shù)據(jù)丟失的情況[11]。

目前已經(jīng)出現(xiàn)了多種針對(duì)云存儲(chǔ)環(huán)境的數(shù)據(jù)完整性驗(yàn)證方案。一個(gè)實(shí)用的云存儲(chǔ)完整性驗(yàn)證算法應(yīng)該具有較小的網(wǎng)絡(luò)開銷，并且沒有驗(yàn)證次數(shù)的限制，另外由于用戶存在對(duì)云端的數(shù)據(jù)進(jìn)行操作的需求，因此一個(gè)實(shí)用的完整性驗(yàn)證方案還要能支持動(dòng)態(tài)操作。文獻(xiàn)[12]提出了兩種針對(duì)云存儲(chǔ)的完整性驗(yàn)證算法，然而這兩種方法均不能對(duì)文件的動(dòng)態(tài)操作提供支持；文獻(xiàn)[13]提出了一種基于Diffie-Hellman體制的完整性驗(yàn)證方法，該方法對(duì)驗(yàn)證次數(shù)沒有限制，但是不能支持?jǐn)?shù)據(jù)塊的插入操作并且計(jì)算開銷較大；文獻(xiàn)[10]提出了一種基于merkel hash tree(MHT)的完整性認(rèn)證方案，在該方案中，CSP為產(chǎn)生一次完整性驗(yàn)證需要讀取所有的數(shù)據(jù)塊以得到Merkel哈希樹，當(dāng)用戶數(shù)據(jù)較大或數(shù)據(jù)塊較小時(shí)，會(huì)使得Merkel哈希樹的深度過深而消耗較多的計(jì)算資源，影響CSP的服務(wù)質(zhì)量；文獻(xiàn)[14]提出了一種基于改進(jìn)的Merkel哈希樹和雙線性對(duì)的完整性審計(jì)方案，在該方案中按照兩個(gè)層級(jí)對(duì)用戶數(shù)據(jù)進(jìn)行劃分，使Merkel哈希樹中的每一個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)多個(gè)數(shù)據(jù)塊，從而降低Merkel哈希樹的深度，提高構(gòu)造效率，同時(shí)該方案也能夠支持?jǐn)?shù)據(jù)塊的動(dòng)態(tài)操作。然而在極端情況下，例如用戶不斷在文件的末尾追加數(shù)據(jù)塊，則會(huì)出現(xiàn)文獻(xiàn)[14]中提到的樹不平衡的情況，從而使根結(jié)點(diǎn)到某個(gè)葉子節(jié)點(diǎn)的路徑過長，效率將會(huì)在很大程度上降低。

為了解決文獻(xiàn)[14]中提出的方案在上述情況下的效率問題，本文基于改進(jìn)的跳表和短簽名技術(shù)，提出一種能夠支持動(dòng)態(tài)操作的完整性驗(yàn)證協(xié)議。本文對(duì)跳表中的結(jié)點(diǎn)提出一種新的定義方式，該定義方式可以在邏輯上消除跳表中的環(huán)狀結(jié)構(gòu)，從而降低跳表中結(jié)點(diǎn)的依賴關(guān)系數(shù)量，在生成跳表、更新跳表和進(jìn)行驗(yàn)證時(shí)降低計(jì)算開銷；同時(shí)本文在跳表中引入可達(dá)范圍計(jì)數(shù)，使得在發(fā)生數(shù)據(jù)塊的插入和刪除時(shí)，跳表中需要更新的結(jié)點(diǎn)數(shù)量更少，從而更有效地對(duì)動(dòng)態(tài)操作提供支持。最后對(duì)該方案進(jìn)行了理論分析和實(shí)驗(yàn)驗(yàn)證，證明該方案是高效的。

1 理 論

1.1 系統(tǒng)模型

針對(duì)云存儲(chǔ)的完整性驗(yàn)證系統(tǒng)通?？梢苑譃閮煞侥Ｐ秃腿侥Ｐ停渲袃煞侥Ｐ椭邪脩?Client)和云存儲(chǔ)服務(wù)提供商(CSP)，三方模型在兩方模型的基礎(chǔ)上引入了一個(gè)可信的第三方驗(yàn)證者(TPA)，TPA用于為用戶承擔(dān)驗(yàn)證任務(wù)，代替用戶周期性的對(duì)存儲(chǔ)在CSP中的數(shù)據(jù)和文件進(jìn)行完整性驗(yàn)證。本文提出的方案基于兩方模型，如圖1所示。

圖中用戶指有著數(shù)據(jù)在線存儲(chǔ)需求的云存儲(chǔ)服務(wù)用戶；云存儲(chǔ)服務(wù)器是由云存儲(chǔ)服務(wù)提供商管理的一組服務(wù)器，具有海量的存儲(chǔ)能力和強(qiáng)大的計(jì)算能力，對(duì)外提供數(shù)據(jù)存儲(chǔ)和訪問功能。在本文提出的方案中，用戶在對(duì)文件進(jìn)行訪問時(shí)，同時(shí)獲取與之對(duì)應(yīng)的輔助認(rèn)證信息，使用輔助認(rèn)證信息對(duì)正在訪問的文件進(jìn)行完整性驗(yàn)證。本文中對(duì)文件的分塊處理與文獻(xiàn)[14]類似，即按照固定的塊大小對(duì)文件進(jìn)行劃分，產(chǎn)生認(rèn)證數(shù)據(jù)的基本單位是數(shù)據(jù)塊。

圖1 兩方模型

在本文提出的協(xié)議中，用戶將數(shù)據(jù)提交到云端進(jìn)行在線存儲(chǔ)前，首先需要在本地對(duì)文件進(jìn)行一些處理工作，包括文件的塊劃分、摘要生成、跳表生成、簽名等，完成上述步驟后，用戶將文件和輔助認(rèn)證信息一并提交到云端進(jìn)行保存，之后用戶便刪除本地的文件副本和輔助驗(yàn)證信息副本，以減輕本地的存儲(chǔ)壓力。用戶在訪問存儲(chǔ)在云端的文件時(shí)，獲取需要訪問的部分以及該部分對(duì)應(yīng)的輔助認(rèn)證信息，使用輔助認(rèn)證信息對(duì)該部分的文件內(nèi)容進(jìn)行驗(yàn)證，以便確定該部分文件內(nèi)容是否正確和完整。

1.2 跳表

跳表(skip lists)是一種能夠快速進(jìn)行查找、刪除和插入的數(shù)據(jù)結(jié)構(gòu)，跳表的結(jié)構(gòu)如圖2所示。

圖2 跳表的結(jié)構(gòu)

跳表包含若干層，其中每一層均由鏈表構(gòu)建，跳表中的每一個(gè)結(jié)點(diǎn)均包含一個(gè)指向右邊結(jié)點(diǎn)的指針和一個(gè)指向下方結(jié)點(diǎn)的指針，跳表中最左邊一列和最右邊一列的結(jié)點(diǎn)被稱為哨兵結(jié)點(diǎn)。跳表中的底層鏈表有序地存儲(chǔ)所有元素，對(duì)于某一層Si和Si的上一層Si+1，出現(xiàn)在Si中的非哨兵結(jié)點(diǎn)將以某個(gè)概率出現(xiàn)在上一層中，即以一定概率在Si+1層中生成對(duì)應(yīng)結(jié)點(diǎn)，并且哨兵結(jié)點(diǎn)所在列的層數(shù)不小于任何非哨兵結(jié)點(diǎn)所在列。

在跳表中進(jìn)行查找，從左上角的結(jié)點(diǎn)開始，用p表示指向當(dāng)前結(jié)點(diǎn)的指針，p只能向右或者向下移動(dòng)，查找某個(gè)結(jié)點(diǎn)的算法描述如下：

查找過程結(jié)束時(shí)，p指向目標(biāo)結(jié)點(diǎn)或者小于目標(biāo)結(jié)點(diǎn)的最大結(jié)點(diǎn)。

在跳表中插入一個(gè)結(jié)點(diǎn)時(shí)，例如需要插入的結(jié)點(diǎn)編號(hào)為x，則首先執(zhí)行查找x的操作，得到一個(gè)指向小于x的最大結(jié)點(diǎn)的指針，此時(shí)再將x結(jié)點(diǎn)插入到p所指向的結(jié)點(diǎn)的后面，并概率性地產(chǎn)生x結(jié)點(diǎn)的上層結(jié)點(diǎn)。

執(zhí)行刪除操作時(shí)，首先執(zhí)行查找操作找到小于目標(biāo)結(jié)點(diǎn)的最大結(jié)點(diǎn)所在位置，之后刪除目標(biāo)結(jié)點(diǎn)以及目標(biāo)結(jié)點(diǎn)所在列的所有結(jié)點(diǎn)，該過程與在鏈表中刪除一個(gè)結(jié)點(diǎn)類似。

1.3 可交換哈希函數(shù)

標(biāo)準(zhǔn)的哈希函數(shù)只有一個(gè)輸入?yún)?shù)，可交換哈希函數(shù)是一種包含多個(gè)輸入?yún)?shù)的哈希函數(shù)，并且當(dāng)輸入?yún)?shù)均保持不變時(shí)，任意交換各個(gè)參數(shù)的輸入順序，函數(shù)的輸出是一致的。包含2個(gè)輸入?yún)?shù)的可交換哈希函數(shù)滿足下述性質(zhì)：

式中，EH是可交換哈希函數(shù)，本文使用的可交換哈希函數(shù)包含3個(gè)輸入?yún)?shù)。

1.4 安全模型

在云存儲(chǔ)系統(tǒng)中，由于云存儲(chǔ)服務(wù)器是半可信的，因此用戶存儲(chǔ)在云端的文件面臨著損壞、篡改甚至被云存儲(chǔ)服務(wù)提供商有意刪除等風(fēng)險(xiǎn)，而云存儲(chǔ)服務(wù)提供可能會(huì)為了維護(hù)其自身利益而向用戶隱瞞并且試圖在文件的完整性被破壞后通過某種方法使得用戶不能發(fā)現(xiàn)文件的完整性已經(jīng)被破壞，所以該系統(tǒng)中可能會(huì)出現(xiàn)如下形式的攻擊：

1)偽造數(shù)據(jù)塊的攻擊。用戶在訪問某個(gè)存儲(chǔ)在云服務(wù)器中的數(shù)據(jù)塊時(shí)，如果云服務(wù)器發(fā)現(xiàn)該數(shù)據(jù)塊存在丟失、部分丟失或被篡改的情況，云服務(wù)器可能會(huì)通過某種技術(shù)手段偽造一個(gè)數(shù)據(jù)塊提供給用戶，從而使得用戶不能發(fā)現(xiàn)完整性已被破壞。

2)偽造輔助認(rèn)證信息的攻擊。用戶在訪問某個(gè)存儲(chǔ)在云服務(wù)器中的數(shù)據(jù)塊時(shí)，如果該數(shù)據(jù)塊或?qū)?yīng)的輔助認(rèn)證信息存在丟失、部分丟失或者被篡改的情況，云服務(wù)器可能會(huì)偽造一對(duì)對(duì)應(yīng)的數(shù)據(jù)塊和輔助認(rèn)證信息提供給用戶，從而使得用戶不能發(fā)現(xiàn)完整性已被破壞。

2 協(xié)議的構(gòu)造

2.1 改進(jìn)的跳表

本文對(duì)跳表的改進(jìn)主要有3點(diǎn)：

定義 1定義跳表中的子結(jié)點(diǎn)。對(duì)于跳表中的結(jié)點(diǎn)i，定義其左邊的結(jié)點(diǎn)j和下面的結(jié)點(diǎn)k為結(jié)點(diǎn)i的子結(jié)點(diǎn)，如果結(jié)點(diǎn)j是所在列的頂層結(jié)點(diǎn)，則稱j是i的實(shí)子結(jié)點(diǎn)，否則稱j是i的虛子結(jié)點(diǎn)。

定義 2跳表中的底層非哨兵結(jié)點(diǎn)存儲(chǔ)2個(gè)哈希值，分別稱為contentHash和nodeHash。跳表中的其他結(jié)點(diǎn)只存儲(chǔ)nodeHash，其中contentHash直接通過使用哈希函數(shù)對(duì)數(shù)據(jù)塊計(jì)算摘要得到。

定義 3跳表中的結(jié)點(diǎn)不再存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)塊的索引，而是存儲(chǔ)以該結(jié)點(diǎn)為祖先結(jié)點(diǎn)的底層結(jié)點(diǎn)數(shù)量。

根據(jù)定義1可知本文所使用的跳表的根結(jié)點(diǎn)為右邊哨兵結(jié)點(diǎn)的頂層結(jié)點(diǎn)，該跳表的結(jié)構(gòu)如圖3所示，其中虛線框代表的是虛子結(jié)點(diǎn)，虛線箭頭為父結(jié)點(diǎn)指向虛子結(jié)點(diǎn)的指針，方框內(nèi)“+”和“-”為哨兵結(jié)點(diǎn)。

圖3 改進(jìn)的跳表結(jié)構(gòu)

在該跳表中，底層結(jié)點(diǎn)中的contentHash用于存儲(chǔ)數(shù)據(jù)塊的摘要值。假設(shè)當(dāng)前結(jié)點(diǎn)是i，i的左子結(jié)點(diǎn)是j，i的下子結(jié)點(diǎn)是k，計(jì)算i結(jié)點(diǎn)的nodeHash時(shí)，根據(jù)下面所定義的依賴關(guān)系進(jìn)行。

1)若k==null，即i是底層結(jié)點(diǎn)。

①如果i是哨兵結(jié)點(diǎn)，并且j是虛子結(jié)點(diǎn)：

②如果i是哨兵結(jié)點(diǎn)，并且j是實(shí)子結(jié)點(diǎn)：

③如果i不是哨兵結(jié)點(diǎn)，并且j是虛子結(jié)點(diǎn)：

④如果i不是哨兵結(jié)點(diǎn)，并且j是實(shí)子結(jié)點(diǎn)：

2)若k!=null，即i是非底層結(jié)點(diǎn)。

①如果j是虛子結(jié)點(diǎn)：

②如果j是實(shí)子結(jié)點(diǎn)：

式中，φ是一個(gè)特定的字符串。根據(jù)上述依賴關(guān)系可知，在本文所使用的跳表中，信息的流向所構(gòu)成的結(jié)構(gòu)為樹狀結(jié)構(gòu)，并且該樹狀結(jié)構(gòu)的根結(jié)點(diǎn)為跳表的右上方結(jié)點(diǎn)。

根據(jù)定義3，本文使用的跳表中不記錄數(shù)據(jù)塊在文件中的索引，而使用可達(dá)范圍計(jì)數(shù)來確定跳表結(jié)點(diǎn)與數(shù)據(jù)塊的對(duì)應(yīng)關(guān)系，因此在某個(gè)位置新加入一個(gè)結(jié)點(diǎn)后，不需要對(duì)該結(jié)點(diǎn)之后的每一個(gè)結(jié)點(diǎn)進(jìn)行修改，只需要修改從新加入結(jié)點(diǎn)到根結(jié)點(diǎn)這一條路徑上所經(jīng)過的結(jié)點(diǎn)的可達(dá)范圍計(jì)數(shù)，該路徑的平均長度為log(n)，因此能夠更高效的對(duì)動(dòng)態(tài)操作提供支持。使用可達(dá)范圍計(jì)數(shù)標(biāo)識(shí)數(shù)據(jù)塊與結(jié)點(diǎn)對(duì)應(yīng)關(guān)系的跳表結(jié)構(gòu)如圖4所示。其中橢圓型框圖代表數(shù)據(jù)塊，其中的數(shù)字代表數(shù)據(jù)塊索引；跳表中各個(gè)結(jié)點(diǎn)中的數(shù)字代表可達(dá)范圍計(jì)數(shù)。對(duì)于結(jié)點(diǎn)i以及其左子結(jié)點(diǎn)j和下子結(jié)點(diǎn)k，如果j是虛子結(jié)點(diǎn)，則i的計(jì)數(shù)等于k的計(jì)數(shù)；如果j是實(shí)子結(jié)點(diǎn)，則i的計(jì)數(shù)等于j與k的計(jì)數(shù)之和。

圖4 使用可達(dá)范圍計(jì)數(shù)的跳表結(jié)構(gòu)

在圖4所示的跳表中進(jìn)行查找某個(gè)數(shù)據(jù)塊對(duì)應(yīng)的結(jié)點(diǎn)時(shí)，指針p開始時(shí)指向根結(jié)點(diǎn)，查找算法如下：if(p.reachableCount＜target)

在執(zhí)行查找操作時(shí)，可以使用棧來記錄過程中經(jīng)過的結(jié)點(diǎn)路徑，使用該路徑可以得到目標(biāo)結(jié)點(diǎn)對(duì)應(yīng)的輔助認(rèn)證信息。在該跳表中執(zhí)行數(shù)據(jù)塊的插入和刪除操作時(shí)，首先執(zhí)行查找操作，其余部分與基礎(chǔ)跳表的操作方法類似，在此不再贅述。

2.2 基本方案

假設(shè)用戶需要提交到云服務(wù)器進(jìn)行保存的文件是M，M包含n個(gè)數(shù)據(jù)塊，即M={m1,m2,…,mn}，基本方案由3個(gè)步驟組成。

1)SetUp(1λ)→(H,EH,sk,pk)。用戶選擇隨機(jī)數(shù)得到用戶私鑰sk=(x,g)，其中g(shù)是群G的生成元，G是基于橢圓曲線構(gòu)造的乘法循環(huán)群，G的階數(shù)為p。用戶根據(jù)私鑰計(jì)算公鑰pk=(y,g)，其中y=gx，根據(jù)雙線性對(duì)的性質(zhì)[15]，有等式e(y,g)=e(g,g)x=e(g,y)成立。同時(shí)用戶還需要選擇在協(xié)議中使用的哈希函數(shù)和可交換哈希函數(shù)；

2)GenSL(M,H,EH,sk)→(SL,σ)。用戶對(duì)文件M進(jìn)行分塊處理，得到數(shù)據(jù)塊集合M={m1,m2,…,mn}，并產(chǎn)生跳表SL，SL的底層結(jié)點(diǎn)數(shù)量為n+2，包含2個(gè)哨兵結(jié)點(diǎn)和n個(gè)非哨兵結(jié)點(diǎn)。之后用戶使用哈希函數(shù)H計(jì)算數(shù)據(jù)塊集合中每一個(gè)元素的摘要指，并將摘要值按順序?qū)懭胩淼讓臃巧诒Y(jié)點(diǎn)的contentHash中。最后用戶使用可交換哈希函數(shù)EH計(jì)算SL中每一個(gè)結(jié)點(diǎn)的nodeHash值，并使用私鑰sk對(duì)根節(jié)點(diǎn)r的nodeHash值進(jìn)行簽名，得到簽名值σ。完成上述步驟后，用戶將(SL,σ)和文件M提交到云存儲(chǔ)服務(wù)器進(jìn)行在線存儲(chǔ)；

3)Verify(mi,ηi,σ,H,EH,pk)→true/false 。當(dāng)用戶訪問數(shù)據(jù)塊集合中的某個(gè)數(shù)據(jù)塊mi時(shí)，云存儲(chǔ)服務(wù)器一并向用戶返回?cái)?shù)據(jù)塊mi、輔助驗(yàn)證信息ηi和根結(jié)點(diǎn)的簽名σ。輔助驗(yàn)證信息是一個(gè)集合，包含從mi所對(duì)應(yīng)的跳表結(jié)點(diǎn)到根節(jié)點(diǎn)所在路徑上的所需nodeHash，根據(jù)跳表的性質(zhì)，該集合的大小平均為log(n)，因此根據(jù)2.1節(jié)中定義的依賴關(guān)系，可以使用mi和輔助驗(yàn)證信息ηi計(jì)算出根節(jié)點(diǎn)r'。用戶計(jì)算出r'后，使用數(shù)字簽名σ驗(yàn)證r'的合法性，如果驗(yàn)證通過則系統(tǒng)返回true，否則返回false。

2.3 動(dòng)態(tài)操作

在本方案中，動(dòng)態(tài)操作包括3種類型：數(shù)據(jù)塊的修改(update)、插入(insert)和刪除(delete)。假設(shè)認(rèn)證結(jié)構(gòu)SL和簽名σ已經(jīng)生成并提交到云存儲(chǔ)服務(wù)器中進(jìn)行保存，下面介紹動(dòng)態(tài)操作過程。

1)用戶產(chǎn)生操作消息。用戶執(zhí)行算法GenOPMsg()，下面對(duì)不同的操作類型進(jìn)行描述。

修改操作：假設(shè)用戶對(duì)索引為x的數(shù)據(jù)塊進(jìn)行修改，得到新數(shù)據(jù)塊m′x，則用戶產(chǎn)生消息(update,x)，并將消息發(fā)送至云存儲(chǔ)服務(wù)器。

插入操作：假設(shè)用戶需要在文件中的x位置新插入一個(gè)數(shù)據(jù)塊mx，則用戶使用特定概率計(jì)算新插入數(shù)據(jù)塊在跳表中對(duì)應(yīng)的結(jié)點(diǎn)所在列的層數(shù)L，并將消息(insert,x,L)發(fā)送至云存儲(chǔ)服務(wù)器。

刪除操作：假設(shè)用戶需要?jiǎng)h除文件中的第x個(gè)數(shù)據(jù)塊，則用戶產(chǎn)生消息(delete,x)并發(fā)送至云存儲(chǔ)服務(wù)器。

2)更新SL與簽名。云存儲(chǔ)服務(wù)器在接收到用戶的動(dòng)態(tài)操作請(qǐng)求后，根據(jù)消息內(nèi)容返回所需的輔助認(rèn)證信息，以便用戶對(duì)SL進(jìn)行更新和對(duì)新的SL簽名，下面詳細(xì)介紹其過程。

修改操作：云存儲(chǔ)服務(wù)器返回原數(shù)據(jù)塊mx所對(duì)應(yīng)的輔助認(rèn)證信息ηx。用戶接收到ηx后，使用m′x計(jì)算摘要值并將其作為第x個(gè)跳表結(jié)點(diǎn)的contentHash，再根據(jù)輔助認(rèn)證信息ηx計(jì)算得到根節(jié)點(diǎn)的nodeHash，并對(duì)其簽名。

插入操作：云存儲(chǔ)服務(wù)器在SL中的第x個(gè)位置新插入一列結(jié)點(diǎn)，該列的高度為L。此時(shí)新插入結(jié)點(diǎn)的contentHash和nodeHash均為空值，然后執(zhí)行查找算法find(x)并得到輔助認(rèn)證信息ηx，云存儲(chǔ)服務(wù)器將ηx返回給用戶，用戶使用mx計(jì)算摘要值并將其作為第x個(gè)跳表結(jié)點(diǎn)的contentHash，再根據(jù)輔助認(rèn)證信息ηx計(jì)算得到根節(jié)點(diǎn)的nodeHash，并對(duì)其簽名。

刪除操作：云存儲(chǔ)服務(wù)器將目標(biāo)結(jié)點(diǎn)x所在列刪除，目標(biāo)結(jié)點(diǎn)后面的結(jié)點(diǎn)將占據(jù)第x個(gè)位置。此時(shí)云存儲(chǔ)服務(wù)器執(zhí)行算法find(x)得到第x個(gè)節(jié)點(diǎn)的輔助認(rèn)證信息ηx，并將ηx與刪除第x個(gè)數(shù)據(jù)塊后、在文件中的索引變更為x的數(shù)據(jù)塊mx返回給用戶。用戶根據(jù)mx和ηx計(jì)算得到SL根結(jié)點(diǎn)的nodeHash并對(duì)其簽名。

3)提交更改。如果用戶執(zhí)行的是修改操作，則向云存儲(chǔ)服務(wù)器提交(m′x,σ′)；如果執(zhí)行的是插入操作，則向云存儲(chǔ)服務(wù)器提交(mx,σ′)；如果執(zhí)行的刪除操作，則向云存儲(chǔ)服務(wù)器提交(σ′)。

2.4 安全性分析

本協(xié)議的攻擊類型主要有數(shù)據(jù)塊偽造攻擊和輔助認(rèn)證信息偽造攻擊兩種，下面分別對(duì)其進(jìn)行簡要的安全性分析。

1)數(shù)據(jù)塊偽造攻擊。假設(shè)在用戶對(duì)數(shù)據(jù)塊mx進(jìn)行完整性驗(yàn)證時(shí)，云存儲(chǔ)服務(wù)器偽造了一個(gè)數(shù)據(jù)塊并且云存儲(chǔ)服務(wù)器向用戶返回假設(shè)該三元組能夠通過驗(yàn)證，則等價(jià)于云存儲(chǔ)服務(wù)器有能力找到m1≠m2，使得Hash(m1)=Hash(m2)，但根據(jù)哈希函數(shù)的單向性和抗碰撞性，這個(gè)問題是一個(gè)困難問題，因此上述三元組不能以不可忽略的概率通過用戶的驗(yàn)證，本協(xié)議能夠抵抗數(shù)據(jù)塊偽造攻擊。

2)輔助認(rèn)證信息偽造攻擊。假設(shè)云存儲(chǔ)能夠用不合法的數(shù)據(jù)塊m′x代替合法數(shù)據(jù)塊mx計(jì)算出非法的SL根節(jié)點(diǎn)nodeHash并對(duì)其簽名，并且該非法簽名和非法的SL根結(jié)點(diǎn)nodeHash能夠通過用戶的公鑰驗(yàn)證，則等價(jià)于云存儲(chǔ)服務(wù)器能夠在沒有私鑰的情況下產(chǎn)生合法簽名，根據(jù)數(shù)字簽名的定義，可知該問題是一個(gè)困難問題，因此云存儲(chǔ)服務(wù)器無法以不可忽略的概率產(chǎn)生合法簽名，本協(xié)議能夠抵抗輔助認(rèn)證信息偽造攻擊。

3 性能分析

將本文算法與另外3種針對(duì)云存儲(chǔ)環(huán)境的數(shù)據(jù)完整性驗(yàn)證方案進(jìn)行性能對(duì)比，之后將本文的方案與文獻(xiàn)[14]的方案進(jìn)行模擬分析實(shí)驗(yàn)。本文所提出的協(xié)議與文獻(xiàn)[14]中所提出的方案在初始化階段均需生成輔助認(rèn)證信息，而產(chǎn)生輔助認(rèn)證信息的時(shí)間復(fù)雜度均為O(n)，且產(chǎn)生的認(rèn)證結(jié)構(gòu)中所包含的節(jié)點(diǎn)數(shù)量的期望值均為文件塊數(shù)量的2倍，因此該部分不做性能測試。

設(shè)n代表用戶需要存儲(chǔ)在云服務(wù)器中的文件包含的數(shù)據(jù)塊數(shù)量，本文與PDP方案、文獻(xiàn)[10]和文獻(xiàn)[14]方案的性能分析對(duì)比結(jié)果如表1所示。

表1 性能分析比較

為支持動(dòng)態(tài)操作，需要使用能夠支持動(dòng)態(tài)操作的認(rèn)證性數(shù)據(jù)結(jié)構(gòu)，本文方案使用的是前面介紹的跳表。在驗(yàn)證時(shí)，從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的平均路徑長度是logn，因此驗(yàn)證時(shí)的計(jì)算復(fù)雜度是O(logn)，如表1所示。

下面將本文的方案與文獻(xiàn)[14]中的方案進(jìn)行模擬對(duì)比實(shí)驗(yàn)。實(shí)現(xiàn)環(huán)境的配置為：主頻為3.2 GHz的雙核CPU臺(tái)式計(jì)算機(jī)，8 GB內(nèi)存，64位Windows 7操作系統(tǒng)，編碼所用的開發(fā)語言為Java，使用的密碼學(xué)工具庫為jPBC v2.0.0。

對(duì)于日志文件，在文件的尾部追加內(nèi)容是一種常態(tài)操作。本文測試的場景為連續(xù)向文件尾部追加數(shù)據(jù)塊，測試開始前用大小為1 GB的文件產(chǎn)生認(rèn)證結(jié)構(gòu)，文件塊的大小設(shè)置為8 KB，通過在文件的尾部追加不同數(shù)量的文件塊以造成認(rèn)證結(jié)構(gòu)出現(xiàn)不同程度的不平衡。測量在不同程度的不平衡狀態(tài)下，為每一個(gè)追加的文件塊進(jìn)行結(jié)構(gòu)調(diào)整所消耗的平均時(shí)間，測試結(jié)果如圖5所示。

從理論分析而言，本文所提出的協(xié)議在執(zhí)行尾部追加操作時(shí)，為每一個(gè)追加的文件塊進(jìn)行結(jié)構(gòu)調(diào)整的平均時(shí)間復(fù)雜度為O(logn)。從上述測試結(jié)果可知，在向文件尾部進(jìn)行連續(xù)追加文件塊的場景中，本文提出的協(xié)議性能優(yōu)于文獻(xiàn)[14]中的方案。

測試向文件中隨機(jī)插入文件塊，測試前先用1 GB大小的文件產(chǎn)生認(rèn)證結(jié)構(gòu)，文件塊的大小設(shè)置為8 KB，測試在文件中隨機(jī)插入不同數(shù)量的文件塊后，平均插入每一個(gè)文件塊時(shí)，調(diào)整認(rèn)證結(jié)構(gòu)所消耗的時(shí)間，測試結(jié)果如圖6所示。測試結(jié)果顯示本文方案與文獻(xiàn)[14]中的方案性能相近。

圖5 連續(xù)在末尾追加數(shù)據(jù)塊

圖6 在隨機(jī)位置插入數(shù)據(jù)塊

圖7 對(duì)尾部數(shù)據(jù)塊進(jìn)行完整性驗(yàn)證

測試不平衡狀態(tài)下驗(yàn)證的時(shí)間消耗，首先在云端存儲(chǔ)大小為1 GB的文件塊和對(duì)應(yīng)的認(rèn)證結(jié)構(gòu)，文件塊的大小設(shè)置為8 KB，通過在原始文件尾部追加不同數(shù)量的文件塊以造成認(rèn)證結(jié)構(gòu)出現(xiàn)不同程度的不平衡后，對(duì)最后一個(gè)文件塊進(jìn)行完整性驗(yàn)證以觀察在不同程度的不平衡下，驗(yàn)證所需要的時(shí)間，測試結(jié)果如圖7所示。從測試結(jié)果可知，在不平衡狀態(tài)下，本文所提出的方案在驗(yàn)證時(shí)的性能優(yōu)于文獻(xiàn)[14]中的方案。

4 結(jié) 束 語

云存儲(chǔ)中的數(shù)據(jù)安全問題是不可回避的問題，而數(shù)據(jù)的完整性驗(yàn)證是保護(hù)數(shù)據(jù)安全的重要手段之一，因此面向云存儲(chǔ)和量子存儲(chǔ)的完整性驗(yàn)證方法和協(xié)議成為了近幾年的研究熱點(diǎn)之一[15-16]。本文基于改進(jìn)的跳表提出一種適用于兩方模型的云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證協(xié)議，理論分析和模擬實(shí)驗(yàn)證明該協(xié)議具有較高的效率，但該方案沒有考慮驗(yàn)證任務(wù)的代理問題，今后的工作將是對(duì)驗(yàn)證任務(wù)的代理問題進(jìn)行研究。

[1]耿紀(jì)昭. 云存儲(chǔ)中數(shù)據(jù)完整性驗(yàn)證機(jī)制的研究與實(shí)現(xiàn)[D].成都： 電子科技大學(xué), 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]蘇蘭. 面向云計(jì)算的數(shù)據(jù)完整性檢驗(yàn)方法研究與實(shí)現(xiàn)[D].成都： 電子科技大學(xué), 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]鄧曉鵬, 馬自堂, 高敏霞. 一種基于雙線性對(duì)的云數(shù)據(jù)完整性驗(yàn)證算法[J]. 計(jì)算機(jī)應(yīng)用研究, 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]傅穎勛, 羅圣美, 舒繼武. 安全云存儲(chǔ)系統(tǒng)與關(guān)鍵技術(shù)綜述[J]. 計(jì)算機(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]李暉, 孫文海, 李鳳華. 公共云存儲(chǔ)服務(wù)數(shù)據(jù)安全及隱私保護(hù)技術(shù)綜述[J]. 計(jì)算機(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]秦志光, 王士雨, 趙洋. 云存儲(chǔ)服務(wù)的動(dòng)態(tài)數(shù)據(jù)完整性審計(jì)方案[J]. 計(jì)算機(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.