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 |
|---|---|---|
| Tom | 12 | 85 |
| Jerry | 13 | 87 |
| Alice | 14 | 88 |
| Jack | 13 | 85 |
通过加密, 我们获得了同等条件的如下表格.
| Name | Age | GPA |
|---|---|---|
| x?!*~/^^ | (┐「ε:) (:3 」∠) | (ง •̀_•́)ง (•̀ᴗ•́)و ̑̑ ヽ |
| ( ・◇・)？ ヽ(´Д｀)ﾉ | (｀･ω･´) (´･ω･｀) | （´∀｀*) （＾∀＾） |
| (╯‵□′)╯︵┻━┻ | (ノ｀Д´)ノ | ￣工￣lll） (﹁”﹁) |
| (´Д｀) | o(*≧▽≦)ツ | [] |
对于这样一张加密以后的数据表, 即使别人获取了数据库内容, 在没有密钥的情况下也不能知道里面的数据是什么. 那么, 对于通过认证的用户, 如何正确处理用户的请求? 比如用户现在需要所有GPA大于87的学生的信息, 如何在上面的表格中完成查找, 且不对MySQL-SERVER 进行代码上的修改?
我们有如下的原始语句:
1 | SELECT * from student where GPA > 87; |
这个语句由客户端发出, 首先到达MySQL-Proxy, 由于数据已经被加密了,所以如果这个语句直接发到数据库上执行, 是不能返回正确的结果的, 在MySQL-Proxy处, 首先要进行处理. 观察上面的表格, 我们发现87加密以后的结果是: （´∀｀*) （＾∀＾） 所以, 在MySQL-Proxy处, 对SQL语句进行处理, 将87进行加密, 加密以后的SQL语句就变成了:
1 | SELECT * from student where GPA >（´∀｀*) （＾∀＾） |
这样, MySQL-SERVER会执行修改以后的SQL语句, 并且返回加密后的结果, MySQL-Proxy获得加密以后的结果, 解密, 然后返回给客户端.
上面的过程涉及一个问题, 就是GPA >（´∀｀*) （＾∀＾), 如何能够保证返回GPA大于87的所有数据. 这就需要用到OPE(order preserving encryption). 这种算法本身能够保证, 加密前后, 数据的相对顺序保持一致. 也就是说, 加密前有A<B, 那么加密后也保证A’<B’. 上面例子中的算法显然不满足OPE的性质, 所以实际的处理不能基于上面的算法.
能够处理 >的请求以后, 自然也可以处理 = 的请求了. 事实上, OPE的算法虽然没有暴露明文, 但是数据的相对顺序暴露给了攻击者, 所以安全性较低. 如果仅仅需要处理Where GPA = 87的情况, 可以对数据列采用DET方法加密, 这种算法保证相同的明文加密可以的到相同的密文, 但是并不保证相对顺序不变, 这样安全性更高.
如果需要支持加法或者乘法操作, 则需要使用HOM也即同态加密. 数据列通过这类算法加密以后, 就可以在加密的情况下进行加法和乘法的操作, 并且返回结果给MySQL-Proxy, 然后MySQL-Proxy可以将数据解密返回给客户端.
洋葱存储模型
上面的例子中, 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来完成, 因为这种解密不会暴露明文给服务器.
所以, 对于上述的表格, 如果我们执行如下的插入语句:
1 | INSERT INTO Employees values(1,"zhangfei"); |
则会根据洋葱模型扩展成:
1 | 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语句, 这样数据库服务器不能获得明文数据. 其通过特殊的加密算法, 使得数据库服务器能够对加密数据进行处理, 返回加密的结果. 在数据存储上, 做了一定的优化, 采用了洋葱加密模型, 一开始处于最强的加密层次, 在需要支持某类操作的时候, 才进行部分解密, 到达能够支持特定操作的层次.
本文是Cryptdb的设计与实现的第一篇,后续内容会不断在我的博客 https://yiwenshao.github.io/ 更新, 也可以关注我的简书或CSDN博客, 内容会做同步.
相关文献
[1]. Popa, Raluca Ada, et al. “CryptDB: protecting confidentiality with encrypted query processing.” Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 2011.
[2]. Gentry, Craig. “Fully homomorphic encryption using ideal lattices.” STOC. Vol. 9. No. 2009. 2009.
[3]. wiki 同态加密