一種采用簽名與哈希技術的云存儲去重方案

張桂鵬，匡振曦，陳平華

廣東工業大學 計算機學院，廣州510006

1 引言

近年來，云計算行業呈現出穩定快速的發展態勢。由于云計算產業結構的不斷優化和提供云計算服務的企業不斷增多，用戶數據的處理和存儲得到了極大的簡化和保障，用戶只需將數據存儲外包給第三方云存儲服務提供商即可。然而，隨著存儲在云服務器的數據爆炸式增長，數據需要占用的存儲空間和傳輸帶寬也將增加。因此重復數據刪除技術[1-2]成為了一項急需研究的數據壓縮技術，該技術通過計算出的文件標簽來檢測和消除冗余數據，能夠極大地減少存儲空間和降低傳輸帶寬消耗，受到了學術界和工業界越來越多的關注。

按照檢測文件大小粒度的不同，重復數據刪除方案可以分為文件級去重方案[3]和數據塊級去重方案[4-5]。文件級去重方案可以消除文件的重復副本，只保留一份文件副本和指向副本的索引；而數據塊級去重方案能夠消除不同文件中重復數據塊，同樣只保留一份數據塊副本和指向數據塊的索引。盡管重復數據刪除方案大大提高了數據存儲空間利用率，節省了大量磁盤空間，但是由于數據存儲在第三方云存儲服務器上，這將導致用戶無法判斷自己數據是否處于安全存儲的狀態，數據的安全性和隱私性得不到有效的保障，即使用傳統的加密算法對數據進行加密，也會導致不同用戶的相同數據產生不同的密文，從而影響重復數據刪除。

為了解決傳統加密算法與重復數據刪除不兼容的問題，Douceur 等[6]提出收斂加密算法（Convergent Encryption，CE），使用收斂密鑰來加密和解密文件，其中收斂密鑰由文件內容通過散列函數計算生成，因此相同的文件會產生相同的收斂密鑰，從而生成相同的密文。CE 算法使得重復數據刪除得以實現，并已廣泛地應用在一些理論研究和去重方案[7-10]中。Puzio等[11]結合CE 算法提出了ClouDedup 方案，引入第三方密鑰服務器來對數據再次進行加密，減少客戶端的存儲空間消耗；Li 等[12]將秘密共享方案與CE 算法結合，提出了CDStore 方案，通過將算法中的隨機信息確定化來實現數據的安全去重，有效地減少存儲空間；Stanek 等[13]根據文件的流行程度提出了一種面向不同等級的加密算法，分別對流行和非流行文件采用不同的加密模式，來加強對數據的保密性。但由于CE算法缺乏嚴格的密碼學原語定義和形式化的安全模型，以上所提到的結合CE算法的方案都無法應對攻擊者進行的暴力破解。

Bellare 等[14]提出了一種新的密碼學原語—消息鎖加密算法（Message-Locked Encryption，MLE），該算法的提出為收斂加密算法提供了理論依據，然而MLE 只適用于保護具有比較高的不可預測性的數據。2015年，Bellare 等[15]在MLE 的基礎上提出了一種擴展MLE 方案，但是iMLE 方案仍停留在理論探索階段，實用性不高；文獻[7]使用基于lockbox原理來存儲并加密數據，在數據去重中引入代理重加密技術，保證數據內容無法被猜測獲取，但服務器需要承擔數量龐大的密鑰管理;Li等[16]提出了一種混合云架構的數據去重方案，通過執行額外的加密算法來增強數據的安全性，使得數據只能被具有特定權限的用戶訪問，但私有云需要承擔過大的計算量，不適用于具有較大規模用戶量的去重系統。張桂鵬等[17]在混合云架構中引入權限等級函數來計算去重標簽，并且用Merkle哈希樹來計算權限密鑰，有效地降低去重標簽和密鑰的計算時間開銷。Chen 等[18]提出了BL-MLE方案，能夠通過少量元數據來實現文件級和數據塊級的安全去重，適用于大規模加密文件，然而在去重過程中增加了POW 驗證，服務器端的通信消耗過大。為了降低計算開銷，Liu 等[19]提出了一種適用于云加密去重系統中的完整性審計方案，該方案能夠減少客戶端的計算開銷，有效地保證了外包數據的機密性和完整性，但仍存在著MLE算法面臨的缺陷，亟需進一步進行方案的研究和改進。

為了提高數據的安全性和機密性，實現支持多云存儲系統[20]的數據安全去重，提出了一種采用簽名與哈希技術的云存儲去重方案，主要貢獻如下。

（1）在數據去重過程中采用了雙層校驗機制：全局校驗和局部校驗。通過雙層校驗機制能夠審計文件的完整性以及精確地定位到損壞的數據塊，保證了數據的完整性，有效地防止單一云存儲服務提供商對數據進行壟斷控制。

（2）改進了傳統的云存儲去重系統模型，引入多云模型并且在元數據服務器部署密鑰和權限服務器，通過構造Merkle哈希樹來生成校驗值δ，從而計算出去重標簽，保證了重復數據能夠被檢測，降低去重標簽的計算開銷。

（3）能夠有效地支持文件級和數據塊級別的重復數據刪除，高效地實現了多云存儲的安全去重系統。

2 預備知識

2.1 符號說明

符號及說明如表1所示。

表1 符號說明

2.2 代數簽名

代數簽名是一種具有同態性和代數性的哈希函數，作為一種輕量級的信息簽名方式，計算開銷較小。代數簽名的基本特性是指數據塊代數簽名的和與所對應得數據塊和的代數簽名結果一致[21]。設λ 為有限域的一種元素，且向量λ=(λ1,λ2,…,λn)由非零元素組成。由n個數據塊(f[1],f[2],…,f[n])組成的文件F 的代數簽名計算如下：

其中的代數簽名的一些性質如下：

性質1 長度為r 的塊f[i]串聯f[j]后的代數簽名計算式為：

性質2 文件F 中所有數據塊的簽名總和等于每個數據塊的簽名總和：

性質3 兩個文件F 和G 的代數簽名和等于每個文件簽名和：

2.3 Merkle哈希樹

Merkle哈希樹是一種哈希二叉樹，所構造的所有節點均為Hash值，葉子節點為數據信息的哈希值，其余非葉子節點由其孩子節點串接后哈希運算得到的，依次從下向上逐層運算，最終將會得到唯一的根節點ROOT，此時Merkle哈希樹構造完成。在本方案中，設定Merkle哈希樹構造函數為Mroot=MHT({m})，其中{m}為數據信息集合，函數的輸出值為該根節點的值Mroot。如圖1所示，該Merkle 哈希樹的葉子節點A、B、C、D 分別為H(B1),H(B2),H(B3),H(B4)，非葉子節點E=H(H(B1)+H(B2))，F=H(H(B3)+H(B4)，最終能夠得到唯一的根節點值G=H(H(E)+H(F))=MHT({Bi})，其中1 ≤i ≤4。

圖1 Merkle哈希樹構造流程圖

2.4 所有權證明算法（POW）

所有權證明算法用來證明用戶是否擁有存儲在云服務器中的數據，以防止攻擊者通過數據指紋信息從服務器中獲取完整的文件。服務器需要根據文件生成相應的挑戰發送給用戶，用戶根據擁有的文件，生成正確的應答并返回驗證，以此來證明用戶確實擁有該文件，在現有文獻中已有許多有效的POW，包括基于MHT的POW[22]、BF-POW[23]等。

3 問題闡述

3.1 系統模型

本章將介紹方案中存在的系統模型和安全威脅模型的定義，如圖2所示，系統模型包含三種實體模型：用戶實體，元數據服務器，多云存儲服務提供商實體。

圖2 多云環境下的數據安全去重系統模型

用戶實體（User）：用戶需要將數據文件進行上傳存儲到MDS 中，以降低文件傳輸中的帶寬，節省存儲空間，其中數據文件只需要上傳一份，不需要上傳重復的文件，在支持訪問控制的數據去重系統中，用戶上傳文件時可設定文件的訪問權限，以提供特定的用戶進行分享下載。

元數據服務器（MDS）：元數據服務器主要對用戶上傳的數據文件進行處理，具有一定的存儲容量（相比于云存儲服務提供商的存儲容量則小很多），將處理后的密文存儲在MS-CSP上，當用戶上傳數據文件時，元數據服務器進行安全去重檢測來降低存儲成本。在本方案中，設定元數據服務器為誠實可信的第三方服務器。

多云存儲服務提供商實體（MS-CSP）：多云存儲服務提供商由多個不同的云存儲服務提供商（S-CSP）構成，主要接收來自MDS 處理加密后的數據文件和相關標簽，并合理地存儲在其服務器上。在本方案中，假定MS-CSP具有充足的存儲容量和計算能力。

3.2 威脅模型和安全目標

在本方案中，威脅模型主要考慮了兩種類型的攻擊者：外部攻擊者和內部攻擊者，外部攻擊者和內部攻擊者都試圖通過公共信道盡可能多地獲取到存儲在MS-CSP 的數據信息，外部攻擊者未擁有有效的權限，會企圖偽裝成合法的用戶來與MDS 進行交互；內部攻擊者擁有部分有效的權限，可以看作是誠實而又好奇的用戶，也會上傳文件與MDS和MS-CSP進行交互，試圖獲取到其他用戶的數據密文或者加密密鑰。因此在基于MDS 為誠實可信的第三方前提下，安全模型提出了以下安全性要求，包括數據的安全性和數據的完整性。

數據的安全性：包括了去重標簽和密文的安全性，非授權的用戶或者沒有被身份認證的用戶將無法獲取到任何的去重標簽，只有被授權的用戶在MDS 的驗證通過下，才能通過與私有云進行交互計算來獲取文件的去重標簽，從而執行數據重復檢測操作。在本方案中，去重標簽通過采用了Mapbox和Lockbox結合的機制來加密，有效地抵制了暴力攻擊，同時加密密文的密鑰只保存在MDS，非授權的用戶即使進行串謀，也無法通過獲取密鑰來解密密文。

數據的完整性：由于數據文件是由多個不同的S-CSP進行存儲管理，存儲在MS-CSP的數據將會面臨著被攻擊者進行竊取損壞，或者其中某些S-CSP進行的惡意串謀行為等風險，數據的完整性要求MDS 能夠檢測出數據是否完整，即使數據被損壞，也能檢測出存儲在哪些S-CSP的數據遭受攻擊損壞，使得用戶不需擔心數據被惡意替換損壞。

4 方案實現

4.1 基本思路

本方案改進了傳統的云存儲去重系統模型，在上傳文件時，用戶通過構造Merkle哈希樹來生成校驗值，從而計算出去重標簽，保證了重復數據能夠被檢測。MDS對來自用戶的數據文件進行預處理，采用Mapbox 和Lockbox結合的機制來加密數據信息，保證非授權的用戶無法對文件進行訪問，在下載文件時，使用雙層校驗機制能夠檢測出數據是否完整，也可以定位到丟失損壞的數據塊，高效實現了支持文件級和數據塊級的數據安全去重系統。

4.2 系統初始化

設定用戶身份標識為ID（ID可由加密的用戶名，密碼等組成），用戶所擁有的權限集為PU，用戶設定上傳文件F 的訪問限制權限集為PF，云存儲服務提供商的數量為n；在本方案中，數據去重是基于多個獨立的S-CSP環境下執行的，此時的文件是由多個S-CSP進行協同存儲，而不再是由單一的S-CSP 存儲，每個S-CSP都存儲著數量不定的數據塊，在缺少其他S-CSP的協同下，單一的S-CSP 將無法獲取到完整的文件，有效地避免傳統單一的S-CSP對用戶文件進行壟斷控制。

4.3 用戶認證

為了確保數據文件的安全性，用戶在上傳文件之前，需要與MDS之間進行身份認證.首先用戶將身份標識ID 和所具有的權限PU發送給MDS，MDS 進行身份認證[24]并輸出驗證結果，如果驗證結果不通過，MDS將停止當前的數據操作，拒絕用戶與MS-CSP進行數據交互；如果驗證通過，則繼續執行下列操作。

4.4 文件上傳

文件上傳過程包括文件級和數據塊級的安全去重過程，用戶先執行文件級數據去重，當檢測結果為文件不重復，則再將文件切分成數據塊，進而執行細粒度更小的塊級去重，具體的操作流程如下：

用戶選取哈希函數H1、H2，計算文件F 的去重標簽?Fi=H2(H1(F⊕δ))，用戶將去重標簽?Fi發送給MDS，其中?Fi用于對文件F 的重復檢測，MDS 并將檢測的結果返回給用戶。

若檢測結果為：文件F 為重復，則進行以下操作。

MDS將與用戶之間運行POW算法，通過所有權證明的檢測來判定用戶是否確實擁有文件F ，如果沒有通過所有權證明，MDS將停止與用戶進行數據操作，拒絕用戶訪問當前的文件；如果通過所有權證明，MDS通知用戶不再上傳文件F ，授權允許用戶擁有該文件F并返回指針給用戶，以便用戶訪問文件，用戶無需再上傳文件F。

若檢測結果為：文件F 為不重復，MDS選取一密鑰kB，將密鑰kB發送給用戶，用戶進而執行數據塊級別的重復檢測刪除：

用戶計算出每一塊數據塊Bi的去重標簽?Bi=H2(H1(B)⊕kB)，將去重標簽?Bi發送給MDS，其中?Bi用于對數據塊Bi的重復檢測，MDS 根據文件的訪問限制權限PF選取權限密鑰kp，并將檢測結果返回給用戶。

若檢測結果為：數據塊Bi為重復，則進行以下操作。

MDS同樣需要與用戶之間運行POW算法，如果通過所有權證明，MDS通知用戶無需再上傳數據塊Bi，并更新Lockboxi結構信息，同時使用密鑰kp對Lockboxi進行解密，即Mapboxi=Decrypt(kp,Lockboxi)，更新該數據塊Bi的Mapboxi信息并返回塊指針給用戶，以便用戶訪問相應的數據塊。如果沒有通過所有權證明，MDS 將停止與用戶進行數據操作，拒絕用戶訪問當前的數據塊Bi。

若檢測結果為：數據塊Bi為不重復，則進行以下操作。

用戶將文件校驗值δ 和數據塊Bi發送給MDS，MDS將生成數據塊Bi的Mapboxi結構，來記錄數據塊Bi的位置和標簽，Mapboxi結構包括了數據塊序號Numi、文件標簽信息?Fi、數據塊標簽信息?Bi、存儲的位置地址σi；接著MDS 使用用戶的權限密鑰kp對Mapboxi進行加密，來生成數據塊Bi的Lockboxi結構，即結構還記錄該數據塊的IDi，用戶的訪問限制權限PF，Lockboxi結構能有效防止Mapboxi信息泄露，只有用戶權限符合權限PF，才能對Mapboxi信息進行訪問。

MDS對數據塊Bi進行加密，得到密文Ci=Encrypt(kB,Bi)，同時使用代數簽名計算出數據塊Bi的簽名信息Γi=Sλ(f[i]||Lockboxi)，將權限密鑰kp和密鑰kB存儲在MDS 所部署的權限和密鑰管理服務器上，并將所得到的數據{Ci、Γi}一起發送到MS-CSP，MS-CSP存儲后將會返回塊指針σi，指針σi記錄著密文Ci的存儲位置，包括所在的S-CSP編號和排列位置。

4.5 文件下載

當需要下載文件F ，用戶發送下載請求給MDS，MDS 獲取到該用戶的權限密鑰kp，先驗證用戶所具有的權限PU是否符合文件訪問權限PF。當驗證通過時，MDS 獲取存儲在MS-CSP 的數據信息{Ci、Γi} ，MDS 使用密鑰kB對密文Ci進行解密，得到數據塊，此時需要對下載到的數據塊執行雙層校驗機制，即全局校驗和局部校驗，具體操作如下：

（2）MDS 先計算出Sλ(Lockboxi) ，將Sλ(Lockboxi)與同時下載到的簽名信息Γi進行異或運算，得到

（3）MDS 對下載到的數據塊Bi分別計算出其代數簽名，得到S′λ(f[i])，只要檢測到S′λ(f[i])與Sλ(f[i])不相同，則說明該數據塊Bi已經遭受損壞，通過附加的數據塊標識σi可確定存儲數據塊Bi的S-CSP的代號和排列位置。

5 安全性分析

本文方案通過全局校驗和局部校驗來校驗文件的完整性以及精確地定位到丟失損壞的數據塊，保證了數據的完整性，并且采用Mapbox 和Lockbox 結合的機制來加密數據信息，使得非授權的用戶無法對文件進行訪問；在假定MDS為可信第三方的前提下，本章將從以下兩方面進行安全性分析，即數據安全性和數據的完整性。

5.1 數據的安全性

數據安全性包括了去重標簽的安全性和密文的安全性。本方案所采用去重標簽生成算法與傳統的標簽生成算法不同，傳統的標簽生成算法通過對數據文件進行哈希運算獲得，即?=TagGen(F)=H(F)，當攻擊者知道數據文件F屬于有限可預測的文件集合{F1,F2,…,Fn}，攻擊者通過對集合的數據元素進行哈希運算并將結果與? 進行逐一對比，以此能夠猜測出數據內容F，在本方案中，文件級的去重標簽計算需要校驗值δ 的參與，而校驗值δ 是通過Merkle哈希樹的構造來生成，對于相同的文件F、δ 和?Fi也將保持一致，一方面能夠保證了重復數據能夠被檢測，另一方面即使攻擊者得知數據文件F 的相關信息，由于無法推測出校驗值δ，因而也猜測不出數據內容F ，有效地抵制了攻擊者進行的暴力攻擊。

對于密文信息的安全性，本方案使用Mapbox 和Lockbox 結合的機制來加密數據信息，數據文件被分割成若干個數據塊Bi，Mapbox 存儲著數據塊Bi的地址標簽等相關信息，而Lockbox 存儲著數據塊的IDi訪問限制權限和已加密的Mapbox。外部攻擊者或非授權的用戶由于缺少有效的權限密鑰kp，將無法通過MDS的權限驗證來與其進行交互；內部攻擊者即使通過公共信道獲取到了其他用戶的Lockbox，也無法分辨出其中的數據信息來解密出Lockbox；在假定MDS為可信第三方的前提下，密文C 和簽名信息Γi存儲在MS-CSP，而解密密鑰kB只存儲在MDS中，在MDS未授權的情況下，S-CSP 將無法獲取到密鑰kB的任何信息，因此即使SCSP與未授權的用戶進行共謀，也無法通過偽造密鑰kB來解密密文。

5.2 數據的完整性

在下載文件時，需要對數據的完整性進行雙層校驗，本方案采用的全局校驗能夠檢測出文件F 的完整性，即所切分成的數據塊是否存在丟失損壞，數據塊Bi一旦發生丟失損壞，生成的校驗值δ 會立即改變，通過校驗值δ 可判斷文件是否完整。局部校驗通過密文附加的簽名信息Sλ(f[i])來能夠定位到丟失損壞的數據塊，包括兩種情況：如果某一數據塊Bi的S′λ(f[i])不存在，即該數據塊Bi已經缺失，如果某一數據塊Bi的S′λ(f[i])與計算出的Sλ(f[i])不同，即該數據塊Bi已遭損壞，并且通過標識σi可確定該損壞數據塊Bi原先存儲的S-CSP代號，以此進行問責。

6 性能分析與實驗評估

本章將提出的方案與文獻[16]所提出的文件級去重方案進行仿真實驗對比，本方案的仿真實驗環境是在i5-7300HQ 的CPU，內存8 GB，主頻2.50 GHz 的64 位PC機上實現的，采用Java語言編程進行性能仿真測試。

實驗1 測試不同文件大小下去重標簽生成的時間開銷，實驗分別選取文件大小為20 MB、40 MB、60 MB、80 MB、100 MB和120 MB，在數據塊大小為6 KB，權限數目恒定的情況下進行仿真測試，實驗結果如圖3 所示。隨著文件大小越大，兩個方案中去重標簽生成所需要的時間開銷也會隨之增加，本方案與文獻[16]方案相比，在計算去重標簽所需要的時間開銷會更少，并且在文件大小越大的情況下，時間開銷差異會更加明顯。

圖3 不同文件大小下的去重標簽生成的時間開銷

實驗2 測試不同文件大小下密文生成的時間開銷，實驗分別選取文件大小為10 MB、20 MB、30 MB、40 MB、50 MB、60 MB、70 MB、和80 MB進行仿真測試，數據塊的大小恒為16 KB。實驗結果如圖4 所示，當文件大小越大，密文所需要的計算時間開銷也會增加，本方案中對數據塊采用的是對稱加密算法，可以看出文件大小和密文生成的時間開銷趨向于一定的線性關系。

圖4 不同文件大小下的密文生成的時間開銷

實驗3 測試不同數據塊數目下校驗值δ 的計算時間開銷。在實驗中，使用3 組數據塊大小分別為4 KB、8 KB和16 KB進行仿真測試，實驗結果如圖5所示。校驗值δ 所需要的計算時間開銷隨著數據塊數目增多而單調遞增。并且數據塊大小越大，需要的時間開銷也將越多，當數目增多時，數據塊大小對于所需時間開銷的影響也將更加明顯；從圖中可看出，數據塊大小為4 KB 和8 KB 的曲線僅僅呈現出緩慢增長趨勢，而數據塊大小為16 KB 時，計算哈希值的時間開銷將明顯增多，總計算時間開銷也會明顯增大，其曲線大致保持線性增加。

圖5 不同數據塊數目下的校驗值δ 的計算時間開銷

7 結束語

本文提出了一種采用簽名與哈希技術的云存儲去重方案，能夠有效地支持文件級和數據塊級的加密數據去重檢測，實現了細粒度的去重。同時，采用Mapbox和Lockbox結合的機制來加密數據信息，使得非授權的用戶無法對文件進行訪問。進行下載文件時，由代數簽名構成的雙層校驗機制，能夠校驗文件的完整性以及精確地定位到丟失損壞的數據塊，保證了數據的完整性；安全性分析表明，方案能夠有效地抵制攻擊者進行的暴力攻擊。仿真實驗結果表明，方案能有效地降低去重標簽的計算開銷，減少存儲空間。今后的研究工作主要集中在數據去重過程中，保護各參與方的隱私信息不被泄露，同時提出相應的策略來高效地執行大數據環境下的數據檢測去重操作。