基于CryptDB的選擇加密策略研究

張成果，楊 庚，王 偉

(南京郵電大學 計算機學院，江蘇 南京 210003)

基于CryptDB的選擇加密策略研究

張成果，楊 庚，王 偉

(南京郵電大學 計算機學院，江蘇 南京 210003)

針對云中數據隱私保護問題，采用加密存儲是一可行的選擇。而在未解密的情況下，如何對密文進行計算成了近年來研究的熱點。為提高密文計算效率，節約密文數據的存儲空間，將選擇加密策略與CryptDB密文數據庫系統相結合，設計并實現了支持選擇加密策略的CryptDB密文數據庫系統。由于CryptDB使用多個洋蔥加密模型，需將數據加密成多份以適用不同場景，對不敏感字段加密增加了計算時間及存儲空間。針對這些問題，提出一種用戶自定義的敏感字段檢測算法，并且在原系統中創建和注冊明文洋蔥，修改元數據表,以及對自定義SQL語句的攔截和改寫，實現選擇加密策略。實驗結果表明，在滿足用戶對數據表安全性要求的前提下，隨著加密字段減少，密文計算時間和存儲空間顯著減少，提高了CryptDB系統的效率和實用性。

選擇加密；密文計算；CryptDB；密文數據庫；洋蔥加密

0 引 言

隨著云計算的快速發展，云安全成為亟待解決的問題，并且引起了業界的高度重視。例如：Cisco結合云計算網絡應用無邊界的特點，提出自防御云安全技術架構(SDC)；八百客推出傳輸協議加密和URL數據訪問安全碼技術等措施來加強企業數據安全。在云計算的模式下，大量個人及企業用戶將私有的數據在不加密的情況下，通過網絡傳輸存儲在云服務器上。這種模式帶來三個方面的安全問題：一是如何保證在網絡傳輸過程中數據不被非法截取；二是如何確保存儲在第三方云服務器上的數據不被非法訪問；三是如何保證用戶在任何時候都能安全訪問到自身的數據[1]。

解決上述問題較好的方法之一就是用戶對其私有數據進行加密。用傳統的加密算法對數據加密后存儲在云服務器上，用戶無法直接對數據進行查詢、計算及修改等操作。必須將服務器端的密文下載到本地進行解密后，才能對數據進行操作，再對修改后的數據加密并且傳輸到云端存儲。顯然，在面對大規模的數據庫存儲需求時，該方案在執行效率上遠低于明文數據庫。密文計算相關算法的提出解決了上述問題。文中從提高密文計算效率以及減少密文存儲空間角度出發，提出一種選擇加密算法，并通過實驗驗證了算法的有效性。

1 相關工作

自20世紀90年代起，一些密文搜索和計算的方案被相繼提出。1995年，Chor等[2]首次提出私有信息檢索的概念，并在不泄露檢索信息的前提下，實現從數據庫中檢索到用戶所需的信息。2000年，Song等[3]首次提出一種對稱可查詢加密(SSE)方案，開創了在未解密的情況下查詢密文的先例。用戶使用該機制對數據進行加密后，將密文數據交由服務器端存儲；當用戶需要根據關鍵字檢索文件時，將該關鍵字的搜索憑證(search capability)發給服務器，服務器根據這個憑證在密文數據上直接進行檢索，將包含該關鍵字的文件返回給用戶，用戶只需對返回的文件進行解密即可。近年來，可查詢加密機制得到廣泛的研究，Li等[4]解決了關鍵字的模糊查詢問題，Cao等[5]提出了查詢多關鍵字的解決方案。

可查詢加密機制的研究側重于文本文件查詢，對于數據庫中密文數據存儲及查詢等問題，以往的可查詢加密機制則無法滿足需求。如不支持一些基本的SQL查詢，不支持數值之間的大小比較，不支持JOIN操作以及求和操作等。

同態加密算法[6]的提出解決了在未解密的情況下對密文數據進行操作的問題，且全同態算法允許在密文數據上執行任意的操作，并得到與明文下操作相同的結果。其缺陷在于當前全同態算法的執行效率低，時間開銷大，不具有實際應用價值。

2011年，MIT人工智能實驗室(CSAIL)研發了世界上首個可實際使用的開源密文數據庫系統—CryptDB[7]。該系統以中間代理的形式為數據庫提供加解密功能。與直接在明文數據庫中進行操作的時間相比，只增加了15%～20%的額外開銷。CryptDB對數據表全部字段進行加密后存儲在數據庫中，并且能夠直接在密文上執行SQL操作。由于CryptDB采用多層加密的洋蔥加密方案來加密數據，并把數據加密成多份以適用于多種檢索場景，所以其加密存儲對服務器的運算和存儲開銷是巨大的。為解決大規模數據加密時間開銷巨大的問題，選擇加密策略是一種可行的方法。2013年，Fu等[8]提出一種安全高效的云備份服務Pangolin，將選擇加密集成到數據壓縮中來保證敏感應用數據的安全性，以降低數據安全風險。2016年，張伯雍等[9]提出一種適用于移動終端的動態選擇加密方案，動態選擇加密算法對部分數據加密，既保護了數據隱私又提高了加密效率。

在數據庫存儲中，并不是所有的字段都是敏感的。對大量不敏感的字段進行加密，不僅不能增加數據表安全性，還耗費大量的加密時間和存儲空間。針對這些問題，文中提出了一種用戶自定義敏感字段檢測算法，并在CryptDB源碼的基礎上，通過創建及注冊明文洋蔥，修改元數據表和攔截及改寫自定義SQL語句，構建了一個支持選擇加密策略的CryptDB系統。該系統可對用戶指定的敏感字段進行加密，其余字段直接保存為明文。在保證原系統所有功能正常工作及滿足用戶對數據表安全性需求的基礎上，降低了加密的計算量和密文的存儲空間，從而增加了系統的實用性和靈活度。

2 選擇加密策略及實現

2.1 CryptDB密文數據庫系統

為支持不同的SQL操作，CryptDB系統將明文數據進行多層加密，每層使用不同加密算法，每種加密算法支持不同的SQL操作，且從內向外加密算法的安全等級越來越高。因其構造層次類似于洋蔥，所以又稱為洋蔥加密[7]。

CryptDB設計了四種洋蔥。其中，DET洋蔥(Onion Eq)支持對密文數據的等值比較操作，包含等值比較和等值連接操作；OPE洋蔥(Onion Ord)支持對密文數據的大小比較和排序等操作；HOM洋蔥(Onion Add)支持對密文數據的加法運算；SEARCH洋蔥(Onion Search)支持對密文數據的關鍵字匹配。即如要插入一個字段明文數據，經過Proxy的改寫之后，會將其轉化成上述的四個洋蔥即四個字段，然后再保存到數據庫中。基于優化的目的，對數值型數據不需要進行關鍵詞匹配，對字符型數據不需要進行加法操作。所以CryptDB對數值型數據只保存其DET洋蔥、OPE洋蔥和HOM洋蔥；而對字符型數據，除DET、OPE洋蔥外，只保存其SEARCH洋蔥(但實驗結果表明，在MIT官網下載公開的CryptDB的版本，對于字符型數據只會創建DET和OPE洋蔥，并不會創建SEARCH洋蔥)。

CryptDB對于不同表，不同列，不同洋蔥，不同的加密等級，使用的加密密鑰K也各不相同。加密密鑰K是由MK計算得到。其中，MK是主密鑰，保存在Proxy中，PRP是偽隨機序列[10]。計算公式如下所示：

K= PRPMK(tablet,columnc,oniono,layerl)

(1)

CryptDB對數據表中所有字段進行加密。設一張表有n個字段，每個字段可以表示成(attri,enci),i∈[1,n]。其中，attri表示第i個字段的屬性值；enci表示第i個字段是否加密且enci≡true。CryptDB的數據模型表示為：

MCryptDB={(attr1,true),(attr2,true),…,(attrn,true)}

(2)

2.2 數據模型

為比較具有選擇加密功能的CryptDB系統與原系統在功能及靈活性上的差異，設具有選擇加密功能CryptDB的數據模型為MSel-CryptDB。

定義1：SelectiveCryptDB數據模型。設表中有n個字段，SelectiveCryptDB的數據表中每一字段可以表示成(attri,enci)，則數據表模型表示為：

MSel-CryptDB={(attr1,enc1),(attr2,enc2),…， (attrn,encn)}

(3)

其中，attri表示第i個字段的屬性值；enci表示第i個字段是否加密且enci∈{true,false}，i∈[1,n]。

性質1：對于任意數值i∈[1,n]，都有MCryptDB?MSel-CryptDB成立。

證明：由定義1易得MCryptDB?MSel-CryptDB，即原系統是新系統的一個真子集。當且僅當∩enci=true(i∈[1,n])時，MCryptDB=MSel-CryptDB，綜上證得MCryptDB?MSel-CryptDB。

由性質1可得，SelectiveCryptDB系統不僅包含原系統的全部功能，還增加了系統靈活性，降低了系統存儲空間。可以根據用戶不同的需求，自由選擇字段進行加密，充分給予用戶自主性且能提高系統運行的效率。

2.3 策略實現

2.3.1 用戶自定義敏感字段檢測

表1 S參數等級

用戶可以根據自身的安全性需要，設置每個字段的安全等級Si、權重Pi、敏感閾值η、數據表安全等級Φset。計算出哪些字段是敏感的，并且當Φ≥Φset，即可認為達到用戶對數據表隱私保護的需求。如果當前的Φ<Φset，說明不能達到用戶對數據表安全等級的要求。那么，用戶必須動態調整Si和Pi，重新計算出敏感和非敏感字段，使得數據表的安全性達到用戶設定的安全等級，保證了選擇加密之后的數據表的安全性。

2.3.2 選擇加密算法

定義數據庫的選擇加密為用戶創建表時，可以指定需要加密和不需要加密的列[11]。對于指定要加密的部分，系統將一個字段加密成三個洋蔥保存在數據庫中。而對于非敏感數據即無需加密的部分，只為其創建明文洋蔥(oPlain)，該洋蔥直接將明文數據保存于數據庫，并且將該列所處的加密狀態保存于元數據表，為之后插入和檢索數據提供基礎信息。而對于敏感字段，元數據表記錄了當前各個洋蔥所處的加密等級等信息。在執行SQL操作之前，先查詢該元數據表，獲取各個字段是否加密，以及當前所處加密等級等信息，然后再利用獲取到的元數據信息對當前字段值進行相對應的加密。其偽代碼實現如算法1所示。選擇加密系統執行流程如圖1所示。

圖1 選擇加密系統執行流程

算法1：選擇加密算法SelectiveEncryption(sql)。

輸入：原始SQL語句；

輸出：加密后的SQL語句。

SelectiveEncryption(sql)

//LEX()函數對sql語句進行詞法解析

token←LEX(sql)

encsql←null

iftoken←CREATE_TABLE_CLAUSEthen

foreachk∈MSel-CryptDB

ifk.enc←TRUEthen

encsql←encsql+CreateEncryptOnion(k)

secretkey←CalcKey(table,onion,layer)

else

encsql←encsql+CreatePlainOnion(k)

secretkey←NULL

endif

WriteToMetaTable(k,secretkey)

endfor

elseiftoken←INSERT_CLAUSEthen

p←SearchMetaTable()

foreachp∈MSel-CryptDB

ifp.enc←TRUEthen

encsql←encsql+OnionEncrypt(p)

else

encsql←encsql+OnionPlaint(p)

endif

endfor

endif

returnencsql

3 系統性能分析

通過2.1節可知，對于數值型數據，CryptDB為其創建DET洋蔥、OPE洋蔥和HOM洋蔥；對于字符型數據，創建DET洋蔥和OPE洋蔥。

對于數值型數據，RND采用的是添加初始化向量IV的Blowfish算法，DET采用的是Blowfish加密算法，DETJOIN采用的是基于橢圓加密ECC的ECJoin算法。對于字符型數據，RND采用的是帶初始化向量IV(即salt值)處于CBC模式的AES加密算法，它能保證密文加密的隨機性，即相同明文加密后密文不相同；DET采用初始向量相同的CMC模式(即初始化向量都為“0”的CBC模式)AES加密算法，所以相同的明文加密后得到相同的密文；OPE采用mOPE加密算法；HOM采用Paillier加密算法。

設Blowfish加密算法的復雜度為RBlowfish，AES加密算法的復雜度為RAES，ECJoin加密算法的復雜度為RECJoin，mOPE加密算法的復雜度為RmOPE，HOM加密算法的復雜度為Rpaillier，n為待加密明文的規模。

對于數值型數據，DET洋蔥的復雜度為：

UDET_NUM=RECJoin+2RBlowfish

(4)

OPE洋蔥的復雜度為：

UOPE_NUM=RmOPE+RBlowfish

(5)

HOM洋蔥的復雜度為：

UHOM_NUM=Rpaillier

(6)

對于字符型數據，DET洋蔥的復雜度為：

UDET_STR=RECJoin+2RAES

(7)

OPE洋蔥的復雜度為：

UOPE_STR=RmOPE+RAES

(8)

由式(4)～(6)可知，加密一個數值型數據的復雜度為:

UNUM=UDET_NUM+UOPE_NUM+UHOM_NUM= RECJoin+3RBlowfish+RmOPE+Rpaillier

(9)

由式(7)、(8)可知，加密一個字符型數據的復雜度為：

USTR=UDET_STR+UOPE_STR=RECJoin+ 3RAES+RmOPE

(10)

由文獻[12]可知，ECJoin復雜度為O(n+logn)。由文獻[13-14]可知，AES，Blowfish，Paillier算法時間復雜度為O(n)。由文獻[10]可知，mOPE編碼的時間復雜度為O(logn)，且經過mOPE編碼之后，還需要對B樹上的葉子節點進行DET加密，所以mOPE算法的時間復雜度為O(n+logn)。

假設創建一張有N個字段的數據表，其中有X個數值型字段需要加密，Y個字符型字段需要加密。設執行一條Insert語句的通信時間為Ttrans，一個字段明文的計算時間為Tplain，設浮點計算的時間為Tfc。則

Tinsert(N,X,Y)={X·UNUM+Y·USTR+Ttrans+ (N-X-Y)·Tplain}·Tfc

(11)

當減少k(k∈[0,N])個數值型加密字段時，執行一條Insert語句的時間為：

Tinsert(N,X-k,Y)={(X-k)·UNUM+ Y·USTR+Ttrans+(N-(X-k)- Y)·Tplain}·Tfc

(12)

所以，減少k個數值型加密字段時，插入一條提高數據效率：

(13)

同理，減少k個字符型加密字段，插入一條提高數據效率：

(14)

在實際實驗中，為避免通信時間的影響，采用批處理方式進行插入。每次插入150條數據，所以Ttrans≈0。在較為理想的情況下，相對于加密時間，明文的計算時間可以忽略不計，即Tplain≈0。

綜上：

(15)

同理:

(16)

由式(15)和式(16)可以得出如下結論：插入語句執行效率的提高與加密字段的減少個數成正比。即在總字段不變的前提下，隨著加密字段數的減少，執行插入語句提高的效率是遞增的。

4 實 驗

4.1 實驗環境

文中實驗的硬件環境為：

CPU：Intel(R) Xeon E3，Memory為16 GB (2x8 GB) 1 333 MHz Dual Ranked RDIM；

Disk:1 TB 3.5-inch 7.2 K RPM SATA II Hard Drive。

軟件平臺為:ubuntu-12.04，CryptDB。

4.2 實驗方案

運行CryptDB密文數據庫系統，建立兩張表。第一張表中包含10個字段，字段均為int類型；第二張表包含10個字段，均為varchar類型。然后，通過軟件生成不同規模的insert語句。每條insert語句中每個字段的值隨機生成。規模分為三個等級：100條insert語句，1 000條insert語句，10 000條insert語句。

因為分為int和varchar類型兩張表，所以最終一共生成6個sql腳本文件。分別是：int-100.sql，int-1000.sql，int-10000.sql，varchar-100.sql，varchar-1000.sql，varchar-10000.sql。

通過為敏感字段檢測模塊設置不同的參數，動態計算出敏感與非敏感字段，分別運行上述六個測試腳本文件，記錄每個腳本的執行時間及存儲空間。

4.3 實驗數據及分析

分別運行int-100.sql，int-1000.sql，int-10000.sql三個腳本，并且記錄其運行時間和存儲空間，如表3所示。

表3 數值型數據插入時間及存儲空間

分別運行varchar-100.sql，varchar-1000.sql，varchar-10000.sql三個腳本，并且記錄其運行時間和存儲空間，如表4所示。

表4 字符型數據插入時間及存儲空間

由于數據庫按照設定的值進行增長，該數值不能設置太小。如果太小，則易產生碎片，并且影響IO性能。所以，兩個表存儲空間相差不大時，值可能相同，但是實際大小并不相同。所以，存儲空間表中的值是有一些誤差的。

表3和表4記錄了隨著加密字段數的減少，插入語句的加密時間和存儲空間變化。從中可以得到如下結論：

(1)隨著數據表中加密字段個數的減少，加密的時間和存儲空間顯著遞減。

(2)字符型數據的加密時間遠小于數值型數據的加密時間。這是由于數值型數據比字符型數據多創建一個HOM洋蔥。

(3)字符型數據加密之后所占存儲空間遠小于數據型的密文數據。這是由于HOM加密需占用較多的存儲空間。

圖2是在加密字段減少個數遞增的情況下，數值型數據插入語句效率提高的曲線圖。

圖2 數值型數據插入語句提高的效率

圖3是在加密字段減少個數遞增的情況下，字符型數據插入語句效率提高的曲線圖。

圖3 字符型數據插入語句提高的效率

從圖2和圖3的變化趨勢可以直觀看到，加密字段減少個數與插入語句提高的效率成正比，與之前的理論分析相符。

5 結束語

針對開源密文數據庫系統CryptDB必須對數據庫全部字段進行加密而導致性能過低的問題，提出了一種用戶自定義敏感字段檢測算法，在滿足用戶對數據表安全性需求的基礎上動態計算出敏感字段，并依此在CryptDB系統中實現選擇加密策略并且取得了理想的實驗結果。實驗結果表明，在保證原系統所有功能正常工作且不降低安全性的前提下，能夠提高密文計算的效率，使得執行插入語句提高的效率與加密字段減少的個數成正比，且能減少數據表存儲空間，增加CryptDB的實用性和靈活度。

未來的工作重點將圍繞以下幾點展開：將CryptDB部署在并行環境中，進一步提高密文計算效率；CryptDB中只支持對整形的加法，可以構造支持浮點計算的洋蔥，進一步完善CryptDB。

[1] 王于丁，楊家海，徐 聰，等.云計算訪問控制技術研究綜述[J].軟件學報，2015，26(5):1129-1150.

[2] Chor B,Goldreich O,Kushilevitz E,et al.Private information retrieval[J].Journal of the ACM,1998,45(6):965-981.

[3] Song D X,Wagner D,Perrig A.Practical techniques for searches on encrypted data[C]//IEEE symposium on security and privacy.[s.l.]:IEEE,2000:44-55.

[4] Li J,Wang Q,Wang C,et al.Fuzzy keyword search over encrypted data in cloud computing[C]//International conference on computer communications.New Jersey:IEEE Press,2010:441-445.

[5] Cao N,Wang C,Li M,et al.Privacy-preserving multi-keyword ranked search over encrypted cloud data[J].IEEE Transactions on Parallel and Distributed Systems,2014,8(6):222-233.

[6] Rivest R L,Adleman L,Dertouzos M L.On data banks and privacy homomorphisms[M]//Foundations of secure computation.New York:Academic Press,1978:169-179.

[7] Raluca A,Popa N,Zeldovich H,et al.CryptDB:a practical encrypted relational DBMS[R].[s.l.]:[s.n.],2011.

[8] Fu Y J,Xiao N,Liao X K,et al.Application-aware client-side data reduction and encryption of personal data in cloud backup services[J].Journal of Computer Science and Technology,2013,28(6):1012-1024.

[9] 張伯雍,何涇沙.基于安全策略的動態加密技術研究[J].電子設計工程,2016,24(5):19-21.

[10] Curino C A,Jones E P C,Popa R A,et al.Relational cloud:a database-as-a-service for the cloud[C]//Fifth Biennial conference on innovative data systems research.Asilomar,CA,USA:[s.n.],2011:235-240.

[11] Li M,Yang C,Tian J.Video selective encryption based on Hadoop platform[C]//IEEE international conference on computational intelligence and communication technology.[s.l.]:IEEE,2015:208-212.

[12] Popa R A,Li F H,Zeldovich N.An ideal-security protocol for order-preserving encoding[C]//IEEE symposium on security and privacy.[s.l.]:IEEE,2014:463-477.

[13] Liu B,Baas B M.Parallel AES encryption engines for many-core processor arrays[J].IEEE Transactions on Computers,2013,62(3):536-547.

[14] He X,Machanavajjhala A,Ding B.Blowfish privacy:tuning privacy-utility trade-offs using policies[C]//Proceedings of the 2014 ACM SIGMOD international conference on management of data.[s.l.]:ACM,2013:1447-1458.

Investigation on Selective Encryption Strategy with CryptDB

ZHANG Cheng-guo,YANG Geng,WANG Wei

(College of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In order to protect privacy of sensitive data stored on the cloud,encrypting data is a feasible way.Computing on the encrypted data without decrypting is becoming a research hotspot.Combining selective encryption strategy with CryptDB,an encrypted database system which supports selective encryption strategy is proposed to improve the performance of encrypting and decrease the storage space.Since the use of multiple onion encryption models,data should be encrypted into several copies by CryptDB to adapt different situations.Encrypting non-sensitive fields will experience high computation time and increase storage space.A user-defined sensitive field detection algorithm is proposed and implemented through creating and registering the plain onion within original system,modifying the metadata tables,and intercepting and revising the SQL queries.With the context meeting the user’s requirements of data security,the experimental results show that the scheme decreases the time of computation and storage space with the number of encrypted fields decreasing and makes the system more efficient and practical.

selective encryption;cipher computing;CryptDB;encrypted database;onion encryption

2016-05-22

2016-09-08

時間：2017-02-17

國家自然科學基金資助項目(61572263，61272084)

張成果(1991-)，男，碩士研究生，研究方向為密文數據庫、數據隱私保護；楊 庚，博士，教授，博士生導師，CCF高級會員，研究方向為網絡與信息安全、分布與并行計算、大數據隱私保護。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1634.088.html

TP302

A

1673-629X(2017)03-0136-06

10.3969/j.issn.1673-629X.2017.03.028