一種支持動態更新的遠程數據完整性驗證方法*

趙文強

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

?

一種支持動態更新的遠程數據完整性驗證方法*

趙文強

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

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

云存儲; 數據完整性; 數據動態更新

Class Number TP311

1 引言

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

2 支持動態更新的遠程數據完整性驗證方案

2.1 數據更新信息表

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

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

表1 數據更新信息表

2.2 數據完整性驗證方案

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

假定橢圓曲線上的乘法循環群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。

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

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

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

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

(1)

3 數據更新操作

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

·修改操作Modification:本文主要用DUIT表中的版本號V來記錄數據的修改操作,每次當數據塊被修改時,版本號V將單調地遞增,步長為1。

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

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

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

4 方案分析

4.1 方案的正確性

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

4.2 性能分析

4.2.1 DUIT的時間復雜度分析

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

4.2.2 DUIT的存儲開銷分析

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

5 結語

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

[1] 武永衛,黃小猛.云存儲[J].中國計算機學會通訊,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].軟件學報,2011,22(1):71-83.

[10] 陳海波.公有云中的安全研究[J].中國計算機學會通訊,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