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

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

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

云存儲服務(wù)端密文特征值（完整）用戶端將密文和特征值分批傳給云存儲服務(wù)端密文特征值（完整）密文特征值（完整）11/7/202323客戶端

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

密

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

11/7/202326檢索過程

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

11/7/202328例001100001111011000110000特征值密文…………0011000020FF@RSE11010011RE45KY%G…………11110110984REFoT………001100001111011020FF@RSE984REFoT用戶端解密檢索結(jié)果11/7/202329建立索引

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

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

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

基于密文形式可查詢的密文數(shù)據(jù)庫11/7/202333ApplicationDBServerSQLUser1User2User3數(shù)據(jù)庫中的隱私數(shù)據(jù)泄露例如,SonyPlaystationNetwork被黑客攻擊泄露了7700萬用戶的個人信息檔案系統(tǒng)管理員威脅1:數(shù)據(jù)庫服務(wù)器的被動攻擊

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

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

降低了數(shù)據(jù)的泄漏量適度的開銷:大約只增加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加密方案集

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

根據(jù)SQL語句所包含的數(shù)據(jù)操作類型，調(diào)整加密方案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如何去加密每一個數(shù)據(jù)項?

所需加密方案取決于查詢

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

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

加密初始化的時候，采用安全度最高的加密方案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挑戰(zhàn)：數(shù)據(jù)共享在加密數(shù)據(jù)上的過程查詢msg_idsenderreceivermsg_idmessage5“secretmessage”5AliceBobSPEAKS_FORmsg_idSPEAKS_FORmsg_idENC_FORmsg_id如何從SQL語句層級中捕獲應(yīng)用程序的訪問控制策略？Annotations將用戶口令與Key綁定Km5Km5Km5Howtoenforceaccesscontrolcryptographically?Alice-passBob-pass11/7/202345評估Cryptdb是否支持真實的查詢/應(yīng)用程序？

加密后，數(shù)據(jù)安全性如何?使用后，性能如何?11/7/202346不支持的查詢語句一些更復(fù)雜的運算,比如,trigonometry操作需要結(jié)合互補相容的加密方案例如,T1.a+T1.b>T2.c

擴展:拆分SQL語句,