云環境下支持可更新加密的分布式數據編碼存儲方案

嚴新成 陳 越 巴 陽 賈洪勇 朱 彧

1(戰略支援部隊信息工程大學 鄭州 450001) 2(鄭州大學軟件與應用科技學院 鄭州 450001)

隨著大數據與云計算技術的發展，越來越多的數據可以在云端進行存儲、計算以及共享.數據加密有效保證了存儲與通信的機密性.而根據美國國家標準與技術研究院(National Institute of Standards and Technology, NIST)發布的Special Publication[1]SP 800-57，基于密碼學的密文密鑰具有嚴格的生命周期，保留時間越長，密鑰泄露風險越大.

我們知道，在加解密服務中，非對稱加密主要實現的是對稱密鑰的保護和共享，也就是對實際存儲數據的訪問權限的一種控制.就存儲的用戶敏感數據而言，對稱加密提供的是基本的安全性保障.云服務器的存儲數據資源豐富，其分為“冷數據”和“熱數據”，不同類型的數據其價值相差甚大.對于云中長期存儲的數據而言，尤其是重要性較高的敏感密文數據，由于密文的硬破解是困難的[2]，因此密鑰存儲與使用的安全性直接影響了密文存儲的安全性.現代密碼學都假定用戶密鑰對可能的攻擊來說是完全隱藏的，但在實際中通過邊信道攻擊，例如時間攻擊、電源耗損、冷啟動攻擊以及頻譜分析等，都能從保密密鑰或加密系統內部獲得有關密鑰的部分信息[3]，極大損害了存儲密文的安全性.因此，對于長期存儲的加密敏感數據，為防止用戶私鑰泄露，需要周期性地輪換密鑰或根據實際情況撤銷部分用戶訪問權限.

比如NIST[4]建議定期輪換密鑰，開放式Web應用程序安全項目OWASP[5]也是如此，支付卡行業[6]定期要求輪換客戶數據.谷歌[7]和亞馬遜[8]現在為其長期存儲服務中的此類操作提供部分支持，因此被授權密鑰更新的客戶可以這樣做.然而，正如Everspaugh等人[9]所指出的那樣，Google和Amazon所使用的技術存在可疑的和未定義的安全性，且容易受到密鑰搜索攻擊(key-scraping attacks).因此，密鑰更新是實踐中的難題之一.

此外，雖然更新共享文件很常見，但很少關注如何有效地更新分布式存儲系統中的大量加密的文件.事實上，要修改文件中的任何一個比特位，當前的解決方案需要通過簡單且昂貴的方式下載和解密文件[10].數據重加密是實現密文更新的簡單方式，但是極大增加了客戶端的計算開銷以及存儲系統的通信開銷，同時客戶端需要更大的緩存空間來存儲從服務器端返回的額外數據塊.混合加密雖然實現了用戶私鑰(密鑰加密密鑰)的更新，但內部的數據加密密鑰并未更新.對于之前能訪問該數據密鑰的被撤銷權限的用戶而言，數據的存儲仍存在安全風險.我們知道，數據的存儲結構包括2類：集中式存儲和分布式存儲.集中式存儲使得數據在管理上較為直觀方便，但難以滿足數據災備的需求.而將數據重加密或混合加密直接應用到分布式數據存儲時，通信及計算開銷過大：上一個版本的密文塊更新需要經歷從各個數據節點“下載-還原-解密-重加密-重新分塊上傳”的過程，客戶端計算開銷及系統的通信開銷均可能成為制約系統運行效率的關鍵[11].因此，就云存儲的實際應用而言，需要同時考慮數據的機密性、完整性、可用性及單節點的直接更新，這對支持加密的分布式數據存儲提出了更高的要求，即能夠在各數據節點存儲的編碼后的密文數據的基礎上直接進行數據更新，從而避免數據上傳下載帶來的通信開銷以及還原密文和重加密帶來的計算開銷，為進一步構建安全實用的加密云存儲系統提供有效的技術支撐.

1 相關工作

從當前研究來看，密鑰更新面臨的最大挑戰仍然是密文更新的計算開銷問題.本文整理并歸納了近幾年關于可更新加密的研究工作，并結合分布式云存儲及數據安全更新的場景分析可更新加密在實際應用中的問題與挑戰.

云計算技術的大規模應用使得存儲數據的隱私保護問題日益凸顯，加密環境下密鑰泄露的威脅場景也無處不在.Sahai等人[12]在CRYPTO 2012上提出這樣一個擔心：在云存儲系統中，當用戶證書變化時，必須同時考慮私鑰的撤銷以及密文的更新，使得被撤銷權限的用戶無法訪問之前可解密的數據，而合法用戶不受影響；Sahai等人定義了可撤銷存儲，基于密文代理技術，利用公開信息直接對給定策略加密的密文進行“重加密”，使得該密文轉換為原明文信息對應的更具有約束性策略的新的密文，保證新加密的數據無法被已撤銷私鑰的用戶訪問；通過對Lewko等人[13]的方案進行改進，分別構建了支持KPABE(key-policy attribute-based encryption)和CPABE(ciphertext-policy attribute-based encryption)的解決方案，均滿足上述定義的“分段密鑰產生”特性，并在標準模型下證明是安全的.

自更新加密(self-updatable encryption, SUE)由Lee等人[14]在ASIACRYPT 2013提出，是一個新開發的密碼學原語，它實現了作為內置功能的密文更新，從而提高了云管理中密鑰撤銷和時間演進的效率.在SUE中，當且僅當用戶擁有與密文的時間相同或未來某個時間對應的私鑰時，用戶可以解密與特定時間相關聯的密文.此外，可以只使用公共信息將附加到某個時間的密文更新為附加到未來時間的新密文.Datta等人[15]在標準假設下給出了素數階雙線性群中的第1個完全安全的SUE方案，即決策線性假設和決策雙線性Diffie-Hellman假設;但Freeman[16]和Lewko[17]指出，素數階雙線性群的通信和存儲以及計算效率比具有相當安全級別的復合階雙線性群要高得多.因此，文獻[15]提出的SUE方案比現有的完全安全的SUE具有高度的成本效益.Lee[18]在素數階雙線性群中提出了一種SUE方案，該方案公共參數較短，并將其先前的方案擴展到支持密文時間間隔的TI-SUE(time-interval SUE)方案;Aono等人[19]提出了密鑰可輪換和安全可更新同態加密的概念，其中任何密文密鑰都可以輪換和更新，同時仍然保持底層明文的完整和未透露;Lee等人[20]提出了第1個SUE和RS-ABE方案來解決新的威脅，即被撤銷權限的用戶仍然可以訪問由存儲服務器提供的過去的密文.

Rodriguez等人[21]考慮使用計數器(counter, CTR)模式加密來保護數據安全.CTR由Diffie和Hellman[22]提出，并在2001年被NIST通過，作為加密的安全操作碼[23].有關如何生成這些“計數器”的規范可以在NIST發布的標準中找到.但是，他們提出的方案缺乏用戶私鑰的定義和標準的安全證明.

然而，上述可更新數據加密方案并未考慮實際云存儲中的應用.如引言所述，集中式存儲難以滿足有效的數據災備需要.也就是說，構建支持可更新加密的分布式數據存儲方案可以滿足更高的安全性和可靠性要求.分布式存儲架構是用于在授權用戶之間存儲和共享大數據的云計算系統的最重要組件之一.分布式存儲系統通過分散在單個不可靠節點上的冗余提供對數據的可靠訪問，應用場景包括數據中心、點對點存儲系統和無線網絡中的存儲[24].現代分布式存儲系統將冗余編碼技術應用于存儲數據，能夠解決集中式存儲的單點失效問題以及避免多副本存儲的巨大開銷；Hu等人[25]研究了功能最小存儲再生碼FMSR,它可以在沒有幸存節點的編碼要求的情況下實現無編碼修復，同時保留最小的修復帶寬保證并最小化磁盤讀取；Rawat等人[26]研究分布式存儲系統的安全性和本地可修復性，并重點介紹能夠實現最佳局部修復的編碼方案；Li等人[27]提出了一種通用轉換以實現分布式存儲系統中MDS編碼的最佳修復；Su[28]引入了一種稱為柔韌FR編碼的新型FR編碼，它可以解決現有FR編碼不夠靈活，無法充分適應分布式存儲系統變化的缺點；唐英杰等人[29]針對基于糾刪碼的分布式存儲中數據恢復開銷過大問題，提出一種基于網絡計算的高效故障重建方案來減少網絡流量，有效解決了客戶端的網絡瓶頸.

2 預備知識

2.1 密鑰同態偽隨機函數

2.2 FMSR碼

(n,k)FMSR碼將大小為M的原始文件切分成k(n-k)個固定大小的數據塊，再將它們編碼成n(n-k)個編碼塊然后上傳到n個數據節點，每個節點存儲相鄰的n-k個編碼塊.數據讀取時，首先從隨機挑選的k個數據節點中下載k(n-k)個編碼塊進行譯碼操作，然后將還原后的數據塊合并成原始文件.

當某節點意外失效時，為保證數據的安全性和服務的連續性，數據修復過程如下：從正常工作的n-1個數據節點上各取一個數據塊重新進行編碼，用生成的n-k個編碼塊來替代失效節點存儲的數據.(4,2)FMSR碼的修復過程如圖1所示：

Fig. 1 Data recovery of (4,2)FMSR encoding for corrupted nodes圖1 (4,2)FMSR碼的損壞節點數據恢復

2.3 DDH假設

3 DDES-UE方案設計

3.1 系統架構

Fig. 2 System architecture of DDES -UE圖2 DDES -UE方案系統架構

DDES-UE的系統架構如圖2所示.它主要分為2部分：客戶端和云存儲系統.客戶端系統通過Internet連接到各種數據存儲服務器(data storage server, DSS)和數據管理服務器(data management server, DMS).云存儲系統由分布在網絡中的一系列數據存儲服務器和數據管理服務器組成，通過網絡連接形成分布式存儲系統.待存儲的數據首先在客戶端基于密鑰同態偽隨機函數進行分塊加密，然后將分塊密文進行編碼，生成的編碼數據塊分布式存儲在不同的數據節點(即數據存儲服務器)中，關于密文的相關信息和密鑰由數據管理服務器管理.具體的數據存儲過程見3.2.4節.

3.2 方案構建

3.2.1 數據加密

Fig. 3 Data encryption and ciphertext segmentation圖3 數據加密與密文分割

算法1.數據加密算法.

輸入：對稱密鑰k、待加密的數據m；

②χ=x+y；

③τ=h(m)+R(x,0)；

⑤ for 1≤i≤η*接下來計算密文體

⑦ end for

3.2.2 數據分割

在實際部署中，用戶端可通過運行客戶端程序與云存儲系統進行交互，后者除了負責數據的上傳和下載，還負責維護編碼參數和加密密鑰等信息.

3.2.3 數據編碼

客戶端對原始密文數據(即密文體F)進行編碼，得到n(n-k)×r個編碼數據塊，記作(Pij)i=1,2,…,n(n-k),j=1,2,…,r,每個編碼塊都是k(n-k)個初始密文數據塊Macro-blocks所包含的所有子數據塊Mini-block的線性組合.

具體的編碼過程為：

1) 首先在客戶端構造一個n(n-k)×k(n-k)的編碼矩陣EM=(αi,j)，其中元素αi,j均是從有限域GF(2w)中隨機產生，EM必須滿足MDS性質.

2) 客戶端使用過程1)中產生的編碼矩陣與初始密文塊(即k(n-k)個Macro-block)進行乘法運算，得到n(n-k)×r個編碼數據塊.編碼矩陣中每個行向量稱之為一個編碼向量，其形式為Pi=(Pi,1,Pi,2,…,Pi,r)，對應于一個編碼塊.對初始密文塊的每個Macro-block進行編碼后得到的編碼塊矩陣為

(1)

其中,i=1,2,…,n(n-k),x=1,2,…,r.

3.2.4 數據存儲

客戶端將n(n-k)×r個編碼數據塊上傳給n個數據節點，每個節點存儲相鄰的(n-k)×r個數據塊，編碼矩陣由客戶端持有.同時將密文頭上傳至數據管理服務器.

取n=4，k=2時，單個文件的上傳過程如圖4所示.注意在編碼塊的產生過程中，我們以Macro-block為單位進行表述.

Fig. 4 Process of data chunking storage圖4 數據分塊存儲過程

3.2.5 密文更新

數據更新包括2個階段：更新令牌生成和密文重新加密.我們分別描述它們，然后在不同的分布式數據節點中給出編碼塊的獨立更新過程.更新令牌生成過程的描述如算法2所示.

算法2.更新令牌產生算法.

② if (χ,τ)=⊥ then

③ return ⊥；

④ end if

⑥χ′=χ+x′+y′；

⑦τ′=τ+R(x′,0)；

算法3.密文重加密算法.

③ for 1≤i≤η

⑤ end for

第i行第υ列的編碼塊的更新過程可表示為

(2)

3.2.6 數據還原

1) 數據解碼與合并

根據2.2節中基于FMSR碼的數據讀取過程，客戶端從n個數據節點中任取k個負載較小的節點并下載其所有的編碼塊，共計k(n-k)×r個編碼塊，然后從3.2.3節構造的EM中取出上述編碼數據對應的行向量，組成一個k(n-k)×k(n-k)階方陣，記作EM′.需要注意的是，新產生的方陣EM′中的數據來源于EM，其各個行向量線性無關，因此逆矩陣EM′-1必然存在；

然后客戶端使用EM′-1乘以下載的編碼數據塊即可得到k(n-k)×r個原始塊，將其合并組裝即可得到初始的密文數據塊.

取n=4，k=2時，文件M的下載過程如圖5所示，其中每個數據節點存儲的數據塊代表編碼塊矩陣對應的行向量，即Pi,j=(Pi,1,Pi,2,…,Pi,r).

2) 數據解密

Fig. 5 Process of data reduction圖5 數據還原過程

算法4.數據解密算法.

輸出：原始明文M或⊥.

② if (χ,τ)=⊥ then

③ return ⊥；

④ end if

⑥ for 1≤i≤η

⑧ end for

⑨ ifh(m)+R(χ-y,0)=τthen

⑩ returnm=(m1,m2,…,mη)；

4 安全性及數據可用性分析

4.1 安全性分析

根據Everspaugh等人[9]的方案證明，這里從可更新加密不可區分性UE-IND和重加密安全性UE-REENC兩個方面給出DDES-UE中可更新加密的安全性證明.

證明. UE-IND安全游戲選取2個參數t和κ，并初始化t+κ秘密密鑰，其中κ個給予敵手，t個保留用于在諭言中使用.我們用k1,k2,…,kt表示未泄露的密鑰，kt+1,kt+2,…,kt+κ表示已泄露的密鑰.在安全游戲中，我們要求至少一個未泄露的密鑰，但對已泄露的密鑰數量不進行要求，即t≥1,κ≥0.敵手的目標是猜測比特位b，成功意味著方案泄露了關于明文的部分信息.

我們將證明分為2部分:1)使用π的AE安全性來表明用于密鑰同態PRF輸入的x的值對敵手而言是隱藏的；2)基于R是一個密鑰同態偽隨機函數這一事實來說明不可區分性成立，考慮到敵手無法了解到x.

UE-IND安全游戲描述：

b←${0,1};

k1,k2,…,kt+κ←$KeyGen();

return (b′=b).

Enc(i,m):

returnEnc(ki,m).

return ⊥;

end if

else returnC′;

end if

LR(i,m0,m1):

ifi>tthen

return ⊥;

end if

C←$Enc(ki,mb);

returnC.

—若j≤i，為隨機值r′返回(r′,x′,y′)，并存儲(x+x′,y+y′,m)，或者

—若j>i，返回(ε(kj,(χ′,h(m)+R(x+x′,0))),x′,y′).

Enc(i,m):

χ=x+y;

Ci[r]=(x,y,m);

for 1≤i≤η

end for

if (x,y,m)=⊥ then

return ⊥;

end if

χ′=x+y+x′+y′;

ifj≤ithen

Cj[r]=(x+x′,y+y′,m);

else

τ=h(m)+R(x+x′,0);

end if

if (x,y,m)=⊥ then

return ⊥;

end if

x′=x+y-y′;

for 1≤i≤η

end for

τ=h(m)+R(x,0);

ifτ-R(x′,0)=h(m′) then

returnm=(m1,m2,…,mη);

else

return ⊥;

end if

類似地，re-encryption查詢，其中目標密鑰j未泄露，即j≤t，敵手接收在x′下加密的新密文，但仍無法獲得x′的信息.另一方面，如果j>t，InvalidRE=true，因此攻擊者能夠學習到密文頭.其形式為：ε(kj,(x+y+x′+y′,h(m)+R(x+x′,0))).由于攻擊者擁有kj，他們可以解密密文頭.但是x仍被y所隱藏.

對于所有的κ≥0,t≥1均成立.

成立.

證明. 在該定理證明中，應用與定理1證明中相同的t個步驟.然后我們用隨機字符串替換密文頭，并通過記錄先前看到的輸入來模擬re-keygen過程.

4.2 數據可用性分析

本節通過對受損節點的數據重構過程描述來說明DDES-UE方案能夠保證部分節點失效情形下的數據可用性.在2.2節有簡要描述，這里進行詳細說明.在數據節點N1,N2,…,Nn中，假設對數據節點Nx上的數據進行恢復，步驟為

1)客戶端在除了Nx以外的每個節點上隨機挑選一個編碼塊(共有(n-k)n-1種不同的可能)，在存儲的編碼矩陣中取出這(n-1)個編碼塊所對應的編碼向量，記作ECVi1,ECVi2,…,ECVin-1.

2)在客戶端構造(n-k)×(n-1)的變換矩陣TM=(γi,j)，其中i=1,2,…,n-k,j=1,2,…,n-1,矩陣中的元素γi,j均從有限域GF(2w)中隨機產生.

(3)

其中每個新的編碼向量可表示為

(4)

5) 客戶端判斷EM′是否滿足MDS性質，即判斷EM′的中任意k(n-k)個行向量組成的方陣是否滿秩.若滿足MDS性質，執行步驟6)，否則跳到步驟1)，進入下一輪迭代，重新挑選新的編碼向量和變換系數.

6) 客戶端將TM，以及步驟1)中挑選出的編碼塊序號發送給數據節點Nx.

7) 數據節點Nx從相應的數據節點上下載步驟1)中的挑選出的編碼塊，并使用TM對這些編碼塊進行編碼得到n-k個數據塊，覆蓋自身的原有數據，完成一次數據重構.

5 DDES-UE方案的性能分析

DDES-UE方案在存儲結構、數據加密、密鑰輪換以及安全性證明4個方面的對比如表1所示.

本節主要從數據上傳、數據下載、污染數據恢復以及密文更新4個環節對DDES-UE方案的性能進行驗證與分析，分別選取10～100 MB(每次以10 MB遞增)的文件大小，對每個環節中各部分所涉及的關鍵計算(如數據讀取、數據寫入、群元素加法運算、群元素加法運算、群元素冪運算、群元素映射等)的時間開銷進行了綜合測試，并使用Java編程語言構建了我們的參考實現.實驗環境描述為：Windows 64 b操作系統，Intel?CoreTMi7-4770 CPU(3.4 GHz)，內存12 GB.

Table 1 Comparison of Advantages in Different Schemes表1 方案優勢對比

Note: “” indicates that this scheme does not show the corresponding explanation.

在仿真實驗中首先需要實例化DDES-UE使用的密鑰同態PRF.這里使用R(x,i)=H(i)x，其中H被建模為隨機預言H:X→G.構建H的自然方法是采用常規Hash函數h:{0,1}*→{0,1}n.X是任何合適的集合(例如，某些固定長度的位串)，并且(G,+)是判定性Diffie Hellman假設成立的群.

其中數據上傳(選取數據加密、數據編碼、數據傳輸、數據寫入4個部分)與數據下載(選取數據讀取、數據傳輸、數據解碼、數據解密4個部分)過程仿真實驗結果如圖6、圖7所示.結合Hu等人[25]以及陳越等人[33]中的性能分析可以看出，本文構造的DDES-UE方案在分布式數據存儲與恢復(如在數據上傳與下載過程中涉及的數據讀取、數據傳輸、數據編碼解碼以及數據合并等運算和在污染數據恢復時的變換矩陣計算、下載編碼塊、數據重構等)上的性能開銷在可接受范圍內.

Fig. 6 Time cost in different stages of data uploading圖6 數據上傳過程計算開銷

Fig. 7 Time cost in different stages of data downloading圖7 數據下載過程計算開銷

污染數據修復(選取計算轉換矩陣、下載編碼數據塊、數據重構、數據寫入4個部分)與數據更新過程仿真實驗結果分別如圖8、圖9所示.隨著文件大小的增長，污染數據修復過程及數據更新的計算開銷均呈線性增長趨勢，但前者的時間開銷較小，能夠保證高效的數據可恢復性；而文件更新的計算開銷過大.接下來對仿真實驗中涉及數據加解密的計算開銷進行詳細分析.

Fig. 8 Time cost in different stages of data recovery圖8 數據修復過程計算開銷

Fig. 9 Time cost of one data update圖9 一次數據更新過程計算開銷

當然，正如Everspaugh等人[9]描述的那樣，我們提出的方案DDES-UE當前最適用于體量小但非常有價值的數據，比如大型企業的重要客戶資料備份等.該方案既能夠通過分布式存儲滿足數據災備及污染數據恢復的需求，同時也支持分布式架構下存儲數據的直接更新，有效避免了數據恢復與重加密更新的計算開銷和數據上傳下載造成的網絡通信開銷.

6 結束語

本文提出DDES-UE方案，支持分布式云存儲中不同數據節點持有的編碼密文塊的直接更新.基于密鑰同態偽隨機函數，可以將當前密文直接更新為新版本的密文，且更新后的密文與當前版本的密文是一致分布的，即等同于用新密鑰加密的密文，在保證數據安全性的同時節約了通信資源成本.

此外，結合改進的FMSR編碼技術，提出的DDES-UE方案能夠確保分布式存儲系統中部分數據節點受損時的數據可用性，且支持數據恢復時的完整性驗證.同時，可更新加密中的密鑰更新具有時變性，壓縮了攻擊者發起攻擊的時間窗口.假設在較長時間內攻擊者通過某種攻擊方式獲取到存儲密文及用戶私鑰及編碼矩陣，若三者不在同一個時間周期，則無法完成解密，從而使得攻擊結果無效.因此，當云存儲中加密數據的密鑰周期性更新時，系統能夠通過增加攻擊者的時間成本，有效降低攻擊者通過獲取密文密鑰相關信息來破解密文的概率.

安全性證明和性能分析表明:DDES-UE方案可以實現安全有效的密文更新，以應對密鑰泄露的風險；避免了數據重加密時數據上傳下載帶來的巨大通信開銷，并支持數據恢復以保證數據的持續可用性.然而，以群元素大小為單位的數據更新導致計算偽隨機函數所需的標量乘法次數以及Elligator2函數中元素映射的次數成為制約密文更新效率的關鍵因素.這使得我們在有效解決了降低網絡帶寬負載及客戶端重加密計算開銷問題之后，仍需考慮如何降低執行密文更新操作的云存儲服務器的計算開銷.因此，未來工作將深入研究分布式云環境下以數據塊為單位的直接密文更新方法以及針對橢圓曲線點的標量乘法效率改進，為進一步構建更具普適性的加密云存儲系統提供技術支持.