密文檢索技術(shù)

密文檢索技術(shù)5/28/20231第一頁，共四十八頁，編輯于2023年，星期五一、密文數(shù)據(jù)庫無限量的存儲資源為什么至今并未得到廣泛應(yīng)用？云計算5/28/20232第二頁，共四十八頁，編輯于2023年，星期五原因：用戶云端攻擊者訪問控制不再起作用5/28/20233第三頁，共四十八頁，編輯于2023年，星期五解決方案：密文存儲用戶云端攻擊者數(shù)據(jù)加密是最簡單、有效的做法5/28/20234第四頁，共四十八頁，編輯于2023年，星期五問題：密文數(shù)據(jù)庫如何檢索？用戶云端攻擊者5/28/20235第五頁，共四十八頁，編輯于2023年，星期五用戶云端攻擊者如果不考慮效率，將密文傳回用戶，再解密，是最安全的做法。問題：密文數(shù)據(jù)庫如何檢索？5/28/20236第六頁，共四十八頁，編輯于2023年，星期五傳統(tǒng)的方法是首先對加密數(shù)據(jù)進(jìn)行解密，然后對解密數(shù)據(jù)進(jìn)行檢索。這種方法是不安全也是不高效。用戶云端攻擊者解密檢索5/28/20237第七頁，共四十八頁，編輯于2023年，星期五二、密文數(shù)據(jù)庫檢索策略1.不用解密而直接操作密文數(shù)據(jù)2.一種是分步查詢5/28/20238第八頁，共四十八頁，編輯于2023年，星期五1.直接操作密文數(shù)據(jù)數(shù)據(jù)庫的秘密同態(tài)技術(shù)和數(shù)據(jù)庫的序加密等。秘密同態(tài)技術(shù)對加密算法提出了一定的約束條件，使?jié)M足密文同態(tài)的加密算法的應(yīng)用不具有普遍性。數(shù)據(jù)庫的序加密方法主要采用序列密碼算法，序列密碼算法采用異或的運算方法，密鑰序列不能重復(fù)，如果對不同記錄采取不同的密鑰種子，則密鑰管理難度太大，如果對不同記錄采取相同的密鑰種子，則會存在不少相同或相近的密文字段值，容易受到統(tǒng)計攻擊和已知明文攻擊。5/28/20239第九頁，共四十八頁，編輯于2023年，星期五基于同態(tài)加密技術(shù)檢索查詢技術(shù)保持?jǐn)?shù)值順序的數(shù)據(jù)庫加密方法OPES(OrderPreservingEncryption)數(shù)據(jù)庫分區(qū)5/28/202310第十頁，共四十八頁，編輯于2023年，星期五2.分步檢索查詢一般需要進(jìn)行查詢分解，先對密文數(shù)據(jù)進(jìn)行范圍查詢，縮小解密范圍，快速解密后再執(zhí)行精確查詢，查詢策略的核心難點在于需要盡量提高對密文數(shù)據(jù)庫查詢的準(zhǔn)確率，縮小返回客戶端的密文數(shù)據(jù)的范圍。5/28/202311第十一頁，共四十八頁，編輯于2023年，星期五數(shù)值型分步檢索查詢數(shù)據(jù)庫分區(qū)范圍檢索用戶云端5/28/202312第十二頁，共四十八頁，編輯于2023年，星期五在數(shù)據(jù)庫密文檢索時，通過關(guān)鍵詞的數(shù)值大小判斷關(guān)鍵詞落在哪一個分區(qū)，進(jìn)而根據(jù)數(shù)值范圍確定數(shù)據(jù)庫中哪些記錄可能符合檢索條件。

例：如對于檢索條件Y＞450，可以判定分區(qū)1、分區(qū)4的所有記錄是滿足檢索條件的，而通過解密分區(qū)5的所有記錄，可以精確判斷剩余滿足條件的數(shù)據(jù)庫記錄。5/28/202313第十三頁，共四十八頁，編輯于2023年，星期五僅通過值域分區(qū)的方式建立數(shù)據(jù)庫值索引容易造成數(shù)據(jù)庫信息泄漏，因此，數(shù)據(jù)庫分區(qū)的方式通常會采用HASH技術(shù)，對數(shù)值進(jìn)行HASH后，根據(jù)HASH值再進(jìn)行分區(qū)，進(jìn)而避免信息泄漏的問題。5/28/202314第十四頁，共四十八頁，編輯于2023年，星期五三、密文數(shù)據(jù)庫索引機(jī)制1.密文數(shù)據(jù)的直接索引2.地址加密的密文索引3.動態(tài)安全的密文索引5/28/202315第十五頁，共四十八頁，編輯于2023年，星期五1.密文數(shù)據(jù)的直接索引序號關(guān)鍵詞地址1Key1Add12Key2Add2………序號地址密文1Add1C12Add2C2………5/28/202316第十六頁，共四十八頁，編輯于2023年，星期五對密文數(shù)據(jù)的直接索引方法的主要缺點是密文索引樹中的地址數(shù)據(jù)是以明文方式存放的，攻擊者可將各結(jié)點的密文數(shù)據(jù)按其對應(yīng)的明文進(jìn)行排序，并利用部分明、密文對應(yīng)的統(tǒng)計規(guī)律獲得可用于破譯的關(guān)鍵信息。5/28/202317第十七頁，共四十八頁，編輯于2023年，星期五2.地址加密的密文索引序號關(guān)鍵詞加密地址1Key1C(Add1)2Key2C(Add2)………序號地址密文1Add1C12Add2C2………5/28/202318第十八頁，共四十八頁，編輯于2023年，星期五2.地址加密的密文索引地址加密的密文索引方法可以解決直接密文索引的缺陷，但如果攻擊者能同時動態(tài)跟蹤數(shù)據(jù)庫的訪問過程，則有可能找出密文與密文地址的對應(yīng)關(guān)系，得到可乘之機(jī)。5/28/202319第十九頁，共四十八頁，編輯于2023年，星期五3.動態(tài)安全的密文索引動態(tài)安全的密文索引方法雖然可以有效地對抗攻擊者對密文數(shù)據(jù)和索引的對應(yīng)關(guān)系進(jìn)行動態(tài)追蹤分析，但實現(xiàn)起來卻非常復(fù)雜，需要采用雙地址索引，每次訪問索引之后，都訪問2個密文數(shù)據(jù)，其中一個密文數(shù)據(jù)主要是為了產(chǎn)生混淆效果，敵手通過動態(tài)分析檢索過程和猜測，能完全知道密文數(shù)據(jù)的排序關(guān)系的概率大大降低，從而使密文索引的安全性有所提高。5/28/202320第二十頁，共四十八頁，編輯于2023年，星期五客戶端密文特征云端客戶端特征值云端檢索詞比對匹配結(jié)果存儲過程檢索過程四、基于特征精確檢索方案5/28/202321第二十一頁，共四十八頁，編輯于2023年，星期五明文密文特征值（完整）客戶端

云存儲服務(wù)端密文特征值（完整）用戶端將密文和特征值分批傳給云存儲服務(wù)端密文特征值（完整）密文特征值（完整）第二十二頁，共四十八頁，編輯于2023年，星期五客戶端

檢索詞特征值匹配結(jié)果索引特征值

密

文比對5/28/202323第二十三頁，共四十八頁，編輯于2023年，星期五基于Hash的密文精確檢索方案利用Hash函數(shù)建立索引，在加密前的信息后面鏈接一個隨機(jī)數(shù)保證相同明文在加密后產(chǎn)生不同的密文，提高了安全性。在數(shù)據(jù)庫中每一個記錄有很多的字段，選取適合精確檢索建立索引的字段建立索引，并將建立的索引存到對應(yīng)的字段中。在檢索時根據(jù)檢索詞在對應(yīng)的字段中檢索，如果匹配成功，檢索出對應(yīng)的整個記錄。5/28/202324第二十四頁，共四十八頁，編輯于2023年，星期五建立索引

5/28/202325第二十五頁，共四十八頁，編輯于2023年，星期五檢索過程

5/28/202326第二十六頁，共四十八頁，編輯于2023年，星期五五、基于Hash的密文模糊檢索方案利用Hash函數(shù)建立模糊檢索的索引，通過模糊匹配實現(xiàn)對密文數(shù)據(jù)的模糊檢索

5/28/202327第二十七頁，共四十八頁，編輯于2023年，星期五例001100001111011000110000特征值密文…………0011000020FF@RSE11010011RE45KY%G…………11110110984REFoT………001100001111011020FF@RSE984REFoT用戶端解密檢索結(jié)果5/28/202328第二十八頁，共四十八頁，編輯于2023年，星期五建立索引

5/28/202329第二十九頁，共四十八頁，編輯于2023年，星期五密文檢索5/28/202330第三十頁，共四十八頁，編輯于2023年，星期五安全分析

1.特征值特征值的提取基于帶密鑰的摘要算法。因此，根據(jù)特征值并不能推斷出任何明文信息，同時，也保證了：只有持有密鑰的人，才可以進(jìn)行密文檢索。

2.云端安全性在整個操作過程中，云端就像是個盲人，在云端沒有任何的明文出現(xiàn)。云端負(fù)責(zé)存儲、檢索、提取數(shù)據(jù)，但是卻看不到任何明文。5/28/202331第三十一頁，共四十八頁，編輯于2023年，星期五六、密文檢索發(fā)展方向密文數(shù)據(jù)庫的檢索是一項復(fù)雜的工作，高效、安全的密文數(shù)據(jù)庫檢索更是數(shù)據(jù)庫安全技術(shù)研究的熱點．在今后的工作中我們將進(jìn)一步研究檢索算法，以使之能適應(yīng)諸如模糊查詢、多表查詢、復(fù)合條件查詢等各種復(fù)雜查詢模式的密文數(shù)據(jù)庫檢索機(jī)制。5/28/202332第三十二頁，共四十八頁，編輯于2023年，星期五CryptDB:

基于密文形式可查詢的密文數(shù)據(jù)庫5/28/202333第三十三頁，共四十八頁，編輯于2023年，星期五ApplicationDBServerSQLUser1User2User3數(shù)據(jù)庫中的隱私數(shù)據(jù)泄露例如,SonyPlaystationNetwork被黑客攻擊泄露了7700萬用戶的個人信息檔案系統(tǒng)管理員威脅1:數(shù)據(jù)庫服務(wù)器的被動攻擊

威脅2:所有服務(wù)器上的任何攻擊黑客5/28/202334第三十四頁，共四十八頁，編輯于2023年，星期五CryptDB概述目標(biāo):保護(hù)隱私數(shù)據(jù)對加密的數(shù)據(jù)執(zhí)行SQL查詢語句使用細(xì)粒度的keys;把基于訪問控制的用戶密碼和這些keys綁定ApplicationDBServerSQLThreat1:passiveDBserverattacksThreat2:anyattacksonallserversonencrypteddataUser1User2User35/28/202335第三十五頁，共四十八頁，編輯于2023年，星期五首次實現(xiàn)對密文數(shù)據(jù)執(zhí)行大部分的SQL查詢語句

將數(shù)據(jù)庫對系統(tǒng)管理員、外包數(shù)據(jù)庫不可見（或：使得DBA或黑客無法通過DBMS獲取原數(shù)據(jù)。）即使當(dāng)服務(wù)器都被攻陷以后，在攻擊期間，也能保護(hù)未登陸用戶的數(shù)據(jù)安全

降低了數(shù)據(jù)的泄漏量適度的開銷:大約只增加26%的開銷（

TPC-C）

主要工作不更改DBMS(例如,Postgres,MySQL)5/28/202336第三十六頁，共四十八頁，編輯于2023年，星期五col1/rankcol2/nametable1/empSELECT*FROMempWHEREsalary=100x934bc1x5a8c34x5a8c34x84a21cSELECT*FROMtable1WHEREcol3=x5a8c34Proxy?x5a8c34x5a8c34?x5a8c34x5a8c34x4be219x95c623x2ea887x17cea7col3/salaryApplication60100800100隨機(jī)加密確定性加密5/28/202337第三十七頁，共四十八頁，編輯于2023年，星期五col1/rankcol2/nametable1(emp)x934bc1x5a8c34x5a8c34x84a21cx638e54x638e54x922eb4x1eab81SELECT*FROMtable1WHEREcol3≥x638e54Proxyx638e54x922eb4x638e54col3/salaryApplication60100800100確定性加密SELECT*FROMempWHEREsalary

≥

100開放性加密5/28/202338第三十八頁，共四十八頁，編輯于2023年，星期五使用SQL-aware加密方案集

兩個關(guān)鍵技術(shù)大部分的SQL語句使用有限的標(biāo)準(zhǔn)謂詞集

根據(jù)SQL語句所包含的數(shù)據(jù)操作類型，調(diào)整加密方案5/28/202339第三十九頁，共四十八頁，編輯于2023年，星期五加密方案e.g.,=,!=,IN,COUNT,GROUPBY,DISTINCTSchemeRND

HOMDET

SEARCH

JOINOPEFunctionnone+,*equalityjoinwordsearchorderConstructionAESinCBCAESinCMCPaillierournewschemeSongetal.,‘00Boldyrevaetal.’09firstimplementatione.g.,>,<,ORDERBY,SORT,MAX,MINrestrictedILIKEHighest安全性seepapere.g.,sum5/28/202340第四十頁，共四十八頁，編輯于2023年，星期五如何去加密每一個數(shù)據(jù)項?

所需加密方案取決于查詢

事先未知查詢語句Leaksorder!rankALL?col1-RNDcol1-HOMcol1-SEARCHcol1-DETcol1-JOINcol1-OPE‘CEO’‘worker’5/28/202341第四十一頁，共四十八頁，編輯于2023年，星期五intvalueHOMOnionAdd洋蔥加密方案valueJOINDETRNDOnionEqualityOnionSearch

同一加密層中同一列的所有數(shù)據(jù)項使用相同的密鑰

加密初始化的時候，采用安全度最高的加密方案OReachvaluevalueOPE-JOINOPERNDOnionOrdertextvalueSEARCH5/28/202342第四十二頁，共四十八頁，編輯于2023年，星期五示例:SELECT*FROMempWHERErank=‘CEO’;emp:ranknamesalary‘CEO’‘worker’‘CEO’JOINDETRNDOnionEqualitycol1-OnionEqcol1-OnionOrdercol1-OnionSearchcol2-OnionEqtable1:………RNDRNDSEARCHRNDSEARCHRNDRNDRND5/28/202343第四十三頁，共四十八頁，編輯于2023年，星期五例子

UPDATEtable1SETcol1-OnionEq=

Decrypt_RND(key,col1-OnionEq);‘CEO’JOINDETRNDSELECT*FROMtable1WHEREcol1-OnionEq=xda5c0407;DETOnionEqualityRNDRNDSELECT*FROMempWHERErank=‘CEO’;DETDETcol1-OnionEqcol1-OnionOrdercol1-OnionSearchcol2-OnionEqtable1………RNDRNDSEARCHRNDSEARCHRND5/28/202344第四十四頁，共四十八頁，編輯于2023年，星期五挑戰(zhàn)：數(shù)據(jù)共享在加密數(shù)據(jù)上的過程查詢msg_idsenderreceivermsg_idmessage5“secretmessage”5Ali