云存储系统中数据完整性验证协议

文章编号:1001-9081(2012)01-0008-05 doi:10.3724/SP.J.1087.2012.00008

摘 要:

在云存储网络环境中，数据的安全性和完整性是用户最关心的问题之一。综合考虑云存储网络环境中的安全需求，设计了云存储数据完整性验证（CSDIV）协议。客户端把数据文件和校验标签上传到云存储服务器后随机抽查，服务器返回验证证据并由客户端判断文件的完整性。协议可以有效地验证云存储数据的完整性，并抵抗恶意服务器欺骗和恶意客户端攻击，从而提高整个云存储系统的可靠性和稳定性。仿真实验数据表明，所提协议以较低的存储、通信及时间开销实现了数据的完整性保护。

关键词:云存储；数据完整性；同态标签；安全协议；数据存储安全

中图分类号: TP393.04 文献标志码:A

Abstract:

In the cloud storage network, the security and integrity of data are the major concerns of clients. Taking full consideration of the security requirements for cloud storage network, a new Cloud StorageData Integrity Verification (CSDIV) protocol was proposed. The clients uploaded files and tags to the servers and then did random check; the servers returned proofs and the clients judged the result. This protocol could not only ensure the integrity of data in the cloud storage effectively, but also resist the cheat from the untrusted servers and the attack from the malicious clients, and then improved the reliability and stability of the whole cloud storage system. The simulation experimental results show that the proposed protocol realizes the protection of data integrity at low cost of storage, communication and delay.

Key words:

cloud storage; data integrity; homomorphic tag; security protocol; data storage security

0 引言

随着计算机网络的不断发展，人们对于数据存储的要求也越来越高，特别是在云计算兴起的背景下，基于海量数据的云存储系统成为关注的热点。很多的网络服务商，包括国外的DropBox以及国内的金山快盘等，都开始提供云存储服务，帮助用户实现任意地点、任意时间、任意数据的访问，不仅给人们带来了方便和效益，同时也节约了社会的资源与能源。但是，因为云存储的安全性、可靠性及服务水平等还存在众多问题亟待解决，所以云存储仍未得到广泛认可与使用。数据存放在云存储中，用户最关心的问题之一是数据的完整性。当存储服务商可以有效地对用户提供数据完整性验证，并不断提高服务水平，云存储将获得广泛的应用。

1 相关工作

传统存储系统的数据完整性检查主要是基于访问的，如在线存储系统［1］、海量存储系统［2］以及数据库存储系统［3］等，这些系统频繁访问服务器上的数据，增加了服务器的负担，严重浪费网络的带宽资源；另一种比较常见的方案是基于挑战和应答的方法，由客户端提出挑战某些数据块，服务器来生成数据完整性的证据，最后由客户端来判断结果，如Ateniese等提出了可证明数据持有(Provable Data Possession, PDP)模型［4-7］，但该模型没有考虑数据在传输过程中的安全性；还有一种思想是惠普公司Shah等提出的审计方案［8］，该方案将用户的检查任务交给可信第三方来完成，但是这势必会增加原存储服务商的代价而且很可能泄露信息从而带来新的安全隐患；Zhu等提出了一种分层混合云模型［9］，能有效利用不同云存储服务商提供的云资源来协作存储用户的数据，同时将这个模型划分成3层：解释层、服务层和存储层，在一定程度上增加了系统的可靠性，同时额外增加了一些存储的开销。

以上方案的不足，主要在于缺乏对云存储网络环境特性的考虑，没有尽可能地降低服务器的通信开销和存储开销，缺少安全协议保障用户数据的安全性。针对上述不足，本文基于PDP模型，提出一种适用于云存储的数据完整性验证（Cloud StorageData Integrity Verification, CSDIV）协议。客户端在把数据文件及其校验标签上传到云存储服务器后，通过随机抽查的方式，让服务器生成指定数据块的验证证据并返回，由客户端判断数据文件的完整性。同时，该协议具有适应性：对于较小的文件，可以通过检查所有的数据块来保证结果的有效性；而对于较大的文件，则可以检查部分数据块以一定的概率来保证数据的完整性，从而减少系统资源和网络带宽的消耗。

2 云存储数据完整性的验证方案

2.1 方案综述

本方案参考Google文件系统（Google File System, GFS）［10］的设计，将系统实体分为四类角色：客户端C、主服务器S、接口服务器S0以及存储服务器S1，S2，S3,…。当C想要把一个文件F保存在云存储系统中，可以与S0进行交互，上传或者下载数据文件，这样能最大限度地简化客户端的执行流程。而S则是整个云存储的中心枢纽，它不但负责所有存储资源S1，S2，S3,…的分配和调度，而且在存储目录中保存了用户的存储信息。这样的设计实现了控制流和数据流的分离，S0和S之间只有控制流，没有数据流，从而降低了主服务器的负载［11］。由于文件被分成多个数据块保存在存储服务器上，因此C与S0以及S0与S1，S2，S3,…之间可以并行地传输数据，有效提高系统的吞吐量。

整个系统方案的流程概述如下：首先，C与S0进行相互认证，获取会话密钥；接着C生成用于校验的公私钥对，并为每个待上传的数据块生成相应的标签，利用其同态的特性来唯一地标记对应的数据块；然后C向S0申请访问云存储系统，S0告知主服务器S，S根据系统当前的状况分配存储资源S1,S2,S3,…给C，接着C就上传F给S0，S0根据S的分配将数据块传送到相应的存储服务器。

在验证阶段，客户端C发起一个校验的挑战，主服务器S根据存储目录中用户的存储信息，通知相应的存储服务器，把校验标签发送给接口服务器S0，并由S0将标签和验证信息返回给C，C根据保存在本地的私钥来验证数据是否完整。至此，整个云存储中数据完整性的验证流程结束。用户在任何时间如果需要再进行数据验证，可以随时执行验证阶段的任务。

2.2 相关概念

2.2.1 密码学符号列表

本文所使用的基本密码学符号及其含义如表1所示。

2.2.2 同态标签

同态标签是具有同态属性的标签数据［12］，可以将多个从文件块计算的标签合成为单个值，因此可以节省系统传输的带宽。假设给定两个标签Ti和Tj，它们是由所对应的数据块mi和mj计算得到的定长数据值，可以把标签和数据块看成具有映射关系，通过计算Ti+Tj的结果，来判断mi+mj的情况，即可以实现利用同态的特性来验证数据的完整性。

2.2.3 SVO逻辑

在安全协议分析领域，通常使用形式化分析的方法来判定协议的安全性。其中：BAN(Burrows,Abadi,Needham)请补充其中文名称和英文全称。逻辑［13］可以看作是形式化方法的代表作和里程碑，SVO(Syverson, van Orschot)逻辑［14］则是BAN逻辑的一个改进版本。本文所需使用的基本SVO逻辑术语及其含义如表2所示。

2.3 云存储数据完整性的验证协议

2.3.1 协议设计

云存储数据完整性验证方案分为准备阶段和验证阶段，因此对应地设计了两个协议，协议中的实体与图1中的一致。假设服务器之间相互信任，同时为了实现用户的认证，防止恶意用户的攻击，CSDIV协议基于X.509公钥认证框架［15］，参考了三向认证协议［16］，C和S0都拥有自己的公私钥对，且事先已经获得对方的公钥。这里C的认证公私钥对是（PKC，SKC），S0的认证公私钥对是（PKS0，SKS0）。

协议1 准备阶段协议。

1)CS0:EPKS0(rC,S0,K1),SigSKC(h(rC,S0,K1))；

2)S0C:EPKC(rS0,C,rC,K2),SigSKS0(h(rS0,C,rC,K2))；

3)CS0:EPKS0(rS0,S0),SigSKC(h(rS0,S0))；

4)CS0:EK(F,size,N),SigSKC(h(F,size,N))；

5)S0S:C,F,size,N；

6)SS0:n,S(i)~BlockNumber；

7)S0C:EK(n),SigSKS0(h(n))；

8)CS0:EK(Block(i)),SigSKC(h(Block(i)))；

9)S0S1,S2,S3,…:C,F,Block(i)；

10)S1,S2,S3,…S:C,F,BlockNumber,IndexNumber；

11)SS0C:{"success","failure"}。

准备阶段的协议1说明如下。

1)C选取随机数rC和临时会话密钥K1，对rC、S0的标识符和K1加密，并对它们的哈希值做签名。

2)S0验证签名和哈希值，如果通过则S0选取随机数rS0和临时会话密钥K2，对rS0、C的标识符、rC和K2加密，并对它们的哈希值做签名。

3)C验证签名和哈希值，检查rC是否是自己发送的随机数，如果通过则C对rS0和S0的标识符加密并对它们的哈希值做签名；S0验证签名和哈希值，检查rS0是否是自己发送的随机数；如果双方都通过认证，就可以根据已获取的K1和K2，通过单向哈希函数计算得到最终的会话密钥KhK1(K2)。

4)C运行Key算法生成用于文件校验的参数（N,sk），并对文件名F,文件大小size和模数N的哈希值做签名。

5)S0验证签名和哈希值，把客户端标识符C、F、size以及N发送给S。

6)S根据云存储系统当前的状况，计划将文件F分成n块上传到S1,S2,S3,…这几个存储服务器，并把存储服务器S(i)需要存储的块号信息发送给S0。

7)S0发送n给C告知其要分成几个数据块上传，并对n的哈希值做签名。

8)C验证签名和哈希值，把F分成n块m1,m2,…,mn，运行Tag算法为每一个文件块mi计算对应的标签Ti，每个数据块由块号、文件块和标签块组成，即Block(i)=imiTi，并对数据块的哈希值做签名。

9)S0验证签名和哈希值，将Block(i)、标识符C和文件名F发送给相应的存储服务器S1,S2,S3,…。

10)S1,S2,S3,…收到数据块后，为其生成一个索引号Index Number便于以后查找并告知S。

11)S在存储目录中更新C有关F的所有信息后，返回协议的运行结果。

协议2 验证阶段协议。

1)CS0:EK(F,u,K3,K4),SigSKC(h(F,u,K3,K4))；

2)S0S:C,F,ij,aj；

3)SS0:C,F,N；

4)SS1,S2,S3,…:IndexNumber,ij,aj,N；

5)S1,S2,S3,…S0:Tij ,mij aj mod N；

6)S0C:EK(V),SigSKS0(h(V))。

验证阶段的协议2说明如下：

1)C生成抽查数u（1≤u≤n）以及挑战密钥K3和K4，对F,u,K3,K4的哈希值做签名；

2)S0验证签名和哈希值，然后用伪随机置换函数得到随机抽查的块号ij=pK3(j)，用伪随机函数生成混淆系数aj=fK4(j)，将C,F,ij,aj发送给S；

3)S找到保存在存储目录中客户端C的文件F对应的模数N发送给S0；

4)S根据C,F,ij找到被挑战块对应的服务器号S(i)和索引号Index Number并告知S1,S2,S3,…；

5)S1,S2,S3,…根据索引号找到相应的数据块，计算数据块当前信息mij aj mod N，连同标签块Tij一起发送给S0；

6)S0运行Proof算法生成验证信息V，C运行Verify算法校验文件的完整性。

2.3.2 算法设计

本节重点介绍在2.3.1节中CSDIV协议用到的4个多项式时间算法：Key,Tag,Proof,Verify。

算法Key (N,sk)Key(1k)/*生成用于文件校验的参数*/

程序前

Generate parameters N, e, d meet the conditions of RSA assumption;

rR{0,1}k;

sk(e,d,r);

Output (N,sk);

程序后

算法由C执行，时间复杂度为O(1)，生成了基于RSA假设的安全参数N,e,d：首先选择两个大的安全素数p和q，计算RSA模数N=p×q，欧拉函数φ(N)=(p-1)(q-1)；然后选择一个整数e满足1

算法Tag (T1,T2,…,Tn)Tag(pk,sk,m)/*为每个文件块生成标签块*/

程序前

for (i=1;i≤n;i++)

{Wi=r×i; Ti=［h(Wi)×mi］e mod N;}

Output (T1,T2,…,Tn);

程序后

算法由C执行，时间复杂度为O(n)，为每个文件块生成对应的标签块。Wi是一个由r和i组成的秘密参数，把它的哈希值乘以mi使其与对应的文件块关联上，再用e和N对结果进行加密，就得到了标签块，最后输出所有标签块信息。

算法Proof VProof(mij aj mod N,Tij,pk)/*生成文件校验的证据*/

程序前

T=∏iui1Tajij=［h(Wi1 )a1 ×…×h(Wiu )au ×mi1 a1 ×…×miu au ］e mod N;

P=h(mi1 a1 ×…×miu au mod N);

Output V=(T,P);

程序后

算法由S0执行，时间复杂度为O(1)，利用同态特性将被检查的标签合并，得到原始状态T，然后求系统当前文件的哈希值，得到当前状态P，最后将(T,P)作为数据完整性的证据V输出。

算法Verify {"success","failure"}Verify(N,sk,u,K3,K4,V)/*对证据进行验证*/

程序前

t=Td mod N;

for (j=1; j≤u; j++)

{ij=pK3(j);aj=fK4(j);Wij=r×ij;t=th(Wij)aj mod N;}

If h(t)=P

Output "success";

Else Output "failure";

程序后

算法由C执行，时间复杂度为O(n)，用密钥d对T进行处理，然后计算ij、aj和Wij，接着将t除以h(Wij)aj得到［mi1 a1 ×…×miu au ］ mod N，如果h(t)=P，就表明云存储完整地保存用户文件F。

3 协议的安全性分析

在云存储的网络环境中，可能存在着各种威胁网络安全的恶意行为，本章重点讨论两种可能存在的恶意行为，分析CSDIV协议的安全性。

3.1 恶意服务器欺骗

假设云存储系统S*是一组不诚实的服务器，它可能在数据不完整的情况下，对客户端进行恶意欺骗，声称依然完好无损地保存着数据，使得CSDIV协议的运行结果仍然为“success”。

CSDIV协议是基于概率模型的，支持对数据的任意块进行抽样检查。假设一个文件F包含n个数据块，服务器删除或丢失了其中的任意t块数据，C随机抽查n中的u块数据。设随机变量X表示C检测到文件数据有丢失，则其概率PX=P｛X≥1｝=1－P｛X=0｝=1－n－tn×n－1－tn－1×…×n－u+1－tn－u+1。因为n－i－tn－i≥n－i－1－tn－i－1，所以PX的值域是［1－(n－tn)u，1－(n－u+1－tn－u+1)u］。

由此可知PX的下界决定了CSDIV协议的有效性，即至少有1－(n－tn)u的概率检测到数据丢失。假设n中有1%的数据丢失，即t=0.01n，则1－(n－tn)u=1－0.99u，同理可得t=0.03n和t=0.005n的情况下，随机抽查的块数u与成功检测数据丢失的概率PX之间的关系。由图4可知，PX与n无关，当n很大时，u仍然可以保持一个较小的值，使得S*很难进行成功的欺骗。

方案的特点在于能根据用户的需求灵活运用。特别地，当u=n时，则表示对每一块数据都进行检查，即用户对精度要求比较高的时候，CSDIV协议也能以100%的概率证明数据的完整性。

3.2 恶意客户端攻击

假设客户端M（Malice）是恶意用户，它可能利用两种攻击手段：直接攻击和间接攻击。直接攻击是指M截获客户端C发送给接口服务器S0的认证信息，企图向S0发动重放攻击（ReplayAttack, RA），来通过服务器的认证，使S0误以为是C与其进行通信；间接攻击是指M通过各种技术手段切入C和S0之间，从而发动中间人攻击（ManintheMiddle Attack, MITM），进行信息篡改和信息窃取。

CSDIV准备阶段协议的前3个步骤就是用来进行身份认证的。其中：随机数用于防止重放攻击；身份标识符用来标识通信的主体；临时会话密钥是通信双方用来生成最终会话密钥的；对消息的签名是消息发送方对消息的认证，用于抵抗中间人攻击。该协议通过三向认证后，通信的双方都能确定对方的身份，并防止恶意用户的非法访问。下面将使用SVO逻辑来分析CSDIV协议认证部分的安全性，描述如下：

M1:CS0:{rC,S0,K1}KS0,{h(rC,S0,K1)}K－1C

M2:S0C:{rS0,C,rC,K2}KC,{h(rS0,C,rC,K2)}K－1S0

M3:CS0:{rS0,S0}KS0,{h(rS0,S0)}K－1C

条件 A1表示基本假设，协议的运行环境是不安全的；A2表示每个主体的公钥是公开的；A3表示每个主体的私钥仅为其所知；A4表示C believes fresh (rC此处的“C”是否为下标，还是现在这样的书写形式？请明确。)；A5表示S0 believes fresh (rS0同理，此处的“S0”是否应该为下标，请明确。)；A6表示C controls M1/M3；A7表示S0 controls M2；A8表示C believes PK(S0,K)∧C received {X}K-1C believes (S0 said X)；A9表示S0 controls X∧S0 says XS0 believes X。

目标 G1表示S0 believes C believes K1；G2表示C believes S0 believes K2。

证明

由M2，A2，A3，A8得：

F1：C believes S0 said (rS0,C,rC,K2)

由F1，A4得：

F2：C believes S0 says (rS0,C,rC,K2)

由F2，A7,A9得：

F3：C believes S0 believes K2（证得G1）

由M3，A2，A3，A5得：

F4：S0 believes fresh(rS0,S0)

由M1，A2，A3，A8得：

F5：S0 believes C said (rC,S0,K1)

由F4，F5得：

F6：S0 believes C says (rC,S0,K1)

由F6，A6，A9得：

F7：S0 believes C believes K1（证得G2）

在SVO逻辑下可以证明得到目标G1和G2并且没有发现漏洞，由此可见，CSDIV协议认证部分能有效抵抗恶意客户端的攻击，同时保证C和S0正确交换临时会话密钥K1和K2，从而得到最终的会话密钥K，使得C与S0进行安全的通信。

4 协议的性能分析

在Intel Pentium Dual E2140 1.60GHz CPU,1GB内存的Windows XP的系统中，用Visual C++ 6.0设计CSDIV协议的仿真程序，其中Hash函数使用的是SHA1［17］，其输出结果为160b，网络延迟假设为42ms，客户端和服务器之间传输速率为100KBps，服务器之间传输速率为10MBps，文件分块大小为64KB，则标签每个占0.125KB。

4.1 存储开销分析

C需要存储的信息有S0的标识符及公钥、用于认证的公私钥和用于文件校验的公私钥，S0要保存C的标识符及公钥和用于认证的公私钥，S要在存储目录里保存C的标识符、文件名、文件公钥、块号、服务器号和索引号这些信息，S1,S2,S3,…则保存索引号和文件数据块。其中密钥长度为1024b，其他信息为128b。与传统的远程完整性检查（Remote Integrity Checking, RIC）协议［18］相比，CSDIV协议可以把校验标签保存在服务器，RIC则保存在本地，各实体的存储情况如表3所示，可知CSDIV协议减轻了客户端的存储开销。

4.2 通信开销分析

与RIC协议相比，CSDIV协议利用了同态标签的优势，可将校验标签合并后返回，从而节约了部分通信开销。计算不同文件大小情况下，完成一次验证过程中协议通信的数据总和，如图6所示，可知CSDIV协议降低了验证所需的通信开销。

4.3 时间开销分析

由于PDP和CSDIV协议不用返回所有保存在服务器中的校验标签，所以它们比RIC协议的验证时间要少得多。运行仿真程序，通过对不同大小的文件进行测试，抽查其中10%的数据块，可以得到PDP和CSDIV协议验证所需的时间，如图7所示，可知CSDIV协议比PDP协议所需的验证时间更少。

5 结语

本文提出的云存储中数据完整性验证协议（CSDIV），为用户检查文件的完整性提供了一种有效的方案，从而提高整个云存储系统的可靠性和稳定性。仿真结果表明，系统只需少量的存储开销和通信开销，就能保证该协议的有效执行，并且随着文件的增大，验证所花的时间仍然保持在较低的值，因而该协议适用于云存储中的海量数据处理。

参考文献:

[1] YUMEREFENDI A R, CHASE J S. Strong accountability for network storage ［J］. ACM Transactions on Storage, 2007, 3(3): 6-6.

[2]KUBIATOWICZ J, BINDEL D, CHEN Y, et al. OceanStore: An architecture for globalscale persistent storage ［C］// Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM Press, 2000: 190-201.

[3]MAHESHWARI U, VINGRALEK R, SHAPIRO W. How to build a trusted database system on untrusted storage ［C］// OSDI00: Proceedings of the 4th Conference on Symposium on Operating System Design and Implementation. Berkeley, CA: USENIX Association, 2000: 10-10.

[4]ATENIESE G, BURNS R, CURTMOLA R, et al. Provable data possession at untrusted stores ［C］// CCS07: Proceedings of the 14th ACM Conference on Computer and Communications Security. New York: ACM Press, 2007: 598-609.

[5]ATENIESE G, PIETRO R D, MANCINI L V, et al. Scalable and efficient provable data possession ［C］// SecureComm08: Proceedings of the 4th International Conference on Security and Privacy in Communication Networks. New York: ACM Press, 2008: 1-10.

[6]ATENIESE G, KAMARA S, KATZ J. Proofs of storage from homomorphic identification protocols ［C］// ASIACRYPT09: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. Berlin: SpringerVerlag, 2009: 319-333.

[7]CURTMOLA R, KHAN O, BURNS R, et al. MRPDP: Multiplereplica provable data possession ［C］// The 28th International Conference on Distributed Computing Systems. Piscataway: IEEE, 2008: 411-420.

[8]SHAH M A, BAKER M, MOGUL J C, et al. Auditing to keep online storage services honest ［C］// HOTOS07: Proceedings of the 11th USENIX Workshop on Hot Topics in Operating Systems. Berkeley, CA: USENIX Association, 2007: 1-6.

[9]ZHU Y, WANG H, HU Z, et al. Efficient provable data possession for hybrid clouds ［C］// CCS10: Proceedings of the 17th ACM Conference on Computer and Communications Security. New York: ACM Press, 2010: 756-758.

[10]GHEMAWAT S, GOBIOFF H, LEUNG ST. The Google file system ［C］// Proceedings of the 19th ACM Symposium on Operating Systems Principles. New York: ACM Press, 2003: 29-43.

[11]刘鹏.云计算［M］.北京:电子工业出版社,2010.

[12]CHANG EC, JIA X. Remote integrity check with dishonest storage server ［C］// Proceedings of the 13th European Symposium on Research in Computer Security. Berlin: SpringerVerlag, 2008: 223-237.

[13]BURROWS M, ABADI M, NEEDHAM R M. A logic of authentication ［J］. ACM Transactions on Computer Systems, 1990, 8(1): 233-271.

[14]SYVERSON P F, van OORSCHOT P C. On unifying some cryptographic protocol logics ［C］// SP94: Proceedings of the 1994 IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 1994: 14-28.

[15]冯登国.安全协议――理论与实践［M］.北京:清华大学出版社,2011.

[16]赵晓明,孟庆超,刘军.基于SVO逻辑的X.509协议安全性分析［J］.军事通信技术,2007,28(3):63-67.

[17] EASTLAKE D, JONES P. RFC 3174: US Secure Hash Algorithm 1 (SHA1) ［S］, 2001.

[18]DESWARTE Y, QUISQUATER JJ, SADANE A. Remote integrity checking: How to trust files stored on untrusted servers ［C］// Proceedings of 2004 Conference on Integrity and Internal Control in Information Systems. Berlin: SpringerVerlag, 2004: 1-11.

收稿日期:20110803;修回日期:20110911。 基金项目:国家自然科学基金资助项目（61072080）；福建省自然科学基金资助项目（2011J05148）；福建省教育厅科技项目（JA10079, JB10041）。

作者简介:曹夕（1988-），男，福建福州人，硕士研究生，CCF会员，主要研究方向：网络与信息安全； 许力（1970-），男，福建福州人，教授，博士生导师，CCF高级会员，主要研究方向：无线网络与移动通信、网络与信息安全； 陈兰香（1979-），女，湖北麻城人，讲师，博士，CCF会员，主要研究方向：计算机体系结构、网络存储、信息安全。