支持正则表达式的密文检索方案的研究

李威杰 华保健 李 曦

(中国科学技术大学软件学院 安徽 合肥 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