Transcript PISB - College of Engineering | Oregon State University

6th ACM Conference
Security
and11.3
Privacy
in Wireless
and
27th on
Annual
IFIP WG
Working
Conference
onMobile Networks
Data and Applications Security and Privacy (DBSec '13)
Practical Immutable Signature Bouquets (PISB) for
Authentication and Integrity in Outsourced Databases
Attila Altay Yavuz
Robert Bosch Research and Technology Center
Pittsburgh, PA 15203, USA
[email protected]
07/16/2013
DBSec 2013
Motivation
 Data outsourcing is beneficial, especially for small-medium business
 Reduces the cost via continuous service, expertise, maintenance/upgrade;
 Database as a Service (DAS) [1]: Data owners outsource their data
to a database service provider (e.g., IBM). Database service provider
offers a reliable maintenance and access for the hosted data.
 Despite its benefits, DAS also brings security and privacy challenges:
 Privacy versus utilization (e.g., searchable encryption)
 Access privacy (e.g., ORAM [2])
 Authentication and integrity: Immutable digital signatures (e.g.,
[3,4])
2
DBSec 2013
A DAS Model and Limitations (I)
 Model of Hacigumus et al. [1] extended by Mykletun et al. in [3]
M1,…,Mn
S1, …., Sn
High bandwidth
M1,…,Mn
S1, …., Sn
- Each tuple in database is M1,…, Mn
- Compute signatures S1,…,Sn
- Semi-trusted entity
- Honest service, but
compromise?
A query related to some tuples on the server
Each query: O(K) signature transmission
Better verification efficiency?
Return tuples {M1,…,Mk}
along with S1,…,Sk
- Bandwidth, battery and/or
Computation limited queriers
Verify S1,…,Sk before accepting results
3
DBSec 2013
Digression: Aggregate Signatures
 Given multiple individual signatures and corresponding public key(s), output
a single compact (verifiable) signature
 Condensed-RSA (C-RSA) [3]: Aggregate signatures with the same private key
pk  (n, e), sk  (n, d), where n  p  q and p,q large primes
e  d  1 mod (n), where (n)  ( p  1)( q  1).
H : { 0,1 }*  Z n* , ideal full domain cryptograp hic hash function
RSA signature on a data item m is   H(m)d mod n, verificat ion  e  H(m) mod n
Given messages m1 , , mk and sk  (n, d), pk  (n,e), Condensed - RSA :
k
 1,k   H(mi ) mod n
d
i 1
k
( 1,k ) mod n   H(mi ) mod n
e
i 1
 Boneh Lynn Shacham (BLS) [5]: Cryptographic pairing-based, signatures
under the different private keys can be aggregated
4
DBSec 2013
A DAS Model and Limitations (II)
 DAS model of Mykletun et al. in [3]
M1,…,Mn
S1, …., Sn
High bandwidth
M1,…,Mn
S1, …., Sn
- Each tuple in database is M1,…, Mn
- Compute individual signatures S1,…,Sn with Agg
- Semi-trusted entity
A query related to some tuples on the server
O(1) signature transmission
Batch signature verification
Given tuples{M1,…,Mk},
Select corresponding S1,…,Sk
S = Agg(S1,…,Sk)
Return S as aggregate signature
Problem: Aggregate signatures are mutable
- Bandwidth, battery and/or
Computation limited queriers
Verify S before accepting results
5
DBSec 2013
Problem Statement: Signature Mutability
 Given two C-RSA signatures, it is possible to derive a new valid signature
 1,i on (m1 ,
 1,i on (m1 ,
,mi ) and  1, j on (m1 ,
,m j ), where i  j, mutable signature is:
 i 1, j  1, j  (1,i )-1 mod n on (m j 1 , ,mi )
,mi ) and  i 1, j on (mi 1 , ,m j ), mutable signature is:
 1, j   1,i   i 1, j mod n
on (m1 ,  ,m j )
The same applies to BLS signature scheme (aggregation is modular addition).
 Access Control Applications: Colluding clients can elevate access privileges
 Paid Database Services: Online authorized music album distributor (server), store
large database of digitally signed songs. Colluding clients can act as “album
distributor” without paying, by mix-matching songs and their signatures. Steal
profit of actual distributor.
6
DBSec 2013
Limitations of Existing Immutable Signatures
 Mykletun et al. developed immutable signature schemes in [3,4].
 Immutable Condensed RSA (IC-RSA): Hide C-RSA signature
 Guillou-Quisquater [6] based scheme : Use zero-knowledge to hide C-RSA signature.



(+) It is the most computationally efficient variant proposed in [3,4].
(-) Interaction introduces communication overhead and delay,
(-) A signature scheme is supposed to be non-interactive!
 Skroot based scheme: Use “Signature of Knowledge” [7] to hide C-RSA signature


(+) Non-interactive, more communication efficient than GQ-based scheme
(-) High computational cost and storage cost
 Immutable BLS Signatures (iBLS) : BLS signature  on m’=(m1,…,ml).
Compute a secondary protection signature  on m’, and aggregate  on .


(+) Non-interactive and small signature
(-) The most computationally costly alternative (due to crypto pairing): Verifier side
7
DBSec 2013
Practical Immutable Signature Bouquets (PISB)
 (i) PISB Condensed Sequential RSA (PISB-CSA-RSA); (ii) PISB-Generic.
 Non-Interactive Immutability: Communication efficiency, PISB-CSA-RSA requires
1 KB overhead, while GQ-based in [3,4] requires 9 KB overhead.
 High Computational Efficiency: PISB-CSA-RSA is up to 40 times faster than iBLS,
skroot and GQ based schemes in [3,4]. PISB-Generic offers pre-computability, which is
ideal for server to handle requests at peak times.
 Small Signature Sizes: PISB-CSA-RSA is more communication efficient than GQ and
skroot based schemes in [3,4]. PISB-Generic is more efficient than PISB-CSA-RSA,
and it is comparable to iBLS [3,4].
 Low End-to-End Delay: Much faster response time based on the above properties.
 Provable Security: PISB schemes are only immutable signatures with formal proofs.
8
DBSec 2013
PISB-CSA-RSA Scheme (Intuition)
 Recall iBLS signatures [3,4]: Server computes a protection signature  over queried
data items, and aggregate  on the original aggregate signature .
 Limitation of IC-RSA: IC-RSA cannot aggregate signatures of data owner and clients.
The same modulo n cannot be shared among multiple signers (expose key [8]).
 Objective: Server and data owner jointly compute a single compact RSA signature, such
that server can aggregate C-RSA signature and his protection RSA signature.
 Observation: Sequential Aggregate RSA (SA-RSA) [9] can help! (Simplified below)
(n1 , e1 )
(n1 , d1 )
m1
1
(n2  n1 , e2 )
(n2  n1 , d2 )

m1 , m2

Verify  1 with (n1 ,e1 )
h2  H (m1 || m2 || n1 || e1 ),
y2  h2   1 mod n2 ,
 2  ( y2 ) d mod n2 ,
2
(ni  ni 1 , ei 1 )
(ni  ni 1 , di )
Verify  i-1 with (n1 , e1 , ni 1 , ei 1 )
hi  H (m1 ||  mi || n1 || e1  ni || ei ),
yi  hi   i 1 mod ni ,
 i  ( yi ) d mod ni ,
i
9
DBSec 2013
PISB-CSA-RSA Scheme (Detailed)
10
DBSec 2013
PISB-Generic Scheme (Intuition)
 Do we have to aggregate protection signature?
 Power of Simplicity: Server just computes a standard signature  on the aggregate
signature , and define the final signature as a pair (,) .
 Seems communication inefficient as it is not “fully aggregate”. However:
 ECDSA + (BLS or C-RSA ) combination is much more communication and
computation efficient than Skroot and GQ schemes in [3,4].
 Flexible: Allows cross data owners queries, protection signature can be any
signature such as offline/online signature [10], token-ECDSA [11].
 However, PISB-CSA-RSA outperforms PISB-Generic for various performance
metrics.
11
DBSec 2013
PISB-Generic Scheme (Detailed)
12
DBSec 2013
Performance Analysis
~40
times
Best
morefor
server
efficient
Small
Offline/online
signature
ECDSA+C-RSA
Non-cross
signer
Cross
signer
NotOverall
ideal for
verifier
the most
versatile
choice
•Estimated execution times (l = 10 query elements, in ms) are measured on a computer with an Intel(R) Core(TM) i7 Q720
at 1.60GHz CPU and 2GB RAM running Ubuntu 10.10. We used MIRACL library.
• PISB Generic is implemented with ECDSA + BLS with pre-computed parameters
• End-to-end delay: Sign + Verify + transmission (remote client –server)
13
DBSec 2013
Security Analysis
 Immutable Existential Unforgeability under Chosen Message Attack (I-EU-CMA) for PISB:
 I-EU-CMA is an extension of EU-CMA such that adversary wins if the forgery is a
combination or subset of queried messages (i.e., signature mutations).
 A vector of messages
 Winning condition
14
DBSec 2013
Security Analysis (Cont’)
Theorem 1. PISB-Generic is (t, qs, )-I-EU-CMA secure, if ASig is (t’, qs,  )-EUCMA secure and Sig is (t’, qs, )-EU-CMA secure, where t’= O(t) + qs(Op + Op’)
and (Op,Op’) are the cost of signing for ASig and Sig, respectively.
 Any forgery on  also requires forging protection signature s’ .
 Generating mutable signature on  requires forging s’.
 Simulation is indistinguishable.
Theorem 2. PISB-CSA-RSA is (t, qs, )-I-EU-CMA secure, if RSA is (t’, (2l)  qs, 
)-EU-CMA secure, where t’= O(t) + (2l) qs  Exp, where l and Exp denote the
modular exponentiation and number of messages in a single query, respectively.
 Forging sequential aggregate RSA signature  is as difficult as forging RSA.
  is on m || pk , producing subset/combination requires forging RSA, individual
forgery of data items require forging  thereby forging RSA.
 Given two RSA signature oracles (O1,O2), simulator generates PISB-CSA-RSA
signatures by computing a C-RSA signature via O1 and a SA-RSA signature via
O2. Simulation is indistinguishable.
15
DBSec 2013
Conclusion
 PISB schemes are efficient immutable signatures for outsourced databases
 PISB-CSA-RSA
 Very low client computational overhead
 Compact constant size signature, no interaction
 Suitable choice for resource-limited clients
 PISB-Generic
 Very simple, various options
 Cross signer aggregation is possible
 More efficient than previous alternatives: Simplicity
 Provable security guarantee
16
DBSec 2013
17
DBSec 2013
References
[1] Hacigumus, H., Iyer, B., Mehrotra, S.: Providing database as a service. In: Proceedings of the 18th International Conference on Data Engineering,
ICDE 2002, Washington, DC, USA, pp. 29–38 (2002)
[2] Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious ram simulation.
Proc. of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 157–167 (2012)
[3] Mykletun, E., Narasimha, M., Tsudik, G.: Authentication and integrity in outsourced databases. Transaction on Storage (TOS) 2(2), 107–138
(2006)
[4] Mykletun, E., Narasimha, M., Tsudik, G.: Signature bouquets: Immutability for aggregated/condensed signatures. In: Samarati, P., Ryan, P.Y.A.,
Gollmann, D., Molva, R. (eds.) ESORICS 2004. LNCS, vol. 3193, pp. 160–176. Springer, (2004)
[5] Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.)
EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)
[6] Guillou L., Quisquater, J.: A “Paradoxical” Identity-Based Signature Scheme Resulting from Zero-Knowledge. Advances in Cryptology - Crypto
(1998) 216–231
[7] Camenisch, J., Stadler, M.: Efficient Group Signature Schemes for Large Groups. Advances in Cryptology - Crypto (1997).
[8] Ding, X., Tsudik, G.: Simple identity-based cryptography with mediated rsa. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 193–210.
Springer, Heidelberg (2003)
[9] Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch,
J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004)
[10] Catalano, D., Di Raimondo, M., Fiore, D., Gennaro, R.: Off-line/on-line signatures: Theoretical aspects and experimental results. In: Cramer, R.
(ed.) PKC 2008. LNCS, vol. 4939, pp. 101–120. Springer, Heidelberg (2008)
[11] D. Naccache, D. M’Raïhi, S. Vaudenay, and D. Raphaeli. Can D.S.A. be improved? Complexity trade-offs with the digital signature standard. In
Proc. of the 13th International Conference on the Theory and Application of Cryptographic Techniques (EUROCRYPT ’94), pages 77–85, 1994
18