1、6/5/202212022-6-5北京电子科技学院信息安全系第八讲第八讲 密文数据库检索技术密文数据库检索技术李子臣李子臣 博士博士 教授教授密码与信息安全新技术专题讲座密码与信息安全新技术专题讲座16/5/20222一、密文数据库一、密文数据库无限量的存储资源无限量的存储资源为什么至今并未为什么至今并未得到广泛应用？得到广泛应用？云计算云计算6/5/20223原因：原因：用户用户云端云端攻击者攻击者访问控制不访问控制不再起作用再起作用6/5/20224解决方案：密文存储解决方案：密文存储用户用户云端云端攻击者攻击者数据加密是最简数据加密是最简单、有效的做法单、有效的做法6/5/20225问题
2、：密文数据库如何检索？问题：密文数据库如何检索？用户用户云端云端攻击者攻击者6/5/20226用户用户云端云端攻击者攻击者如果不考虑效率，将密文传如果不考虑效率，将密文传回用户，再解密，是最安全回用户，再解密，是最安全的做法。的做法。问题：密文数据库如何检索？问题：密文数据库如何检索？6/5/20227n传统的方法是首先对加密数据进行解密，然传统的方法是首先对加密数据进行解密，然后对解密数据进行检索。这种方法是不安全后对解密数据进行检索。这种方法是不安全也是不高效。也是不高效。用户用户云端云端攻击者攻击者解密解密检索检索6/5/20228二、密文数据库检索策略二、密文数据库检索策略1.不用解密
3、而直接操作密文数据不用解密而直接操作密文数据2.一种是分步查询一种是分步查询6/5/202291.直接操作密文数据直接操作密文数据n 数据库的秘密同态技术和数据库的序加密等。数据库的秘密同态技术和数据库的序加密等。n 秘密同态技术对加密算法提出了一定的约束条秘密同态技术对加密算法提出了一定的约束条件，使满足密文同态的加密算法的应用不具有件，使满足密文同态的加密算法的应用不具有普遍性。普遍性。n 数据库的序加密方法主要采用序列密码算法，数据库的序加密方法主要采用序列密码算法，序列密码算法采用异或的运算方法，密钥序列序列密码算法采用异或的运算方法，密钥序列不能重复，如果对不同记录采取不同的密钥种不
4、能重复，如果对不同记录采取不同的密钥种子，则密钥管理难度太大，如果对不同记录采子，则密钥管理难度太大，如果对不同记录采取相同的密钥种子，则会存在不少相同或相近取相同的密钥种子，则会存在不少相同或相近的密文字段值，容易受到统计攻击和已知明文的密文字段值，容易受到统计攻击和已知明文攻击。攻击。6/5/202210保持数值顺序的数据库加密方法保持数值顺序的数据库加密方法OPES(Order Preserving Encryption)ijijppcc数据库分区数据库分区6/5/2022112.分步检索查询分步检索查询n一般需要进行查询分解，先对密文数一般需要进行查询分解，先对密文数据进行范围查询，缩
5、小解密范围，快据进行范围查询，缩小解密范围，快速解密后再执行精确查询，查询策略速解密后再执行精确查询，查询策略的核心难点在于需要尽量提高对密文的核心难点在于需要尽量提高对密文数据库查询的准确率，缩小返回客户数据库查询的准确率，缩小返回客户端的密文数据的范围。端的密文数据的范围。6/5/202212数据库分区数据库分区范围检索范围检索用户用户云端云端n在数据库密文检索时，通过关键词的数值大在数据库密文检索时，通过关键词的数值大小判断关键词落在哪一个分区，进而根据数小判断关键词落在哪一个分区，进而根据数值范围确定数据库中哪些记录可能符合检索值范围确定数据库中哪些记录可能符合检索条件。条件。 例：如
6、对于检索条件例：如对于检索条件Y Y450450，可以判定，可以判定分区分区1 1、分区、分区4 4的所有记录是满足检索条件的的所有记录是满足检索条件的，而通过解密分区，而通过解密分区5 5的所有记录，可以精确的所有记录，可以精确判断剩余满足条件的数据库记录。判断剩余满足条件的数据库记录。6/5/202213n仅通过值域分区的方式建立数据库值仅通过值域分区的方式建立数据库值索引容易造成数据库信息泄漏，因此索引容易造成数据库信息泄漏，因此，数据库分区的方式通常会采用，数据库分区的方式通常会采用HASHHASH技术，对数值进行技术，对数值进行HASHHASH后，根据后，根据HASHHASH值再进行
7、分区，进而避免信息泄漏的值再进行分区，进而避免信息泄漏的问题。问题。6/5/2022146/5/202215三、密文数据库索引机制三、密文数据库索引机制1.密文数据的直接索引密文数据的直接索引2.地址加密的密文索引地址加密的密文索引3.动态安全的密文索引动态安全的密文索引6/5/2022161.密文数据的直接索引密文数据的直接索引序号序号关键词关键词地址地址1Key1Add12Key2Add2序号序号地址地址密文密文1Add1C12Add2C26/5/202217n对密文数据的直接索引方法的主要缺点对密文数据的直接索引方法的主要缺点是密文索引树中的地址数据是以明文方是密文索引树中的地址数据是以
8、明文方式存放的，攻击者可将各结点的密文数式存放的，攻击者可将各结点的密文数据按其对应的明文进行排序，并利用部据按其对应的明文进行排序，并利用部分明、密文对应的统计规律获得可用于分明、密文对应的统计规律获得可用于破译的关键信息。破译的关键信息。6/5/2022182.地址加密的密文索引地址加密的密文索引序号序号关键词关键词加密地址加密地址1Key1C(Add1)2Key2C(Add2)序号序号地址地址密文密文1Add1C12Add2C26/5/2022192.地址加密的密文索引地址加密的密文索引n地址加密的密文索引方法可以解决直接地址加密的密文索引方法可以解决直接密文索引的缺陷，但如果攻击者能同
9、时密文索引的缺陷，但如果攻击者能同时动态跟踪数据库的访问过程，则有可能动态跟踪数据库的访问过程，则有可能找出密文与密文地址的对应关系，得到找出密文与密文地址的对应关系，得到可乘之机。可乘之机。6/5/2022203.动态安全的密文索引动态安全的密文索引n动态安全的密文索引方法虽然可以有效地对动态安全的密文索引方法虽然可以有效地对抗攻击者对密文数据和索引的对应关系进行抗攻击者对密文数据和索引的对应关系进行动态追踪分析，但实现起来却非常复杂，需动态追踪分析，但实现起来却非常复杂，需要采用双地址索引，每次访问索引之后，都要采用双地址索引，每次访问索引之后，都访问访问2 2个密文数据，其中一个密文数据
10、主要个密文数据，其中一个密文数据主要是为了产生混淆效果，敌手通过动态分析检是为了产生混淆效果，敌手通过动态分析检索过程和猜测，能完全知道密文数据的排序索过程和猜测，能完全知道密文数据的排序关系的概率大大降低，从而使密文索引的安关系的概率大大降低，从而使密文索引的安全性有所提高。全性有所提高。6/5/202221客户端客户端密文特征密文特征云端云端客户端客户端特征值特征值云端云端检索词检索词比对比对匹配结果匹配结果存储过程检索过程四、基于特征精确检索方案四、基于特征精确检索方案明文明文密文密文特征值特征值（完整）（完整）客户端客户端 云存储服务端云存储服务端密文密文特征值特征值（完整）（完整）用
11、户端将密文和特征值用户端将密文和特征值分批分批传给云存储服务端传给云存储服务端密文密文特征值特征值（完整）（完整）密文密文特征值特征值（完整）（完整）6/5/202223 检索词特征值检索词特征值匹配结果匹配结果索索引引特特征征值值 密密 文文比比对对6/5/202224基于基于HashHash的密文精确检索方案的密文精确检索方案n 利用利用HashHash函数建立索引，在加密前的信息后面链函数建立索引，在加密前的信息后面链接一个随机数保证相同明文在加密后产生不同的接一个随机数保证相同明文在加密后产生不同的密文，提高了安全性。密文，提高了安全性。n 在数据库中每一个记录有很多的字段，选取适合在
12、数据库中每一个记录有很多的字段，选取适合精确检索建立索引的字段建立索引，并将建立的精确检索建立索引的字段建立索引，并将建立的索引存到对应的字段中。索引存到对应的字段中。n 在检索时根据检索词在对应的字段中检索，如果在检索时根据检索词在对应的字段中检索，如果匹配成功，检索出对应的整个记录。匹配成功，检索出对应的整个记录。6/5/202225建立索引 6/5/202226检索过程 6/5/202227五、基于五、基于HashHash的密文模糊检索方案的密文模糊检索方案n利用Hash函数建立模糊检索的索引，通过模糊匹配实现对密文数据的模糊检索 6/5/202228001100001111011000
13、110000特征值特征值密文密文0011000020FFRSE11010011RE45KY%G11110110984REFoT001100001111011020FFRSE984REFoT6/5/202229建立索引 6/5/202230密文检索6/5/202231 1. 1. 特征值特征值 特征值的提取基于特征值的提取基于带密钥的摘要算法带密钥的摘要算法。因此，。因此，根据特征值并不能推断出任何明文信息，同时，也保根据特征值并不能推断出任何明文信息，同时，也保证了：只有持有密钥的人，才可以进行密文检索。证了：只有持有密钥的人，才可以进行密文检索。 2. 2. 云端安全性云端安全性 在整个操作
14、过程中，云端就像是个盲人，在在整个操作过程中，云端就像是个盲人，在云端没有任何的明文出现。云端负责存储、检索、提云端没有任何的明文出现。云端负责存储、检索、提取数据，但是却看不到任何明文。取数据，但是却看不到任何明文。6/5/202232六、密文检索发展方向六、密文检索发展方向n密文数据库的检索是一项复杂的工作，密文数据库的检索是一项复杂的工作，高效、安全的密文数据库检索更是数据高效、安全的密文数据库检索更是数据库安全技术研究的热点库安全技术研究的热点n在今后的工作中我们将进一步研究检索在今后的工作中我们将进一步研究检索算法，以使之能适应诸如模糊查询、多算法，以使之能适应诸如模糊查询、多表查询
15、、复合条件查询等各种复杂查询表查询、复合条件查询等各种复杂查询模式的密文数据库检索机制。模式的密文数据库检索机制。6/5/202233ApplicationApplicationDB ServerDB ServerSQLSQLUser 1User 1User 2User 2User 3User 3数据库中的隐私数据泄露数据库中的隐私数据泄露例如例如, Sony Playstation Network被黑客攻击泄露了被黑客攻击泄露了7700万用户的个人信息档案万用户的个人信息档案系统管理员系统管理员威胁威胁1: 数据库服数据库服务器的被动攻击务器的被动攻击 威胁威胁2: 所有服务器上的任何攻击所
16、有服务器上的任何攻击黑客黑客6/5/202234CryptDB 概述目标目标: 保护隐私数据保护隐私数据1.对加密的数据执行对加密的数据执行SQL查询语句查询语句2.使用细粒度的使用细粒度的keys;把基于访问控制的用户密码和这些把基于访问控制的用户密码和这些keys绑定绑定ApplicationApplicationDB ServerDB ServerSQLSQLThreat 1: passive DB Threat 1: passive DB server attacksserver attacksThreat 2: any attacks on all serversThreat 2:
17、any attacks on all serverson encrypted dataon encrypted dataUser 1User 1User 2User 2User 3User 36/5/2022351.首次实现对密文数据执行大部分的首次实现对密文数据执行大部分的SQL查询语句查询语句 将数据库对系统管理员、外包数据库不可见（或：将数据库对系统管理员、外包数据库不可见（或：使得使得DBADBA或黑客无法通过或黑客无法通过DBMSDBMS获取原数据。）获取原数据。）2.即使当服务器都被攻陷以后，在攻击期间，也能保护即使当服务器都被攻陷以后，在攻击期间，也能保护未登陆用户的数据安全未登
18、陆用户的数据安全 降低了数据的泄漏量降低了数据的泄漏量3.适度的开销适度的开销: 大约只增加大约只增加26%的开销（的开销（ TPC-C） 主要工作4.不更改不更改DBMS(例如例如, Postgres, MySQL)6/5/202236col1/rankcol1/rank col2/namecol2/nametable1/emptable1/empSELECT * FROM emp WHERE salary = 100 x934bc1x5a8c34x5a8c34x84a21cSELECT * FROM table1 WHERE col3 = x5a8c34ProxyProxy? ?x5a8c
19、34x5a8c34? ?x5a8c34x5a8c34x4be219x4be219x95c623x95c623x2ea887x2ea887x17cea7x17cea7col3/salarycol3/salaryApplicationApplication6060100100800800100100随机加密随机加密确定性加密确定性加密6/5/202237col1/rankcol1/rankcol2/namecol2/nametable1 (emp)table1 (emp)x934bc1x5a8c34x5a8c34x84a21cx638e54x638e54x922eb4x1eab81SELECT *
20、 FROM table1 WHERE col3 x638e54ProxyProxyx638e54x922eb4x638e54col3/salarycol3/salaryApplicationApplication6060100100800800100100确定性加密确定性加密SELECT * FROM emp WHERE salary 100开放性加密开放性加密6/5/2022381.使用 SQL-aware 加密方案集 两个关键技术两个关键技术大部分的SQL语句使用有限的标准谓词集 2. 根据SQL语句所包含的数据操作类型，调整语句所包含的数据操作类型，调整加密方案加密方案6/5/20223
21、9加密方案e.g., =, !=, IN, e.g., =, !=, IN, COUNT, GROUP BY, COUNT, GROUP BY, DISTINCT DISTINCT Scheme RND HOM DET SEARCH JOINOPEFunctionnone+, *equalityjoinword searchorderConstructionAES in CBCAES in CMCPaillierour new scheme Song et al.,00Boldyreva et al.09first first implementationimplementatione.g.,
22、 , , T2.c 扩展: 拆分SQL语句, 预计算列, 或者添加新的加密方案6/5/202247性能表现DB server DB server 吞吐量吞吐量CryptDB CryptDB ProxyProxyEncrypted Encrypted databasedatabaseApplication Application 1 1CryptDBCryptDB: :Plain Plain databasedatabaseApplication Application 1 1MySQL:MySQL:CryptDB CryptDB ProxyProxyApplication Applicatio
23、n 2 2Application Application 2 2LatencyLatency硬件: 2.4 GHz Intel Xeon E5620 8 cores, 12 GB RAM6/5/202248TPC-C 测评Throughput Throughput loss 26%loss 26%延时延时(ms/query): 0.10 MySQL vs. 0.72 CryptDB6/5/202249加密方案全同态加密(starting with Gentry10)在加密数据上查询 (e.g., Song et al.,00)系统建议 (e.g., Hacigumus et al.,02)更低的安全程度, 可重写的DBMS, 处理客户端完整的查询(e.g., Nguyen et al.,07, Sion05)相关工作相关工作6/5/2022501. 首个能在加密的数据上运行大多数的标准查询语句的实用性DBMS2. 即使当所有的服务器都被攻陷之后，也能保护在受攻击期间保护未登陆用户的数据安全3. 适度的开销且不改变DBMSCryptDB6/5/202251
