云加密数据安全重复删除方法∗

张曙光，咸鹤群，王利明，刘红燕

1(青岛大学 计算机科学技术学院，山东 青岛 266071)

2(广西密码学与信息安全重点实验室(桂林电子科技大学)，广西 桂林 541004)

3(中国科学院 信息工程研究所 第五研究室，北京 100093)

随着大数据时代的到来，作为基础设施的云存储服务变得愈加重要.在云服务持续高速度发展的背景下，服务提供商不再局限于一味地堆积硬件，而是逐步通过尽可能提高存储效率的方式，达到“无形”增加存储空间并换取经济效益的目的.目前，提高存储效率的技术主要包括数据压缩和重复数据删除.数据压缩技术虽然能够通过对整体数据重新编码，实现存储空间的更少占用，但由于压缩后的数据需要在解码后才可正常使用，这无疑增加了系统的计算负担.重复数据删除技术的思想是通过摒除数据的重复存储，进而减少存储冗余[1，2].生而逢时，在如火如荼发展的云计算和大数据应用场景中，同一数据副本时常被不同用户重复存储，造成巨量存储空间浪费，重复数据删除技术恰成为解决该问题的最佳方法.经最新研究表明:重复数据删除技术可以在备份应用系统中减少高达90%的存储需求，在标准文件系统中使存储需求降低约70%[3].

良好的云存储系统应能够为用户提供安全的数据存储环境，然而在实际应用中，云服务提供商并非完全可信.例如，Facebook在2013年泄露了用户的联系信息[4]，iCloud在2014年泄露了用户的私密照片[5].数据加密是解决此类风险的良好选择，然而由于数据的加密密钥由用户在本地独立生成，密钥的多样性导致相同数据副本被加密为不同密文，使得云服务提供商无法识别数据是否重复，造成大量存储冗余.如何对加密后的数据执行重复安全删除，是云存储安全领域的研究热点之一.

起初，研究者提出由云服务商提供唯一密钥并执行加密操作，如此，数据控制权依然驻留在云服务商中，虽然能够抵抗外部敌手攻击，但无法防止数据由服务商内部泄露.Douceur等研究者提出客户端收敛加密(convergent encryption，简称CE)方法[6].计算数据副本的哈希值并将其作为加密密钥，此时输入同一数据副本即可得到相同数据密文[7，8].收敛加密虽拥有较高的执行效率，却未实现语义安全，容易遭受离线暴力破解攻击[9，10].Bellare等研究者提出信息锁加密方案(message-locked encryption，简称MLE)[11]，虽复杂化了密钥计算与加密方式，但与CE相比，其核心思想无变化，因此同样无法实现语义安全[12，13].Bellare等研究者提出了DupLESS[14]，相同数据的不同属主与可信第三方运行茫然伪随机函数计算协议(oblivious pseudorandom function，简称OPF)，用以输出相同加密密钥.Duan等研究者对DupLESS进行扩展与改进，对可信第三方的任务进行分解，将密钥生成过程的参与方扩展为多个用户[15].文献[14，15]中的方案无法抵抗云服务器在线穷举攻击.Puzio等研究者提出首个基于双层加密的重复加密数据删除方案ClouDedup[7]，内层是高效的收敛加密，外层加密与解密工作外包给可信第三方.除了安全性的提高，双层加密带来的还有高额的计算开销与通信开销.与文献[14，15]相似，ClouDedup无法防止云服务商与第三方的合谋攻击.Stanek等人提出:用户在上传数据之前需要确定数据的类型，若数据属主数量低于预定义流行度阈值，则该数据副本将被定义为非流行数据；反之，则将其标记为流行数据[17].非流行数据采用双层加密.随着数据副本数量不断增加，当等于阈值后，云服务商便进行外层解密，进而借助内层收敛加密的特性，执行重复数据删除.同时，为了抵抗敌手进行女巫攻击[16，18]，引入身份服务器.与文献[7]中的方案类似，多方服务器的引入带来高额的计算与通信开销.Puzio等研究者基于完美哈希函数(PHF)设计了数据流行度查询算法，依赖第三方的协助，查询数据副本流行度，并根据查询结果执行相应的加密算法[19].该方案无法解决非流行加密数据重复删除的问题[3]，且与文献[14，15，17]类似，可信第三方实体必须实时在线参与，然而在实际应用中，部署完全可信的第三方比较困难.Liu等研究者设计首个无可信第三方参与的加密数据重复删除方案，使用口令认证密钥交换协议(password authenticated key exchange，简称PAKE)传递密钥，相同数据副本属主能够计算得到同一加密密钥[9].方案的不足点在于，参与方必须实时在线，导致系统的可行性与实用性较低.

本文贡献:

本文在划分数据类型的基础上，提出一种无需初始数据上传用户与可信第三方实时在线的加密数据重复删除方案.

1) 基于椭圆曲线构造流行度查询标签，在语义安全的前提下，使用该标签验证加密副本是否产生于同一明文，并判断其流行度.借助密文策略属性加密，保证查询标签生成协议的安全实现；

2) 设计安全的密钥共享协议，确保同一数据副本的初始属主能够借助云服务商，将加密密钥安全离线共享至后继属主，实现非流行数据重复删除.构造新的流行数据加密算法，增强流行数据的存储安全；

3) 总结常见的敌手模型，通过安全分析证明本方案可抵御敌手模型中的恶意攻击.

1 系统设计与敌手模型

1.1 系统模型

如图1所示，本系统共包含3类实体:密钥生成中心(KDC)、用户群(users)与云服务器(CSP).系统建立初期，KDC为用户生成密钥对集合，并将随机值密文参数集合部署在云服务器，然后转入离线状态.云服务器为用户提供数据的在线存储与共享服务，且具有删除重复加密数据的功能.

1.2 设计目标

本方案需要满足以下性质.

1) 有效性

a) 云服务器能够识别重复的加密数据，并判断数据类型(非流行数据或流行数据)，根据数据类型采取相应加密算法；

b) 数据初始上传者能够将加密密钥通过云服务器，以离线的方式传递给后继上传者；

c) 云服务器能够执行加密数据重复删除.

2) 安全性

a) 使用椭圆曲线生成的查询标签识别数据冗余度与流行度，识别过程不泄漏数据的任何明文信息；

b) 初始上传者将加密密钥以密文形式存储在云服务器，但云服务器无法对其解密；

c) 客户端加密数据重复删除与云服务器端重复数据删除混合使用，防止侧信道攻击.

3) 高效性

a) 保证流行度查询标签生成算法和密钥传递算法的高效性；

b) 针对不同流行度数据，采用不同加密算法，在确保安全性的前提下，提高系统执行效率.

1.3 敌手模型

在数据安全需求方面，用户假定云服务提供商是不可信的；用户在系统效率方面的要求与云服务提供商的存储成本存在一定矛盾.因此，本文不考虑用户与云服务器合谋攻击.由于在重复数据删除方案中，侧信道攻击主要针对客户端重复数据删除(穷举并上传文件，观察是否发生重复数据删除)，而本方案只对隐私度比较低的流行数据使用客户端重复数据删除，因此侧信道攻击问题不是本文的研究重点.

本文的敌手有以下两类.

1) 云服务提供商

云服务提供商能够按照系统所设计的协议与用户执行所有的交互，可以访问或复制用户存储在云服务器上的加密数据、查询标签等所有信息，因此可以对查询标签与加密数据执行离线穷举攻击，其攻击方式为:猜测穷举某数据内容的所有可能，构造查询标签集合并与用户的查询标签进行比较，验证猜测正确性，最终获得数据内容.

2) 用户群中的恶意成员(恶意用户)

恶意用户拥有与合法用户完全相同的访问能力和权限，掌握KDC分配的密钥对.其可能的攻击方式如下.

a) 劫持受害者与云服务器的通信信道，假冒云服务器，与受害者执行方案中的所有交互协议，对受害者的查询标签执行离线穷举攻击，即:穷举猜测某数据内容的所有可能，构造查询标签集合并与用户的查询标签进行比较，验证猜测正确性，获得数据内容；

b) 执行在线穷举攻击，穷举某数据内容的所有可能，逐一构造查询标签并发送至云服务器，根据云服务器的回复消息判断该数据是否已被存储在云服务器.

2 定义与预备知识

2.1 具有离线密钥传递的云加密数据安全重复删除方案

本方案共包含以下4种算法.

a)SystemSet:系统初始设置算法.KDC为用户生成属性密钥对，并为云服务器部署密文参数；

b)PopularityCheck:流行度查询算法.由用户与云服务器共同完成.持有相同数据的用户，可以在不泄露任何数据内容的情况下获得相同的查询标签，进而查询数据流行度；

c)UnPopularDedup:非流行加密数据重复删除算法.由用户与云服务器共同完成.云服务器存储首次上传的加密数据；若云服务器检测到冗余数据被上传，则将其删除，并为当前用户创建数据的访问链接；

d)PopularUpload:流行加密数据重复删除算法.由用户与云服务器共同完成.若拥有某数据的用户数量等于流行度阈值，则用户上传收敛加密密文；若大于流行度阈值，则执行客户端重复数据删除，即:用户无需实际上传加密数据，云服务器会为其创建数据的访问链接.

2.2 有限域上的椭圆曲线

定义有限域GF(P)，其特征P≠2，3，参数a，b∈GF(P)满足4a3+27b2≠0.

定义满足等式y2=x3+ax+b的点(x，y)∈GF(P)×GF(P)与无穷远点O构成的集合为椭圆曲线E(a，b)(GF(P))[20−23].

在下面定义的加法运算下，这些点可构成Abelian群:O是恒等元，假设M，N为E(a，b)(GF(P))上的两个点，若M=O，则−M=O，M+N=N+M=N；设定M=(x1，y1)，N=(x2，y2)，则−M=(−x1，−y1)，且M+N=O；若M=−N，则M+N=(x3，y3)，其中，

2.3 密文策略属性加密

安全的基于密文策略属性加密(CP-ABE)方案通常包含以下算法[24−26].

a)Setup(λ)→〈PK，MS〉:系统初始化.输入安全参数λ，输出密钥对〈PK，MS〉；

b)Encrypt(PK，F，S)→CS:加密算法.输入公钥PK，消息F，访问结构S，输出密文CS；

d)Decrypt(PK，SK，CS)→F:解密算法.输入公钥PK，用户私钥SK，密文CS，其中，访问策略隐含在CS中.当且仅当ATi∈S，才能解密得到消息F[27，28].

3 具有离线密钥传递的云加密数据安全重复删除方案

3.1 方案概述

系统建立初始，KDC通过SystemSet算法为每个注册用户生成属性加密算法的公私钥对，并将密文参数集合部署到云服务器.在PopularityCheck算法中，用户发送数据短哈希值至云服务器，以获取生成查询标签所需要的参数值，并使用椭圆曲线计算流行度查询标签，用以查询数据的流行度.在此之后，云服务器将查询结果回传至用户，并与用户执行UnPopularDedup或PopularUpload，其中，UnPopularDedup表示非流行加密数据重复删除算法，PopularUpload表示流行加密数据重复删除算法.

3.2 SystemSet

1) KDC执行以下算法生成密钥对〈PK，MS〉.

算法1.私钥生成算法.

3) KDC通过以下方式得到密文参数集合，并将其部署在云服务器.

算法2.属性加密算法.

3.3 PopularityCheck

3.3.1 获取生成查询标签所需随机数

Ui选取短哈希函数SH，计算数据Fi的短哈希值shi=SH(Fi)，并发送shi至云服务器(短哈希函数具有较高的碰撞率，相同数据的短哈希值必定相同，不同数据的短哈希值可能相同).

3.3.2 流行度查询

Ui使用随机数向量集合(第3.3.1节中，两种情况下j的取值分别为j∈[1，Nmax]与j=0，将二者合并得到j∈[0，Nmax])与云服务器执行算法3，以查询数据的流行度.

算法3.流行度查询算法.

3.3.3 UnpopularDedup

3.3.4 PopularDedup

4 安全分析与证明

结合前文所述的敌手模型，本节从以下4个方面分析方案的安全性.

4.1 密文参数与查询标签安全性

1) 密文参数安全.

定理1.若ATCSP⊭S，则属性加密方案中的解密算法(Decrypt)无法正常执行，其中，ATCSP表示云服务器属性集合，⊭表示云服务器属性集合无法满足用户属性集合.

证明:由SystemSet可知:

2) 流行度查询标签安全.

云服务器虽持有σi，j与参数密文Xj1，Xj2，然而，由定理1可知，云服务器无法解密Xj1，Xj2，故只能通过以下方式穷举查询标签，以猜测加密数据的明文信息.

a) 穷举数据集合{Fr}r∈[1，n]；

b) 穷举随机参数值集合{xt}t∈[1，n]；

c) 穷举随机参数值集合{μz}z∈[1，n]；

d) 计算标签集合{σCSP=ηi−SKCSP⋅(H(Fr+xtmodn)−μz)}；

e) 将得到的结果与iσ′逐一比较，其中，，观察是否存在相等值；

f) 若存在相等值，则表明Fr=Fi.

然而，由以上可知，云服务器攻击的时间复杂度为O(n3).由于n可视为无限大值，因此在实际应用中，实现第e)步是极为困难的.

4.2 防止假冒云服务器的行为

以下为恶意用户UD假冒云服务器与受害者Ui运行PopularityCheck算法的过程.

a)Ui向云服务器发出执行PopularityCheck请求；

b)UD截获请求消息，发送ηDG，XD1，XD2至t(a)；

c)Ui计算并将发送至UD；

d)UD将查询标签σD=ηD−dD⋅C′发送至Ui；

e) 由于UD持有ηDG，XD1，XD2，因此可以对CD采取离线穷举攻击，即执行以下操作:

①穷举数据{Fr}r∈[1，n]；

② 计算密文集合{Cr}={H(Fr+lD)}；

③与Ci逐一对比.若Cr=Ci，则Fr=Fi.

解决方法:用户在与云服务器通信之前，需要借助公钥基础设施(PKI)获取并验证云服务器身份，借助PKCSP协商会话密钥对通信内容加密.UD便无法仿冒云服务器身份获取有用信息.

4.3 防止用户进行在线穷举攻击

定理3.恶意用户UD无法对云服务器中的非流行数据Fi执行在线穷举攻击.

证明:不失一般性，UD的攻击方式为:

a)UD穷举数据{Fr}r∈[1，n]；

b)UD将穷举结果逐一与云服务器运行PopularityCheck和UnpopularDedup；

d)UD根据响应，判断攻击是否成功.

由UnpopularDedup可知:

4.4 标签唯一性与正确性证明

1) 唯一性证明

2) 正确性证明

5 实验分析

实验采用C++语言，借助OPENSSL[29]，GMP[30]，PBC[31]和CP-ABE[32]函数库实现了系统软件.以阿里云作为云服务提供商，租用虚拟机配置为4Core CPU，8GB内存，1Mbps带宽，1T存储空间.椭圆曲线基域大小设定为512bit，域中元素大小为160bit.随机选取了2 500个文件存储在云服务器中.随机设定拥有每个文件的用户数量.设置流行度阈值为T=8，非流行数据与流行数据的比例大致为3:4.

通过以下3组实验，证明方案的高效性.

a) 上传大小为80MB的文件FA，计算本方案各阶段的时间开销；

b) 上传大小为10MB的文件FB，分别测试本方案与PerfectDedup方案[19]的总时间开销；

c) 上传大小相同的文件，比较本方案、文献[17]中的方案、文献[19]中的方案各自所需的存储开销.

实验中的每步操作重复执行20次，取平均值作为实验结果.

1) 系统每阶段的时间开销.

Fig.2 Time span on each stage of the system图2 系统每阶段的时间开销

如何高效且安全地识别冗余数据，是加密数据重复删除方案的基础.本文对较为优异的现有相关方案的生成查询标签算法进行了效率测试，并与本方案比较.实验结果如图3所示，本方案在生成查询标签方面，明显优于其他方案.

Fig.3 Time span on check tag generation of each scheme图3 各方案生成查询标签所需时间开销

为达到语义安全，本方案需要将初始上传属主的加密密钥安全共享至后继上传属主，这会使数据加密算法产生部分额外通信与计算开销.然而，由于密钥传递方式的设计较为高效，因此它对加密算法的性能影响较小.本方案与CE[6]的比较结果在表1中给出，其中，t(a)表示本方案在执行加密算法时产生的时间开销，t(b)表示执行收敛加密时产生的时间开销，t(b)−t(a)表示执行两种加密算法时产生时间开销的差值，表示以上差值为系统带来影响的大小.实验结果表明:二者加密算法所需的时间开销相差甚小；且随着数据不断增大，差值渐成为可忽略值.

Table 1 Comparison of time span between our scheme and CE表1 本方案与CE方案的时间开销对比

2) 较少的总时间开销.

本方案与PerfectDedup方案[19]所需要的总时间开销对比如图4所示.与PerfectDedup相比，由于本方案不需要进行第三方服务器的数据更新，流行度查询阶段需要的时间开销较小，因此在总时间开销方面，本方案具有较明显的优势.

Fig.4 Comparison of total time span between our scheme and PerfectDedup图4 本方案与PerfectDedup 方案的总时间开销对比

3) 占用更少的存储空间.

通过上传大小为500MB文件，测试本方案、文献[17]中的方案、文献[19]中的方案各自占用云服务器中的存储空间情况，实验结果如图5所示.由于本方案支持非流行数据重复删除，因此能够节省更多的存储空间.文件越大，优势越明显.

4) 方案特点比较.

由上述实验可知，摆脱实时在线第三方的依赖与划分数据流行度，是减少方案计算开销与通信开销的有效方法.表2分析了本方案与其他代表性方案是否具备上述两种方法的特点.

Table 2 Scheme characteristics comparison表2 方案特点比较

Fig.5 A comparison of three schemes of cloud server storage overhead (each file 500MB)图5 3种方案中云服务器存储开销对比(每个文件500MB)

6 总结与展望

本文提出一种无需初始数据上传用户和可信第三方实时在线参与的加密数据重复删除方法.基于椭圆曲线构造流行度查询标签，在语义安全的前提下，使用该标签识别数据冗余度与流行度.借助密文策略属性加密，保证查询标签生成协议与密钥共享协议的安全实现，同一数据副本的初始上传用户能够借助云服务商，将加密密钥安全离线共享至后继上传用户，实现非流行数据重复删除.改进后的收敛加密算法，能够使用户自行计算安全加密密钥，不仅保证了流行数据的存储安全，同时提高了云服务商消除流行重复加密数据的效率.本文最后进行了详细的安全性分析与效率评估，并与其他现有方案对比，证明本方案在满足语义安全的同时，进一步提高了加密数据重复删除系统的执行效率.

在本文基础上设计具有动态更新数据所有权的安全加密数据重复删除方案，是下一步的研究方向.