Report

Distributed Multiple Secret Key Management for Cluster-based Ad Hoc Networks 分散式多重密鑰管理機制應用於群集 隨意型網路 長庚大學通識中心 李榮宗 Outline Introduction Background Distributed ID-based multiple secret key management scheme (IMKM) Conclusion 2 Introduction Ad-hoc networks and security concerns Authenticated key management protocols Scope of the work Summary of contributions 3 Ad-hoc networks and security concerns A mobile ad hoc network (MANET) is an autonomous system of mobile nodes connected through wireless links 4 Ad-hoc networks and security concerns (Cont’d) A cluster is a connected graph including a clusterhead (CH) responsible for establishing and organizing the cluster 5 4 3 1 2 8 6 Cluster head Gateway Node 7 5 Ad-hoc networks and security concerns (Cont’d) Deploying security mechanisms in MANETs is difficult Absence of fixed infrastructure Shared wireless medium Node mobility Limited resources of mobile devices Bandwidth-restricted Error-prone communication links 6 Ad-hoc networks and security concerns (Cont’d) Ad hoc networks are subject to various kinds of attacks Passive eavesdropping Active impersonation Message replay Message distortion key management is particularly difficult to implement in such networks 7 Authenticated key management protocols Threshold sharing-based key management with distributed authorities Session key management protocols Two-party authenticated key management protocols Multi-party authenticated key management protocols 8 Authenticated key management protocols (Cont’d) Threshold sharing-based key management with distributed authorities Using (t,n) threshold scheme Certificate exchanges consumes much bandwidth Does not provide verifiablity When t shareholders are compromised, the overall system security is broken 9 Authenticated key management protocols (Cont’d) Session key management protocol Two-party authenticated key management protocols by bilinear pairings Based on Discrete logarithm problems over elliptic curve groups Is not secure against key revealing attacks Does not provide perfect forward secrecy 10 Authenticated key management protocols (Cont’d) Multi-party authenticated key management protocols by bilinear pairings Suffers from the man-in-the-middle attack Suffers from the impersonation attack Disadvantages in number of rounds , pairingcomputation and communication bandwidth 11 Scope of work In this paper, we address key management issues in cluster-based mobile ad hoc networks We present a fully distributed ID-based multiple secret key management scheme (IMKM) as a combination of ID-based, multiple secret and threshold cryptography ID-based approach eliminates the need for certificate-based public-key distribution 12 Scope of work (Cont’d) Multiple secret key update scheme enhances system security and eliminate communication and computation overhead for key update Fully distributed threshold secret sharing scheme solves the single point of failure and compromise tolerance problems Cluster-based mechanism reduces routing overhead and provides more scalable solutions 13 Summary of contributions Our IMKM scheme provides complete and solid solutions for key management The overall system security is still guaranteed even when t shareholders are compromised in IMKM. When the network becomes sparse, it is quite difficult to collect t shares to reconstruct the secret. However, it is easy to adjust threshold t in IMKM which makes the system more robust and reliable. 14 Background Symmetric and public key cryptography Elliptic curve cryptosystems (ECC) Legrange interpolation polynomial Threshold sharing scheme Shuffling scheme Security schemes for attacks 15 Symmetric key and public key cryptography Symmetric key The same key is used to do both encryption and decryption. Advantages: efficient, easy to use Disadvantages: less secure than public key, problem of sharing keys Ex: DES, RC6, MD5, SHA-1, etc. 16 Symmetric key and public key cryptography (Cont’d) Public key Motivated by three limitations of symmetric key cryptography, that is, key delivery, key management and user authentication Advantages: encryption is stronger than symmetric key Disadvantages: much processing power, much longer data files are create and transmitted Ex: RSA, ElGamal, ECC, etc. 17 Elliptic curve cryptosystems (ECC) Based on the difficulty of solving elliptic curve discrete logarithm problem (ECDLP) (Ex: Q = kP) Smaller key sizes Low communication cost Faster implementation For resource-constrained environments, such as smart cards, and wireless devices 18 Elliptic curve cryptosystems (ECC) (Cont’d) Security comparisons of RSA, ElGamal and ECC RSA & ElGamal ECC Key length Necessary Computing The ratio of Key length（bits） （bits） workload（MIPS） key length 512 106 104 5:1 768 132 108 6:1 1024 160 1012 7:1 2048 210 1020 10:1 21000 600 1078 35:1 19 Legrange interpolation polynomial Given n 1 points x , y , x , y ,..., x , y , x , y , where x are distinct. Seek a polynomial with degree n such that f ( x) y 0 0 1 1 n-1 n-1 n n i 20 Legrange interpolation polynomial (Cont’d) The Lagrangian interpolating polynomial is given by: f ( x) ∑L ( x) f ( x ) where n in f (x) stands for the nth order polynomial that approximates the function y f (x) given at n 1 data points as xx x , y , x , y ,..., x , y , x , y and L ( x) n n i i 0 i n n 0 0 1 1 n-1 n-1 n n i j 0 , j i j xi x j Li (x) is a weighting function that includes a product of terms with terms of j i omitted 21 Legrange interpolation polynomial (Cont’d) Given a set of three data points {(0,3),(1,9),(2,21)}, we shall determine the Lagrange interpolation polynomial of degree 2 which passes through these points. First, we compute L0 ( x) ( x - 1)( x - 2) - x( x - 2) x( x - 1) , L1 ( x) , L2 ( x) 2 1 2 Lagrange interpolation polynomial is: f2 ( x) 3L0 ( x) 9L1 ( x) 21L2 ( x) 3x2 3x 3 22 Threshold sharing scheme The dealer chooses t 3, n 5 , and random polynomial f ( x) (3x2 3x 3) mod 17. Suppose the unique ID of each user i is IDi i , i 1,2,,5 , then the shares of each user are: S1 f (1) 9, S2 f (2) 4, S3 f (3) 5, S4 f (4) 12, S5 f (5) 8 That is the polynomial passes through points (1,9), (2,4), (3,5), (4,12), (5,8) 23 Threshold sharing scheme (Cont’d) After combining t shares (ex. S1, S3, S5), the original polynomial can be reconstructed by using the Legrange interpolation as follows: f ( x) [9 ((x133)()(1x55)) 5 ((x311)()(3x55)) 8 ((5x 11)()(5x33)) ] mod 17 [9 ( x 3)(8 x 5) 5 ( x 1)(4x 5) 8 ( x 1)(8 x 3) ] mod 17 (9(81 )(x 3)(x 5) 5(4) 1 ( x 1)(x 5) 8(81 )(x 1)(x 3)) mod 17 (9(15)(x 3)(x 5) 5(4)(x 1)(x 5) 8(15)(x 1)(x 3)) mod 17 (3x 2 3x 3) mod 17 24 Shuffling scheme To prevent the exposure of shares, the shuffling scheme is introduced First, each pair of nodes (i, j) securely exchange a shuffling factor di,j One node in the pair adds di, j to its partial share while the other one subtracts di, j For node i, it must apply all t −1 shuffling factors, either by adding or subtracting, to its partial share 25 Shuffling scheme (Cont’d) When a new member k joins the secret sharing network The shuffled partial share is generated as di',k di ,k i where i -1, x ≤0 sign ( x ) sign ( j i ) d ∑ 1, x 0 i , j and t j 1, j ≠i After receives t shuffled partial shares, node k recovers its share as: t ∑d i 1 ' i ,k t t i 1 i 1 t t t ∑(di ,k i ) ∑di ,k ∑∑ sign ( j - i) di , j ∑di ,k 0 dk i 1 j 1, j ≠i i 1 26 Security schemes for attacks Intrusion detection system (IDS) - Unwanted manipulations to systems Watchdog - Selfish behavior Packet leashes - Wormhole attack Rushing attack prevention (RAP) - Denial of service attack 27 Distributed ID-based multiple secret key management scheme Design goals and system models Network initialization Key revocation Multiple secrets key update scheme Key joining, key eviction Group key agreement protocol Protocol analysis 28 Design goals and system models Design goals It must not have a single point of compromise and failure It should be compromise-tolerant Efficiently and securely revoke keys of compromised nodes once detected and update keys of uncompromised nodes Efficient schemes to generate group session key 29 Design goals and system models (Cont’d) System models We envision a cluster-based MANET consisting of n clusterheads (CHs) called D-PKGs, D-PKGs are selected to enable secure and robust key revocation and update If a cluster-based routing protocol is used, the clusters established by the routing protocol can also be employed in our security conceptualization The size of the network may be dynamically changing with CH join, leave, or failure over time. 30 Design goals and system models (Cont’d) Each CHi has a unique ID, denoted by IDi Communications are potentially insecure and errorprone We assume that compromised CHs will eventually exhibit detectable misbehavior We also assume that adversaries compromise no more than (t 1) out of n CHs simultaneously, where t 1 n / 2 Nor can adversaries break the underlying cryptographic primitive on which we base our design 31 Network initialization Generation of pairing parameters and key initiation System setup: PKG (Private key generator) chooses a random number s ∈Zq* as the PKG’s private key. Ppub sP0 is the PKG’s public key. The system parameters of PKG are as follows: p, q, g, G1 , G2 , eˆ, P0 , Ppub , Pm , H1 , H 2 , H 3 32 Network initialization (Cont’d) Key extraction: CHi submits his identity information IDi to PKG. PKG computes Ii H1( IDi ) (1 ≤i ≤n) and CHi ’s public and private key pair: Qi ( I i s) P0 , S i ( I i s) -1 P0 PKG preloads the key pair and system parameters on CH i (1 ≤i ≤n) securely. 33 Generation of pair–wise keys In order to provide perfect forward secrecy, we modified McCullagh and Barreto’s scheme as follows: 1) Each CHi (1 ≤i ≤n) randomly chooses his ephemeral key xi Z q* , computes X i, j xi (I j P0 Ppub ) and sends X i, j to CHj (1 ≤ j ≤n, j i) . 2) After exchange the ephemeral values, all CHs can compute their pair–wise keys: ki, j eˆ(P0 , P0 ) xi eˆ( X j ,i , Si ) eˆ( X j ,i , Si ) xi xi x j xi x j ˆ ˆ e(P0 , P0 ) e(P0 , P0 ) (1 ≤i, j ≤n, i ≠j ) 34 Generation of pair–wise keys (Cont’d) The above pair-wise key agreement protocol satisfies all the following security properties: Implicit key authentication, Known session key security, No key-compromise impersonation, Perfect forward secrecy, No unknown key-share, No key control. Therefore, it is secure employed in MANETs. 35 Verifiable secret sharing 36 Verifiable secret sharing (Cont’d) Each CHi , creates a (t,n) threshold sharing of ai,0 by generating a random polynomial of degree t-1 t -1 * f ( x ) ∑l 0 ai ,l xl (mod q) over Z q , as: i 2) Each CHi computes I H ( ID ) (1 ≤ j ≤n) and securely sends an encrypted subshare, fi ( I j ) , to CHj , using pair-wise key Ki , j . 3) Each CHi broadcasts public values y g (mod p ) 4) Each CHj verifies that subshare f i ( I j ) by checking that g fi ( I j ) tl 10 ( y i,l ) ( I j )l (mod p) 1) j 1 j ai ,l i ,l 37 Verifiable secret sharing (Cont’d) 5) d j ∑i 1 f i ( I j ) P0 n Each CHj computes its share key, and broadcasts public key d j pub H 2 (Ppub )d j Any subset, , of size t CHs, can determine the master secret key: D ∑j∈ j (0)d j (a1,0 a 2,0 a n,0 ) P0 - Ii ( 0 ) , where j i ,i j I j -Ii (mod q) The public key, DPUB , of the master secret key, can be generated from any t CHs’ public keys: D pub ∑j∈ j (0)d j pub H 2 (Ppub )D 38 Key revocation The key revocation scheme is comprised of three sub-processes: Misbehavior notification Revocation generation Revocation verification 39 Misbehavior notification Upon detection of CHi’s misbehavior, CHj generates an accusation, {IDi , T j }K j,v , against CHi Securely transmits it to CHv (1 ≤v ≤n, v ≠i, j ) T is a time stamp used to withstand message replay attacks K is the pair-wise key of CHj and CHv j j ,v 40 Revocation generation When the number of accusations reaches a predefined revocation threshold, β t norml CHj, having the smallest IDs, generates a partial revocation, REVj H1 (IDi )d j Each CHj sends it to the revocation leader securely The revocation leader checks whether the equation H 2 (Ppub )REVj d j pub H1 (IDi ) holds. 41 Revocation generation (Cont’d) The revocation leader can construct a complete revocation from these partials using Lagrange interpolation: IDi' ∑j∈ j (0) REVj H 1 ( IDi ) D The revocation leader then floods IDi , IDi' throughout the network to inform others that CHi has been compromised. 42 Revocation verification Upon receipt of IDi' , each clusterhead verifies it by checking whether the equation H 2 ( Ppub ) IDi' H1 ( IDi ) D pub holds This means that IDi' has been correctly accumulated from all other t-1 unrevoked CHs Each clusterhead then records ID in its key revocation list (KRL) and declines to interact with it thereafter. 43 i Multiple secrets key update scheme To resist cryptanalysis, it is a good practice to update keys frequently. At each regular predetermined time interval, updates each CH’s share key, d j , to n (1 ≤m ≤U ) by replacing the d 'j ∑ f ( I ) P i j m i 1 generator, p0 , with pm of d j Key update is quite simple and efficient 44 Key joining Scheme I Each CHj creates a new subshare, f ( I ) , and securely sends it to CHk. CHk constructs its share as: d k = ∑j∈φ, j ≠k f j ( I k ) Pm CHk creates a (t,n) threshold sharing of ak , 0 by generating a random polynomial of degree, t-1, t -1 f k ( x) ∑l 0 ak ,l x l (mod q) and securely sends f ( I ) to each CHj ( j ∈ , j k ) . Upon receiving f ( I ) from CHk, each CHj reconstructs the share key, d 'j = d j + f k (I j )Pm 45 j k k k j j Key joining (Cont’d) Scheme II (shuffling scheme) Each CHj generates the partial share for CHk: d j , k = ∑i∈φ f i ( I j )λ j ( I k ) + δ j , where j ( I k ) is the Lagrange coefficient ∏ i∈φ,i ≠j II kj --IIii (mod q) , and 0 δ j = ∑v∈φ,v ≠j sign( I j - I v ) K j ,v , where sign( x) -11,, xx≤ 0 and K j,v is the shuffling factor. The shuffled share, d j ,k , is then returned to CHk. After receiving t partial shares, CHk can construct its share, d k = ∑j∈φ, j ≠k d j ,k Pm . 46 Key eviction When CHk is revoked, and the number of revoked CHs reaches the predetermined update threshold ( t ) : Each CHi chooses a random number, Δ i ∈Z q* , changes its share, a i ,0 , to a i ,0 i and securely sends i to all unrevoked CHj After receiving all i values, each CHj reconstructs the share key, d 'j d j (i ,i j i ) Pm 47 Group key agreement protocol We presented an efficient ID-based authenticated group key agreement (AGKA) protocols Scheme Each CHi randomly chooses an ephemeral key, Li. Each CHi constructs a Lagrange interpolating polynomial with degree n-1, as follows: Bi ( x) u 1 Li j 1, j u ( K n n ( x - Ki , j ) i ,u - K i , j ) (mod q) ain-1 x n-1 ai1 x ai0 (mod q) Each CHi then broadcasts (ai0 , ai1 , , ain-1 ) 48 Group key agreement protocol (Cont’d) Group key computation Each CHj uses the pair–wise session keys, K , to recover keys, Li , using the following equation: B(k ) [a ( K ) a ( K ) a ] mod q L After recovering all the keys, Li , each CHj computes the group session key as follows: j ,i n -1 j ,i in-1 j ,i i1 j ,i i0 i SK SK j ( L1 L2 Ln ) Pm Member leave Reprocesses AGKA protocol 49 Protocol analysis Security analysis Share key distribution Group key distribution Performance analysis Comparison in key update Verifiable secret sharing Comparison in group key distribution 50 Security analysis Share key distribution We compare the security of IMKM to that of RCBC(MOCA, URSA, AKM) and IBC-K. These five approaches are all based on threshold schemes (robust). When compromised t CHs, the CA’s (RCBC) private key, or the PKG’s (IBC-K) master secret key will be revealed. 51 Security analysis (Cont’d) The overall system security is still guaranteed even when t shareholders are compromised in IMKM. With IMKM, even compromise of the PKG does not reveal the master secret key. In summary, IMKM outperforms RCBC and IBC-K with respect to security. 52 Security analysis (Cont’d) Group key distribution The proposed authenticated group key agreement (AGKA) protocol satisfies the following security attributes: Implicit key authentication Known session key security Backward and forward secrecy No key-compromise impersonation No unknown key-share 53 Performance analysis We compare our IMKM with RCBC, with respect to key updates For RCBC, the duration spans from the first point of contact between a node and random D-CAs, to the point where the last node completes its key update. For IMKM, the key eviction process starts when the revocation leader broadcasts a key update message to other D-PKGs (CHs) and finishes after all the DPKGs have exchanged the key update materials. 54 Performance analysis (Cont’d) The key update time includes packet transmission time and all cryptographic processing time. IMKM key update avg completion time (sec) Network cluster size Speed RCBC key update avg completion time (sec) Network cluster size Speed (m/s) 10 20 30 40 (m/s) 5 3.729 8.106 16.174 27.977 5 99.986 132.292 149.857 198.699 10 4.029 9.032 16.594 29.741 10 100.352 131.788 150.51 15 3.964 9.613 17.103 30.241 15 10 99.09 20 30 40 199.69 132.439 150.489 200.767 55 Performance analysis (Cont’d) We also count the key update bandwidth overhead in terms of number of messages and bytes. It should be noted that overhead is similar at all mobility speeds, suggesting that both schemes are robust to mobility. 56 800 700 600 500 400 300 200 100 0 IMKM RCBC 316 312 3000 738 738 735 302 Overhead (messages) Overhead (messages) Performance analysis (Cont’d) 2620 2586 2554 2500 IMKM 2000 RCBC 1500 1038 1111 1097 1000 500 0 5 10 15 Mobility (m/s) Fig. 5.2 Average messages sent, 20 nodes 5 10 15 Mobility (m/s) Fig. 5.3 Average messages sent, 40 nodes 57 Performance analysis (Cont’d) 277455 278800 250000 IMKM 200000 RCBC 150000 100000 50000 40159 1200000 279130 40577 38824 0 Overhead (bytes) Overhead (bytes) 300000 1000000 942351 950521 960644 IMKM 800000 RCBC 600000 400000 200000 133731 143135 141385 0 5 10 15 Mobility (m/s) Fig. 5.4 Average bytes sent, 20 nodes 5 10 15 Mobility (m/s) Fig. 5.5 Average bytes sent, 40 nodes 58 Performance analysis (Cont’d) Performance of verifiable secret sharing 120 110 100 90 80 70 60 50 40 30 20 10 0 Mobility 5m/sec Mobility 10m/sec 99.83 95.31 93.61 Mobility 15m/sec Time (sec) 66.76 64.26 60.29 17.53 16.7717.03 10 30.41 28.43 27.85 20 30 40 # of nodes Fig. 5.1 Verifiable secret sharing: avg. delay vs. node speed 59 Performance analysis (Cont’d) Comparison in group key distribution Table 5.4 Comparison of AGKA protocols Protocol Round Scalar Pairings Bandwidth Barua’s ID-AGKA log3 n 9( n 1) 5n log 3 n 3 <5n(n-1) Du’s ID-AGKA 2 n(n+5) 4n 3(n-1) Lin’s AGKA 2 n 2n 2n IMKM Scheme 1 n None n - Round: The total number of rounds. - Scalar: The total number of scalar multiplications in G1. - Pairings: The total number of pairing computations. - Bandwidth: The total number of messages sent by CHs. 60 Conclusion Conclusion We have proposed a secure, efficient, and scalable distributed ID-based multiple secrets key management scheme (IMKM) for clusterbased MANETs. IMKM is a complete and solid solution for key management, which includes share key, pairwise key and group key distribution. 61 Conclusion (Cont’d) The master secret key is generated and distributed by all clusterheads which leads to more autonomous and flexible key update methods. The proposed IMKM scheme improves on the security and performance of previously proposed key management protocols (i.e., RCBC and IBC-K) for MANETs. 62 Conclusion (Cont’d) Besides, we presented an efficient one round ID-based authenticated group key agreement protocols, which minimize the number of rounds and bandwidth usage, as well as satisfies all primary security concerns. 63 Thanks! 64 67 68 69 70 71