基于雙層加密的云存儲數據去重方法*

高文靜, 咸鶴群, 田呈亮, 李增鵬, 賀云龍

1. 青島大學 計算機科學技術學院, 青島266071

2. 中國科學院信息工程研究所信息安全國家重點實驗室, 北京100093

1 引言

數據去重技術是一種高效的數據縮減技術, 可以有效的節(jié)省存儲空間、降低傳輸帶寬消耗. 數據去重也被稱作重復數據刪除(data deduplication), 即每個數據副本只在云服務器上存儲一份, 并為擁有此數據所有權的用戶創(chuàng)建訪問鏈接[1]. 但隨著云服務器端數據安全問題的不斷出現[2], 為保護數據隱私, 用戶普遍將數據進行加密后上傳至云服務器存儲. 對于云存儲中加密數據的去重問題, Douceur 等人首次提出收斂加密(CE, convergent encryption)[3], 作為數據隱私性與去重高效性的平衡方案. CE 直接使用明文數據的哈希值作為加密密鑰, 易于實現且計算效率高, 在云存儲數據去重中得到了廣泛的應用[4-6]. 但加密密鑰過度依賴明文, 使其易遭受離線窮舉攻擊. 為明確安全目標, 定義形式化安全模型, Bellare 等人基于CE 提出了消息鎖加密(MLE, message-locked encryption)[4], 加密密鑰由明文數據和系統(tǒng)參數共同計算得到, 但本質上和收斂加密相同, 不能達到語義安全.

Puzio 等人提出ClouDedup 方案[5],在CE 的基礎上,增加額外的加密操作和訪問控制機制來保證數據的機密性. 該方案將數據外層加密和解密過程外包給第三方服務器, 并借助MM (metadata manager)來存儲包括加密密鑰在內的元數據. 該方案中系統(tǒng)要求額外服務器都是完全可信的, 且不能合謀. Stanek等人首次提出了“數據流行度” 的概念, 根據隱私程度將用戶數據劃分為流行數據和非流行數據[7]. 使用語義安全的加密算法保護非流行數據的安全, 對隱私程度不高的流行數據執(zhí)行數據去重操作, 需借助完全可信的IS (indexing service) 提供索引服務. Puzio 等人提出PerfectDedup 方案[8], 通過完美哈希函數計算數據標識, 作為數據流行度查詢的依據. 該方案需借助可信第三方保證非流行數據的語義安全, 實現對流行數據的去重. 但可信第三方在實際應用中部署困難, 易成為系統(tǒng)瓶頸[9].

Bellare 等人提出DupLESS 方案[1], 用戶與密鑰服務器KS (key server) 通過運行OPRF (oblivious pseudorandom function) 協議生成加密密鑰, 保證數據的安全性. 該方案可有效的抵抗蠻力攻擊, 同時也要求KS 完全可信, 難以抵抗KS 和云服務器的合謀攻擊. Liu 等人提出一種無需可信第三方的加密數據安全去重方案[10]. 擁有相同數據副本的用戶通過在線運行PAKE (password authenticated key exchange) 協議進行密鑰交換, 能夠有效的抵抗在線窮舉攻擊. 但該方案需要用戶在上傳數據之前, 與其他用戶執(zhí)行PAKE 協議來獲取加密密鑰, 要求參與協商的用戶實時在線, 一定程度上增加了通信開銷, 也降低了方案的實用性.

Stanek 等人在原有方案的基礎上提出改進的門限數據去重方案[11], 其核心為門限密碼系統(tǒng), 進一步保證了非流行數據的語義安全. 該方案借助IRS (index repository service) 提供索引服務, 并進行流行度查詢. 非流行數據采用雙層加密, 在云服務器端仍保存多份副本, 存在較大的數據冗余. 該方案要求IRS完全可信, 才可實現數據的安全去重, 不能擺脫可信第三方的束縛. Yuan 等人提出dedupDUM 方案[12],支持用戶動態(tài)管理, 采用預先驗證的訪問控制技術, 可驗證用戶身份的有效性. 該方案對用戶數據采用重加密技術保護, 在隨機收斂加密的基礎上, 使用組密鑰進行重加密. 組密鑰根據組內用戶信息生成, 每當用戶組發(fā)生改變時, 組密鑰都隨之發(fā)生變化, 對用戶數據進行一次重加密. 頻繁的加解密操作一定程度上消耗了云服務器端的計算資源. Wang 等人提出一種基于密鑰共享的數據安全去重方案[13], 對于收斂加密密鑰的管理問題提出一種基于所有權證明的密鑰共享方法, 但需借助可信第三方實現. Fan 等人提出了一種隱私保護的數據去重方案[14], 依賴可信執(zhí)行環(huán)境TEE(trusted execution environment)提供安全的密鑰管理, 可以有效的保護敏感數據的機密性.

針對以上問題, 本文提出了一種基于雙層加密的云存儲數據去重方案, 擺脫了可信第三方的束縛, 實現云存儲中加密數據的高效去重. 主要貢獻如下:

(1) 無需任何第三方參與, 加強了去重方案的實用性；

(2) 實現了對非流行數據的去重, 進一步提高去重效率；

(3) 添加了額外的安全機制, 有效防止非授權用戶下載數據.

2 預備知識

2.1 收斂加密

收斂加密(CE, convergent encryption) 是解決加密數據去重的有效措施. 通過對明文數據M 進行哈希計算得到加密密鑰K = H(M), 使用K 對M 加密得到密文C = SE(K,M). 收斂加密執(zhí)行效率高, 但在數據的信息熵較低時, 易遭受離線窮舉攻擊. 即攻擊者窮舉{Mi}(i=1,2,···), 計算Mi的哈希值Ki=H(Mi), 并進一步計算密文Ci=SE(Ki,Mi). 通過對比C =Ci是否成立, 即可對明文數據M進行猜測.

2.2 ElGamal 公鑰密碼算法

ElGamal 公鑰密碼算法的安全性基于離散對數問題[15]. 設q 是一個大素數, G 為以g 為生成元的q階循環(huán)群, 其中g ∈Zq.

離散對數問題: 若給定x, x ∈Zq, 計算y ≡gxmod q 是容易的; 但對于給定的y ∈G, 求解x ≡loggy mod q 是困難的. 我們把求解x ≡loggy mod q 的困難問題稱為離散對數問題.

ElGamal 公鑰密碼算法主要包含以下三個函數:

(1) {pk,sk} ←KeyGen(q,G,g): 密鑰生成函數, 以(q,G,g) 作為輸入, 輸出公私鑰對{pk,sk}. 選取唯一的sk, 1 ＜sk ＜q-1, 計算pk=gskmod q. pk 為公鑰, 對外公開; sk 為私鑰, 由用戶保存.

(2) c ←E(pk,m): 加密函數, 輸入公鑰pk 和待加密數據m, 輸出密文c. 對于數據m, 首先選取一個秘密的隨機數, 1 ＜k ＜q. 計算c1=gkmod q, c2=m(pk)kmod q. 輸出密文c=c1‖c2.

(3) m ←D(sk,c): 解密函數, 輸入私鑰sk 和待解密密文c, 輸出原始數據m. 其中c = c1‖ c2, 計算m=c2/c1sk.

2.3 所有權證明

所有權證明(PoW, proof of ownership)[16,17]是提高客戶端數據去重方案安全性的有效措施. 通過執(zhí)行PoW, 用戶可以向服務器證明其確實擁有對某個文件的所有權, 而不是僅僅擁有文件的一小部分信息. Halevi 首次提出了基于Merkle hash tree (MHT) 的PoW 方法[17]. 用戶端和服務器端都根據文件內容建立MHT, 并根據挑戰(zhàn)問答的形式由服務器發(fā)起挑戰(zhàn). 用戶端對給定葉子節(jié)點的子集提供有效的MHT 路徑. 具體來說, PoW 是一種由證明者(用戶) 和驗證者(云服務器) 運行的交互式算法. 云服務器對于已存儲的數據M, 計算關于M 的短信息值φ(M). 向云服務器證明對M 的所有權時, 用戶計算并向云服務器發(fā)送φ′, 與其運行證明算法. 當φ′=φ(M) 并且證明正確時, 認為用戶成功證明了對于M 的所有權.

2.4 雙線性映射

設G, GT是2 個q 階的乘法循環(huán)群, 其中q 為大素數, g 是群G 的生成元, 1GT是群GT的單位元.定義映射關系e:G×G →GT, 并滿足在以下性質[18]:

(1) 雙線性: ?a,b ∈Zq, 都有e(ga,gb)=e(g,g)ab;

(2) 可計算性: ?g1,g2∈G, e(g1,g2) 是可計算的;

(3) 非退化性: ?g1,g2∈G, 使得e(g1,g2)／=1GT.

3 系統(tǒng)模型和定義

3.1 系統(tǒng)模型

本方案的系統(tǒng)模型如圖1 所示, 包含云服務器和用戶.

云服務器CSP (cloud service provider): 主要提供云存儲服務, 用于存儲用戶數據. CSP 對存儲的文件統(tǒng)計其合法上傳用戶并計數, 用于安全驗證和文件流行度查詢.

用戶U (user): 將數據外包到云服務器以節(jié)省本地存儲空間. 為保護數據隱私, 將數據加密后再上傳至云服務器.

圖1 系統(tǒng)模型Figure 1 System model

3.2 威脅模型

在本文方案中, 我們主要考慮以下兩類攻擊者:

(1) 內部攻擊者: 指系統(tǒng)內部的敵手, 主要指云服務器. 我們認為云服務器是誠實且好奇的, 可對其存儲的用戶數據進行任意訪問;

(2) 外部攻擊者: 指系統(tǒng)外部的敵手, 主要指非授權用戶. 外部敵手通過竊聽公共信道獲取部分上傳數據的相關信息, 其主要目的是非法獲取云服務器上存儲的用戶數據的明文信息.

3.3 安全目標

本文方案的安全目標如下:

(1) 數據的隱私性: 去重方案應保證存放在云服務器上用戶數據的隱私性, 包括非流行數據和流行數據. 云服務不應獲取任何關于其存儲的用戶數據的明文信息. 非授權用戶不能獲取關于云服務上存儲的用戶數據的明文信息.

(2) 數據的完整性: 去重方案應保證存儲在云服務器上用戶數據的完整性. 方案允許授權用戶下載數據時驗證其數據的完整性.

3.4 符號定義

本文中使用的符號如表1 所示.

3.5 函數定義

(1) KC←KGenCE(M), 收斂加密方案中的密鑰生成函數. 輸入數據M, 輸出對應的收斂加密密鑰KC.

(2) C ←Enc(K,M), 使用對稱加密算法的加密函數. 輸入密鑰K 和待加密數據M, 輸出加密后的密文C.

(3) M ←Dec(K,C), 使用對稱加密算法的解密函數. 輸入密鑰K 和待解密數據C, 輸出解密后的數據M.

(4) 安全的哈希函數H: {0,1}*→Zq; 短哈希函數SH: {0,1}*→{0,1}s.

(5) c ←E(pk,m), ElGamal 公鑰密碼算法中的加密函數. 輸入公鑰pk 和數據m, 輸出密文c.

表1 符號定義Table 1 Symbol definition

(6) m ←D(sk,c), ElGamal 公鑰密碼算法中的解密函數. 輸入私鑰sk 和密文c, 輸出原始數據m.

(7) K ←KeyExt(p,k), 密鑰擴展函數. 輸入輔助參數p 和初始密鑰k, 確定性輸出長度為l 的密鑰.

(8) TF←TGen(p,CF), 標簽生成函數. 輸入參數p 和文件F 的收斂密文CF, 輸出文件標簽TF. 具體來說, 計算V = gH(CF)·p, Aux = gp, 數據標簽TF為V 和Aux 組成的二元組, 即TF=＜V,Aux ＞. 本文方案中使用用戶私鑰sk 作為標簽生成函數的參數.

(9) re ←TCheck(TF,Tag_List), 標簽查找函數. 輸入文件標簽TF和標簽列表Tag_List, 輸出查找結果re. 若存在T′=＜V′,Aux′＞∈Tag_List 且e＜V,Aux′＞=e＜V′,Aux ＞, 則代表Tag_List 中已存在該文件標簽, 輸出re=T′; 否則, 輸出re=0.

4 方案

本文提出一種基于雙層加密的云存儲數據去重方案, 無需第三方參與, 實現云存儲中加密數據的高效去重. 通過劃分數據流行度, 對隱私程度較高的非流行數據, 采用雙層加密. 內層為簡單高效的收斂加密,外層采用語義安全的對稱加密. 加密密鑰由用戶根據數據信息結合云服務器提供的隨機密鑰計算得到, 不需借助額外服務器或實時在線用戶傳遞密鑰. 當云服務器上存儲的用戶數據達到流行度閾值時, 該數據轉換為流行數據, 去除外層加密, 云服務器存儲數據的收斂加密結果. 本方案能夠實現對非流行數據的去重,而且在數據流行度轉換時刻, 不需要用戶重復上傳數據, 進一步節(jié)省了網絡帶寬, 提高了去重效率.

方案主要包括三部分: 系統(tǒng)初始化, 文件上傳和文件下載.

4.1 系統(tǒng)初始化

系統(tǒng)初始化階段, 生成一個密鑰池KeySet, 其中包含足夠多數量的隨機密鑰, 密鑰長度為固定值s.密鑰池安全的存放在CSP 上. 對每一個加入系統(tǒng)的用戶Ui確定唯一的身份標識IDi, 并為之分配專屬的公私鑰對{pki,ski}, 其中公鑰pki對外公開, 私鑰ski由Ui保存.

CSP 上存放有文件標簽列表Tag_List,文件信息表DB.Tag_List 為CSP 上已存儲數據對應標簽的集合, 主要用于數據重復性檢測. DB 與CSP 上存儲的每一個文件相關聯, 具體來說, 對于CSP 上存儲的文件F, 以標簽TF作為標識, 與其相關聯的文件信息表DB[TF] 包含四條記錄, DB[TF].data 為存儲的文件密文, DB[TF].user 為文件的合法用戶列表, DB[TF].rkey 為文件加密所需的隨機密鑰, DB[TF].ctr為文件的合法用戶數量.

4.2 文件上傳

用戶Ui選擇文件F 上傳到云服務器CSP 存儲時(文件上傳的具體流程見算法1), 首先對F 進行收斂加密, 計算文件標簽TF,i, 發(fā)送上傳請求upload_request‖IDi‖TF,i到CSP. CSP 收到Ui的上傳請求后, 進行數據重復性檢測. CSP 運行標簽查找函數re ←TCheck(TF,i,Tag_List), 若re = 0, 則本次上傳為文件的初始上傳, 執(zhí)行算法2; 否則, 上傳文件為重復文件, 且該文件在CSP 中對應標簽TF為標簽查找函數的返回值re, 執(zhí)行算法3.

算法1 文件上傳1. Ui:2. Compute convergent key KC ←KGenCE(F)3. Compute convergent ciphertext CF ←Enc(KC,F)4. Compute file tag TF,i ←TGen(ski,CF)5. Ui →CSP: Send upload_request ‖ IDi ‖ TF,i to CSP 6. CSP: re ←TCheck(TF,i,Tag_List)7. if re = 0, then execute Algorithm 2 8. else, TF = re, execute Algorithm 3

4.2.1 初始文件上傳

上傳文件F 為CSP 中不存在的文件時, 為初始文件上傳.

CSP 首先將Ui上傳的文件標簽TF,i添加到文件標簽列表Tag_List. Ui作為F 的初始上傳者, 其上傳的文件標簽TF,i作為CSP 中對于F 的唯一標識, 即TF= TF,i. 其次初始化對應文件信息表, 設置DB[TF].ctr=0, 并在密鑰池KeySet 中隨機選取密鑰rk, 令DB[TF].rkey=rk. CSP 將rk 用公鑰加密RK ←E(pki,rk), 發(fā)送data_demand‖RK 到Ui, 要求Ui上傳數據.

Ui收到RK 后用私鑰對其解密rk ←D(ski,RK), 并以收斂加密密文的短哈希值SH(CF) 和rk 作為輸入, 通過密鑰擴展函數計算加密密鑰K ←KeyExt(SH(CF),rk). Ui用K 對文件的收斂加密密文CF進行再加密得到雙層加密密文←Enc(K,CF), 并將data_upload‖IDi‖發(fā)送到CSP.

CSP 收到Ui上傳的數據后, 存儲文件密文DB[TF].data =, 更新用戶列表DB[TF].users ={IDi}, 并初始化DB[TF].ctr=1. Ui保存{TF,i,KC,K}.

至此, 文件上傳結束. 初始文件上傳的具體流程見算法2.

算法2 初始文件上傳1. CSP: TF = TF,i, initialize DB[TF]2. DB[TF].ctr = 0 3. Select random key rk←RKeySet, DB[TF].rkey = rk 4. Encrypt rk using pki, RK ←E(pki,rk)5. CSP →Ui: Send data_demand ‖ RK to Ui 6. Ui:7. Decrypt RK, rk ←D(ski,RK)8. Compute encryption key K ←KeyExt(SH(CF),rk)9. Re-encrypt F, C*F ←Enc(K,CF)10. Ui →CSP: Send data_upload ‖ IDi ‖ C*F to CSP 11. CSP: DB[TF].data = C*F, DB[TF].users = {IDi}, DB[TF].ctr = 1 12. Ui: Store {TF,i,KC,K}.

4.2.2 后續(xù)文件上傳

上傳文件F 為CSP 中已存在的文件時, 為后續(xù)文件上傳, 系統(tǒng)執(zhí)行數據去重操作, 用戶無需再上傳數據.

CSP 發(fā)送PoWverif_request 給Ui, 要求進行PoW 驗證. 若所有權驗證通過, 則證明Ui確實擁有F, CSP 將對應文件信息表中信息進行更新, DB[TF].ctr+=1, 并將Ui添加到合法用戶列表中DB[TF].users=DB[TF].users ∪{IDi}.

根據文件的合法用戶數量DB[TF].ctr 和流行度閾值t 之間的關系, 又可分為以下三種情況:

(1) 當DB[TF].ctr ＜t 時, 我們定義F 為非流行文件, 具有較高的隱私性. Ui需與CSP 交互獲取文件加密密鑰.CSP 將文件隨機密鑰rk 用公鑰加密RK ←E(pki,rk) 并發(fā)送給Ui. Ui收到RK 之后用私鑰解密, rk ←D(ski,RK), 得到rk. 并計算文件加密密鑰K ←KeyExt(SH(CF),rk). Ui保存{TF,i,KC,K}.

(2) 當DB[TF].ctr = t 時, 為流行度轉換, 即經過本次上傳之后, F 由非流行文件轉變?yōu)榱餍形募?Ui需上傳輔助信息, 用于存儲在CSP 上文件密文的外層解密.CSP 發(fā)送auxinfo_demand 給Ui要求上傳輔助信息. Ui計算輔助密鑰auxKey=SH(CF) 并發(fā)送到CSP. CSP 計算加密密鑰K ←KeyExt(auxKey,DB[TF].rkey). CSP 用該密鑰解密已存儲的文件密文←Dec(K,DB[TF].data), 并進一步驗證SH() 與auxKey 是否相等. 若auxKey = SH(), 則解密正確, 并更新DB[TF].data =. 此時, CSP 上存儲的數據為文件的收斂加密密文. Ui只需保存{TF,i,KC} 用于后期文件下載.

(3) 當DB[TF].ctr＞t 時,我們定義F 為流行文件,具有較低的隱私性. Ui只需自行保存{TF,i,KC},用于后期文件下載.至此, 文件上傳操作結束. 后續(xù)文件上傳的具體流程見算法3.

算法3 后續(xù)文件上傳1. CSP →Ui: Send PoWverif_request to Ui 2. Ui running PoW with CSP 3. if verification successful, then 4. CSP: DB[TF].ctr+ =1, DB[TF].users = DB[TF].users ∪{IDi}5. if DB[TF].ctr ＜t, then 6. CSP: rk = DB[TF].rkey, RK ←E(pki,rk)7. CSP →Ui: Send RK to Ui 8. Ui:9. Decrypt RK, rk ←D(ski,RK)10. Compute encryption key K ←KeyExt(SH(CF),rk)11. Store {TF,i,KC,K}12. end 13. else if DB[TF].ctr = t, then 14. CSP →Ui: Send auxinfo_demand to Ui 15. Ui: Compute auxKey =SH(CF)16. Ui →CSP: Send auxinfo_upload ‖ auxKey to CSP 17. CSP:18. Compute encryption key K ←KeyExt(auxKey,DB[TF].rkey)19. Compute C′F ←Dec(K,DB[TF].data)20. DB[TF].data = C′F 21. Ui: Store {TF,i,KC}22. end 23. else, Ui: Store {TF,i,KC}24. end 25. else, return ERROR

4.3 文件下載

若用戶Uj下載文件F, 則發(fā)送下載請求download_request ‖ IDj‖ TF,j到CSP. CSP 首先根據該用戶上傳的文件標簽TF,j查找CSP 上F 對應的文件標簽TF. 其次, CSP 查詢用戶權限, 若IDj∈DB[TF].users, 則為合法用戶, 進一步驗證用戶身份. CSP 選取隨機數r, 用該用戶的公鑰加密R ←E(pkj,r) 并發(fā)送給Uj. Uj用私鑰解密得到r′←D(skj,R), 將H(r′) 發(fā)送給CSP. CSP 計算H(r)并與收到的H(r′)對比,若H(r′)=H(r),則用戶身份驗證通過,CSP 發(fā)送密文C =DB[TF].data給Uj.

Uj收到文件密文后, 對密文進行解密, 分以下兩種情況:

(1) Uj保存有{TF,i,KC,K}, 則首先計算MF←Dec(K,C) 并進行驗證. 若TGen(skj,MF) =TF,j, 則MF為F 的收斂加密密文, 進一步用收斂加密密鑰KC進行解密得到原始文件F =Dec(KC,MF). 若TGen(skj,C)=TF,j, 則CSP 上存儲的F 已轉變?yōu)榱餍形募? 此時Uj收到的文件密文為收斂加密密文,直接用收斂加密密鑰KC進行解密得到原始文件F =Dec(KC,C).否則, 返回錯誤信息.

(2) Uj保存有{TF,j,KC}, 首先進行驗證, 若TGen(skj,C) = TF,j, 則確定C 為F 的收斂加密密文, Uj用收斂加密密鑰進行解密得到原始文件F =Dec(KC,C).

文件下載的具體流程見算法4.

算法4 文件下載1. Uj →CSP: Send download_request ‖ IDj ‖ TF,j to CSP 2. CSP: TF ←TCheck(TF,j,Tag_List), check whether IDj ∈DB[TF].users or not 3. if IDj ∈DB[TF].users, then 4. CSP: Select random number r, compute R ←E(pkj,r) and send R to Uj 5. Uj: Compute r′ ←D(skj,R), and send H(r′) to CSP 6. CSP: Check whether H(r′) = H(r)7. if H(r′) = H(r), CSP send C = DB[TF].data to Uj 8. Uj:9. if have {TF,i,KC,K}, then 10. Compute MF ←Dec(K,C)11. if TGen(skj,MF) = TF,j, then compute F = Dec(KC,MF)12. else if TGen(skj,C) = TF,j, then compute F = Dec(KC,C)13. else, return ERROR 14. end 15. else if have {TF,j,KC}, then 16. if TGen(skj,C) = TF,j, then compute F = Dec(KC,C)17. else, return ERROR 18. end 19. end 20. else, return ERROR

5 安全性分析

根據3.2 節(jié)提出的威脅模型, 本文方案主要考慮來自內部敵手和外部敵手的攻擊. 內部敵手主要指云服務器, 外部敵手主要指非授權用戶. 本文提出方案中涉及的系統(tǒng)參數及3.4 節(jié)定義的函數均對外公開.我們認為CSP 是誠實且好奇的, 非授權用戶可能會通過假冒合法用戶與CSP 進行交互, 嘗試對CSP 上存儲的用戶數據進行非法訪問. 我們假設外部敵手憑借其攻擊能力, 可竊聽公共信道獲取部分上傳數據,從而對用戶數據進行蠻力攻擊.

5.1 數據標簽的安全性

本文方案中由用戶計算數據標簽, 云服務器基于雙線性映射e 檢測數據重復性. 方案應保證數據標簽的安全性, 接下來從數據標簽的正確性、數據標簽的唯一性和抗窮舉攻擊三方面進行分析與證明.

5.1.1 數據標簽的正確性

定理1 文件F 的初始上傳者Ui計算文件標簽TF,i=＜Vi,Auxi＞, 上傳到云服務器中保存, 作為F 的唯一標識. 那么, F 的后續(xù)上傳者Uj計算文件標簽TF,j=＜Vj,Auxj＞, 一定滿足e(Vi,Auxj) =e(Vj,Auxi).

證明: 根據標簽生成函數, Vi= gH(CF)·ski, Auxi= gski, Vj= gH(CF)·skj, Auxj= gskj, 其中CF為F 對應收斂密文. 由雙線性映射的性質, 可得以下等式:

不失一般性, 不同用戶Ui和Uj對相同文件F 計算的文件標簽TF,i=＜Vi,Auxi＞, TF,j=＜Vj,Auxj＞,一定滿足e(Vi,Auxj)=e(Vj,Auxi). 由此可證數據標簽的正確性.

5.1.2 數據標簽的唯一性

引理1 (哈希函數的抗碰撞性) 對于安全的哈希函數H : {0,1}*→Zq, ?M1,M2∈{0,1}*, 且M1／= M2, 使得H(M1) = H(M2) 的概率是可忽略的. 我們用ε 表示可忽略值, 即: Pr[H(M1) =H(M2)|M1／=M2]≤ε.

定理2 設文件F 的初始上傳者Ui計算文件標簽TF,i=＜Vi,Auxi＞, 上傳到云服務器中保存, 作為F 的唯一標識. 當用戶Uj上傳文件F′時, 計算文件標簽TF′,j=＜Vj,Auxj＞, 上傳到云服務器進行數據重復性檢測. 方案保證數據標簽的唯一性, 即存在F ／= F′, 使得e(Vi,Auxj) = e(Vj,Auxi) 的概率是可忽略的:

證明: 采用反證法進行證明. 假設存在F ／=F′, 使得e(Vi,Auxj)=e(Vj,Auxi). 即

當F ／= F′, CF／= CF′. 根據引理1, Pr[H(CF) = H(CF′)|CF／= CF′] ≤ε. 不失一般性, 若e(Vi,Auxj)=e(Vj,Auxi), 則H(CF)=H(CF′), 與假設相矛盾, 所以假設不成立. 即當且僅當F =F′時, 才滿足e(Vi,Auxj)=e(Vj,Auxi). 由此可證數據標簽的唯一性.

5.1.3 抵抗窮舉攻擊

本節(jié)針對方案中數據標簽存在被窮舉攻擊的風險進行安全性分析. 假設存在一個多項式時間的敵手A, 針對某一文件的標簽TF=＜V,Aux ＞進行離線窮舉攻擊, 進而猜測TF對應的數據明文M. 攻擊過程如下:

①A 窮舉數據{M′}, 對其進行收斂加密得到收斂加密密文CM′;

②A 選擇隨機數r←RZq, 運行標簽生成函數TM′←TGen(r,CM′), 得到TM′=＜VA,AuxA＞, 其中VA=gH(CM′)·r, AuxA=gr;

③A 通過標簽查找函數中的匹配算法，對比e(V,AuxA) 與e(VA,Aux) 是否相等;

④若e(V,AuxA)=e(VA,Aux), 則A 猜測TF對應的數據明文M =M′.

在明文空間足夠大的情況下, A 不知數據大小|M|, 以上攻擊是不可行的. 在實際應用中，用戶外包到云服務器存儲的數據小到幾 KB, 大到數 GB (例如視頻文件). 假設明文空間 MS ={M|M ∈{0,1}*,|M|≤n}, n ＞230×8. A 在該明文空間下窮舉數據M′∈MS, 成功攻破標簽TF的概率遠遠小于, 我們認為此概率是可忽略的.

5.2 保證數據的隱私性

方案保證存儲在CSP 上用戶數據的隱私性, 敵手不應獲取任何數據明文.

定理3 本文方案可防止CSP 獲取其存儲的用戶數據明文.

證明: 盡管CSP 可獲取用戶數據密文, 根據存儲的文件信息表, 可獲取文件的流行度和隨機密鑰,但仍不能解密得到數據明文. 對于某個特定密文C, 若為非流行數據的密文, 為雙層加密密文. 內層為收斂加密, 外層采用語義安全的加密算法保護, CSP 在沒有密鑰的情況下難以解密. 即使C 為流行數據的收斂加密密文, 根據引理1, CSP 在不知明文M 的情況下, 難以計算出收斂加密密鑰H(M), 不能對C 進行解密. 即CSP 無法解密獲取用戶數據明文.

引理2 (公鑰密碼的安全性) 基于離散對數困難問題的ElGamal 公鑰密鑰體制是安全的, 即在沒有私鑰的情況下, 成功解密經公鑰加密的密文的概率是可忽略的.

定理4 本文方案可有效的阻止非授權用戶獲取用戶數據明文.

證明: 非授權用戶Ua想要獲取CSP 上存儲的數據, 根據4.3 節(jié)中的文件下載操作流程, 可能假冒合法用戶身份并使用其身份標識IDi, 發(fā)送download_request‖IDi‖TF,i到CSP, 通過權限驗證. CSP發(fā)送使用公鑰pki加密的隨機數密文R = E(pki,r), 根據引理2, Ua在沒有私鑰的情況下, 無法解密獲取r. Ua不能返回給CSP 正確的驗證信息, 難以通過身份驗證. 即非授權用戶Ua無法獲取CSP 上存儲的數據.

5.3 允許授權用戶驗證數據的完整性

定理5 CSP 上存儲數據的可驗證性. 授權用戶可通過下載數據并檢測標簽的一致性, 驗證存儲在CSP 上數據的完整性.

證明: 由4.3 節(jié)中文件下載部分, 授權用戶Ub請求下載文件F, 通過CSP 發(fā)起的用戶身份驗證之后, 收到由CSP 發(fā)送的密文C. Ub對密文進行解密的過程中即可驗證數據完整性.

5.4 能有效的抵抗蠻力攻擊

本文方案考慮外部敵手對CSP 上存儲密文發(fā)動蠻力攻擊的情況, 本節(jié)主要針對該攻擊, 進行安全性分析, 建立一個安全模型游戲Game. 在該游戲中, 除了云服務器和用戶, 同時還存在一個多項式時間的攻擊者A. 假設在游戲的交互中, A 憑借其攻擊能力, 獲取了存儲在CSP 上的密文C. 本文方案能有效的抵抗來自A 的蠻力攻擊.

引理3 (蠻力攻擊) 收斂加密的密鑰由原始文件計算得到, 密鑰過度依賴明文. 若敵手已知密文, 便可窮舉數據, 對其進行加密并與已知密文進行對比, 則可能猜測出原始數據.

定理6 CSP 上存儲密文的不可區(qū)分性可保證去重方案能有效的抵抗蠻力攻擊. 即A 已知存儲在CSP 上的密文C, 通過暴力窮舉的方式猜測出原始數據M, 贏得游戲Game 的概率是可忽略的.

5.5 進一步討論

5.5.1 使用短哈希函數SH 的原因

本文方案中使用短哈希函數SH: {0,1}*→{0,1}s計算收斂加密密文的短哈希值SH(CF), 作為計算數據外層加密密鑰的輔助參數. 方案中使用短哈希函數主要有以下兩個原因:

(1) 在4.2.2 節(jié)中, 后續(xù)文件上傳的流行度轉換情況, 上傳用戶需計算輔助密鑰auxKey = SH(CF)并發(fā)送給CSP, 用于CSP 計算數據外層加密密鑰. 由于短哈希函數會增加碰撞率, 不同的數據可能計算出相同的短哈希值. 所以即使在傳輸過程中, SH(CF) 意外泄露了, 敵手也無法從其中獲取關于原始文件F 的有用信息.

(2) 短哈希值長度更短, 計算或傳輸的效率更高, 減輕用戶端計算負擔.

5.5.2 方案的改進

為了節(jié)省網絡帶寬, 本文方案僅要求文件的初始上傳者上傳文件數據, 后續(xù)上傳者只需進行驗證而不需上傳數據, 極大的節(jié)省了用戶和云服務器間的通信開銷. 而且, 本文方案具有更高的靈活性, 若用戶存在較高的安全性需求, 本文方案只需很小的代價就可改進為服務器端數據去重, 能夠有效的抵抗側信道攻擊[21], 從而具有更高的安全性.

具體來說, CSP 在用戶請求上傳文件時, 無論該用戶是否為文件的初始上傳者, 均要求用戶上傳數據密文. 即在4.2.2 節(jié)中, 對于后續(xù)文件的上傳, CSP 發(fā)送data_demand 給用戶, 要求用戶上傳密文. CSP收到用戶上傳的密文后, 再執(zhí)行去重操作. 該改進方案基于服務器端去重, 在一定程度上會增加網絡帶寬消耗, 但具有更高的安全性.

6 仿真實驗

我們分別模擬實現了云服務器端和用戶端. 使用一臺戴爾OptiPlex 5250 臺式計算機模擬云服務器,配備有3.20 GHz Intel(R) Core(TM) i5-6500 四核處理器和8 GB 運行內存, 運行操作系統(tǒng)為Windows 10. 我們另外使用了一臺聯想Lenovo s40-70 計算機模擬用戶端, 配備有1.70 GHz Intel(R) Core(TM)i5-4210 四核處理器和4 GB 運行內存, 運行操作系統(tǒng)為Windows 10. 為測試方案性能, 我們借助Visual Studio 2017 的編譯環(huán)境, 使用SQL Server 2017 數據庫存儲數據, 采用C# 語言編寫Windows 窗體應用程序模擬實現去重過程, 限制網絡傳輸帶寬為10 Mbps. 利用OPENSLL 函數庫[19]實現方案中所需的密碼算法, 其中使用MD5 哈希函數生成數據標簽, SHA-256 用于生成收斂加密密鑰, 采用256 bit 強度的AES 實現數據加解密.

我們將不同體積的數據上傳至云服務器, 并分以下三種情況進行模擬實驗:

(1) 初始文件上傳, 即上傳CSP 中不存在的文件.

(2) 非流行文件的上傳, 即上傳文件為已存儲在CSP 上, 但未超過流行度閾值的非流行文件.

(3) 流行文件的上傳, 即上傳文件為已存儲在CSP 上的流行文件.

本節(jié)的主要內容包括方案的性能分析、計算開銷、去重效率和方案特點對比四部分.

6.1 性能分析

我們從理論上對本文方案進行性能分析, 主要包括通信開銷和存儲開銷, 并與Stanek 方案[11]進行對比. 對于數據M, CT、CC分別表示數據標簽規(guī)模、密文規(guī)模, CK、Crk、Csk分別表示數據加密密鑰規(guī)模、隨機密鑰規(guī)模和用戶私鑰規(guī)模. CID表示用戶標識規(guī)模.

通信開銷主要包括文件上傳和文件下載兩部分, 文件上傳又分為初始文件上傳、非流行文件上傳和流行文件上傳三種情況. 對比結果如表2 所示, 本文方案不會增加額外的通信開銷. 對于文件的后續(xù)上傳, 無論是非流行文件還是流行文件, 都不需要重復上傳文件密文, 很大程度上節(jié)省了通信開銷.

存儲開銷對比主要包括云服務器端、額外服務器端和用戶端三部分. 我們設定數據M 為非流行數據,其合法用戶數量為N. 對比結果如表3 所示, 本文方案無需額外服務器, 沒有額外的存儲開銷. 實現了對非流行數據的去重, 相同數據在云服務器端只存儲一份副本, 很大程度上節(jié)省了云服務端的存儲空間.

表2 通信開銷對比Table 2 Communication overhead comparison

表3 存儲開銷對比Table 3 Storage overhead comparison

6.2 計算時間開銷

我們對本文方案的計算時間開銷進行了測試, 測試的主要過程包含標簽生成、所有權驗證、密鑰生成、數據加密和數據上傳. 方案中公鑰加密的數據體積較小, 計算時間忽略不計. 根據方案特點, 我們將不同體積的文件上傳至云服務器, 分三種情況進行模擬實驗. 情況1 為初始文件上傳, 需要用戶對數據進行雙層加密并上傳到云服務器, 該情況下的測試結果如圖2 所示. 情況2 為非流行文件的上傳, 此時需要用戶根據收到的隨機密鑰自行計算外層加密密鑰并存儲, 不需重復上傳文件密文, 該情況下的測試結果如圖3 所示. 情況3 為流行文件上傳, 此時用戶只需對文件進行收斂加密, 并保存收斂加密密鑰, 該情況下的測試結果如圖4 所示.

對三種情況的總時間開銷統(tǒng)計結果如圖5 所示. 其中情況1 (初始文件上傳) 下的總時間開銷較大, 情況2 (非流行文件的上傳) 和情況3 (流性文件的上傳) 下不需要上傳數據, 只需要少量的計算時間. 整體來看, 本文方案在時間開銷方面具有明顯的性能優(yōu)勢.

圖2 初始文件上傳Figure 2 Initial file uploading

圖3 非流行文件上傳Figure 3 Unpopular file uploading

6.3 去重效率

本文中去重效率的定義與其他主流方案[20]相同, 定義為用戶需外包給CSP 存儲的數據中重復數據體積所占總數據體積的比值.

為了模擬真實的應用場景, 在系統(tǒng)初始化階段, 隨機產生8000 個不同的文件, 文件大小隨機, 上限為500 MB. 隨機選取3000 個不同的文件存儲到云服務器中, 為每個文件設定隨機的合法用戶數量. 設定流行度閾值為5, 并使得非流行數據占數據總量的比例不低于1/3. 測試方案的去重效率實驗中, 隨機選擇指定數量的文件上傳到CSP, 統(tǒng)計方案的去重效率. 將本文方案與PerfectDedup 方案[8]和Stanek 方案[11]進行對比, 數據去重效率實驗結果如圖6 所示. 三個方案都對數據進行流行度劃分, Stanek 方案和PerfectDedup 方案只對流行數據去重, 但后者基于數據塊去重, 去重效率高于前者. 本文方案實現了對非流行數據的去重, 同一數據副本在云服務器端只存儲一份, 數據去重效率高于其他兩個方案.

圖4 流行文件上傳Figure 4 Popular file uploading

圖5 方案總時間開銷Figure 5 Total time cost

圖6 去重效率對比Figure 6 Data deduplication ratio comparison

6.4 方案特點對比

將本文提出的方案與ClouDedup[5]、PerfectDedup[8]、Stanek[11]在方案特點方面進行對比, 結果如表4 所示. 本文方案針對加密數據進行去重, 無需可信第三方, 對用戶數據進行流行度劃分, 實現了對非流行數據的去重, 可防止非授權用戶下載.

表4 方案特點對比Table 4 Feature comparison

7 結論

本文提出了一種基于雙層加密的云存儲數據去重方案, 可實現云存儲中加密數據的高效去重. 擺脫了第三方服務器的束縛, 去重方案更具有實用性. 通過劃分數據流行度, 對隱私程度較高的非流行數據采用雙層加密, 對隱私程度不高的流行數據采用收斂加密. 實現了非流行數據的去重, 進一步提高了去重效率.添加了額外的安全機制, 可有效的防止非授權用戶下載數據, 保證云服務器上用戶數據的安全性. 分析并討論了方案的安全性, 實驗結果表明本文方案具有較高的執(zhí)行效率.