云環(huán)境下基于編碼樹的新型保序加密算法

紀 鵬,呂旭明,蘇善婷,陳 碩,李東民,劉 賽

(1.國網(wǎng)遼寧省電力有限公司,沈陽110000; 2.南京航空航天大學 計算機科學與技術(shù)學院,南京 211106;3.南瑞集團(國網(wǎng)電力科學研究院)有限公司,南京 210000)

0 概述

隨著互聯(lián)網(wǎng)普及率不斷提升,網(wǎng)絡(luò)用戶信息量呈爆炸式增長,計算機領(lǐng)域進入大數(shù)據(jù)時代[1]。為適應計算量指數(shù)級增長,計算模式從單機處理模式發(fā)展為分布式任務(wù)處理模式,再到目前的云計算模式。用戶無需關(guān)心云平臺內(nèi)部如何工作,通過管理服務(wù)器將計算或存儲任務(wù)分派給集群計算機進行處理,最大限度地利用資源[2]。

云計算帶來諸多便利和優(yōu)勢的同時在安全方面也帶來新的挑戰(zhàn)。數(shù)據(jù)上傳到云服務(wù)器后便脫離用戶的物理控制,云存儲服務(wù)器被不法分子攻破會導致大規(guī)模用戶隱私數(shù)據(jù)泄露,這樣的惡性事件帶來的后果十分嚴重。盡管云服務(wù)提供商承諾保證用戶數(shù)據(jù)安全,但當下復雜網(wǎng)絡(luò)環(huán)境中存在的各種木馬、蠕蟲、惡意軟件、病毒以及各種先進的竊密手段讓人防不勝防。因此,云環(huán)境下的數(shù)據(jù)安全以及隱私保護問題成為制約其推廣的主要瓶頸,通過技術(shù)手段提升數(shù)據(jù)安全勢在必行。

數(shù)據(jù)加密是一種保護用戶數(shù)據(jù)的常用方法,用戶在本地對數(shù)據(jù)進行加密,將密文存儲在云平臺進行托管。即便云存儲服務(wù)器發(fā)生數(shù)據(jù)泄露,被竊取的僅僅是密文數(shù)據(jù),在沒有密鑰的情況下無法獲取真實數(shù)據(jù)[3]。同時,數(shù)據(jù)加密技術(shù)可防止第三方不可信云服務(wù)器管理員利用技術(shù)手段對用戶數(shù)據(jù)進行竊取,為用戶數(shù)據(jù)的安全提供有力保障。

采用加密手段保護數(shù)據(jù)的限制在于,解密過程必須通過被信任的第三方應用[4]。傳統(tǒng)加密算法多數(shù)不支持對密文的運算操作:1)加密數(shù)據(jù)難以通過傳統(tǒng)的信息檢索方式實現(xiàn)有效檢索,必須將云端大量文件傳輸回本地,逐一解密后再檢索;2)云平臺應用擴展的會受到限制,例如,用戶需要對云端的數(shù)據(jù)排序或范圍查詢,云平臺很難提供相應功能,極大削弱了云計算的應用范圍和優(yōu)勢。

文獻[5]提出保序加密的基本概念,對于任意明文,若滿足x>y,則必有[x1,x2]?；诖颂攸c,對于[x1,x2]范圍內(nèi)明文的查詢,可轉(zhuǎn)化為對[x1,x2]范圍內(nèi)密文查詢。該加密算法可應用于不可信的云環(huán)境下,對隱私數(shù)據(jù)保護的同時對密文進行相應計算,實現(xiàn)密文數(shù)據(jù)范圍查詢、排序等操作,突破在云環(huán)境下的檢索瓶頸。

本文提出一種基于編碼樹的保序加密算法。該算法對明文數(shù)據(jù)進行分割并通過對稱加密算法得到明文對應的DET密文,在服務(wù)端構(gòu)建滿足B樹結(jié)構(gòu)的編碼樹。以明文大小作為關(guān)鍵字排列順序的依據(jù),將關(guān)鍵字查找路徑作為最終保序密文,同時利用密文更新策略保證加密算法的高效性和可靠性。

1 相關(guān)工作

保序加密是一個廣義概念,本質(zhì)是通過構(gòu)造函數(shù)將明文數(shù)據(jù)轉(zhuǎn)化為密文數(shù)據(jù)。研究者基于此概念通過不同角度設(shè)計構(gòu)造函數(shù),主要包括基于超幾何分布、基于隨機均勻采樣以及基于查找樹的編碼方式3種類型。

文獻[6]提出基于超幾何分布取樣的加密構(gòu)造算法,對于定義域[x1,x2]內(nèi)的明文,其加密后密文分布在[y1,y2],對于密文y3=(y1+y2)/2,根據(jù)超逆幾何概率從定義域選擇明文x3與之對應。文獻[7]設(shè)計的算法與此思路類似,在密文與明文空間劃分方法及映射函數(shù)不同。文獻[8]提出一種基于非退化矩陣的保序加密方案,通過矩陣實現(xiàn)明文與密文間的映射,具有較高安全性。由于矩陣構(gòu)造過程復雜性較高,該方法不適用云環(huán)境下海量數(shù)據(jù)加密。文獻[9]提出基于噪聲的保序加密算法,在線性加密函數(shù)基礎(chǔ)上添加隨機噪聲,以此提高加密安全性。文獻[10]采用基于網(wǎng)格對角線劃分實現(xiàn)保序密文生成,將每個明文數(shù)據(jù)作為坐標系中一點,通過二分搜索找出位于對角線上的點并將這些點作為密鑰,通過線型函數(shù)計算密文。文獻[11]基于近似公約數(shù)提出一種隨機數(shù)保序加密算法,該算法可保證常數(shù)加密復雜度并且能夠隱藏明文分布信息。

以上方法基于數(shù)學方法定義構(gòu)造函數(shù),缺點是可能泄露明文分布情況。攻擊者獲取密文后,采用碰撞攻擊的方式能夠?qū)崿F(xiàn)解密。文獻[6]提出等序明文不可區(qū)分(INDistinguishability under Ordered Chosen Plaintext Attacks,IND-OCPA)的定義,這一定義規(guī)定經(jīng)過保序加密后,攻擊者即使獲得2個密文也無法根據(jù)密文序關(guān)系確定明文序關(guān)系。文獻[12]提出基于二叉樹的保序編碼構(gòu)造方式,將密文作為關(guān)鍵字存儲在查找樹中,存儲位置根據(jù)明文大小確定,由根節(jié)點出發(fā)到達每一個關(guān)鍵字的路徑確定數(shù)據(jù)的保序密文,這種方法生成的密文不依賴于密鑰,與傳統(tǒng)的加密方法有所區(qū)別,嚴格來說屬于一種編碼方法。文獻[13]采用編碼方式保序加密,不同的是在加密過程中通過惰性計算提高加密速度,插入數(shù)據(jù)時使用普通加密算法處理,對數(shù)據(jù)查詢時通過編碼方式得到保序密文。在頻繁插入操作應用場景下可顯著提高加密效率,并對明文頻率信息隱藏。文獻[14]改進了文獻[12]方法中的編碼方式,提高了加密效率同時保證IND-OCPA安全性,在此基礎(chǔ)上提出一種改進算法[15],基于明文頻率實現(xiàn)將一對一編碼規(guī)則改進為一對多編碼方式,一對多編碼指相同的明文經(jīng)過加密后可被映射為不同密文,這種編碼方式優(yōu)點是加密后明文頻率分布發(fā)生變化。文獻[16]在基于編碼的保序加密算法基礎(chǔ)上進行擴展,利用消息空間擴展以及非線性空間分割來隱藏數(shù)據(jù)的分布和頻率。文獻[17]使用同態(tài)加密對保序加密中密文生成過程進行改進,提出一種支持多種關(guān)系運算的保序加密算法。文獻[18]提出基于空間的保序加密方案,利用數(shù)據(jù)庫常用索引結(jié)構(gòu)生成數(shù)據(jù)保序密文,實現(xiàn)對高維數(shù)據(jù)加密并支持多種不同查詢類型。

2 基于編碼樹的保序加密算法

定義1(確定性加密DET) DET是一種偽隨機轉(zhuǎn)換方式,相同明文經(jīng)過轉(zhuǎn)換后所得密文內(nèi)容相同,密文在恢復時根據(jù)密鑰進行逆向變換可實現(xiàn)還原,支持對明文數(shù)據(jù)等值匹配[19-20]。DET加密采用對稱加密實現(xiàn),比如固定IV的AES-CBC模式。

定義2(保序加密OPE) OPE通過一個保持數(shù)據(jù)有序性的映射機制實現(xiàn)明文與密文編碼的轉(zhuǎn)化,對于保序加密算法Enc定義域內(nèi)任意明文,若滿足x>y,必有OPE={KeyGen,InitState,Enc,Dec,Order}。因此對于OPE={KeyGen,InitState,Enc,Dec,Order}范圍內(nèi)明文的查詢,可轉(zhuǎn)化為對OPE={KeyGen,InitState,Enc,Dec,Order}范圍內(nèi)密文的查詢[21]。

定義3(保序編碼OPC) OPC能夠反映密文間大小關(guān)系,對不可信服務(wù)器是可見的,明文大小的比較可轉(zhuǎn)換為對保序編碼大小的比較。在設(shè)計保序編碼時應盡量降低與明文之間的相關(guān)性,保證不可信服務(wù)器無法通過保序編碼獲取明文數(shù)據(jù)。

2.1 保序加密算法整體框架

保序加密算法可形式化表示為一個五元組OPE={KeyGen,InitState,Enc,Dec,Order}。算法功能拆分為2部分,運行在客戶端負責保序密文的生成和運行在服務(wù)器,在用戶更新數(shù)據(jù)時對密文進行同步更新。其中,KeyGen具有隨機性,而其他元素具有確定性,Enc具有交互性,各元素具體含義如下:

1)密鑰生成:KeyGen(1k)→sk,在服務(wù)器上輸入安全參數(shù)Dec(sk,c)→v,通過密鑰生成函數(shù)生成用戶加密私鑰sk。

2)服務(wù)器初始化:Dec(sk,c)→v,在服務(wù)器通過輸入安全參數(shù)Dec(sk,c)→v,生成初始編碼樹st。

3)加密:Dec(sk,c)→v,該過程是客戶端與服務(wù)器交互過程,在客戶端輸入私鑰sk與明文v,服務(wù)器輸入原始編碼樹st,最終客戶端獲得對應密文c,客戶端將密文傳輸?shù)椒?wù)器存儲,服務(wù)器生成新的編碼樹Dec(sk,c)→v。

4)解密:Dec(sk,c)→v,客戶端運行解密函數(shù),輸入私鑰sk以及密文c,得到對應明文v。

5)編碼調(diào)整:Order(st,c)→e,在服務(wù)器進行編碼調(diào)整,輸入原始編碼樹st以及密文c,生成一個新的保序編碼表e。

保序加密算法通過對稱加密算法生成DET密文,根據(jù)明文數(shù)據(jù)大小關(guān)系構(gòu)建編碼樹,通過明文數(shù)據(jù)在編碼樹中查找路徑生成OPC,將DET密文與OPC存儲于數(shù)據(jù)服務(wù)器中,加密流程如圖1所示。

圖1 保序加密流程

2.2 基于編碼樹的OPC生成策略

定義4(編碼樹OPEm) OPEm結(jié)構(gòu)類似于m階B樹,節(jié)點的關(guān)鍵字為用戶數(shù)據(jù)DET密文,圖2給出一個OPE4實例。

圖2 編碼樹結(jié)構(gòu)示意圖

編碼樹具體結(jié)構(gòu)如下:

1)根節(jié)點至少包含2個子節(jié)點,除非編碼樹僅包含一個關(guān)鍵字。

2)每個非根節(jié)點指向子節(jié)點的指針個數(shù)取值范圍為[m/2,m],關(guān)鍵字個數(shù)取值范圍為[m/2-1,m-1]。

3)包含n個關(guān)鍵字的節(jié)點組織形式為(P0,V1,P1,V2,…,Vn,Pn)。其中,V1、V2、V3關(guān)鍵字滿足V1對應的明文數(shù)據(jù)小于V2對應的明文數(shù)據(jù),P1為指向該節(jié)點子樹的指針,子樹中所有節(jié)點關(guān)鍵字所對應明文數(shù)據(jù)大于V1對應的明文數(shù)據(jù)并且小于V2對應的明文數(shù)據(jù)。

在圖2中,每個節(jié)點中關(guān)鍵字為DET密文(受限于圖片大小僅展示密文部分內(nèi)容),方框內(nèi)數(shù)字為明文數(shù)據(jù),實際明文并不出現(xiàn)在編碼樹中,此處僅為形象說明。

對于一個OPEm定義如下編碼規(guī)則:

1)每個非葉子節(jié)點指針依次編碼(0,1,…,m)。

2)節(jié)點內(nèi)部關(guān)鍵字依次編碼(0,1,…,m-1)。

3)編碼二進制表示,每個編碼長度len=lbm。

每個關(guān)鍵字編碼過程可轉(zhuǎn)化為在編碼樹中查找一個關(guān)鍵字的過程。從根節(jié)點出發(fā)向下查找關(guān)鍵字,如果關(guān)鍵字位于節(jié)點內(nèi),則將關(guān)鍵字編碼按位串聯(lián),否則將使用到的指針編碼按位串聯(lián),直到查找到關(guān)鍵字所在節(jié)點[22]。

對于高度為H的編碼樹,設(shè)定其編碼長度為L=H×len。編碼樹第h層節(jié)點(根節(jié)點為第1層節(jié)點,葉子節(jié)點為第H層節(jié)點)中關(guān)鍵字實際編碼code長度為可通過式(1)計算:

|code|=h×len,1≤h≤H

(1)

在實際編碼尾部用1將編碼長度填充至L,關(guān)鍵字OPE編碼格式為OPC=(code[11…1])。對于圖2所示編碼樹,樹的高度為3,對應編碼長度為6。按照上文定義的編碼標準對明文進行編碼結(jié)果如表1所示。

表1 編碼結(jié)果

最終保序密文為OPC對應的十進制形式,從表1可看出,基于編碼樹生成的OPC與明文數(shù)據(jù)之間沒有任何相關(guān)性,因此不會泄露任何明文信息,同時OPC的大小能夠準確反映明文數(shù)值間大小關(guān)系。

2.3 保序密文更新規(guī)則

在節(jié)點中插入關(guān)鍵字后,若該節(jié)點內(nèi)關(guān)鍵字數(shù)量超過m-1會引起節(jié)點分裂。因此,在討論插入數(shù)據(jù)時編碼更新方案分2種情況:未發(fā)生節(jié)點分裂和發(fā)生節(jié)點分裂。

1)未發(fā)生節(jié)點分裂

對于未發(fā)生節(jié)點分裂情況編碼更新較為簡單,新增關(guān)鍵字編碼通過位于之前的關(guān)鍵字編碼加1,在之后的關(guān)鍵字通過在原編碼基礎(chǔ)上加1得到。假設(shè)關(guān)鍵字節(jié)點位于編碼樹第h層,并在實際編碼后補充len×h個1,對應編碼更新規(guī)則如式(2)所示。

code′=code+1

(2)

2)發(fā)生節(jié)點分裂

對于分裂過程中新生成的節(jié)點中所有關(guān)鍵字,由于分裂位置發(fā)生在一個節(jié)點的m/2處,編碼路徑對應增加m/2,并在編碼后填充(L-len×h)個1,編碼更新規(guī)則如式(3)所示。

(3)

對于分裂過程中插入父節(jié)點的關(guān)鍵字,將原關(guān)鍵字編碼最后len位置為1,其他編碼保持不變,更新后該關(guān)鍵字將位于h-1層節(jié)點,在編碼后填充(L-len×h+len)個1,編碼更新規(guī)則如式(4)所示。

code′=code<

(4)

分裂后如果生成新的根節(jié)點,則樹中所有關(guān)鍵字右移一個編碼長度len,編碼更新規(guī)則如式(5)所示。

code″=code′>>len

(5)

新生成的根節(jié)點只包含左右2個子樹,根節(jié)點左子樹所有關(guān)鍵字在編碼頭部串聯(lián)00,根節(jié)點右子樹所有關(guān)鍵字在編碼頭部串聯(lián)01,以彌補右移后空缺的編碼位。

圖3給出在編碼樹中插入關(guān)鍵字后造成節(jié)點分裂并生成新根節(jié)點的實例,為簡潔表示圖中編碼樹中關(guān)鍵字直接用明文代替。在構(gòu)建保序編碼時選取m=4,L=6,對應的編碼更新情況如表2所示。

圖3 編碼樹更新實例

關(guān)鍵字更新前更新后編碼層數(shù)編碼層數(shù)2400[1111]=1510000[11]=324601[1111]=3110001[11]=725310[1111]=4710100[11]=192150000[11]=32000000=03180001[11]=72000001=13450100[11]=192000100=43471000[11]=352001000=83481001[11]=392001001=93491011[11]=47200[1111]=151901100[11]=482010100=20350——010000=163

3 實驗結(jié)果與分析

3.1 安全性分析

等序明文不可區(qū)分是保序加密理想的安全狀態(tài),規(guī)定對于2個序關(guān)系相同的明文,攻擊者無法區(qū)分加密后密文的序關(guān)系。

定義5(IND-OCPA博弈) 對于一個客戶端C以及攻擊者Adv有如下的博弈過程:

1)C通過密鑰生成函數(shù)KeyGen(1k)→sk生成一個密鑰sk,并選擇一個隨機位b。

2)C與Adv進行多輪博弈,每輪博弈過程中攻擊者進行自適應調(diào)整,第i輪博弈過程如下:

(1)Adv向客戶端C發(fā)送2個明文m/2-1。

(2)C將明文m/2-1與密鑰sk作為輸入,在服務(wù)器Sev中進行保序加密,在此過程中Adv通過監(jiān)視Sev可獲得加密結(jié)果。

3)攻擊者輸出一個m/2-1,作為b的猜測。

在多輪博弈過程中輸入的明文序列m/2-1與m/2-1具有相同的序關(guān)系(對于所有的m/2-1,滿足m/2-1)。如果攻擊者猜測的結(jié)果m/2-1,則認為攻擊者取得勝利。

攻擊者向客戶端輸入明文序列m/2-1以及m/2-1,通過服務(wù)器獲取信息。保序加密使用對稱加密算法生成DET密文,對于相同明文生成密文信息相同。接下來論證在客戶端加密V明文序列和W明文序列時攻擊者所能夠獲得的信息相同[23]。

初始階段服務(wù)器不存儲任何信息,之后的每次數(shù)據(jù)加密,由于明文序列V與W具有相同序關(guān)系,密文會被插入到編碼樹中相同位置,所得保序密文也相同,這種情況下攻擊者仍然無法根據(jù)密文區(qū)分出對應的明文。因此,本文算法滿足IND-OCPA安全定義。

3.2 實驗測試

本文實驗硬件平臺包括1臺客戶端、1臺管理服務(wù)器、2臺數(shù)據(jù)服務(wù)器,具體配置為:

客戶端向用戶提供登錄界面,實現(xiàn)與管理服務(wù)器建立連接并請求服務(wù),機器配置為:Intel Core 4核處理器,3.0 GHz、4 GB RAM、Window 7操作系統(tǒng)、JDK1.7。

管理服務(wù)器通過開源云計算框架OpenStack管理后端數(shù)據(jù)服務(wù)器,通過webservice為用戶提供服務(wù),機器配置為:Intel Core4核處理器,3.2 GHz、16 GB RAM、Ubuntu 14操作系統(tǒng)。

數(shù)據(jù)服務(wù)器配置為:8個AMD Opteron8431 6核處理器,2.4 GHz、64 GB RAM、Ubuntu 14操作系統(tǒng)、MySql 5.6。

編碼樹的階m是影響性質(zhì)的一個重要參數(shù),影響每個節(jié)點中關(guān)鍵字以及子節(jié)點指針的數(shù)量[24]。一般選取m為2的冪,保證每個編碼長度len能取到整數(shù)。考慮一次讀取到內(nèi)存數(shù)據(jù)量不宜過大,m分別取16、32,對應的len分別為4和5。

根據(jù)上文介紹保序加密流程可知,加密過程包括根據(jù)明文大小判斷數(shù)據(jù)位于編碼樹中位置以及編碼調(diào)整步數(shù)。對于n個關(guān)鍵字,生成平衡二叉樹的高度h=lbn,對應計算編碼時間復雜度為m/2-1。對于m階B樹,其高度h取值范圍為[logmn,logm/2((n+1)/2)+1],對于最壞的情況樹高h=logm/2((n+1)/2)+1(樹中每個節(jié)點包含m/2-1個關(guān)鍵字)。此時計算編碼時間復雜度為O(logm/2(n))。采用m階編碼樹理論上可將時間縮短為原來的1/logm/22。

數(shù)據(jù)插入后需進行編碼調(diào)整。對于二叉平衡樹進行保序編碼時,檢查過程是從插入數(shù)據(jù)節(jié)點位置開始向上回溯,檢查過程時間復雜度為O(lbn)。對于B樹進行編碼,檢查判斷插入數(shù)據(jù)后節(jié)點關(guān)鍵字是否超過m-1,檢查時間復雜度為O(logm/2(n))。使用2種結(jié)構(gòu)進行編碼更新的時間復雜度均為O(1)。

測試數(shù)據(jù)集包含5 000條數(shù)值型數(shù)據(jù),其集合R={r1,r2,…,r5 000},每條數(shù)據(jù)均通過隨機函數(shù)生成,無統(tǒng)一序關(guān)系,分別使用mOPE[12]、OPEBCT16(m設(shè)置為16)與OPEBCT32(m設(shè)置為32)對數(shù)據(jù)進行加密。上述3種方法運行時間進行統(tǒng)計,包括加密總時間、編碼生成時間以及編碼更新時間,如圖4～圖6所示。

圖4 加密總時間隨插入記錄數(shù)量變化趨勢

圖5 保序編碼生成時間隨插入記錄數(shù)量變化趨勢

圖6 編碼更新時間隨插入記錄數(shù)量變化趨勢

從圖4可以看出,使用mOPE、OPEBCT16與OPEBCT32加密5 000條數(shù)據(jù)所花費總時間分別為11 948 ms、3 859 ms、3 214 ms,加密時間分別為原來的32.3%(約等于1/lb 8)與 26.9%(約等于1/lb 16)。

從圖5和圖6可以看出,在編碼生成過程與編碼更新過程中,使用OPEBCT方法可縮短加密時間,但時間縮短原因是不同的。前者由于B樹高度降低使得客戶端與服務(wù)端通信次數(shù)減少,后者由于編碼更新規(guī)則的設(shè)置減少服務(wù)器內(nèi)部計算開銷。

表3給出3種方法各步驟平均運行時間,其中查找路徑長度根據(jù)客戶端與服務(wù)端通信次數(shù)確定。從表3數(shù)據(jù)可看出,本文方法減少加密過程中客戶端與服務(wù)端通信次數(shù),提高插入數(shù)據(jù)時保序密文生成時間,與上文分析結(jié)果一致。

表3 3種方法平均耗時對比

綜上所述,使用編碼樹替代二叉平衡樹進行保序編碼的生成工作,能夠有效減少加密過程所耗費時間,同時隨著編碼樹階m的增大,加密時間呈縮小趨勢?？紤]計算機內(nèi)存一次可計算數(shù)據(jù)量將m設(shè)置為32。

4 結(jié)束語

本文提出一種基于編碼樹的保序加密算法,該算法對明文數(shù)據(jù)分割并通過對稱加密算法得到明文對應的DET密文,在服務(wù)端構(gòu)建滿足B樹結(jié)構(gòu)的編碼樹,以明文大小為關(guān)鍵字排列順序提供依據(jù),將關(guān)鍵字查找路徑作為最終保序密文。針對保序密文的可變性,提出了保序密文更新策略,當用戶插入新數(shù)據(jù)時根據(jù)更新規(guī)則實現(xiàn)密文同步變換。測試結(jié)果表明,本文算法具有較高的加密效率。下一步將圍繞保序加密算法應用場景,根據(jù)密文保持明文序關(guān)系的特性,以支持多種密文運算。