一種基于代數簽名的遠程數據完整性驗證方法

王惠清　洪志全

1(瀘州醫學院現代教育技術中心　四川 瀘州 646000)

2(成都理工大學信息科學技術學院　四川 成都 610059)

?

一種基于代數簽名的遠程數據完整性驗證方法

王惠清1洪志全2

1(瀘州醫學院現代教育技術中心四川 瀘州 646000)

2(成都理工大學信息科學技術學院四川 成都 610059)

摘要云存儲服務中，用戶將數據存儲在不可信的云儲存服務器上,用戶數據面臨安全考驗。針對這種情況，為了讓用戶可以驗證存儲在云存儲服務器上數據的完整性，提出一種基于代數簽名的遠程數據完整性驗證方法。首先運用代數簽名的特性，生成輕型的代數標簽進行數據驗證，同時引入一種新的數據結構(DT)來實現遠程數據的動態更新從而降低數據驗證的計算和通信開銷。最后給出該方法的正確性和安全性分析，以及性能分析。實驗結果表明，在大規模數據驗證時，該方法與其他方法相比具有更高的驗證效率、較小的計算和通信開銷。

關鍵詞云存儲代數簽名遠程數據驗證動態更新數據完整性

AN INTEGRITY VERIFICATION ALGORITHM FOR REMOTE DATA BASED ON ALGEBRAIC SIGNATURE

Wang Huiqing1Hong Zhiquan2

1(Modern Education Technology Center,Luzhou Medical College,Luzhou 646000,Sichuan,China)2(Institute of Information Science and Technolgy,Chengdu University of Technology,Chengdu 610059,Sichuan,China)

AbstractIn cloud storage service, users store their data on the untrusted cloud storage server, users data faces security test. In view of this, in order to allow users to verify the integrity of the data stored in cloud storage server, this paper proposes an algebraic signature-based remote data integrity verification method. The method uses the algebraic signature feature first, generates light algebra labels for data verification. At the same time it introduces a new data structure (DT) to realise dynamic remote data updating so as to reduce the overheads of calculation and communication of data verification. Finally, the correctness and safety analysis of the method are given, as well as the performance analysis. Experimental results show that in large-scale data verification, this method has higher efficiency, less computation and communication overhead compared with other method.

KeywordsCloud storageAlgebraic signatureRemote data verificationDynamic updateData integrity

0引言

云存儲服務中，服務提供商(CSP)是不可信的，為了謀取更大的利益，CSP可能將存儲在云服務器上的數據進行篡改和刪除，為了保護數據的安全和完整性，研究人員提出數據持有型證明(PDP)來檢測云存儲中的數據的正確性和完整性。數據完整性驗證研究主要集中在可恢復證明(POR)和數據持有型證明，其主要的區別是PDP支持檢測數據完整性，但無法保證數據可恢復性；POR可以確保存儲數據的可恢復性[1]。

在文獻[2,3]中，Ateniese等人正式定義了PDP方案，并使用基于RSA的模指運算構造同態標簽來實現持有性證明。但是由于RSA編碼的使用，PDP方案給服務器端帶來了極大的計算開銷和通信負載。文獻[3]中，Ateniese等人考慮到在文獻[2]中的靜態數據更新問題，提出了基于對稱密鑰的半動態數據更新的方法，然而在數據更新過程中，數據擁有者需要重新生成已保留的挑戰，這對于大文件不適用。文獻[4]中，Erway等人提出動態數據持有性證明方法，該方法主要實現了數據驗證的動態性，盡管該方案可以保證可變大小數據塊的完整性，但是并不能驗證獨立數據塊的完整性。文獻[5]中，Juels等提出可恢復證明方案,該方案可保證數據的完整性和可恢復性。但是該方案在數據更新時，由于錯誤恢復和數據加密，會給客戶端帶來高額的計算負載。文獻[6,7]中，Waters利用BLS簽名提出一個支持公開審計的POR方案，但該方案可泄露客戶隱私信息并且不支持數據的動態更新。文獻[8-12]中，Wang等人提出云計算下的數據完整性公共審計方案。該方案利用梅克爾散列樹(MHT)解決了數據動態化的問題，并實現了審計批處理操作，使得TPA能夠同時處理來自多個不同用戶的審計請求。可是不足的是該方案泄漏數據內容給審計者，并且會給審計者帶來嚴重的計算負載。文獻[13,14]中，Yang等克服了在文獻[11]中的隱私問題，實現了一個基于雙線性對的數據完整性驗證方案，該方案引入一種新的數據結構來支持動態數據更新。然而，隨著數據塊數的增加，會給審計者帶來嚴重的計算負載和通信開銷。

綜合考慮以上方案，本文提出一種基于代數簽名的遠程數據完整性驗證方法，該方案允許用戶檢測在云存儲中的數據持有性，引入一種數據結構表來支持數據的動態更新，擴展了本文所提出的數據完整性驗證方案，并且極大地減小了服務端和客戶端的計算負載和通信負載。最后通過與其他文獻方法的對比分析，實驗結果證明該方法具有高效性、可行性。

1系統模型

圖1　系統模型

本文案的云存儲服務架構如圖1所示，這個架構由用戶(Client)、數據管理員(DA)、云存儲服務器CSS(cloud storage server)和第三方審計者TPA(Third Party Auditor)4個部分構成。其中用戶擁有大量的數據需要存儲在云服務器。數據管理員(DA)對于存儲在云服務器中的數據進行動態更新操作，如修改、刪除和插入。云存儲服務器(CSS)由云服務提供商管理，擁有龐大的存儲和計算資源。備份用戶數據和生產一個挑戰的證明。本文中的TPA可認為是可靠且獨立的，并沒有與云存儲服務商或用戶勾結的動機。

2云存儲數據完整性檢測方法

2.1數據完整性檢測算法

代數簽名是一個具有同態性和代數性的哈希函數。代數簽名方法的基本特性是指數據塊代數簽名的和與所對應得數據塊和的代數簽名結果一致[15]。設λ是有限域中的一個元組，是由不同的非零元素λ=(λ1,λ2,…,λn)組成的一個向量。文件F化分成n數據塊f[1],f[2],…,f[n]，計算文件F的代數簽名公式為：

(1)

其代數簽名的性質如下：

性質1長度為r的數據塊b[1]和b[2]相連接的代數簽名計算公式為：

Sλ(f[i]‖f[j])=Sλ(f[i])⊕rySλ(f[j])

(2)

性質2文件F的所有數據塊的總和的代數簽名與每個數據塊代數簽名的總和相等。

Sλ(f[1])+Sλ(f[2])+…+Sλ(f[n])

=Sλ(f[1]+f[2]+…+f[n])

(3)

性質3兩個文件F,G的總和的代數簽名與每個文件簽名的總和相等。

Sλ(F+G)=Sλ(F)+Sλ(G)

(4)

數據完整性證明是一種幫助用戶驗證不可信存儲運營商是否正確地持有其數據的有效手段，一般由三方組成用戶(Client)、云存儲服務器CSS(cloud storage server)和可信第三方(TPA)。本文中引入了數據管理員(DA)作為對外包數據的管理。在該數據完整性檢測方法中，假設文件F包含n數據塊并且每個數據塊被劃分成r子數據塊，如果最后的數據塊有較少的字塊，通過設置fl,j=0forj≤r來增加數據塊的大小。本檢測方法由以下幾個步驟。

Ti=Sλ(f[i]‖(IDF‖i‖LDi‖Vi))

(5)

3) 證據生成階段：CSP收到挑戰信息后，依據收到的挑戰信息和對應的標簽信息，利用式(6)計算數據塊σ的線性組合和聚集認證標簽μ，然后將P=(σ,μ)作為組成數據驗證證據信息。

(6)

然后CSP將證據P=(σ,μ)返回給DA。

4) 在接收到證據后，DA運用塊標簽的代數簽名以及公鑰pk，以及下面的公式對文件塊進行正確性驗證，如果等式成立，則數據完整性未受到破壞。否則，數據塊遭到破壞。

(7)

2.2算法正確性和安全性

DA從云服務器獲得證據信息后，驗證這些證據信息以確保存儲的遠程數據的正確性及完整性。運用代數標簽的性質計算如下：

=Sλ(f[cs1]+…+f[csc])

=Sλ(f[cs1])+…+Sλ(f[csc])

=μ

可見，Sλ(σ)=μ，即數據完整性得到證明。

代數簽名在使用中，碰撞概率是非常低的，甚至可以忽略不計。一個256 B的簽名僅有2-256的可能性發生碰撞，這對于一個未持有任何秘密信息的攻擊者來說，構造簽名碰撞是非常困難的。挑戰中選取的數據塊數量可根據用戶的要求進行改變，這樣可以防止云存儲服務器對固定的挑戰塊c預先計算并存儲所有可能的校驗標簽值。所以代數簽名技術對于驗證遠程數據的正確性是非常有用的。

2.3數據動態更新

為了支持動態數據更新，這里引進一種稱作Data Table(DT)的數據結構。DT數據表可以防止存儲服務器使用之前版本存儲的數據而不是更新過的數據導致數據通過惡意攻擊，造成存儲的數據受到破壞。DT數據表由兩部分組成，邏輯塊LDi和版本號Vi。LDi表示數據塊的原始索引，Vi表示當前數據塊的版本號。如果有一數據塊被更新，則表DT中的版本號Vi必需自加1。同時，在DT表中的每個數據塊的索引也表示遠程數據塊的物理位置。

數據管理員(DA)負責創建數據表DT，并且在數據更新期間管理DT數據表。下面具體介紹動態數據操作：修改、插入和刪除。

1) 數據修改：假設DA想要修改文件F中第i塊f[i]為f′[i]。則DA執行的修改算法如下：

(1) 找到請求數據塊所在的特定數據表DT，然后更新版本號Vi=Vi+1；

(2) 為所修改的數據塊生成新的塊標簽，如下：

(8)

圖2　數據的修改

2) 數據插入：DA需要在f[i]后插入一新數據塊f*[i]，插入新數據塊的算法如下：

(1) 在DT數據表中依據range范圍找到文件F的第i塊數據塊f[i]。

(3) DA修改表項的最大、最小范圍，即range的取值。

(9)

圖3　數據的插入

圖4　刪除數據塊

3方案性能分析

本部分主要是評估本文所提的遠程數據驗證方法的性能，首先分析本方法對遠程數據篡改檢測的概率。其次，對比分析本方法與近期在文獻[11]和文獻[14]所提出的方法在數據更新操作過程中的計算負載和通信負載。

3.1數據篡改檢測的概率分析

本方法中的遠程數據驗證是基于隨機抽樣策略來降低服務器工作負載。這里分析方法中的數據篡改檢測的概率是基于塊抽樣。假設CSP修改了遠程數據塊n中的m塊，那么，篡改塊的概率相當于pm=m/n。設c為挑戰塊數，r為基本塊數，x為隨機變量用來表示選擇的塊數與CSP修改的塊數相比。命名為px(x≥1)，計算如下：

px(x≥1)=1-px(x=0)

則計算得到數據篡改檢測的概率范圍為：

圖5　挑戰塊c與破壞塊m之間的關系

假設DA把1 GB文件劃分為125 000數據塊，每個數據塊為8 KB，外包給云存儲服務器。圖5顯示在數據篡改檢測概率在px={0.8,0.9,0.99,0.99999}集合下，挑戰塊c與損壞塊數m(篡改塊數占總塊數的比例)之間的關系，例如，如果服務器修改遠程數據塊的10%，那么DA需要隨機選取98塊數據作為挑戰塊才能實現px至少為0.99999。很顯然，隨著損壞塊數的增加，在檢測概率一定的情況下，所需要的挑戰塊數達到最小。

3.2計算復雜度的對比分析

表1　計算復雜度的對比分析

4實驗結果

為了檢測本文所提架構的可用性，本文利用Eucalyptus技術搭建小型云平臺，使用兩臺計算機和三臺惠普服務器分別作為客戶端、數據管理員、可信第三方服務器和兩臺云服務器。首先配置Eucalyptus和云平臺的核心組件，配置了統一的網絡通信時間；然后配置云服務器與客戶端的SSH服務和監聽服務；以及配置了MIRACL庫；最后，根據本文提出的云存儲數據完整性驗證方法進行以下實驗。

圖6　對比分析更新不同數據塊的計算開銷

實驗一對比分析文獻[14]和文獻[11]所提出的最新遠程數據完整性驗證方法，計算數據在插入、刪除和修改的操作中的復雜度計算。對一個大小為1 GB的外包文件F進行數據更新實驗，文件F包含125 000個數據塊，圖6顯示了本文所提出的數據更新方案的高效性，這里更新(插入、刪除)的數據塊數從100到1000遞增，之間的間隔為100。文獻[14]的方案，插入或是刪除一個數據塊需要在MHT樹中尋找到第i塊的位置，同時每次都需要重新計算根節點的哈希表帶來了極大的計算負載。文獻[11]的方案尋找文件第i塊的位置，需要預先移動n-i數據塊作為插入或刪除操作，同時需要重復操作至少100次，極大地加重了驗證服務器的計算負載。本文所提方案可以在客戶端極大地降低計算負載。圖6顯示了在更新不同的數據塊所花費的計算開銷，結果顯示本文所提方案是非常高效的。

圖7　對比分析不同大小文件塊的計算開銷

實驗二對比分析不同文件塊大小對計算負載的影響，圖7顯示的是文件塊的大小對計算負載的影響，這里DA通過從1~10 GB文件中隨機插入或刪除100個數據塊來更新不同大小的外包數據。文獻[14]中的計算負載隨著文件塊大小的增長，從0.8到大約2.3快速的增長。文獻[11]的方案中，當文件的大小從1到10 GB增長時(文件中的數據塊大小都是8KB)，數據塊的數量也隨著增加。因此，驗證服務器為了進行數據更新需要移動大量的數據塊。正如在圖7中所示，本文的方案由于使用10個DTs而不是1個，帶來了極小的計算負載。所以，本文方法能夠應用在大規模的動態數據驗證。

實驗三對于同一個文件F，選擇不同的文件塊大小，對完整性檢測計算實驗開銷，選擇200 MB的文件，依次選取4、8、16、32、64、128 KB，每次選取560塊，然后記錄每次實驗所花費的時間和通信開銷。實驗結果如表2所示。

表2　完整性檢測的計算開銷

續表2

實驗結果顯示，在進行數據完整性檢測時，文件塊的大小對檢測計算開銷沒有什么影響，各個階段的計算時間基本保持穩定，檢測請求階段計算時間約為0.76 s，驗證信息生成階段計算時間約為1.08 s，完整性驗證階段計算時間約為1.65 s，對于一個200 MB的文件整個檢測過程大概需要3.49 s左右，計算時間總體較小，符合預期的目標。實驗環境穩定的情況下，每次實驗的通信開銷穩定在60 KB左右，通信開銷較小，符合預期設計的目標。

5結語

本文提出了一種有效的遠程數據驗證方法來確保存儲在云服務器上的數據安全。該方法運用代數簽名的性質驗證遠程數據的完整性，可以極大地減少數據驗證的計算開銷。同時引入了一個稱為Data Table的數據結構表，用來支持數據的動態更新，包括插入、修改和刪除操作。然后分析該方案的正確性和安全性，最后與其他文獻中的方法進行對比分析，實驗證明該方法的可行性和高效性。下一步將在此基礎上在DT表中尋找最佳的劃分子塊數來擴展該方案。同時也希望本方案能夠運用在分布式云存儲服務上。

參考文獻

[1] 陳蘭香.一種基于同態Hash的數據持有性證明方法[J].電子與信息學,2011,33(9):2200-2204.

[2] Ateniese G,Berns R,Curtmola R,et al.Provable Data Possession at Untrusted Stores[C]//Proc of the 14thACM Conference on Computer and Communications Security.New York:ACM,2007:598-609.

[3] Ateniese G,Pietro R D,Mancini L V,et al.Scalable and Efficient Provable Data Possessin[C]//Proc of the 4thInternational Conference on Security and Privacy in Communication Netowrks Istanbul.Turkey:ACM,2008:1-10.

[4] Erway C,Papamanthou C,Tamassia R,et al.Dynamic Provable Data Possession[C]//Proc of the 16thACM Conferenceon Computer andCommunications Security.Chicago,Illinois,USA:ACM,2009:213-222.

[5] Juels A,Burton S,Kaliski J.Proofs of Retrievability for Large Files[C]//Proc of the 14thACM Conference on Computer and Communications Security.Alexandria,Virginia,USA:ACM,2007:584-597.

[6] Shacham H,Waters B.Compact Proofs of Retrievability[C]//Advancesin Cryptology(ASIACRYPT):Springer Berlin Heidelberg,2008:90-107.

[7] 馮登國,張敏,張妍,等.云計算安全研究[J].軟件學報,2011(22):71-83.

[8] Zhang Y,Blanton M.Efficient Dynamic Provable Possession of Remote Data via Update Trees[J].IACR Cryptology ePrint Arc hive,2012,28(3):291-291.

[9] Wang C,Ren K,Lou W,et al.Toward Publicly Auditable Secure Cloud Data Storage Services[J].IEEE Network,2011,24:19-24.

[10] Zhou H,Sheng Z,Nenghai Y.A Privacy Preserving Remote Data Integrity Checking Protocol with Data Dynamics and Public Verifiability[J].IEEE Transactionson Knowledge and Data Engineering,2011,23(9):1432-1437.

[11] Wang Q A,Wang C,Ren K,et al.Enabling Public Auditability and Data Dynamics for Storage Security in Cloud Computing[J].IEEE T Parall Distr,2011,22:847-859.

[12] Wang C,Wang Q,Ren K,et al.Toward Secure and Dependable Storage Services in Cloud Computing[J].IEEE Transactions on Services Computing,2012,5:220-232.

[13] 于洋洋,虞慧群,范貴生.一種云存儲數據完整性驗證方法[J].華東理工大學學報:自然科學版,2013(39):211-216.

[14] Yang K,Jia X.An Efficient and Secure Dynamic Auditing Protocol for Data Storage in Cloud Computing[J].IEEE T Parall Distr,2012,30:1717-1726.

[15] Schwarz T S J,Miller E L.Using Al Gebraic Signatures to Check Remotely AdminIsteredStorage[C]//the 26thIEEE International Conference on Distributed Computing Systems,2006:12-12.

中圖分類號TP309.2

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.070

收稿日期：2014-06-27。國家自然科學基金青年科學基金項目(51308465)；四川省教育廳項目(08ZC055)。王惠清，碩士，主研領域：計算機網絡，云計算，分布式系統。洪志全，教授。