一種支持動態(tài)更新的遠程數(shù)據(jù)完整性驗證方法*

趙文強

(武漢市武昌區(qū)長虹橋37-1號 武漢 430064)

?

一種支持動態(tài)更新的遠程數(shù)據(jù)完整性驗證方法*

趙文強

(武漢市武昌區(qū)長虹橋37-1號 武漢 430064)

論文針對云存儲中數(shù)據(jù)外包的特性,提出了一種支持數(shù)據(jù)動態(tài)更新的遠程數(shù)據(jù)完整性驗證方案,利用數(shù)據(jù)更新信息表支持數(shù)據(jù)的修改、插入、刪除等動態(tài)操作,在橢圓曲線上的雙線性配對算法的基礎(chǔ)上設(shè)計了一個遠程數(shù)據(jù)完整性驗證方案,并對方案的正確性和性能進行了分析,分析表明該文方案是可行的。

云存儲; 數(shù)據(jù)完整性; 數(shù)據(jù)動態(tài)更新

Class Number TP311

1 引言

云存儲[1]能夠向用戶提供以互聯(lián)網(wǎng)為載體的存儲服務(wù)平臺,使得存儲于其上的數(shù)據(jù)能以服務(wù)的形式按需為用戶所使用。但在云存儲模式下,數(shù)據(jù)外包存儲在云服務(wù)器中,超出了數(shù)據(jù)屬主的物理控制范圍,不可信的云服務(wù)提供商(Cloud Service Provider,CSP)有可能會惡意丟失或刪除部分用戶極少訪問的數(shù)據(jù)[2],以節(jié)省存儲空間;而且,為了維護其商業(yè)信譽,CSP極有可能向用戶隱瞞數(shù)據(jù)丟失或損壞的事實,使得用戶數(shù)據(jù)的完整性被破壞。解決該問題的一個簡單直接的方法就是定期地將所有數(shù)據(jù)下載到本地,檢查其完整性,但該方法會消耗大量的通信帶寬和本地存儲空間,導(dǎo)致云存儲的優(yōu)勢不復(fù)存在。因此,本文在云存儲模式下設(shè)計了一種遠程數(shù)據(jù)完整性[3]驗證方法,該方法能夠定期地檢查存儲于云服務(wù)器的數(shù)據(jù)的完整性,并且支持數(shù)據(jù)的安全動態(tài)更新[4]。

2 支持動態(tài)更新的遠程數(shù)據(jù)完整性驗證方案

2.1 數(shù)據(jù)更新信息表

為了支持數(shù)據(jù)的動態(tài)更新,如修改、插入、刪除等操作,本文為每個文件單獨設(shè)計了一張數(shù)據(jù)更新信息表(Data Update Information Table,DUIT)[5]來記錄每個數(shù)據(jù)塊的實時狀態(tài)。

DUIT的初始狀態(tài)如表1(a)所示。DUIT表的第一行為表頭,不包含任何實際數(shù)據(jù)信息。DUIT表共有四列,其中,Id(i)表示數(shù)據(jù)塊的實際物理索引,是本文ChalGen算法的數(shù)據(jù)塊的唯一標(biāo)識符;并且在插入或刪除操作中,索引i也會相應(yīng)地改變。BID是數(shù)據(jù)塊的實時邏輯索引,當(dāng)有插入操作時,BID值會重復(fù)。V是數(shù)據(jù)塊的版本號,初始值為0,主要用來記錄數(shù)據(jù)塊的修改和刪除操作。E被用來記錄插入和附加操作,初始值為0。擁有相同實時邏輯索引BID的數(shù)據(jù)塊如果沒有被修改,將通過值E來區(qū)分。數(shù)據(jù)擁有者為每個文件維護一張DUIT表以追蹤數(shù)據(jù)當(dāng)前的狀態(tài)并且檢查外包數(shù)據(jù)的完整性。

表1 數(shù)據(jù)更新信息表

2.2 數(shù)據(jù)完整性驗證方案

本文的遠程數(shù)據(jù)完整性驗證方案是基于橢圓曲線上的雙線性配對算法構(gòu)造的。因此,下面首先簡要介紹雙線性配對算法[6]。

假定橢圓曲線上的乘法循環(huán)群G1、G2和GT具有相同的階p、g1和g2分別是G1和G2的生成元,e是一個可計算的雙線性映射[7]e:G1×G2→GT,并且具有以下特性:對于任意的u∈G1、v∈G2和所有的a、b∈Zp,有1)可計算性:e(ua,vb)=e(u,v)ab,該特性也蘊含著對于任意u1、u2∈G1和v∈G2,e(u1u2,v)=e(u1,v)·e(u2,v)成立。2)非退化性:e(g1,g2)≠1。3)可計算性,即存在一個有效的算法能夠計算出e。

本文詳細的遠程數(shù)據(jù)完整性驗證方案如下所述。

2) 標(biāo)簽生成算法TagGen[9]:給定一個數(shù)據(jù)文件F=(m1,m2,…,mn),其中mi∈Zp,i=1,…,n,Owner運行該算法為每個數(shù)據(jù)塊mi計算一個標(biāo)簽σi=(H(wi)·umi)x∈G1,其中,函數(shù)H(·):{0,1}*→G1將字符串與G1中的點進行一一映射,wi=name‖BIDi‖Vi‖Ei,name∈Zp為Owner隨機選取的,并作為文件F的標(biāo)識符;BIDi為數(shù)據(jù)塊mi在文件F中的原始索引位置;Vi是mi的更新計數(shù)器,初始值為0;Ei記錄的是插入操作,對于數(shù)據(jù)塊mi,若其位置處沒有插入操作則Ei被置為0。每次當(dāng)數(shù)據(jù)塊mi處有插入操作發(fā)生時,Ei的值就會單調(diào)遞增,步長為1。將所有數(shù)據(jù)塊的標(biāo)簽集合表示為φ={σi}1≤i≤n。執(zhí)行完該算法后,Owner將文件F和驗證標(biāo)簽集合φ一起發(fā)送給CSP,并且在本地刪除數(shù)據(jù)以節(jié)省存儲空間。與此同時,Owner還會為每個文件F生成一個原始的數(shù)據(jù)更新信息表DUIT。

3) 質(zhì)詢生成算法ChalGen[10]:在每輪數(shù)據(jù)完整性審計過程中,Owner都從DUIT表的物理索引值中隨機地選取c個非空值I={s1,s2,…,sc}。為不失一般性,本文假定s1≤…≤sc,這可通過一個偽隨機排序算法實現(xiàn)。Owner首先為I={s1,s2,…,sc}中的每個si選擇一個隨機值vi∈Zp,然后將質(zhì)詢Chal={(i,vi)}i∈I發(fā)送給CSP。這些質(zhì)詢值指定了在該輪審計過程中被要求抽樣檢測的數(shù)據(jù)塊。

5) 示證驗證算法VerifyProof:Owner運行該算法以驗證CSP發(fā)送的示證的有效性。如果等式(1)成立,算法輸出1,表示所抽樣的數(shù)據(jù)塊是完整的;否則輸出0,表示數(shù)據(jù)的完整性被破壞了。

(1)

3 數(shù)據(jù)更新操作

本文用數(shù)據(jù)更新信息表DUIT來支持數(shù)據(jù)的動態(tài)更新操作,包括數(shù)據(jù)的修改操作Modification、刪除操作Deletion、插入操作Insertion,各種更新操作的詳細過程如下所示。

·修改操作Modification:本文主要用DUIT表中的版本號V來記錄數(shù)據(jù)的修改操作,每次當(dāng)數(shù)據(jù)塊被修改時,版本號V將單調(diào)地遞增,步長為1。

·刪除操作Deletion:本文以一種較簡單的方式處理數(shù)據(jù)塊的刪除操作,僅僅改變要被刪除數(shù)據(jù)塊的版本號V值,并修改其他數(shù)據(jù)塊的物理索引Id值。

·Deletion(i):當(dāng)要刪除數(shù)據(jù)塊mi時,將其物理索引Id值置為NULL,并將其版本號Vi置為-1。然后Owner將在mi之后的數(shù)據(jù)塊的物理索引Id值逐個更新,將從第i+1個數(shù)據(jù)塊開始的每個數(shù)據(jù)塊的Id值減1,也即j=j-1(j=i+1,…,n)。

·數(shù)據(jù)插入操作Insertion:本文將附加操作看作插入操作的一種特殊情況,即每次都在文件尾部插入數(shù)據(jù)。DUIT表中的E域被用來記錄插入/附加操作,并用來區(qū)分已有數(shù)據(jù)塊與新插入的數(shù)據(jù)塊。

4 方案分析

4.1 方案的正確性

將式(1)的左右兩邊進行代替變換即可驗證其正確性,如下所示。

4.2 性能分析

4.2.1 DUIT的時間復(fù)雜度分析

DUIT表可以被看作為一個有序數(shù)組,對DUIT的每個操作都可以等價為對一個有序數(shù)組的操作。對于數(shù)據(jù)塊mi的更新操作,首先需要定位mi的位置,可以通過二分查找法進行,其時間復(fù)雜度為O(logn)。對于數(shù)據(jù)修改操作,由于只需要更改版本號V的值,其時間復(fù)雜度為O(1)。因此,對于數(shù)據(jù)修改操作,其平均時間復(fù)雜度為O(logn)。數(shù)據(jù)的刪除操作需要更改mi的版本號V,并依此更新mi后續(xù)數(shù)據(jù)塊的物理索引Id,其時間復(fù)雜度為O(n)。故數(shù)據(jù)刪除操作的平均時間復(fù)雜度為O(n)。類似的,數(shù)據(jù)插入操作的平均時間復(fù)雜度也為O(n)。批量更新數(shù)據(jù)的情況與單個數(shù)據(jù)塊更新的時間復(fù)雜度相同。

4.2.2 DUIT的存儲開銷分析

在本文DUIT表的設(shè)計中,可以將Id域設(shè)置為占4個字節(jié),BID域占4個字節(jié),V域占10個比特,E域占10個比特,則一個表項占用84Bit。如果一個數(shù)據(jù)塊為4KB,則該表可以記錄的文件大小為16TB,一個數(shù)據(jù)塊可以修改1024次,在同一塊數(shù)據(jù)后面可以插入1024個新數(shù)據(jù)塊,可以滿足大部分應(yīng)用。對于1GB的文件,如果每個數(shù)據(jù)塊為4KB,則該文件的DUIT占用的額外存儲空間大約為2.5MB,可見本文設(shè)計的DUIT額外占用的存儲空間并不多。頻繁地更新操作會導(dǎo)致表項增多,DUIT占用的空間也會增加,但是增幅不大,如將1GB的文件通過插入操作變?yōu)?GB,DUIT占用的存儲空間只增加到5MB。而且,在云存儲模式下,存儲資源是相對充裕廉價的,而帶寬有時則成為用戶體驗的瓶頸。因此,消耗少量的存儲資源以節(jié)省帶寬資源是可行的。

5 結(jié)語

本文針對云存儲中數(shù)據(jù)外包的特性,提出了一種支持數(shù)據(jù)動態(tài)更新的遠程數(shù)據(jù)完整性驗證方案,利用數(shù)據(jù)更新信息表支持數(shù)據(jù)的動態(tài)操作,利用橢圓曲線上的雙線性配對算法設(shè)計了一個具體的遠程數(shù)據(jù)完整性驗證方案,并分析了方案的正確性和性能,分析表明本文方案是可行的。

[1] 武永衛(wèi),黃小猛.云存儲[J].中國計算機學(xué)會通訊,2009,5(6):44-52.

[2] C Gentry. A Fully Homomorphic Encryption Scheme[D]. Palo Alto, California: Stanford University,2009.

[3] Y Deswarte, J J Quisquater, A Saidane. Remote Integrity Checking: How to Trust Files Stored on Untrusted Servers[C]//Proceedings of International Federation for Information Processing Intergrity and Internal Control in Information Systems,2004:1-11.

[4] C Wang, Q Wang, K Ren, et al. Privacy-Preserving Public Auditing for Data Storage Security in Cloud Computing[C]//Proceedings of 2010 IEEE International Conference on Computer Communication,2010:1-9.

[5] B Wang, B Li, H Li. Public Auditing for Shared Data with Efficient User Revocation in the Cloud[C]//Proceedings of 2013 IEEE International Conference on Computer Communication,2013:2904-2912.

[6] G Ateniese, R Pietro, L Mancini, et al. Scalable and Efficient Provable Data Possession[C]//Proceedings of the 4th International Conference on Security and Privacy in Communication Netowrks, Article No.9,2008.

[7] Q Wang, C Wang, J Li, et al. Enabling Public Verifiability and Data Dynamic for Storage Security in Cloud Computing[C]//Proceedings of 14th European Symposium on Research in Computer Security,2009:355-370.

[8] REN Zhengwei, WANG Lina, WU Qianhong, et al. Data Dynamics Enabled Privacy-Preserving Public Batch Auditing in Cloud Storage[J]. Chinese Journal of Electronics,2014,23(2):297-301.

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

[10] 陳海波.公有云中的安全研究[J].中國計算機學(xué)會通訊,2012,8(7):15-21.

Remote Data Integrity Verification Scheme with Dynamics Updating

ZHAO Wenqiang

(No. 37-1 Changhong Crossroads, Wuchang District, Wuhan 430064)

On the basis of the issue of outsourced data, a remote data integrith verification scheme which supports data dynamics updating is proposed. A data updating information table is designed to support data transact, insert and delete. A remote data integrity verification scheme based on bilinear pairing algorithm of elliptic curve is proposed. The analysis of the correctrness of the scheme and performance shows that this scheme is feasible.

cloud storage, data integrity, data dynamics

2015年4月5日,

2015年5月31日

趙文強,男,碩士,研究方向:信號與信息處理。

TP311

10.3969/j.issn.1672-9730.2015.10.025