一种基于代数签名的远程数据完整性验证方法

王惠清　洪志全

1(泸州医学院现代教育技术中心　四川 泸州 646000)

2(成都理工大学信息科学技术学院　四川 成都 610059)



一种基于代数签名的远程数据完整性验证方法

王惠清1洪志全2

1(泸州医学院现代教育技术中心四川 泸州 646000)

2(成都理工大学信息科学技术学院四川 成都 610059)

摘要云存储服务中，用户将数据存储在不可信的云储存服务器上,用户数据面临安全考验。针对这种情况，为了让用户可以验证存储在云存储服务器上数据的完整性，提出一种基于代数签名的远程数据完整性验证方法。首先运用代数签名的特性，生成轻型的代数标签进行数据验证，同时引入一种新的数据结构(DT)来实现远程数据的动态更新从而降低数据验证的计算和通信开销。最后给出该方法的正确性和安全性分析，以及性能分析。实验结果表明，在大规模数据验证时，该方法与其他方法相比具有更高的验证效率、较小的计算和通信开销。

关键词云存储代数签名远程数据验证动态更新数据完整性

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

云存储服务中，服务提供商(CSP)是不可信的，为了谋取更大的利益，CSP可能将存储在云服务器上的数据进行篡改和删除，为了保护数据的安全和完整性，研究人员提出数据持有型证明(PDP)来检测云存储中的数据的正确性和完整性。数据完整性验证研究主要集中在可恢复证明(POR)和数据持有型证明，其主要的区别是PDP支持检测数据完整性，但无法保证数据可恢复性；POR可以确保存储数据的可恢复性[1]。

在文献[2,3]中，Ateniese等人正式定义了PDP方案，并使用基于RSA的模指运算构造同态标签来实现持有性证明。但是由于RSA编码的使用，PDP方案给服务器端带来了极大的计算开销和通信负载。文献[3]中，Ateniese等人考虑到在文献[2]中的静态数据更新问题，提出了基于对称密钥的半动态数据更新的方法，然而在数据更新过程中，数据拥有者需要重新生成已保留的挑战，这对于大文件不适用。文献[4]中，Erway等人提出动态数据持有性证明方法，该方法主要实现了数据验证的动态性，尽管该方案可以保证可变大小数据块的完整性，但是并不能验证独立数据块的完整性。文献[5]中，Juels等提出可恢复证明方案,该方案可保证数据的完整性和可恢复性。但是该方案在数据更新时，由于错误恢复和数据加密，会给客户端带来高额的计算负载。文献[6,7]中，Waters利用BLS签名提出一个支持公开审计的POR方案，但该方案可泄露客户隐私信息并且不支持数据的动态更新。文献[8-12]中，Wang等人提出云计算下的数据完整性公共审计方案。该方案利用梅克尔散列树(MHT)解决了数据动态化的问题，并实现了审计批处理操作，使得TPA能够同时处理来自多个不同用户的审计请求。可是不足的是该方案泄漏数据内容给审计者，并且会给审计者带来严重的计算负载。文献[13,14]中，Yang等克服了在文献[11]中的隐私问题，实现了一个基于双线性对的数据完整性验证方案，该方案引入一种新的数据结构来支持动态数据更新。然而，随着数据块数的增加，会给审计者带来严重的计算负载和通信开销。

综合考虑以上方案，本文提出一种基于代数签名的远程数据完整性验证方法，该方案允许用户检测在云存储中的数据持有性，引入一种数据结构表来支持数据的动态更新，扩展了本文所提出的数据完整性验证方案，并且极大地减小了服务端和客户端的计算负载和通信负载。最后通过与其他文献方法的对比分析，实验结果证明该方法具有高效性、可行性。

1系统模型

图1　系统模型

本文案的云存储服务架构如图1所示，这个架构由用户(Client)、数据管理员(DA)、云存储服务器CSS(cloud storage server)和第三方审计者TPA(Third Party Auditor)4个部分构成。其中用户拥有大量的数据需要存储在云服务器。数据管理员(DA)对于存储在云服务器中的数据进行动态更新操作，如修改、删除和插入。云存储服务器(CSS)由云服务提供商管理，拥有庞大的存储和计算资源。备份用户数据和生产一个挑战的证明。本文中的TPA可认为是可靠且独立的，并没有与云存储服务商或用户勾结的动机。

2云存储数据完整性检测方法

2.1数据完整性检测算法

代数签名是一个具有同态性和代数性的哈希函数。代数签名方法的基本特性是指数据块代数签名的和与所对应得数据块和的代数签名结果一致[15]。设λ是有限域中的一个元组，是由不同的非零元素λ=(λ1,λ2,…,λn)组成的一个向量。文件F化分成n数据块f[1],f[2],…,f[n]，计算文件F的代数签名公式为：

(1)

其代数签名的性质如下：

性质1长度为r的数据块b[1]和b[2]相连接的代数签名计算公式为：

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

(2)

性质2文件F的所有数据块的总和的代数签名与每个数据块代数签名的总和相等。

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

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

(3)

性质3两个文件F,G的总和的代数签名与每个文件签名的总和相等。

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

(4)

数据完整性证明是一种帮助用户验证不可信存储运营商是否正确地持有其数据的有效手段，一般由三方组成用户(Client)、云存储服务器CSS(cloud storage server)和可信第三方(TPA)。本文中引入了数据管理员(DA)作为对外包数据的管理。在该数据完整性检测方法中，假设文件F包含n数据块并且每个数据块被划分成r子数据块，如果最后的数据块有较少的字块，通过设置fl,j=0forj≤r来增加数据块的大小。本检测方法由以下几个步骤。

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

(5)

3) 证据生成阶段：CSP收到挑战信息后，依据收到的挑战信息和对应的标签信息，利用式(6)计算数据块σ的线性组合和聚集认证标签μ，然后将P=(σ,μ)作为组成数据验证证据信息。

(6)

然后CSP将证据P=(σ,μ)返回给DA。

4) 在接收到证据后，DA运用块标签的代数签名以及公钥pk，以及下面的公式对文件块进行正确性验证，如果等式成立，则数据完整性未受到破坏。否则，数据块遭到破坏。

(7)

2.2算法正确性和安全性

DA从云服务器获得证据信息后，验证这些证据信息以确保存储的远程数据的正确性及完整性。运用代数标签的性质计算如下：

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

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

=μ

可见，Sλ(σ)=μ，即数据完整性得到证明。

代数签名在使用中，碰撞概率是非常低的，甚至可以忽略不计。一个256 B的签名仅有2-256的可能性发生碰撞，这对于一个未持有任何秘密信息的攻击者来说，构造签名碰撞是非常困难的。挑战中选取的数据块数量可根据用户的要求进行改变，这样可以防止云存储服务器对固定的挑战块c预先计算并存储所有可能的校验标签值。所以代数签名技术对于验证远程数据的正确性是非常有用的。

2.3数据动态更新

为了支持动态数据更新，这里引进一种称作Data Table(DT)的数据结构。DT数据表可以防止存储服务器使用之前版本存储的数据而不是更新过的数据导致数据通过恶意攻击，造成存储的数据受到破坏。DT数据表由两部分组成，逻辑块LDi和版本号Vi。LDi表示数据块的原始索引，Vi表示当前数据块的版本号。如果有一数据块被更新，则表DT中的版本号Vi必需自加1。同时，在DT表中的每个数据块的索引也表示远程数据块的物理位置。

数据管理员(DA)负责创建数据表DT，并且在数据更新期间管理DT数据表。下面具体介绍动态数据操作：修改、插入和删除。

1) 数据修改：假设DA想要修改文件F中第i块f[i]为f′[i]。则DA执行的修改算法如下：

(1) 找到请求数据块所在的特定数据表DT，然后更新版本号Vi=Vi+1；

(2) 为所修改的数据块生成新的块标签，如下：

(8)

图2　数据的修改

2) 数据插入：DA需要在f[i]后插入一新数据块f*[i]，插入新数据块的算法如下：

(1) 在DT数据表中依据range范围找到文件F的第i块数据块f[i]。

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

(9)

图3　数据的插入

图4　删除数据块

3方案性能分析

本部分主要是评估本文所提的远程数据验证方法的性能，首先分析本方法对远程数据篡改检测的概率。其次，对比分析本方法与近期在文献[11]和文献[14]所提出的方法在数据更新操作过程中的计算负载和通信负载。

3.1数据篡改检测的概率分析

本方法中的远程数据验证是基于随机抽样策略来降低服务器工作负载。这里分析方法中的数据篡改检测的概率是基于块抽样。假设CSP修改了远程数据块n中的m块，那么，篡改块的概率相当于pm=m/n。设c为挑战块数，r为基本块数，x为随机变量用来表示选择的块数与CSP修改的块数相比。命名为px(x≥1)，计算如下：

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

则计算得到数据篡改检测的概率范围为：

图5　挑战块c与破坏块m之间的关系

假设DA把1 GB文件划分为125 000数据块，每个数据块为8 KB，外包给云存储服务器。图5显示在数据篡改检测概率在px={0.8,0.9,0.99,0.99999}集合下，挑战块c与损坏块数m(篡改块数占总块数的比例)之间的关系，例如，如果服务器修改远程数据块的10%，那么DA需要随机选取98块数据作为挑战块才能实现px至少为0.99999。很显然，随着损坏块数的增加，在检测概率一定的情况下，所需要的挑战块数达到最小。

3.2计算复杂度的对比分析

表1　计算复杂度的对比分析

4实验结果

为了检测本文所提架构的可用性，本文利用Eucalyptus技术搭建小型云平台，使用两台计算机和三台惠普服务器分别作为客户端、数据管理员、可信第三方服务器和两台云服务器。首先配置Eucalyptus和云平台的核心组件，配置了统一的网络通信时间；然后配置云服务器与客户端的SSH服务和监听服务；以及配置了MIRACL库；最后，根据本文提出的云存储数据完整性验证方法进行以下实验。

图6　对比分析更新不同数据块的计算开销

实验一对比分析文献[14]和文献[11]所提出的最新远程数据完整性验证方法，计算数据在插入、删除和修改的操作中的复杂度计算。对一个大小为1 GB的外包文件F进行数据更新实验，文件F包含125 000个数据块，图6显示了本文所提出的数据更新方案的高效性，这里更新(插入、删除)的数据块数从100到1000递增，之间的间隔为100。文献[14]的方案，插入或是删除一个数据块需要在MHT树中寻找到第i块的位置，同时每次都需要重新计算根节点的哈希表带来了极大的计算负载。文献[11]的方案寻找文件第i块的位置，需要预先移动n-i数据块作为插入或删除操作，同时需要重复操作至少100次，极大地加重了验证服务器的计算负载。本文所提方案可以在客户端极大地降低计算负载。图6显示了在更新不同的数据块所花费的计算开销，结果显示本文所提方案是非常高效的。

图7　对比分析不同大小文件块的计算开销

实验二对比分析不同文件块大小对计算负载的影响，图7显示的是文件块的大小对计算负载的影响，这里DA通过从1~10 GB文件中随机插入或删除100个数据块来更新不同大小的外包数据。文献[14]中的计算负载随着文件块大小的增长，从0.8到大约2.3快速的增长。文献[11]的方案中，当文件的大小从1到10 GB增长时(文件中的数据块大小都是8KB)，数据块的数量也随着增加。因此，验证服务器为了进行数据更新需要移动大量的数据块。正如在图7中所示，本文的方案由于使用10个DTs而不是1个，带来了极小的计算负载。所以，本文方法能够应用在大规模的动态数据验证。

实验三对于同一个文件F，选择不同的文件块大小，对完整性检测计算实验开销，选择200 MB的文件，依次选取4、8、16、32、64、128 KB，每次选取560块，然后记录每次实验所花费的时间和通信开销。实验结果如表2所示。

表2　完整性检测的计算开销

续表2

实验结果显示，在进行数据完整性检测时，文件块的大小对检测计算开销没有什么影响，各个阶段的计算时间基本保持稳定，检测请求阶段计算时间约为0.76 s，验证信息生成阶段计算时间约为1.08 s，完整性验证阶段计算时间约为1.65 s，对于一个200 MB的文件整个检测过程大概需要3.49 s左右，计算时间总体较小，符合预期的目标。实验环境稳定的情况下，每次实验的通信开销稳定在60 KB左右，通信开销较小，符合预期设计的目标。

5结语

本文提出了一种有效的远程数据验证方法来确保存储在云服务器上的数据安全。该方法运用代数签名的性质验证远程数据的完整性，可以极大地减少数据验证的计算开销。同时引入了一个称为Data Table的数据结构表，用来支持数据的动态更新，包括插入、修改和删除操作。然后分析该方案的正确性和安全性，最后与其他文献中的方法进行对比分析，实验证明该方法的可行性和高效性。下一步将在此基础上在DT表中寻找最佳的划分子块数来扩展该方案。同时也希望本方案能够运用在分布式云存储服务上。

参考文献

[1] 陈兰香.一种基于同态Hash的数据持有性证明方法[J].电子与信息学,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].软件学报,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] 于洋洋,虞慧群,范贵生.一种云存储数据完整性验证方法[J].华东理工大学学报:自然科学版,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。国家自然科学基金青年科学基金项目(51308465)；四川省教育厅项目(08ZC055)。王惠清，硕士，主研领域：计算机网络，云计算，分布式系统。洪志全，教授。