第八讲-密文检索技术

11/7/202312023/11/7北京电子科技学院信息安全系第八讲密文数据库检索技术李子臣博士教授密码与信息安全新技术专题讲座111/7/20232一、密文数据库无限量的存储资源为什么至今并未得到广泛应用？云计算11/7/20233原因：用户云端攻击者访问控制不再起作用11/7/20234解决方案：密文存储用户云端攻击者数据加密是最简单、有效的做法11/7/20235问题：密文数据库如何检索？用户云端攻击者11/7/20236用户云端攻击者如果不考虑效率，将密文传回用户，再解密，是最安全的做法。问题：密文数据库如何检索？11/7/20237传统的方法是首先对加密数据进行解密，然后对解密数据进行检索。这种方法是不安全也是不高效。用户云端攻击者解密检索11/7/20238二、密文数据库检索策略1.不用解密而直接操作密文数据2.一种是分步查询11/7/202391.直接操作密文数据数据库的秘密同态技术和数据库的序加密等。秘密同态技术对加密算法提出了一定的约束条件，使满足密文同态的加密算法的应用不具有普遍性。数据库的序加密方法主要采用序列密码算法，序列密码算法采用异或的运算方法，密钥序列不能重复，如果对不同记录采取不同的密钥种子，则密钥管理难度太大，如果对不同记录采取相同的密钥种子，则会存在不少相同或相近的密文字段值，容易受到统计攻击和已知明文攻击。11/7/202310基于同态加密技术检索查询技术保持数值顺序的数据库加密方法OPES(OrderPreservingEncryption)数据库分区11/7/2023112.分步检索查询一般需要进行查询分解，先对密文数据进行范围查询，缩小解密范围，快速解密后再执行精确查询，查询策略的核心难点在于需要尽量提高对密文数据库查询的准确率，缩小返回客户端的密文数据的范围。11/7/202312数值型分步检索查询数据库分区范围检索用户云端在数据库密文检索时，通过关键词的数值大小判断关键词落在哪一个分区，进而根据数值范围确定数据库中哪些记录可能符合检索条件。

例：如对于检索条件Y＞450，可以判定分区1、分区4的所有记录是满足检索条件的，而通过解密分区5的所有记录，可以精确判断剩余满足条件的数据库记录。11/7/202313仅通过值域分区的方式建立数据库值索引容易造成数据库信息泄漏，因此，数据库分区的方式通常会采用HASH技术，对数值进行HASH后，根据HASH值再进行分区，进而避免信息泄漏的问题。11/7/20231411/7/202315三、密文数据库索引机制1.密文数据的直接索引2.地址加密的密文索引3.动态安全的密文索引11/7/2023161.密文数据的直接索引序号关键词地址1Key1Add12Key2Add2………序号地址密文1Add1C12Add2C2………11/7/202317对密文数据的直接索引方法的主要缺点是密文索引树中的地址数据是以明文方式存放的，攻击者可将各结点的密文数据按其对应的明文进行排序，并利用部分明、密文对应的统计规律获得可用于破译的关键信息。11/7/2023182.地址加密的密文索引序号关键词加密地址1Key1C(Add1)2Key2C(Add2)………序号地址密文1Add1C12Add2C2………11/7/2023192.地址加密的密文索引地址加密的密文索引方法可以解决直接密文索引的缺陷，但如果攻击者能同时动态跟踪数据库的访问过程，则有可能找出密文与密文地址的对应关系，得到可乘之机。11/7/2023203.动态安全的密文索引动态安全的密文索引方法虽然可以有效地对抗攻击者对密文数据和索引的对应关系进行动态追踪分析，但实现起来却非常复杂，需要采用双地址索引，每次访问索引之后，都访问2个密文数据，其中一个密文数据主要是为了产生混淆效果，敌手通过动态分析检索过程和猜测，能完全知道密文数据的排序关系的概率大大降低，从而使密文索引的安全性有所提高。11/7/202321客户端密文特征云端客户端特征值云端检索词比对匹配结果存储过程检索过程四、基于特征精确检索方案明文密文特征值（完整）客户端

云存储服务端密文特征值（完整）用户端将密文和特征值分批传给云存储服务端密文特征值（完整）密文特征值（完整）11/7/202323客户端

检索词特征值匹配结果索引特征值

密

文比对11/7/202324基于Hash的密文精确检索方案利用Hash函数建立索引，在加密前的信息后面链接一个随机数保证相同明文在加密后产生不同的密文，提高了安全性。在数据库中每一个记录有很多的字段，选取适合精确检索建立索引的字段建立索引，并将建立的索引存到对应的字段中。在检索时根据检索词在对应的字段中检索，如果匹配成功，检索出对应的整个记录。11/7/202325建立索引

11/7/202326检索过程

11/7/202327五、基于Hash的密文模糊检索方案利用Hash函数建立模糊检索的索引，通过模糊匹配实现对密文数据的模糊检索

11/7/202328例001100001111011000110000特征值密文…………0011000020FF@RSE11010011RE45KY%G…………11110110984REFoT………001100001111011020FF@RSE984REFoT用户端解密检索结果11/7/202329建立索引

11/7/202330密文检索11/7/202331安全分析

1.特征值特征值的提取基于带密钥的摘要算法。因此，根据特征值并不能推断出任何明文信息，同时，也保证了：只有持有密钥的人，才可以进行密文检索。

2.云端安全性在整个操作过程中，云端就像是个盲人，在云端没有任何的明文出现。云端负责存储、检索、提取数据，但是却看不到任何明文。11/7/202332六、密文检索发展方向密文数据库的检索是一项复杂的工作，高效、安全的密文数据库检索更是数据库安全技术研究的热点．在今后的工作中我们将进一步研究检索算法，以使之能适应诸如模糊查询、多表查询、复合条件查询等各种复杂查询模式的密文数据库检索机制。CryptDB:

基于密文形式可查询的密文数据库11/7/202333ApplicationDBServerSQLUser1User2User3数据库中的隐私数据泄露例如,SonyPlaystationNetwork被黑客攻击泄露了7700万用户的个人信息档案系统管理员威胁1:数据库服务器的被动攻击

威胁2:所有服务器上的任何攻击黑客11/7/202334CryptDB概述目标:保护隐私数据对加密的数据执行SQL查询语句使用细粒度的keys;把基于访问控制的用户密码和这些keys绑定ApplicationDBServerSQLThreat1:passiveDBserverattacksThreat2:anyattacksonallserversonencrypteddataUser1User2User311/7/202335首次实现对密文数据执行大部分的SQL查询语句

将数据库对系统管理员、外包数据库不可见（或：使得DBA或黑客无法通过DBMS获取原数据。）即使当服务器都被攻陷以后，在攻击期间，也能保护未登陆用户的数据安全

降低了数据的泄漏量适度的开销:大约只增加26%的开销（

TPC-C）

主要工作不更改DBMS(例如,Postgres,MySQL)11/7/202336col1/rankcol2/nametable1/empSELECT*FROMempWHEREsalary=100x934bc1x5a8c34x5a8c34x84a21cSELECT*FROMtable1WHEREcol3=x5a8c34Proxy?x5a8c34x5a8c34?x5a8c34x5a8c34x4be219x95c623x2ea887x17cea7col3/salaryApplication60100800100随机加密确定性加密11/7/202337col1/rankcol2/nametable1(emp)x934bc1x5a8c34x5a8c34x84a21cx638e54x638e54x922eb4x1eab81SELECT*FROMtable1WHEREcol3≥x638e54Proxyx638e54x922eb4x638e54col3/salaryApplication60100800100确定性加密SELECT*FROMempWHEREsalary

≥

100开放性加密11/7/202338使用

SQL-aware加密方案集

两个关键技术大部分的SQL语句使用有限的标准谓词集

根据SQL语句所包含的数据操作类型，调整加密方案11/7/202339加密方案e.g.,=,!=,IN,COUNT,GROUPBY,DISTINCTSchemeRND

HOMDET

SEARCH

JOINOPEFunctionnone+,*equalityjoinwordsearchorderConstructionAESinCBCAESinCMCPaillierournewschemeSongetal.,‘00Boldyrevaetal.’09firstimplementatione.g.,>,<,ORDERBY,SORT,MAX,MINrestrictedILIKEHighest安全性seepapere.g.,sum11/7/202340如何去加密每一个数据项?

所需加密方案取决于查询

事先未知查询语句Leaksorder!rankALL?col1-RNDcol1-HOMcol1-SEARCHcol1-DETcol1-JOINcol1-OPE‘CEO’‘worker’11/7/202341intvalueHOMOnionAdd洋葱加密方案valueJOINDETRNDOnionEqualityOnionSearch

同一加密层中同一列的所有数据项使用相同的密钥

加密初始化的时候，采用安全度最高的加密方案OReachvaluevalueOPE-JOINOPERNDOnionOrdertextvalueSEARCH11/7/202342示例:SELECT*FROMempWHERErank=‘CEO’;emp:ranknamesalary‘CEO’‘worker’‘CEO’JOINDETRNDOnionEqualitycol1-OnionEqcol1-OnionOrdercol1-OnionSearchcol2-OnionEqtable1:………RNDRNDSEARCHRNDSEARCHRNDRNDRND11/7/202343例子

UPDATEtable1SETcol1-OnionEq=

Decrypt_RND(key,col1-OnionEq);‘CEO’JOINDETRNDSELECT*FROMtable1WHEREcol1-OnionEq=xda5c0407;DETOnionEqualityRNDRNDSELECT*FROMempWHERErank=‘CEO’;DETDETcol1-OnionEqcol1-OnionOrdercol1-OnionSearchcol2-OnionEqtable1………RNDRNDSEARCHRNDSEARCHRND11/7/202344挑战：数据共享在加密数据上的过程查询msg_idsenderreceivermsg_idmessage5“secretmessage”5AliceBobSPEAKS_FORmsg_idSPEAKS_FORmsg_idENC_FORmsg_id如何从SQL语句层级中捕获应用程序的访问控制策略？Annotations将用户口令与Key绑定Km5Km5Km5Howtoenforceaccesscontrolcryptographically?Alice-passBob-pass11/7/202345评估Cryptdb是否支持真实的查询/应用程序？

加密后，数据安全性如何?使用后，性能如何?11/7/202346不支持的查询语句一些更复杂的运算,比如,trigonometry操作需要结合互补相容的加密方案例如,T1.a+T1.b>T2.c

扩展:拆分SQL语句,