基于RASL的云存储数据完整性验证算法

唐明，张娇蓉（西华大学计算机与软件工程学院，成都　610039）

基于RASL的云存储数据完整性验证算法

唐明，张娇蓉
（西华大学计算机与软件工程学院，成都610039）

云存储；完整性验证；同态哈希；RASL

0　引言

云存储指的是通过集群应用、网格技术或分布式文件系统等功能，将网络中大量各种不同类型的存储设备通过应用软件集合起来协同工作，共同对外提供数据存储和业务访问功能的一个系统，它能保证数据的安全性，并节约存储空间。通过云存储服务，用户可以从云服务器上便捷、高效地获取存储的数据，同时也没有本地存储和维护数据的负担。云存储具有低成本、高可用性、高扩展性、高可靠性等传统存储方式所不具备的特点，越来越多的用户选择将数据存储到云服务器上。

然而，这种新的存储方式也面临这新的安全问题，即数据完整性。作为用户方，关心的安全问题主要包括两个方面：首先，用户会担心存储在云端的数据会不会随着数据中心发生故障而丢失，即数据安全性；其次，用户对存储在云端的数据会不会被窥探也会有所顾虑，即隐私安全性。用户将数据存储在云服务器上后，往往就失去了对所存储的数据的控制权，因此，若云存储服务提供商是不可信或半可信的话，数据拥有者可能会被云存储服务提供商欺骗而不能确定存储在云端的数据是否完整。故数据拥有者需要一种安全有效的服务机制来确保数据被安全、完整地存储在云端。

云存储数据完整性检测的早期方案［2～3］是要求用户将存储在云端的数据取回本地后再验证其完整性，用户在存储和验证之前都需要计算数据的哈希值。然而随着数据量的增加和用户的增长，该方案的计算量及通信成本也变的非常大，因此这种方式已不可取。之后，Deswarte等人于2003年提出了基于RSA的哈希函数的第一个远程完整性数据验证方案，即用户只需要取回部分数据就能验证存储数据的完整性，并在2008年提出其改进方案，使之支持数据更新操作。2007年，Ateniese等［5］人首次在其可证明持有方案中提出公开审计的问题，并给出了适用于静态数据的S-PDP方案和E-PDP方案，为了降低通信开销与计算开销，这两种方案都使用了同态标签技术［6］，但该方案均不支持动态审计与批量审计。

最近，周锐等人［7］为了保证云存储数据的完整性，提出了一种基于同态哈希函数的完整性检测算法，该算法在可信第三方的审计下，通过聚合多个RSA签名对云存储数据完整性进行验证，同时还采用了同态线性认证技术和随机掩蔽技术实现隐私保护。该算法支持数据完全更新、单项审计与多项审计，但是不能抵抗周恩光等人提出的已知证据伪造攻击。通过该攻击方法，敌手可以假冒云服务器，对用户记性欺骗，同时云服务器也可以在客户数据丢失的情况下，利用该攻击方法对客户进行欺骗。

针对上述方案的不足，本文利用Erway等人提出的基于等级的认证跳表技术对周锐等人提出的方案进行改进，并给出了安全性证明及性能分析，改进方案能抵抗已知证据伪造攻击。

1　预备知识

1.1同态哈希函数

同态哈希函数即一个具有同态性质的哈希函数，它满足以下性质：

（1）同态性：对任意的两个消息m1，m2及实数w1，w2，有H（w1m1+w2m2）=H（m1）w1H（m2）w2。

（2）免碰撞性：攻击者不存在概率多项式算法可以伪造 （m1，m2，m3，w1，w2），且满足m3≠w1m1+w2m2使得H（m3）=H（m1）w1H（m2）w2。

1.2基于等级的认证跳表

基于等级的认证跳表［9］（Rank-based Authenticated Skip List，RASL）是Erway等人在其支持完全数据更新的PDP方案中提出的概念，图1是RASL中的一个例子。

图1　基于等级的认证表

以图1为例，在RASL中，最左上的节点w7称为起始节点，每个节点v都包含rgt（v）节点向右的指针和dwn（v）节点向下的指针，这两个指针主要用来查询。对每个节点我们还需定义节点的等级，即从节点出发所能到达的底层节点的数量，记作r（v）。节点的层数记作l（v），l（v）=0表示底层节点。在图1中，每个节点内的值即表示该节点的级数。同时对每个节点v，我们用low （v）和high（v）分别来表示从该节点出发，最左和最右可到达底层节点的序号。对起始节点，我们有r（s）=n，low（s）=1和high（s）=n。利用已知节点的等级和相对应的最左及最右可到达节点的序号，我们可以到达底层的任意节点。

2　对周锐等人方案的攻击

利用周恩光等人［8］提出的已知证据伪造攻击的方法，我们可以对周锐等人提出的审计方案进行类似的攻击，具体攻击方法如下：

假设TPA与CS之间成功进行了N次完整性验证，敌手窃听并保存以下信息：

其中Pi=（μi，σi，Yi）（1≤i≤n）是第i次完整性验证过程中云服务器发送的证据。

则可以在没有文件F的情况下伪造一个合法的证据，在伪造过程中，客户存储在云端服务器上的数据均未泄漏，即敌手未获得用户的任何数据。这样敌手就可以利用伪造的证据欺骗用户，使得用户存储的数据即使被篡改，用户也无法通过验证而得知。

3　基于RASL的云存储数据完整性验证方案

KeyGen（1k）：输入安全参数k，选取大素数p和q，计算N=pq和φ（N）=（p-1）（q-1）；选取小整数e满足1＜e＜φ（N），且gcd（e，φ（N））=1；利用扩展欧几里德算法，计算满足ed≡1modφ（N）的唯一整数d，1＜d＜φ（N）；选择安全的同态哈希函数H（·）：ZN*→ZN*。用户的私钥为sk=d，公钥为pk=（N，e）。

SigGen（sk，F）：设用户存储的数据为F=｛m1，m2，…，mn｝，用户为数据F选取随机标识符name∈ZN*，并对每个数据块mi计算签名σi=（H（name||i）H（mi））d，签名集合Φ=｛σ1，σ2，…，σn｝。RASL的底层节点为按顺序排列的签名σi，即x（vi）=σi。客户计算RSAL的起始节点哈希值Mc（Mc为公开变量），并将｛F，Φ｝和RASL发送给云服务器之后删除。

Challenge：用户从集合｛1，2，…，n｝中随机选择c个元素组成的集合I=｛s1，s2，…，sc｝，其中s1＜s2＜…＜sc。对i∈I，用户选择随机值vi∈Zp，并将挑战消息chal=｛（i，vi）｝s1＜i＜sc发送至云服务器。

VerifyProof（pk，chal，P）：验证分为两步进行，收到证据P后，用户首先利用证明信息｛Π（i）｝s1＜i＜sc对σi的值及其索引值i进行验证。具体验证方法如下：

用户选取初始值λ0=0，ρ0=0，γ0=0，ε0=0，对j∈｛1，2，…，k｝，计算λj=lj，ρj=ρj-1+qj，δj=dj；

若δj=rgt，则rj=h（λj，ρj，γj-1，gj），εj=εj-1；若δj=dwn，则rj=h（λj，ρj，gj，γj-1），εj=εj-1+qj；

经过循环计算后，若rk≠Mc，则验证不通过，返回reject；若rk=Mc，则验证通过，返回accept。

4　结语

本文利用已知证据伪造攻击的方法给出了对文献［7］的具体攻击方法，通过攻击表明该方案不能抵抗已知证据伪造攻击。同时，应用同态哈希函数及RASL等相关技术，对原方案进行改进，并提出了基于RASL的云存储数据完整性方案，该方案能抵抗已知证据伪造攻击，并且能够保护客户的隐私数据不被泄漏。

［1］Deswarte Y，Quisquater J，Saïdane A.Remote Integrity Checking［M］.Integrity and Internal Control in Information Systems VI. Springer US，2004：1～11

［2］Blum M，Evans W，Gemmell P，et al.Checking the Correctness of Memories［J］.Algorithmica，1994，12（2-3）：225～244

［3］Naor M，Rothblum G N.The Complexity of Online Memory Checking［C］.Foundations of Computer Science，2005.FOCS 2005.46thAnnual IEEE Symposium on.IEEE，2005：573～582

［4］秦志光，吴世坤，熊虎.云存储服务中数据完整性审计方案综述［J］.信息网络安全，2014（7）：1～6

［5］Ateniese G，Burns R，Curtmola R，et al.Provable Data Possession at Untrusted Stores［C］.Proceedings of the 14th ACM Conference on Computer and Communications Security.Acm，2007：598～609

［6］Ateniese G，Kamara S，Katz J.Proofs of Storage from Homomorphic Identification Protocols［M］.Advances in Cryptology-ASIACRYPT 2009.Springer Berlin Heidelberg，2009：319～333

［7］周锐，王晓明.基于同态哈希函数的云数据完整性验证算法［J］.计算机工程，2014，40（6）：64～69

［8］周恩光，李舟军，郭华等.一个改进的云存储数据完整性验证方案［J］.电子学报，2014，42（1）：150～154

［9］Erway C，Küpcü A，Papamanthou C，et al.Dynamic Provable Data Possession［A］.Proceedings of the 16th ACM Conference on Computer and Communications Security［C］.Chicago：Acm，2009：213-222

Cloud Storage；Integrity Verification；Homomorphic Hash；RASL

Integrity Verification Algorithm of Cloud Storage System Based on RASL

TANG Ming，ZHANG JIAO-rong
（School of Computer and Software Engineering，Xihua University，Chengdu 610039）

1007-1423（2015）10-0005-04

10.3969/j.issn.1007-1423.2015.10.002

唐明（1987-），男，湖北天门人，硕士研究生，研究方向为计算机网络与信息安全系统

2015-03-17

2015-04-08

随着信息技术的发展，网络化存储将逐渐成为未来存储领域的热点。而目前的云存储服务也将是网络存储发展的必然趋势。因此如何确保云存储环境下用户数据的完整性成为人们关注的问题。周锐等人提出基于同态哈希的云数据完整性验证算法中的公开审计方案。通过对该方案的分析，发现该方案容易受到已知证据伪造攻击，并给出具体的攻击方法。为了防止攻击，利用基于等级的认证跳表技术（RASL）对该方案进行改进，并对本文方案做安全性分析及证明。

张娇蓉（1988-），女，四川巴中人，硕士研究生，研究方向为序列设计

With the development of information technology，network storage will gradually become a hot storage areas in the future.The current cloud storage service will be the inevitable trend of development of network storage.Therefore，how to ensure the integrity of user data in cloud storage environments has become an issue of concern.Zhou Rui et al proposed public audit scheme for cloud data integrity verification based on the homomorphic hash.Through the analysis of the scheme，the scheme is vulnerable to the known evidence of forgery attack，and gives a specific attack method.In order to prevent attacks，improves the scheme based on RASL，and the proposed scheme is security by formal proofs.