Cryptdb原理概述（1）

Cryptdb[1]是MIT的CSAIL 在11年sosp上提出的, 其在数据库上实现了同态加密技术. 本⽂基于⼀些相关⽂献, 以及对代码的调研, 对该系统的实现原理以及相关的技术做介绍.

同态加密

加密是⼀种保证数据安全的⽅法, 但是数据加密以后, 对于数据进⾏操作就变的复杂了. 举例来说, 我对两个数字A和B进⾏了加密存储, 分别变成了A’和B’, 现在我们有⼀个计算两个数的和的需求, 也就是需要计算A+B.那么⼀般来说, 我们需要拿到密钥以及密⽂A’和B’, 然后解密出原始的数据A和B, 进⾏加法计算, 获得A+B=C, 然后对C进⾏加密变成C’, 最后对加密结果进⾏存储.

假设我们的数据存在服务器上, 客户端给服务器发送请求来获取数据. 那么上述的过程就存在问题. 如果我们的数据在服务器端解密并且返回给客户端, 那么服务器段就获取了密钥, 从⽽存在服务器上的加密数据的安全性不能的到保证. 如果我们把密⽂拉到客户端, 然后由客户端进⾏加法计算, 那么就⽆法利⽤服务端的计算能⼒, 服务器只承担存储的功能, 这在计算量⽐较⼤的时候, 是⽆法实现的.

同态加密[3]的出现, 解决了上述问题. 同态加密算法允许对密⽂直接进⾏计算, 获得加密的结果. 这样, 对于上述的例⼦, 我们可以直接从A’,B’获得加密的计算结果C’, 然后把C’返回给⽤户. 这样, 我们不会把密钥暴露给服务器, ⼜可以利⽤服务器的计算能⼒, 客户端只要负责对数据进⾏解密就可以了.

09年的时候, Gentry[2]提出了全同态加密算法, 也就是可以对密⽂进⾏任意的操作. 这篇⽂章证明了全同态加密是理论上可⾏的, 但是全同态加密复杂度很⾼, 不能在实际系统中使⽤.

但是, 如果我们只是要求部分的加密操作, ⽽不是想对加密数据进⾏任意的操作, 是不是有复杂度低的算法, 可以满⾜实际系统的需求呢? Cryptdb就是基于这种思想提出的, 对于数据库来说, 常见的操作不多, 如果只是⽀持⼀部分的加密操作, 复杂度是可以接受的.

激光模组Cryptdb

Cryptdb 希望在数据库系统上实现加密运算, 达到的效果是: 存在数据库中的数据全部是加密的, 但数据库依然可以对加密的数据执⾏⽤户的SQL语句, 返回加密的数据给⽤户, 然后⽤户可以对返回的结果进⾏解密, 获得明⽂的数据. 其基于的思想是, 全同态加密难以实⽤, 但对于数据库来说, 只要求⼏种常见的运算, 不需要任意的运算. 举例来说, 对于普通的select 语句中的where条件, 需要⽐较相等的运算. 对于order by, 需要⽐较⼤⼩的运算, 对于⼀些函数如SUM, 需要加法运算. 如果只是⽀持这些常见的操作, 就可以在吞吐量下降20%的开销的情况下, 满⾜⼤部分的SQL查询.

系统组成模型

Cryptdb系统可以分为三个部分: Client, MySQL-Proxy, 以及MySQL-SERVER. 其主要逻辑实现在MySQL-Proxy, 对于MySQL-SERVER则是通过UDF来完成⼀些辅助的功能.

MySQL-Proxy能够获取⽤户发送的SQL请求, 并进⾏中间的处理, 然后将处理以后的请求发送给MySQL-SERVER. 请求在服务器上执⾏完成以后, 结果也会经过MySQL-Proxy的处理, 然后返回给客户端.

所以, Cryptdb的基本想法是, 在MySQL-Proxy处对⽤户的SQL的关键字段请求进⾏加密，并且依然保证SQL语句的语法要求, 然后发送给MySQL-SERVER, 处理完成以后, MySQL-SERVER返回加密的数据给MySQL-PROXY, 在Proxy处解密, 然后返回给客户端.

鸽钟加密查询的⽀持

有了上⾯的系统模型, 我们已经可以对插⼊的数据进⾏加密, 下⾯通过例⼦说明如何在这种条件下实现加密数据的查询.

假设我们有如下的数据表:

Name Age GPA

Tom1285

Jerry1387

Alice1488

Jack1385

通过加密, 我们获得了同等条件的如下表格.

Name Age GPA

x?!*~/\^^(┐「ε:)(:3 」∠)( ·_·) (·ᴗ·)وヽ( ·◇·)？ヽ(´Д｀) (｀ ω ´) (´ ω ｀)（´∀｀*) （＾∀＾）

(╯‵□′)╯︵┻━┻(ノ｀Д´)ノ￣⼯￣lll） (﹁”﹁)

(´Д｀)o(*≧▽≦)ツ[]~(￣▽￣)~*

对于这样⼀张加密以后的数据表, 即使别⼈获取了数据库内容, 在没有密钥的情况下也不能知道⾥⾯的数据是什么. 那么, 对于通过认证的⽤户, 如何正确处理⽤户的请求? ⽐如⽤户现在需要所有GPA⼤于87的学⽣的信息, 如何在上⾯的表格中完成查, 且不对MySQL-SERVER 进⾏代码上的修改?

透明填充母料

我们有如下的原始语句:

SELECT * from student where GPA > 87;

这个语句由客户端发出, ⾸先到达MySQL-Proxy, 由于数据已经被加密了，所以如果这个语句直接发到数据库上执⾏, 是不能返回正确的结果的, 在MySQL-Proxy处, ⾸先要进⾏处理. 观察上⾯的表格, 我们发现87加密以后的结果是: （´∀｀*) （＾∀＾）所以, 在MySQL-Proxy处，对SQL语句进⾏处理, 将87进⾏加密, 加密以后的SQL语句就变成了:

智能美甲SELECT * from student where GPA >（´∀｀*) （＾∀＾）

这样, MySQL-SERVER会执⾏修改以后的SQL语句, 并且返回加密后的结果, MySQL-Proxy获得加密以后的结果, 解密, 然后返回给客户端.

上⾯的过程涉及⼀个问题, 就是GPA >（´∀｀*) （＾∀＾), 如何能够保证返回GPA⼤于87的所有数据. 这就需要⽤到OPE(order

preserving encryption). 这种算法本⾝能够保证, 加密前后, 数据的相对顺序保持⼀致. 也就是说, 加密前有A

洋葱存储模型

上⾯的例⼦中, OPE算法可以⽀持⼤⼩⽐较, DET算法可以⽀持两个数是否想等的⽐较, HOM可以⽀持加法. 但是没有⼀种算法可以同时⽀持多种操作, 所以依然是上⾯的表格, 如果我们需要同时⽀持加法和⼤⼩⽐较的操作, 就必须另外想办法处理. 在论⽂中提出的⽅法是多洋葱模型, 简单来说, 就是对于GPA这列数据, ⽤不同的算法存储多次, 需要哪种操作, 就选择哪种算法加密的列进⾏处理.

下⾯给出论⽂中的例⼦:

如图所⽰, 原始的Employees表有两列, 上⾯的四个层次化的洋葱模型, 分别可以⽀持不同的加密操作. 其中Onion Eq⽀持相等⽐较的操作, Onion Ord⽀持⼤⼩⽐较, Onion Add⽀持加法, ⽽Onion Search ⽀持LIKE的搜索. 所以为了⽀持不同的操作, 原始的列ID被存储成了四列,⼀个洋葱存⼀列. 这样, 要对ID进⾏加法操作, 就转换成对加密表的C1-Add列进⾏操作, 要对ID列进⾏排序操作, 则转换成对C1-Ord列进⾏操作, 这个转化就是通过MySQL-Proxy来完成. 由于ID是整数, 不需要⽀持search 操作, 所以也就没有进⾏存储.

还有⼀个问题, 就是为什么要多层次的加密? 这主要是为了保证数据的安全性, 同时保证能够⽀持加密操作，是⼀种折中的设计. ⼀开始所有的洋葱都是处于RND层次, 也就是加密等级最⾼的层次. 在这个

层次, 没有DET和OPE的性质, 不能⽀持相应的操作. 如果某⼀次⽤户需要OPE 或者DET的⾏为, 就对这⼀列数据进⾏解密, 解密到DET或者OPE的层次, 然后再进⾏处理. 这个剥洋葱的过程, 可以由MySQL-SERVER来完成, 因为这种解密不会暴露明⽂给服务器.

所以, 对于上述的表格, 如果我们执⾏如下的插⼊语句:

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

则会根据洋葱模型扩展成:

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

每个字段都是经过层次化的加密的. 需要注意的是, 在Cryptdb的最新实现中, SEARCH并没有被实现.

总结

Cryptdb是⼀种数据库加密代理, 其截获⽤户的SQL语句, 进⾏加密操作, 然后给数据库发送加密以后的SQL语句, 这样数据库服务器不能获得明⽂数据. 其通过特殊的加密算法, 使得数据库服务器能够对加密数据进⾏处理, 返回加密的结果. 在数据存储上, 做了⼀定的优化, 采⽤了洋葱加密模型, ⼀开始处于最强的加密层次, 在需要⽀持某类操作的时候, 才进⾏部分解密, 到达能够⽀持特定操作的层次.