張曙光，咸鶴群，王利明，劉紅燕

1(青島大學 計算機科學技術(shù)學院，山東 青島 266071)

2(廣西密碼學與信息安全重點實驗室(桂林電子科技大學)，廣西 桂林 541004)

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

隨著大數(shù)據(jù)時代的到來，作為基礎(chǔ)設施的云存儲服務變得愈加重要.在云服務持續(xù)高速度發(fā)展的背景下，服務提供商不再局限于一味地堆積硬件，而是逐步通過盡可能提高存儲效率的方式，達到“無形”增加存儲空間并換取經(jīng)濟效益的目的.目前，提高存儲效率的技術(shù)主要包括數(shù)據(jù)壓縮和重復數(shù)據(jù)刪除.數(shù)據(jù)壓縮技術(shù)雖然能夠通過對整體數(shù)據(jù)重新編碼，實現(xiàn)存儲空間的更少占用，但由于壓縮后的數(shù)據(jù)需要在解碼后才可正常使用，這無疑增加了系統(tǒng)的計算負擔.重復數(shù)據(jù)刪除技術(shù)的思想是通過摒除數(shù)據(jù)的重復存儲，進而減少存儲冗余[1，2].生而逢時，在如火如荼發(fā)展的云計算和大數(shù)據(jù)應用場景中，同一數(shù)據(jù)副本時常被不同用戶重復存儲，造成巨量存儲空間浪費，重復數(shù)據(jù)刪除技術(shù)恰成為解決該問題的最佳方法.經(jīng)最新研究表明:重復數(shù)據(jù)刪除技術(shù)可以在備份應用系統(tǒng)中減少高達90%的存儲需求，在標準文件系統(tǒng)中使存儲需求降低約70%[3].

良好的云存儲系統(tǒng)應能夠為用戶提供安全的數(shù)據(jù)存儲環(huán)境，然而在實際應用中，云服務提供商并非完全可信.例如，F(xiàn)acebook在2013年泄露了用戶的聯(lián)系信息[4]，iCloud在2014年泄露了用戶的私密照片[5].數(shù)據(jù)加密是解決此類風險的良好選擇，然而由于數(shù)據(jù)的加密密鑰由用戶在本地獨立生成，密鑰的多樣性導致相同數(shù)據(jù)副本被加密為不同密文，使得云服務提供商無法識別數(shù)據(jù)是否重復，造成大量存儲冗余.如何對加密后的數(shù)據(jù)執(zhí)行重復安全刪除，是云存儲安全領(lǐng)域的研究熱點之一.

起初，研究者提出由云服務商提供唯一密鑰并執(zhí)行加密操作，如此，數(shù)據(jù)控制權(quán)依然駐留在云服務商中，雖然能夠抵抗外部敵手攻擊，但無法防止數(shù)據(jù)由服務商內(nèi)部泄露.Douceur等研究者提出客戶端收斂加密(convergent encryption，簡稱CE)方法[6].計算數(shù)據(jù)副本的哈希值并將其作為加密密鑰，此時輸入同一數(shù)據(jù)副本即可得到相同數(shù)據(jù)密文[7，8].收斂加密雖擁有較高的執(zhí)行效率，卻未實現(xiàn)語義安全，容易遭受離線暴力破解攻擊[9，10].Bellare等研究者提出信息鎖加密方案(message-locked encryption，簡稱MLE)[11]，雖復雜化了密鑰計算與加密方式，但與CE相比，其核心思想無變化，因此同樣無法實現(xiàn)語義安全[12，13].Bellare等研究者提出了DupLESS[14]，相同數(shù)據(jù)的不同屬主與可信第三方運行茫然偽隨機函數(shù)計算協(xié)議(oblivious pseudorandom function，簡稱OPF)，用以輸出相同加密密鑰.Duan等研究者對DupLESS進行擴展與改進，對可信第三方的任務進行分解，將密鑰生成過程的參與方擴展為多個用戶[15].文獻[14，15]中的方案無法抵抗云服務器在線窮舉攻擊.Puzio等研究者提出首個基于雙層加密的重復加密數(shù)據(jù)刪除方案ClouDedup[7]，內(nèi)層是高效的收斂加密，外層加密與解密工作外包給可信第三方.除了安全性的提高，雙層加密帶來的還有高額的計算開銷與通信開銷.與文獻[14，15]相似，ClouDedup無法防止云服務商與第三方的合謀攻擊.Stanek等人提出:用戶在上傳數(shù)據(jù)之前需要確定數(shù)據(jù)的類型，若數(shù)據(jù)屬主數(shù)量低于預定義流行度閾值，則該數(shù)據(jù)副本將被定義為非流行數(shù)據(jù)；反之，則將其標記為流行數(shù)據(jù)[17].非流行數(shù)據(jù)采用雙層加密.隨著數(shù)據(jù)副本數(shù)量不斷增加，當?shù)扔陂撝岛?，云服務商便進行外層解密，進而借助內(nèi)層收斂加密的特性，執(zhí)行重復數(shù)據(jù)刪除.同時，為了抵抗敵手進行女巫攻擊[16，18]，引入身份服務器.與文獻[7]中的方案類似，多方服務器的引入帶來高額的計算與通信開銷.Puzio等研究者基于完美哈希函數(shù)(PHF)設計了數(shù)據(jù)流行度查詢算法，依賴第三方的協(xié)助，查詢數(shù)據(jù)副本流行度，并根據(jù)查詢結(jié)果執(zhí)行相應的加密算法[19].該方案無法解決非流行加密數(shù)據(jù)重復刪除的問題[3]，且與文獻[14，15，17]類似，可信第三方實體必須實時在線參與，然而在實際應用中，部署完全可信的第三方比較困難.Liu等研究者設計首個無可信第三方參與的加密數(shù)據(jù)重復刪除方案，使用口令認證密鑰交換協(xié)議(password authenticated key exchange，簡稱PAKE)傳遞密鑰，相同數(shù)據(jù)副本屬主能夠計算得到同一加密密鑰[9].方案的不足點在于，參與方必須實時在線，導致系統(tǒng)的可行性與實用性較低.

本文貢獻:

本文在劃分數(shù)據(jù)類型的基礎(chǔ)上，提出一種無需初始數(shù)據(jù)上傳用戶與可信第三方實時在線的加密數(shù)據(jù)重復刪除方案.

1) 基于橢圓曲線構(gòu)造流行度查詢標簽，在語義安全的前提下，使用該標簽驗證加密副本是否產(chǎn)生于同一明文，并判斷其流行度.借助密文策略屬性加密，保證查詢標簽生成協(xié)議的安全實現(xiàn)；

2) 設計安全的密鑰共享協(xié)議，確保同一數(shù)據(jù)副本的初始屬主能夠借助云服務商，將加密密鑰安全離線共享至后繼屬主，實現(xiàn)非流行數(shù)據(jù)重復刪除.構(gòu)造新的流行數(shù)據(jù)加密算法，增強流行數(shù)據(jù)的存儲安全；

3) 總結(jié)常見的敵手模型，通過安全分析證明本方案可抵御敵手模型中的惡意攻擊.

1 系統(tǒng)設計與敵手模型

1.1 系統(tǒng)模型

如圖1所示，本系統(tǒng)共包含3類實體:密鑰生成中心(KDC)、用戶群(users)與云服務器(CSP).系統(tǒng)建立初期，KDC為用戶生成密鑰對集合，并將隨機值密文參數(shù)集合部署在云服務器，然后轉(zhuǎn)入離線狀態(tài).云服務器為用戶提供數(shù)據(jù)的在線存儲與共享服務，且具有刪除重復加密數(shù)據(jù)的功能.

1.2 設計目標

本方案需要滿足以下性質(zhì).

1) 有效性

a) 云服務器能夠識別重復的加密數(shù)據(jù)，并判斷數(shù)據(jù)類型(非流行數(shù)據(jù)或流行數(shù)據(jù))，根據(jù)數(shù)據(jù)類型采取相應加密算法；

b) 數(shù)據(jù)初始上傳者能夠?qū)⒓用苊荑€通過云服務器，以離線的方式傳遞給后繼上傳者；

c) 云服務器能夠執(zhí)行加密數(shù)據(jù)重復刪除.

2) 安全性

a) 使用橢圓曲線生成的查詢標簽識別數(shù)據(jù)冗余度與流行度，識別過程不泄漏數(shù)據(jù)的任何明文信息；

b) 初始上傳者將加密密鑰以密文形式存儲在云服務器，但云服務器無法對其解密；

c) 客戶端加密數(shù)據(jù)重復刪除與云服務器端重復數(shù)據(jù)刪除混合使用，防止側(cè)信道攻擊.

3) 高效性

a) 保證流行度查詢標簽生成算法和密鑰傳遞算法的高效性；

b) 針對不同流行度數(shù)據(jù)，采用不同加密算法，在確保安全性的前提下，提高系統(tǒng)執(zhí)行效率.

1.3 敵手模型

在數(shù)據(jù)安全需求方面，用戶假定云服務提供商是不可信的；用戶在系統(tǒng)效率方面的要求與云服務提供商的存儲成本存在一定矛盾.因此，本文不考慮用戶與云服務器合謀攻擊.由于在重復數(shù)據(jù)刪除方案中，側(cè)信道攻擊主要針對客戶端重復數(shù)據(jù)刪除(窮舉并上傳文件，觀察是否發(fā)生重復數(shù)據(jù)刪除)，而本方案只對隱私度比較低的流行數(shù)據(jù)使用客戶端重復數(shù)據(jù)刪除，因此側(cè)信道攻擊問題不是本文的研究重點.

本文的敵手有以下兩類.

1) 云服務提供商

云服務提供商能夠按照系統(tǒng)所設計的協(xié)議與用戶執(zhí)行所有的交互，可以訪問或復制用戶存儲在云服務器上的加密數(shù)據(jù)、查詢標簽等所有信息，因此可以對查詢標簽與加密數(shù)據(jù)執(zhí)行離線窮舉攻擊，其攻擊方式為:猜測窮舉某數(shù)據(jù)內(nèi)容的所有可能，構(gòu)造查詢標簽集合并與用戶的查詢標簽進行比較，驗證猜測正確性，最終獲得數(shù)據(jù)內(nèi)容.

2) 用戶群中的惡意成員(惡意用戶)

惡意用戶擁有與合法用戶完全相同的訪問能力和權(quán)限，掌握KDC分配的密鑰對.其可能的攻擊方式如下.

a) 劫持受害者與云服務器的通信信道，假冒云服務器，與受害者執(zhí)行方案中的所有交互協(xié)議，對受害者的查詢標簽執(zhí)行離線窮舉攻擊，即:窮舉猜測某數(shù)據(jù)內(nèi)容的所有可能，構(gòu)造查詢標簽集合并與用戶的查詢標簽進行比較，驗證猜測正確性，獲得數(shù)據(jù)內(nèi)容；

b) 執(zhí)行在線窮舉攻擊，窮舉某數(shù)據(jù)內(nèi)容的所有可能，逐一構(gòu)造查詢標簽并發(fā)送至云服務器，根據(jù)云服務器的回復消息判斷該數(shù)據(jù)是否已被存儲在云服務器.

2 定義與預備知識

2.1 具有離線密鑰傳遞的云加密數(shù)據(jù)安全重復刪除方案

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

a)SystemSet:系統(tǒng)初始設置算法.KDC為用戶生成屬性密鑰對，并為云服務器部署密文參數(shù)；

b)PopularityCheck:流行度查詢算法.由用戶與云服務器共同完成.持有相同數(shù)據(jù)的用戶，可以在不泄露任何數(shù)據(jù)內(nèi)容的情況下獲得相同的查詢標簽，進而查詢數(shù)據(jù)流行度；

c)UnPopularDedup:非流行加密數(shù)據(jù)重復刪除算法.由用戶與云服務器共同完成.云服務器存儲首次上傳的加密數(shù)據(jù)；若云服務器檢測到冗余數(shù)據(jù)被上傳，則將其刪除，并為當前用戶創(chuàng)建數(shù)據(jù)的訪問鏈接；

d)PopularUpload:流行加密數(shù)據(jù)重復刪除算法.由用戶與云服務器共同完成.若擁有某數(shù)據(jù)的用戶數(shù)量等于流行度閾值，則用戶上傳收斂加密密文；若大于流行度閾值，則執(zhí)行客戶端重復數(shù)據(jù)刪除，即:用戶無需實際上傳加密數(shù)據(jù)，云服務器會為其創(chuàng)建數(shù)據(jù)的訪問鏈接.

2.2 有限域上的橢圓曲線

定義有限域GF(P)，其特征P≠2，3，參數(shù)a，b∈GF(P)滿足4a3+27b2≠0.

定義滿足等式y(tǒng)2=x3+ax+b的點(x，y)∈GF(P)×GF(P)與無窮遠點O構(gòu)成的集合為橢圓曲線E(a，b)(GF(P))[20?23].

在下面定義的加法運算下，這些點可構(gòu)成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〉:系統(tǒng)初始化.輸入安全參數(shù)λ，輸出密鑰對〈PK，MS〉；

b)Encrypt(PK，F(xiàn)，S)→CS:加密算法.輸入公鑰PK，消息F，訪問結(jié)構(gòu)S，輸出密文CS；

d)Decrypt(PK，SK，CS)→F:解密算法.輸入公鑰PK，用戶私鑰SK，密文CS，其中，訪問策略隱含在CS中.當且僅當ATi∈S，才能解密得到消息F[27，28].

3 具有離線密鑰傳遞的云加密數(shù)據(jù)安全重復刪除方案

3.1 方案概述

系統(tǒng)建立初始，KDC通過SystemSet算法為每個注冊用戶生成屬性加密算法的公私鑰對，并將密文參數(shù)集合部署到云服務器.在PopularityCheck算法中，用戶發(fā)送數(shù)據(jù)短哈希值至云服務器，以獲取生成查詢標簽所需要的參數(shù)值，并使用橢圓曲線計算流行度查詢標簽，用以查詢數(shù)據(jù)的流行度.在此之后，云服務器將查詢結(jié)果回傳至用戶，并與用戶執(zhí)行UnPopularDedup或PopularUpload，其中，UnPopularDedup表示非流行加密數(shù)據(jù)重復刪除算法，PopularUpload表示流行加密數(shù)據(jù)重復刪除算法.

3.2 SystemSet

1) KDC執(zhí)行以下算法生成密鑰對〈PK，MS〉.

算法1.私鑰生成算法.

3) KDC通過以下方式得到密文參數(shù)集合，并將其部署在云服務器.

算法2.屬性加密算法.

3.3 PopularityCheck

3.3.1 獲取生成查詢標簽所需隨機數(shù)

Ui選取短哈希函數(shù)SH，計算數(shù)據(jù)Fi的短哈希值shi=SH(Fi)，并發(fā)送shi至云服務器(短哈希函數(shù)具有較高的碰撞率，相同數(shù)據(jù)的短哈希值必定相同，不同數(shù)據(jù)的短哈希值可能相同).

3.3.2 流行度查詢

Ui使用隨機數(shù)向量集合(第3.3.1節(jié)中，兩種情況下j的取值分別為j∈[1，Nmax]與j=0，將二者合并得到j∈[0，Nmax])與云服務器執(zhí)行算法3，以查詢數(shù)據(jù)的流行度.

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

3.3.3 UnpopularDedup

3.3.4 PopularDedup

4 安全分析與證明

結(jié)合前文所述的敵手模型，本節(jié)從以下4個方面分析方案的安全性.

4.1 密文參數(shù)與查詢標簽安全性

1) 密文參數(shù)安全.

定理1.若ATCSP?S，則屬性加密方案中的解密算法(Decrypt)無法正常執(zhí)行，其中，ATCSP表示云服務器屬性集合，?表示云服務器屬性集合無法滿足用戶屬性集合.

證明:由SystemSet可知:

2) 流行度查詢標簽安全.

云服務器雖持有σi，j與參數(shù)密文Xj1，Xj2，然而，由定理1可知，云服務器無法解密Xj1，Xj2，故只能通過以下方式窮舉查詢標簽，以猜測加密數(shù)據(jù)的明文信息.

a) 窮舉數(shù)據(jù)集合{Fr}r∈[1，n]；

b) 窮舉隨機參數(shù)值集合{xt}t∈[1，n]；

c) 窮舉隨機參數(shù)值集合{μz}z∈[1，n]；

d) 計算標簽集合{σCSP=ηi?SKCSP?(H(Fr+xtmodn)?μz)}；

e) 將得到的結(jié)果與iσ′逐一比較，其中，，觀察是否存在相等值；

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

然而，由以上可知，云服務器攻擊的時間復雜度為O(n3).由于n可視為無限大值，因此在實際應用中，實現(xiàn)第e)步是極為困難的.

4.2 防止假冒云服務器的行為

以下為惡意用戶UD假冒云服務器與受害者Ui運行PopularityCheck算法的過程.

a)Ui向云服務器發(fā)出執(zhí)行PopularityCheck請求；

b)UD截獲請求消息，發(fā)送ηDG，XD1，XD2至t(a)；

c)Ui計算并將發(fā)送至UD；

d)UD將查詢標簽σD=ηD?dD?C′發(fā)送至Ui；

e) 由于UD持有ηDG，XD1，XD2，因此可以對CD采取離線窮舉攻擊，即執(zhí)行以下操作:

①窮舉數(shù)據(jù){Fr}r∈[1，n]；

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

③與Ci逐一對比.若Cr=Ci，則Fr=Fi.

解決方法:用戶在與云服務器通信之前，需要借助公鑰基礎(chǔ)設施(PKI)獲取并驗證云服務器身份，借助PKCSP協(xié)商會話密鑰對通信內(nèi)容加密.UD便無法仿冒云服務器身份獲取有用信息.

4.3 防止用戶進行在線窮舉攻擊

定理3.惡意用戶UD無法對云服務器中的非流行數(shù)據(jù)Fi執(zhí)行在線窮舉攻擊.

證明:不失一般性，UD的攻擊方式為:

a)UD窮舉數(shù)據(jù){Fr}r∈[1，n]；

b)UD將窮舉結(jié)果逐一與云服務器運行PopularityCheck和UnpopularDedup；

d)UD根據(jù)響應，判斷攻擊是否成功.

由UnpopularDedup可知:

4.4 標簽唯一性與正確性證明

1) 唯一性證明

2) 正確性證明

5 實驗分析

實驗采用C++語言，借助OPENSSL[29]，GMP[30]，PBC[31]和CP-ABE[32]函數(shù)庫實現(xiàn)了系統(tǒng)軟件.以阿里云作為云服務提供商，租用虛擬機配置為4Core CPU，8GB內(nèi)存，1Mbps帶寬，1T存儲空間.橢圓曲線基域大小設定為512bit，域中元素大小為160bit.隨機選取了2 500個文件存儲在云服務器中.隨機設定擁有每個文件的用戶數(shù)量.設置流行度閾值為T=8，非流行數(shù)據(jù)與流行數(shù)據(jù)的比例大致為3:4.

通過以下3組實驗，證明方案的高效性.

a) 上傳大小為80MB的文件FA，計算本方案各階段的時間開銷；

b) 上傳大小為10MB的文件FB，分別測試本方案與PerfectDedup方案[19]的總時間開銷；

c) 上傳大小相同的文件，比較本方案、文獻[17]中的方案、文獻[19]中的方案各自所需的存儲開銷.

實驗中的每步操作重復執(zhí)行20次，取平均值作為實驗結(jié)果.

1) 系統(tǒng)每階段的時間開銷.

Fig.2 Time span on each stage of the system圖2 系統(tǒng)每階段的時間開銷

如何高效且安全地識別冗余數(shù)據(jù)，是加密數(shù)據(jù)重復刪除方案的基礎(chǔ).本文對較為優(yōu)異的現(xiàn)有相關(guān)方案的生成查詢標簽算法進行了效率測試，并與本方案比較.實驗結(jié)果如圖3所示，本方案在生成查詢標簽方面，明顯優(yōu)于其他方案.

Fig.3 Time span on check tag generation of each scheme圖3 各方案生成查詢標簽所需時間開銷

為達到語義安全，本方案需要將初始上傳屬主的加密密鑰安全共享至后繼上傳屬主，這會使數(shù)據(jù)加密算法產(chǎn)生部分額外通信與計算開銷.然而，由于密鑰傳遞方式的設計較為高效，因此它對加密算法的性能影響較小.本方案與CE[6]的比較結(jié)果在表1中給出，其中，t(a)表示本方案在執(zhí)行加密算法時產(chǎn)生的時間開銷，t(b)表示執(zhí)行收斂加密時產(chǎn)生的時間開銷，t(b)?t(a)表示執(zhí)行兩種加密算法時產(chǎn)生時間開銷的差值，表示以上差值為系統(tǒng)帶來影響的大小.實驗結(jié)果表明:二者加密算法所需的時間開銷相差甚??；且隨著數(shù)據(jù)不斷增大，差值漸成為可忽略值.

Table 1 Comparison of time span between our scheme and CE表1 本方案與CE方案的時間開銷對比

2) 較少的總時間開銷.

本方案與PerfectDedup方案[19]所需要的總時間開銷對比如圖4所示.與PerfectDedup相比，由于本方案不需要進行第三方服務器的數(shù)據(jù)更新，流行度查詢階段需要的時間開銷較小，因此在總時間開銷方面，本方案具有較明顯的優(yōu)勢.

Fig.4 Comparison of total time span between our scheme and PerfectDedup圖4 本方案與PerfectDedup 方案的總時間開銷對比

3) 占用更少的存儲空間.

通過上傳大小為500MB文件，測試本方案、文獻[17]中的方案、文獻[19]中的方案各自占用云服務器中的存儲空間情況，實驗結(jié)果如圖5所示.由于本方案支持非流行數(shù)據(jù)重復刪除，因此能夠節(jié)省更多的存儲空間.文件越大，優(yōu)勢越明顯.

4) 方案特點比較.

由上述實驗可知，擺脫實時在線第三方的依賴與劃分數(shù)據(jù)流行度，是減少方案計算開銷與通信開銷的有效方法.表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 總結(jié)與展望

本文提出一種無需初始數(shù)據(jù)上傳用戶和可信第三方實時在線參與的加密數(shù)據(jù)重復刪除方法.基于橢圓曲線構(gòu)造流行度查詢標簽，在語義安全的前提下，使用該標簽識別數(shù)據(jù)冗余度與流行度.借助密文策略屬性加密，保證查詢標簽生成協(xié)議與密鑰共享協(xié)議的安全實現(xiàn)，同一數(shù)據(jù)副本的初始上傳用戶能夠借助云服務商，將加密密鑰安全離線共享至后繼上傳用戶，實現(xiàn)非流行數(shù)據(jù)重復刪除.改進后的收斂加密算法，能夠使用戶自行計算安全加密密鑰，不僅保證了流行數(shù)據(jù)的存儲安全，同時提高了云服務商消除流行重復加密數(shù)據(jù)的效率.本文最后進行了詳細的安全性分析與效率評估，并與其他現(xiàn)有方案對比，證明本方案在滿足語義安全的同時，進一步提高了加密數(shù)據(jù)重復刪除系統(tǒng)的執(zhí)行效率.

在本文基礎(chǔ)上設計具有動態(tài)更新數(shù)據(jù)所有權(quán)的安全加密數(shù)據(jù)重復刪除方案，是下一步的研究方向.