Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

CryptDB Part1

No description
by

Ziynet d

on 11 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of CryptDB Part1

Ziynet Nesibe DAYIOĞLU CryptDB CryptDB From
The Point of Thread 1 Dynamic Example Based on Thread-1 CryptDB History suggests we will never build perfect
systems that cannot be compromised
Administrators make configuration mistakes
Cloud computing poses new threats
Curious or malicious cloud administrators
Servers out of your control Compromises inevitable MIT CSAIL (Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan)
Year :
Gmail Group :
Open Source
Attack :
Demo General Info CryptDB consists of a DBMS server and separate application server which runs tha application code and issues DBMS queries
Approach is to execute queries over encrypted data, and key insight that makes it practical (SQL uses a well-defined set of operator which we can support effeciently over encrypted data)

Sensitive data is never available in plaintext at the DBMS server.
The DBMS server cannot compute the results for queries that involve computation classes not requested by the application.
If the application requests
no relational predicate filtering on a column, nothing about the data content leaks
equality checks on a column, proxy reveals which items repeat in that column, but not the actual values
order checks on a column, the proxy reveals the order in the column to encrypt sensitive data, and run all computations on clients
Applications don’t lend themselves to this approach(database-backed web sites, which computes over large amounts of data..)
Even if tenable, converting an existing server-side application is difficult
to consider theoretical solutions such as fully homomorphic encryption (still very slow) Previous Approaches to reduce the damage caused by server compromises Important data leaks from databases
What about encrypting data before sending it to the cloud who doesn’t need to decrypt data to process query? Database System Not integrity, or completeness of results returned to the application
Deletion, modification can be done
Attacks on user machines, such as cross-site scripting, are outside of the scope User 3 User 2 User 1 on encrypted data Threat 2: any attacks on all servers Threat 1: passive DB server attacks SQL DB Server Application Goal: protect confidentiality of data CryptDB in a nutshell 1-To execute SQL queries over encrypted data
-SQL queries are made up of a well-defined set of primitive operators (equality checks, order comparisons, aggregates(sums), joins)
-Encryption is done in a way that allows DBMS to execute on transformed data
-Effecient (mostly uses symmetric key encryption, avoids fully homomorphic, runs on unmodified DBMS)
2-To use adjustable query-based encryption
-Some encryption scheme leak more information than others about the data to the DBMS server
-Adjusts scheme depending on the query observed at run-time
-Uses onions to compactly store multiple ciphertexts within each other in the database, and avoid expensive re-encryption
3-To chain encryption keys to user passwords (Next lecture)
-Each data item in the db can be decrypted only through a chain of the keys rooted in the password of one of the users with access to that data. If adversary does not know the user’s password, then s/he can not decrypt user’s data even if the servers are compromised. CryptDB addresses these challenges using three key ideas: 1-Trade-off between minimizing the amount of confidential information revealed to the DBMS server and the ability to efficiently execute queries
-Too slow
-Not adequate confidential
-Strong and effecient cryptosystem prevents server from executing sql queries (only solution: giving decryption key! )
2-Minimizing the amount of data leaked when an adversary compromises the application server in addition to the DBMS server
-Arbitrary computation on encrypted data is not practical, then application must be able to access decrypted data(compromise?)
-Assign each user a different database encryption key for their data (not working for applications with shared data) Two challenges in combating these threats - Thread 1: a curious DBA who tries to learn private by snooping on the DBMS server
CryptDB prevents the DBA from learning private data.
(This lecture)

- Thread 2: an adversary that gains complete control of application and DBMS servers
CryptDB cannot provide any guarantees for users that are logged into the application during an attack, but can still ensure the confidentiality of logged-out users’ data.
(Next lecture) Two threats addressed by CryptDB -to encrypt sensitive data, and run all computations on clients
-Applications don’t lend themselves to this approach(database-backed web sites, which computes over large amounts of data..)
-Even if tenable, converting an existing server-side application is difficult
-to consider theoretical solutions such as fully homomorphic encryption (still very slow) Previous Approaches -History suggests we will never build perfect systems that cannot be compromised
-Administrators make configuration mistakes
-Cloud computing poses new threats
-Curious or malicious cloud administrators
-Servers out of your control Compromises inevitable MIT CSAIL (Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan)
October 2011
Mailing List and Group : cryptdb-users@csail.mit.edu.
Open Source
Attack
Demo General Info -CryptDB consists of a DBMS server and separate application server which runs tha application code and issues DBMS queries
-Approach is to execute queries over encrypted data, and key insight that makes it practical (SQL uses a well-defined set of operator which we can support effeciently over encrypted data)

-Sensitive data is never available in plaintext at the DBMS server.
-The DBMS server cannot compute the results for queries that involve computation classes not requested by the application.
-If the application requests
no relational predicate filtering on a column, nothing about the data content leaks
equality checks on a column, proxy reveals which items repeat in that column, but not the actual values
order checks on a column, the proxy reveals the order in the column Important data leaks from databases
What about encrypting data before sending it to the cloud who doesn’t need to decrypt data to process query? Database System Not integrity, or completeness of results returned to the application
Deletion, modification can be done
Attacks on user machines, such as cross-site scripting, are outside of the scope User 3 User 2 User 1 Threat 2: any attacks on all servers Goal: protect confidentiality of data CryptDB in a nutshell Application SQL on encrypted data DB Server Threat 1: passive DB server attacks Processing a query:

1- 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

2- 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

3- Proxy sends the encrypted query to the DBMS server

4- DBMS executes query using standard SQL (invoking UDFs for aggregation or keyword searches) and returns the encrypted results

5- Proxy intercepts and decrypts results, and sends them to the application Goal: to use the most secure encryption schemes that enable running the requested queries
For each layer of each onion, proxy uses the same key for encrypting values in the same column(allows the proxy to perform operations on a column without having to compute separate keys for each row that will be manipuated), and different keys across tables, columns ( prevents server from learning any additional relations), onions, and onion layers.

All keys are derived from The Master Key:
//PRP is a pseudorandom permutation (e.g., AES)

Data layout at the server: When the application creates the table shown on the left, the table created at the DBMS server is the one shown on the right.





CryptDb implements onion layer decryption using UDFs that run on the DBMS server.



Proxy updates its own internal state to remember that column C2-Ord in Table1 is now at layer OPE in DBMS
Onion decryption happens only when it is requested.
If stripped off, then no decryption is required. 2- Adjustable Query-based Encryption Onion encryption layers - Some onions or onion layers may be omitted, depending on column types or schema annotations provided by application developers.
- DET and JOIN are often merged into a single onion layer, since JOIN is a concatenation of DET and JOIN-ADJ.
-A random IV for RND, shared by the RND layers in Eq and Ord, is also stored for each data item. e.g., sum Security Highest e.g., >, <, ORDER BY, SORT, MAX, MIN (first implementation) Boldyreva et al.’09 Song et al.,‘00 new scheme Paillier AES in CMC AES in CBC Construction order word search join equality +, * none Function OPE JOIN SEARCH DET HOM RND Scheme 1-SQL-aware Encryption
schemes restricted ILIKE e.g., =, !=, IN, COUNT, GROUP BY, DISTINCT DBMS-side -> not trusted (but application and proxy are trusted)
CryptDB enables the DBMS server to execute SQL queries on encrypted data almost as if it were executing on plaintext data. Existing applications don’t need to be changed.
CryptDB’s proxy stores a secret master key MK, the database schema, and the current encryption layers of all columns. The DBMS server sees an anonymized schema (in which table and column names are replaced), encrypted user data, and some auxiliary tables used by CryptDB.
CryptDB equips the server with user-defined functions (UDFs) that enable the server to compute on ciphertexts for certain operations. More:
*CryptDB doesn’t encrypt NULLs
*Most other DBMS mechanisms (transactions, indexing) work the same way, with no modifications (ex. BEGIN, COMMIT, ABORT)
*For INSERT, DELETE, and UPDATE
DELETE require no additional processing.
For all INSERT and UPDATE queries that set the value of a column to a constant, the proxy encrypts each inserted column’s value with each onion layer that has not yet been stripped off in that column.
an UPDATE that sets a column value based on an existing column value (salary+=1).
- the values in the OPE and DET onions would become stale.
- any encryption scheme that simultaneously allows addition and direct comparison on the ciphertext is insecure.
//Server can compute the difference between any two values in the database
Two approaches :
- If a column is incremented and then only projected:
when a query requests the value of this field, the proxy should request the HOM ciphertext from the Add onion, because the HOM value is up-to-date.
- If a column is used in comparisons after it is incremented:
replace the update query with two queries: a SELECT of the old values to be updated, followed by an UPDATE setting the new values. Misc: If next query is also an equality check

Ex. SELECT COUNT(*) FROM Employees
WHERE Name = ‘Bob’

then no new DBMS decryptions are necessary,
as C2-Eq onion/column is already at DET level,
 proxy directly issues:
SELECT COUNT(*) FROM Table1 WHERE C2-Eq = xbb4a
and xbb4a = EKeyT1,C2,Eq,DET ( EKeyT1,C2,Eq,JOIN(Bob) )

Subsequent equality checks require no en/decryptions on C2-Eq;
en/decryptions only happen when a different operator is requested on that column (ex. JOIN, SELECT w/no WHERE)

- Step 3: Proxy receives encrypted RND level
result x2b82 and decrypts it using:

DKeyT1,C1,Eq,JOIN(DKeyT1,C1,Eq,DET

(DKeyT1,C1,Eq,RND (x2b82, x27c3) ) ) = 23


Proxy sends decrypted result 23 to the application

Table1’s data, and C1-Eq and C2-Eq’s current layer/level,
remain unchanged from previous step. Step 2: Proxy encrypts “Alice”, to its EQ onion,
DET layer encryption value of x7b3d via
EKeyT1,C2,Eq,DET(EKeyT1,C2,Eq,JOIN(Alice))

(equivalent to moving outwards through onion,
or adding a layer)

Proxy generates query and sends it to DBMS:
SELECT C1-Eq, C1-IV FROM Table1 WHERE C2-Eq = x7b3d

NB: Proxy must request the random IV from column C1-IV in
order to decrypt the RND ciphertext from C1-Eq

Eq Onion layers and encrypted values remain unchanged
from previous UPDATE step (i.e. still at the DET layer) Step 1: Proxy sends to the DBMS:
UPDATE Table1
SET C2-Eq = DECRYPT RND(KeyT1,C2,Eq,RND, C2-Eq, C2-IV)

DBMS decrypts entire C2-Eq column to DET layer:

DKeyT1,C2,Eq,RND(xd1e3, x8a13) = x7b3d

DKeyT1,C2,Eq,RND(x3f2a, x73fd) = xbb4a
...
 every row is fetched and altered!

Proxy updates its internal state to
log that Table1 column C2-Eq is
now at layer DET in the DBMS.
Eq Onions are at the default RND encryption layer.

The query is:

SELECT ID FROM Employees
WHERE Name = ‘Alice’

need to get to DET layer of
Eq Onions Example of An Dynamic Encrypted SQL Query Summary of Part-1 *CryptDB is a system that provides practical and provable confidentiality for applications backed by SQL databases

*CryptDB works by executing SQL queries over encrypted data using a collection of effecient SQL-aware encryption schemes

*By using adjustable query-based encryption, system makes data leakage minimum.

*CryptDB does not reveal any data to the DBMS Admin as plaintext, so admin never gets access to the decrypted data Thanks for Paying Attention!
Full transcript