一种改进的多用户多副本数据完整性验证方案

潘洪志 方 群,2 何 昕,2

1(安徽师范大学计算机与信息学院 安徽芜湖 241002) 2 (网络与信息安全安徽省重点实验室(安徽师范大学) 安徽芜湖 241002 (asdphz2015@163.com)

在云环境中，用户会将自己的数据设计成多个副本存储在云存储服务提供商提供的多个存储节点上，对于用户来说，数据的存储过程是透明的，用户在需要的时候取出即可[1-4].可是用户的数据存储在各个数据节点上并不是平行的.为了节约存储空间和提高经济效益，对于某些不常用，不常访问的数据，云服务提供商可能会对这些数据进行窃取、篡改[5].同时，一些不可信的云存储环境可能会使用户数据遭受窥视或损坏.用户虽然采用匿名加密[6]、数据分块交叉存储[7]等技术来保障数据的隐秘性，但对数据的安全性并不能完全保证.因此，我们需要采用合适的多副本数据完整性验证策略，在提高验证效率的同时保护用户数据的可靠性.

目前大部分方案是采用Merkle树[8]、跳表[9]等树形结构来支持多副本和支持动态更新环境下的完整性验证策略，这些策略虽然支持了数据动态更新，但在构造认证过程中需要大量的辅助信息，大大增加了数据访问复杂度.本文在基于双线性映射特性的签名机制下，提出一种改进方案，利用自适应Trie树的简单结构来简化验证方式，同时利用随机掩码技术来满足多副本的批量化验证，高效地保护了用户的数据安全.

本文首先给出云环境下数据完整性检测模型，通过分析数据完整性验证方案存在的问题给出最适合解决方案，最后通过理论分析和仿真实验证明方法的有效性.

1 系统模型

本文中的系统模型如图1所示，模型主要包括用户(users)、可信第三方审计者(TPA)、云存储服务提供商(CSP)，其中：

用户(users).用户将自己的数据存放在云服云存储服务器上，通过客户端访问云存储服务器.

可信第三方审计者(TPA).可信第三方审计者主要是帮助用户存储验证信息和规则.通过用户授权，代替用户进行密钥管理、数据完整性策略管理和数据验证规则管理.

云存储服务提供商(CSP).CSP提供计算资源、存储资源和网络资源.

在系统初始化阶段，用户初始化数据文件的初始数据，并与CSP和TTPA协商密钥.在挑战-应答阶段，用户可以保持离线，所有验证工作由TTPA和CSP完成.当TTPA验证数据完整性时，向CSP发送挑战信息chal.CSP接收到挑战后，根据存储的数据生成完整证据P返回给TTPA，然后TTPA对接收的证据进行验证，其过程如图1所示：

图1 数据完整性验证模型

2 问题定义

2.1 数据完整性审计方案存在的问题

Ateniese等人[10]定义的PDP方案中，使用了基于RSA模指运算的同态标签，在该方案中用于验证服务器证明的元数据为wi=v‖i，生产的同态标签为Ti=(h(wi)·gbi)dmodN，最后通过验证下列等式是否成立来判断云存储服务器上的数据是否完整.

但是该方案并不能直接应用于云环境中多副本的存储环境下，因为对于用户来说，他们无法判断云服务提供商是否存储了和用户商定的副本数量，若这里的副本都是相同的，则会出现云服务提供商只存储了1份数据，但向用户声称自己存储了之前商定的足够份数的数据，而用户并不能判断.针对这个不安全问题，Curmola等人[11]第1次提出了MR-PDP方案，用户首先使用密钥k和对称加密算法对文件F加密，然后对密文F′进行分块处理，得到F′={f1,f2,…,fn}.

F′=Ek(F),F′={f1,f2,…,fn}，

并通过随机掩码技术对密文块F′={f1,f2,…,fn} 进行处理，得到Fu={fu,1,fu,2,…,fu,n},其中1≤i≤n,bu,i=fi+ru,i.通过伪随机函数生成ru,i=ψz(u‖i),1≤i≤u.最后通过验证下列等式是否成立来判断云存储服务器上的数据是否完整.

通过该方案识别用户数据的完整性和安全性.但是该方案并不支持公共审计，如果将该方案直接应用到公共审计的环境下，则可能将ru,j信息泄露给可信第三方.

因此，在考虑多副本环境下，用户除了对自己存放在云端的数据验证是否完整之外，还需要能够支持对云端数据进行动态更新操作.

2.2 多用户多副本批量审计方案

2.2.1AT树

Trie树又称字典树、单词查找树或者前缀树，是一种用于快速检索的多叉树结构.Trie树利用字符串的公共前缀来节省空间，最大限度地减少不必要的字符串比较并提高查询效率.传统的Trie树只有一类节点，以数组表示，每个index是指向子节点的指针.在AT树中，新增2个新节点——叶子节点和扩展节点，节点由key和value组成.key为带标识id的十六进制前缀码，标识id用于区分叶子节点和扩展节点.若终止符标记被打开，那么key对应的是叶子节点，value存储数据的Hash值；若终止符标记被关闭，那么value值就是用于在数据块中查询对应的节点的地址.

如图2所示，扩展节点和叶子节点的id位为1个4 b二进制数字，最低位表示key的奇偶性，第二低位为编码终止符状态.

图2 自适应Trie树节点结构

图3是一个自适应Trie树的初始化结构图:

图3 自适应Trie树的初始化结构图

如图3所示，通过增加节点的种类，树的深度可以得到有效控制，避免攻击者操纵树的深度，发起DoS攻击；而且树的根只取决于数据的内容，与其更新顺序无关.另外为保护机密性，AT树节点二元组key,value只存储经过特殊编码的值，可有效保护数据隐私，提高安全性.

2.2.2数据完整性审计方案

数据完整性审计方案分为2个阶段：初始化阶段、审计阶段.在初始化阶段，用户调用KeyGen()生成公钥和私钥；然后执行SigGen()生成数据块、数据块同态标签.在审计阶段，首先支持多个用户验证所有副本数据完整性.可信第三方调用chal生成挑战信息.

假设G1,G2是阶为素数p的乘法群，令e:G1×G2→Gt表示一个双线性映射，u和g分别为G1和G2的生成元.

1)KeyGen():该阶段首先在客户端(Client)产生公钥和私钥.过程为：

Step1. 随机选取α,β1,β2,…,βn∈p，g∈G1，H∈G1，选取随机密钥k；

Step2. 计算Hβi→Hi,Hi∈G2,1≤i≤n，y∈e(g,H),x0∈e(h,H)a0;

Step3. 输出公钥pk≡(k,Hn,y,x0)和私钥sk≡(βn,L,a0,g).

2)SigGen(sk,F)→(Trust)：该阶段为标签生成阶段，首先将用户的数据进行加密处理，然后对加密的数据进行分块，随机化处理，生成1个同态标签集合Trust，最后云服务提供商接收用户处理后的数据进行构造对应的验证结构.具体步骤如下：

Step1. 假设用户数据原文件用F表示，对文件F进行加密处理得到F′，然后将文件F′分成n块,得到F′≡(b1,b2,…,bn);

Step3. 使用随机掩码函数f(g):{0,1}k×{0,1}l→{0,1}l对分块数据进行随机化处理，得到ftk,i={mtk,1,mtk,2,…,mtk,n}，mtk,i=btk,i+rl,rl=f(l‖k),l∈p,1≤i≤n;

Step4. 计算各个数据块的标签值Ttk,i=Hk(mtk,i)·Hmtk,i，得到同态标签集合Trusttk,i={Ttk,i|i∈{1,2,…,n}};

Step5. 用户将本地的标签集合Trusttk,i和数据文件分块集合ftk,i发送给CSP，并删除本地文件;

Step6. 云服务提供商将接收到的文件F生成c个副本，分别存储在地理位置不同的服务器节点上，同时生成副本数据集ftk,i,j和标签集合Trusttk,i,j，ftk,i,j={ftk,i,1,ftk,i,2,…,ftk,i,n}，Trusttk,i,j={Trusttk,i,1,Trusttk,i,2,…,Trusttk,i,n}，1≤j≤c;

Step7. 云服务提供商同时将副本数据集和标签集合同步更新到各个数据节点，并给用户反馈是否成功存储的结果.

3)GenProof(F,chal,Trust)→(P).

用户委托TPA对云存储服务器节点中的数据进行完整性审计，TPA接收到用户的授权之后，生成挑战信息，并将挑战信息发送给云服务提供商.然后云服务提供商对挑战信息进行回复，将验证信息返回给TPA.具体步骤如下：

Step1. 从集合{1,2,…,n}中随机选择c个元素组成集合Ic≡{s1,s2,…,sc},s1≤sc≤sn，用户将挑战消息chal≡{(Ic,N)}(其中N为时间戳)，发送给云服务提供商;

Step2. 云服务提供商收到挑战信息chal,并将挑战信息chal和副本信息生成调整信息chalu={ftk,i,j,Trusttk,i,j,chal},1≤u≤c分别发送给相对应的副本存储器节点;

Step3. 云环境中的各个副本存储节点接收到挑战信息之后，分别计算持有性证据:

4)VerifyProof(chal,P)→(True,False)：输入证据P和挑战信息chal，如果验证通过输出True,验证失败输出False.

审计者收到证据P后，审计者验证式(1)，如果验证成功，输出结果为“True”,否则系统输出“False”.公式为

(1)

2.2.3数据动态操作

本节主要讨论用户数据更新问题，用户对云存储数据更新操作包括数据修改(M)、数据删除(D)和数据插入(I)操作.

1) 数据修改(M)

Step3. 客户端接收到服务器反馈回来的验证信息之后，和本地的信息作比对.如果确定信息正确，则删除本地的已更新的数据块和相关信息；如果校验信息不正确，则重新请求更新操作.

算法1. 数据修改算法.

① Begin

Ttk,i,j);

Ttk,i,j);

⑧ Send the proofRUpdateto client;

⑩ Print True;

2) 数据插入(I)

假设第k个用户需要在自己的数据中的第i个位置的数据块前插入新的数据块f*，则需要进行以下操作：

Step1. 计算需要新插入数据块f*的认证标签TF*，然后生成更新请求消息Update=(I,(k,i),f*,Tf*),并将请求消息发送给云服务器;

Step2. 服务器接收到客户端的插入请求消息之后，根据(k，i)找到更新数据所要更新的位置，然后插入数据f*,同时更新认证标签信息TF*,更新完成，反馈插入操作信息RUpdate;

Step3. 客户端接收到服务器关于插入操作反馈的验证信息之后，进行校验，如果确定信息正确，则删除本地已更新的数据块和相关信息,如果校验信息不正确，则重新请求插入操作.

算法2. 数据插入算法.

输入：需要插入的数据块ftk,i,j;

① Begin

② Input (f*);

③Tf*=Sign(f*);

④Update(f*)=(I，(k,i-1),f*,Tf*);

⑤ Send the requestUpdate(f*) to server;

⑥ExceUpdate(I，(k,i-1),f*,Tf*);

⑧ Send the proofRUpdateto client;

⑩ Print True;

3) 删除操作(D)

假设第k个用户需要删除数据中第i个位置中的数据块ftk,i,j.其操作步骤同插入类似，过程如下：

Step1. 客户端生成请求消息Update=(M，(k,i),Ttk,i,j)发送给云存储服务器.

Step2. 服务器收到更新请求之后，首先根据(k,i)找到数据所在位置，取出数据块的标签值和Ttk,i,j验证，确定用户的校验值的信息是否正确.如果不正确就返回拒绝更新信息；如果正确，则更新相应的数据块和数据块的标签，并返回更新后的数据块的验证信息RUpdate.

Step3. 客户端接收到服务器反馈的验证信息之后，和本地的信息作比对.如果确定信息正确，则删除本地已更新的数据块和相关信息；如果校验信息不正确，则重新请求删除操作.

算法3. 数据删除算法.

输入：待删除数据块;

① Begin

②Update(ftk,i,j)=(D，(k,i),ftk,i,j,Ttk,i,j);

③ Send the requestUpdate(ftk,i,j) to server;

④ExceUpdate(D，(k,i),ftk,i,j,Ttk,i,j);

⑥ Send the proofRUpdateto client;

⑧ Print True;

⑨ else Print False;

⑩ End

3 实验分析

本节将从通信开销和计算开销来评价整个方案的性能.实验环境为:Inter Core i5 CPU 2.3 GHz,内存4 GB，64 b Windows7操作系统.双线性映射使用的是版本号为2.0.0.0的jpbc库，使用128 b AES加密算法加密数据，使用椭圆曲线域表示G1,G2,GT，随机数的大小为r=80,ρ=160.我们假设用户数量为K，每个文件M大小为|M|=223b，副本数量为t.

假设可信第三方每次随机挑战n块当中的c块数据，并且存在1个恶意的云服务修改了其中的k块数据.设随机变量X表示检测到数据有损坏的块数，其样本空间X={0,1,2,…,k}.由概率基础知识得到：

(2)

1) 通信开销

通信开销主要产生在用户将数据块和签名信息上传到服务器中，还有可信第三方向云服务提供商发起的挑战过程产生的通信开销.其中数据文件产生的通信开销约为1.5t×210(单位为b)；可信第三方向云服务提供商发起的挑战过程产生的通信开销约为lb 460+128t(单位为b).另外，文献[12]的通信开销为lb 460+256t+790(单位为b)，文献[13]的通信开销为lb 460+128t+160(单位为b).图4显示的是通信开销随着副本的数量变化情况.

图4 通信开销随副本数量的变化情况

2) 计算开销

假设数据副本数量t=1.本节方案CSP证明生成时间随用户数量k变化情况如图5所示.同样，当用户数量k=1时,CSP证明生成时间随副本数量t变化情况如图6所示.

图5 当用户数量为1时CSP证明生成时间随副本数量的变化情况

图6 当副本数量为1时CSP证明生成时间随用户数量的变化情况

通过实验可以看出，本文方案与其他多副本数据完整性验证方案相比，计算开销、存储开销和通信开销都相对较小.

4 总 结

针对多副本数据完整性验证方案计算和通信开销较大的问题，本文提出了一种改进的多用户多副本数据完整性批量审计方案，引入了可信任的第三方审计师TPA来支持公共审计，利用签名技术和线性代数映射实现用户数据的真实性验证.最后，通过该方案性能分析表明，该方案具有较低的计算开销和通信开销.

[1]Wang C, Wang Q, Ren K, et al. Ensuring data storage security in cloud computing[C]Proc of the 17th Int Workshop on Quality of Service. Piscataway, NJ: IEEE, 2009: 1-9

[2]王一蕾, 吴英杰, 孙岚. 隐私保护关系型数据发布的多维划分动态规划算法[J]. 南京大学学报: 自然科学版, 2013, 49(2): 258-267

[3]Lin L, Li Q, Kong L, et al. Tenant-oriented composite authentication tree for data integrity protection in SaaS[C]Proc of Int Conf on Web-Age Information Management. Berlin: Springer, 2014: 402-414

[4]Liu H, Zhang P, Liu J. Public data integrity verification for secure cloud storage[J]. Journal of Networks, 2013, 8(2): 373-380

[5]Li J, Wang Q, Wang C, et al. Fuzzy keyword search over encrypted data in cloud computing[C]Proc of Conf on Information Communications. Piscataway, NJ: IEEE, 2010: 441-445

[6]Ni J, Yu Y, Mu Y, et al. On the security of an efficient dynamic auditing protocol in cloud storage[J]. IEEE Trans on Parallel & Distributed Systems, 2013, 25(10): 2760-2761

[7]Liu C, Yang C, Zhang X, et al. External integrity verification for outsourced big data in cloud and IoT[J].

Future Generation Computer Systems, 2015, 49(C): 58-67

[8]Wang Q, Wang C, Li J, et al. Enabling public verifiability and data dynamics for storage security in cloud computing[C]Proc of European Conf on Research in Computer Security. Berlin: Springer, 2009: 355-370

[9]谭霜, 贾焰, 韩伟红. 云存储中的数据完整性证明研究及进展[J]. 计算机学报, 2015, 38(1): 164-177

[10]Ateniese G, Burns R, Curtmola R, et al. Provable data possession at untrusted stores[C]Proc of ACM Conf on Computer and Communications Security. New York: ACM, 2007: 598-609

[11]Curtmola R, Khan O, Burns R, et al. MR-PDP: Multiple-replica provable data possession[C]Proc of Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2008: 411-420

[12]Chen H F, Lin B G, Yang Y, et al. Public batch auditing for 2M-PDP based on BLS in cloud storage[J]. Journal of Cryptologic Research, 2014, 1(4): 368-378

[13]Zha Y X, Luo S S, Bian J C, et al. Multiuser and multiple-replica provable data possession scheme based on multi-branch authentication tree[J]. Journal on Communi-cations, 2015, 36(11): 80-91