云加密數據安全重復刪除方法?

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

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

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

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

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

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

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

本文貢獻:

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

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

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

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

1 系統設計與敵手模型

1.1 系統模型

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

1.2 設計目標

本方案需要滿足以下性質.

1) 有效性

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

b) 數據初始上傳者能夠將加密密鑰通過云服務器，以離線的方式傳遞給后繼上傳者；

c) 云服務器能夠執行加密數據重復刪除.

2) 安全性

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

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

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

3) 高效性

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

b) 針對不同流行度數據，采用不同加密算法，在確保安全性的前提下，提高系統執行效率.

1.3 敵手模型

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

本文的敵手有以下兩類.

1) 云服務提供商

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

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

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

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

b) 執行在線窮舉攻擊，窮舉某數據內容的所有可能，逐一構造查詢標簽并發送至云服務器，根據云服務器的回復消息判斷該數據是否已被存儲在云服務器.

2 定義與預備知識

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

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

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

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

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

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

2.2 有限域上的橢圓曲線

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

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

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

b)Encrypt(PK，F，S)→CS:加密算法.輸入公鑰PK，消息F，訪問結構S，輸出密文CS；

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

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

3.1 方案概述

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

3.2 SystemSet

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

算法1.私鑰生成算法.

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

算法2.屬性加密算法.

3.3 PopularityCheck

3.3.1 獲取生成查詢標簽所需隨機數

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

3.3.2 流行度查詢

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

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

3.3.3 UnpopularDedup

3.3.4 PopularDedup

4 安全分析與證明

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

4.1 密文參數與查詢標簽安全性

1) 密文參數安全.

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

證明:由SystemSet可知:

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

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

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

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

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

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

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

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

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

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

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

a)Ui向云服務器發出執行PopularityCheck請求；

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

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

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

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

①窮舉數據{Fr}r∈[1，n]；

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

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

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

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

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

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

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

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

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

由UnpopularDedup可知:

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

1) 唯一性證明

2) 正確性證明

5 實驗分析

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

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

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

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

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

實驗中的每步操作重復執行20次，取平均值作為實驗結果.

1) 系統每階段的時間開銷.

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

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

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

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

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

2) 較少的總時間開銷.

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

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

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

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

4) 方案特點比較.

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

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

在本文基礎上設計具有動態更新數據所有權的安全加密數據重復刪除方案，是下一步的研究方向.