數據庫加密字符串快速查詢方法研究
2009-01-01 00:00:00曹楊何大可
計算機應用研究 2009年2期
(西南交通大學信息安全與國家計算網格實驗室，成都 610031)
摘 要：為了提高在數據庫中查詢加密字符串數據的性能，提出一種新的基于對偶特征碼的快速查詢方法。特征碼與加密字符串數據一一對應，作為索引保存在索引字段中。查詢時使用兩階段查詢策略，首先利用索引字段對加密數據進行一次粗糙查詢以過濾掉與查詢不相關的記錄，然后在解密的數據上再進行一次精確查詢，對粗糙查詢結果進行二次過濾，得到符合查詢條件的記錄。實驗表明，該方法的性能比現有查詢方法有較大提高。
關鍵詞：數據庫加密; 加密字符串查詢; 對偶特征碼; 兩階段查詢
中圖分類號：TP301 文獻標志碼：A
文章編號：1001-3695(2009)02-0736-03
Practical techniques for fast query over encrypted character data in database
CAO Yang，HE Da-ke
(Information Security National Computing Grid Laboratory， Southwest Jiaotong University， Chengdu 610031， China)
Abstract: To improve the performance of querying encrypted character data in database， this paper proposed an approach based on characteristic code of pairs coding that generated characteristic codes for encrypted data as index stored in an index field. When querying the encrypted character data， applied the principle of two-phase query. In the first place，implemented a coarse query over the encrypted data to filter the records which not related to the querying conditions. Then decrypted the rest records and implemented a refined query over them again to get the records exactly match to the query conditions. Results of experiments show that this approach achieves a higher performance than other query methods.
Key words：database encryption; query over encrypted character data; pairs characteristic codes; two-phase query
隨著技術的飛速發展，信息系統日益復雜化，人們對計算機安全的需求與日俱增。數據庫作為當前網絡和信息系統的基礎平臺，解決數據庫安全問題成為目前最為緊迫的挑戰之一。雖然現有的數據庫系統已經采取了相關的安全措施，但是仍然存在一些安全漏洞，如黑客攻擊[1]、DBA（數據庫管理員）的權限過大、備份介質丟失造成機密信息的泄露等。在傳統安全措施的基礎上[1]，保障數據庫機密數據安全性的最好方法是采用數據加密技術將數據庫中的機密數據加密[2~4]。這樣，攻擊者即使繞過（或攻破）了各種系統安全機制，最后得到的也只是加密后的密文數據，同理也防止了備份數據流失造成機密信息的泄露。但是，字符串數據加密后便失去了本身很多固有的特性（如有序性、相似性、可比性等），導致了查詢時需要對所有加密數據先進行解密，然后才能進行查詢。而加/解密操作往往代價很大，極大地降低了系統的查詢性能[5，6]。同時也使得加密字符串的模糊查詢會變得很困難[7]。
針對以上問題，Wang Zheng-fei等人[8]的研究工作給出了比較好的解決方案，后來的崔賓閣等人[9]基本上沿用了文獻[8]中的思想，其查詢速度基本與文獻[8]持平。本文在Wang等人研究工作的基礎上提出了一種基于對偶特征碼的快速查詢新方法。新方法具有比原方法更高的偽記錄過濾性能，并利用高效的SQL查詢語言，使得對加密字符串數據的查詢效率比原方法有了進一步的提升。以下將文獻[8]中的方法稱為原方法，本文提出的方法稱為新方法。
1 整體系統構架
本文采用典型的數據庫管理系統（DBMS）外部加/解密方式，即在應用程序和DBMS之間增加一個查詢分析器（主要包括查詢翻譯模塊(QTM)和查詢過濾模塊(QFM)），如圖1所示。該模塊的作用是為上下層提供數據的加/解密服務和查詢條件的翻譯服務。增加該模塊后，數據的加/解密操作和查詢操作對于上層（應用程序層）用戶來說是完全透明的。采用該構架的優點是不需要修改DBMS，可以方便地修改模塊功能，可移植性強。
2 對偶特征碼（CCPC）
對偶特征碼(characteristic code of pairs coding， CCPC)是針對原明文字符串數據而言，每一個明文字符串對應一個CCPC。CCPC通過一個對偶特征碼生成函數（PCF）得到。PCF有三個輸入參數，第一個是一個任意長度的字符串S1，長度為n，單位為Byte，其各字節的字符分別表示為c1c2…cn；第二個參數是特征碼的長度L，L≥1，單位也是Byte；第三個是對原明文字符串數據進行加/解密的密鑰K，其形式為一個任意長度的字符串。
PCF的輸出是一個字符串S2，長度為L，其各位的字符分別表示為p1p2…pL。形式上有，PCF( c1c2…cn， L， K) = (p1p2…pL )。兩個字符串之間的轉換通過一個帶密鑰的hash函數（HMAC）來實現。轉換過程是：a）將字符串S2各字節置“@”，即將S2置為一個形式為“@@…@”的字符串，其長度為L。b）由S1中兩個相鄰的對偶字符生成一個正整數p，形式為HMAC( cjcj + 1， K ) = p，1 ≤j ≤n-1 ， 1≤p≤L；c）將字符pp的字符值加1，當其值大于90時（即等于Z時），其值不再增加； d）重新執行b）的操作，直到j=n-1；e）將S2中的“ @” 替換成“ _”。
舉例說明。例1，當輸入為PCF (“abcde”， 4， K ) 時，HMAC(“ab”， K ) = 3，HMAC( “bc”， K ) = 1，HMAC(“cd”， K ) = 3，HMAC( “de”， K ) = 4，則輸出為“A_BA”。
需要說明兩點：a）這里的HMAC是經過改造的[4]，以保證其輸出值的范圍不大于L。b）將S2各字節置“@”的原因在于，在步驟c)執行字符值加1時，“@”就變成了“A”，便于查詢分析器生成DBMS支持的SQL查詢語句。最后一步中將S2中的“@” 替換成“_”，也是基于這個考慮。
下面將把該函數與原方法中的PC函數[8]作對比。
原方法中的PC函數在文獻[8]的描述中是一個字符串，但實際上是一個以比特位（bit）為單位的，長度為m bit的二進制串b1b2…bm。這樣的設計在理論上有利于減小編制特征碼索引字段給數據庫帶來的空間開銷，但實現上難以在查詢翻譯模塊將其轉換成DMBS支持的SQL查詢語句，因為SQL查詢語句中不能包含二進制數據。實際操作時仍是將各比特位放大成字節，用來將各比特位表示成SQL查詢語句可識別的ASCII字符。比如比特 1 表示成ASCII碼的0x31。其結果是造成了一個字節只用來表示 0 或 1 兩種字符，字節的利用效率很低。
新方法中的PCF函數充分考慮到這一點不足，并通過前述的計數累加方式把一個字節充分利用起來。比如，例1中“ab”和“cd”的HMAC值同為3，則在特征碼的第3字節上累加成“B”，表示有兩個對偶字符串的HMAC值是一樣的。這個累加計數的方式為后來的粗糙查詢提供了很好的過濾條件，這將在5.2節中進行分析。
3 加密關系存儲模式
對于每個關系R ( T1， …， Tr ，…， Tn )， Tr為待加密的字符串字段，加密后的關系模式為RE ( T1， …， TEr ， …， Tn， Tsr )。其中：TEr是對應于Tr的加密字符串字段，即TEr = E( Tr )；Tsr是對應于Tr的輔助索引字段，用于存儲CCPC。
4 查詢策略
本文使用兩階段查詢策略[8]。第一階段，利用索引字段對加密數據進行一次粗糙查詢以過濾掉與查詢不相關的記錄；第二階段，對第一階段得到的粗糙查詢結果進行二次過濾，得到符合查詢條件的記錄。如圖1，查詢時，查詢分析器接收來自用戶的原始查詢條件，通過QTM，根據一定的轉換規則將該條件翻譯成DBMS支持的SQL查詢語句；DBMS執行完查詢任務后向查詢分析器返回符合條件的記錄集，但該記錄集只是粗糙查詢的結果，包括了一定數量的不滿足用戶原始查詢條件的偽記錄。查詢分析器接收到該記錄集后，通過內部的QFM對其進行二次過濾，得到符合用戶原始查詢條件的最終結果，并將其以明文的形式返回給應用程序。
41 查詢翻譯（QT）算法
411 完全匹配查詢
查詢與查詢條件中的字符串值完全相等的記錄。st為查詢條件中的字符串值，Tr為加密字段，Tsr為相應的索引字段，PCF( st， L， K ) = p1p2…pL，則有where Tr =′st′ → where Tsr =′p1p2…pL′
412 模糊匹配查詢
查詢包含查詢條件中的字符串值的記錄。st為查詢條件中的字符串值，Tr為加密字段，Tsr為相應的索引字段，PCF(st， L， K )= p1p2…pL，則有where Tr like st → where Tsr like [p1-′Z′][p2-′Z′]…[pL-′Z′]。
413 組合匹配查詢
包含以上兩種類型的查詢組合，查詢條件之間以AND、OR等邏輯運算符連接。OP表示邏輯運算符，sti表示查詢條件中的字符串值，Tr表示加密字段，Tsr表示相應的索引字段，PCF(sti， L， K ) = pi1pi2…piL，則有where Tr like st1 OP Tr like st2 OP…OP Tr like sti → where Tsr like [p11-′Z′][p12-′Z′]…[p1L-′Z′] OP Tsr like [p21-′Z′][p22-′Z′]…[p2L-′Z′] OP … OP Tsr like [pi1-′Z′][pi2-′Z′]...[p-′Z′]。
42 查詢過濾（QF）算法
設粗糙查詢得到的結果記錄集為Rcd，包含n條記錄，分別記為Rcd1， Rcd2，…，Rcdn。先將它們解密為記錄集RcdD，形式上有 Rcd =E( RcdD )。在Rcd上執行原始的查詢條件即可得到最終的查詢結果記錄集，即 where Tr like st → where RcdD like st。
5 算法性能分析
51 安全性
由于加密后的關系模式為RE ( T1， …， TEr ， …， Tn， Tsr )，其中的重要字段TEr是以密文形式存儲的，可以認為它的安全性由加密算法和密鑰的安全性決定[2，8]。本文主要分析Tsr，也就是CCPC索引字段的安全性。
在原方法中 ，通過使用hash函數保障索引字段安全性[8，9]，新方法中由于使用的是HMAC（即帶密鑰的hash函數），使得CCPC索引字段在安全性上更有提升。因為在實際情況下，TEr字段中的記錄往往并不屬于一個用戶，很可能是多個用戶都在這個字段中存放有自己的數據，而不同的用戶往往會使用不同的加密密鑰K，這使得相同的字符串可以對應不同的CCPC，使得攻擊者更難通過CCPC分析出加密字段TEr的內容。
52 查詢效率
由于PCF函數產生的CCPC擁有計數累加特性，使得轉換后的模糊匹配的查詢條件更為嚴格，具有比原方法更好的粗糙查詢性能。比如例2，設新方法中，PCF (“abcde”， 4，K) = “A_BA”，PCF ( “fghij”， 4，K) = “B_AA”，PCF (“abcd”，4，K) = “A_B_”；則相應地，在沒有計數累加特性的原方法中是PC (“abcde” )=“1011”， PC (“fghij”)=“1011”，PC (“abcd”) = “1010”。可以清楚地看到當查詢條件字符串為“abcd”時，在粗糙查詢階段，新方法得到的結果記錄集只有記錄 E(“abcde”)，不包括E(“fghij”)；而原方法則會將“fghij”誤判為也滿足查詢條件的記錄。由此可以看到新方法可以在粗糙查詢階段提高查詢的準確率，降低不滿足原始查詢條件的“偽記錄”數目，從而提高了查詢效率。
53 存儲空間
由于在關系模式中增加了一個索引字段，會增大數據庫的存儲空間開銷，這個開銷與索引字段的長度L成正比，L值越大，查詢性能越好，但安全性越差，存儲空間開銷越大；L值越小，查詢性能越差，但安全性越好，存儲空間開銷越小[8，9]。與原方法相比，新方法在存儲性能上并沒有改善。
6 實驗與結果分析
實驗主要目的是對比兩種方法的查詢性能。根據TPC-H標準[10]，由dbgen標準程序自動生成實驗數據庫，比例因子為0.1。以其中的lineitem表作為本次實驗的數據源，以COMMENT字段作為待加密的敏感字段。加密算法采用AES128[4]。實驗環境為Windows XP（Pentium IV 1.8 GHz + 512 MB RAM）+ SQL Server 2000 + VS2005。
由于新方法和原方法在第二階段查詢上的相似性（都采用先解密再查詢的方式），其查詢性能的好壞主要體現在第一階段的過濾性能上。實驗中，隨機生成平均長度為20 Byte的待查詢字符串，查詢語句為select * from lineitem where comment like待查詢字符串。每個實驗結果均為重復實驗100次的平均值（取整）。
表1顯示了兩種方法在不同索引字段大小的情況下，查詢相同字符串時得到的記錄數大小對比。第一階段得到的記錄數越少則在第二階段所需解密的記錄數就越少，說明方法在第一階段的過濾性能越好。可以看到在索引字段小于32時新方法的過濾性要明顯優于原方法，驗證了5.2節的分析；而在索引字段大于32時，新方法與原方法的過濾性能在絕對值上差別不大，因為新方法中的累加計數效果會隨著索引字段增大而衰減，即對偶字符串的HMAC值在索引字段很大的情況下，很難落到同一位置，新方法逐漸地退化成原方法。但是，從表1中可以看到，當索引字段大于32時，從相對值來看，新方法的過濾性能比起原方法仍有超過50%的提升。
表2顯示了兩種方法在不同索引字段大小的情況下，查詢相同字符串時所需要的時間對比。結合表1可以看出，查詢時間是與第一階段得到的記錄數成正比的，第一階段得到的記錄數越多，整個查詢過程需要的查詢時間越長。由于測試環境和具體實現不同，對原方法的實驗結果與文獻[8]有所不同。
圖2和3為新方法在過濾性能和查詢時間代價上相對原方法的提升比。提升比定義為：( 1-新方法實驗結果/原方法實驗結果)×100。從圖3可以看到，當索引字段小于32時，新方法查詢時間代價比原方法降低了60%左右；當索引字段大于32時，也在10%以上。可見新方法的性能比原方法有較大的提高。
7 結束語
新方法基于對偶特征碼，通過構造新的對偶特征碼生成函數，在查詢性能上較原方法有較大的提高。通過在加密數據表中增加索引字段，新方法將對加密數據的查詢轉換為對索引字段的查詢，利用兩階段查詢的方法實現對加密字符串的高效查詢。
新方法繼承了原方法的所有特性（高效性、安全性、實用性），還在查詢性能上有較大提升，平均查詢時間代價比原方法減小了近40%。如果索引字段大小取值合理的話，查詢時間代價可以比原方法減小60%以上，同時還能保證安全性不受影響。
但新方法存在一些不足，如完全匹配查詢（條件為=）時，SQL查詢代價比原方法大，約比原方法高出200~300 ms，這可能與SQL查詢語言的內部實現細節有關[12，13]，需要作進一步的研究。
參考文獻：
［1］CANIM M， KANTARCIOGLU M. Design and analysis of querying encrypted data in relational databases[C]// IFIP WG 11.3 Working Conference on Database and Applications Security. Berlin:Springer， 2007.
[2]STALLING W.Cryptography and network security principles and practices[M].[S.l.]: Prentice Hall， 2003 : 14-71.
[3]JAJODIA S. Database security and privacy[J].ACM Computer Surveys，1996，28(1):129-131.
[4]STINSON D R. Cryptography: theory and practice[M].[S.l.]:CRC Perss， 2002 : 23-56.
[5]LYER B，MEHRORTA S，MYKLETUN E，et al.A framework of efficient storage securiy in RDBMS[C]// Proc of the 9th Intemational Coneference on Extending Database Technology (EDBT).2004:147-164.
[6]BENNETT K，GROTHO C，HOORZOV T， et al.Effieient sharing of encrypted data[C]// Proc of Australasian Conference on Information Security and Privacy (ACISP).2002:107-120.
[7]王正飛， 施伯樂. 數據庫加密技術及其應用研究[D]. 上海：復旦大學， 2005.
[8]WANG Zheng-fei，DAI Jing，Wang Wei，et al. Fast query over encyrpted character data in database[J].Communications in Information and System， 2004，3314(4):289-300.
[9]崔賓閣，劉大昕，王桐.支持快速查詢的數據庫加密方法研究[J].計算機科學，2006，33(6):115-118.
[10]Transaction Processing Performance Council.TPC BenchmarkTM H standard specification revision 2.6.0[S/OL].[2007-08-16]. http://www.tpc.org.
[11]HACIGUMUS H，BALA L，MEHROTRA S.Providing database as a service，Technical Report TR-DB-02-02 [R]. Irvine: Database Research Group at University of California，2002.
[12]GARCIA-MOLINA H， ULLMAN D， WIDOM J. Database system implementation[M].[S.l.]: Prentice Hall，2001:59-78.
[13]陶宏才. 數據庫原理及設計[M].北京:清華大學出版社， 2004:133-138.
