advertisement

Efficient Self-Healing Group Key Distribution with Revocation Capability by Donggang Liu, Peng Ning, Kun Sun Presented by Haihui Huang (hhuang3@eos.ncsu.edu) 1 Outline • • • • • • • Introduction Group key distribution overview Self-healing key distribution Revocation capability Novel personal key distribution Contribution and conclusion Future work 2 Introduction • Common way to ensure communication security: encrypt and authenticate messages • Challenge: – how to distribute keys to valid nodes • Challenges in ensuring communication security for mobile wireless ad hoc networks over unreliable channels – Volatile membership – Disruption of communication by adversary – Resource constraints 3 Group Key Distribution Techniques • Group controller – Can’t scale to large groups • Iolus – subgroup hierarchy • Logical Key Hierarchy(LKH) or Key Graph – Keys are organized into a tree hierarchy • Self-healing key distribution • Stateless key distribution 4 Self-healing Key Distribution • Users are capable of recovering lost group keys on their own • No need to request additional transmissions from the group manager – Lower network traffic – Decrease the load on the group manager • To recover the key via self-healing – A user must be a member both before and after the session in which a particular key is sent 5 Revocation Capability • The ability to revoke users and thus prevent them from learning new keys • t-revocation capability – Possible to prevent at most t users at a time from learning new session key – With the revocation polynomial g(x) constructed as g(x)=(x-r1)(x-r2)…(x-rw) 6 Personal Key Share Distribution-Scheme 1 • t-revocation capability • To distribute keys to selected group members so that each member shares a distinct personal key with the group manage • But the other(revoked) group members and adversary cannot get any information of the keys • Choose a random t-degree polynomial f(x) from Fq[x] and select f(i) to be the personal key share for each member • Group manager broadcasts a single polynomial w(x) so that – Valid group member Ui can recover f(i) from w(x) and personal secret Si – Revoked group member Ui’ will NOT be able to recover f(i’) 7 Personal Key Share Distribution-Scheme 1(cont) • Construct w(x) with the help of a revocation polynomial g(x) and a masking polynomial h(x) by computing w(x)=g(x)*f(x)+h(x) • g(x) is constructed in such a way that – For valid member Ui, g(i) <> 0 – For revoked member Ui’, g(i’)==0 • Choose a random t-degree polynomial f(x) from Fq[x] and select f(i) to be the personal key share for each member • Group manager broadcasts a single polynomial w(x) so that – Valid group member Ui can recover f(i) from w(x) and personal secret Si : f(i) = ( w(i) - h(i) ) / g(i) – Revoked group member Ui’ will NOT be able to recover f(i’) as g(i’)==0 8 How to achieve self-healing • Use secret sharing – Based on polynomial interpolation – Bind the ability of users to recover from packet loss to the user’s membership status 9 How to achieve self-healing(2) • Split group session key Kj into two t-degree polynomials, pj(x) and qj(x) such that Kj=pj(x)+qj(x) • In session j1: broadcast polynomials {p1(x),…,pj1(x),qj1(x),…, qj(x) ,…qj2(x),…, qm(x)} • In session j2(j2>j1): broadcast polynomials {p1(x),…,pj1(x), …, pj(x),…,pj2(x),qj2(x),…,qm(x)} • For any session j(j1<j<j2), we can recover Kj=pj(x)+qj(x) 10 Personal Key Share Distribution- Scheme 2 • Self-healing key distribution with t-revocation capability • In the jth session key distribution, given a set of revoked member Ids, Rj={r1,r2,…,rwj), |Rj|=wj<t • Group manager broadcasts message Bj= {Rj} ∪{Pj,i(x) = gj(x)pi(x) + hj,i(x)}i=1,...,j ∪{Qj,i(x) = gj(x)qi(x) + hj,i+1(x)}i=j,…m where gj(x) = (x − r1)(x − r2)...(x − rwj ). 11 Reducing Storage Requirement • In Scheme 2, the storage overhead in each group member is O(m2logq). – m: total sessions – logq: session key size • Use only ONE masking polynomial for each pi(x),qi(x) • Reduce the storage requirement in each member from O(m2logq) to O(mlogq) in Scheme 3 12 Personal Key Share Distribution- Scheme 3 • Improved self-healing key distribution with trevocation capability • In the jth session key distribution, given a set of revoked member Ids, Rj={r1,r2,…,rwj), |Rj|=wj<t • Group manager broadcasts message Bj= {Rj} ∪{Pi(x) = gj(x)pi(x) + hi(x)}i=1,...,j ∪{Qj,i(x) = qi(x) + fi(x)}i=j,…m where gj(x) = (x − r1)(x − r2)...(x − rwj ). 13 Personal Key Share Distribution- Scheme 4 • Trading off self-healing capability for less broadcast size • Introduce a “sliding window” of l sessions – only redundant information for the sessions that fall into this window is broadcasted – Can NOT ensure the same self-healing property as in previous schemes – Reduce storage overhead to (2m+2l-1)logq 14 Personal Key Share Distribution- Scheme 5 • Aimed at situations where they are relatively long term but infrequent communication failures • Introduce a “sliding window” of (l-1)d sessions – Assume each group member can receive at least d consecutive broadcast key distribution messages – Selectively include the same amount of redundant information from a large “window” of session(i.e. 2(l-1)d+1) in each key distribution message – storage overhead : (2m+2(l-1)d+1)logq 15 Conclusion • Presented several group key distribution schemes for very large and dynamic groups over reliable channels • Developed several efficient unconditionally secure and self-healing group key distribution schemes that significantly improved over the previous approaches • Developed 2 techniques that allow trade-offs between broadcast message size and recoverabilities of lost session keys 16 Future work • Develop a model that characterizes failures in large and highly mobile wireless networks • Further investigate the performance of the proposed schemes in this model • Seek more efficient ways to perform the initial key distribution for the proposed schemes 17 Questions? 18