一種基于代數(shù)簽名的遠程數(shù)據(jù)完整性驗證方法

王惠清　洪志全

1(瀘州醫(yī)學(xué)院現(xiàn)代教育技術(shù)中心　四川 瀘州 646000)

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

?

一種基于代數(shù)簽名的遠程數(shù)據(jù)完整性驗證方法

王惠清1洪志全2

1(瀘州醫(yī)學(xué)院現(xiàn)代教育技術(shù)中心四川 瀘州 646000)

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

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

關(guān)鍵詞云存儲代數(shù)簽名遠程數(shù)據(jù)驗證動態(tài)更新數(shù)據(jù)完整性

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引言

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

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

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

1系統(tǒng)模型

圖1　系統(tǒng)模型

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

2云存儲數(shù)據(jù)完整性檢測方法

2.1數(shù)據(jù)完整性檢測算法

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

(1)

其代數(shù)簽名的性質(zhì)如下：

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

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

(2)

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

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

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

(3)

性質(zhì)3兩個文件F,G的總和的代數(shù)簽名與每個文件簽名的總和相等。

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

(4)

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

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

(5)

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

(6)

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

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

(7)

2.2算法正確性和安全性

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

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

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

=μ

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

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

2.3數(shù)據(jù)動態(tài)更新

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

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

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

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

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

(8)

圖2　數(shù)據(jù)的修改

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

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

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

(9)

圖3　數(shù)據(jù)的插入

圖4　刪除數(shù)據(jù)塊

3方案性能分析

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

3.1數(shù)據(jù)篡改檢測的概率分析

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

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

則計算得到數(shù)據(jù)篡改檢測的概率范圍為：

圖5　挑戰(zhàn)塊c與破壞塊m之間的關(guān)系

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

3.2計算復(fù)雜度的對比分析

表1　計算復(fù)雜度的對比分析

4實驗結(jié)果

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

圖6　對比分析更新不同數(shù)據(jù)塊的計算開銷

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

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

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

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

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

續(xù)表2

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

5結(jié)語

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

參考文獻

[1] 陳蘭香.一種基于同態(tài)Hash的數(shù)據(jù)持有性證明方法[J].電子與信息學(xué),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].軟件學(xué)報,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] 于洋洋,虞慧群,范貴生.一種云存儲數(shù)據(jù)完整性驗證方法[J].華東理工大學(xué)學(xué)報:自然科學(xué)版,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。國家自然科學(xué)基金青年科學(xué)基金項目(51308465)；四川省教育廳項目(08ZC055)。王惠清，碩士，主研領(lǐng)域：計算機網(wǎng)絡(luò)，云計算，分布式系統(tǒng)。洪志全，教授。