由于许多IT企业相继推出了云计算相关服务，促进了该技术的发展，用户通过云存储保存的数据量也逐渐庞大，增长速度也日益加快。根据IDC(International Data Corporation)的一份报告显示，到2020年世界上数据量的总和将会超过44 ZB。巨大的存储空间需求与现有的存储能力产生了冲突。云服务提供商解决这一冲突的最佳方式是采取云存储数据去重技术，近期的一些研究成果也表明，在云存储中存在着大量的重复数据，而实验也表明重复数据删除可减少0%~95%的存储空间。
与数据的本地存储不同，云存储使用户失去了对数据的绝对控制权，用户便有了更多的安全担忧。显然，用户希望对数据加密后再上传到云存储服务器，但不同的密钥加密数据后会产生不同的密文，这样重复数据删除也就变得不可能，因此，如何化解数据去重与数据安全之间的矛盾，实现安全的数据去重技术已成为企业及科研机构的一个重要任务。
收敛加密技术缓解了重复数据删除系统的安全问题。收敛加密技术通过取数据的哈希值作为密钥，并以此加密数据，使相同的数据原文在同一加密密钥下得到相同的密文，实现了对重复数据的删除。然而由于加密方式的确定性，收敛加密也有相应的安全缺陷，假如恶意用户知道密文C对应的原文数据在一个元素数量有限的集合{D1, D2, …, Dn}中，恶意用户可以加密Di(i∈{1, 2, …, n})，得到密文Ci，若判断出C与Ci相等，则Di就是C对应的原文数据。基于这种情况，现在也出现了一些对收敛加密技术进行改进的方案。
针对以上所述问题，本文采取收敛加密技术实现重复数据的删除，同时通过所有权证明解决收敛加密的安全缺陷；此外，为了降低所有权证明的时间开销，提出一种基于布隆过滤器进行所有权证明的方案。当用户向服务器发送文件存储请求，且服务器判定数据已存在重复时，服务器随机选取J个文件块，让用户计算相应的挑战信息，服务器通过布隆过滤器对用户计算结果进行验证，当J个验证结果在布隆过滤器的位置都为1时，则所有权证明通过，服务器授予用户该文件的访问权限。
1 研究现状重复数据删除技术通过检测并发现冗余数据而对数据只保留一份存储来节省存储空间[1]。不仅越来越多的学者和科研机构发表关于重复数据删除的理论研究成果，而且一些商业系统也将重复数据删除技术应用到实践中。为了能对数据进行重复删除的同时保证数据的安全性，Douceur等[2]首先提出了收敛加密技术，其是一种由数据的哈希值作为密钥的确定性加密技术，收敛加密在进行重复数据删除的同时很好地实现了数据机密性保护[3-4]，如Bitcase、Ciphertite等商业系统采用了收敛加密技术[5]。然而收敛加密具有易受字典攻击、选择明文攻击等特点[6]，其仅能保护不可预测数据，对于可预测数据的保护是比较脆弱的，但是现实中大多数数据都是可预测的。于是为了克服这一安全缺陷，Puzio等[7-8]实现了ClouDedup 方案，在对数据进行收敛加密的基础上又引入一个单独的密钥服务器KS对数据再次加密。由于KS的密钥是唯一的，因此也能对重复数据进行删除。Bellare等[9]实现了DupLESS方案，DupLESS中用户借助一个密钥服务器通过OPRF(Oblivious PseudoRandom Function)协议获得加密密钥，并用此密钥加密数据，很好地防止了字典攻击；同时针对收敛加密的理论缺陷，Bellare等[10]提出了MLE(Message-Locked Encryption)这一密码学定义，为收敛加密提供了理论依据。此外，重复数据删除包括文件级重复数据删除[11]和文件块级重复数据删除[12]，而对于文件块级重复数据删除由于对文件进行分块，提高了重复删除的效率，但却引入了密钥管理难度提升等问题[13-14]。为了降低密钥管理的难度，Li等[15]借助(n, k, r)-RSSS(Ramp Secret Sharing Scheme)分享函数，通过大于r个KM-CSP的通信得到收敛密钥，提出了高可靠性的Dekey方案；Zhou等[16]实现了多级密钥管理的SecDep方案，在用户之间的数据进行文件级重复删除，在用户本身的数据进行文件块级重复删除。用文件级密钥对文件块级密钥进行加密，而文件级密钥则被划分成多份子密钥后分发到多个密钥服务器中，避免了密钥数量随着不同文件与文件共享数的增加而线性增长，同时又实现了密钥管理的高可靠性。
在重复数据删除系统中，一份数据仅需存储一次，后续相同数据就不再存储，而是对用户分配访问控制权限。为了验证用户确实持有数据，Halevi等[17]率先引入了“所有权证明”(Proof of oWnership, PoW)的概念，只有当用户拥有完整的数据时可以通过验证，而仅拥有部分数据则无法通过验证；文献[18]在云存储系统中引入了PoW算法；文献[19]基于PoW算法提出同时提高安全性与效率的Proof of Storage with Deduplication(POSD)数据去重解决方案；Pietro等[20]提出基于挑战/应答机制的PoW算法，使带宽开销和计算开销不依赖于输入文件的大小，提升了效率的同时又具有很高的安全性；Blasco等[21]提出了基于布隆过滤器的PoW方案，由服务器初始化布隆过滤器，通过文件块验证信息与布隆过滤器对比，以判断用户是否拥有数据，在效率方面有着显著的提高；但文献[21]中并未涉及到数据的安全性问题。
2 研究思想及系统模型本文方案的研究思想为：以收敛加密为核心，以基于布隆过滤器的所有权证明方式降低数据访问授权的时间开销，并以全局文件级去重与局部文件块级去重相结合降低存储空间开销。方案系统模型如图 1所示。
|
图 1 方案系统模型 Figure 1 Scheme system model |
收敛加密保证了相同的数据加密后会产生相同的密文，保证了对重复数据的删除。用户通过密钥产生函数计算出数据密钥，用标记产生函数计算出数据标记，并将数据标记上传到服务器进行重复性检测，当服务器存在相应标记则证明数据重复。涉及到的函数如下：
1) GenKey(D) Key。Key是收敛密钥产生算法通过计算数据D的哈希值所得。
2) Encrypt(Key, D) C。由Key与D作为输入，通过对称性与确定性加密算法计算出D对应的密文C。
3) Decrypt(Key, C) D。由Key与C作为输入，通过对称解密算法计算出密文C对应的原文D。
4) GenTag(D) T。GenTag是标记产生算法，将数据D作为输入，计算出D对应的标记T；此外，本文也允许使用函数GenTagC(C)T，即由密文C产生数据D的标记。
2.2 所有权证明算法所有权证明算法(PoW)是在客户端进行重复数据删除时提升安全性的有力措施，是由服务器与客户端共同参与的一种交互式算法。算法执行时，服务器向客户端发出验证请求，客户端计算数据D对应的哈希值h(D)并上传到服务器；服务器计算数据D哈希值h′(D)与客户端上传的哈希值进行对比：若二者值相同，则所有权证明通过；否则所有权证明失败。
2.3 布隆过滤器布隆过滤器是一种具有较高空间效率的概率性数据结构，由一个较长的二进制向量和一系列随机映射函数组成，用于判断一个元素是否属于特定的集合。布隆过滤器的主要优点是其具有较少的查询时间和较低的空间复杂度。然而布隆过滤器的一个缺陷是其存在一定的错误概率，即一个不属于集合的元素被误判为属于集合，而且集合中元素越多错误的概率就越大，相反的情况则不会出现；另一个缺陷就是不可以删除已存在的元素。
对于将集合G={G0, G1, …, Gn-1} 中的元素插入到布隆过滤器中，首先长度为m比特的布隆过滤器{b0, b1, …, bm-1}被初始化，所有比特位均为0。此外布隆过滤器需要k个独立的哈希函数{h1, h2, …, hk-1}能产生在 0~m-1均匀分布的哈希值。对于任意一个元素Gi(G(0≤i≤n-1) ，分别计算Gi对应的k个哈希函数值h1(Gi), h2(Gi), …, hk-1(Gi)，再将k个哈希值在布隆过滤器对应位置全部置为1。若验证任意元素e是否属于G，只需检测布隆过滤器中h1(e), h2(e), …, hk-1(e)位置的比特是否全部为1，当存在某一位置为0证明e不属于G，否则e属于G。而出现错误情况的概率为
基于文件块的细粒度重复数据删除，可以显著提高存储空间利用率。由于不同用户存储数据的冗余主要来自于相同的文件，所以方案提供全局的重复文件的删除；此外，有关检测到不存在重复的文件，在属于该用户的数据中进行局部文件块级重复删除，即当用户存储数据时，首先计算文件标记，进行文件级重复删除：若存在重复，则对文件进行所有权证明；若不存在重复，用户对文件分块，服务器在用户自有的数据范围内进行重复性检测，而用户仅需将不存在重复的文件块存储到服务器。
3 方案实现本方案通过收敛加密保护数据的安全性，同时能对重复的数据进行删除；此外利用布隆过滤器对数据所有权进行证明，提高所有权证明的效率。由于方案在客户端进行重复数据检测，因此只考虑数据的存储、取回以及数据的访问授权，具体步骤和细节的阐述如下：
3.1 系统初始化S1:用户初始化收敛加密方案的四个算法(GenKey, Encrypt, Decrypt, GenTag)，此外还需初始化用于所有权证明的PoW算法；
S2:存储服务器初始化用于存储元数据如文件标记、布隆过滤器的存储系统，其次初始化用于存储数据和密钥的文件存储系统。
3.2 文件存储用户存储文件F的过程如下。
S1:用户首先计算文件F的标记T，上传到服务器进行重复性检测。
S2:服务器根据T进行重复检测，并返回结果0(无重复)或1(存在重复，转到S3′)给用户。
S3:若返回结果为0，则用户对文件F进行分块{B1, B2, …, Bn}，首先分别计算每一块的哈希密钥h(Bi)(1≤i≤n)，然后对每一块都加密为CBi；然后计算块标记T(CBi)，分别上传到存储服务器。
S4:服务器在用户拥有的文件块范围内对块Bi(1≤i≤n)进行重复检测，并将结果返回给用户。
S5:若用户使用同一私钥userKey，则需用私钥userKey对不存在块对应的密钥进行加密，将相应密钥密文{C(h(Bi))}与块密文{CBi}上传到存储服务器;否则计算全部密钥密文和块密文上传到存储服务器。
S6:服务器对块密文{CBi}与密钥密文{C(h(Bi))}进行存储，同时初始化一个该文件的布隆过滤器和哈希函数H。对于每一密文块CBi，根据其摘要信息计算相应的块代号Ri，由Ri和i通过HMAC_SHA1算法计算出用于布隆过滤器验证的Li，最后计算Li关于H的哈希值H(Li)。将布隆过滤器中H(Li)对应位置的比特置为1，然后返回给用户所有块密文{CBi}对应的指针。
S3′:若返回结果为1，则向服务器请求文件的访问权限。
S4′:服务器对用户进行所有权证明，随机挑选J个文件块{CBj}(1≤j≤J)，请求用户计算块代号{Rj}。
S5′:用户对文件F进行分块{B1, B2, …, Bn}，首先计算所有块的收敛密钥{h(Bi)} (1≤i≤n)，对请求中的J个文件块加密为{CBj}；并计算请求中J个文件块的代号{Rj}，再上传到服务器。
S6′:服务器收到{Rj}，计算相应{Lj}与{H(Lj)}:若布隆过滤器中{H(Lj)}位置的比特均为1，则返回给用户文件块的指针；否则返回给用户警告信息。
S7′:用户存储文件块的指针，并用私钥userKey将块密钥{h(Bi)}加密为{C(h(Bi))}，然后上传至服务器。
S8′:服务器对密钥密文{C(h(Bi))}进行存储。
3.3 文件取回用户取回文件F时的详细步骤如下：
S1:用户向服务器发送取回请求，同时发送请求文件F的文件名和文件ID。
S2:服务器收到请求，首先核对用户的ID:若无访问权限则返回警告；若有访问权限则将文件块密文{CBi}(1≤i≤n)和密钥密文{C(h(Bi))}返回给用户。
S3:用户收到返回结果，首先用自己的私钥userKey对密钥密文{C(h(Bi))}进行解密，恢复出的密钥{h(Bi)}，再对{CBi}进行解密得到{Bi}，从而恢复出文件F。
4 实验仿真 4.1 实验条件本节将对文献[17]和文献[18]中的Baseline方案与本文提出的基于布隆过滤器的BF方案进行了一系列的实验对比。在实验中随机选取了大量的文件，文件大小在64 KB至32 MB之间；所有的标记都通过SHA-1算法计算得到，收敛加密的密钥通过SHA-256算法计算得到；在所有权证明阶段，Baseline方案使用了SHA-1算法，BF方案中客户端使用了SHA-1算法，服务器端采用了HMAC_SHA1算法；当文件大小为64 KB时，3.2节中J值为1，其他情况下J值为文件块总数的25%；对Baseline和BF进行测试，其中设置32 KB为文件分块大小的固定值，最后得出实验结果并分析实验的结论。
4.2 实验结果与结论实验测试了在文件块无重复和文件重复的两种情况不同大小文件存储过程中的时间开销。首先，当文件中所有的文件分块都不存在重复时，Baseline方案主要包括计算文件标记，对文件进行分块，分别计算各块收敛密钥，对文件块加密，由文件块密文计算块标记进行块级查重，客户端用私钥对收敛密钥加密，服务器计算文件块对应的哈希值。
由图 2可知，BF方案的效率优于Baseline方案；当文件大于16 MB时，时间开销增长较快。因为文件过大时文件分块数急剧增多，服务器在Baseline方案中计算文件块哈希值的开销或BF方案中初始化布隆过滤器的开销快速增长。
|
图 2 文件块无重复的总时间开销 Figure 2 Total time overhead for file blocks without duplication |
当文件首次存储时，由于服务器需要初始化布隆过滤器占用了很大的时间开销，所以此时BF方案较Baseline方案在效率方面优势不太明显；但当文件存在重复时，服务器需要对客户端进行所有权证明。BF方案效率要明显优于Baseline方案。
|
图 3 文件块无重复的服务器时间开销 Figure 3 Server time overhead for file blocks without duplication |
|
图 4 基于布隆过滤器的所有权证明时间开销 Figure 4 Time overhead of PoW |
此外，当客户端存储的文件存在重复时，Baseline方案中客户端计算文件标记、对文件分块、通过计算文件块收敛密钥对块加密、计算块密文哈希值用于所有权证明，最后用私钥对收敛密钥进行加密并上传到存储服务器。由图 5可知随着文件的增大，BF方案相对于Baseline方案的优势也越来越明显。
|
图 5 文件重复时的总时间开销 Figure 5 Total time overhead for file blocks with duplication |
BF方案中，用户在进行文件块级重复删除时，由于只在该用户拥有访问权限的数据范围内进行重复检测，对于已存在的文件块就无需进行所有权证明，因此便节省了时间开销；其次，对于重复的文件块，其相应的密钥已经上传至存储服务器，用户就无需再上传，节省了密钥所占的存储空间，避免了密钥数量随着文件数量的增多和文件共享用户数的增多而线性增长。
为了验证上述时间与空间开销的降低，本次实验随机选取大小为16 MB的文件，进行了多次重复实验。在文件分块后进行重复检测，以检测结果中重复比率即文件块重复的数量与文件块总数的比值为横坐标，当横坐标值分别为0、25%、50%和75%时，得出对密钥进行加密时间开销和密钥空间开销的变化趋势。
在BF方案中，由于文件块重复率的提升使得客户端需要对收敛密钥加密的数量随之减少，因此对密钥加密的时间开销相应降低。而Baseline方案中客户端需对所有密钥加密，对密钥加密时间固定。
图 6中，由于Baseline方案对文件块进行了全局的重复检测，最后客户端需要对文件块的所有收敛密钥加密并上传到服务器，因此文件块重复率的变化对密钥空间无影响；而BF方案客户端最终需要上传到服务器的仅为不重复文件块对应密钥的密文，所以消耗的密钥空间随着文件块重复率的提升而线性降低。
|
图 6 加密收敛密钥的时间开销 Figure 6 Encryption convergence key time overhead |
|
图 7 加密密钥的空间开销 Figure 7 Space overhead of encryption key |
当一个元素e不属于集合G，通过布隆过滤器验证e与G的从属关系时，可能会产生e属于G的误判情况，这是因为布隆过滤器初始化过程中将G中所有元素哈希值对应位置的比特置为1，而e的哈希值在布隆过滤器中对应位置比特恰好已被置为1, 同时对于一个确定的布隆过滤器产生误判的概率为
本文将基于布隆过滤器的所有权证明算法应用到重复数据删除方案中，提高了所有权证明的效率。此外，通过用户之间的文件级重复删除和用户内的文件块级重复删除，解决了密钥数量随着数据的增多和数据共享用户数的增多而线性增长的问题，但由于方案中引入了关于文件的布隆过滤器，增加了存储空间的开销；而且布隆过滤器大小固定，对于较小的文件，相对空间利用率较低，因此，下一步的研究工作是使布隆过滤器的大小随文件大小动态变化，更加合理地利用存储空间。
| [1] | 杨超, 张俊伟, 董学文, 等. 云存储加密数据去重删除所有权证明方法[J]. J计算机研究与发展, 2015, 52 (1) : 248-258. ( YANG C, ZHANG J W, DONG X W, et al. Proving method of ownership of encrypted files in cloud de-duplication deletion[J]. Journal of Computer Research and Development, 2015, 52 (1) : 248-258. ) |
| [2] | DOUCEUR J R, ADYA A, BOLOSKY W J, et al. Reclaiming space from duplicate files in a serverless distributed file system[C]//Proceedings of the 22nd International Conference on Distributed Computing Systems. Washington, DC:IEEE Computer Society, 2002:617-624. |
| [3] | MARQUES L,COSTA C J. Secure deduplication on mobile devices[C]//Proceedings of the 2011 Workshop on Open Source and Design of Communication. New York:ACM, 2011:19-26. |
| [4] | XU J, CHANG E-C, ZHOU J. Weak leakage-resilient client-side deduplication of encrypted data in cloud storage[C]//Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communication Security. New York:ACM, 2013:195-206. |
| [5] | DUAN Y T. Distributed key generation for secure encrypted deduplication:achieving the strongest privacy[C]//Proceedings of the 6th Edition of the ACM Workshop on Cloud Computing Security. New York:ACM, 2014:57-68. |
| [6] | HARNIK D, PINKAS B, SHULMAN-PELEG A. Side channels in cloud services:deduplication in cloud storage[J]. IEEE Security and Privacy, 2010, 8 (6) : 40-47. doi: 10.1109/MSP.2010.187 |
| [7] | PUZIO P, MOLVA R, ONEN M, et al. Block-level de-deduplication with encrypted data[EB/OL].[2016-01-16].http://www.eurecom.fr/en/publication/4326/download/rs-publi-4326.pdf. |
| [8] | PUZIO P, MOLVA R, ÖNEN M, et al. ClouDedup:secure deduplication with encrypted data for cloud storage[C]//Proceedings of the 2013 IEEE 5th International Conference on Cloud Computing Technology and Science. Washington, DC:IEEE Computer Society, 2013,1:363-370. |
| [9] | BELLARE M, KEELVEEDHI S, RISTENPART T. DupLESS:server-aided encryption for deduplicated storage[C]//Proceedings of the 22nd USENIX Conference on Security. Berkeley, CA:USENIX Association, 2013:179-194. |
| [10] | BELLARE M, KEELVEEDHI S, RISTENPART T. Message-locked encryption and secure deduplication[C]//Advances in Cryptology-EUROCRYPT 2013, LNCS 7881. Berlin:Springer, 2013:296-312. |
| [11] | WILCOX-O'HEARN Z, WARNER B. Tahoe:the least-authority file system[C]//Proceedings of the 4th ACM International Workshop on Storage Security and Survivability. New York:ACM, 2008:21-26. |
| [12] | LI J, CHEN X F, XHAFA F, et al. Secure deduplication storage systems supporting keyword search[J]. Journal of Computer and System Sciences, 2015, 81 (8) : 1532-1541. doi: 10.1016/j.jcss.2014.12.026 |
| [13] | MEISTER D, BRINKMANN A. Multi-level comparison of data deduplication in a backup scenario[C]//Proceedings of SYSTOR 2009:the Israeli Experimental Systems Conference. New York:ACM, 2009:Article No. 8. |
| [14] | MEYER D T, BOLOSKY W J. A study of practical deduplication[J]. ACM Transactions on Storage, 2012, 7 (4) : 14. |
| [15] | LI J, CHEN X, LI M, et al. Secure deduplication with efficient and reliable convergent key management[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25 (6) : 1615-1625. doi: 10.1109/TPDS.2013.284 |
| [16] | ZHOU Y, FENG D, XIA W, et al. SecDep:a user-aware effcient fine-grained secure deduplication scheme with multi-level key management[C]//Proceedings of the 201531th Symposium on Mass Storage Systems and Technologies. Washington, DC:IEEE Computer Society, 2015:1-14. |
| [17] | HALEVI S, HARNIK D, PINKAS B, et al. Proofs of ownership in remote storage systems[C]//Proceedings of the 18th ACM Conference on Computer and Communications Security. New York:ACM, 2011:491-500. |
| [18] | GONZÁLEZ-MANZANO L, ORFILA A. An effcient confidentiality-preserving proof of ownership for deduplication[J]. Journal of Network and Computer Applications, 2015, 50 : 49-59. doi: 10.1016/j.jnca.2014.12.004 |
| [19] | ZHENG Q, XU S. Secure and efficient proof of storage with deduplication[C]//Proceedings of the 2nd ACM Conference on Data and Application Security and Privacy. New York:ACM, 2012:1-12. |
| [20] | PIETRO R D, SORNIOTTI A. Boosting efficiency and security in proof of ownership for deduplication[C]//Proceedings of the 7th ACM Symposiumon on Information, Computer and Communications Security. New York:ACM, 2012:81-82. |
| [21] | BLASCO J, ORFILA A, PIETRO R D, et al. A tunable proof of ownership scheme for deduplication using bloom filters[C]//Proceedings of the 2014 IEEE Conference on Communications and Network Security. Piscataway, NJ:IEEE, 2014:481-489. |