改进的基于同态哈希的云存储数据完整性验证方案

黄 石刘文卓曹天杰

(中国矿业大学计算机科学与技术学院,江苏徐州 221116)

改进的基于同态哈希的云存储数据完整性验证方案

黄 石,刘文卓,曹天杰

(中国矿业大学计算机科学与技术学院,江苏徐州 221116)

为了解决云存储用户数据完整性验证问题,在分析现有远程数据完整性校验方法的基础上,在标签生成的过程中加入同态哈希与伪随机数,提出一种支持动态数据与无限次挑战的同态哈希的数据完整性验证方案。通过安全性与性能的分析证明该方案的有效性,在保证远程数据完整性的同时,减少了存储空间的冗余和带宽消耗。

云存储;数据完整性;同态哈希;标签

1 数据完整性验证方案研究现状

远程数据验证允许客户端在一个不可信的服务器上检验外包数据的完整性。可恢复性证明POR(proof of retrievability)是Juels等[1]提出的完整性验证算法,其关键是将一些随机的数据块加入到存储的数据中,其插入的位置由伪随机序列决定,并使用了纠错码。这些数据块和数据本身没有任何关系,称之为“哨兵”,这些“哨兵”起到了 tag的作用,用于对数据进行完整性验证。数据持有性证明 PDP(provable data possession)是Ateniese等[2]提出的,其2个显著特点是能够支持公开验证,以及在方案中使用了同态签名算法[3],这样就能使第三方以较小的开销来验证文件是否被完整存储。肖达等[4]提出数据持有性验证(data possession checking)的基本思想是验证者随机指定文件中若干个位置的数据块和相应的密钥,服务器计算哈希值并返回给验证者,验证者再比较哈希值与校验快是否一致,从而判定数据是否被正确持有,这是国内第一篇研究数据持有性验证的文章。由Ateniese[5]等提出的SPDP(scalable provable data possession)方案与PDP算法的区别在于新增了对动态数据的支持,采用了提前约定tag数目的标签组织方式,将生成的tag用对称密钥加密后保存在服务器或本地,每次挑战时使用一个tag进行验证,但该方案也限定了验证次数。Erway等[6]提出的DPDP(dynamic provable data possession)算法是使用了一种与树结构类似的跳表(skiplist)结构来生成tag,相比SPDP算法而言首次提出了一个可以支持动态数据的完整性验证方案。Chen等[7]在DPDP算法的基础之上采用了RS码和柯西矩阵加强了原有算法的鲁棒性和动态更新的性能。除此以外还包括在私有云上的完整性验证方案IPDP和混合云上的完整性验证方案CPDP等[8]。

文献[9]针对上述一些算法中存在的问题提出了一种基于同态哈希的数据持有性证明方法,但该方法并不能防止服务器伪造与挑战块相对应的标签,从一定程度上说,无法很好地验证数据持有性。本文在文献[9]的基础上,结合文献[10]提出的同态哈希算法,提出一种支持动态数据和无限次挑战的基于同态哈希的数据完整性验证方案,在用户不用取回数据的前提下,很好地保证了远程数据的完整性并减少了存储空间的冗余与带宽消耗。

2 同态哈希

同态是抽象代数中2个代数结构之间保持结构不变的映射。例如设G,G′是两个群,f是G到G′的一个映射,若对任意的a,b∈G都有f(ab)=f(a)f(b),则f就称为G到G′的一个同态。

同态哈希(homomorphic hash)一直以来都被使用于对等网络中,通常与纠删码、网络编码一起抵抗攻击事件。在对等网络中,每个对等体会从其他的对等体那里直接获取原始数据块,因此可以用到SHA1这类哈希函数,通过比较所接收到的数据块的哈希值与原始哈希值来直接验证接收到的数据块的正确性。但1个对等体接收到的随机的编码包不能被源节点预先定义,因此标准的哈希函数在这里无法使用。但同态哈希函数却能使对等体发现伪造块的存在。

使用文献[10]中提出的同态哈希函数hG(·),hG(·)有一组哈希参数G=(p,q,g),其中参数描述见表1。g的每个元素可以被表示成x(p-1)/qmodp,其中x∈Zp且x≠1。

其中rand(·)是一个伪随机函数,作为一个伪随机数生成器来使用,用作初始化过程中同态哈希函数参数的生成、标签生成阶段随机数的生成以及挑战阶段确定随机抽取的用于挑战的数据块的选择,从而使挑战能够均匀覆盖所有的数据。

表1 参数描述Table1 Parameter description

对于一个块的bi,哈希值可以按照式(1)计算:

原始块(b1,b2,…,bn)的哈希值分别为h(b1),h(b2),…,h(bn)。

给出一个编码块ej和一个系数向量(cj,1,cj,2,…,cj,n),则同态哈希函数hG(·)满足下列等式:

这一特性就能够用来验证一个编码块的完整性。发布者首先需要预先计算每个数据块的同态哈希值,下载者下载这些同态哈希值,一旦收到了验证块就使用式(1)计算其哈希值,然后使用式(2)来验证该验证块的正确性。

3 基于同态哈希的远程数据完整性验证方案

3.1 方案描述

基于同态哈希的数据完整性验证方案的流程分为5个阶段,分别是初始化(Setup)、标签生成(TagBlock)、挑战阶段(Challenge)、证据生成(ProofGen)和证据验证(ProofVerify)阶段。

首先需要将文件分块存储,在后期的标签生成、证据验证等阶段都是以这些数据块为最小单位进行的。在初始化阶段,主要生成一系列初始化参数用作哈希函数的生成上。在标签生成阶段,客户端使用伪随机数生成器产生一系列伪随机数,然后将文件块与伪随机数相乘得到标签。客户端将文件块bi、tag以及p、q发送至服务器,客户端保存生成元g、G以及伪随机数生成器使用的种子seed。在挑战阶段,客户端使用伪随机数生成器生成k个随机的挑战块发给服务器。在证据生成阶段,服务器计算出数据块与标签相应的证据bc和tc,并将bc和tc返回客户端。在证据验证阶段,客户端用种子seed重新生成相应的伪随机数,验证服务器返回的tc是否是客户端指定的tc,同时验证了此tc是否对应正确的bc。

将文件F表示成一个m×n的矩阵,矩阵中的每个单元都是Zp中的元素。对m的选择保证每一个元素都小于2λq-1,因此小于q。

此时,F的第j列仅仅与文件F第j个消息块相关,写成bj=(b1,j,…,bm,j),因此对于2个文件块的加法运算只需要将相应的列向量直接相加来实现。也就是说,将文件的第i块和第j块相加,只需计算:

初始化阶段参数的生成使用文献[10]中的初始化算法,具体的算法实现见图1。

图1 基于同态哈希的数据完整性验证方案描述Fig.1 Description of data integrity verification method based on homomorphic hashing

3.2 对动态数据的支持

对动态数据的支持包括插入、删除2个基本操作。数据插入以数据块为最小单位进行操作,每次可以在不同的位置插入一个或多个数据块。假设需要插入的数据块为bs,客户端计算该数据块的标签,以及重新计算第m块以后的标签,再将更新以后的F′和tag′上传到服务器,然后立即发出一次对该数据块的验证以确保数据的上传过程是正确的。在进行数据块的删除操作时,首先确定需要删除的数据块,用bt表示,再用该文档对应的seed重新生成随机数序列,对删除位置之后的数据块重新取对应位置的随机数,计算标签,将删除的数据块的位置和更新后的标签传至服务器,删除服务器上相应的数据块,并计算更新该数据块之后的标签,具体过程如图2所示。

图2 支持动态数据的描述Fig.2 Description of supporting dynamic data

4 安全性与性能分析

4.1 安全性分析

探测概率Pdet是指客户端进行一次挑战验证过程中,服务器能够成功地对其中的一些数据块进行修改或删除的概率[5],可由式(3)描述:

式中:d——被损坏或删除的数据块;k——1次验证中包含的数据块数。若文档中的一些重要字节被删除或篡改了,可以使用纠错码处理这些微小变化,从而重新恢复原始文档,但纠错码对于含有大量数据块的文档是不适用的。

此方案中服务器端保存所有的数据本身、p、q、数据块及对应的标签。客户端保存生成标签使用的伪随机数种子seed,大素数p、q以及生成元g。该方案的安全性是基于可验证标签的,标签的构造使用了同态哈希算法和一系列伪随机数。

在challenge阶段,挑战者challenger随机生成k个挑战块发给A,A生成挑战块的完整性验证P,若P通过了验证,则认为A完成了一次成功的欺骗。

服务器接收到挑战brj后,在于分析一个概率多项式时间算法PPT(probabilistic ploynomial time)中是否能够在概率多项式时间内找到一对碰撞。若对于时间复杂度为τ(λ)的概率多项式时间敌手满足:

式中ε(λ)是一个足够小的数,则证明此算法是安全的。文献[11]给出了函数族hG是一个碰撞抵抗哈希函数的证明过程。

假设A删除了challenger挑战的数据块,从而将任意的数据块及其对应的标签返回给challenger。此时,虽然能够验证其返回的bc与标签tc是正确对应的,但由于 A不知道构造标签使用的随机数ri,因此challenger只需要将收到的数据块进行同态哈希后,用与生成标签相同的种子生成伪随机数后重新构造标签,并与A返回的标签进行比较,就能验证A返回的数据块与标签是否是challenger指定的。

4.2 性能分析

在生成标签时取数据块大小β为16 kB,同态哈希输出λp为1024 bit,因此此哈希函数将文件的存储空间减为原来的λp/β=1/128,粗略判断这种Tag的组织方式对减小存储冗余的效果十分明显。该方案在支持动态数据的同时,还能够支持无限多次的挑战,表2是几种方案的比较(其中DIVH是本文的方案)。其中t表示挑战次数,s表示每块中数据分片的个数,c表示CPDP方案中混合云服务器的个数。

从表2可以看出,本文的方案在时间复杂度上与PDP方案是相同的。在支持动态数据的同时,本文方案能够支持无限多次挑战,因为挑战块是用户随机生成的。每次选取不同的数据块,服务器也无法猜出生成元g的准确数值,与SPDP方案中只能事先约定挑战的次数生成token相比有很大的改进。但在添加和删除操作方面来讲,与SPDP方案类似,也需要对所有涉及相应数据块的token取回进行更新。

表2 方案比较Table2 Scheme comparison

5 结 语

在分析和总结前人方法的基础上,提出了一种基于同态哈希的数据完整性验证方案,并通过安全性与性能分析证明了此方案的可行性与有效性。在本文的基础之上,仍需进一步研究如何实现更少的冗余存储空间,如何使单次挑战覆盖更多的数据、更快的验证速度、占用更少的带宽以及对数据的可恢复性。

[1]JUELS A,KALISKI B S,POR S.Proof of rerievability for large files[C]//Proc of the 14th ACM Conf on Computer and Communications Security.New York:ACM,2007:584-597.

[2]ATENIESE G,BURNS R,CURTMOLA R,et al.Provable data possession at untrusted stores[C]//Proc of the 14th ACM Conf on Computer and Communications Security.New York:ACM,2007:598-609.

[3]JOHNSON R,MOLNAR D,SONG D,et al.Homomorphic signature schemes[C]//Proc of CT-RSA.New York:Springer,2002: 244-262.

[4]肖达,舒继武,陈康,等.一个网络归档存储中实用的数据持有性检查方案[J].计算机研究与发展,2009,46(10):1660-1668.(XIAO Da,SHU Jiwu,CHEN Kang,et al.A practical data possession checking scheme for networked archival storage[J].Journal of Computer Research and Development,2009,46(10):1660-1668.(in Chinese))

[5]ATENIESE G,DI P R,MANCINI L V,et al.Scalable and efficient provable data possession[C]//Proc of the 4th International Confon Security and Privacy in Communication Netowrks(SecureComm 2008).New York:ACM,2008:1-10.

[6]ERWAY C,KUPCU A,PAPAMANTHOU C,et al.Dynamic provable data possession[C]//Proc of the 16th ACM Conf on Computer and Communications Security(CCS 2009).New York:ACM,2009:213-222.

[7]CHEN B,CURTMOLA R.Robust dynamic provable data possession[C]//Distributed Computing Systems Workshops (ICDCSW),32nd International Conference on.Macau:IEEE,2012:515-525.

[8]ZHU Y,WANG H,HU Z,et al.Cooperative provable data possession[R]//Beijing:Peking University and Arizona University, 2010.

[9]陈兰香.一种基于同态hash的数据持有性验证方法[J].电子与信息学报,2011,33(9):2199-2204.(CHEN Lanxiang.A Homomorphic Hashing based provable data possession[J].Journal of Electronics&Information Technology:2011,33(9):2199-2204.(in Chinese))

[10]KROHN M,FREEDMAN M J,MAZIERES D.On-the-fly verification of rateless erasure codes for efficient content distribution [C]//Procof IEEE Symposium on Security and Privacy.Lee Badger:IEEE,2004:226-240.

[11]BELLARE M,GOLDREICH O,GOLDWASSER S.Incremental cryptography:the case of hashing and signing[C]//Advances in Cryptology-CRYPTO'94.Berlin:Springer Berlin Heidelberg,1994:216-233.

[12]HAO Zhuo,ZHONG Sheng,YU Nenghai.A privacy-preserving remote data integrity checking protocol with data dynamics and pubic verifiability[J].IEEE Transactions Oil Knowledge and Data Engineering,2011,23(9):1432-1437.

[13]WANG Qian,WANG Cong,REN Kui,et al.Enabling pubic auditability and data dynamics for storage security in cloud computing [J].Transactions on Paralel and Distributed Systems,2011,22(5):847-859.

[14]冯登国,张敏,张妍,等.云计算安全研究[J].软件学报,2011,22(1):71-83.(FENG Dengguo,ZHANG Min,ZHANG Yan,et al.Study on cloud computing security[J].Journal of Software,2011,22(1):71-83.(in Chinese))

[15]于洋洋,虞慧群,范贵生.一种云存储数据完整性验证方法[J].华东理工大学学报:自然科学版,2013,39(2):211-216.(YU Yangyang,YU Huiqun,FAN Guisheng.An approach to verifying the data integrity of cloud storage[J].Journal of East China University of Science and Technology:Natural Science Edition,2013,39(2):211-216.(in Chinese))

An improved method of data integrity verification based on homomorphic hashing in cloud storage

HUANG Shi,LIU Wenzhuo,CAO Tianjie
(School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,China)

Based on analysis of existing remote data integrity verification methods and using homomorphic hashing and pseudo-random numbers in the tag blocking stage,a data integrity verification method,supporting dynamic data and considering challenges to be unlimited,is proposed to deal with the problem of users'data integrity verification in cloud storage.The effectiveness of this method is verified through security and performance analyses.With a guarantee of maintaining the remote data integrity,the method can reduce the redundancy of storage space and the bandwidth consumption in data communication.

cloud storage;data integrity;homomorphic hashing;tag

TP302.7

:A

:1000-1980(2015)03-0278-05

10.3876/j.issn.1000-1980.2015.03.015

2014-11 12

黄石(1979—),男,安徽桐城人,讲师,博士研究生,主要从事信息安全、云存储安全研究。E-mail:huangshi@cumt.edu.cn