一种采用签名与哈希技术的云存储去重方案

张桂鹏，匡振曦，陈平华

广东工业大学 计算机学院，广州510006

1 引言

近年来，云计算行业呈现出稳定快速的发展态势。由于云计算产业结构的不断优化和提供云计算服务的企业不断增多，用户数据的处理和存储得到了极大的简化和保障，用户只需将数据存储外包给第三方云存储服务提供商即可。然而，随着存储在云服务器的数据爆炸式增长，数据需要占用的存储空间和传输带宽也将增加。因此重复数据删除技术[1-2]成为了一项急需研究的数据压缩技术，该技术通过计算出的文件标签来检测和消除冗余数据，能够极大地减少存储空间和降低传输带宽消耗，受到了学术界和工业界越来越多的关注。

按照检测文件大小粒度的不同，重复数据删除方案可以分为文件级去重方案[3]和数据块级去重方案[4-5]。文件级去重方案可以消除文件的重复副本，只保留一份文件副本和指向副本的索引；而数据块级去重方案能够消除不同文件中重复数据块，同样只保留一份数据块副本和指向数据块的索引。尽管重复数据删除方案大大提高了数据存储空间利用率，节省了大量磁盘空间，但是由于数据存储在第三方云存储服务器上，这将导致用户无法判断自己数据是否处于安全存储的状态，数据的安全性和隐私性得不到有效的保障，即使用传统的加密算法对数据进行加密，也会导致不同用户的相同数据产生不同的密文，从而影响重复数据删除。

为了解决传统加密算法与重复数据删除不兼容的问题，Douceur 等[6]提出收敛加密算法（Convergent Encryption，CE），使用收敛密钥来加密和解密文件，其中收敛密钥由文件内容通过散列函数计算生成，因此相同的文件会产生相同的收敛密钥，从而生成相同的密文。CE 算法使得重复数据删除得以实现，并已广泛地应用在一些理论研究和去重方案[7-10]中。Puzio等[11]结合CE 算法提出了ClouDedup 方案，引入第三方密钥服务器来对数据再次进行加密，减少客户端的存储空间消耗；Li 等[12]将秘密共享方案与CE 算法结合，提出了CDStore 方案，通过将算法中的随机信息确定化来实现数据的安全去重，有效地减少存储空间；Stanek 等[13]根据文件的流行程度提出了一种面向不同等级的加密算法，分别对流行和非流行文件采用不同的加密模式，来加强对数据的保密性。但由于CE算法缺乏严格的密码学原语定义和形式化的安全模型，以上所提到的结合CE算法的方案都无法应对攻击者进行的暴力破解。

Bellare 等[14]提出了一种新的密码学原语—消息锁加密算法（Message-Locked Encryption，MLE），该算法的提出为收敛加密算法提供了理论依据，然而MLE 只适用于保护具有比较高的不可预测性的数据。2015年，Bellare 等[15]在MLE 的基础上提出了一种扩展MLE 方案，但是iMLE 方案仍停留在理论探索阶段，实用性不高；文献[7]使用基于lockbox原理来存储并加密数据，在数据去重中引入代理重加密技术，保证数据内容无法被猜测获取，但服务器需要承担数量庞大的密钥管理;Li等[16]提出了一种混合云架构的数据去重方案，通过执行额外的加密算法来增强数据的安全性，使得数据只能被具有特定权限的用户访问，但私有云需要承担过大的计算量，不适用于具有较大规模用户量的去重系统。张桂鹏等[17]在混合云架构中引入权限等级函数来计算去重标签，并且用Merkle哈希树来计算权限密钥，有效地降低去重标签和密钥的计算时间开销。Chen 等[18]提出了BL-MLE方案，能够通过少量元数据来实现文件级和数据块级的安全去重，适用于大规模加密文件，然而在去重过程中增加了POW 验证，服务器端的通信消耗过大。为了降低计算开销，Liu 等[19]提出了一种适用于云加密去重系统中的完整性审计方案，该方案能够减少客户端的计算开销，有效地保证了外包数据的机密性和完整性，但仍存在着MLE算法面临的缺陷，亟需进一步进行方案的研究和改进。

为了提高数据的安全性和机密性，实现支持多云存储系统[20]的数据安全去重，提出了一种采用签名与哈希技术的云存储去重方案，主要贡献如下。

（1）在数据去重过程中采用了双层校验机制：全局校验和局部校验。通过双层校验机制能够审计文件的完整性以及精确地定位到损坏的数据块，保证了数据的完整性，有效地防止单一云存储服务提供商对数据进行垄断控制。

（2）改进了传统的云存储去重系统模型，引入多云模型并且在元数据服务器部署密钥和权限服务器，通过构造Merkle哈希树来生成校验值δ，从而计算出去重标签，保证了重复数据能够被检测，降低去重标签的计算开销。

（3）能够有效地支持文件级和数据块级别的重复数据删除，高效地实现了多云存储的安全去重系统。

2 预备知识

2.1 符号说明

符号及说明如表1所示。

表1 符号说明

2.2 代数签名

代数签名是一种具有同态性和代数性的哈希函数，作为一种轻量级的信息签名方式，计算开销较小。代数签名的基本特性是指数据块代数签名的和与所对应得数据块和的代数签名结果一致[21]。设λ 为有限域的一种元素，且向量λ=(λ1,λ2,…,λn)由非零元素组成。由n个数据块(f[1],f[2],…,f[n])组成的文件F 的代数签名计算如下：

其中的代数签名的一些性质如下：

性质1 长度为r 的块f[i]串联f[j]后的代数签名计算式为：

性质2 文件F 中所有数据块的签名总和等于每个数据块的签名总和：

性质3 两个文件F 和G 的代数签名和等于每个文件签名和：

2.3 Merkle哈希树

Merkle哈希树是一种哈希二叉树，所构造的所有节点均为Hash值，叶子节点为数据信息的哈希值，其余非叶子节点由其孩子节点串接后哈希运算得到的，依次从下向上逐层运算，最终将会得到唯一的根节点ROOT，此时Merkle哈希树构造完成。在本方案中，设定Merkle哈希树构造函数为Mroot=MHT({m})，其中{m}为数据信息集合，函数的输出值为该根节点的值Mroot。如图1所示，该Merkle 哈希树的叶子节点A、B、C、D 分别为H(B1),H(B2),H(B3),H(B4)，非叶子节点E=H(H(B1)+H(B2))，F=H(H(B3)+H(B4)，最终能够得到唯一的根节点值G=H(H(E)+H(F))=MHT({Bi})，其中1 ≤i ≤4。

图1 Merkle哈希树构造流程图

2.4 所有权证明算法（POW）

所有权证明算法用来证明用户是否拥有存储在云服务器中的数据，以防止攻击者通过数据指纹信息从服务器中获取完整的文件。服务器需要根据文件生成相应的挑战发送给用户，用户根据拥有的文件，生成正确的应答并返回验证，以此来证明用户确实拥有该文件，在现有文献中已有许多有效的POW，包括基于MHT的POW[22]、BF-POW[23]等。

3 问题阐述

3.1 系统模型

本章将介绍方案中存在的系统模型和安全威胁模型的定义，如图2所示，系统模型包含三种实体模型：用户实体，元数据服务器，多云存储服务提供商实体。

图2 多云环境下的数据安全去重系统模型

用户实体（User）：用户需要将数据文件进行上传存储到MDS 中，以降低文件传输中的带宽，节省存储空间，其中数据文件只需要上传一份，不需要上传重复的文件，在支持访问控制的数据去重系统中，用户上传文件时可设定文件的访问权限，以提供特定的用户进行分享下载。

元数据服务器（MDS）：元数据服务器主要对用户上传的数据文件进行处理，具有一定的存储容量（相比于云存储服务提供商的存储容量则小很多），将处理后的密文存储在MS-CSP上，当用户上传数据文件时，元数据服务器进行安全去重检测来降低存储成本。在本方案中，设定元数据服务器为诚实可信的第三方服务器。

多云存储服务提供商实体（MS-CSP）：多云存储服务提供商由多个不同的云存储服务提供商（S-CSP）构成，主要接收来自MDS 处理加密后的数据文件和相关标签，并合理地存储在其服务器上。在本方案中，假定MS-CSP具有充足的存储容量和计算能力。

3.2 威胁模型和安全目标

在本方案中，威胁模型主要考虑了两种类型的攻击者：外部攻击者和内部攻击者，外部攻击者和内部攻击者都试图通过公共信道尽可能多地获取到存储在MS-CSP 的数据信息，外部攻击者未拥有有效的权限，会企图伪装成合法的用户来与MDS 进行交互；内部攻击者拥有部分有效的权限，可以看作是诚实而又好奇的用户，也会上传文件与MDS和MS-CSP进行交互，试图获取到其他用户的数据密文或者加密密钥。因此在基于MDS 为诚实可信的第三方前提下，安全模型提出了以下安全性要求，包括数据的安全性和数据的完整性。

数据的安全性：包括了去重标签和密文的安全性，非授权的用户或者没有被身份认证的用户将无法获取到任何的去重标签，只有被授权的用户在MDS 的验证通过下，才能通过与私有云进行交互计算来获取文件的去重标签，从而执行数据重复检测操作。在本方案中，去重标签通过采用了Mapbox和Lockbox结合的机制来加密，有效地抵制了暴力攻击，同时加密密文的密钥只保存在MDS，非授权的用户即使进行串谋，也无法通过获取密钥来解密密文。

数据的完整性：由于数据文件是由多个不同的S-CSP进行存储管理，存储在MS-CSP的数据将会面临着被攻击者进行窃取损坏，或者其中某些S-CSP进行的恶意串谋行为等风险，数据的完整性要求MDS 能够检测出数据是否完整，即使数据被损坏，也能检测出存储在哪些S-CSP的数据遭受攻击损坏，使得用户不需担心数据被恶意替换损坏。

4 方案实现

4.1 基本思路

本方案改进了传统的云存储去重系统模型，在上传文件时，用户通过构造Merkle哈希树来生成校验值，从而计算出去重标签，保证了重复数据能够被检测。MDS对来自用户的数据文件进行预处理，采用Mapbox 和Lockbox结合的机制来加密数据信息，保证非授权的用户无法对文件进行访问，在下载文件时，使用双层校验机制能够检测出数据是否完整，也可以定位到丢失损坏的数据块，高效实现了支持文件级和数据块级的数据安全去重系统。

4.2 系统初始化

设定用户身份标识为ID（ID可由加密的用户名，密码等组成），用户所拥有的权限集为PU，用户设定上传文件F 的访问限制权限集为PF，云存储服务提供商的数量为n；在本方案中，数据去重是基于多个独立的S-CSP环境下执行的，此时的文件是由多个S-CSP进行协同存储，而不再是由单一的S-CSP 存储，每个S-CSP都存储着数量不定的数据块，在缺少其他S-CSP的协同下，单一的S-CSP 将无法获取到完整的文件，有效地避免传统单一的S-CSP对用户文件进行垄断控制。

4.3 用户认证

为了确保数据文件的安全性，用户在上传文件之前，需要与MDS之间进行身份认证.首先用户将身份标识ID 和所具有的权限PU发送给MDS，MDS 进行身份认证[24]并输出验证结果，如果验证结果不通过，MDS将停止当前的数据操作，拒绝用户与MS-CSP进行数据交互；如果验证通过，则继续执行下列操作。

4.4 文件上传

文件上传过程包括文件级和数据块级的安全去重过程，用户先执行文件级数据去重，当检测结果为文件不重复，则再将文件切分成数据块，进而执行细粒度更小的块级去重，具体的操作流程如下：

用户选取哈希函数H1、H2，计算文件F 的去重标签ϕFi=H2(H1(F⊕δ))，用户将去重标签ϕFi发送给MDS，其中ϕFi用于对文件F 的重复检测，MDS 并将检测的结果返回给用户。

若检测结果为：文件F 为重复，则进行以下操作。

MDS将与用户之间运行POW算法，通过所有权证明的检测来判定用户是否确实拥有文件F ，如果没有通过所有权证明，MDS将停止与用户进行数据操作，拒绝用户访问当前的文件；如果通过所有权证明，MDS通知用户不再上传文件F ，授权允许用户拥有该文件F并返回指针给用户，以便用户访问文件，用户无需再上传文件F。

若检测结果为：文件F 为不重复，MDS选取一密钥kB，将密钥kB发送给用户，用户进而执行数据块级别的重复检测删除：

用户计算出每一块数据块Bi的去重标签ϕBi=H2(H1(B)⊕kB)，将去重标签ϕBi发送给MDS，其中ϕBi用于对数据块Bi的重复检测，MDS 根据文件的访问限制权限PF选取权限密钥kp，并将检测结果返回给用户。

若检测结果为：数据块Bi为重复，则进行以下操作。

MDS同样需要与用户之间运行POW算法，如果通过所有权证明，MDS通知用户无需再上传数据块Bi，并更新Lockboxi结构信息，同时使用密钥kp对Lockboxi进行解密，即Mapboxi=Decrypt(kp,Lockboxi)，更新该数据块Bi的Mapboxi信息并返回块指针给用户，以便用户访问相应的数据块。如果没有通过所有权证明，MDS 将停止与用户进行数据操作，拒绝用户访问当前的数据块Bi。

若检测结果为：数据块Bi为不重复，则进行以下操作。

用户将文件校验值δ 和数据块Bi发送给MDS，MDS将生成数据块Bi的Mapboxi结构，来记录数据块Bi的位置和标签，Mapboxi结构包括了数据块序号Numi、文件标签信息ϕFi、数据块标签信息ϕBi、存储的位置地址σi；接着MDS 使用用户的权限密钥kp对Mapboxi进行加密，来生成数据块Bi的Lockboxi结构，即结构还记录该数据块的IDi，用户的访问限制权限PF，Lockboxi结构能有效防止Mapboxi信息泄露，只有用户权限符合权限PF，才能对Mapboxi信息进行访问。

MDS对数据块Bi进行加密，得到密文Ci=Encrypt(kB,Bi)，同时使用代数签名计算出数据块Bi的签名信息Γi=Sλ(f[i]||Lockboxi)，将权限密钥kp和密钥kB存储在MDS 所部署的权限和密钥管理服务器上，并将所得到的数据{Ci、Γi}一起发送到MS-CSP，MS-CSP存储后将会返回块指针σi，指针σi记录着密文Ci的存储位置，包括所在的S-CSP编号和排列位置。

4.5 文件下载

当需要下载文件F ，用户发送下载请求给MDS，MDS 获取到该用户的权限密钥kp，先验证用户所具有的权限PU是否符合文件访问权限PF。当验证通过时，MDS 获取存储在MS-CSP 的数据信息{Ci、Γi} ，MDS 使用密钥kB对密文Ci进行解密，得到数据块，此时需要对下载到的数据块执行双层校验机制，即全局校验和局部校验，具体操作如下：

（2）MDS 先计算出Sλ(Lockboxi) ，将Sλ(Lockboxi)与同时下载到的签名信息Γi进行异或运算，得到

（3）MDS 对下载到的数据块Bi分别计算出其代数签名，得到S′λ(f[i])，只要检测到S′λ(f[i])与Sλ(f[i])不相同，则说明该数据块Bi已经遭受损坏，通过附加的数据块标识σi可确定存储数据块Bi的S-CSP的代号和排列位置。

5 安全性分析

本文方案通过全局校验和局部校验来校验文件的完整性以及精确地定位到丢失损坏的数据块，保证了数据的完整性，并且采用Mapbox 和Lockbox 结合的机制来加密数据信息，使得非授权的用户无法对文件进行访问；在假定MDS为可信第三方的前提下，本章将从以下两方面进行安全性分析，即数据安全性和数据的完整性。

5.1 数据的安全性

数据安全性包括了去重标签的安全性和密文的安全性。本方案所采用去重标签生成算法与传统的标签生成算法不同，传统的标签生成算法通过对数据文件进行哈希运算获得，即ϕ=TagGen(F)=H(F)，当攻击者知道数据文件F属于有限可预测的文件集合{F1,F2,…,Fn}，攻击者通过对集合的数据元素进行哈希运算并将结果与ϕ 进行逐一对比，以此能够猜测出数据内容F，在本方案中，文件级的去重标签计算需要校验值δ 的参与，而校验值δ 是通过Merkle哈希树的构造来生成，对于相同的文件F、δ 和ϕFi也将保持一致，一方面能够保证了重复数据能够被检测，另一方面即使攻击者得知数据文件F 的相关信息，由于无法推测出校验值δ，因而也猜测不出数据内容F ，有效地抵制了攻击者进行的暴力攻击。

对于密文信息的安全性，本方案使用Mapbox 和Lockbox 结合的机制来加密数据信息，数据文件被分割成若干个数据块Bi，Mapbox 存储着数据块Bi的地址标签等相关信息，而Lockbox 存储着数据块的IDi访问限制权限和已加密的Mapbox。外部攻击者或非授权的用户由于缺少有效的权限密钥kp，将无法通过MDS的权限验证来与其进行交互；内部攻击者即使通过公共信道获取到了其他用户的Lockbox，也无法分辨出其中的数据信息来解密出Lockbox；在假定MDS为可信第三方的前提下，密文C 和签名信息Γi存储在MS-CSP，而解密密钥kB只存储在MDS中，在MDS未授权的情况下，S-CSP 将无法获取到密钥kB的任何信息，因此即使SCSP与未授权的用户进行共谋，也无法通过伪造密钥kB来解密密文。

5.2 数据的完整性

在下载文件时，需要对数据的完整性进行双层校验，本方案采用的全局校验能够检测出文件F 的完整性，即所切分成的数据块是否存在丢失损坏，数据块Bi一旦发生丢失损坏，生成的校验值δ 会立即改变，通过校验值δ 可判断文件是否完整。局部校验通过密文附加的签名信息Sλ(f[i])来能够定位到丢失损坏的数据块，包括两种情况：如果某一数据块Bi的S′λ(f[i])不存在，即该数据块Bi已经缺失，如果某一数据块Bi的S′λ(f[i])与计算出的Sλ(f[i])不同，即该数据块Bi已遭损坏，并且通过标识σi可确定该损坏数据块Bi原先存储的S-CSP代号，以此进行问责。

6 性能分析与实验评估

本章将提出的方案与文献[16]所提出的文件级去重方案进行仿真实验对比，本方案的仿真实验环境是在i5-7300HQ 的CPU，内存8 GB，主频2.50 GHz 的64 位PC机上实现的，采用Java语言编程进行性能仿真测试。

实验1 测试不同文件大小下去重标签生成的时间开销，实验分别选取文件大小为20 MB、40 MB、60 MB、80 MB、100 MB和120 MB，在数据块大小为6 KB，权限数目恒定的情况下进行仿真测试，实验结果如图3 所示。随着文件大小越大，两个方案中去重标签生成所需要的时间开销也会随之增加，本方案与文献[16]方案相比，在计算去重标签所需要的时间开销会更少，并且在文件大小越大的情况下，时间开销差异会更加明显。

图3 不同文件大小下的去重标签生成的时间开销

实验2 测试不同文件大小下密文生成的时间开销，实验分别选取文件大小为10 MB、20 MB、30 MB、40 MB、50 MB、60 MB、70 MB、和80 MB进行仿真测试，数据块的大小恒为16 KB。实验结果如图4 所示，当文件大小越大，密文所需要的计算时间开销也会增加，本方案中对数据块采用的是对称加密算法，可以看出文件大小和密文生成的时间开销趋向于一定的线性关系。

图4 不同文件大小下的密文生成的时间开销

实验3 测试不同数据块数目下校验值δ 的计算时间开销。在实验中，使用3 组数据块大小分别为4 KB、8 KB和16 KB进行仿真测试，实验结果如图5所示。校验值δ 所需要的计算时间开销随着数据块数目增多而单调递增。并且数据块大小越大，需要的时间开销也将越多，当数目增多时，数据块大小对于所需时间开销的影响也将更加明显；从图中可看出，数据块大小为4 KB 和8 KB 的曲线仅仅呈现出缓慢增长趋势，而数据块大小为16 KB 时，计算哈希值的时间开销将明显增多，总计算时间开销也会明显增大，其曲线大致保持线性增加。

图5 不同数据块数目下的校验值δ 的计算时间开销

7 结束语

本文提出了一种采用签名与哈希技术的云存储去重方案，能够有效地支持文件级和数据块级的加密数据去重检测，实现了细粒度的去重。同时，采用Mapbox和Lockbox结合的机制来加密数据信息，使得非授权的用户无法对文件进行访问。进行下载文件时，由代数签名构成的双层校验机制，能够校验文件的完整性以及精确地定位到丢失损坏的数据块，保证了数据的完整性；安全性分析表明，方案能够有效地抵制攻击者进行的暴力攻击。仿真实验结果表明，方案能有效地降低去重标签的计算开销，减少存储空间。今后的研究工作主要集中在数据去重过程中，保护各参与方的隐私信息不被泄露，同时提出相应的策略来高效地执行大数据环境下的数据检测去重操作。