云平臺數據完整性混合驗證方案

毛向杰,張 品

(杭州電子科技大學 通信工程學院,杭州 310018)

0 概述

近年來,云計算[1]的快速發展為用戶降低了大量的本地存儲空間并減輕了數據管理負擔[2],使用戶能夠通過不同設備在不同位置方便地訪問云端數據,并且可以隨時分享這些數據。但是,由于用戶未在物理端對數據進行存儲,因此該模式面臨外部威脅,如云數據的存儲安全性問題。云存儲安全必須保證用戶能夠存儲數據并且無需擔心是否要驗證其完整性,因此,高效驗證云數據的完整性非常重要[3]。

云端存儲的各種數據效用不同,一些數據會被經常性查看,而一些數據幾乎不會被查看。以私有云為例,用戶將日常生活中用到的數據在云端備份,如書籍壓縮包、視頻壓縮包等資料常會在首次存進云盤后被查看,然后就幾乎不會再被查看,也不會被更新。高頻率訪問的數據種類有限,通常為用戶拍攝的照片、電影和音樂等。在云數據的硬件存儲中,會根據數據訪問頻率及規律將存儲的數據分為熱數據、溫數據和冷數據,其中,冷數據所占比例高達80%[4]。

一般數據的機密性通常由數據加密[5]和匿名機制[6]等方法來保證,在云存儲技術出現后,研究者提出新的方法來保障云數據的安全性。現有的數據完整性驗證方案主要分為數據可恢復性證明(POR)方案[7]和數據持有性證明(PDP)方案[8]兩類。在POR方案中,用戶不僅可以驗證遠程數據的完整性,而且可以通過使用糾刪碼來完整地恢復損壞的云端數據。與POR方案相比,由于PDP方案未使用糾刪碼,因此其效率更高。

為達到更高的驗證效率,現有多數PDP方案使用同態驗證標簽(Homomorphic Verifiable Tags,HVTs),主要包括基于MAC[9]、基于RSA[10]和基于BLS[11]3種PDP完整性驗證方案。其中,MAC只能進行有限次驗證且輔助信息過多。在相同的安全強度下,BLS簽名[12]具有較短的簽名位數,約為160 bit,相比RSA簽名的1 024 bit要少很多,此外,其具有同態的特性,能夠將多個簽名聚合為一個[13],這也減少了整個驗證過程的計算代價和通信開銷。基于BLS簽名的方案采用輕量級第三方審計模型,滿足云存儲輕量級設計要求,降低了用戶的計算負擔。

在云存儲技術快速發展的背景下,云數據的日益增長使用戶有了新的需求,數據不再是靜態形式,而需要經常進行插入、刪除等動態操作,因此,PDP方案的設計不能僅局限于解決靜態數據的完整性驗證問題。文獻[14]提出動態數據持有性證明(Dynamic Provable Data Possession,DPDP)方案,DPDP方案對PDP方案的較大改進是支持動態數據操作,近年來研究者通過不斷改進現有的DPDP方案,使其性能得到不斷提升。目前主流的DPDP方案都使用認證數據結構(Authenticated Data Structure,ADS)進行完整性審計,如基于默克爾哈希樹(Merkle Hash Tree,MHT)[15-16]、基于跳表[17]、基于多分支樹(Large Branching Tree,LBT)[18]等多種DPDP完整性驗證方案。對于數據的隱私保護,文獻[19]采用隨機掩碼技術提高方案的安全性,并采用索引表機制實現數據的動態更新,減少了計算和通信開銷。

由于多數云數據不需要動態更新,因此為提高審計效率,可以考慮對不涉及動態更新的數據使用PDP驗證方案,從而省去較多的驗證環節。本文提出一種數據混合HPDP方案,對無需進行動態操作的數據選擇PDP驗證,而需要更新的數據則使用效率較高的LBT方案,從而降低計算開銷和通信負擔,提高驗證效率。

1 云平臺數據完整性驗證方案模型

1.1 預備知識

雙線性映射的定義為:e:G×G→GT,其中,G和GT為GDH(Gap Diffie-Hellman)群,即乘法循環群,該雙線性映射具有以下性質:

1)雙線性:

?x,y∈G?e(xa,yb)=e(x,y)ab

(1)

2)可計算性:e存在并且能夠高效計算。

3)非退化性:

?x∈G,x≠0?e(x,x)≠1

(2)

1.2 方案模型

本文方案模型使用混合驗證策略,其為文獻[20]方案的改進。如圖1所示,該模型由數據所有者(Data Owner,DO)、云服務供應商(Cloud Service Provider,CSP)和第三方審計(Third Party Auditor,TPA)組成。其中,DO負責對數據初始化,委托TPA對數據進行審計;CSP提供數據的存儲服務,管理DO的數據,具有較強的計算存儲能力,并且應答TPA發來的挑戰,返回證明給TPA;TPA是由用戶委托的完整性審計實體,負責向CSP發起挑戰信息并且驗證CSP返回的證明是否正確,然后將審計結果返回給DO。對于靜態數據文件,DO在進行初始化時采用基于BLS-PDP的完整性驗證方案;對于動態數據文件,DO在進行初始化時選擇基于LBT-DPDP的數據完整性驗證方案。

圖1 云數據完整性審計系統架構Fig.1 Architecture of cloud data integrity audit system

數據審計過程通常分為以下3個階段:

1)Setup階段。數據的擁有者預處理文件,先執行密鑰生成算法生成公私鑰對,再將文件分塊,利用標簽生成算法生成元數據。將處理后的文件發送到云服務器,刪除本地存儲的文件副本。

2)Challenge階段。數據的擁有者向第三方審計發起驗證請求,第三方審計隨機生成要驗證的數據塊的下標,向云服務器發起挑戰。

3)Check-proof階段。云服務器收到挑戰后運行證明算法生成證明并返回給第三方審計。第三方審計使用驗證算法來驗證返回的證明是否正確,將驗證結果0/1(0代表數據被破壞,1代表數據完好)返回給數據的擁有者。

2 云數據完整性混合驗證方法

2.1 方案設計

本文方案在設計時考慮的重點是對于整個云存儲性質的判定,考慮用戶存儲數據的類型以及使用云存儲的場景,通過了解用戶對于存儲的具體要求制定相應的存儲策略,從而在用戶進行數據審計時選取合適的審計方案。本文為每個用戶提供2種審計方案,用戶在進行數據預處理上傳時選擇一種審計方案來進行預處理。如果上傳一些靜態文件,后續不需要進行插入、刪除和修改操作,直接使用BLS-PDP方案處理數據;如果是動態文件,則使用LBT-PDP方案。

為對不同類型的數據進行相應的審計,可以采用分區存儲或者標記的方法。本文使用分區存儲的方法將云存儲分為動態存儲區和靜態存儲區。在用戶發起挑戰請求時,如果選取的數據在靜態存儲區,使用BLS-PDP方案進行驗證,反之則使用LBT-DPDP方案驗證。

整個方案模型仍按第三方審計模型設計,只是用戶端的數據處理方式有所不同。DO會根據上傳數據的類型來選擇不同的驗證方案,選定驗證方案后對數據進行相應的初始化處理并上傳到CSP,在數據進行完整性驗證時也會按照方案的不同執行不同的審計流程。對于數據初始化階段,2種方案只存在很小的差別。對于挑戰-應答階段,大致流程基本相同,但具體細節不同,LBT-DPDP方案的計算開銷與通信代價更大。此外,LBT-DPDP方案中還存在數據動態操作階段。本文方案的整體流程如圖2所示。

圖2 混合驗證方案流程Fig.2 Procedure of hybrid verification scheme

2.2 方案描述

本文方案為混合驗證方案,由PDP方案實現靜態數據審計,由DPDP方案實現動態數據審計。

1)靜態審計

對于靜態數據,不涉及動態操作,需要考慮的是審計的開銷,在這種情況下,使用BLS-PDP方案更能節省系統的計算代價與通信開銷;針對數據量大、數據更新頻繁的動態數據,顯然使用LBT-DPDP方案更合適。靜態審計的具體步驟如下:

(1)KeyGen(1k)→(pk,sk)。在系統初始化時,由DO在本地執行。1k為輸入的安全參數,返回一對公私鑰(pk,sk)。

(2)TagBlock(sk,F)→{T}。TagBlock(·)算法由DO執行,生成元數據T,即同態簽名標簽集。該算法的輸入參數包括私鑰sk和數據文件F,返回認證的元數據T。

(3)GenProof(pk,F′,T,chal)→P。該算法由CSP運行,生成完整性證明P。輸入參數包括公鑰pk、處理后的文件F′、挑戰請求chal和認證元數據集合T,返回證明P。

(4)CheckProof(pk,chal,P)→(1,0)。該算法由驗證者TPA運行,對CSP返回的證明P進行判斷。輸入參數為公鑰pk、挑戰請求chal及證明P。返回驗證結果1或0,1表明數據完整,0表示數據被破壞。

整個驗證過程無需考慮數據的更新操作,在DO初始化上傳數據之后,后續的完整性審計工作完全交給TPA完成,大幅降低了DO的計算負擔,同時整個驗證的通信量也得到大幅減少,其對數據的審計是一次性生成元數據,可以進行無數次的審計。此外,由于使用的是HVTs,因此BLS-PDP方案在擁有同態優勢的同時,生成元數據時占用的內存更少,每個數據塊只占用20 Byte,從而減少了通信開銷。

2)動態審計

對于需要進行動態更新的動態審計,本文選用LBT-DPDP方案以高效地執行動態操作。文獻[20]方案在動態審計時使用的是跳表,但是LBT相比跳表更高效,因此,本文方案使用LBT-DPDP作為動態審計的方法。LBT支持大規模的數據插入操作,其為動態更新最常使用的操作。動態審計的具體步驟如下:

(1)KeyGen(1k)→{sk,pk}。該算法由DO運行,輸入安全參數1k,返回私鑰sk和公鑰pk。

(2)TagGen(sk,F)→{T}。該算法由DO運行并產生元數據,將數據文件F和私鑰sk作為輸入并輸出標簽集T,T是數據塊{mi}上簽名{τi}的集合。

(3)Update(F,Info,Ω,pk)→{F′,P}。該算法由CSP運行并應答TPA的更新請求。采用數據文件F,更新信息Info,以前的輔助信息Ω和公鑰pk作為輸入。輸出的是數據文件F的新版本F′及其證明P。CSP將證明P發送給TPA。

(4)VerifyUpdate(P,pk)→{1,0}。該算法由TPA運行并驗證CSP是否正確更新了數據。輸入包含來自CSP的證明P和公鑰pk。如果證明有效則輸出接受結果1,反之輸出拒絕結果0。

(5)Challenge(·)→{chal}。TPA運行該算法啟動挑戰并發送CSP的挑戰信息chal。

(6)GenProof(F′,T,chal,pk)→{P}。該算法由CSP運行,將數據文件F′、元數據T、挑戰信息chal以及公鑰pk作為輸入,輸出證明信息P。

(7)VerifyProof(P,pk)→{1,0}。TPA運行該算法來驗證來自CSP的證明信息P。如果證明正確輸出1,反之輸出0。

3 性能分析與實驗評估

每一種檢驗云存儲數據完整性的方案都有各自的優缺點,有不同的適用場景,沒有哪一種方案能夠滿足所有的存儲需求且性能最優。因此,沒有一個統一的標準來對每一種方案進行評價,但是可以通過組合方案的方法發揮出各自方案的優點,下文從通信開銷和計算開銷2個方面來分析BLS-PDP方案與LBT-DPDP方案在針對不同數據類型時的優勢。

3.1 計算代價分析

計算開銷主要來自于實體DO、TPA和CSP,它們在不同階段產生的計算開銷決定了整個方案的驗證效率。在初始化階段,主要是由DO對數據進行預處理產生的計算開銷,整個初始化階段會因為采用不同的方案而有不同的計算復雜度。對于BLS-PDP方案而言,不用構造樹形結構而只需生成元數據即可,因此,計算開銷大幅降低,時間復雜度為O(1)。而LBT-DPDP方案則需要構建LBT,整個過程的時間復雜度為O(logkn)。因此,對于DO而言,在初始化階段,2種方案的計算復雜度不同,BLS-PDP方案在初始化階段對數據的處理效率更高。

在動態更新階段,LBT-DPDP方案進行修改操作時需要執行1次指數級計算操作,進行插入操作時需要2次指數級計算,進行刪除操作時不需要計算,而BLS-PDP方案沒有動態更新操作。

在完整性審計階段,對數據的處理不同于初始化階段的數據一次性處理和動態更新階段的針對性處理,因為這2個階段的處理次數是有限制的,而完整性審計階段是一個周期性重復的過程,只要數據存儲在CSP,就會不斷地進行完整性審計,因此,完整性驗證是整個方案中計算量最多的環節,也決定了整個方案的驗證效率。假設數據塊的總數為n,挑戰的數據塊數目為c,LBT-DPDP方案的審計過程需要的計算為2c次加法和2c次乘法,此外每次審計都要遍歷LBT,因此,總的時間復雜度為O(logkn)。BLS-PDP的TPA審計過程只需要對隨機抽取的c個數據塊進行驗證即可,沒有其他復雜的計算,時間復雜度為O(c),而c的值約為460,數值不大,因此,整個時間復雜度可以表示為O(1)。

BLS的完整性審計計算速度遠快于LBT,大幅節約了整個系統的計算資源,并且兩者計算速度的差異會隨著數據量的增大而增大,滿足線性關系。因此,對于海量的云端數據而言,本文混合方案能夠節約計算資源,提高整個云端數據的審計效率。

3.2 通信代價分析

通信開銷主要在于信息的交互,因為數據上傳的通信開銷只會在數據初始化階段,所以整個驗證過程的通信代價都取決于挑戰-應答階段,即TPA與CSP之間為進行完整性驗證而相互傳遞信息的開銷大小。LBT-DPDP方案在CSP產生證明信息時,構建ADS需要大量輔助信息,這使得通信代價大幅提高。而BLS-PDP方案因為不存在樹形結構,無需太多輔助信息來產生證明,因此,其通信代價遠低于LBT-DPDP方案。

LBT-DPDP方案的完整性驗證需要構建認證路徑以及大量的輔助信息,從被選取的數據塊對應的葉子節點一直向根節點移動,中間通過的路徑的節點都為驗證該數據塊正確性的輔助信息,時間復雜度為O(logkn)。而BLS-PDP方案只需要傳輸c個數據塊的信息就可以達到審計的目的,并且因為使用HTVs,可以將多個數據塊的信息聚合為一個,所以通信的時間復雜度為O(1)。BLS-PDP方案的通信開銷遠小于LBT-DPDP方案,減輕了TPA與CSP的通信負擔。

現有多種審計方案的性能比較結果如表1和表2所示,其中,c為隨機抽取的數據塊數目,f為數據塊損壞的比例,n為文件分塊數,k為LBT的出度,a為動態文件百分比。可以看出,BLS-PDP方案除了不能進行動態更新,在整個驗證過程中效率明顯高于LBT-DPDP方案,節約了整個系統的計算資源,減少了通信開銷,并且整個CSP存儲的靜態數據越多,BLS-PDP方案的性能優勢越大,而對于需要動態更新的動態數據,LBT-DPDP方案具有支持批操作以及審計過程中輔助信息更少的優點。由此可見,2種方案的結合可使云數據的審計更高效。

表1 7種審計方案的功能對比Table 1 Function comparison of seven audit schemes

表2 7種審計方案的復雜度對比Table 2 Complexity comparison of seven audit schemes

3.3 實驗評估

為驗證本文混合驗證方案的性能優勢,在Windows10環境中使用Java實現方案基本功能,PC機的配置為英特爾酷睿四核,CPU i5-4200M,主頻2.50 GHz,內存4 GB。方案中使用的加解密算法、簽名和哈希均從PBC庫和OpenSSL庫中調取。實驗輸入采用1 600個隨機生成的數據文件,總大小為1 GB,結果取10次實驗的平均值。

為驗證本文混合方案的TPA驗證效率優于單一動態驗證方案,分別實現BLS-PDP和LBT-DPDP驗證方案,并將三者進行對比,LBT-DPDP驗證方案默認使用最大出度16。實驗步驟如下:

1)質詢數據塊數量為460,混合驗證方案的TPA驗證時間與數據的類型有關,設定不同的動態數據占比,驗證TPA時間與動態數據占比的關系。

2)假定動態數據與靜態數據各占50%,質詢數據塊數量為460,比較3種驗證方案在不同數據塊大小下TPA的驗證時間。

3)同樣設置動態數據與靜態數據各占50%,數據塊分塊大小為4 kB,比較3種方案總的審計時間,驗證本文方案的審計效率是否具有優勢。

動態數據所占百分比對TPA驗證時間的影響如圖3所示。可以看出,全為靜態數據與全為動態數據的驗證時間分別為數據混合狀態驗證時間的下限與上限,動態數據越多,驗證時間也越長,驗證時間與動態數據的占比接近呈線性關系。

圖3 動態數據占比對TPA驗證時間的影響Fig.3 Effect of percentages of dynamic data on TPA verification time

3種方案的TPA驗證時間比較如圖4所示,從圖4可以看出,BLS-PDP方案時間最短,其不涉及復雜的ADS生成與驗證,LBT-DPDP方案時間最長,而本文方案介于兩者之間,且與動態文件與靜態文件各自所占比例有關,靜態文件越多,本文方案的驗證時間越短,效率越高,節省的系統資源越多。

圖4 3種方案的TPA驗證時間對比Fig.4 TPA verification time comparison of three schemes

文獻[20]方案與本文方案的審計時間對比如圖5所示。可以看出,與文獻[20]方案相比,因為LBT比跳表高效,所以在相同的數據塊大小情況下,本文方案審計時間較少,且隨著審計數據塊的增多,LBT審計節省的時間越多,總體的審計效率更高。

圖5 本文方案與文獻[20]方案的審計時間對比Fig.5 Audit time comparison between the proposed scheme and the scheme in literature[20]

4 結束語

本文提出一種云平臺數據完整性混合驗證方案。根據用戶存儲數據的類型選用不同的審計方案,對靜態類型文件與動態類型文件分別使用BLS-PDP方案和LBT-DPDP方案,從而提高審計效率,發揮不同審計方案的優勢。性能分析與實驗結果表明,該方案能夠減少完整性驗證過程中的計算量與通信代價。下一步將研究具體的PDP與DPDP選擇方法,同時降低TPA與CSP的通信量。此外,還將考慮解決方案的兼容性問題,使2種方案能夠實現代碼復用和模塊共用。