Transcript PowerPoint ****

Network Security
CryptDB:
Confidentiality with Encrypted Query Processing
Raluca Ada Popa, Catherine M. S. Redfield,
Nickolai Zeldovich, and Hari Balakrishnan
MIT CSAIL
1 Intro
1 Intro
Theft of private information
Threat 2: any attacks on all servers
Threat 1: passive
DB server attacks
User 1
User 2
Application
User 3
SQL
DB Server
System
administrator
Hackers
1 Intro
Previous solution
1. Encrypt sensitive data and run all computations on clients
• Difficult to convert to this form
2. Theoretical solutions such as fully homomorphic encryption
• Allow server to compute arbitrary function over
encrypted data
• Computationally expensive
1 cryptDB

Goal: protect confidentiality of data
Threat 2: any attacks on all servers
Threat 1: passive
DB server attacks
User 1
User 2
Application
User 3
Hackers
SQL
DB Server
System
administrator
1. Process SQL queries on encrypted data
2. Use fine-grained keys; chain these keys to user passwords
based on access control
2 Overview
2 Over view
Application
plain query
decrypted results
Proxy
transformed query
DB Server
encrypted results
Encrypted DB
Stores schema, master key
 No data storage
 No query execution

Process queries completely
at the DBMS, on encrypted
database

Application server
1.
2.
Runs the application code and issues DBMS queries on behalf of one or more users
Is modified so that it provides the db proxy with encryption keys
DBMS server
1.
2.
3.
All its data is encrypted (including table and column names)
Cluelessly processes encrypted data as if it were unencrypted
Has user defined functions (UDFs) installed to allow it to compute on ciphertexts for
certain operations
2 Over view
Application
plain query
decrypted results
Proxy
transformed query
DB Server
encrypted results
Encrypted DB
Stores schema, master key
 No data storage
 No query execution

Process queries completely
at the DBMS, on encrypted
database

Database proxy
1.
2.
3.
4.
5.
Runs the application code and issues DBMS queries on behalf of one or more users
Encrypts queries received from application and sends them to DBMS
Changes some query operators if necessary, while preserving query's semantics
Decrypts DBMS returned results and send them to the application
Decides the key to be used for encrypting/decrypting each data item
2 Over view
Application
plain query
Proxy
decrypted results
transformed query
DB Server
encrypted results
Encrypted DB
Stores schema, master key
 No data storage
 No query execution

Processing a query:
1.
2.
3.
4.
5.
Process queries completely
at the DBMS, on encrypted
database

Database proxy intercepts application’s query and rewrites it by anonymizing table
and column names & encrypting constants with the key of the encryption scheme
best suited for the operation and the user
Database proxy checks if the DBMS needs to adjust encryption level before
executing the query
- if yes  issue an UPDATE query that invokes a UDF to adjust the encryption level
layer of the appropriate columns
Database proxy sends the encrypted query to the DBMS server
DBMS executes query using standard SQL (invoking UDFs for aggregation or
keyword searches) and returns the encrypted results
Database proxy intercepts and decrypts results, and sends them to the application
3
Queries over
encrypted data
3
Queries over
encr ypt ed dat a
Onions of Encryption
SEARCH
text value
RND
DET
JOIN
RND
OPE
OPE-JOIN
value
value
Onion Search
HOM
int value
Onion Equality
Onion Order
Onion Add
1. Each onion is best suited for a different SQL operator
2. Listed from strong to weak
3
Queries over
encr ypt ed dat a
Table created by DBMS server
Each application column is expanded into multiple columns
Replace column name with corresponding onion names
Replace constant in the query with onion encryption of that constant
Repalce certain operators with UDF-based counterparts
3
Queries over
encr ypt ed dat a
Example
SELECT ID FROM Employees WHERE Name = ‘Alice’
Lowering the encryption of Name to layer DET
UPDATE Table1
SET C2-Eq = DECRYPT RND(KeyT1,C2,Eq,RND, C2-Eq, C2-IV)
Rewrite the request
SELECT C1-Eq, C1-IV FROM Table1 WHERE C2-Eq = x7b3d
Receive encrypted RND level result and decrypts it to constant
3
Queries over
encrypted data
Computing Joins
• Equi-joins: join predicate is based on equality
A=B
• Range joins: involve order checks
A<B
3
Queries over
encrypted data
Equi-joins (requirements)
• Columns to be joined should be encrypted with the same key, so that
the server can see matching values between them
• Columns never to be joined should not be encrypted with the same
key, so that the server cannot join columns which are not requested
3
Queries over
encrypted data
Equi-joins (special case)
• Columns to be joined are known a priori, CryptDB can use DET
encryption scheme with the same key for them
• However, this seldom happens
3
Queries over
encrypted data
Equi-joins (using JOIN-ADJ)
• allows the server to adjust the key of each column at runtime
• A keyed cryptographic hash with the additional property that hashes
can be adjusted to change their key without access to the plaintext
3
Queries over
encrypted data
JOIN encryption scheme
JOIN(v) = JOIN-ADJ(v) || DET(v)
Why in this form?
1. Allow the proxy to decrypt DET component to obtain v
2. Allow the server to check two JOIN values for equality by comparing
the JOIN-ADJ components
3
Queries over
encrypted data
JOIN encryption scheme (Working
Details)
1. Initially, each column is encrypted at the JOIN layer with a different
key
2. When a join is requested, the proxy gives the server an onion key to
adjust the JOIN-ADJ values in one column to match the other column
3. Columns to be joined now share the same JOIN-ADJ key, allowing
the server to join them
4. JOIN-ADJ values are kept after adjustments
3
Queries over
encrypted data
JOIN encryption scheme (Working
Details)
4
Multiple
Principals
Threat Model
4
Multiple
Principals
Application infrastructure and proxy are also untrusted.
A Scenerio
phpBB: a popular online web forum.
In phpBB, each user has an account and a password, belongs to
certain groups, and can send private messages to other users.
Depending on their groups’permissions, users can read entire
forums, only forum names, or not be able to read a forum at all.
Working Process
4
Multiple
Principals
1. Each user has a key(password).
2. CryptDB derives many encryption keys from the original key and
encrypt different data items with different keys to enforce the access
control policy.
3. All the keys are deleted after the user have logged out.
Policy Annotations
4
Multiple
Principals
Application developer must annotate the schema of a database by
specifying, for any subset of data items, which principal has access to it.
Principal
A principal is an entity, such as a user or a group.
Each SQL query involving an annotated data item requires the privilege
of the corresponding principal.
PRINCTYPE
4
Multiple
Principals
Define the principal types used in the application, such as users, groups,
or messages.
External principal，
correspond to end users who explicitly authenticate themselves to
the application using a password.
Internal principal,
intermediate variable to maintain system integrity and security.
Privileges of internal principals can be acquired only through
delegation.
ENC_FOR
4
Multiple
Principals
Specify which columns in the SQL schema contain sensitive data, along
with the principals that should have access to that data.
Caution!
CryptDB requires that,
For each private data item in a row,
The name of the principal that should have access to that data be
stored in another column in the same row.
ENC_FOR
4
Multiple
Principals
In table privmsgs，
subject & msgtext can be access
through specific principals of type msg.
like in the table below,
the decryption of msgtext x37a21f
is available only to principal 5 of type
msg.
SPEAKS_FOR
4
Multiple
Principals
Specify rules for how to delegate the privileges of one principal to other.
( a x ) SPEAKS_FOR ( b y )
This annotation indicates that,
Each row present in that table T specifies that,
Principal a of type x speaks for CryptDB requires that, principal b of
type y, meaning that a has access to all keys that b has access to.
x, y: fixed principal types.
b: is always specified by the name of a column in table T.
a: either the name of another column in the same table, a constant,
or T2:col.
SPEAKS_FOR
4
Multiple
Principals
In table privmsgs_to，
sender_id & rcpt_id of type user
can access all the data that specific
principals of type msg can access.
like in the table below,
user 1 & 2, which are the sender
and receipt of msg 5, can access msg
5.
Key Chaining
4
Multiple
Principals
Each principal is associated with a secret, randomly chosen key.
For External Principals,
Each external principal corresponds to an end user.
To give an external user access to the corresponding key on login,
CryptDB stores the key of each external principal in a third table,
external keys, encrypted with the principal’s password.
Obtain a user’s key given the user’s password;
Change user’s password without changing the key of the principal.
4
One Problem
Multiple
Principals
What if a principal is not online?
Database
2. Create msg x for
;
Encrypted x with its key;
Encrypt x’s key with KN’s key;
Encrypt x’s key with XL’s key?
1. Send
CryptDB
The key of each principal is a combination of a symmetric key and a
public–private key pair.