趙文強(qiáng)

(武漢市武昌區(qū)長(zhǎng)虹橋37-1號(hào) 武漢 430064)

?

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

趙文強(qiáng)

(武漢市武昌區(qū)長(zhǎng)虹橋37-1號(hào) 武漢 430064)

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

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

Class Number TP311

1 引言

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

2 支持動(dòng)態(tài)更新的遠(yuǎn)程數(shù)據(jù)完整性驗(yàn)證方案

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

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

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

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

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

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

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

本文詳細(xì)的遠(yuǎn)程數(shù)據(jù)完整性驗(yàn)證方案如下所述。

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

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

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

(1)

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

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

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

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

·Deletion(i):當(dāng)要?jiǎng)h除數(shù)據(jù)塊mi時(shí),將其物理索引Id值置為NULL,并將其版本號(hào)Vi置為-1。然后Owner將在mi之后的數(shù)據(jù)塊的物理索引Id值逐個(gè)更新,將從第i+1個(gè)數(shù)據(jù)塊開始的每個(gè)數(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)的左右兩邊進(jìn)行代替變換即可驗(yàn)證其正確性,如下所示。

4.2 性能分析

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

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

4.2.2 DUIT的存儲(chǔ)開銷分析

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

5 結(jié)語

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

[1] 武永衛(wèi),黃小猛.云存儲(chǔ)[J].中國計(jì)算機(jī)學(xué)會(huì)通訊,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ì)算安全研究[J].軟件學(xué)報(bào),2011,22(1):71-83.

[10] 陳海波.公有云中的安全研究[J].中國計(jì)算機(jī)學(xué)會(huì)通訊,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日

趙文強(qiáng),男,碩士,研究方向:信號(hào)與信息處理。

TP311

10.3969/j.issn.1672-9730.2015.10.025