Report

A Security Analysis of Cliques Protocols Suites Olivier Pereira – Jean-Jacques Quisquater UCL Crypto Group © UCL Crypto group Feb-15 What are Cliques Protocols? • Suite of Group Key Agreement Protocols http://www.isi.edu/~gts/CLIQUES/ • We are concentrating on the A-GDH.2 suite Authenticated - Group Diffie-Hellman.2 • Main Protocol: Key Generation • Several subprotocols: – Member Adding (A-GDH.2-MA), Deleting – Group Splitting, Fusion of groups – ... © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 2 The A-GDH.2 Protocols • All protocols are based on a single problem: The Diffie-Hellman Decision Problem x y i.e. knowing and (mod p), xy it is difficult to compute (mod p) • All Arithmetic is performed in a cyclic group G that is a subgroup of prime order q of *p • is a generator of G • Each couple of users (Mi, Mj) shares a longterm key: Kij © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 3 The Key-Generation Protocol • ri are random numbers M1 r1 M r1 r2 r1r2 M 2 3 r1r2 r1r3 r2r3 r1r2r3 r2r3r4K14 r1r3r4K24 r1r2r4K34 M4 •The shared Key is r1r2r3r4 • r1r2r3r4 = (r1r2r3)r4 = (r2r3r4K14)r1(1/K14) = (r1r3r4K24)r2(1/K24) © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 4 Intended Security Properties • Implicit Key Authentication : – A user that is not a member of the group cannot obtain the view of the key of one of the honest users • Perfect Forward Secrecy : – The compromise of long-term key(s) cannot result in the discovery of past session keys • Resistance to Known-Key Attacks : – The compromise of past session keys cannot result in the possibility of impersonation of honest parties in later sessions © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 5 Intended Security Properties • All these properties must be fulfilled in the presence of an active attacker that is able to – intercept messages – delete messages – replay messages – substitute part of messages –… • Only informal arguments are given to justify these properties © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 6 Two Approaches of Verification Cryptographic Formal Random Oracle Paradigm Messages as strings of bits Use of logic, state exploration, nominal calculus, … Symbolic representation of Messages Probabilistic Security Properties Formal Expression of Security Properties © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 7 Two Approaches of Verification • The “computational” aspect of these protocols makes it perhaps closer from “cryptographic” approaches (already used for A-DH…) • We are trying to adapt ideas from the “formal” community • Several notions close to the Strand Space approach • Intuitive... © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 8 Messages and Intruder’s Knowledge • Three types of elements manipulated: – Random numbers : ri – Long-term Keys : Kij – Elements of G expressed as raised to a power that is a product of the elements of the two first types • Behaviour of honest users: – “Blind” reception of a sequence of powers of – Exponentiation of these elements with random numbers and long-term Keys © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 9 Messages and Intruder’s Knowledge (II) • The Group-Key is generated in the same way • Each member of the group computes the key, but has no confirmation of its value. We use “Sn(Mi)” to denote Mi’s view of the Group Key • No correspondence properties intended between the views of the different users © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 10 Intended Security Properties (cont.) • Implicit Key Authentication – The secret is not a value – The secret is the possession of a couple of values presenting between them some connection. The relation is the secret!!! Ex: Key computation in the Key Generation Protocol M1 Mn Mi: x , then Mi computes xri(1/Kin)=Sn(Mi). Mn-1 The result of this computation is intended to be secret… So any pair (x, xri(1/Kin)) can be used to attack Mi! © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 11 Messages and Intruder’s Knowledge (III) • Two interesting sets of elements: – E = the set of the long-term keys and of the random numbers – R = the set of all possible ratios between products of elements of E. The R-set will be used to model the connection between powers of Ex: The ratio corresponding to the secret of M1 will be r1.(1/K1n) © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 12 Limitations of this Scheme • We consider G as infinite – But G is very large... • Our scheme does not allows the discovery of attacks that use connections between more than two elements of G. – But all secrets can be expressed as connections between two elements... • We will not capture the possibility of combining two powers of to obtain a new useful power of – But the (generalised) DDH-problem is hard... © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 13 Intruder’s Capabilities • Capabilities in term of elements of E, R – Let EI and RI be the subsets of elements of E and R known by the Intruder – First rule: Exponentiation (1) If e EI and r RI then r.e RI and r.e-1 RI Ex: If the intruder knows x and xy, we will model it by y RI . If he knows e EI, then he can deduce xye and xy(1/e) so y.e RI and y.e-1 RI © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 14 Intruder’s Capabilities (II) • Other way to obtain new elements of G: Use of “Services” • Service = s: G G : s(x) = px (where p is a product of elements of E) • Each Service correspond to a transformation provided by a honest user during the execution of the protocol © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 15 Intruder’s Capabilities (III) • Second rule: use of Services: – Let S be the set of available services (2) If s S : s(x)= p.x, and r RI then r.p RI or r.p-1 RI Ex: If the Intruder knows y and yz, we will model it by z RI . If s S : s(x)= p.x then • if y is sent to the user providing s, the intruder will obtain the couple ( yp, yz) and z.p-1 RI • if yz is sent to the user providing s, the intruder will obtain the couple ( y, yzp) and z.p RI © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 16 Proving Security Properties • The problem is: – Knowing initial sets EI, RI, S – Is it possible to derive a secret rs ( RS) by applying in a “suitable way” the rules (1) and (2) ??? • What is a “suitable way”? – The use of the (2)-rule needs some restrictions in order to respect the availability of services • Solution of this problem amounts to study a linear equation system! © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 17 Implicit Key Authentication for the Key Generation Protocol 1. Expression of EI, RI, S, RS EI = , RI={r1} S = {r2, …, rn-1, rnK1n, …, rnKn-1n} RS={ ri K in1 | 1 i<n, rn} 2. Expression of the balance of the variables 1 r K We will first check the secrecy of 1 1n © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 18 Implicit Key Authentication (II) 1 r K 3. System corresponding to 1 1n Balance for ri (i<n): r1= 1, r2= 0, …, rn-1= 0 Balance for rn: rnK1n+rnK2n+…+rnKn-1n= 0 Balance for Kin: rnK1n = -1, rnK2n = 0, …, rnKn-1n= 0 Inconsistency between the last n equations: r1 K1n1 is secret! This can be easily transposed for the other secrets… © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 19 Implicit Key Authentication (III) • What comes if I was member of another not disjoint group? • It is possible to discover attacks… © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 20 Perfect Forward Secrecy 1. Expression of EI, RI, S, RS EI = {K1n, …, Kn-1n}, RI={r1} S = {r2, …, rn-1, rnK1n, …, rnKn-1n} RS={ ri K in1 | 1 i<n, rn} 2. Deletion of the elements of EI (due to the 1-rule) RI={r1} S = {r2, …, rn} RS={ri | 1 i n} 3. Resolution of the system: This system admits trivial solutions for each secret! © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 21 Perfect Forward Secrecy (II) • Attack upon M2 M1 r1 M r1 r2 r1r2 M 2 3 r1r2 r1r3 r2r3 r1r2r3 r2r3r4K14 r1r3r4K24 r1r2r4K34 M4 r2 K 2n1 • In this scheme, S4(M2)= • But if K24 is compromised, the Intruder is able to compute S4(M2) since he knows r2 ! • But this is not very dangerous... © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 22 Perfect Forward Secrecy (III) • Attack upon Mn M1 r1 r1 r2 r1r2 M2 M3 r1r2r3 r1r2 r1r3 r2r3 r1r2r3 r1r2r3r4K14 r1r3r4K24 r1r2r4K34 M4 • In this scheme, S4(Mi)= r1r2 ...rn (i>1) • But if K14 is compromised, the Intruder is able to compute S4(Mi)! • This seems more dangerous! © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 23 Resistance to Known-Keys Attacks • Similar... • The resolution of the corresponding system provides anew several attacks. – One scheme has been proposed in the paper defining the protocol (not really annoying) – We found two other schemes (more annoying!) © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 24 Addition of the A-GDH.2-MA Protocol • Adding of a new member M1 M2 r2r3r4r’4r5K14K15 r1r3r4r’4r5K24K25 r1r2r4r’4r5K34K35 r1r2r3r’4r5K44K45 M3 M4 M5 r2r3r4r’4K14 r1r3r4r’4K24 r1r2r4r’4K34 r1r2r3r’4K44 r1r2r3r4r’4 • The new key is intended to be r1r2r3r4r’4r5 © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 25 Implicit Key Authentication? • Simple fusion of the sets corresponding to the EI, RI, S, RS of the two protocols • A little bit longer to write… But extremely regular! • Several attacks found... – Ex: the use of the value r1 and of the services 1 r K rnr’n and K1nrnr’n provides the secret 1 1n © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 26 Scenario • Adding of a 4-th member M1 r1 M r1 r2 r1r2 M 2 3 r2r3r’3K13 r1r3r’3K23 I r2r3r’3K13 r1r3r’3K23 r1r2r’3K33 r1r2r3r’3 M4 • I intercepts the broadcast of the Key Gen. • I convince M3 to add a new member in the group and uses the first round of the M.A. protocol to produce a broadcast • I shares a key with all members but M3... © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 27 Eventually... Property Result Implicit Key Authentication KO: Up to n-1 users fooled KO: Compromising 1 long- Perfect Forward Secrecy term key n-1 Users fooled Resistance to Known Keys Attacks KO: 1 Known-Key © UCL Crypto group Feb-15 1 User fooled Analysis of the A-GDH.2 Protocols 28 Further Directions • Incorporating our machinery in more general models • Modify this protocol suite in such a way that is correct from our model point of view! © UCL Crypto group Feb-15 Analysis of the A-GDH.2 Protocols 29