CDED:支持加密數據去重的云數據審計方案

金 瑜,龔 鑫,何 亨,李 鵬

1(武漢科技大學 計算機科技與技術學院，武漢 430065)2(湖北省智能信息處理與實時工業系統重點實驗室，武漢 430065)

1 引 言

云計算是近年來的研究熱點，其中作為云計算中主要服務之一的云存儲[1]，也廣受工業界和學術界關注.云存儲是數據外包存儲服務，即數據擁有者將本地計算機的數據存儲到云服務器上，從而實現數據的托管，用戶可隨時隨地訪問外包數據.現在提供云存儲的平臺很多，例如Amazon的S3[2]，Microsoft的Azure[3]，但是云數據泄漏和丟失情況時有發生，為了防止這種情況，研究者提出了云存儲的數據審計，即對云數據進行完整性驗證[4].

隨著經濟發展，各行各業產生了海量數據，由于云存儲具有廉價的優點，很多用戶都愿意將自己的數據保存到云服務器中.然而，在這些海量數據中有很大一部分是冗余的，即多個云用戶可能存儲了同一份數據在云服務器中，從而造成了存儲空間的浪費，這對于云服務提供商來說是個不小的負擔，因此重復數據刪除的概念也隨之被提出來[5].一般情況下，為了避免暴露隱私，數據都是以密文的形式存儲在云服務器上，所以，我們應該考慮加密數據的去重.

綜上所述，為了保證云數據存儲既安全又高效，我們需要一種新的支持加密數據去重的審計方案，因為一般審計方案將不再適用.原因是：一般審計方案是針對單個用戶的數據和標簽進行審計，對重復數據都要加密和生成標簽；而去重后，云服務器將對多個用戶擁有的相同數據只保存一份加密數據和一份標簽.

然而，目前同時考慮加密數據去重和數據完整性驗證的方案存在缺點，如①按塊去重時用戶需要生成大量密鑰保存在本地，并且進行重復數據檢查之前要加密數據；②需要用戶一直在線參與審計過程，并且用戶和云服務器計算量大.針對這些問題本文提出了CDED， 一種新的同時支持加密數據去重和數據完整性驗證方案：

①加密數據去重時，采用了代理重加密的方法來保證數據安全，這樣用戶端不需要保存大量加密密鑰，且省去了上傳重復數據之前加密數據的計算量；

②在數據完整性驗證中，采用了新的公開審計和代理重簽名方法，保證用戶不用一直在線參與審計過程，也減少了用戶端和云服務器的計算量.

2 相關工作

2.1 完整性驗證

2007年，Anteniese等人[4]首次定義了PDP協議并且提出了兩個PDP方案(S-PDP，E-PDP)，他們使用隨機抽樣來做完整性驗證，并且利用RSA簽名的同態特性，使被挑戰文件塊的標簽聚集在一起，從而使通信開銷為O(1)，但是他們的方案只支持靜態數據完整性驗證.Juels ，Burton和Kalisli提出了基于崗哨的POR驗證協議[6]，該協議除了能夠檢測到數據是否完整保存在云服務器中，還能夠恢復損壞的數據，但是該方案只能做有限次數的驗證.

2008年，Anteniese等人[7]在PDP模型基礎上提出了可擴展的PDP方案，該方案可以支持動態數據操作，但它只支持部分動態操作，即不能支持完全的插入操作.第二年，Erway等人[8]提出了DPDP(dynamic provable data possession)，使用基于跳表的動態數據結構來支持全動態數據操作.同年，Wang等人[9]也提出了全動態數據操作機制.與DPDP不同的是，文獻[9]采用的是基于Merkle-Tree[10]的數據結構，該方案支持公開審計和利用BLS簽名[11]機制來保證數據塊的完整性.但是，文獻[8,9]均沒有考慮批量審計，針對此問題，2012年Yang等人[12]提出了一種支持了批量審計和動態數據更新操作的方案.

2.2 加密云數據去重和審計

對于加密數據去重，Halevi等人[13]首次提出了POW協議的概念，他們使用了Merkle樹驗證用戶持有數據的真實性，但該方案存在數據泄漏的風險，即未授權用戶能夠訪問用戶的敏感信息.2012年Zheng等人[14]提出了POSD(Proof of Data Storage with Deduplication)這個新穎的概念，他們的方案支持數據去重和數據完整性驗證，但POSD被證明是不安全的[15].2013年Yuan等人[16]也提出支持安全數據去重和云存儲數據完整性驗證方案，他們的方案采用了基于多項式認證標簽和同態線性認證技術，但沒有考慮數據塊更新.2015年Li等人[17]提出了安全的加密數據去重和數據審計方案，采用的是收斂加密[18]技術，即加密方式與存儲數據相關.在該機制中，用戶需要先將密文上傳到一個完全可信的審計服務器，當云服務器上存在相同的文件時，審計服務器只上傳部分信息到云服務器.2017年Liu等人[19]提出了自己的支持加密數據去重和數據完整性審計方案，以下簡稱OTC，該方案也采用了收斂加密技術.由于收斂加密技術存在容易受到離線字典攻擊的危險，因此存在安全問題.假設數據Mi屬于字典S={M1,M2,…,Mn}中一個，它的密文是Ci，而攻擊者能夠從S的字典中通過n次加密得到密文從而和密文Ci進行比較.

除了收斂加密技術的缺點以外，OTC還有如下缺點：

①當按照塊去重時，OTC會根據數據塊來生成加密密鑰，當數據塊越來越多時，用戶端需要保存的密鑰也越來越多，假如用戶端是移動設備，存儲大量密鑰是個不小的負擔，并且OTC不管數據是否重復都會先將數據加密成密文來進行去重；

②在進行數據完整性驗證中，OTC在每次挑戰響應審計中都需要用戶參與并且進行計算返回結果，這對于用戶也是不夠友好的，因為用戶不可能一直保持在線的狀態.并且由于按塊去重的情況下導致用戶需要為一個文件需要生成n個重簽名密鑰 和云服務器端證據生成過程中冪運算過多，導致用戶和云服務器計算量大.

因此基于OTC的不足，我們提出了自己的安全數據去重和數據完整性審計方案CDED.我們的方案在數據去重方面借鑒了Yan[20]的代理重加密方式，在用戶上傳重復數據之前不用加密數據和生成加密密鑰保存；而數據完整性驗證方面采用了一種新的公開審計和代理重簽名方法，上傳數據的第一個用戶生成標簽發送給云服務器保存，當TPA替其他擁有重復數據的用戶ui進行審計時，云服務器將數據標簽重新簽名為用戶ui簽名的標簽，云服務器生成證據響應，發送給TPA進行驗證數據是否完整保存在云服務器中.我們的方案與OTC方案相比，減少了用戶端重簽名密鑰的計算量和驗證數據完整性中云服務器生成證據的耗時，并且我們的方案在驗證時不需要用戶一直在線參與審計過程，審計過程中總的通信量也相對較少.

3 CDED詳述

3.1 系統模型定義

CDED系統模型如圖1所示，系統中包含四個實體：用戶(Owners)、云服務器(CSP)、第三方審計者(TPA)和授權方(AP).Owners可以是個人或者企業，存儲數據在CSP上；CSP為Owners提供存儲和計算資源；TPA代替Owners驗證存儲在CSP的數據是否完整；AP對Owners進行數據所有權驗證和幫助生成完整的重簽名密鑰.方案的大致過程如下：

①Owners初始化數據，為數據生成標識，上傳標識到CSP；

②CSP驗證用戶上傳數據標識是否存在，如果不存在，用戶則生成隨機對稱密鑰DEK后，使用其生成數據密文，并且使用AP廣播的公鑰pkt加密DEK和生成簽名一起上傳到CSP，Owners生成部分重簽名密鑰發送給AP；

圖1 系統模型圖Fig.1 System model

③CSP驗證用戶上傳數據標識如果存在，CSP則發送指令給授權方，AP開始對用戶進行數據所有權驗證(POW)；

④如果Owners通過驗證，證明真實擁有數據，則生成部分重簽名密鑰rek給AP保存；否則，Owners上傳數據到CSP失敗；

⑤Owners發送相關元數據信息給TPA后，TPA向CSP發起審計挑戰；

⑥CSP收到TPA的挑戰后，CSP向AP方發送指令獲取重簽名密鑰，AP根據指令生成隨機數x并且生成完整的重簽名密鑰rek返回給CSP，同時AP將隨機數x發送給TPA方；

⑦CSP根據收到的重簽名密鑰為相應的挑戰生成證據proof，然后將證據發送給TPA；

⑧TPA收到證據后，再根據驗證公式驗證數據是否完整的保存在CSP，并將審計結果返回給Owners.

3.2 安全性假設

如上所述，在CDED的系統模型中有Owners、CSP、TPA和AP四個實體.本文作了如下安全假定：

①假設AP方全可信的，會誠實執行數據去重中的用戶所有權驗證和代理重簽名操作；

②假設TPA是半可信的，會誠實執行審計操作但可能會好奇的窺探Owners隱私；

③假設CSP是半可信的，會誠實存儲Owners數據，但是當由于意外導致Owners數據丟失時，他們會為了自己的利益偽造證據欺騙TPA.

3.3 預備知識

3.3.1 代理重加密

代理重加密過程大致是數據的第一個上傳用戶生成加密密鑰DEK，使用AP廣播公鑰將DEK加密后發送到給云服務器保存，當存在其他用戶ui上傳重復數據后需要將取回的密文解密為明文，云服務器需要使用AP生成重加密密鑰將加密后的DEK轉換為由使用ui的公鑰加密的DEK，用戶ui可以使用自己的私鑰解密得到DEK.

3.3.2 代理重簽名

代理重簽名，由Blazez等人[21]在方案中首次提出，該方案使得一個半信任的代理方能夠把兩個用戶的簽名互相轉換，也就是代理方能夠將Alice對數據塊的簽名轉化為Bob對該數據塊的簽名，并且在代理重簽名的過程中，代理方不能獲取到兩個用戶的私鑰，即代理方不能代表Alice或者Bob任何一方簽名.

3.3.3 雙線性對

假設G1,G2,GT都是素數階為p的乘法循環群，g1,g2分別是G1,G2的生成元，映射e:G1×G2→GT稱為雙線性配對，它滿足如下三條性質：

①雙線性：?m∈G1,n∈G2和a,b∈Zp?e(ma,nb)=(m,n)ab；

②非退化性：e(g1,g2)≠1；

③可計算性：e能夠被有效的計算.

3.4 CDED關鍵過程

我們的方案由三部分組成，初始化階段，安全去重階段和公開審計階段.我們使G1,G2,GT都是以p為素數階的乘法循環群，雙線性對e:G1×G2→GT，g1,g2分別是G1,G2的生成元.其中H:{0,1}*→G1是哈希函數，能夠將信息摘要Minfo映射到G1循環群中；h:{0,1}*→Zp是哈希函數，能夠根據數據得到對應于Zp內的值.

3.4.1 初始化階段

云用戶執行密鑰生成算法KeyGen，數據加密算法Encryp，標簽生成算法TagGen ，重簽名密鑰生成算法RekGen .

Encryp(F,DEK)→C.數據加密算法輸入生成的對稱密鑰DEK和明文數據后將會輸出加密密文C.

TagGen(F)→T.標簽生成算法輸入文件F，由于我們的方案采用的按塊去重的粒度，文件F需要被分割成多個小文件，按塊去重既可以是按照固定大小的去重也可以是可變大小的去重，本方案中為了方便計算采用了固定大小的塊去重即F={F(1),F(2),…F(n)}，對應的密文表示法為C={C(1),C(2),…C(n)}.用戶根據數據計算密鑰:

kF(k)=h(F(k))∈Zp(k∈[1,n])

(1)

(2)

RekGen(skt,{kF(k)}1

(3)

用戶將得到的部分重簽名密鑰發送給AP.

3.4.2 安全去重階段

由于我們的安全去重階段借鑒了文獻[20]中的方法，這里只簡單概述.安全的數據去重發生在用戶A要存儲相同的數據在CSP的時候.當CSP收到A的請求后將會驗證接受到的數據標識，如果驗證通過，CSP將會委托AP去對上傳數據的用戶A進行數據所有權檢查，AP收到所有權檢查后將會對用戶發起挑戰，用戶將根據收到的挑戰生成證據發送給AP，最后AP驗證證據判斷用戶是否真實擁有數據，通過驗證后用戶A將生成數據的部分重簽名密鑰發送給AP保存.

3.4.3 公開審計階段

公開審計階段需要執行挑戰算法Challenge，證據生成算法ProofGen，證據驗證算法Verify.

ProofGen(C,T,chal)→P.證據生成算法由云服務器端執行，輸入相關被挑戰的密文數據，相應的標簽數據和來自TPA的挑戰信息，輸出證據其中證據包含標簽證據TP和數據證據DP.標簽證據生成公式為：

(4)

(5)

DP的計算公式為：

(6)

云服務器將生成的證據P=(TP,DP)返回給審計方TPA.

Verify(Minfo,x,pkt,chal)→{0,1}.審計方計算驗證證據算法，輸入數據摘要信息，AP發送過來的隨機數x,用戶的公鑰pkt，云服務器發送過來的證據P和挑戰信息chal.審計方首先計算挑戰哈希:

(7)

(8)

當等式(8)成立時輸出1反之輸出0.下面是等(8)的推導過程：

=e(Hchal,pkt)·DP

4 安全性分析

本文借鑒了文獻[20]中的數據去重方案.由于關于去重的安全性分析已經在[20]中已經進行了證明，因此這里不再贅述，接下來重點關注審計過程的安全性.

定理1.在公開審計過程中，云服務器不能通過偽造證據來通過TPA的審計

證明：假設存在攻擊者偽造了不正確的證據P′=(DP′,TP′)且偽造的證據通過的TPA的審計驗證.根據等式(8)我們能得到如下等式：

(9)

根據雙線性對的性質，將公式(8)和公式(9)相除得到:

(10)

uj=aβj·bλj

(11)

其中βj,λj∈Zp是隨機值，從而我們能夠得到：

(12)

經過推導上述公式我們可以知道，

(13)

當我們已知a,b,askt∈G1時能夠求解出bskt，這與CDH難題矛盾，CDH難題的描述為：在已知m∈Zp和gm,g,h∈G1的情況下求解hm是困難的.

定理2.TPA不能通過已有的數據獲得用戶的隱私數據.

證明：本文采取了方案[12]的方法，利用雙線性對的性質保護用戶的隱私，使得TPA不能通過數據塊的線性組合推導出用戶的數據隱私并且數據被加密了即使TPA獲得了密文也無法解密得到明文.

5 性能分析

5.1 理論分析

對于加密數據去重，OTC方案采用了基于數據相關的收斂加密方式，用戶在上傳數據之前都要生成加密密鑰保存在本地，還要對數據進行加密然后再上傳數據進行數據重復檢查.另外，由于OTC中加密密鑰是基于數據信息來生成的，所以根據去重粒度的不同，同樣大小的文件生成的密鑰個數也不同；而我們的方案CDED中借鑒了Yan[20]的代理重加密機制，在上傳重復數據之前不需要加密數據和保存加密密鑰在用戶端.我們從理論的角度分析了 CDED和OTC在用戶上傳n份不同的重復數據時，所需要的加密數據耗時和密鑰的存儲開銷.表1給出了比較結果.其中t1和t2分別表示一份文件的數據加密時間和一份文件塊數據加密時間，k表示組成一份文件的文件塊個數，加密密鑰采用的是128位的數據.

5.2 實驗分析

我們實現了OTC和CDED的原型系統.實驗相關運行環境如下：

①軟件環境：

操作系統：16.04Ubuntu,編程語言：C,使用的密碼學庫：0.5.12版本 (Pairing-Based Cryptographa)PBC庫和1.1.0g版本OpenSSL庫.

②硬件環境：

RAM:4.0GB ，CPU:Intel(R) Core i7-6700 @3.40GHz.

在實驗中，我們選擇Type-A橢圓曲線初始化配對，設定二級文件塊大小為20Byte.實現了文件的按塊去重.

表1 去重階段數據加密耗時和密鑰存儲花費對比

Table 1 Comparison of data encryption cost and key storage cost in the stage of deduplication

按文件去重按塊去重加密耗時存儲花費加密耗時存儲花費OTCn·t1n·128bitn·k·t2n·k·128bitCDED無無無無

實驗1.比較了用戶端重簽名密鑰生成的時間開銷.如圖2所示，隨著文件數由10，20，30，40，50逐漸變大時，OTC相比于我們的方案需要花費更多的時間來生成重簽名密鑰，這是因為我們的方案中在用戶端計算重簽名密鑰的公式只是生成的部分重簽名密鑰，減少了乘運算量，但是我們也考慮了Liu[19]方案中惡意用戶與云服務器合謀的情況，由AP為每次被挑戰數據塊生成新的隨機數來構成完整的重簽名密鑰，這樣保護了用戶用于生成標簽的私鑰不會因為云服務器和惡意用戶的合謀而泄漏.

圖2 重簽名密鑰生成時間花費Fig.2 Re-signature key generation time cost

實驗2.在文件大小為20MB時，組成一個一級文件塊的二級塊個數為s=20，按塊去重塊大小為64KB的條件下，我們考察Liu[19]的方案和我們的方案在隨著挑戰塊數變化時，云服務器端生成證據計算量的比較.如圖3所示，在挑戰塊數由100，200，300，400，500變化時我們的方案在證據生成的耗時相比于Liu[19]的方案更小，按照Liu[19]的方案，根據其生成證據的公式可以分析出挑戰塊個數變化對證據生成的計算影響更大和公式中冪、乘運算更多.

圖3 證據生成耗時Fig.3 Proof generation time

實驗3.在文件大小為20MB，組成一個一級文件塊的二級塊個數為s=20，按塊去重塊大小為64KB的條件下，我們考察了Liu[19]的方案和我們的方案中隨著挑戰塊的變化時，TPA端證據驗證計算量比較.如圖4所示，我們能夠知道隨著挑戰塊數由100,200,300,400,500的變化，我們的方案和Liu[19]的方案兩者在審計者方的驗證證據耗時相差不大基本保持在同一平面，但是Liu[19]的方案在每次的挑戰審計中在計算驗證公式時都需要用戶的參與，這就表示用戶需要一直在線，這個設計肯定對用戶來說是不友好的，因為用戶將審計任務委托給了TPA肯定是不希望自己時刻保證在線參與審計這不僅耗費了用戶的計算資源也占用了用戶的時間，且TPA的挑戰審計是定期的進行的.

圖4 證據驗證耗時Fig.4 Proof verification cost

圖5 通信量Fig.5 Communication cost

6 總結與未來工作

針對現有的支持加密數據去重審計方案的缺點，本文提出了一種新的支持數據去重的完整性驗證方案CDED.本文主要討論了按塊去重的細粒度去重方案下的完整性驗證的情況.在加密數據去重方面借鑒了Yan等人[20]的方案，相比于Liu[19]的去重方案中采用收斂加密，Yan[20]的代理重加密的方式更加安全.通過理論分析，與現有方案OTC相比，在CDED中，用戶端獲得了較小的存儲和計算開銷；在審計方面我們在借鑒Yang[12]的等人方案中審計公式的基礎上，引入了代理重簽名，這不僅解決了標簽數據的去重而且安全分析中證明了我們的方案的正確性和不可偽造性.通過實驗得出，與OTC相比，在CDED中，用戶不需要一直在線，并且用戶端和服務器端計算量都減少了.

本文中考慮的是單一云服務器下支持去重的審計方案可能有單點失效問題，應該引入多云協作的情況下做數據去重的審計，這將是我們下一步工作的研究方向.