Transcript ThesisPresentation1 - California State University, Los Angeles

SECURE DATABASE OUTSOURCING
ALLA LANOVENKO
ADVISIOR: DR. HUIPING GUO
CALIFORNIA STATE UNIVERSITY LOS ANGELES
03-19-2007
1
Outline
• Database-As-A-Service Model (DAS)
– Overview of the DAS Model
– Advantages and Disadvantages of DAS Model
• Related Work on Secure Database Outsourcing
• Suggested Dynamic Group Key Management Schema for
Outsourced Databases
• Conclusion
2
Database-As-A-Service Model (DAS)
•
Data owner: an organization that produces data to be made
available for controlled external release.
•
User: an organization or human entity that presents requests
(queries) to the system and transforms this queries into queries
on the encrypted data stored on the server .
•
Server: an organization that receives the encrypted data from a
3
data owner and makes them available for distribution to users.
Advantages of DAS Model
• Saves organizations hardware and software resources
• Reduce database cost
• A way for organizations to share the expertise of the
database professionals
• Promises higher availability and more effective disaster
protection plan.
4
Disadvantages of the DAS Model
• Security
–
Data confidentiality: outsiders and the server cannot see the owner’s
database contents in any case. Users of the database have only partial
access to the outsourced data, they can only access the permitted
data by the owner.
–
Owner privacy: database owner does not want the server to know
about the queries and the returned results.
–
Authentication and data integrity: users must be ensured that data
returned from the untrusted server is originated from the data owner
and has not been tampered with.
5
Outline
• Database-As-A-Service Model
• Related Work on Secure Database Outsourcing
– Query Execution Techniques for Outsourced Databases
– Access Control Mechanism for Outsourced Databases
• Suggested Dynamic Group Key Management Schema for
Outsourced Databases
• Conclusion
6
Query Execution Techniques for
Outsourced Databases
• To store only encrypted data do not work because it would
enable external service provider to support selective
access. Since confidentiality demands that data decryption
must be possible only at the client side different techniques
were presented to enable external servers to execute
queries on encrypted data.
• Proposed query execution techniques to select the data to
be return in responds to a query without the need of
decrypting the data themselves based on storing together
with the encrypted data additional indexing information [1,
2,13, 16, 17].
7
Query Execution Techniques for
Outsourced Databases
•
index of range technique proposed by Mehrotra, Li and Iyer
for both equality and range predicate query.
8
Query Execution Techniques for
Outsourced Databases
•
Basic idea of how index of range technique works:
– Employee(eid, ename, salary, addr, did)
–
EmployeeS(etuple, eidS, enameS, salaryS, addrS, didS) on server side
–
Partition of attribute eid Employee [0, 200] = 2, [200, 400] = 7, [400, 600] = 5, [600,
800] = 1 and [800, 1000] = 4
–
To retrieve record of the employee whose employee id = 320
SELECT * from Employee
map to
SELECT * from Employee
WHERE eid = “320”
WHERE eid = 7
9
Query Execution Techniques for
Outsourced Databases
•
The Other Query Execution Techniques :
– in [1, 13] proposed a hash-based method suitable for selection
queries
– in [3] order preserving encryption schema (OPES) is presented to
support equality and range query. This approach operates only on
integer value
– in [10] proposed techniques for performing arithmetic operations (
+, -, *, / ) on encrypted data and do not consider comparison
operations.
– [4, 5] proposed execution of aggregation queries over encrypted
data
Limitation of the proposed techniques: they are protecting data at
the server side, and provides complete access to the database
contents on the client side.
10
Access Control Mechanism for
Outsourced Databases
•
Proposed by Damiani, Foresti, Samarati and others prof. of University
of Milan, access control mechanism exploit data encryption by
including authorization in the encrypted data themselves. In this
way it is enforce access restriction to deferent users, sets of users, or
applications.
•
Access Control Mechanism for outsourced databases proposed a
different method that consists in grouping users with the same
access privileges and in encrypting each groupof tuples with the
key associated with the set of users that can access it.
•
Mechnism limited to the static groups.
•
Can not be directly applied to the dynamic groups. In this case
outsourced database has to be re-encrypted each time group
membership changes.
11
Outline
•
Database-As-A-Service Model
•
Related Work on Secure Database Outsourcing
•
Suggested Dynamic Group Key Management Schema for
Outsourced Databases
– System Description
– System Architecture
– Group Key Distribution Model
– Query Processing
– Experiment
•
Conclusion
12
Suggested Dynamic Group Key
Management Schema for Outsourced
Databases
•
The thesis proposes a dynamic group key management schema for
outsourced databases.
•
The proposed schema is performing scalable encryption/decryption
algorithm at the server side and the client side using key pair generated from
the group keys based on most widely used Rivest-Shamir-Adelman (RSA)
cryptographic algorithm.
•
In case of dynamic group, proposed schema solves database re-encryption
problem in the event when group membership changes dynamically. It
efficiently solves the security problems: data confidentiality and owner
privacy.
13
System Description
•
All the users of the outsourced database are divided into different
groups based on access privilege.
•
Users with the same access privilege can access the same part of the
outsourced data.
•
Each group of database users has pair of keys:
– Encryption key KGRe
– Decryption key key KGRd
– Mod n
• which are generated by the database owner using RSA
algorithm, KGRe and KGRd are secret to the group members.
14
System Description
• Group encryption key KGRe is used by the database
owner to encrypt tuples in the database.
– C = EKGRe [ Data ] mod n
• Group decryption key KGRd is used by the owner to
randomly generate a pair of group subkeys KGRd1 and
KGRd2 such that
– Data = DKGRd [ C ] mod n
– Data’ = DKGRd1 [ DKGRd2 [ C ] ] mod n
Data = Data’
15
System Architecture
•
•
Proposed group key distribution schema uses centralized setting.
Includes tree entities:
– Database owner: is responsible for producing, distributing, managing and
updating group keys.
– Group User: decrypts the result from the server using the first part of the group
decryption subkey KGRd1 in the decryption algorithm in order to get the
plaintext result.
– Server: is responsible for producing the query result on the encrypted
database, decrypting the result with the second part of the group decryption
subkey KGRd2 and sending encrypted result to the group user.
16
Group Key Distribution Model
•
Three phases in the system: initialization, adding new group
member, and evicting existing group member.
•
Initialization Phase:
– Establishes group keys.
– Performed by the database owner:
• uses RSA cryptographic algorithm to generate two
keys: group encryption key (KGRe , mod n) and group
decryption key (KGRd , mod n).
• splits decryption key KGRd on two parts and produces
two group subkeys KGRd1 and KGRd2.
17
Group Key Distribution Model
•
db owner sends to each user Ui 
GRi a subkey KGRd1 and modulus
n. Group members hold a group
subkey KGRd1 and mod n as their
secret key.
•
db owner sends to the server a
group subkey KGRd2. The Server
holds a group subkey KGRd2 as
group GRi secret key.
•
db owner encrypts set of tuples
with group GRi encryption key
(KGRe, mod n) and store them in
the outsourced database.
18
Group Key Distribution Model
• Adding a Group Member
19
Group Key Distribution Model
• Evicting a Group Member
20
Query Processing
21
Experiment
•
•
•
For the experiment we used the programming language Java with the following
characteristics: java version 1.4.2 Java(TM) 2 Runtime Environment, Standard Edition
(build 1.5.0_02-b09).
We also used Microsoft Access database for the data storage.
Customer
Account
Amount$
Alice
5678
3
Bob
2190
95
Donna
3456
740
Elvis
9017
56
Alla
8324
10,712
Sal
0153
839
Original data
Customerk {etuple, CustomerInd, AccountInd, AmountInd, Subkey}
Encrypted table
22
Experiment
•
Key distribution schema
Group
number
Encryption key
Decryption
key
Subkey 1
(user side)
Subkey 2
(server side)
Modulus
1
905
44825
8965
5
11021
2
593
10769
979
11
23701
•
Group 1 member retrieve the Customer table
–
Select * from the Customer
map to
Select etuple from the Customer
Query Result Received by the Group 1 Member
•
Group 2 member query result
23
Experiment
•
Group 1 Member Eviction
Group number
1
(before
member
eviction)
1
(after member
eviction)
Encryption
key
Decryption
key
Subkey 1
(user side)
Subkey 2
(server side)
Modulus
905
44825
8965
5
11021
905
44825
4075
11
11021
•The test shows that on the select query existing group 1 users receive the same result as it
shown in previous slide. However, evicted member can not access the tuples. Since
Data = CKGRd mod n and Data’ = (C KGRd1’) KGRd2 mod n , Data Data’
Evicted Group 1 Member Query Result
24
Conclusion
• Thesis investigates a solution for implementing through
cryptography a selective access policy. Based on the
modification of the RSA cryptographic algorithm, the thesis
proposed key management schema for outsourced
databases.
• This schema is suitable for the dynamic environment where
authorizations, users, and objects can dynamically change.
We also performed implementation of our schema and
presented experimental result .
25
References
[1] Ernesto Damiani, S. De Capitani di Vimercati, Sara Foresti, Sushil Jajodia, Stefano
Paraboschi, Pierangela Samarati, Key Management for Multi-User Encrypted Databases,
Proceedings of the 2005 ACM workshop on Storage security and survivability, November
2005.
[2] H. Hacig¨um¨us, B. Iyer, S. Mehrotra, and C. Li. Executing SQL over encrypted data in the
database-service-provider model. In Proc. of the ACM SIGMOD’2002, Madison, WI, USA,
June 2002.
[3] R. Agrawal, J. Kierman, R. Srikant, and Y. Xu. Order preserving encryption for numeric data.
In Proc. of ACM SIGMOD 2004, Paris, France, June 2004.
[4] S. Akl and P. Taylor. Cryptographic solution to a problem of access control in a hierarchy.
ACM Transactions on Computer System, 1(3):239–248, August 1983.
[5] D. Boneh, G. D. Crescenzo, R. Ostrovsky, and G. Persiano. Public-key encryption with
keyword search. In Proc. of Eurocrypt 2004, Interlaken, Switzerland, May 2004.
[6] D. Boneh and M. Franklin. Identity-based encryption from the weil pairing. In Proc. CRYPTO
01, pages 213–229, 2001.
[7] C. Boyens and O. Gunter. Using online services in untrusted environments – a privacypreserving architecture. In Proc. of the 11th European Conference on Information Systems
(ECIS ’03), Naples, Italy, June 2003.
[8] R. Brinkman, J. Doumen, and W. Jonker. Using secret sharing for searching in encrypted
data. In Proc. of the Secure Data Management Workshop, Toronto, Canada, August 2004.
[9] A. Ceselli, E. Damiani, S. De Capitani di Vimercati, S. Jajodia, S.Paraboschi, and P. Samarati.
26
Modeling and assessing inference exposure in encrypted databases. ACM Transactions
References
on Information and System Security (TISSEC), 8(1):119–152, February 2005.
[10] E. Damiani, S. De Capitani di Vimercati, M. Finetti, S. Paraboschi, P. Samarati, and S.
Jajodia. Implementation of a storage mechanism for untrusted DBMSs. In Proc. of the
Second International IEEE Security in Storage Workshop, Washington DC, USA, May 2003.
[11] E. Damiani, S. De Capitani di Vimercati, S. Foresti, . Jajodia, S.Paraboschi, and P.Samarati.
Metadata management in outsourced encrypted databases. In Proc. of the 2nd VLDB
Workshop on Secure Data Management (SDM’05), Trondheim, Norway, September 2005.
[12] E. Damiani, S. De Capitani di Vimercati, S. Foresti, S. Jajodia, S. Paraboschi, and P.
Samarati. Selective release of information in outsourced encrypted databases. Technical
report, University of Milan, 2005.
[13] E. Damiani, S. De Capitani di Vimercati, S. Jajodia, S. Paraboschi, and P. Samarati.
Balancing confidentiality and efficiency in untrusted relational DBMSs. In Proc. of the 10th
ACM Conference on Computer and Communications Security, Washington, DC, USA,
October 27-31 2003.
[14] G. Davida, D. Wells, and J. Kam. A database encryption system with subkeys. ACM
Transactions on Database Systems, 6(2):312–328, June 1981.
[15] E. Goh. Secure indexes. http:// eprint.iacr.org/2003/216/.
[16] H. Hacig¨um¨us, B. Iyer, and S. Mehrotra. Providing database as a service. In Proc. of 18th
International Conference on Data Engineering, San Jose, CA, USA, February 2002.
[17] H. Hacig¨um¨us, B. Iyer, and S. Mehrotra. Ensuring the integrity of encrypted databases in
the database-as-a-service model. In DBSec, pages 61–74, 2003.
27
References
[18] H. Hacig¨um¨us, B. Iyer, and S. Mehrotra. Efficient execution of aggregation queries over
encrypted relational databases. In Proc. of the 9th International Conference on Database
Systems for Advanced Applications, Jeju Island, Korea, March 2004.
[19] H. Hacig¨um¨us and S. Mehrotra. Performance-conscious key management in encrypted
databases. In DBSec, pages 95–109, 2004.
[20] L. Harn and H. Lin. A cryptographic key generation scheme for multilevel data security.
Computers and Security, 9(6):539–546, October 1990.
21] B. Hore, S. Mehrotra, and G. Tsudik. A privacy-preserving index for range
queries. In Proc. of the 30th VLDB Conference, Toronto, Canada, 2004.
[22] M. Hwang and W. Yang. Controlling access in large partially ordered
hierarchies using cryptographic keys. The Journal of Systems and
Software, 67(2):99–107, July 2003.
[23] S. MacKinnon, P.Taylor, H. Meijer, and S.Akl. An optimal algorithm for
assigning cryptographic keys to control access in a hierarchy. IEEE
Transactions on Computers, 34(9):797–802, September 1985.
[24] E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in
outsourced database. In Proc. of the 11th Annual Network and Distributed
System Security Symposium, San Diego, CA, USA, February 2004.
[25] R. Sandhu. Cryptographic implementation of a tree hierarchy for access
28
control. Information Processing Letters, 27(2):95–98, April 1988.
References
[26] B. R. Waters, D. Balfanz, G. Durfee, and D. K. Smetters. Building an encrypted and
searchable audit log. In Proc. of the 11th Annual Network and Distributed System Security
Symposium, San Diego, CA, February 2004.
[27] M. Winslett and J. D. Ullman. Jeffrey D. Ullman speaks out on the future of higher
education, startups, database theory, and more. SIGMOD Record, 30(3), 2001.
[28] Alan T. Sherman and David A. McGrew. Key Establishment in Large Dynamic Groups Using
One-Way Function Trees. IEEE Transactions on Software Eng., 29(5):444–458, 2003.
[29] S. Castano, M.G. Fugini, G. Martella, P. Samarati. Database Security. Addison-Wesley and
ACM Press 1994, ISBN 0-201-59375-0
[30] A. Umar. Information Security and Auditing in the Digital Age - A Managerial and Practical
Perspective. NGE Solutions, December 2003 (e-book version)
[31] E. Mykletun, M. Narasimha, G. Tsudik. Authentication and Integrity in
Outsourced
Databases. The 11th Annual Network and Distributed System
Security Symposium –
NDSS2004, San Diego, California, USA, February 5- 6, 2004
[32] RSA laboratories. http://www.rsasecurity.com/rsalabs
[33] Whitfield Diffie and Martin Hellman. New Directions In Cryptography. IEEE Transactions on
Information Theory, 22(6):644–645, Nov. 1976.
[34] P. Atzeni, S. Ceri, S. Paraboschi, and R. Torlone. Database Systems: Concepts, Languages,
and Architecture. McGraw Hill, 1999.
29
Thank you!!
30