基于遞歸秘密共享的可靠云存儲方案

王家玲

一、引言

云存儲是云計算技術[1]的一個延伸，可以認為它是一個配備了海量存儲空間的云計算系統(tǒng)。但是，由于云存儲系統(tǒng)規(guī)模巨大，集中了諸多用戶的應用和隱私數(shù)據(jù)，同時云存儲具有前所未有的開放性和復雜性，其安全性面臨著比傳統(tǒng)信息存儲更為嚴峻的挑戰(zhàn)[2]。因此，設計安全可信的云存儲方案具有重要的實踐意義。

本方案利用遞歸的門限秘密共享方案，實現(xiàn)數(shù)據(jù)資源的拆分和冗余存儲。方案不僅能有效保證云存儲數(shù)據(jù)的機密性，還能實現(xiàn)數(shù)據(jù)的冗余存儲，且方案的存儲開銷較傳統(tǒng)的完全冗余存儲以及基于Shamir(k,n)秘密共享存儲存儲降低了很多，大大節(jié)約了存儲空間。

二、相關工作

云存儲的安全問題主要集中在數(shù)據(jù)的機密性和完整性。就機密性而言，加密技術是保護數(shù)據(jù)機密性的一種較為有效的手段。在數(shù)據(jù)被存儲到云端之前，我們可以對數(shù)據(jù)進行加密，這樣云服務商和攻擊者都無法獲得數(shù)據(jù)的明文內容。用戶可以通過密文檢索技術來訪問數(shù)據(jù)。但是這種方法多用于靜態(tài)數(shù)據(jù)云存儲的場景，不適合數(shù)字資源不斷動態(tài)更新的場景。

就完整性而言，對于用戶來說，由于不存儲數(shù)據(jù)的備份，因此，能夠確保數(shù)據(jù)在云端服務器上的完整性至關重要。數(shù)據(jù)冗余存儲是目前來說比較有效的手段。目前，主要的冗余方法有兩種：完全副本冗余和糾錯碼冗余。完全副本冗余是指保存多份數(shù)據(jù)的完整副本，只要還有一個副本可以訪問，數(shù)據(jù)就不會丟失。侯孟書等[3]為被頻繁訪問的數(shù)據(jù)增加副本數(shù)量，并選擇高性能存儲節(jié)點存放，從而提高數(shù)據(jù)的可用性。完全副本冗余雖然簡單、直觀，但是有存儲空間消耗大，處理大文件時性能差等缺點。

糾錯碼是指將存儲的數(shù)據(jù)先切分為m個部分，然后編碼變換成n(n>m)個部分，恢復數(shù)據(jù)時只要得到其中任意t(t≥m)個部分即可。目前，大多數(shù)云存儲模型中使用糾刪碼算法將數(shù)據(jù)分割來提高數(shù)據(jù)的冗余性。Weatherspoon等[4]采用隨機過程的方法，量化分析了完全副本冗余和糾錯碼對系統(tǒng)可靠性的影響，發(fā)現(xiàn)使用糾錯碼冗余，可以在與副本冗余得到相同可靠性的條件下，極大地節(jié)約系統(tǒng)中的存儲空間和維護帶寬。不過該算法得到的數(shù)據(jù)都是以明文形式顯示的，因此數(shù)據(jù)的機密性無法保證。

為保證數(shù)據(jù)的機密性和冗余性，一些云存儲模型使用門限秘密共享算法實現(xiàn)云存儲。(k,n)門限秘密共享方案是把一個數(shù)據(jù)分成n個秘密份額分給n個參與者掌管，這些參與者中k個或k個以上的參與者所構成的子集可以合作重構這個秘密。研究者們利用多種數(shù)學模型構建了多種門限秘密共享方案[5]～[9]，這些方案不僅能保證數(shù)據(jù)的冗余存儲，還能提供機密性的保證。但是該算法會帶來存儲空間的劇增，造成用戶成本的增加。

為此，本文提出一個既能保證數(shù)據(jù)冗余存儲又能提供數(shù)據(jù)機密性的可靠云存儲方案，該方案采用基于遞歸的秘密共享算法將數(shù)據(jù)進行分割，分割后每個數(shù)據(jù)塊的大小比源數(shù)據(jù)小很多，不會帶來存儲空間的劇增。方案的安全性由需存儲的數(shù)據(jù)塊的大小決定，數(shù)據(jù)越大，安全性越高，故適合海量數(shù)據(jù)的云存儲情況。

三、可靠冗余存儲方案

方案的基本思想是基于遞歸的(k,n)門限秘密共享方案[10]，將數(shù)字資源S分割轉換成n個數(shù)據(jù)塊，分別保存在云存儲系統(tǒng)的多個服務器上，至少k個完整數(shù)據(jù)分塊組合可以恢復原來的數(shù)據(jù)，任意k-1個或更少完整數(shù)據(jù)塊不能重構S，且不能獲得有關S的任何信息。數(shù)據(jù)塊完整性的判斷，通過數(shù)據(jù)完整性檢測算法實現(xiàn)。這不但實現(xiàn)了數(shù)據(jù)的冗余存儲，只要服務器上至少有k個數(shù)據(jù)塊沒被損壞，就能恢復出原來的數(shù)據(jù)；又保證了數(shù)據(jù)的機密性，攻擊者只有攻破至少k個數(shù)據(jù)塊才能恢復數(shù)據(jù)S，否則不能獲得有關S的任何信息。

1.方案框架

數(shù)字資源云存儲過程如下：若數(shù)字資源S能平均分塊，則將S平均分割成k個大小相同的數(shù)據(jù)塊S1,S2,…,Sk；若S長度不能被平均分塊，則先將S分成長度為的k-1個數(shù)據(jù)塊，最后一個長度小于的數(shù)據(jù)塊，可通過數(shù)據(jù)前方補零的方法使其與前面k-1個數(shù)據(jù)塊長度相等，故通過數(shù)據(jù)前方補零的方法可使S平均分割。因此，為了不再贅述，可假設文后的數(shù)字資源長度均能被平均分塊。數(shù)字資源持有者隨機選擇一個數(shù)據(jù)a，與S1,S2,…,Sk一起作為RSS分發(fā)算法（遞歸秘密共享算法的分發(fā)階段）的輸入，通過該算法轉換輸出n個數(shù)據(jù)大小相同的數(shù)據(jù)塊D1,D2,…,Dn，然后再將各數(shù)據(jù)塊劃分成m個數(shù)據(jù)塊并生成其簽名，將數(shù)據(jù)分別發(fā)送存儲到云端的多個服務器上，用戶隨時通過數(shù)據(jù)完整性檢測算法檢測云服務器上數(shù)據(jù)的完整性，若想恢復數(shù)據(jù)S，只需在云存儲服務器上下載任意k個無損壞的數(shù)據(jù)塊，利用RSS重構算法（遞歸秘密共享算法數(shù)據(jù)重構階段），即可獲得S1,S2,…,Sk，從而得到原始數(shù)據(jù)S。方案框架如圖1所示。

圖1 方案框架圖

2.具體方案描述

本方案假設云存儲商是半可信的，即云服務商不會主動泄露和破壞用戶存儲的數(shù)據(jù)，但是不能完全保證因為機器故障或黑客攻擊導致數(shù)據(jù)的泄露與破壞。本方案是遞歸的采用Shamir的(k,n)門限秘密共享算法，對各數(shù)據(jù)塊進行自加密以保證數(shù)據(jù)的機密性和冗余存儲。

令p是大素數(shù)，滿足p>max(Smax,n)，其中Smax=max(Si)（1≤i≤（k-1））。數(shù)字資源記為S，被平均劃分成大小相等的k個數(shù)據(jù)塊記為|S1|=|S2|=…=|Sk|，k為門限值。遞歸的Shamir的 (k,n)門限秘密分發(fā)算法記為RSSDeeling(S,a)，其中S為原始數(shù)據(jù)，a為預先生成的一個隨機數(shù)據(jù)，a ZP，n為最終轉換的數(shù)據(jù)塊的個數(shù)。D1,D2,…,Dn為轉換后的數(shù)據(jù)塊，即函數(shù)RSSDeeling(S,a)的輸出。再將每個數(shù)據(jù)塊分成m個小數(shù)據(jù)塊，第i個數(shù)據(jù)塊記為Dij（1≤j≤m），它的數(shù)字簽名記為RSSProof(i,Vij)算法為數(shù)據(jù)塊Dj的完整性檢測算法，其中Vij（VijZP）是為數(shù)據(jù)塊Dij選取的隨機數(shù)。RSSRecover(N1,N2,…,Nk)為數(shù)據(jù)重構算法，其中N1,N2,…,Nk是從云存儲設備上下載的任意k個完整數(shù)據(jù)塊。

整個方案分為三個過程：分發(fā)存儲過程、完整性檢測過程和數(shù)據(jù)重構過程。

(1)分發(fā)存儲過程

a.將數(shù)字資源S切割成大小相等的k個數(shù)據(jù)塊，記為|S1|=|S2|=…=|Sk|，S={S1,S2,…,Sk}；

b.選擇數(shù)據(jù)a ZP，構造一次多項式f1(x)=ax+S1；

d.當 2≤i≤（k-1）時，構建如下多項式：

I.當 i＜（k-1）時，計算 i+1 個點：

II.當 i＝k-1 時，計算 n 個點：

e.將各數(shù)據(jù)塊再平均劃分成m個小數(shù)據(jù)塊，利用數(shù)字簽名算法，生成各數(shù)據(jù)塊Dij（1≤i≤n,1≤j≤m）的簽名，其中，H是hash函數(shù)，可將任意長度的二進制字符串映射為群G上的元素；μ是群G的生成元；α是用戶私鑰，V=gα是公鑰。

(2)完整性檢測過程

用戶將數(shù)據(jù)發(fā)送至云存儲器后，可通過可恢復性完整性驗證算法RSSProof(j,Vij)[11][12]來檢測云存儲服務器上的數(shù)據(jù)的完整性，這里以其中的一個數(shù)據(jù)塊Di為例，其他數(shù)據(jù)塊方法類似，不再贅述。

a.為小數(shù)據(jù)塊Dij生成一個挑戰(zhàn)對(j,Vij)，構成挑戰(zhàn)集合

b.針對挑戰(zhàn)對，云存儲服務方首先將其對應數(shù)據(jù)塊平均劃分成m個小數(shù)據(jù)塊Dij，給出應答對 ，其中。

c.用戶通過判斷方程 是否成立來判斷第i個數(shù)據(jù)塊Di是否完整，該方程中的e是密碼學中的雙線性映射方程。

下面證明一下完整性檢測判斷方程能否判斷數(shù)據(jù)的完整性。

由雙線性映射的重要性質可知，

等式左邊：

因此，若數(shù)據(jù)完整沒發(fā)生任何變化，等式成立；反之，若數(shù)據(jù)發(fā)生變化，則等式不成立。

(3)數(shù)據(jù)重構過程

用戶根據(jù)完整性檢測結果來選擇是否要進行數(shù)據(jù)重構。如果服務器上的n個數(shù)據(jù)塊中，有大量數(shù)據(jù)塊被損壞，但是被損壞的數(shù)據(jù)塊個數(shù)不多于n-k個，那么完整的數(shù)據(jù)塊不少于k個，這時，我們可以選擇使用數(shù)據(jù)重構算法來重構數(shù)據(jù)S。如果損壞的數(shù)據(jù)塊個數(shù)超過了n-k個，則無法重構數(shù)據(jù)。數(shù)據(jù)重構過程如下：

a.從云存儲服務器上下載k個完整的數(shù)據(jù)塊（i,Di）1≤i≤k；

b.使用拉格朗日插值公式構造多項式：

計算Sk-1=fk-1（0）.

c.當 2≤i≤（k－1）時，

計算Si=fi（0）.

四、方案分析

1.機密性

由于數(shù)據(jù)在存儲到云端服務器之前，我們將數(shù)據(jù)進行了分割和轉換，轉換后的數(shù)據(jù)與原數(shù)據(jù)截然不同。用戶數(shù)據(jù)文件變換后內容與原文件相比發(fā)生了變化，對于外部攻擊者來說，獲得某個分塊并不能知曉有關原文件的任何內容，黑客如想得到原數(shù)據(jù)的有關信息，必須要同時攻破多個服務器，至少獲得k個數(shù)據(jù)塊信息，才能通過恢復算法獲得原數(shù)據(jù)S。若攻擊者獲得少于k個數(shù)據(jù)塊的信息，將得不到有關S的任何信息。不是一般性，假設攻擊者獲得k-1個數(shù)據(jù)塊信息，相當于已知一個k次多項式的k-1個點，無法唯一確定該多項式。相當于在Zp內隨機猜測數(shù)據(jù)S，其概論為1/p。而攻擊者同時攻破多個服務器，且獲得k個相關數(shù)據(jù)塊的概率很小，顯然加大了攻擊者攻擊的難度。這就有效的保證了數(shù)據(jù)在存儲到云存儲服務器上的機密性。數(shù)據(jù)塊越大，素數(shù)p要求越大，這樣猜測S的概率越小，數(shù)據(jù)安全性越高。

2.冗余性

由于該方案是一個(k,n)門限秘密共享方案，即我們將原始數(shù)據(jù)S經(jīng)過轉換后，生成了n個分塊，而其中任意k個分塊組合，通過數(shù)據(jù)恢復算法可恢復出原數(shù)據(jù)S。如果服務器上的n個數(shù)據(jù)塊中，有大量數(shù)據(jù)塊被損壞，但是被損壞的數(shù)據(jù)塊個數(shù)不多于n-k個，即完整的數(shù)據(jù)塊不少于k個，這時，我們可以使用數(shù)據(jù)重構算法來重構數(shù)據(jù)S。即該方案允許損壞的數(shù)據(jù)塊的個數(shù)最多為n-k個。如果損壞的數(shù)據(jù)塊個數(shù)超過了n-k個，則無法重構數(shù)據(jù)。

3.存儲開銷

服務器端的存儲開銷主要由冗余機制引入，由秘密共享方案的冗余度決定。對一個數(shù)據(jù)S，令|S|表示秘密的大小，若使用經(jīng)典的Shamir(k,n)秘密共享方案，產(chǎn)生的每個數(shù)據(jù)塊大小為均|S|，若產(chǎn)生n個數(shù)據(jù)分塊，云存儲服務器上需存儲的數(shù)據(jù)大小將為n×|S|，空間效率較低。原數(shù)據(jù)S越大，空間效率將越低，不適合海量信息的存儲。在本方案中，采用的是基于遞歸的Shamir(k,n)秘密共享方案，首先將秘密S分為大小為的k個數(shù)據(jù)分塊，若轉換成n個數(shù)據(jù)分塊，則云存儲服務器上需存儲的數(shù)據(jù)大小將為大大節(jié)約了存儲空間，有很高的空間效率。故本方案中的冗余存儲機制盡可能地降低了云存儲服務器的存儲開銷。

五、結束語

隨著云存儲的出現(xiàn)，海量的數(shù)字資源存儲到云端服務器成為必然趨勢。但是云存儲的安全問題面臨著越來越嚴峻的挑戰(zhàn)。為保證數(shù)據(jù)的保密性和冗余性，本文提出了一個高效可靠的云存儲方案，方案由三部分組成，即：數(shù)據(jù)分塊分發(fā)過程、數(shù)據(jù)完整性檢測過程和數(shù)據(jù)重構過程。文章通過分析方案的機密性、冗余性和存儲開銷得出所提方案的優(yōu)越性。

[1]HayesB.CloudComputing[J].Communications of the ACM,2008,51(7):9－11.

[2]馮登國,張敏,張妍，等.云計算安全研究[J].軟件學報，2011，22(1):71-83.

[3]侯孟書,王曉斌,盧顯良，等.一種新的動態(tài)副本管理機制[J].計算機科學,2006,33(9):50-51.

[4]Weatherspoon H,Kubiatowicz J.Erasure coding vs replication:quantitative comparison[M].In:Proc of the 1st Int'l Workshop Peer-to-Peer Systems,2002.

[5]Shamir A.How to Share a Secret[J].Communications of the ACM，1979，22(11):612-613.

[6]Blakley G.Safeguarding Cryptographic Keys[C].Proceedings of the National Computer Conference,Montvale:NCC,1979:242-268.

[7]Asmuth C.,Bloom J.A Modular Approach to Key Safeguarding[J].IEEE Transactionson Information Theory,1983,29(2):208-2I0.

[8]Karnin E.D.,Green J.W.,Hellman M.E..On Sharing Secret Systems[C].IEEE Transactions on Information Theory,1983,29(1):35-41.

[9]Feldman P.A Practical Scheme for Non-interactive Verifiable Secret Sharing[C].Proceeding of 28th IEEE symposium on Foundations of computer science,Canada:IEEE,1987.427-437.

[10]Parakh A,Kak S.Space efficient secret sharing for implicit data security[J].InformationSciences,2011,181(2):335-341.

[11]D.L.G.Filho,P.S.L.M.Barreto.Demonstrating data possession and uncheatable data transfer[R/OL].Cryptology ePrint Archive,Report 2006/150,2006.

[12]Y.Deswarte,J.-J.Quisquater.Remote Integrity Checking[C].Sixth Working Conference on Integrity and Internal Control in Information Systems.Kluwer Academic Publishers,2004.1－11.