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

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

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

摘 要 由于云存储密文的静态性特征,密钥泄露成为影响存储数据安全性的重要因素.数据重加密是应对密钥泄露的有效手段,但相应的计算开销以及上传下载的通信开销增加了用户和存储系统的负担.此外,对基于分布式编码的数据存储而言,密文更新需要在解密密文的基础上进行,密文合并过程同样增加了系统的通信及计算开销.针对上述问题,提出一种云环境下支持可更新加密的分布式数据编码存储方案(distributed data encoding storage scheme supporting updatable encryption, DDES-UE).通过利用密钥同态伪随机函数构造可更新加密方案,可避免密文更新的计算与通信开销过大问题;基于密文分割与改进FMSR编码实现数据分布式存储,保证存储数据的高可用性和各存储节点的直接数据更新.安全性证明及性能分析表明:提出的方案在保证数据存储安全性的同时,能够支持部分存储节点损坏时安全高效的数据可恢复性以及解密数据的完整性验证.与传统的数据重加密相比,DDES-UE能够避免数据重加密及数据上传、下载、解码、合并带来的计算和通信开销,对于构建支持直接数据更新的安全高效云存储系统有重要意义.此外,周期性密钥更新可有效增加攻击者通过获取密钥破解密文的时间成本,从而增强了系统的主动安全防御能力.

关键词 分布式云存储;密钥泄露;可更新加密;FMSR编码;周期性密钥更新

随着大数据与云计算技术的发展,越来越多的数据可以在云端进行存储、计算以及共享.数据加密有效保证了存储与通信的机密性.而根据美国国家标准与技术研究院(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 密钥同态伪随机函数

考虑一个高效可计算的函数其中和(G,⊗)都是群.我们称(R,⊕,⊗)是密钥同态的伪随机函数(key homomorphic pseudorandom functions, KHPRF),如果函数R是安全的,并且对于每个以及元素都有R(k1,x)⊗R(k2,x)=R(k1k2,x)成立.函数R的安全性定义如下:

定义为随机选择一个密钥然后运行攻击者的游戏,该敌手可以自适应地查询谕言,返回应用于查询消息的Rk.敌手输出一个比特位.在游戏中,敌手可以自适应地查询谕言并返回一个从G中随机抽取的值.同样敌手输出一个比特.我们假设在任一游戏中都不会向其谕言查询2次相同的值.我们定义敌手的PRF优势为

的值是可忽略的,则称函数R是安全的.随机预言模型中的安全密钥同态PRF的简单示例是函数R(k,x)=H(x)k,其中G是加法群,判定性Diffie Hellman假设成立.这种构建最初归功于Naor,Pinkas和Reingold[30].

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假设

以元组(G,g,p)为输入,其中群G表示阶为p生成元为g的循环群,判定Diffie-Hellman(DDH)问题关于λ是困难的,即pλ位素数.更确切地说,如果对于任何高效的敌手都有概率:


λ中可忽略不计,则称群(G,g,p)满足DDH假设,其中概率超过p,g的随机选择,a,b,c∈Zp的随机选择以及的硬币投掷.

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 数据加密

在数据加密过程中使用密钥同态伪随机函数和Hash函数h:{0,1}*G.假设消息M可以由群G中的元素序列m1,m2,…,ml表示.集合中的元素都可以用整数来表示.注意虽然都产生参数,但是前者表示的是密钥生成算法,生成的是对称密钥k;后者是群从中随机选取2个元素.客户端对数据进行加密的过程如下.

此外,图3给出了一个简单的数据加密和密文分块的例子,其中参数n=4,k=2,r=5.数据加密前首先调用密钥产生算法生成一个对称密钥k.数据加密过程的描述如算法1所示.

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

算法1. 数据加密算法.

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

输出:密文头

x,首先从群选出2个重要参数x,y*

χ=x+y

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

使用上一阶段产生的对称密钥k来加密(χ,τ)生成密文头

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

⑦ end for

最后,算法返回其中密文头由数据管理服务器保存.

3.2.2 数据分割

在数据分割阶段,客户端首先将加密后的文件(即密文体部分)切分成块.假设密文大小为F,将之切分成k(n-k)个固定大小的数据块(每个数据块称为Macro-block),记作每个数据块Macro-block的大小为Fk(n-k),包含r个子数据块,记为Mini-block(在阶为素数pZp中).即对于

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

3.2.3 数据编码

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

具体的编码过程为:

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

2) 客户端使用过程1)中产生的编码矩阵与初始密文块(即k(n-k)个Macro-block)进行乘法运算,得到n(n-kr个编码数据块.编码矩阵中每个行向量称之为一个编码向量,其形式为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-kr个编码数据块上传给n个数据节点,每个节点存储相邻的(n-kr个数据块,编码矩阵由客户端持有.同时将密文头上传至数据管理服务器.

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

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

3.2.5 密文更新

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

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

输入:当前使用的对称密钥ki及密文头以及需要更新至下个周期使用的对称密钥kj

输出:更新令牌

① (χ,使用ki解密当前使用的密文头

② if (χ,τ)=⊥ then

③ return ⊥;

④ end if

x′,从群中随机选取2个新的参数x′,y′*

χ′=χ+x′+y′;

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

基于算法2生成的更新令牌,密文重加密过程描述如算法3所示:

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

输入:当前版本的密文以及更新令牌

输出:新产生的密文

③ for 1≤iη

⑤ end for

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



R(x′-x,(i-1)×r+υ))=Pi,υ+

(2)

并将发送至数据管理服务器存储,替换上个版本的

3.2.6 数据还原

1) 数据解码与合并

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

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

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

2) 数据解密

客户端从数据管理服务器下载执行数据解密过程如算法4所示.

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

算法4. 数据解密算法.

输入:当前使用的对称密钥k及当前版本的密文

输出:原始明文M或⊥.

① (χ,使用k解密当前版本的密文头

② if (χ,τ)=⊥ then

③ return ⊥;

④ end if

⑥ for 1≤iη

⑧ end for

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

⑩ return m=(m1,m2,…,mη);

else

return ⊥;

end if

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

4.1 安全性分析

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

定理1. 为认证加密方是一个密钥同态伪随机函数,h:{0,1}*G是一个Hash函数.Π是第3节描述的可更新加密方案.那么对于针对Π的任意敌手对于所有的κ≥0,t≥1,存在敌手满足:

证明. 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):

return Enc(ki,m).

return ⊥;

end if

else return C′;

end if

LR(i,m0,m1):

if i>t then

return ⊥;

end if

C$ Enc(ki,mb);

return C.

G0为UE-IND游戏.对于1≤it,游戏GiGi-1等同,除了我们用随机字符串r替换ε(ki,(χ,h(m)+R(x,0)))加密并存储元组(x,y,m)作为由随机字符串r索引的表C中的查找.对于的查询,如果某些先前返回的r满足则正常计算x′,y′.

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

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

如果先前没有出现,则返回⊥.这些修改描述了用于DDES-UE方案可更新加密的安全性证明的游戏Gi中的替换算法:

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′;

if ji then

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

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

else

return ⊥;

end if

Si为敌手在游戏Gi中输出正确的比特这一事件.然后我们可以构造敌手使得|Pr[Si-1]-通过调用Π的AE游戏的一个实例来替换ε(ki,·)和函数,可以在实际中得到Gi-1,在随机场景下得到Gi.

假设攻击者在游戏Gt中查询LR谕言机以接收挑战密文C.那么密文头将等于某个随机字符串r,而密文体由参数y和基于输入x的伪随机函数R加密的消息组成.请注意,it时敌手被要求使用AE只能提交一次先前看到的密文头给谕言机.从re-keygen查询中,攻击者可以获得x′,y′,r′的新值.但是,这些不足以了解用于加密消息的x的值.

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

参考Boneh等人[11]给出的原始证明大纲,我们构造一个安全游戏Gt+1,使得等式成立.当it时,我们用PRF挑战谕言替换LR谕言机中R(x,i)的使用,表示为f(i).假设K是PRF挑战者使用的密钥.当PRF挑战来自现实世界时,计算的加密形式可以表述为mi+R(x,i)+f(i)=mi+R(K+x,i).而密文头包括值τ=h(m)+R(K+x,0).综上分析,x的值对于挑战密文的敌手是未知的,因此这种变化能够完美模拟Gt.

如果密钥j是未泄露的,那么我们可以计算否则,InvalidREInvalidRK将为false,并且对于密文体而言谕言机返回⊥.此外,攻击者还可以获得包含加密(x+x′,τ=h(m)+R(K+x+x′,0))的密文头.令Gt+1对应于PRF挑战返回随机值的事件.然后消息总是被f(i)的输出完美掩盖,即使在计算重新加密之后该值也存在.因此,消息和散列都被PRF值隐藏,并且敌手无法以大于12的概率获胜.因此我们得出:

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

定理2. 为认证加密方是一个密钥同态伪随机函数,Π是第3节描述的可更新加密方案.那么对于针对Π的任意敌手存在敌手对于所有的κ≥0,t≥1,使得:

成立.

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

因此,在游戏Gt中,由于所有值都被存储在密文体中的值隐藏,敌手无法获得挑战中使用的x的任何信息,密文头也不会泄露任何被泄露的密钥相关的信息.接下来构建一个PRF敌手来完成游戏.假设在游戏Gt中我们将挑战中的重加密过程替换为也就是说密文头是随机串,并且我们隐含地使用密钥χ+K+x′来重新加密密文体其中K是PRF挑战者使用的密钥.更新令牌为(r,K+x′,y′),而敌手无法获得K+x′.对于敌手任何进一步的查询re-encryption或re-keygen,攻击者将保留f(i)作为掩码的使用.

Gt+1提供的PRF挑战者返回随机值的场景我们可以得出结论,敌手无法获悉有关比特位b的任何信息.由此可以得出敌手的优势:

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)客户端用TM乘以步骤1)中选取的编码向量,得到n-k个新的编码块对应的编码向量该过程可表示为


TM×(ECVi1,ECVi2,…,ECVin-1)T,

(3)

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

(4)

4) 客户端用替换掉原来编码矩阵EM中的数据节点Nx所占部分,形成一个新的编码矩阵EM′.

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® CoreTM i7-4770 CPU(3.4 GHz),内存12 GB.

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

SchemesStorage ArchitectureData Encryption isSupported or NotKey Rotation isSupported or NotSecurity ProofsGoogle[7]Distributed StoragePartial Data EncryptionNo∕Amazon[8]Ddistributed StoragePartial Data EncryptionNo∕Ref [9]∕YesYesYesRef [11]∕YesYes∕Ref [14]∕YesNoYesRef [19]∕YesYesYesRef [21]Distributed Data CodingYesYes∕Ref [24]Distributed Data CodingNoNo∕Ref [25]Distributed Data CodingNoNo∕Ref [26]Distributed Data CodingNoNo∕Ref [33]Distributed Data CodingYesNo∕OursDistributed Data CodingYesYesYes

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

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

在方案实现的过程中我们还需要解决消息编码的问题.根据加密是按块完成的.等式成立前提是消息m已经表述为群G上的元素序列.为实现加密数据到椭圆曲线点的映射,需要构造一个针对数据块的长度为n的编码函数σm:{0,1}nG.根据解密过程生成的mi是群G上的元素,还需要还原为比特序列.因此我们要求消息编码函数的正反向都能够高效计算.本文使用Elligator2函数[31]来实现σm,即构造为KHPRF中的映射函数.Elligator2使用Curve25519曲线进行函数设计.因此在实现中使用特定曲线Curve25519[32],其中p=2255-19.参照Everspaugh等人的方案[9],我们使用SHA256作为散列函数h.Elligator2能够实现Zp中的群元素到群G中元素的双向映射,而mi表示的是划分后的文件块,需要通过Hash函数h:{0,1}*→{0,1}n实现文件块到Zp群元素的映射,此时可以得出H(i)=σm(h(i)).

其中数据上传(选取数据加密、数据编码、数据传输、数据写入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]的测试结果(Rust编程语言实现),其提出的ReCrypt方案加密1个数据块(≤31 B),1 KB,1 MB和1 GB的明文分别需要253 μs,8.5 μs,8.9 s和2.5 h内.同样.我们对数据加密中涉及的计数器模式加密运算和解密过程的运算进行测试,使用Elligator2算法进行加法群元素到椭圆曲线群元素的映射及其逆映射以及一次椭圆曲线群元素加法运算耗时分别为92 μs,157.5 μs和23.5 μs.一方面,使用Elligator2时数据块的大小等于群G中元素大小,这使得实际上使用31 B的块大小,而以MB为单位的文件将产生较多的数据块,极大影响了加密的性能;另一方面,椭圆曲线点的倍数x是从Zp中随机选取的群元素,进行倍数运算时候开销不容忽视.根据等式R(x,i)=H(i)x=(σm(h(i)))x,可看出DDES-UE方案的性能很大程度上取决于计算伪随机函数所需的标量乘法次数和Elligator2中元素映射运算的次数.这是制约DDES-UE中数据加解密及密文更新的效率瓶颈.当前有很多方案(如Sasdrich等人[34]和Zhe等人[35]等)针对椭圆曲线点的标量乘法效率展开研究,如何提高方案中可更新加密的计算效率也是下一步需要解决的问题.

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

6 结束语

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

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

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

参考文献

[1]National Institute of Standards and Technology. Recommendation for key management[OL]. 2016 [2019-06-01]. http:dx.doi.org10.6028NIST.SP.800-57pt1r4

[2]James N, Elaine B, Lawrence B, et al. Report on the development of the advanced encryption standard (AES)[J]. Journal of Research of the National Institute of Standards & Technology, 2001, 106(3): 511-577

[3]Zhang Mingwu, Yang Bo, Tsuyoshi T. Master-key leakage-resilient and continue leakage-resilient functional encryption in dual affine spaces[J]. Chinese Journal of Computers, 2012, 35(9): 1856-1867 (in Chinese)

(张明武, 杨波, Tsuyoshi T. 抗主密钥泄露和连续泄露的双态仿射函数加密[J]. 计算机学报, 2012, 35(9): 1856-1867)

[4]Myers S, Shull A. Practical revocation and key rotation[C] Proc of Cryptographers’ Track at the RSA Conf(CT-RSA 2018). Berlin: Springer, 2018: 157-178

[5]The OWASP Foundation. Open Web application security project: Cryptographic storage cheat sheet[OL]. 2016 [2019-06-01]. https:www.owasp.orgindex.phpCryptographic_Storage_Cheat_Sheet

[6]Payment Card Industry Security Standards Council(PCI SSC). DSS: Payment card industry data security standard[OL]. 2018 [2019-06-01]. https:en.wikipedia.orgwikiPayment_Card_Industry_Data_Security_Standard

[7]Google. Managing data encryption[OL]. 2017 [2019-06-01]. https:goo.gl5UidnU

[8]Amazon Web Services. Rotating customer master keys[OL]. 2017 [2019-06-01]. https:goo.glYm9WeM

[9]Everspaugh A, Paterson K, Ristenpart T, et al. Key rotation for authenticated encryption[G] LNCS 10403: Advances in Cryptology (CRYPTO 2017). Berlin: Springer, 2017

[10]Zhao Yongjun, Chow S S M. Updatable block-level message-locked encryption[C] Proc of the 2017 ACM on Asia Conf on Computer and Communications Security (ASIACCS 2017). New York: ACM, 2017: 449-460

[11]Boneh D, Lewi K, Montgomery H, et al. Key homomorphic PRFs and their applications[G] LNCS 8042: Proc of CRYPTO 2013. Berlin: Springer, 2013: 410-428

[12]Sahai A, Seyalioglu H, Waters B. Dynamic credentials and ciphertext delegation for attribute-based encryption[G] LNCS 7417: Proc of CRYPTO 2012. Berlin: Springer, 2012: 199-217

[13]Lewko A, Okamoto T, Sahai A, et al. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption[G] LNCS 6110: Proc of EUROCRYPT 2010. Berlin: Springer, 2010: 62-91

[14]Lee K, Choi S G, Dong H L, et al. Self-updatable encryption: Time constrained access control with hidden attributes and better efficiency[G] LNCS 8269: Proc of ASIACRYPT 2013. Berlin: Springer, 2013: 235-254

[15]Datta P, Dutta R, Mukhopadhyay S. Fully secure self-updatable encryption in prime order bilinear groups[G] LNCS 8783: Proc of Int Conf on Information Security. Berlin: Springer, 2014: 1-18

[16]Freeman D M. Converting pairing-based cryptosystems from composite-order groups to prime-order groups[G] LNCS 6110: Proc of EUROCRYPT 2010. Berlin: Springer, 2010: 44-61

[17]Lewko A. Tools for simulating features of composite order bilinear groups in the prime order setting[G] LNCS 7237: Proc of EUROCRYPT 2012. Berlin: Springer, 2012: 318-335

[18]Lee K. Self-updatable encryption with short public parameters and its extensions[J]. Designs, Codes and Cryptography, 2016, 79(1): 121-161

[19]Aono Y, Hayashi T, Phong L T, et al. Efficient key-rotatable and security-updatable homomorphic encryption[C] Proc of the 5th ACM Int Workshop on Security in Cloud Computing. New York: ACM, 2017: 35-42

[20]Lee K, Lee D H, Park J H, et al. CCA security for self-updatable encryption: Protecting cloud data when clients readwrite ciphertexts[J]. The Computer Journal, 2019, 62(4): 545-562

[21]Parra J R, Chan T H, Ho S W. Updatable encryption in distributed storage systems using key homomorphic pseudorandom functions[J]. International Journal of Information and Coding Theory, 2016, 3(4): 365-391

[22]Diffie W, Hellman M E. Privacy and authentication: An introduction to cryptography[J]. Proceedings of the IEEE, 1979, 67(3): 397-427

[23]Dworkin M. Recommendation for block cipher modes of operation: Methods and techniques[J]. National Institute of Standards & Technology, 2001, 5(6): 669-675

[24]Dimakis A G, Godfrey P B, Wu Y, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010, 56(9): 4539-4551

[25]Hu Yucong, Lee P P C, Shum K W. Analysis and construction of functional regenerating codes with uncoded repair for distributed storage systems[C] Proc of the 32nd INFOCOM Conf. Piscataway, NJ: IEEE, 2013: 2355-2363

[26]Rawat A S, Koyluoglu O O, Silberstein N, et al. Optimal locally repairable and secure codes for distributed storage systems[J]. IEEE Transactions on Information Theory, 2014, 60(1): 212-236

[27]Li Jie, Tang Xiaohu, Tian Chao. A generic transformation to enable optimal repair in MDS codes for distributed storage systems[J]. IEEE Transactions on Information Theory, 2018, 64(9): 6257-6267

[28]Su Yisheng. Pliable fractional repetition codes for distributed storage systems: Design and analysis[J]. IEEE Transactions on Communications, 2018, 66(6): 2359-2375

[29]Tang Yingjie, Wang Fang, Xie Yanwen. An efficient failure reconstruction based on in-network computing for erasure-coded storage systems[J]. Journal of Computer Research and Development, 2019, 56(4): 767-778 (in Chinese)

(唐英杰, 王芳, 谢燕文. 纠删码存储系统中基于网络计算的高效故障重建方法[J]. 计算机研究与发展, 2019, 56(4): 767-778)

[30]Naor M, Pinkas B, Reingold O. Distributed pseudo-random functions and KDCs[G] LNCS 1592: Proc of EUROCRYPT 1999. Berlin: Springer, 1999: 327-346

[31]Bernstein J, Hamburg M, Krasnova A, et al. Elligator: Elliptic-curve points indistinguishable from uniform random strings[C] Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 967-980

[32]Bernstein J. Curve25519: New Diffie-Hellman speed records[G] LNCS 3958: Proc of PKC 2006. Berlin: Springer, 2006: 207-228

[33]Chen Yue, Wang Longjiang, Yan Xincheng, et al. Mimic storage scheme based on regenerated code[J]. Journal on Communications, 2018, 39(4): 21-34 (in Chinese)

(陈越, 王龙江, 严新成, 等. 基于再生码的拟态数据存储方案[J]. 通信学报, 2018, 39(4): 21-34)

[34]Sasdrich P, Tim G. Efficient elliptic-curve cryptography using Curve25519 on reconfigurable devices[G] LNCS 8405: Proc of the 10th Int Symp on Applied Reconfigurable Computing. Berlin: Springer, 2014: 25-36

[35]Liu Zhe, Groszschaedl J, Hu Zhi, et al. Elliptic curve cryptography with efficiently computable endomorphisms and its hardware implementations for the Internet of things[J]. IEEE Transactions on Computers, 2017, 66(5): 773-785

Distributed Data Encoding Storage Scheme Supporting Updatable Encryption in Cloud

Yan Xincheng1, Chen Yue1, Ba Yang1, Jia Hongyong2, and Zhu Yu1

1(Strategic Support Force Information Engineering University, Zhengzhou 450001) 2(School of Software and Applied Technology, Zhengzhou University, Zhengzhou 450001)

Abstract Due to the long-term immutability of the ciphertext stored in the cloud, key compromise becomes an important factor affecting the security of stored data. Data re-encryption is an effective way to deal with key leakage, but the corresponding computational overhead and communication overhead of data uploading and downloading increase the burden on users and storage systems. In addition, for data storage based on distributed coding, ciphertext update needs to be performed on the basis of decrypting ciphertext, and the ciphertext merging also increases the communication and computational overhead of the system. Aiming at the above problems, a distributed data encoding storage scheme supporting updatable encryption (DDES-UE) in cloud environment is proposed. By constructing the updatable encryption scheme with key homomorphic pseudo-random functions, the heavy calculation and communication overhead of ciphertext update can be avoided; ciphertext segmentation and improved functional minimum storage regenerated code (FMSR) are used for achieving distributed data storage, which ensures high availability for storage data and direct data update of each storage node. Security proofs and performance analysis show that the proposed scheme can support secure and efficient data recoverability in the case of node corruption and the integrity verification of decrypted data while guaranteeing the security of data storage. Compared with traditional data re-encryption, DDES-UE can avoid the computation and communication overhead for data re-encryption, uploading, downloading, decoding, and ciphertext merging as well, which is of great significance for building secure and efficient cloud storage system with direct data update. In addition, the periodic key update can effectively increase the time cost for an attacker to crack the ciphertext by acquiring the key, which also enhance the active security defense capability of the system.

Key words distributed cloud storage; key compromise; updatable encryption; FMSR encoding; periodic key update

(imtodshine@163.com)

中图法分类号 TP309

收稿日期20190610;修回日期:20190805

基金项目国家自然科学基金项目(61702549);河南省科技攻关计划基金项目(172102210017)

This work was supported by the National Natural Science Foundation of China (61702549) and the Key Technologies Research and Development Program of Henan Province (172102210017).

通信作者巴阳(zzu_bayang@163.com)

Yan Xincheng, born in 1991. PhD candidate. His main research interests include cloud data privacy protection and secure data sharing based on cryptography.

Chen Yue, born in 1965. PhD, professor and PhD supervisor. His main research interests include network and information security.

Ba Yang, born in 1989. PhD candidate. His main research interests include blockchain and data security, applied cryptography.

Jia Hongyong, born in 1978. PhD, lecturer. His main research interests include applied cryptography and hierarchical data access control.

Zhu Yu, born in 1992. Master candidate, assistant engineer. His main research interests include cloud computing and data security.