Cryptdb原理概述(1)

Cryptdb[1]是MIT的CSAIL 在11年sosp上提出的, 其在數(shù)據(jù)庫上實現(xiàn)了同態(tài)加密技術(shù). 本文基于一些相關(guān)文獻, 以及對代碼的調(diào)研, 對該系統(tǒng)的實現(xiàn)原理以及相關(guān)的技術(shù)做介紹.

同態(tài)加密

加密是一種保證數(shù)據(jù)安全的方法, 但是數(shù)據(jù)加密以后, 對于數(shù)據(jù)進行操作就變的復(fù)雜了. 舉例來說, 我對兩個數(shù)字A和B進行了加密存儲, 分別變成了A'和B', 現(xiàn)在我們有一個計算兩個數(shù)的和的需求, 也就是需要計算A+B.那么一般來說, 我們需要拿到密鑰以及密文A'和B', 然后解密出原始的數(shù)據(jù)A和B, 進行加法計算, 獲得A+B=C, 然后對C進行加密變成C', 最后對加密結(jié)果進行存儲.

假設(shè)我們的數(shù)據(jù)存在服務(wù)器上, 客戶端給服務(wù)器發(fā)送請求來獲取數(shù)據(jù). 那么上述的過程就存在問題. 如果我們的數(shù)據(jù)在服務(wù)器端解密并且返回給客戶端, 那么服務(wù)器段就獲取了密鑰, 從而存在服務(wù)器上的加密數(shù)據(jù)的安全性不能的到保證. 如果我們把密文拉到客戶端, 然后由客戶端進行加法計算, 那么就無法利用服務(wù)端的計算能力, 服務(wù)器只承擔(dān)存儲的功能, 這在計算量比較大的時候, 是無法實現(xiàn)的.

同態(tài)加密[3]的出現(xiàn), 解決了上述問題. 同態(tài)加密算法允許對密文直接進行計算, 獲得加密的結(jié)果. 這樣, 對于上述的例子, 我們可以直接從A',B'獲得加密的計算結(jié)果C', 然后把C'返回給用戶. 這樣, 我們不會把密鑰暴露給服務(wù)器, 又可以利用服務(wù)器的計算能力, 客戶端只要負(fù)責(zé)對數(shù)據(jù)進行解密就可以了.

09年的時候, Gentry[2]提出了全同態(tài)加密算法, 也就是可以對密文進行任意的操作. 這篇文章證明了全同態(tài)加密是理論上可行的, 但是全同態(tài)加密復(fù)雜度很高, 不能在實際系統(tǒng)中使用.

但是, 如果我們只是要求部分的加密操作, 而不是想對加密數(shù)據(jù)進行任意的操作, 是不是有復(fù)雜度低的算法, 可以滿足實際系統(tǒng)的需求呢? Cryptdb就是基于這種思想提出的, 對于數(shù)據(jù)庫來說, 常見的操作不多, 如果只是支持一部分的加密操作, 復(fù)雜度是可以接受的.

Cryptdb

Cryptdb 希望在數(shù)據(jù)庫系統(tǒng)上實現(xiàn)加密運算, 達到的效果是: 存在數(shù)據(jù)庫中的數(shù)據(jù)全部是加密的, 但數(shù)據(jù)庫依然可以對加密的數(shù)據(jù)執(zhí)行用戶的SQL語句, 返回加密的數(shù)據(jù)給用戶, 然后用戶可以對返回的結(jié)果進行解密, 獲得明文的數(shù)據(jù). 其基于的思想是, 全同態(tài)加密難以實用, 但對于數(shù)據(jù)庫來說, 只要求幾種常見的運算, 不需要任意的運算. 舉例來說, 對于普通的select 語句中的where條件, 需要比較相等的運算. 對于order by, 需要比較大小的運算, 對于一些函數(shù)如SUM, 需要加法運算. 如果只是支持這些常見的操作, 就可以在吞吐量下降20%的開銷的情況下, 滿足大部分的SQL查詢.

系統(tǒng)組成模型

Cryptdb系統(tǒng)可以分為三個部分: Client, MySQL-Proxy, 以及MySQL-SERVER. 其主要邏輯實現(xiàn)在MySQL-Proxy, 對于MySQL-SERVER則是通過UDF來完成一些輔助的功能.

MySQL-Proxy能夠獲取用戶發(fā)送的SQL請求, 并進行中間的處理, 然后將處理以后的請求發(fā)送給MySQL-SERVER. 請求在服務(wù)器上執(zhí)行完成以后, 結(jié)果也會經(jīng)過MySQL-Proxy的處理, 然后返回給客戶端.

所以, Cryptdb的基本想法是, 在MySQL-Proxy處對用戶的SQL的關(guān)鍵字段請求進行加密,并且依然保證SQL語句的語法要求, 然后發(fā)送給MySQL-SERVER, 處理完成以后, MySQL-SERVER返回加密的數(shù)據(jù)給MySQL-PROXY, 在Proxy處解密, 然后返回給客戶端.

加密查詢的支持

有了上面的系統(tǒng)模型, 我們已經(jīng)可以對插入的數(shù)據(jù)進行加密, 下面通過例子說明如何在這種條件下實現(xiàn)加密數(shù)據(jù)的查詢.

假設(shè)我們有如下的數(shù)據(jù)表:

Name	Age	GPA
Tom	12	85
Jerry	13	87
Alice	14	88
Jack	13	85

通過加密, 我們獲得了同等條件的如下表格.

Name	Age	GPA
x?!*~/^^	(┐「ε:) (:3 」∠)	(? ??_??)? (?????)? ?? ヽ
( ?◇?)？ヽ(′Д｀)?	(｀?ω?′) (′?ω?｀)	（′?｀*) （＾?＾）
(╯‵□′)╯︵┻━┻	(ノ｀Д′)ノ	￣工￣lll） (﹁"﹁)
(′Д｀)	o(*≧▽≦)ツ	[]_(￣▽￣)*

對于這樣一張加密以后的數(shù)據(jù)表, 即使別人獲取了數(shù)據(jù)庫內(nèi)容, 在沒有密鑰的情況下也不能知道里面的數(shù)據(jù)是什么. 那么, 對于通過認(rèn)證的用戶, 如何正確處理用戶的請求? 比如用戶現(xiàn)在需要所有GPA大于87的學(xué)生的信息, 如何在上面的表格中完成查找, 且不對MySQL-SERVER 進行代碼上的修改?

我們有如下的原始語句:

SELECT * from student where GPA > 87;

這個語句由客戶端發(fā)出, 首先到達MySQL-Proxy, 由于數(shù)據(jù)已經(jīng)被加密了,所以如果這個語句直接發(fā)到數(shù)據(jù)庫上執(zhí)行, 是不能返回正確的結(jié)果的, 在MySQL-Proxy處, 首先要進行處理. 觀察上面的表格, 我們發(fā)現(xiàn)87加密以后的結(jié)果是: （′?｀*) （＾?＾）所以, 在MySQL-Proxy處, 對SQL語句進行處理, 將87進行加密, 加密以后的SQL語句就變成了:

 SELECT * from student where GPA  >（′?｀*) （＾?＾）

這樣, MySQL-SERVER會執(zhí)行修改以后的SQL語句, 并且返回加密后的結(jié)果, MySQL-Proxy獲得加密以后的結(jié)果, 解密, 然后返回給客戶端.

上面的過程涉及一個問題, 就是GPA >（′?｀*) （＾?＾), 如何能夠保證返回GPA大于87的所有數(shù)據(jù). 這就需要用到OPE(order preserving encryption). 這種算法本身能夠保證, 加密前后, 數(shù)據(jù)的相對順序保持一致. 也就是說, 加密前有A<B, 那么加密后也保證A'<B'. 上面例子中的算法顯然不滿足OPE的性質(zhì), 所以實際的處理不能基于上面的算法.

能夠處理 >的請求以后, 自然也可以處理 = 的請求了. 事實上, OPE的算法雖然沒有暴露明文, 但是數(shù)據(jù)的相對順序暴露給了攻擊者, 所以安全性較低. 如果僅僅需要處理Where GPA = 87的情況, 可以對數(shù)據(jù)列采用DET方法加密, 這種算法保證相同的明文加密可以的到相同的密文, 但是并不保證相對順序不變, 這樣安全性更高.

如果需要支持加法或者乘法操作, 則需要使用HOM也即同態(tài)加密. 數(shù)據(jù)列通過這類算法加密以后, 就可以在加密的情況下進行加法和乘法的操作, 并且返回結(jié)果給MySQL-Proxy, 然后MySQL-Proxy可以將數(shù)據(jù)解密返回給客戶端.

洋蔥存儲模型

上面的例子中, OPE算法可以支持大小比較, DET算法可以支持兩個數(shù)是否想等的比較, HOM可以支持加法. 但是沒有一種算法可以同時支持多種操作, 所以依然是上面的表格, 如果我們需要同時支持加法和大小比較的操作, 就必須另外想辦法處理. 在論文中提出的方法是多洋蔥模型, 簡單來說, 就是對于GPA這列數(shù)據(jù), 用不同的算法存儲多次, 需要哪種操作, 就選擇哪種算法加密的列進行處理.

下面給出論文中的例子:

如圖所示, 原始的Employees表有兩列, 上面的四個層次化的洋蔥模型, 分別可以支持不同的加密操作. 其中Onion Eq支持相等比較的操作, Onion Ord支持大小比較, Onion Add支持加法, 而Onion Search 支持LIKE的搜索. 所以為了支持不同的操作, 原始的列ID被存儲成了四列, 一個洋蔥存一列. 這樣, 要對ID進行加法操作, 就轉(zhuǎn)換成對加密表的C1-Add列進行操作, 要對ID列進行排序操作, 則轉(zhuǎn)換成對C1-Ord列進行操作, 這個轉(zhuǎn)化就是通過MySQL-Proxy來完成. 由于ID是整數(shù), 不需要支持search 操作, 所以也就沒有進行存儲.

還有一個問題, 就是為什么要多層次的加密? 這主要是為了保證數(shù)據(jù)的安全性, 同時保證能夠支持加密操作,是一種折中的設(shè)計. 一開始所有的洋蔥都是處于RND層次, 也就是加密等級最高的層次. 在這個層次, 沒有DET和OPE的性質(zhì), 不能支持相應(yīng)的操作. 如果某一次用戶需要OPE或者DET的行為, 就對這一列數(shù)據(jù)進行解密, 解密到DET或者OPE的層次, 然后再進行處理. 這個剝洋蔥的過程, 可以由MySQL-SERVER來完成, 因為這種解密不會暴露明文給服務(wù)器.

所以, 對于上述的表格, 如果我們執(zhí)行如下的插入語句:

INSERT INTO Employees values(1,"zhangfei");

則會根據(jù)洋蔥模型擴展成:

INSERT INTO Employees values(C1-IV,C1-EQ,C1-ORD,C1-ADD,C2-IV,C2-EQ,C2-ORD,C2-SEARCH);

每個字段都是經(jīng)過層次化的加密的. 需要注意的是, 在Cryptdb的最新實現(xiàn)中, SEARCH并沒有被實現(xiàn).

總結(jié)

Cryptdb是一種數(shù)據(jù)庫加密代理, 其截獲用戶的SQL語句, 進行加密操作, 然后給數(shù)據(jù)庫發(fā)送加密以后的SQL語句, 這樣數(shù)據(jù)庫服務(wù)器不能獲得明文數(shù)據(jù). 其通過特殊的加密算法, 使得數(shù)據(jù)庫服務(wù)器能夠?qū)用軘?shù)據(jù)進行處理, 返回加密的結(jié)果. 在數(shù)據(jù)存儲上, 做了一定的優(yōu)化, 采用了洋蔥加密模型, 一開始處于最強的加密層次, 在需要支持某類操作的時候, 才進行部分解密, 到達能夠支持特定操作的層次.

本文是Cryptdb的設(shè)計與實現(xiàn)的第一篇,后續(xù)內(nèi)容會不斷在我的博客 https://yiwenshao.github.io/ 更新, 也可以關(guān)注我的簡書或CSDN博客, 內(nèi)容會做同步.