[cryptdb]2017/07/13--why your encrypted database is not secure

## [why your encrypted database is not secure](http://www.tuicool.com/articles/J3Qreiv)
## encrypted databases EDBs
encrypted data systems:CryptDB,Mylar,Arx and Seabed, CASB(Cloud Access Security Broker)
company:CipherCloud and SkyHighNetworks

>observations of query evaluations by persistent attackers can exploit the leakage of information from property-revealing encryption(PRE) schemes such as order-revealing encryption,deterministic encryption,and searchable encryption.

<br/>
>many EDBs claim security against snapshot attacks only.

## snapshot attack mechanisms
DBMS will have four state information:
- volatile DB state in RAM and CPU registers
- persistent DB state on disk
- volatile OS state
- persistent OS state

```
access to the disk,DBMS logs
access to query engine(SQL injection),DBMS diagnostic tables
access to memory,data structures and caches
```

## CryptDB:Processing Queries on an Encrypted Database
### 1.Introduction
理论上fully homomorphic encryption(全同态加密)可以使服务器计算任何functions over encrypted data.
CryptDB can execute a wide range of SQL queries over encrypted data.
大多数的SQL query use a small set of well-defined operators
CryptDB两个优点：

- 黑客进入DBMS server(利用漏洞直接获取到DBMS 权限，或者一个不受信任的DBA)
- 黑客获取application and DBMS servers，CryptDB只能给那些目前没有logged-in的用户数据提供保护，不过此篇文章目前不讨论这个问题，只讨论第一种威胁
![two threats of CryptDB](https://leanote.com/api/file/getImage?fileId=596c07fcab644114ba0006f5)

### 2. Threat Model and Overview
#### 2.1 Threat 1: DBMS server compromise
>proxy:
all queries must go through the proxy,the proxy stores a master secret key,which it uses to rewrite queries to execute on encrypted data.
proxy 加密解密所有数据，changes some query operators
<br/>
>DBMS server:
DBMS server 保持查询性能与数据量的平衡，可以通过UDF只执行authorized queries

```
>CryptDB有两项技术:
1)SQL-aware encryption 
use observation,most sql queries are made up of a well-defined set of basic operators,usch as(equ,ord compare,sum,join),CryptDB supports these operators over encrypted data.
By adapting known encryption schemes(for equality,additions,and order checks),and using a new privacy-preserving cryptographic scheme for joins.
CryptDB on encrypted data 支持这些细粒度的基本操作，比如equality checks,order comparisons,aggregates(sums) and joins.

依据事先知道的加密策略，using a new privacy-preserving cryptographic scheme for joins(把那些field 加密后重新组合)
2)adjustable query-based encryption
CryptDB carefully adjust the SQL-aware encryption scheme for any given data item to support different operations on this data.
为了不同的操作on SQL-aware encryption scheme 的data更有效率,CryptDB uses onions of encryption(洋葱加密)，存储了不同的密文(within each other)在数据库里
```
```
CryptDB 加密 data,the names of columns and tables,没有加密的是表结构，多少行，字段的数据类型，内容的大小(size of data in bytes)
泄露了每种操作(classes of computation)的columns,比如做排序，泄露order，equ check，泄露哪一行相等
```
#### 2.2 Threat 2:arbitrary threats
application server/proxy/DBMS server 都可能会被盗用，攻克，这时候黑客可能从proxy获得了master key which used to encrypted the entire databases.
数据通过多次加密，先是 a new key,然后是与用户密码相关的 key，那这样的话数据解密的话会经过a chain of keys.
如果这样的话，application 提供data privacy and sharing policy,CryptDB requires the developer to provice policy annotations over the application's SQL schema.
即使所有的服务器被攻克，logged-out user's keys 获取不到。

### 3. Queries over Encrypted Data
```
proxy  stores:
Master Key ,the database schema,the current encryption layer of each column
```

```
DBMS:
匿名的schema,加密的用户数据,一些附加的表 for CryptDB，optional UDFs(user-defined functions) that enable the DBMS server to compute on ciphertexts for certain operations.
```
> Processing a query in CryptDB involves four steps:
```
1)apllication 发起一个query,proxy 拦截and rewrites:
隐匿表名和列名，use MK 加密常量 with an ecnryption scheme best suited for the desired operation. the proxy also replaces certain operations with UDFs.
2)在执行query前，proxy 检测DBMS server是否要给keys适应加密层，if so,发起一个UPDATE query at DBMS server,which调用UDF to 某个对应columns的加密层

3)The proxy sends the encrypted query to the server,which executes it.

4)server returns the encrypted query result,which the proxy decrypts and returns to the application.

```
(对应第二步)
<center>
![update_ope](https://leanote.com/api/file/getImage?fileId=596c07fdab644114ba0006fa)
</center>
#### 3.1 SQL-aware encryption
- Randon(RND)
equal values are很大的可能性 mapped to different ciphertexts，缺点是计算话效率低下
数值：Blowfish
字符:AES(with a random initialization vector IV)

- Deterministic(DET)
相同的plaintext产生相同的密文，所以操作可以有equality predicates,equality joins,GROUPBY,COUT,DISTINCT
PRP伪随机，
数值:Blowfish
字符:AES
all in CMC mode.
- Order-preserving encryption(OPE)
order relations between data items based on their encrypted values,
```
$if: x < y,then OPE_{K}(x)<OPE_{K}(y),for any secret key K$
```
支持操作:
ORDER BY,MIN,MAX,SORT

OPE 与DET相比，是弱加密，因为它泄露了order信息，half of the data bits
- Homomrphic encryption(HOM)同态加密
a probabilistic encryption scheme as RND(和RND一样都是概率性加密方案)，但它允许在加密的数据上计算.
全同态加密is slow，但针对某些operations is efficient.
用的是Paillier cryptosystem
```
$HOM_{K}(x).HOM_{K}(y)=HOM_{K}(x+y)$
```
如果计算sum aggregates,the proxy replaces SUM with calls to a UDF that performs Paillier multiplication on a column encrypted with HOM.

- Join(Join and OPE-JOIN)

DET-Join but also enables the server to determine repeating values between two different columns.

- Word search(SEARCH)
SEARCH is nearly as secure as RND. 
operations:like
search currently supports only full word searches.
(目前已经支持模糊查询了)
从log上看like后面的constant常量并没有加密，与论文上有出入.
<center>
![search_like_query](https://leanote.com/api/file/getImage?fileId=596c07fcab644114ba0006f6)
</center>

<center>
![search_like_result](https://leanote.com/api/file/getImage?fileId=596c07fdab644114ba0006f8)
</center>

#### 3.2 Adjustable query-based encryption
- compare data or sort a column,the column should be encrypted with RND;  
- for columns that require equality checks but not order checks,DET suffices
- So we need an adaptive scheme that dynamically adjusts encryption strategies.
> *adjustable query-based encryption encryption:*
 encrypt each data item in one or more onions(each value is dressed in layers of increasingly stronger encryption)
 <center>
 ![onion](https://leanote.com/api/file/getImage?fileId=596c07fcab644114ba0006f3)
 </center>
 <center>
 ![encrypt database and onion adjust](https://leanote.com/api/file/getImage?fileId=596c07fcab644114ba0006f4)
 </center>
 each layer of each onion enables a certain class of computation.
 keys:
 each keys derived from MK
 $K_{t,c,o,l}=PRP_{MK}(table t, column c,onion o,layer l)$
 
 onion:
 每个洋葱最外层是最完全的,ORD and Eq最外层是RND,HOM for onion Add,SEARCH for onion search.
 
 剥洋葱：
 一些运算是在哪些layer层，通过发送key把不需要的洋葱层剥掉

CryptDB 洋葱层的解密通过UDFs，which run on the DBMS server,比如：
为了解密column 2 洋葱ord层，proxy发起下面的查询to the server,调用DECRYPT_RND UDF:
$UPDATE Table1 SET C2-Ord=DECRYPT_RND(K,C2-ORD,C2-IV)$

这时候proxy更新内部状态，知道the column C2-Ord in Table1 is now at layer OPE in the DBMS.
(tips:这时候再查询 order by,没有update)

<center>
![no_upate_order](https://leanote.com/api/file/getImage?fileId=596c07fdab644114ba0006f7)
</center>

<center>
![no_update_query](https://leanote.com/api/file/getImage?fileId=596c07fdab644114ba0006f9)
</center>
洋葱不会一直剥下去，其实去掉RND后DET OPE就是steady-state,这也是计算开销比较适中的原因

### 3.3 Executing over encrypted data
1)the proxy replaces column names in a query with corresponding onion names.

2)constant : a corresponding onion encryption of the constant
3)the proxy replaces certain operators with UDF-based couterparts.(HOM 求和就要算乘)

- Read query execution
阐述fig.3的整个过程
- Write query execution
support INSERT,DELETE,UPDATE
### 3.4 Computing joins
>only two kinds of joins supported:
- equi-joins
based on equality(DET)
理论上join的两个column必须加密with the same key
要join的那两列事先知道，所以 CryptDB can use the DET encryption scheme with the same key for each group of columns that are joined together.
如果事先不知道要join，恐怕不好办请用JOIN-ADJ(adjustable join)
- range_joins
based on order(OPE)
用的比较少

### 3.5 Other queries and limitations
certain computations CryptDB cannot support on encrypted data. for example
it doesn't support order comparison with a summation,such as `where salary>age+10`

## 4 Implementation
build on top of mysql-proxy/ a lua module
c++:

- query parser
 - a query encryptor/rewrite
 - a result decryption module

## 5 Experimental Evaluation
- what types of queries and applications does CryptDB support
- what is the level of security that CryptDB provides
- what is the performance impact of using CryptDB
phpBB/HotCRP/grad-apply/Open-EMR/TPC-c/trace
前面四个是选择sensitive的columns,后面的两个是加密整个数据库
phpBB  evaluate the overall performance and a detailed analysis through microbenchmarks on a query mix from TPC-C
### 5.1 Functional evaluation
- 支持大多数的queries，但有些column必须是plaintext的（因为加密后cannot be processed）数量很少,example:string manipulation(substring,lowercase
),date manipulation
- sql.mit.edu trace,support operations over all but 1094 of the 128,840 columns(除去出现比较少的 where having group by order by with limit， not aggregate operators, 571个column 不支持，99.5%支持)
571个中有222个bitwise operator(where clause and perform bitwise aggregation)
205个columns perform string processing in the WHERE clause
76 columns involved in mathematical transformations in the where clause
41 columns invoked the like operator

### 5.2 Security evaluation
定义MinEnc,check steady-state onion levels
RND/HOM > SEARCH > DET/Join > OPE
绝大部分都还是RND

### 5.3 Performance evaluation
mysql 5.1.54

#### 5.3.1 TPC-C
两个性能指标:

- database server throughput(number of queries per second that server can process)
26% lower that that with plain MYSQL on TPC-C
- latency(time interval from when the application issues a query to when it receives the result)
0.12ms 0.1ms
24% mysql-proxy
23% encryption and decryption
53% parsing and processing

### 6 RELATED WORK

信息安全从业人员^_^

导航

最近发表

友情链接