Transcript Presenationslides

Authentication and Integrity
in Outsourced Databases
Kanaka Rajanala
What is Outsourced Database


Organizations outsource their data
management needs to an external
provider.
The service provider hosts client
database and offers mechanisms.
• Create databases
• Updating
• Storing
• Accessing (querying)
Advantages of ODB


The organizations can concentrate on
their core tasks and operate their
business applications via Internet.
Don’t worry about
• Deployment, instillation, maintenance
,upgrades.
• Hire, train/retain people.
Challenges

Overall performance

Scalability

Usability
Challenges
• Privacy/Security
• Protection of outsourced data from
intruders and attacks.
• Protecting clients from misuse of data
by service providers.
• Ensuring
integrity+privacy+completeness of
query replies.
Goal

This paper investigate techniques to
help ODB client authenticate the
origin and verify the integrity of data
returned by the service provider in
response to a posed query.
System Model


ODB is an example of Client –Server
model.
Types of ODB
• Unified Client Model
• Multi Querier Model
• Multi Owner Model
1. Unified Owner Scenario
Server Site
Data Deposit + Queries
Owner/Querier
Server
Encrypted User
Database
A single entity creates, queries, manipulates the
database.
2. Multi-Querier Scenario
Server Site
Data Deposit
Owner/Querier
Server
& queries
Encrypted User
Database
Querier 1
Querier 2
Querier 3
3. Multi-Owner Scenario
Server Site
Server
Owner 1
Encrypted User
Database
Data Queries
Owner 2
Owner 3
Querier 1
Querier 2
Why do we need Integrity

In some occasions where we may not
want secrecy but want integrity
• Every one is allowed to read a message
• But no one is allowed to modify it.
Why do we need Authentication


To authenticate the source of data.
The main goal is to assure ODB
clients that the data they receive
from the server has not be tampered
from an external adversary or the
server itself.
Granularity of Integrity



Table level-impractical for large
tables.
Column level-very expensive for the
owner in terms of computation.
Optimal is to provide integrity at row
level.
Overhead Factors and Desired
Features





Querier computation
Querier bandwidth
Server computation
Owner computation
Server storage
MAC’s or Signatures



With MAC client can ask server to
store record along with MAC.
Works for Unified Client model where
owner and querier are same.
Cannot be worked with other models
• MAC key to be shared between all
owners and queriers.
• Non repudiation of queries cannot be
achieved.
Standard RSA
Condensed RSA

Server:
• Selects records matching posed query
• Multiplies corresponding RSA signatures
• Returns single signature to querier
Server
Given t record signatures:
{σ1, σ2 … σt} ,
compute combined signature
σ1,t =
Πσi mod n
Send σ1,t to the querier
Querier
σ1,t
Given t messages:
{m1,m2 … mt} and σ1,t
verify combined signature:
(σ1,t)e = ? = Π h(mi) (mod n)
Condensed RSA

Reduced querier computation costs
• Querier performs (t-1) mult-s and a one
exponentiation

Constant bandwidth overhead
• Querier receives a single RSA signature

As secure as batch RSA (with FDH)

Not efficient for Multi-Owner model
Batch Verification of RSA Signatures


Batching: useful when many signature
verifications need to be performed
simultaneously
Reduces computational overhead
• By reducing the total number of modular
exponentiations

Fast screening of RSA signatures :
• Given a batch instance of signatures {σ1, σ2 … σt} on
distinct messages {m1, m2 … mt}
e
t



  i 
   h(mi )(mod n)
i 1
 i 1

where h() is a full domain hash function
t
Fast Screening

Reduces (somewhat) querier computation
but not bandwidth overhead
• Individual signatures are sent to the querier
for verification

Bandwidth overhead can be overwhelming
• Consider weak (anemic) queriers
• Query reply can have thousands of records
• Each RSA signature is at least 1024 bits!
Cost Comparisons
1. Querier computation:
Condensed RSA
Batch DSA
Sign
1 signature
6.82
3.82
Verify
1 signature
t =1000 sigs, k=1 signer
t =100 sigs, k=10 signers
t =1000 sigs, k = 10
signers
0.16
44.12
45.16
441.1
8.52
1623.59
1655.86
16203.5
Parameters:
For RSA: |n| = 1024
For DSA: |p| = 1024 and |q| = 160