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

李威杰 華保健 李 曦

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

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

李威杰 華保健 李 曦

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

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

密文檢索 正則表達式 加密 云計算

0 引 言

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

1 相關工作

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

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

2 支持正則表達式的加密方案SCA

2.1SCA的定義

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

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

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

3) 密文匹配算法Match，實現將密文模式串中對應的字符和密文目的串中的字符準確匹配。

2.2SCA的詳細設計

1) 加密算法Enc的設計

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

圖1 加密算法Enc的設計

2) 解密算法Dec的設計

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

圖2 解密算法Dec的設計

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

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

圖3 密文匹配算法Match的設計

2.3SCA對常用正則表達式的支持

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

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

對于ab{3,10}這種數字，對應的checksum則為數字本身，比如3對應的checksum為0x0003,10對應的checksum為0x000a。

舉個例子如下：

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

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

3 SCA的性能分析

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

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

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

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

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的時間復雜度

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

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

Dec(key,ciphertext)

m = “”

foreach (c,checksum) in ciphertext

tmp_ch = AES(key,c)

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

ch = trim(tmp_ch)

m = m + ch

return m

圖5 Dec耗時分析

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

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

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

Match(s,(c,checksum))

if checksum == MD5(s,c)

return true

return false

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

4) 海量數據的性能分析

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

圖7 正則表達式流程圖

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

圖8是經過10組實際數據測試所求得的常量c。

圖8 測量常量c

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

5) 加密后的數據大小

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

4 SCA的安全性分析

4.1 信任和攻擊模型

外包服務器是不可信的，惡意的攻擊者或者惡意服務器管理員很可能在一段時間內取得數據庫的全部權限，來盡可能地獲取數據。SCA的目標是當服務器被入侵之后，盡可能少地泄露數據。因此信任和攻擊模型如下：

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

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

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

4.2SCA安全分析

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

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

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

5 結 語

針對目前還沒有切實有效的在密文狀態下對正則表達式支持的方案，提出了能夠支持常用正則表達式的加密方案SCA。但是SCA的不足之處是加密后，密文體積變為原來的16.5倍左右，對于存儲來說有不小的壓力。

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

[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] 黃汝維,桂小林,余思,等.云環境中支持隱私保護的可計算加密方法[J].計算機學報,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] 魏潤琪.基于全同態加密算法的密文檢索模型的設計與實現[D].西安:西安電子科技大學,2014.

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

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

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

[19] 宋偉,彭智勇,王騫,等.Mimir:一種基于密文的全文檢索服務系統[J].計算機學報,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。李威杰，碩士，主研領域：數據加密。華保健，講師。李曦，副教授。

TP309

A

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