一種改進的多用戶多副本數據完整性驗證方案

潘洪志 方 群,2 何 昕,2

1(安徽師范大學計算機與信息學院 安徽蕪湖 241002) 2 (網絡與信息安全安徽省重點實驗室(安徽師范大學) 安徽蕪湖 241002 (asdphz2015@163.com)

在云環境中，用戶會將自己的數據設計成多個副本存儲在云存儲服務提供商提供的多個存儲節點上，對于用戶來說，數據的存儲過程是透明的，用戶在需要的時候取出即可[1-4].可是用戶的數據存儲在各個數據節點上并不是平行的.為了節約存儲空間和提高經濟效益，對于某些不常用，不常訪問的數據，云服務提供商可能會對這些數據進行竊取、篡改[5].同時，一些不可信的云存儲環境可能會使用戶數據遭受窺視或損壞.用戶雖然采用匿名加密[6]、數據分塊交叉存儲[7]等技術來保障數據的隱秘性，但對數據的安全性并不能完全保證.因此，我們需要采用合適的多副本數據完整性驗證策略，在提高驗證效率的同時保護用戶數據的可靠性.

目前大部分方案是采用Merkle樹[8]、跳表[9]等樹形結構來支持多副本和支持動態更新環境下的完整性驗證策略，這些策略雖然支持了數據動態更新，但在構造認證過程中需要大量的輔助信息，大大增加了數據訪問復雜度.本文在基于雙線性映射特性的簽名機制下，提出一種改進方案，利用自適應Trie樹的簡單結構來簡化驗證方式，同時利用隨機掩碼技術來滿足多副本的批量化驗證，高效地保護了用戶的數據安全.

本文首先給出云環境下數據完整性檢測模型，通過分析數據完整性驗證方案存在的問題給出最適合解決方案，最后通過理論分析和仿真實驗證明方法的有效性.

1 系統模型

本文中的系統模型如圖1所示，模型主要包括用戶(users)、可信第三方審計者(TPA)、云存儲服務提供商(CSP)，其中：

用戶(users).用戶將自己的數據存放在云服云存儲服務器上，通過客戶端訪問云存儲服務器.

可信第三方審計者(TPA).可信第三方審計者主要是幫助用戶存儲驗證信息和規則.通過用戶授權，代替用戶進行密鑰管理、數據完整性策略管理和數據驗證規則管理.

云存儲服務提供商(CSP).CSP提供計算資源、存儲資源和網絡資源.

在系統初始化階段，用戶初始化數據文件的初始數據，并與CSP和TTPA協商密鑰.在挑戰-應答階段，用戶可以保持離線，所有驗證工作由TTPA和CSP完成.當TTPA驗證數據完整性時，向CSP發送挑戰信息chal.CSP接收到挑戰后，根據存儲的數據生成完整證據P返回給TTPA，然后TTPA對接收的證據進行驗證，其過程如圖1所示：

圖1 數據完整性驗證模型

2 問題定義

2.1 數據完整性審計方案存在的問題

Ateniese等人[10]定義的PDP方案中，使用了基于RSA模指運算的同態標簽，在該方案中用于驗證服務器證明的元數據為wi=v‖i，生產的同態標簽為Ti=(h(wi)·gbi)dmodN，最后通過驗證下列等式是否成立來判斷云存儲服務器上的數據是否完整.

但是該方案并不能直接應用于云環境中多副本的存儲環境下，因為對于用戶來說，他們無法判斷云服務提供商是否存儲了和用戶商定的副本數量，若這里的副本都是相同的，則會出現云服務提供商只存儲了1份數據，但向用戶聲稱自己存儲了之前商定的足夠份數的數據，而用戶并不能判斷.針對這個不安全問題，Curmola等人[11]第1次提出了MR-PDP方案，用戶首先使用密鑰k和對稱加密算法對文件F加密，然后對密文F′進行分塊處理，得到F′={f1,f2,…,fn}.

F′=Ek(F),F′={f1,f2,…,fn}，

并通過隨機掩碼技術對密文塊F′={f1,f2,…,fn} 進行處理，得到Fu={fu,1,fu,2,…,fu,n},其中1≤i≤n,bu,i=fi+ru,i.通過偽隨機函數生成ru,i=ψz(u‖i),1≤i≤u.最后通過驗證下列等式是否成立來判斷云存儲服務器上的數據是否完整.

通過該方案識別用戶數據的完整性和安全性.但是該方案并不支持公共審計，如果將該方案直接應用到公共審計的環境下，則可能將ru,j信息泄露給可信第三方.

因此，在考慮多副本環境下，用戶除了對自己存放在云端的數據驗證是否完整之外，還需要能夠支持對云端數據進行動態更新操作.

2.2 多用戶多副本批量審計方案

2.2.1AT樹

Trie樹又稱字典樹、單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構.Trie樹利用字符串的公共前綴來節省空間，最大限度地減少不必要的字符串比較并提高查詢效率.傳統的Trie樹只有一類節點，以數組表示，每個index是指向子節點的指針.在AT樹中，新增2個新節點——葉子節點和擴展節點，節點由key和value組成.key為帶標識id的十六進制前綴碼，標識id用于區分葉子節點和擴展節點.若終止符標記被打開，那么key對應的是葉子節點，value存儲數據的Hash值；若終止符標記被關閉，那么value值就是用于在數據塊中查詢對應的節點的地址.

如圖2所示，擴展節點和葉子節點的id位為1個4 b二進制數字，最低位表示key的奇偶性，第二低位為編碼終止符狀態.

圖2 自適應Trie樹節點結構

圖3是一個自適應Trie樹的初始化結構圖:

圖3 自適應Trie樹的初始化結構圖

如圖3所示，通過增加節點的種類，樹的深度可以得到有效控制，避免攻擊者操縱樹的深度，發起DoS攻擊；而且樹的根只取決于數據的內容，與其更新順序無關.另外為保護機密性，AT樹節點二元組key,value只存儲經過特殊編碼的值，可有效保護數據隱私，提高安全性.

2.2.2數據完整性審計方案

數據完整性審計方案分為2個階段：初始化階段、審計階段.在初始化階段，用戶調用KeyGen()生成公鑰和私鑰；然后執行SigGen()生成數據塊、數據塊同態標簽.在審計階段，首先支持多個用戶驗證所有副本數據完整性.可信第三方調用chal生成挑戰信息.

假設G1,G2是階為素數p的乘法群，令e:G1×G2→Gt表示一個雙線性映射，u和g分別為G1和G2的生成元.

1)KeyGen():該階段首先在客戶端(Client)產生公鑰和私鑰.過程為：

Step1. 隨機選取α,β1,β2,…,βn∈p，g∈G1，H∈G1，選取隨機密鑰k；

Step2. 計算Hβi→Hi,Hi∈G2,1≤i≤n，y∈e(g,H),x0∈e(h,H)a0;

Step3. 輸出公鑰pk≡(k,Hn,y,x0)和私鑰sk≡(βn,L,a0,g).

2)SigGen(sk,F)→(Trust)：該階段為標簽生成階段，首先將用戶的數據進行加密處理，然后對加密的數據進行分塊，隨機化處理，生成1個同態標簽集合Trust，最后云服務提供商接收用戶處理后的數據進行構造對應的驗證結構.具體步驟如下：

Step1. 假設用戶數據原文件用F表示，對文件F進行加密處理得到F′，然后將文件F′分成n塊,得到F′≡(b1,b2,…,bn);

Step3. 使用隨機掩碼函數f(g):{0,1}k×{0,1}l→{0,1}l對分塊數據進行隨機化處理，得到ftk,i={mtk,1,mtk,2,…,mtk,n}，mtk,i=btk,i+rl,rl=f(l‖k),l∈p,1≤i≤n;

Step4. 計算各個數據塊的標簽值Ttk,i=Hk(mtk,i)·Hmtk,i，得到同態標簽集合Trusttk,i={Ttk,i|i∈{1,2,…,n}};

Step5. 用戶將本地的標簽集合Trusttk,i和數據文件分塊集合ftk,i發送給CSP，并刪除本地文件;

Step6. 云服務提供商將接收到的文件F生成c個副本，分別存儲在地理位置不同的服務器節點上，同時生成副本數據集ftk,i,j和標簽集合Trusttk,i,j，ftk,i,j={ftk,i,1,ftk,i,2,…,ftk,i,n}，Trusttk,i,j={Trusttk,i,1,Trusttk,i,2,…,Trusttk,i,n}，1≤j≤c;

Step7. 云服務提供商同時將副本數據集和標簽集合同步更新到各個數據節點，并給用戶反饋是否成功存儲的結果.

3)GenProof(F,chal,Trust)→(P).

用戶委托TPA對云存儲服務器節點中的數據進行完整性審計，TPA接收到用戶的授權之后，生成挑戰信息，并將挑戰信息發送給云服務提供商.然后云服務提供商對挑戰信息進行回復，將驗證信息返回給TPA.具體步驟如下：

Step1. 從集合{1,2,…,n}中隨機選擇c個元素組成集合Ic≡{s1,s2,…,sc},s1≤sc≤sn，用戶將挑戰消息chal≡{(Ic,N)}(其中N為時間戳)，發送給云服務提供商;

Step2. 云服務提供商收到挑戰信息chal,并將挑戰信息chal和副本信息生成調整信息chalu={ftk,i,j,Trusttk,i,j,chal},1≤u≤c分別發送給相對應的副本存儲器節點;

Step3. 云環境中的各個副本存儲節點接收到挑戰信息之后，分別計算持有性證據:

4)VerifyProof(chal,P)→(True,False)：輸入證據P和挑戰信息chal，如果驗證通過輸出True,驗證失敗輸出False.

審計者收到證據P后，審計者驗證式(1)，如果驗證成功，輸出結果為“True”,否則系統輸出“False”.公式為

(1)

2.2.3數據動態操作

本節主要討論用戶數據更新問題，用戶對云存儲數據更新操作包括數據修改(M)、數據刪除(D)和數據插入(I)操作.

1) 數據修改(M)

Step3. 客戶端接收到服務器反饋回來的驗證信息之后，和本地的信息作比對.如果確定信息正確，則刪除本地的已更新的數據塊和相關信息；如果校驗信息不正確，則重新請求更新操作.

算法1. 數據修改算法.

① Begin

Ttk,i,j);

Ttk,i,j);

⑧ Send the proofRUpdateto client;

⑩ Print True;

2) 數據插入(I)

假設第k個用戶需要在自己的數據中的第i個位置的數據塊前插入新的數據塊f*，則需要進行以下操作：

Step1. 計算需要新插入數據塊f*的認證標簽TF*，然后生成更新請求消息Update=(I,(k,i),f*,Tf*),并將請求消息發送給云服務器;

Step2. 服務器接收到客戶端的插入請求消息之后，根據(k，i)找到更新數據所要更新的位置，然后插入數據f*,同時更新認證標簽信息TF*,更新完成，反饋插入操作信息RUpdate;

Step3. 客戶端接收到服務器關于插入操作反饋的驗證信息之后，進行校驗，如果確定信息正確，則刪除本地已更新的數據塊和相關信息,如果校驗信息不正確，則重新請求插入操作.

算法2. 數據插入算法.

輸入：需要插入的數據塊ftk,i,j;

① Begin

② Input (f*);

③Tf*=Sign(f*);

④Update(f*)=(I，(k,i-1),f*,Tf*);

⑤ Send the requestUpdate(f*) to server;

⑥ExceUpdate(I，(k,i-1),f*,Tf*);

⑧ Send the proofRUpdateto client;

⑩ Print True;

3) 刪除操作(D)

假設第k個用戶需要刪除數據中第i個位置中的數據塊ftk,i,j.其操作步驟同插入類似，過程如下：

Step1. 客戶端生成請求消息Update=(M，(k,i),Ttk,i,j)發送給云存儲服務器.

Step2. 服務器收到更新請求之后，首先根據(k,i)找到數據所在位置，取出數據塊的標簽值和Ttk,i,j驗證，確定用戶的校驗值的信息是否正確.如果不正確就返回拒絕更新信息；如果正確，則更新相應的數據塊和數據塊的標簽，并返回更新后的數據塊的驗證信息RUpdate.

Step3. 客戶端接收到服務器反饋的驗證信息之后，和本地的信息作比對.如果確定信息正確，則刪除本地已更新的數據塊和相關信息；如果校驗信息不正確，則重新請求刪除操作.

算法3. 數據刪除算法.

輸入：待刪除數據塊;

① Begin

②Update(ftk,i,j)=(D，(k,i),ftk,i,j,Ttk,i,j);

③ Send the requestUpdate(ftk,i,j) to server;

④ExceUpdate(D，(k,i),ftk,i,j,Ttk,i,j);

⑥ Send the proofRUpdateto client;

⑧ Print True;

⑨ else Print False;

⑩ End

3 實驗分析

本節將從通信開銷和計算開銷來評價整個方案的性能.實驗環境為:Inter Core i5 CPU 2.3 GHz,內存4 GB，64 b Windows7操作系統.雙線性映射使用的是版本號為2.0.0.0的jpbc庫，使用128 b AES加密算法加密數據，使用橢圓曲線域表示G1,G2,GT，隨機數的大小為r=80,ρ=160.我們假設用戶數量為K，每個文件M大小為|M|=223b，副本數量為t.

假設可信第三方每次隨機挑戰n塊當中的c塊數據，并且存在1個惡意的云服務修改了其中的k塊數據.設隨機變量X表示檢測到數據有損壞的塊數，其樣本空間X={0,1,2,…,k}.由概率基礎知識得到：

(2)

1) 通信開銷

通信開銷主要產生在用戶將數據塊和簽名信息上傳到服務器中，還有可信第三方向云服務提供商發起的挑戰過程產生的通信開銷.其中數據文件產生的通信開銷約為1.5t×210(單位為b)；可信第三方向云服務提供商發起的挑戰過程產生的通信開銷約為lb 460+128t(單位為b).另外，文獻[12]的通信開銷為lb 460+256t+790(單位為b)，文獻[13]的通信開銷為lb 460+128t+160(單位為b).圖4顯示的是通信開銷隨著副本的數量變化情況.

圖4 通信開銷隨副本數量的變化情況

2) 計算開銷

假設數據副本數量t=1.本節方案CSP證明生成時間隨用戶數量k變化情況如圖5所示.同樣，當用戶數量k=1時,CSP證明生成時間隨副本數量t變化情況如圖6所示.

圖5 當用戶數量為1時CSP證明生成時間隨副本數量的變化情況

圖6 當副本數量為1時CSP證明生成時間隨用戶數量的變化情況

通過實驗可以看出，本文方案與其他多副本數據完整性驗證方案相比，計算開銷、存儲開銷和通信開銷都相對較小.

4 總 結

針對多副本數據完整性驗證方案計算和通信開銷較大的問題，本文提出了一種改進的多用戶多副本數據完整性批量審計方案，引入了可信任的第三方審計師TPA來支持公共審計，利用簽名技術和線性代數映射實現用戶數據的真實性驗證.最后，通過該方案性能分析表明，該方案具有較低的計算開銷和通信開銷.

[1]Wang C, Wang Q, Ren K, et al. Ensuring data storage security in cloud computing[C]Proc of the 17th Int Workshop on Quality of Service. Piscataway, NJ: IEEE, 2009: 1-9

[2]王一蕾, 吳英杰, 孫嵐. 隱私保護關系型數據發布的多維劃分動態規劃算法[J]. 南京大學學報: 自然科學版, 2013, 49(2): 258-267

[3]Lin L, Li Q, Kong L, et al. Tenant-oriented composite authentication tree for data integrity protection in SaaS[C]Proc of Int Conf on Web-Age Information Management. Berlin: Springer, 2014: 402-414

[4]Liu H, Zhang P, Liu J. Public data integrity verification for secure cloud storage[J]. Journal of Networks, 2013, 8(2): 373-380

[5]Li J, Wang Q, Wang C, et al. Fuzzy keyword search over encrypted data in cloud computing[C]Proc of Conf on Information Communications. Piscataway, NJ: IEEE, 2010: 441-445

[6]Ni J, Yu Y, Mu Y, et al. On the security of an efficient dynamic auditing protocol in cloud storage[J]. IEEE Trans on Parallel & Distributed Systems, 2013, 25(10): 2760-2761

[7]Liu C, Yang C, Zhang X, et al. External integrity verification for outsourced big data in cloud and IoT[J].

Future Generation Computer Systems, 2015, 49(C): 58-67

[8]Wang Q, Wang C, Li J, et al. Enabling public verifiability and data dynamics for storage security in cloud computing[C]Proc of European Conf on Research in Computer Security. Berlin: Springer, 2009: 355-370

[9]譚霜, 賈焰, 韓偉紅. 云存儲中的數據完整性證明研究及進展[J]. 計算機學報, 2015, 38(1): 164-177

[10]Ateniese G, Burns R, Curtmola R, et al. Provable data possession at untrusted stores[C]Proc of ACM Conf on Computer and Communications Security. New York: ACM, 2007: 598-609

[11]Curtmola R, Khan O, Burns R, et al. MR-PDP: Multiple-replica provable data possession[C]Proc of Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2008: 411-420

[12]Chen H F, Lin B G, Yang Y, et al. Public batch auditing for 2M-PDP based on BLS in cloud storage[J]. Journal of Cryptologic Research, 2014, 1(4): 368-378

[13]Zha Y X, Luo S S, Bian J C, et al. Multiuser and multiple-replica provable data possession scheme based on multi-branch authentication tree[J]. Journal on Communi-cations, 2015, 36(11): 80-91