如何加密面向重复数据消除的备份数据

重复数据消除技术是一种提高数据中心存储空间利用率和减小远程备份时带宽占用的有效手段，但由于用户密钥选择不一致和加密算法的雪崩效应，以文件为单位的传统加密方法所得到的加密文件，其重复数据消除效果很差。为解决保证数据机密性与提高重复数据消除率之间的矛盾，提出了一种面向重复数据消除的备份数据加密方法。

一、传统加密与重复数据消除放入矛盾

对以文件为单位的传统加密方法给重复数据消除带来的问题。

1)多个用户各自选用不同的对称密钥加密自己的文件，加密时直接以整个文件作为加密单位，并将加密后的文件分块后，提交给数据中心存储；

2)加密文件的分块方法采用固定长度分块，设每个分块的长度为2位，则分块共有2↓=m种取值；

3)加密后的数据是随机均匀分布的；

4)设每个分块的物理大小为C字节，则分块的逻辑大小为qC字节，其中g代表该分块被g个文件所包含；

5)数据中心的物理存储量是指其所存储分块的物理大小之和，而逻辑存储鼍是指这些分块的逻辑大小之和。

数据中心的物理存储量和逻辑存储量之所以存在差异，是因为数据中心没有存储那些重复的分块。换而言之，如果数据中心收到的分块全都是不同的，则这种情况下物理存储量和逻辑存储量相等。

设初始时数据中心存储的分块数量为O，则数据中心收到的第1个分块一定会被存储，此时物理存储量和逻辑存储量相等，都为C字节。由于加密后的数据是随机均匀分布的，故数据中心收到的第2个分块与第1个分块不相同的概率（即第2个分块被存储的概率）是l-1/m。设数据中心收到了k个分块后（此时逻辑存储量L=kC字节），其物理存储量为Sk字节。因此，当数据中心收到了k一1个分块后，其物理存储量为Sk-I字节，此时数据中心实际存储的分块数量为SL-I/C。数据中心收到的第七个分块与前面这Sk-1/C个分块均不相同的概率（即第七个分块被存储的概率）是l-Sk-1/(mC)，当k>m时，Sk≈mC，Lk=kC，sk=《Lk，物理存储量远小于逻辑存储最，换而言之，当以文件为单位加密时，必须满足k>m才能获得理想的重复数据消除效果。由于m与分块长度j成指数关系，故m通常非常大，例如当分块大小为8 KB时，l=216= 65536，m=255362×1097280如果为了减小m而把分块大小设定得很小，又会大大增加分块数量，从而大幅度增加分块的元数据存储开销和查询的时间开销。因此，在实际应用中，k《m。而当k<m时，Sk≈kC，lk=kC，sk=lk，物理存储量与逻辑存储量近似相等，重复数据消除几乎没有效果。

通过以上分析可以看出，由于加密后的数据可以近似看做密文空间上的随机数据，因此如果以文件为单位进行加密，再对加密后的文件进行重复数据消除，效果是非常差的。

二、面向重复数据消除的数据加密方法

1、DODEM的参与方

面向重复数据消除的备份数据加密方法( DODEM)总共有三个参与方：用户、元数据服务器和分块存储服务器。

（1）用户

用户使用某种一定的分块方法对自己某一版本的备份文件进行分块（分块记为Chunhi），并对每一分块用AES128对称加密算法进行加密，密钥K为Chunki内容的SHA-I哈希值的低128位。该加密过程记为：

KSL=Lmvt28(SHAI(Chunk*,))

Chunkk=AES128(Chunhip,Ks,)

上式中Chunk*代表明文分块，Chunk"代表密文分块。

由于加密密钥取决于分块的内容，因此两个分块只要内容相同，即使由不同的用户加密，也会得到相同的密文分块。

（2）元数据服务器

元数据服务器维护分块映射表(ChunkMap)，该表用于将文件ID( FileID，是系统中备份文件的唯一标识符，通过计算文件名的SHA-I哈希值得到)映射为其对应的分块列表(ChurikLi8t，简记为CL)。CL中存储了文件所包含的各分块的ID( ChunkID)、在文件中的序号和分块对称密钥Ks。借助这些信息，元数据服务器可以协助授权用户解密备份文件。此外，元数据服务器上还维护了一个哈希表Ha8hc，该表中保存了备份系统中已存储的分块的ChunkID（由于ChunkID是分块密文的SHA-I哈希值，因此Hashc实际上是分块内容的哈希表）。通过查询Hashc，元数据服务器可以检测出新写入文件中内容重复的分块。

因为CbunklJist中有解密备份文件所需的信息（即该文件对应的所有分块的密钥），为了保护其不被非授权用户读取，元数据服务器进行如下处理：

1)对给定的备份文件i，为其生成一个对称密钥Ku，并用它加密该文件的分块列表ChunkLkri，记为AES128( CLi，kli)；

2)用磁认加密算法加密Ku，加密密钥是授权用户k的公钥ku-kpub，即RSA( KLi，Kpub)；

3)将该用户的ID（UIDh）和用该用户公钥加密后的kli链接在加密后的ChunkList；后面，得到的结果记为AESI128（CLi,Ku)lIUIDk||RSA(Ku,KUUd);

4)继续链接其他授权用户的ID和用其公钥加密的kli，直到文件i的全部授权用户列表（UListi）添加完毕。

当需要为备份文件i新增一个授权用户时，只需将该用户的ID和用其公钥加密的瓦链接在原来用户列表的后面即可；但如果需要删除一个授权用户时，则需要生成一个新的对称密钥kli*，并用该密钥重新进行上面1）—4）加密过程。由于ChurzkLkt。存储的仅仅是与分块相关的一些元数据，故ChunkList，相对于整个文件而言是非常小的。例如当文件i：大小为lGB，分块大小为8 KB时，ChurzkLkt的大小仅为5MB左右，因此用新生成的对称密钥E加密的是仅仅是大小为5 MB的ChunkList，而不是整个文件。并且无论该文件有多少授权用户，都只需用新对称密钥磁加密ChunhList一次，而各授权用户公钥加密的也仅仅是大小为128b的新对称密钥Kli*。由此可见，更换对称密钥磁所需的加密计算开销并不大。

通过这种方式加密后，要访问和解密备份文件i，需要用Kli解密ChurzkLkt。对所有授权用户而言，可以获得用自己公钥加密的Kui，因此可以用自己的私钥解密得到Kui，从而得到ChunkListi。而对非授权用户而言，因为无法获取Chunksti，故不能获知文件i是由哪些Chunk组成的，即连文件f的密文都无法准确获取，要解密文件i就更困难了。

（3）分块存储服务器

分块存储服务器用于存储经过重复数据消除后的分块，内容相同的分块只存储一份实例，因此可以大幅度减小备份数据的物理存储开销。

用分块密文的SHA-1哈希值作为分块的ChunkID，它是分块的唯一标识符，长度为160b。ChunkID可以由用户提供或由分块存储服务器自行计算，取决于在具体应用中减少网络数据传输量更重要还是减小服务器端计算负载更重要。分块存储服务器的主要工作是存储用户提交的密文分块或根据用户提交的ChunkID读取对应的分块，它不存储与分块解密相关的信息，也不关心这些分块属于哪个文件。

2、基于DODEM的备份文件读写协议

假设基于DODEM的备份系统已具备了以下基础条件：

1)每个用户拥有密钥对（公钥Ku-pub和私钥Ku_prt）；

2)有合适的密钥管理技术（例如公钥基础设施（PublicKey Infrastructure，PKI））来保证公钥的可信分发；

3)元数据服务器能够生成密码学意义上可靠的对称加密密钥(用于加密ChunkList)。

（1）备份文件读协议

用户k读取备份文件i的主要过程如下：

1)用户k向元数据服务器发出读请求RequestR，并同时提交自己的UID,和口令，供服务器进行身份识别；

2)身份识别通过后，用户七将自己要读取的备份文件l的FileID．发送给元数据服务器；

3)元数据服务器将用对称密钥Kr加密的文件i的ChunhLrst，以及使用用户詹的公钥Kuk_pub加密的如一起发送给用户k；

4)用户k收到加密元数据后，先用自己的私钥Kuk-pri解密Kli，然后再用黾解密Chu觑伪ti，有了ChunhLrsti，用户k就知道了文件i所包含分块的ChunkID、分块对称密钥Ks和这些分块在文件i中的顺序；

5)用户k向分块存储服务器发出读请求，并同时提交身份识别信息；