云环境下支持可更新加密的分布式数据编码存储方案

严新成 陈 越 巴 阳 贾洪勇 朱 彧

1(战略支援部队信息工程大学 郑州 450001) 2(郑州大学软件与应用科技学院 郑州 450001)

随着大数据与云计算技术的发展，越来越多的数据可以在云端进行存储、计算以及共享.数据加密有效保证了存储与通信的机密性.而根据美国国家标准与技术研究院(National Institute of Standards and Technology, NIST)发布的Special Publication[1]SP 800-57，基于密码学的密文密钥具有严格的生命周期，保留时间越长，密钥泄露风险越大.

我们知道，在加解密服务中，非对称加密主要实现的是对称密钥的保护和共享，也就是对实际存储数据的访问权限的一种控制.就存储的用户敏感数据而言，对称加密提供的是基本的安全性保障.云服务器的存储数据资源丰富，其分为“冷数据”和“热数据”，不同类型的数据其价值相差甚大.对于云中长期存储的数据而言，尤其是重要性较高的敏感密文数据，由于密文的硬破解是困难的[2]，因此密钥存储与使用的安全性直接影响了密文存储的安全性.现代密码学都假定用户密钥对可能的攻击来说是完全隐藏的，但在实际中通过边信道攻击，例如时间攻击、电源耗损、冷启动攻击以及频谱分析等，都能从保密密钥或加密系统内部获得有关密钥的部分信息[3]，极大损害了存储密文的安全性.因此，对于长期存储的加密敏感数据，为防止用户私钥泄露，需要周期性地轮换密钥或根据实际情况撤销部分用户访问权限.

比如NIST[4]建议定期轮换密钥，开放式Web应用程序安全项目OWASP[5]也是如此，支付卡行业[6]定期要求轮换客户数据.谷歌[7]和亚马逊[8]现在为其长期存储服务中的此类操作提供部分支持，因此被授权密钥更新的客户可以这样做.然而，正如Everspaugh等人[9]所指出的那样，Google和Amazon所使用的技术存在可疑的和未定义的安全性，且容易受到密钥搜索攻击(key-scraping attacks).因此，密钥更新是实践中的难题之一.

此外，虽然更新共享文件很常见，但很少关注如何有效地更新分布式存储系统中的大量加密的文件.事实上，要修改文件中的任何一个比特位，当前的解决方案需要通过简单且昂贵的方式下载和解密文件[10].数据重加密是实现密文更新的简单方式，但是极大增加了客户端的计算开销以及存储系统的通信开销，同时客户端需要更大的缓存空间来存储从服务器端返回的额外数据块.混合加密虽然实现了用户私钥(密钥加密密钥)的更新，但内部的数据加密密钥并未更新.对于之前能访问该数据密钥的被撤销权限的用户而言，数据的存储仍存在安全风险.我们知道，数据的存储结构包括2类：集中式存储和分布式存储.集中式存储使得数据在管理上较为直观方便，但难以满足数据灾备的需求.而将数据重加密或混合加密直接应用到分布式数据存储时，通信及计算开销过大：上一个版本的密文块更新需要经历从各个数据节点“下载-还原-解密-重加密-重新分块上传”的过程，客户端计算开销及系统的通信开销均可能成为制约系统运行效率的关键[11].因此，就云存储的实际应用而言，需要同时考虑数据的机密性、完整性、可用性及单节点的直接更新，这对支持加密的分布式数据存储提出了更高的要求，即能够在各数据节点存储的编码后的密文数据的基础上直接进行数据更新，从而避免数据上传下载带来的通信开销以及还原密文和重加密带来的计算开销，为进一步构建安全实用的加密云存储系统提供有效的技术支撑.

1 相关工作

从当前研究来看，密钥更新面临的最大挑战仍然是密文更新的计算开销问题.本文整理并归纳了近几年关于可更新加密的研究工作，并结合分布式云存储及数据安全更新的场景分析可更新加密在实际应用中的问题与挑战.

云计算技术的大规模应用使得存储数据的隐私保护问题日益凸显，加密环境下密钥泄露的威胁场景也无处不在.Sahai等人[12]在CRYPTO 2012上提出这样一个担心：在云存储系统中，当用户证书变化时，必须同时考虑私钥的撤销以及密文的更新，使得被撤销权限的用户无法访问之前可解密的数据，而合法用户不受影响；Sahai等人定义了可撤销存储，基于密文代理技术，利用公开信息直接对给定策略加密的密文进行“重加密”，使得该密文转换为原明文信息对应的更具有约束性策略的新的密文，保证新加密的数据无法被已撤销私钥的用户访问；通过对Lewko等人[13]的方案进行改进，分别构建了支持KPABE(key-policy attribute-based encryption)和CPABE(ciphertext-policy attribute-based encryption)的解决方案，均满足上述定义的“分段密钥产生”特性，并在标准模型下证明是安全的.

自更新加密(self-updatable encryption, SUE)由Lee等人[14]在ASIACRYPT 2013提出，是一个新开发的密码学原语，它实现了作为内置功能的密文更新，从而提高了云管理中密钥撤销和时间演进的效率.在SUE中，当且仅当用户拥有与密文的时间相同或未来某个时间对应的私钥时，用户可以解密与特定时间相关联的密文.此外，可以只使用公共信息将附加到某个时间的密文更新为附加到未来时间的新密文.Datta等人[15]在标准假设下给出了素数阶双线性群中的第1个完全安全的SUE方案，即决策线性假设和决策双线性Diffie-Hellman假设;但Freeman[16]和Lewko[17]指出，素数阶双线性群的通信和存储以及计算效率比具有相当安全级别的复合阶双线性群要高得多.因此，文献[15]提出的SUE方案比现有的完全安全的SUE具有高度的成本效益.Lee[18]在素数阶双线性群中提出了一种SUE方案，该方案公共参数较短，并将其先前的方案扩展到支持密文时间间隔的TI-SUE(time-interval SUE)方案;Aono等人[19]提出了密钥可轮换和安全可更新同态加密的概念，其中任何密文密钥都可以轮换和更新，同时仍然保持底层明文的完整和未透露;Lee等人[20]提出了第1个SUE和RS-ABE方案来解决新的威胁，即被撤销权限的用户仍然可以访问由存储服务器提供的过去的密文.

Rodriguez等人[21]考虑使用计数器(counter, CTR)模式加密来保护数据安全.CTR由Diffie和Hellman[22]提出，并在2001年被NIST通过，作为加密的安全操作码[23].有关如何生成这些“计数器”的规范可以在NIST发布的标准中找到.但是，他们提出的方案缺乏用户私钥的定义和标准的安全证明.

然而，上述可更新数据加密方案并未考虑实际云存储中的应用.如引言所述，集中式存储难以满足有效的数据灾备需要.也就是说，构建支持可更新加密的分布式数据存储方案可以满足更高的安全性和可靠性要求.分布式存储架构是用于在授权用户之间存储和共享大数据的云计算系统的最重要组件之一.分布式存储系统通过分散在单个不可靠节点上的冗余提供对数据的可靠访问，应用场景包括数据中心、点对点存储系统和无线网络中的存储[24].现代分布式存储系统将冗余编码技术应用于存储数据，能够解决集中式存储的单点失效问题以及避免多副本存储的巨大开销；Hu等人[25]研究了功能最小存储再生码FMSR,它可以在没有幸存节点的编码要求的情况下实现无编码修复，同时保留最小的修复带宽保证并最小化磁盘读取；Rawat等人[26]研究分布式存储系统的安全性和本地可修复性，并重点介绍能够实现最佳局部修复的编码方案；Li等人[27]提出了一种通用转换以实现分布式存储系统中MDS编码的最佳修复；Su[28]引入了一种称为柔韧FR编码的新型FR编码，它可以解决现有FR编码不够灵活，无法充分适应分布式存储系统变化的缺点；唐英杰等人[29]针对基于纠删码的分布式存储中数据恢复开销过大问题，提出一种基于网络计算的高效故障重建方案来减少网络流量，有效解决了客户端的网络瓶颈.

2 预备知识

2.1 密钥同态伪随机函数

2.2 FMSR码

(n,k)FMSR码将大小为M的原始文件切分成k(n-k)个固定大小的数据块，再将它们编码成n(n-k)个编码块然后上传到n个数据节点，每个节点存储相邻的n-k个编码块.数据读取时，首先从随机挑选的k个数据节点中下载k(n-k)个编码块进行译码操作，然后将还原后的数据块合并成原始文件.

当某节点意外失效时，为保证数据的安全性和服务的连续性，数据修复过程如下：从正常工作的n-1个数据节点上各取一个数据块重新进行编码，用生成的n-k个编码块来替代失效节点存储的数据.(4,2)FMSR码的修复过程如图1所示：

Fig. 1 Data recovery of (4,2)FMSR encoding for corrupted nodes图1 (4,2)FMSR码的损坏节点数据恢复

2.3 DDH假设

3 DDES-UE方案设计

3.1 系统架构

Fig. 2 System architecture of DDES -UE图2 DDES -UE方案系统架构

DDES-UE的系统架构如图2所示.它主要分为2部分：客户端和云存储系统.客户端系统通过Internet连接到各种数据存储服务器(data storage server, DSS)和数据管理服务器(data management server, DMS).云存储系统由分布在网络中的一系列数据存储服务器和数据管理服务器组成，通过网络连接形成分布式存储系统.待存储的数据首先在客户端基于密钥同态伪随机函数进行分块加密，然后将分块密文进行编码，生成的编码数据块分布式存储在不同的数据节点(即数据存储服务器)中，关于密文的相关信息和密钥由数据管理服务器管理.具体的数据存储过程见3.2.4节.

3.2 方案构建

3.2.1 数据加密

Fig. 3 Data encryption and ciphertext segmentation图3 数据加密与密文分割

算法1.数据加密算法.

输入：对称密钥k、待加密的数据m；

②χ=x+y；

③τ=h(m)+R(x,0)；

⑤ for 1≤i≤η*接下来计算密文体

⑦ end for

3.2.2 数据分割

在实际部署中，用户端可通过运行客户端程序与云存储系统进行交互，后者除了负责数据的上传和下载，还负责维护编码参数和加密密钥等信息.

3.2.3 数据编码

客户端对原始密文数据(即密文体F)进行编码，得到n(n-k)×r个编码数据块，记作(Pij)i=1,2,…,n(n-k),j=1,2,…,r,每个编码块都是k(n-k)个初始密文数据块Macro-blocks所包含的所有子数据块Mini-block的线性组合.

具体的编码过程为：

1) 首先在客户端构造一个n(n-k)×k(n-k)的编码矩阵EM=(αi,j)，其中元素αi,j均是从有限域GF(2w)中随机产生，EM必须满足MDS性质.

2) 客户端使用过程1)中产生的编码矩阵与初始密文块(即k(n-k)个Macro-block)进行乘法运算，得到n(n-k)×r个编码数据块.编码矩阵中每个行向量称之为一个编码向量，其形式为Pi=(Pi,1,Pi,2,…,Pi,r)，对应于一个编码块.对初始密文块的每个Macro-block进行编码后得到的编码块矩阵为

(1)

其中,i=1,2,…,n(n-k),x=1,2,…,r.

3.2.4 数据存储

客户端将n(n-k)×r个编码数据块上传给n个数据节点，每个节点存储相邻的(n-k)×r个数据块，编码矩阵由客户端持有.同时将密文头上传至数据管理服务器.

取n=4，k=2时，单个文件的上传过程如图4所示.注意在编码块的产生过程中，我们以Macro-block为单位进行表述.

Fig. 4 Process of data chunking storage图4 数据分块存储过程

3.2.5 密文更新

数据更新包括2个阶段：更新令牌生成和密文重新加密.我们分别描述它们，然后在不同的分布式数据节点中给出编码块的独立更新过程.更新令牌生成过程的描述如算法2所示.

算法2.更新令牌产生算法.

② if (χ,τ)=⊥ then

③ return ⊥；

④ end if

⑥χ′=χ+x′+y′；

⑦τ′=τ+R(x′,0)；

算法3.密文重加密算法.

③ for 1≤i≤η

⑤ end for

第i行第υ列的编码块的更新过程可表示为

(2)

3.2.6 数据还原

1) 数据解码与合并

根据2.2节中基于FMSR码的数据读取过程，客户端从n个数据节点中任取k个负载较小的节点并下载其所有的编码块，共计k(n-k)×r个编码块，然后从3.2.3节构造的EM中取出上述编码数据对应的行向量，组成一个k(n-k)×k(n-k)阶方阵，记作EM′.需要注意的是，新产生的方阵EM′中的数据来源于EM，其各个行向量线性无关，因此逆矩阵EM′-1必然存在；

然后客户端使用EM′-1乘以下载的编码数据块即可得到k(n-k)×r个原始块，将其合并组装即可得到初始的密文数据块.

取n=4，k=2时，文件M的下载过程如图5所示，其中每个数据节点存储的数据块代表编码块矩阵对应的行向量，即Pi,j=(Pi,1,Pi,2,…,Pi,r).

2) 数据解密

Fig. 5 Process of data reduction图5 数据还原过程

算法4.数据解密算法.

输出：原始明文M或⊥.

② if (χ,τ)=⊥ then

③ return ⊥；

④ end if

⑥ for 1≤i≤η

⑧ end for

⑨ ifh(m)+R(χ-y,0)=τthen

⑩ returnm=(m1,m2,…,mη)；

4 安全性及数据可用性分析

4.1 安全性分析

根据Everspaugh等人[9]的方案证明，这里从可更新加密不可区分性UE-IND和重加密安全性UE-REENC两个方面给出DDES-UE中可更新加密的安全性证明.

证明. UE-IND安全游戏选取2个参数t和κ，并初始化t+κ秘密密钥，其中κ个给予敌手，t个保留用于在谕言中使用.我们用k1,k2,…,kt表示未泄露的密钥，kt+1,kt+2,…,kt+κ表示已泄露的密钥.在安全游戏中，我们要求至少一个未泄露的密钥，但对已泄露的密钥数量不进行要求，即t≥1,κ≥0.敌手的目标是猜测比特位b，成功意味着方案泄露了关于明文的部分信息.

我们将证明分为2部分:1)使用π的AE安全性来表明用于密钥同态PRF输入的x的值对敌手而言是隐藏的；2)基于R是一个密钥同态伪随机函数这一事实来说明不可区分性成立，考虑到敌手无法了解到x.

UE-IND安全游戏描述：

b←${0,1};

k1,k2,…,kt+κ←$KeyGen();

return (b′=b).

Enc(i,m):

returnEnc(ki,m).

return ⊥;

end if

else returnC′;

end if

LR(i,m0,m1):

ifi>tthen

return ⊥;

end if

C←$Enc(ki,mb);

returnC.

—若j≤i，为随机值r′返回(r′,x′,y′)，并存储(x+x′,y+y′,m)，或者

—若j>i，返回(ε(kj,(χ′,h(m)+R(x+x′,0))),x′,y′).

Enc(i,m):

χ=x+y;

Ci[r]=(x,y,m);

for 1≤i≤η

end for

if (x,y,m)=⊥ then

return ⊥;

end if

χ′=x+y+x′+y′;

ifj≤ithen

Cj[r]=(x+x′,y+y′,m);

else

τ=h(m)+R(x+x′,0);

end if

if (x,y,m)=⊥ then

return ⊥;

end if

x′=x+y-y′;

for 1≤i≤η

end for

τ=h(m)+R(x,0);

ifτ-R(x′,0)=h(m′) then

returnm=(m1,m2,…,mη);

else

return ⊥;

end if

类似地，re-encryption查询，其中目标密钥j未泄露，即j≤t，敌手接收在x′下加密的新密文，但仍无法获得x′的信息.另一方面，如果j>t，InvalidRE=true，因此攻击者能够学习到密文头.其形式为：ε(kj,(x+y+x′+y′,h(m)+R(x+x′,0))).由于攻击者拥有kj，他们可以解密密文头.但是x仍被y所隐藏.

对于所有的κ≥0,t≥1均成立.

成立.

证明. 在该定理证明中，应用与定理1证明中相同的t个步骤.然后我们用随机字符串替换密文头，并通过记录先前看到的输入来模拟re-keygen过程.

4.2 数据可用性分析

本节通过对受损节点的数据重构过程描述来说明DDES-UE方案能够保证部分节点失效情形下的数据可用性.在2.2节有简要描述，这里进行详细说明.在数据节点N1,N2,…,Nn中，假设对数据节点Nx上的数据进行恢复，步骤为

1)客户端在除了Nx以外的每个节点上随机挑选一个编码块(共有(n-k)n-1种不同的可能)，在存储的编码矩阵中取出这(n-1)个编码块所对应的编码向量，记作ECVi1,ECVi2,…,ECVin-1.

2)在客户端构造(n-k)×(n-1)的变换矩阵TM=(γi,j)，其中i=1,2,…,n-k,j=1,2,…,n-1,矩阵中的元素γi,j均从有限域GF(2w)中随机产生.

(3)

其中每个新的编码向量可表示为

(4)

5) 客户端判断EM′是否满足MDS性质，即判断EM′的中任意k(n-k)个行向量组成的方阵是否满秩.若满足MDS性质，执行步骤6)，否则跳到步骤1)，进入下一轮迭代，重新挑选新的编码向量和变换系数.

6) 客户端将TM，以及步骤1)中挑选出的编码块序号发送给数据节点Nx.

7) 数据节点Nx从相应的数据节点上下载步骤1)中的挑选出的编码块，并使用TM对这些编码块进行编码得到n-k个数据块，覆盖自身的原有数据，完成一次数据重构.

5 DDES-UE方案的性能分析

DDES-UE方案在存储结构、数据加密、密钥轮换以及安全性证明4个方面的对比如表1所示.

本节主要从数据上传、数据下载、污染数据恢复以及密文更新4个环节对DDES-UE方案的性能进行验证与分析，分别选取10～100 MB(每次以10 MB递增)的文件大小，对每个环节中各部分所涉及的关键计算(如数据读取、数据写入、群元素加法运算、群元素加法运算、群元素幂运算、群元素映射等)的时间开销进行了综合测试，并使用Java编程语言构建了我们的参考实现.实验环境描述为：Windows 64 b操作系统，Intel®CoreTMi7-4770 CPU(3.4 GHz)，内存12 GB.

Table 1 Comparison of Advantages in Different Schemes表1 方案优势对比

Note: “” indicates that this scheme does not show the corresponding explanation.

在仿真实验中首先需要实例化DDES-UE使用的密钥同态PRF.这里使用R(x,i)=H(i)x，其中H被建模为随机预言H:X→G.构建H的自然方法是采用常规Hash函数h:{0,1}*→{0,1}n.X是任何合适的集合(例如，某些固定长度的位串)，并且(G,+)是判定性Diffie Hellman假设成立的群.

其中数据上传(选取数据加密、数据编码、数据传输、数据写入4个部分)与数据下载(选取数据读取、数据传输、数据解码、数据解密4个部分)过程仿真实验结果如图6、图7所示.结合Hu等人[25]以及陈越等人[33]中的性能分析可以看出，本文构造的DDES-UE方案在分布式数据存储与恢复(如在数据上传与下载过程中涉及的数据读取、数据传输、数据编码解码以及数据合并等运算和在污染数据恢复时的变换矩阵计算、下载编码块、数据重构等)上的性能开销在可接受范围内.

Fig. 6 Time cost in different stages of data uploading图6 数据上传过程计算开销

Fig. 7 Time cost in different stages of data downloading图7 数据下载过程计算开销

污染数据修复(选取计算转换矩阵、下载编码数据块、数据重构、数据写入4个部分)与数据更新过程仿真实验结果分别如图8、图9所示.随着文件大小的增长，污染数据修复过程及数据更新的计算开销均呈线性增长趋势，但前者的时间开销较小，能够保证高效的数据可恢复性；而文件更新的计算开销过大.接下来对仿真实验中涉及数据加解密的计算开销进行详细分析.

Fig. 8 Time cost in different stages of data recovery图8 数据修复过程计算开销

Fig. 9 Time cost of one data update图9 一次数据更新过程计算开销

当然，正如Everspaugh等人[9]描述的那样，我们提出的方案DDES-UE当前最适用于体量小但非常有价值的数据，比如大型企业的重要客户资料备份等.该方案既能够通过分布式存储满足数据灾备及污染数据恢复的需求，同时也支持分布式架构下存储数据的直接更新，有效避免了数据恢复与重加密更新的计算开销和数据上传下载造成的网络通信开销.

6 结束语

本文提出DDES-UE方案，支持分布式云存储中不同数据节点持有的编码密文块的直接更新.基于密钥同态伪随机函数，可以将当前密文直接更新为新版本的密文，且更新后的密文与当前版本的密文是一致分布的，即等同于用新密钥加密的密文，在保证数据安全性的同时节约了通信资源成本.

此外，结合改进的FMSR编码技术，提出的DDES-UE方案能够确保分布式存储系统中部分数据节点受损时的数据可用性，且支持数据恢复时的完整性验证.同时，可更新加密中的密钥更新具有时变性，压缩了攻击者发起攻击的时间窗口.假设在较长时间内攻击者通过某种攻击方式获取到存储密文及用户私钥及编码矩阵，若三者不在同一个时间周期，则无法完成解密，从而使得攻击结果无效.因此，当云存储中加密数据的密钥周期性更新时，系统能够通过增加攻击者的时间成本，有效降低攻击者通过获取密文密钥相关信息来破解密文的概率.

安全性证明和性能分析表明:DDES-UE方案可以实现安全有效的密文更新，以应对密钥泄露的风险；避免了数据重加密时数据上传下载带来的巨大通信开销，并支持数据恢复以保证数据的持续可用性.然而，以群元素大小为单位的数据更新导致计算伪随机函数所需的标量乘法次数以及Elligator2函数中元素映射的次数成为制约密文更新效率的关键因素.这使得我们在有效解决了降低网络带宽负载及客户端重加密计算开销问题之后，仍需考虑如何降低执行密文更新操作的云存储服务器的计算开销.因此，未来工作将深入研究分布式云环境下以数据块为单位的直接密文更新方法以及针对椭圆曲线点的标量乘法效率改进，为进一步构建更具普适性的加密云存储系统提供技术支持.