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

13三月2024第八講密文檢索技術(shù)*2一、密文數(shù)據(jù)庫(kù)無限量的存儲(chǔ)資源為什么至今并未得到廣泛應(yīng)用？云計(jì)算*3原因：用戶云端攻擊者訪問控制不再起作用*4解決方案：密文存儲(chǔ)用戶云端攻擊者數(shù)據(jù)加密是最簡(jiǎn)單、有效的做法*5問題：密文數(shù)據(jù)庫(kù)如何檢索？用戶云端攻擊者*6用戶云端攻擊者如果不考慮效率，將密文傳回用戶，再解密，是最安全的做法。問題：密文數(shù)據(jù)庫(kù)如何檢索？*7傳統(tǒng)的方法是首先對(duì)加密數(shù)據(jù)進(jìn)行解密，然后對(duì)解密數(shù)據(jù)進(jìn)行檢索。這種方法是不安全也是不高效。用戶云端攻擊者解密檢索*8二、密文數(shù)據(jù)庫(kù)檢索策略1.不用解密而直接操作密文數(shù)據(jù)2.一種是分步查詢*91.直接操作密文數(shù)據(jù)數(shù)據(jù)庫(kù)的秘密同態(tài)技術(shù)和數(shù)據(jù)庫(kù)的序加密等。秘密同態(tài)技術(shù)對(duì)加密算法提出了一定的約束條件，使?jié)M足密文同態(tài)的加密算法的應(yīng)用不具有普遍性。數(shù)據(jù)庫(kù)的序加密方法主要采用序列密碼算法，序列密碼算法采用異或的運(yùn)算方法，密鑰序列不能重復(fù)，如果對(duì)不同記錄采取不同的密鑰種子，則密鑰管理難度太大，如果對(duì)不同記錄采取相同的密鑰種子，則會(huì)存在不少相同或相近的密文字段值，容易受到統(tǒng)計(jì)攻擊和已知明文攻擊。*10基于同態(tài)加密技術(shù)檢索查詢技術(shù)保持?jǐn)?shù)值順序的數(shù)據(jù)庫(kù)加密方法OPES(OrderPreservingEncryption)數(shù)據(jù)庫(kù)分區(qū)*112.分步檢索查詢一般需要進(jìn)行查詢分解，先對(duì)密文數(shù)據(jù)進(jìn)行范圍查詢，縮小解密范圍，快速解密后再執(zhí)行精確查詢，查詢策略的核心難點(diǎn)在于需要盡量提高對(duì)密文數(shù)據(jù)庫(kù)查詢的準(zhǔn)確率，縮小返回客戶端的密文數(shù)據(jù)的范圍。*12數(shù)值型分步檢索查詢數(shù)據(jù)庫(kù)分區(qū)范圍檢索用戶云端*13*14*15三、密文數(shù)據(jù)庫(kù)索引機(jī)制1.密文數(shù)據(jù)的直接索引2.地址加密的密文索引3.動(dòng)態(tài)安全的密文索引*161.密文數(shù)據(jù)的直接索引序號(hào)關(guān)鍵詞地址1Key1Add12Key2Add2………序號(hào)地址密文1Add1C12Add2C2………*17對(duì)密文數(shù)據(jù)的直接索引方法的主要缺點(diǎn)是密文索引樹中的地址數(shù)據(jù)是以明文方式存放的，攻擊者可將各結(jié)點(diǎn)的密文數(shù)據(jù)按其對(duì)應(yīng)的明文進(jìn)行排序，并利用部分明、密文對(duì)應(yīng)的統(tǒng)計(jì)規(guī)律獲得可用于破譯的關(guān)鍵信息。*182.地址加密的密文索引序號(hào)關(guān)鍵詞加密地址1Key1C(Add1)2Key2C(Add2)………序號(hào)地址密文1Add1C12Add2C2………*192.地址加密的密文索引地址加密的密文索引方法可以解決直接密文索引的缺陷，但如果攻擊者能同時(shí)動(dòng)態(tài)跟蹤數(shù)據(jù)庫(kù)的訪問過程，則有可能找出密文與密文地址的對(duì)應(yīng)關(guān)系，得到可乘之機(jī)。*203.動(dòng)態(tài)安全的密文索引動(dòng)態(tài)安全的密文索引方法雖然可以有效地對(duì)抗攻擊者對(duì)密文數(shù)據(jù)和索引的對(duì)應(yīng)關(guān)系進(jìn)行動(dòng)態(tài)追蹤分析，但實(shí)現(xiàn)起來卻非常復(fù)雜，需要采用雙地址索引，每次訪問索引之后，都訪問2個(gè)密文數(shù)據(jù)，其中一個(gè)密文數(shù)據(jù)主要是為了產(chǎn)生混淆效果，敵手通過動(dòng)態(tài)分析檢索過程和猜測(cè)，能完全知道密文數(shù)據(jù)的排序關(guān)系的概率大大降低，從而使密文索引的安全性有所提高。*21客戶端密文特征云端客戶端特征值云端檢索詞比對(duì)匹配結(jié)果存儲(chǔ)過程檢索過程四、基于特征精確檢索方案明文密文特征值（完整）客戶端

云存儲(chǔ)服務(wù)端密文特征值（完整）用戶端將密文和特征值分批傳給云存儲(chǔ)服務(wù)端密文特征值（完整）密文特征值（完整）*23

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

密文比對(duì)*24基于Hash的密文精確檢索方案利用Hash函數(shù)建立索引，在加密前的信息后面鏈接一個(gè)隨機(jī)數(shù)保證相同明文在加密后產(chǎn)生不同的密文，提高了安全性。在數(shù)據(jù)庫(kù)中每一個(gè)記錄有很多的字段，選取適合精確檢索建立索引的字段建立索引，并將建立的索引存到對(duì)應(yīng)的字段中。在檢索時(shí)根據(jù)檢索詞在對(duì)應(yīng)的字段中檢索，如果匹配成功，檢索出對(duì)應(yīng)的整個(gè)記錄。*25建立索引

*26檢索過程

*27五、基于Hash的密文模糊檢索方案利用Hash函數(shù)建立模糊檢索的索引，通過模糊匹配實(shí)現(xiàn)對(duì)密文數(shù)據(jù)的模糊檢索

*28001100001111011000110000特征值密文…………0011000020FF@RSE11010011RE45KY%G…………11110110984REFoT………001100001111011020FF@RSE984REFoT*29建立索引

*30密文檢索*31安全分析

1.特征值特征值的提取基于帶密鑰的摘要算法。因此，根據(jù)特征值并不能推斷出任何明文信息，同時(shí)，也保證了：只有持有密鑰的人，才可以進(jìn)行密文檢索。2.云端安全性在整個(gè)操作過程中，云端就像是個(gè)盲人，在云端沒有任何的明文出現(xiàn)。云端負(fù)責(zé)存儲(chǔ)、檢索、提取數(shù)據(jù)，但是卻看不到任何明文。*32六、密文檢索發(fā)展方向密文數(shù)據(jù)庫(kù)的檢索是一項(xiàng)復(fù)雜的工作，高效、安全的密文數(shù)據(jù)庫(kù)檢索更是數(shù)據(jù)庫(kù)安全技術(shù)研究的熱點(diǎn)．在今后的工作中我們將進(jìn)一步研究檢索算法，以使之能適應(yīng)諸如模糊查詢、多表查詢、復(fù)合條件查詢等各種復(fù)雜查詢模式的密文數(shù)據(jù)庫(kù)檢索機(jī)制。CryptDB:基于密文形式可查詢的密文數(shù)據(jù)庫(kù)*33ApplicationDBServerSQLUser1User2User3數(shù)據(jù)庫(kù)中的隱私數(shù)據(jù)泄露例如,SonyPlaystationNetwork被黑客攻擊泄露了7700萬用戶的個(gè)人信息檔案系統(tǒng)管理員威脅1:數(shù)據(jù)庫(kù)服務(wù)器的被動(dòng)攻擊

威脅2:所有服務(wù)器上的任何攻擊黑客*34CryptDB概述目標(biāo):保護(hù)隱私數(shù)據(jù)對(duì)加密的數(shù)據(jù)執(zhí)行SQL查詢語句使用細(xì)粒度的keys;把基于訪問控制的用戶密碼和這些keys綁定ApplicationDBServerSQLThreat1:passiveDBserverattacksThreat2:anyattacksonallserversonencrypteddataUser1User2User3*35首次實(shí)現(xiàn)對(duì)密文數(shù)據(jù)執(zhí)行大部分的SQL查詢語句

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

降低了數(shù)據(jù)的泄漏量適度的開銷:大約只增加26%的開銷（TPC-C）主要工作不更改DBMS(例如,Postgres,MySQL)*36col1/rankcol2/nametable1/empSELECT*FROMempWHEREsalary=100x934bc1x5a8c34x5a8c34x84a21cSELECT*FROMtable1WHEREcol3=x5a8c34Proxy?x5a8c34x5a8c34?x5a8c34x5a8c34x4be219x95c623x2ea887x17cea7col3/salaryApplication60100800100隨機(jī)加密確定性加密*37col1/rankcol2/nametable1(emp)x934bc1x5a8c34x5a8c34x84a21cx638e54x638e54x922eb4x1eab81SELECT*FROMtable1WHEREcol3≥x638e54Proxyx638e54x922eb4x638e54col3/salaryApplication60100800100確定性加密SELECT*FROMempWHEREsalary

≥

100開放性加密*38使用SQL-aware加密方案集兩個(gè)關(guān)鍵技術(shù)大部分的SQL語句使用有限的標(biāo)準(zhǔn)謂詞集

根據(jù)SQL語句所包含的數(shù)據(jù)操作類型，調(diào)整加密方案*39加密方案e.g.,=,!=,IN,COUNT,GROUPBY,DISTINCTSchemeRND

HOMDET

SEARCH

JOINOPEFunctionnone+,*equalityjoinwordsearchorderConstructionAESinCBCAESinCMCPaillierournewschemeSongetal.,‘00Boldyrevaetal.’09firstimplementatione.g.,>,<,ORDERBY,SORT,MAX,MINrestrictedILIKEHighest安全性seepapere.g.,sum*40如何去加密每一個(gè)數(shù)據(jù)項(xiàng)?

所需加密方案取決于查詢事先未知查詢語句Leaksorder!rankALL?col1-RNDcol1-HOMcol1-SEARCHcol1-DETcol1-JOINcol1-OPE‘CEO’‘worker’*41intvalueHOMOnionAdd洋蔥加密方案valueJOINDETRNDOnionEqualityOnionSearch同一加密層中同一列的所有數(shù)據(jù)項(xiàng)使用相同的密鑰加密初始化的時(shí)候，采用安全度最高的加密方案OReachvaluevalueOPE-JOINOPERNDOnionOrdertextvalueSEARCH*42示例:SELECT*FROMempWHERErank=‘CEO’;emp:ranknamesalary‘CEO’‘worker’‘CEO’JOINDETRNDOnionEqualitycol1-OnionEqcol1-OnionOrdercol1-OnionSearchcol2-OnionEqtable1:………RNDRNDSEARCHRNDSEARCHRNDRNDRND*43例子UPDATEtable1SETcol1-OnionEq=

Decrypt_RND(key,col1-OnionEq);‘CEO’JOINDETRNDSELECT*FROMtable1WHEREcol1-OnionEq=xda5c0407;DETOnionEqualityRNDRNDSELECT*FROMempWHERErank=‘CEO’;DETDETcol1-OnionEqcol1-OnionOrdercol1-OnionSearchcol2-OnionEqtable1………RNDRNDSEARCHRNDSEARCHRND*44挑戰(zhàn)：數(shù)據(jù)共享在加密數(shù)據(jù)上的過程查詢msg_idsenderreceivermsg_idmessage5“secretmessage”5AliceBobSPEAKS_FORmsg_idSPEAKS_FORmsg_idENC_FORmsg_id如何從SQL語句層級(jí)中捕獲應(yīng)用程序的訪問控制策略？Annotations將用戶口令與Key綁定Km5Km5Km5Howtoenforceaccesscontrolcryptographically?Alice-passBob-pass*45評(píng)估Cryptdb是否支持真實(shí)的查詢/應(yīng)用程序？加密后，數(shù)據(jù)安全性如何?使用后，性能如何?*46不支持的查詢語句一些更復(fù)雜的運(yùn)算,比如,trigonometry操作需要結(jié)合互補(bǔ)相容的加密方案例如,T1.a+T1.b>T2.c擴(kuò)展:拆分SQL語句,預(yù)計(jì)算列,或者添加新的加密方案*47性能表現(xiàn)DBserver吞吐量CryptDBProxyEncrypteddatabaseApplication1CryptDB:PlaindatabaseApplication1MySQL:CryptDBProxyApplication2Application2Latency硬件:2.4GHzIntelXeonE5620–8cores,12