支持正則表達(dá)式的密文檢索方案的研究

李威杰 華保健 李 曦

(中國科學(xué)技術(shù)大學(xué)軟件學(xué)院 安徽 合肥 230051)(中國科學(xué)技術(shù)大學(xué)蘇州研究院 江蘇 蘇州 215123)

支持正則表達(dá)式的密文檢索方案的研究

李威杰 華保健 李 曦

(中國科學(xué)技術(shù)大學(xué)軟件學(xué)院 安徽 合肥 230051)(中國科學(xué)技術(shù)大學(xué)蘇州研究院 江蘇 蘇州 215123)

隨著云計算的發(fā)展，越來越多的敏感數(shù)據(jù)被存儲在云服務(wù)器上。為了保護(hù)隱私數(shù)據(jù)，通常對隱私數(shù)據(jù)進(jìn)行加密。由于數(shù)據(jù)加密，很多對明文字符串的操作方案變得不可用，尤其是在密文狀態(tài)下，如何使用正則表達(dá)式進(jìn)行字符串的匹配，沒有一種切實有效的方案。對在密文狀態(tài)下正則表達(dá)式的使用進(jìn)行研究，提出一種支持大部分常用的正則表達(dá)式規(guī)則的加密方案SCA(Searchable Crypt Algorithm)。SCA支持的正則表達(dá)式規(guī)則有ab*、bc?、a+、ab{m,n}等常用規(guī)則。

密文檢索 正則表達(dá)式 加密 云計算

0 引 言

隨著云計算技術(shù)的成熟以及云計算成本的降低，越來越多的數(shù)據(jù)和服務(wù)放在了云服務(wù)器上，用戶失去了對數(shù)據(jù)和服務(wù)的直接控制。云服務(wù)商內(nèi)部人員或者外部攻擊者，都可能濫用或者泄露用戶的隱私數(shù)據(jù)。因此，用戶選擇了對隱私數(shù)據(jù)加密存儲。然而，現(xiàn)有的加密方案使得很多對明文有效的操作，在密文狀態(tài)下變得不可用。比如字符串模式匹配，特別正則表達(dá)式。例如，在明文存儲情況下，用戶很容易向郵件服務(wù)器搜索包含“緊急”關(guān)鍵字的郵件，但是加密存儲后，服務(wù)器就很難做到在不解密郵件的情況下，知道哪些郵件包含“緊急”關(guān)鍵字。如果要尋找包含“a*b”這樣模式串的郵件有哪些，則變得更為困難。目前的研究成果支持在加密狀態(tài)下，對關(guān)鍵字進(jìn)行精確匹配搜索、簡單的模糊匹配以及通配符匹配操作，對統(tǒng)配符的操作是基于多個精確匹配來實現(xiàn)的。目前還沒有一種切實有效的方案支持對密文進(jìn)行正則表達(dá)式的操作。本文提出了一種有效的支持常用正則表達(dá)式的加密方案SCA。SCA能夠支持常用的正則表達(dá)式規(guī)則，如a*、ab+、ac?、a{m,n}等。

1 相關(guān)工作

Song等人[1]提出了一種簡單實用的流密文檢索方案。該方案把文本分為若干個單詞，并對每一個單詞用對稱加密算法進(jìn)行加密，并且把加密后的單詞分割成左右兩部分，和等長的對應(yīng)的隨機字符串進(jìn)行異或操作，形成最終的密文。該方案可以有效地支持在密文狀態(tài)下，關(guān)鍵詞的精確匹配。該方案的加密粒度是一個單詞，不能處理單個字符或者漢字，因此無法在密文狀態(tài)下支持正則表達(dá)式檢索。Bonech等人[2-3]提出了非對稱密文檢索方案，此方案要求用戶首先為明文m選擇若干個關(guān)鍵字：w1,w2,…,wn。然后使用公鑰pubkey，對明文和關(guān)鍵字進(jìn)行加密。當(dāng)用戶向服務(wù)器查詢明文是否包含關(guān)鍵字w時,根據(jù)私鑰生成陷門Tw，以及用公鑰加密后的密文關(guān)鍵字w′，就可以測試明文是否包含關(guān)鍵字w。整個過程，服務(wù)器不能得到明文的任何信息。此方案需要對加密的內(nèi)容進(jìn)行關(guān)鍵字的提煉，并且加密粒度為一個單詞，因此無法在密文狀態(tài)下支持正則表達(dá)式。Bellovin等人[4-6]提出了基于BloomFilter的密文檢索方案。此方案需要事先對明文文本進(jìn)行關(guān)鍵字的提取操作，然后初始化一個布隆過濾器，對提取的關(guān)鍵字用hash函數(shù)進(jìn)行hash運算,將布隆過濾器的相關(guān)位置1,如果要搜索密文里是否包含關(guān)鍵字w,只需要用hash函數(shù)對關(guān)鍵字w進(jìn)行hash運算,查看布隆過濾器相關(guān)位置是否都為1，如果都為1，則密文里包含關(guān)鍵字w,否則不包含。此方案的缺陷在于：只能為明文提取有限的關(guān)鍵字，如果明文里包含關(guān)鍵字w，但是沒有提取出來，則是無法檢索到w的。使用布隆過濾器，只能用來判斷關(guān)鍵詞是否存在，無法判斷關(guān)鍵詞的位置，以及布隆過濾器不能用來對數(shù)據(jù)進(jìn)行加密，也無法支持密文狀態(tài)下，使用正則表達(dá)式對密文進(jìn)行檢索。Liu等人[7]改進(jìn)了Bonech等人[2-3]的非對稱密文檢索方案PEKS,提出了一個更加有效更加安全的密文檢索方案EPPKS，但是也只支持若干關(guān)鍵字精確匹配，只是更加有效和安全，但并沒有彌補PEKS缺陷，也是不支持全文匹配和正則表達(dá)式。

根據(jù)以上分析，我們發(fā)現(xiàn)目前對密文進(jìn)行正則表達(dá)式操作的研究還比較少，也沒有切實可行的方案。本文對密文支持正則表達(dá)式進(jìn)行了研究，并提出了支持常用正則表達(dá)式的加密方案SCA。

2 支持正則表達(dá)式的加密方案SCA

2.1SCA的定義

定義1 (SCA的定義)SCA=(Enc,Dec,Match)由以下三部分組成:

1) 加密算法Enc滿足對于兩個相同的明文字符，加密后生成不同的密文，防止統(tǒng)計攻擊分析。

2) 解密算法Dec，能夠準(zhǔn)確無誤地將密文還原成明文字符。

3) 密文匹配算法Match，實現(xiàn)將密文模式串中對應(yīng)的字符和密文目的串中的字符準(zhǔn)確匹配。

2.2SCA的詳細(xì)設(shè)計

1) 加密算法Enc的設(shè)計

如圖1所示，對于給定的一個明文字符m,如果m為要加密存儲在服務(wù)器上的目的串的字符，則生成的結(jié)果包含兩部分，c為根據(jù)密鑰key，利用加密算法加密生成的密文字符，checksum為c的校驗。checksum主要用于Dec和Match算法中。如果m為要檢索的模式串中明文字符，則最終生成flag‖keychecksum(flag為固定長度標(biāo)志位,用來標(biāo)志是普通字符還是正則表達(dá)式的特殊字符)傳遞給服務(wù)器,進(jìn)行Match操作。

圖1 加密算法Enc的設(shè)計

2) 解密算法Dec的設(shè)計

如圖2所示，對于給定的密文c，由用戶密鑰key，將c對應(yīng)的明文字符m解密出來。然后根據(jù)m生成新的校驗cs，判斷cs與原來的校驗checksum是否一致，判斷解密數(shù)據(jù)是否被篡改。

圖2 解密算法Dec的設(shè)計

3) 密文匹配算法Match的設(shè)計

假設(shè)目的串明文字符m對應(yīng)的加密結(jié)果為(c,checksum)，模式串明文字符n，對應(yīng)的加密結(jié)果為c′=flag‖keychecksum，則只需要根據(jù)c和keychecksum計算出一個校驗checksum′，并且比較checksum′與checksum是否相等。如果相等，則說明m和n相等，否則m和n不相等。

圖3 密文匹配算法Match的設(shè)計

2.3SCA對常用正則表達(dá)式的支持

SCA是對明文字符串的單個字符為加密單位進(jìn)行加密的。對于所有檢索模式串中單個明文字符m，SCA經(jīng)過加密后生成c=flag‖keychecksum，flag為固定長度，keychecksum也為固定長度。為了區(qū)分普通字符和正則表達(dá)式的功能字符，這里引進(jìn)了固定長度的flag，假設(shè)flag為8位二進(jìn)制。則對于普通字符，flag設(shè)置為0x00,checksum是Enc計算出來的數(shù)值。對于正則表達(dá)式特殊字符如*、?、+、、{、}等，flag設(shè)置為0x01。對于ab{3,10}這種正則表達(dá)式里的數(shù)字，flag則設(shè)置為0x02。

對于特殊字符*、?、+、、{、}等這種字符，SCA提供一個特定的公開的編碼表，每個字符對應(yīng)一個編碼，作為checksum值,假設(shè)checksum為16位二進(jìn)制。編碼表如下：

對于ab{3,10}這種數(shù)字，對應(yīng)的checksum則為數(shù)字本身，比如3對應(yīng)的checksum為0x0003,10對應(yīng)的checksum為0x000a。

舉個例子如下：

明文狀態(tài)下，在目的字符串中檢索能夠匹配模式串a(chǎn)*b{2,5}子串。明文狀態(tài)下很容易用正則表達(dá)式來完成檢索。在密文狀態(tài)下，當(dāng)用戶要檢索含有模式串a(chǎn)*b{2,5}的字符串時，需要先把模式串a(chǎn)*b{2,5}通過SCA加密之后，傳遞給服務(wù)器，然后服務(wù)器在密文狀態(tài)下來完成檢索任務(wù)。

a*b{2,5}對應(yīng)的密文(0x00,0x02a79b31),(0x01,0x0001),(0x00,0x1c3d562d),(0x01,0x0004),(0x02,0x0002),(0x01,0x0009),(0x02,0x0005),(0x01,0x0005)。此時密文狀態(tài)下的正則表達(dá)式引擎，根據(jù)上述特殊字符的編碼規(guī)則，可以知道其中第二個括號內(nèi)代表的是統(tǒng)配*,后面四個括號代表{2,5}，表示第三個括號對應(yīng)的明文字符重復(fù)2至5次。Match算法描述了如何判斷兩個正常的明文字符在密文狀態(tài)下是否相等。因此，這樣SCA便可以在密文狀態(tài)下有效地支持正則表達(dá)式。

3 SCA的性能分析

1) 加密過程Enc的時間復(fù)雜度

由Enc偽代碼可知，加密單個字符需要進(jìn)行一次random操作，兩次AES操作，一次MD5操作。假設(shè)一次random操作時間為c1,一次AES操作時間為c2,一次MD5操作時間為c3，則加密n個字符需要(c1+2×c2+c3)×n，是一個線性時間復(fù)雜度。圖4為編碼實驗得出的結(jié)果，符合理論分析，橫坐標(biāo)為加密字符個數(shù)，單位為100。下為Enc的偽代碼：

//key為密鑰，m為普通明文或者明文模式串

//type為加密類型，分為兩種，一種是加密普通明文，存儲在服務(wù)器，另一種是加密明文檢索模式串

Enc(key,m,type)

result = []

if(type == ENC_PATTERN)

{

foreach ch in m:

key_checksum = AES(key,ch)

result.append(key_checksum)

return result

}else if(type == ENC_PLAINTEXT){

foreach ch in m:

tmp_ch = ch+r

c = AES(key,tmp_ch)

key_checksum = AES(key,ch)

checksum = MD5(key_checksum,c)

result.append([c,checksum])

}

圖4 Enc耗時分析

2) 解密過程Dec的時間復(fù)雜度

由Dec的偽代碼可知，解密單個密文字符只需要一次AES操作，假設(shè)AES解密需要的時間為c1，則解密n個字符需要c1×n的時間復(fù)雜度，是一個線性時間復(fù)雜度。如圖5實驗結(jié)果，符合理論分析，橫坐標(biāo)為解密字符個數(shù)，單位為100，縱坐標(biāo)為10倍耗時時間。下為Dec的偽代碼:

河口內(nèi)測點含沙量無論大小潮均遠(yuǎn)大于外海測點含沙量，平均含沙量分別為0.07～0.1kg/m3（河口內(nèi)）和0.004～0.04 kg/m3（外海）。

Dec(key,ciphertext)

m = “”

foreach (c,checksum) in ciphertext

tmp_ch = AES(key,c)

//去除固定長度的隨機數(shù)r，得到明文字符

ch = trim(tmp_ch)

m = m + ch

return m

圖5 Dec耗時分析

3) Match過程中的字符匹配時間復(fù)雜度

由以下Match偽代碼可知，對于單個密文字符匹配，只需要進(jìn)行一次MD5操作，假設(shè)MD5操作的時間為c2，則匹配n詞匹配操作需要c2×n的時間復(fù)雜度，是一個線性時間負(fù)責(zé)度。如圖6實驗結(jié)果，符合理論分析。橫坐標(biāo)為字符個數(shù)，單位為100個。下為Match的偽代碼：

//s為密文模式字符,(c,checksum)為密文字符以及校驗

Match(s,(c,checksum))

if checksum == MD5(s,c)

return true

return false

圖6 Match過程字符匹配耗時分析

4) 海量數(shù)據(jù)的性能分析

以通配符的正則匹配規(guī)則為例，如果要在目標(biāo)字符串中，查找是否存在中*國這樣的模式串，則需要的正則表達(dá)式如圖7所示。

圖7 正則表達(dá)式流程圖

在加密狀態(tài)下，則需要把‘中’,‘國’替換成密文狀態(tài)，把明文下的字符相等判斷，替換成密文狀態(tài)下的匹配操作，密文狀態(tài)下進(jìn)行的匹配操作比明文狀態(tài)簡單進(jìn)行相等操作要復(fù)雜耗時一些。對于海量數(shù)據(jù)，假設(shè)正則表達(dá)式所需要的匹配次數(shù)為α次，明文狀態(tài)下正則表達(dá)式所需要的時間為t,則密文狀態(tài)下完成時間需要t+c×α，c為常量。總體來看，密文狀態(tài)下的耗時與明文狀態(tài)下的耗時差與匹配次數(shù)α呈線性關(guān)系。也就是((t+c×α)-t)/α=c，此關(guān)系式得出來是一個常量。

圖8是經(jīng)過10組實際數(shù)據(jù)測試所求得的常量c。

圖8 測量常量c

經(jīng)試驗驗證，密文狀態(tài)下和明文狀態(tài)下的時間關(guān)系如上所述。此處測量的c的大小和實現(xiàn)算法所選擇的加密算法以及正則表達(dá)式規(guī)則有關(guān)系，但c是一個常量，并且關(guān)系式保持不變。

5) 加密后的數(shù)據(jù)大小

這里AES選擇16個字節(jié)為最小加密單位，則單個明文字符會被擴充到16個字節(jié)大小，生成16個字節(jié)的密文字符，同時Checksum也占用了16個字節(jié)，flag占用一個字節(jié),所以一個明文字符被加密后會生成33字節(jié)的密文數(shù)據(jù)。對于如果明文使用utf-8編碼，平均每個字符占用兩個自己，則加密后的數(shù)據(jù)是明文數(shù)據(jù)的16.5倍。

4 SCA的安全性分析

4.1 信任和攻擊模型

外包服務(wù)器是不可信的，惡意的攻擊者或者惡意服務(wù)器管理員很可能在一段時間內(nèi)取得數(shù)據(jù)庫的全部權(quán)限，來盡可能地獲取數(shù)據(jù)。SCA的目標(biāo)是當(dāng)服務(wù)器被入侵之后，盡可能少地泄露數(shù)據(jù)。因此信任和攻擊模型如下：

1) 服務(wù)器是不可信的，惡意的攻擊者或者惡意的管理員可以獲得服務(wù)器的所有權(quán)限，在服務(wù)器被入侵期間，入侵者能夠獲取任何明文和密文，同時還能夠獲取用戶向服務(wù)器發(fā)來的請求以及服務(wù)器返回給用戶的結(jié)果。

2) 用戶和服務(wù)器之間的通信通道是安全的，比如使用了SSL或者IPSec通信協(xié)議。

3) 所有數(shù)據(jù)在服務(wù)器上加密存儲的，并且在服務(wù)器上SCA的任何操作都不進(jìn)行解密。

4.2SCA安全分析

假設(shè)在服務(wù)器被入侵期間，用戶共進(jìn)行了t次查詢，Q1,Q2,…,Qt,服務(wù)器返回了t個結(jié)果S1,S2,…,St(代表匹配數(shù)據(jù)的位置,那么服務(wù)器唯一泄露的數(shù)據(jù)就是S1,S2,…,St這t個位置)。由于在SCA對相同的字符，加密生成不同的結(jié)果，可以抵抗頻率統(tǒng)計攻擊。

定理1 如果SCA所使用的加密算法E是pseudorandompermutation,SCA則只泄露數(shù)據(jù)S1,S2,…,St。

證明SCA對單個明文字符m加密后，包括兩部分內(nèi)容(C,Checksum),一部分是使用密鑰加密后的內(nèi)容C，一部分是校驗數(shù)據(jù)Checksum。構(gòu)造一個SCA模擬器S，對于任意的u∈{1,…,t}，S隨機均等地從{0,1}1選擇Qu和Cu,1為密鑰空間k的長度，那么Checksumu=EQu(Cu),最終S產(chǎn)生(C1,Checksum1),…,(Ct,Checksumt)，它們之間的區(qū)分度和選擇的加密算法E的偽隨機程度保持一致，證畢。

5 結(jié) 語

針對目前還沒有切實有效的在密文狀態(tài)下對正則表達(dá)式支持的方案，提出了能夠支持常用正則表達(dá)式的加密方案SCA。但是SCA的不足之處是加密后，密文體積變?yōu)樵瓉淼?6.5倍左右，對于存儲來說有不小的壓力。

下一步的研究方向為優(yōu)化改進(jìn)SCA，減少密文體積，并且使SCA支持除了正則表達(dá)式之外的更多操作。

[1]SongDX,WagnerP,PerrigP.Practicaltechniquesforsearc-esonEncryptedData[C]//Proceedingsofthe2000IEEESymposiumonSecurityandPrivacy,Berkely,California,USA,2004:44.

[2]BonechD,CrescenzoGD,OstrovskyR,etal.Public-keyen-cryptionwithkeywordsearch[C]//ProceedingsoftheEurocrypt2004,Interlaken,Switzerland,2004:506-522.

[3]WangWC,LiZW,OwensR,etal.Secureandefficientacc-esstooutsourceddata[C]//Proceedingsofthe2009ACMWorkshoponCloudComputingSecurity,Chicago,Illinois,USA,2009:55-66.

[4]HuangRW,GuiXL,YuS,etal.Studyofprivacypreservingframeworkforcloudstorage[J].ComputerScienceandinformationSystems,2011,8(3):801-819.

[5]BellovinSM,CheswickWR.Privacy-enhancedserachesus-ingencryptedbloomfilters[R].TechnicalReport2004/022,IACRePrintCryptographyArchive,2004.

[6]OhtakiY.PraticaldisclosureofserchableencrypteddatawithsupportforBooleanqueries[C]//Proceedingsofthe3rdInternationalConferenceonAvailability,ReliabilityandSecurity(ARES’-2008),Barcelona,Spain,2008:1083-1090.

[7]LiuQ,WangGJ,WuJ.Anefficientprivacypreservingkey-wordsearchschemeincloudcomputing[C]//Proceedingsofthe12thIEEEInternationalConferenceComputationalScienceandEngineering(CSE’09),Vancouver,Canada,2009:715-720.

[8]LiJ,WangQ,WangCetal.Fuzzykeywordsearchoverencry-pteddataincloudcomputing[C]//Proceedingsofthe29thConferenceonComputerCommunications(INFOCOM2010),SanDiego,California,USA,2010:1-5.

[9]HacigümüsH,IyerB,MehrotraS.Efficientexecutionofag-gregationqueriesoverencryptedrelationaldatabases[C]//Procee-dingofthe9thInternationalConferenceDatabaseSystemsforAdvancedApplications(DASFAA2004).JejuIsland,Korea,2004:633-650.

[10] 黃汝維,桂小林,余思,等.云環(huán)境中支持隱私保護(hù)的可計算加密方法[J].計算機學(xué)報,2011,12(34):2392-2402.

[11]YongZhang,LiWeixin,NiuXiamu.Securecipherindexoverencryptedcharacterdataindatabase[C]//ProceedingsofMachineLearningandCybernetics,Kunming,China,2008:1111-1116.

[12]PurushothamaBR,AmberkerBB.EfficientQueryProces-singonOutsourcedEncryptedDatainCloudwithPrivacyPreservation[C]//Proceedingsofthe2012InternationalSymposiumonCloudandServicesComputing(ISCOS),Mangalore,India,2012:88-95.

[13]ZhiqiangYang,ShengZhong,RebeccaNWright.Privacy-PreservingQueriesonEncryptedData[C]//Proceedingsof11thEu-ropeanSymposiumonResearchinComputerSecurity,Hamburg,Germany,2006:479-495.

[14]YousefElmehdwi,BharathKSamanthula,WeiJiang.Securek-NearestNeighborQueryoverEncryptedDatainOutsourcedEnvironments[C]//ProceedingsofIEEE30thInternationalConferenceonDataEngineering(ICDE),Chicago,USA,2014:664-675.

[15] 魏潤琪.基于全同態(tài)加密算法的密文檢索模型的設(shè)計與實現(xiàn)[D].西安:西安電子科技大學(xué),2014.

[16] 段桂華,鞠瑞,王玉斌,等.云計算環(huán)境下的高效密文檢索協(xié)議[J].網(wǎng)絡(luò)信息安全,2013,2013(9):26-29.

[17] 郭璐璐,許春根.云存儲密文檢索方法的研究[J].網(wǎng)絡(luò)信息安全,2013,2013(9):6-9.

[18] 羅文俊,孫志蔚.基于simhash的密文同義詞檢索方法[J].武漢大學(xué)學(xué)報,2014,60(5):459-465.

[19] 宋偉,彭智勇,王騫,等.Mimir:一種基于密文的全文檢索服務(wù)系統(tǒng)[J].計算機學(xué)報,2014,31(5):1170-1183.

[20]GentryC.Fullyhomomorphicencryptionusingideallattices[C]//Proceddingsofthe41rdACMSymposiumonTheoryofComputing(STOC'09),Bethesda,Maryland,USA,2009:169-178.

[21]GentryC.Computingarbitraryfunctionsofencrypteddat-a[J].CommunicationsoftheACM,2010,53(3):97-105.

RESEARCH ON CIPHERTEXT RETRIEVAL METHOD FOR REGULAR EXPRESSION

Li Weijie Hua Baojian Li Xi

(SchoolofSoftwareEngineering,UniversityofScienceandTechnologyofChina,Hefei230051,Anhui,China)(SuzhouInstituteforAdvancedStudy,UniversityofScienceandTechnologyofChina,Suzhou215123,Jiangsu,China)

With the development of cloud computing, more and more sensitive data is stored in remote servers. In order to protect sensitive data from revealing, sensitive data is encrypted . Because data is encrypted, many operations on plaintext is not effective for ciphertext. Especially in the condition of in-ciphertext, the problem of how to handle ciphertext using regular expressions is not solved. After studying the use of regular expressions in ciphertext, a method called SCA(Searchable Crypt Algorithm) is proposed, which supports usual regular expressions such as ab*,bc?,a+,ab{m,n}.

Ciphertext retrieval Regular expression Encryption Cloud computing

2016-01-02。李威杰，碩士，主研領(lǐng)域：數(shù)據(jù)加密。華保健，講師。李曦，副教授。

TP309

A

10.3969/j.issn.1000-386x.2017.03.055