第八講 密文檢索技術(shù)

1、5/26/202212022-5-26北京電子科技學(xué)院信息安全系第八講第八講 密文數(shù)據(jù)庫檢索技術(shù)密文數(shù)據(jù)庫檢索技術(shù)李子臣李子臣 博士博士 教授教授密碼與信息安全新技術(shù)專題講座密碼與信息安全新技術(shù)專題講座15/26/20222一、密文數(shù)據(jù)庫一、密文數(shù)據(jù)庫無限量的存儲(chǔ)資源無限量的存儲(chǔ)資源為什么至今并未為什么至今并未得到廣泛應(yīng)用？得到廣泛應(yīng)用？云計(jì)算云計(jì)算5/26/20223原因：原因：用戶用戶云端云端攻擊者攻擊者訪問控制不訪問控制不再起作用再起作用5/26/20224解決方案：密文存儲(chǔ)解決方案：密文存儲(chǔ)用戶用戶云端云端攻擊者攻擊者數(shù)據(jù)加密是最簡(jiǎn)數(shù)據(jù)加密是最簡(jiǎn)單、有效的做法單、有效的做法5/26/2

2、0225問題：密文數(shù)據(jù)庫如何檢索？問題：密文數(shù)據(jù)庫如何檢索？用戶用戶云端云端攻擊者攻擊者5/26/20226用戶用戶云端云端攻擊者攻擊者如果不考慮效率，將密文傳如果不考慮效率，將密文傳回用戶，再解密，是最安全回用戶，再解密，是最安全的做法。的做法。問題：密文數(shù)據(jù)庫如何檢索？問題：密文數(shù)據(jù)庫如何檢索？5/26/20227n傳統(tǒng)的方法是首先對(duì)加密數(shù)據(jù)進(jìn)行解密，然傳統(tǒng)的方法是首先對(duì)加密數(shù)據(jù)進(jìn)行解密，然后對(duì)解密數(shù)據(jù)進(jìn)行檢索。這種方法是不安全后對(duì)解密數(shù)據(jù)進(jìn)行檢索。這種方法是不安全也是不高效。也是不高效。用戶用戶云端云端攻擊者攻擊者解密解密檢索檢索5/26/20228二、密文數(shù)據(jù)庫檢索策略二、密文數(shù)據(jù)庫檢

3、索策略1.不用解密而直接操作密文數(shù)據(jù)不用解密而直接操作密文數(shù)據(jù)2.一種是分步查詢一種是分步查詢5/26/202291.直接操作密文數(shù)據(jù)直接操作密文數(shù)據(jù)n 數(shù)據(jù)庫的秘密同態(tài)技術(shù)和數(shù)據(jù)庫的序加密等。數(shù)據(jù)庫的秘密同態(tài)技術(shù)和數(shù)據(jù)庫的序加密等。n 秘密同態(tài)技術(shù)對(duì)加密算法提出了一定的約束條秘密同態(tài)技術(shù)對(duì)加密算法提出了一定的約束條件，使?jié)M足密文同態(tài)的加密算法的應(yīng)用不具有件，使?jié)M足密文同態(tài)的加密算法的應(yīng)用不具有普遍性。普遍性。n 數(shù)據(jù)庫的序加密方法主要采用序列密碼算法，數(shù)據(jù)庫的序加密方法主要采用序列密碼算法，序列密碼算法采用異或的運(yùn)算方法，密鑰序列序列密碼算法采用異或的運(yùn)算方法，密鑰序列不能重復(fù)，如果對(duì)不同記

4、錄采取不同的密鑰種不能重復(fù)，如果對(duì)不同記錄采取不同的密鑰種子，則密鑰管理難度太大，如果對(duì)不同記錄采子，則密鑰管理難度太大，如果對(duì)不同記錄采取相同的密鑰種子，則會(huì)存在不少相同或相近取相同的密鑰種子，則會(huì)存在不少相同或相近的密文字段值，容易受到統(tǒng)計(jì)攻擊和已知明文的密文字段值，容易受到統(tǒng)計(jì)攻擊和已知明文攻擊。攻擊。5/26/202210保持?jǐn)?shù)值順序的數(shù)據(jù)庫加密方法保持?jǐn)?shù)值順序的數(shù)據(jù)庫加密方法OPES(Order Preserving Encryption)ijijppcc數(shù)據(jù)庫分區(qū)數(shù)據(jù)庫分區(qū)5/26/2022112.分步檢索查詢分步檢索查詢n一般需要進(jìn)行查詢分解，先對(duì)密文數(shù)一般需要進(jìn)行查詢分解，先對(duì)

5、密文數(shù)據(jù)進(jìn)行范圍查詢，縮小解密范圍，快據(jù)進(jìn)行范圍查詢，縮小解密范圍，快速解密后再執(zhí)行精確查詢，查詢策略速解密后再執(zhí)行精確查詢，查詢策略的核心難點(diǎn)在于需要盡量提高對(duì)密文的核心難點(diǎn)在于需要盡量提高對(duì)密文數(shù)據(jù)庫查詢的準(zhǔn)確率，縮小返回客戶數(shù)據(jù)庫查詢的準(zhǔn)確率，縮小返回客戶端的密文數(shù)據(jù)的范圍。端的密文數(shù)據(jù)的范圍。5/26/202212數(shù)據(jù)庫分區(qū)數(shù)據(jù)庫分區(qū)范圍檢索范圍檢索用戶用戶云端云端n在數(shù)據(jù)庫密文檢索時(shí)，通過關(guān)鍵詞的數(shù)值大在數(shù)據(jù)庫密文檢索時(shí)，通過關(guān)鍵詞的數(shù)值大小判斷關(guān)鍵詞落在哪一個(gè)分區(qū)，進(jìn)而根據(jù)數(shù)小判斷關(guān)鍵詞落在哪一個(gè)分區(qū)，進(jìn)而根據(jù)數(shù)值范圍確定數(shù)據(jù)庫中哪些記錄可能符合檢索值范圍確定數(shù)據(jù)庫中哪些記錄可能符

6、合檢索條件。條件。 例：如對(duì)于檢索條件例：如對(duì)于檢索條件Y Y450450，可以判定，可以判定分區(qū)分區(qū)1 1、分區(qū)、分區(qū)4 4的所有記錄是滿足檢索條件的的所有記錄是滿足檢索條件的，而通過解密分區(qū)，而通過解密分區(qū)5 5的所有記錄，可以精確的所有記錄，可以精確判斷剩余滿足條件的數(shù)據(jù)庫記錄。判斷剩余滿足條件的數(shù)據(jù)庫記錄。5/26/202213n僅通過值域分區(qū)的方式建立數(shù)據(jù)庫值僅通過值域分區(qū)的方式建立數(shù)據(jù)庫值索引容易造成數(shù)據(jù)庫信息泄漏，因此索引容易造成數(shù)據(jù)庫信息泄漏，因此，數(shù)據(jù)庫分區(qū)的方式通常會(huì)采用，數(shù)據(jù)庫分區(qū)的方式通常會(huì)采用HASHHASH技術(shù)，對(duì)數(shù)值進(jìn)行技術(shù)，對(duì)數(shù)值進(jìn)行HASHHASH后，根據(jù)后，

7、根據(jù)HASHHASH值再進(jìn)行分區(qū)，進(jìn)而避免信息泄漏的值再進(jìn)行分區(qū)，進(jìn)而避免信息泄漏的問題。問題。5/26/2022145/26/202215三、密文數(shù)據(jù)庫索引機(jī)制三、密文數(shù)據(jù)庫索引機(jī)制1.密文數(shù)據(jù)的直接索引密文數(shù)據(jù)的直接索引2.地址加密的密文索引地址加密的密文索引3.動(dòng)態(tài)安全的密文索引動(dòng)態(tài)安全的密文索引5/26/2022161.密文數(shù)據(jù)的直接索引密文數(shù)據(jù)的直接索引序號(hào)序號(hào)關(guān)鍵詞關(guān)鍵詞地址地址1Key1Add12Key2Add2序號(hào)序號(hào)地址地址密文密文1Add1C12Add2C25/26/202217n對(duì)密文數(shù)據(jù)的直接索引方法的主要缺點(diǎn)對(duì)密文數(shù)據(jù)的直接索引方法的主要缺點(diǎn)是密文索引樹中的地址數(shù)據(jù)是

8、以明文方是密文索引樹中的地址數(shù)據(jù)是以明文方式存放的，攻擊者可將各結(jié)點(diǎn)的密文數(shù)式存放的，攻擊者可將各結(jié)點(diǎn)的密文數(shù)據(jù)按其對(duì)應(yīng)的明文進(jìn)行排序，并利用部據(jù)按其對(duì)應(yīng)的明文進(jìn)行排序，并利用部分明、密文對(duì)應(yīng)的統(tǒng)計(jì)規(guī)律獲得可用于分明、密文對(duì)應(yīng)的統(tǒng)計(jì)規(guī)律獲得可用于破譯的關(guān)鍵信息。破譯的關(guān)鍵信息。5/26/2022182.地址加密的密文索引地址加密的密文索引序號(hào)序號(hào)關(guān)鍵詞關(guān)鍵詞加密地址加密地址1Key1C(Add1)2Key2C(Add2)序號(hào)序號(hào)地址地址密文密文1Add1C12Add2C25/26/2022192.地址加密的密文索引地址加密的密文索引n地址加密的密文索引方法可以解決直接地址加密的密文索引方法可以

9、解決直接密文索引的缺陷，但如果攻擊者能同時(shí)密文索引的缺陷，但如果攻擊者能同時(shí)動(dòng)態(tài)跟蹤數(shù)據(jù)庫的訪問過程，則有可能動(dòng)態(tài)跟蹤數(shù)據(jù)庫的訪問過程，則有可能找出密文與密文地址的對(duì)應(yīng)關(guān)系，得到找出密文與密文地址的對(duì)應(yīng)關(guān)系，得到可乘之機(jī)。可乘之機(jī)。5/26/2022203.動(dòng)態(tài)安全的密文索引動(dòng)態(tài)安全的密文索引n動(dòng)態(tài)安全的密文索引方法雖然可以有效地對(duì)動(dòng)態(tài)安全的密文索引方法雖然可以有效地對(duì)抗攻擊者對(duì)密文數(shù)據(jù)和索引的對(duì)應(yīng)關(guān)系進(jìn)行抗攻擊者對(duì)密文數(shù)據(jù)和索引的對(duì)應(yīng)關(guān)系進(jìn)行動(dòng)態(tài)追蹤分析，但實(shí)現(xiàn)起來卻非常復(fù)雜，需動(dòng)態(tài)追蹤分析，但實(shí)現(xiàn)起來卻非常復(fù)雜，需要采用雙地址索引，每次訪問索引之后，都要采用雙地址索引，每次訪問索引之后，都

10、訪問訪問2 2個(gè)密文數(shù)據(jù)，其中一個(gè)密文數(shù)據(jù)主要個(gè)密文數(shù)據(jù)，其中一個(gè)密文數(shù)據(jù)主要是為了產(chǎn)生混淆效果，敵手通過動(dòng)態(tài)分析檢是為了產(chǎn)生混淆效果，敵手通過動(dòng)態(tài)分析檢索過程和猜測(cè)，能完全知道密文數(shù)據(jù)的排序索過程和猜測(cè)，能完全知道密文數(shù)據(jù)的排序關(guān)系的概率大大降低，從而使密文索引的安關(guān)系的概率大大降低，從而使密文索引的安全性有所提高。全性有所提高。5/26/202221客戶端客戶端密文特征密文特征云端云端客戶端客戶端特征值特征值云端云端檢索詞檢索詞比對(duì)比對(duì)匹配結(jié)果匹配結(jié)果存儲(chǔ)過程檢索過程四、基于特征精確檢索方案四、基于特征精確檢索方案明文明文密文密文特征值特征值（完整）（完整）客戶端客戶端 云存儲(chǔ)服務(wù)端云存儲(chǔ)

11、服務(wù)端密文密文特征值特征值（完整）（完整）用戶端將密文和特征值用戶端將密文和特征值分批分批傳給云存儲(chǔ)服務(wù)端傳給云存儲(chǔ)服務(wù)端密文密文特征值特征值（完整）（完整）密文密文特征值特征值（完整）（完整）5/26/202223 檢索詞特征值檢索詞特征值匹配結(jié)果匹配結(jié)果索索引引特特征征值值 密密 文文比比對(duì)對(duì)5/26/202224基于基于HashHash的密文精確檢索方案的密文精確檢索方案n 利用利用HashHash函數(shù)建立索引，在加密前的信息后面鏈函數(shù)建立索引，在加密前的信息后面鏈接一個(gè)隨機(jī)數(shù)保證相同明文在加密后產(chǎn)生不同的接一個(gè)隨機(jī)數(shù)保證相同明文在加密后產(chǎn)生不同的密文，提高了安全性。密文，提高了安全性。

12、n 在數(shù)據(jù)庫中每一個(gè)記錄有很多的字段，選取適合在數(shù)據(jù)庫中每一個(gè)記錄有很多的字段，選取適合精確檢索建立索引的字段建立索引，并將建立的精確檢索建立索引的字段建立索引，并將建立的索引存到對(duì)應(yīng)的字段中。索引存到對(duì)應(yīng)的字段中。n 在檢索時(shí)根據(jù)檢索詞在對(duì)應(yīng)的字段中檢索，如果在檢索時(shí)根據(jù)檢索詞在對(duì)應(yīng)的字段中檢索，如果匹配成功，檢索出對(duì)應(yīng)的整個(gè)記錄。匹配成功，檢索出對(duì)應(yīng)的整個(gè)記錄。5/26/202225建立索引 5/26/202226檢索過程 5/26/202227五、基于五、基于HashHash的密文模糊檢索方案的密文模糊檢索方案n利用Hash函數(shù)建立模糊檢索的索引，通過模糊匹配實(shí)現(xiàn)對(duì)密文數(shù)據(jù)的模糊檢索 5

13、/26/202228001100001111011000110000特征值特征值密文密文0011000020FFRSE11010011RE45KY%G11110110984REFoT001100001111011020FFRSE984REFoT5/26/202229建立索引 5/26/202230密文檢索5/26/202231 1. 1. 特征值特征值 特征值的提取基于特征值的提取基于帶密鑰的摘要算法帶密鑰的摘要算法。因此，。因此，根據(jù)特征值并不能推斷出任何明文信息，同時(shí)，也保根據(jù)特征值并不能推斷出任何明文信息，同時(shí)，也保證了：只有持有密鑰的人，才可以進(jìn)行密文檢索。證了：只有持有密鑰的人，才可

14、以進(jìn)行密文檢索。 2. 2. 云端安全性云端安全性 在整個(gè)操作過程中，云端就像是個(gè)盲人，在在整個(gè)操作過程中，云端就像是個(gè)盲人，在云端沒有任何的明文出現(xiàn)。云端負(fù)責(zé)存儲(chǔ)、檢索、提云端沒有任何的明文出現(xiàn)。云端負(fù)責(zé)存儲(chǔ)、檢索、提取數(shù)據(jù)，但是卻看不到任何明文。取數(shù)據(jù)，但是卻看不到任何明文。5/26/202232六、密文檢索發(fā)展方向六、密文檢索發(fā)展方向n密文數(shù)據(jù)庫的檢索是一項(xiàng)復(fù)雜的工作，密文數(shù)據(jù)庫的檢索是一項(xiàng)復(fù)雜的工作，高效、安全的密文數(shù)據(jù)庫檢索更是數(shù)據(jù)高效、安全的密文數(shù)據(jù)庫檢索更是數(shù)據(jù)庫安全技術(shù)研究的熱點(diǎn)庫安全技術(shù)研究的熱點(diǎn)n在今后的工作中我們將進(jìn)一步研究檢索在今后的工作中我們將進(jìn)一步研究檢索算法，以使

15、之能適應(yīng)諸如模糊查詢、多算法，以使之能適應(yīng)諸如模糊查詢、多表查詢、復(fù)合條件查詢等各種復(fù)雜查詢表查詢、復(fù)合條件查詢等各種復(fù)雜查詢模式的密文數(shù)據(jù)庫檢索機(jī)制。模式的密文數(shù)據(jù)庫檢索機(jī)制。5/26/202233ApplicationApplicationDB ServerDB ServerSQLSQLUser 1User 1User 2User 2User 3User 3數(shù)據(jù)庫中的數(shù)據(jù)庫中的隱私隱私數(shù)據(jù)泄露數(shù)據(jù)泄露例如例如, Sony Playstation Network被黑客攻擊泄露了被黑客攻擊泄露了7700萬用戶的個(gè)人信息檔案萬用戶的個(gè)人信息檔案系統(tǒng)管理員系統(tǒng)管理員威脅威脅1: 數(shù)據(jù)庫服數(shù)據(jù)庫服務(wù)

16、器的被動(dòng)攻擊務(wù)器的被動(dòng)攻擊 威脅威脅2: 所有服務(wù)器上的任何攻擊所有服務(wù)器上的任何攻擊黑客黑客5/26/202234CryptDB 概述目標(biāo)目標(biāo): 保護(hù)隱私數(shù)據(jù)保護(hù)隱私數(shù)據(jù)1.對(duì)對(duì)加密的數(shù)據(jù)執(zhí)行加密的數(shù)據(jù)執(zhí)行SQL查詢語句查詢語句2.使用細(xì)粒度的使用細(xì)粒度的keys;把基于訪問控制的用戶密碼和這些把基于訪問控制的用戶密碼和這些keys綁定綁定ApplicationApplicationDB ServerDB ServerSQLSQLThreat 1: passive DB Threat 1: passive DB server attacksserver attacksThreat 2: an

17、y attacks on all serversThreat 2: any attacks on all serverson encrypted dataon encrypted dataUser 1User 1User 2User 2User 3User 35/26/2022351.首次實(shí)現(xiàn)對(duì)密文數(shù)據(jù)執(zhí)行大部分的首次實(shí)現(xiàn)對(duì)密文數(shù)據(jù)執(zhí)行大部分的SQL查詢語句查詢語句 將數(shù)據(jù)庫對(duì)系統(tǒng)管理員、外包數(shù)據(jù)庫不可見（或：將數(shù)據(jù)庫對(duì)系統(tǒng)管理員、外包數(shù)據(jù)庫不可見（或：使得使得DBADBA或黑客無法通過或黑客無法通過DBMSDBMS獲取原數(shù)據(jù)獲取原數(shù)據(jù)。）。）2.即使當(dāng)服務(wù)器都被攻陷以后，在攻擊期間，也能保護(hù)

18、即使當(dāng)服務(wù)器都被攻陷以后，在攻擊期間，也能保護(hù)未登陸用戶的數(shù)據(jù)安全未登陸用戶的數(shù)據(jù)安全 降低了數(shù)據(jù)的泄漏量降低了數(shù)據(jù)的泄漏量3.適度的開銷適度的開銷: 大約只增加大約只增加26%的開銷（的開銷（ TPC-C） 主要工作4.不更改不更改DBMS(例如例如, Postgres, MySQL)5/26/202236col1/rankcol1/rank col2/namecol2/nametable1/emptable1/empSELECT * FROM emp WHERE salary = 100 x934bc1x5a8c34x5a8c34x84a21cSELECT * FROM table1 WH

19、ERE col3 = x5a8c34ProxyProxy? ?x5a8c34x5a8c34? ?x5a8c34x5a8c34x4be219x4be219x95c623x95c623x2ea887x2ea887x17cea7x17cea7col3/salarycol3/salaryApplicationApplication6060100100800800100100隨機(jī)加密隨機(jī)加密確定性加密確定性加密5/26/202237col1/rankcol1/rankcol2/namecol2/nametable1 (emp)table1 (emp)x934bc1x5a8c34x5a8c34x84a21

20、cx638e54x638e54x922eb4x1eab81SELECT * FROM table1 WHERE col3 x638e54ProxyProxyx638e54x922eb4x638e54col3/salarycol3/salaryApplicationApplication6060100100800800100100確定性加密確定性加密SELECT * FROM emp WHERE salary 100開放性加密開放性加密5/26/2022381.使用 SQL-aware 加密方案集 兩個(gè)關(guān)鍵技術(shù)兩個(gè)關(guān)鍵技術(shù)大部分的SQL語句使用有限的標(biāo)準(zhǔn)謂詞集 2. 根據(jù)SQL語句所包含的數(shù)據(jù)操

21、作類型，調(diào)整語句所包含的數(shù)據(jù)操作類型，調(diào)整加密方案加密方案5/26/202239加密方案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., , , T2.c 擴(kuò)展: 拆分SQL語句, 預(yù)計(jì)算列, 或者添加新的加密方案5/26/202247性能表現(xiàn)DB server DB server 吞吐量