Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

P2p-hgkm : an efficient hierarchical group key management protocol for mobile ad-hoc networks 2004

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
ubc_2004-0593.pdf
ubc_2004-0593.pdf [ 6.42MB ]
Metadata
JSON: 1.0051627.json
JSON-LD: 1.0051627+ld.json
RDF/XML (Pretty): 1.0051627.xml
RDF/JSON: 1.0051627+rdf.json
Turtle: 1.0051627+rdf-turtle.txt
N-Triples: 1.0051627+rdf-ntriples.txt
Citation
1.0051627.ris

Full Text

P 2 P - H G K M : A n Efficient Hierarchical Group Key Management Protocol for Mobile Ad-Hoc Networks by Peng Peng B.Sc, Peking University, 2000 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) we accept this thesis as conforming to the required standard The University of British Columbia July 2004 © Peng Peng, 2004 UBCl ml FACULTY OF GRADUATE STUDIES THE UNIVERSITY OF BRITISH COLUMBIA Library Authorization In presenting this thesis in partial fulfillment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Name of Author (please print) Date (dd/mm/yyyy) Title of Thesis: Degree: [Attfrtfrr Of SCceAtE. Year: ^ ,00 4 Department of The University of British Columbia Vancouver, BC Canada grad.ubc.ca/forms/?formlD=THS page 1 of 1 last updated: 20-Jul-04 Abstract Wireless networks are growing rapidly in recent years and research in wireless technology is gaining increasing attention, especially in the area of security. Our thesis addresses an interesting security problem in wireless ad-hoc network: the P2P dynamic secure group key establishment. To secure group communication in an ad-hoc network, a group key shared by all group members is required. This group key should be updated when there are membership changes in the group, e.g. when a new member joins or a current member leaves. In this thesis, we propose a novel efficient P2P hierarchical group key management protocol for ad-hoc networks. We introduce a two-level hierarchical structure and a new scheme of group key update. The idea is to divide the group into subgroups; each maintains its subgroup key and links with other subgroups in a ring structure. A salient feature of our scheme is that group key gets updated and managed in a P2P manner. By introducing subgroups, public encryptions, and unicasts in key updates, will be limited in one subgroup and computation load is distributed to many hosts. Both theoretical analysis and experiment results show that our protocol performs well for the key establishment problem in ad-hoc network in terms of both computing cost and bandwidth overhead. ii Contents Abstract ii Contents iii List of Figures vi List of Tables viii Acknowledgements x Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Overview of P2P-HGKM Protocol 4 1.3 Thesis Contribution 6 1.4 Synopsis 7 Chapter 2 Background and Related Work 8 2.1 Multicast Routing in Ad-Hoc Network 8 2.2 Public Key and Symmetric Key Encryption 10 2.3 Group Key Establishment Protocols 13 2.3.1 Key Agreement Protocols 13 2.3.2 Tree-Based Key Management Protocols 16 ii i 2.4 Related Work 19 Chapter 3 Design and Implementation 22 3.1 Overview of the P2P-HGKM System 22 3.2 Initialization of P2P-HGKM System 26 3.2.1 Multicast the BUILD_REQUEST and Reply (Step 1 and 2)... .28 3.2.2 Dividing Group into Subgroups (Step 3) 30 3.2.3 Initialize and Distribute the Subgroup Key (Step 4) 32 3.2.4 Initialize and Distribute the Group Key (Step 5) 33 3.3 Key update at Join Event 36 3.4 Key Update at Leave Event 39 3.4.1 Non-Leader Node Leave 39 3.4.2 Leader Node Leave - Merge 41 3.4.3 Leader Node Leave - Select a new subgroup leader 45 Chapter 4 P2P-HGKM Performance and Evaluation 49 4.1 P2P-HGKM Security Analysis 50 4.2 P2P-HGKM Experiment Overview 51 4.3 Computational Cost 52 4.3.1 Comparing with other protocols 52 iv 4.3.2 Performance 54 4.4 Communication Cost 59 4.4.1 Comparing with other protocols 59 4.4.2 Performance 60 Chapter 5 Conclusion and Future Work 67 5.1 Conclusion 67 5.2 Future Work 68 Appendix 70 Bibliography 72 v List of Figures Figure 1.1 802.11 Wireless LAN 2 Figure 1.2 Ad-hoc networks 2 Figure 1.3 Members of multicast group are divided into subgroups 5 Figure 1.4 Subgroups link in a ring structure 5 Figure 1.5 Kgroup propagates along the subgroup ring 6 Figure 2.1 ODMRP 9 Figure 2.2 Public key encryptions 11 Figure 2.3 Diffie-Hellman key exchange 13 Figure 2.4 GDH 2.0 algorithm 15 Figure 2.5 GDH 2.0 works in a group with 4 members 15 Figure 2.6 Tree-Based key management protocol 17 Figure 2.7 Step 2 of AT-GDH algorithm 19 Figure 2.8 Step 2 of AT-GDH algorithm 20 Figure 3.1 Multicast group is divided into subgroups 23 Figure 3.2 Subgroups are linked by joint leaders into a ring structure 24 vi Figure 3.3. Key update at Leave Event 25 Figure 3.4 Software layer 26 Figure 3.5 Broadcast the BUILD_SUBGROUP_REQUEST 28 Figure 3.6 Build subgroups 30 Figure 3.7 Initialize and distribute subgroup and group key 33 Figure 3.8 Distribute Kgroup along the subgroup ring 34 Figure 3.9 Key update at Join Event 38 Figure 3.10 Non-leader node leave 40 Figure 3.11 Leader node leave and subgroup merge 44 Figure 3.12 Leaver node leave and a new leader is selected 47 Figure 4.1 Experiment result: public key encryption/decryption 56 Figure 4.2 Experiment result: symmetric key encryption 57 Figure 4.3 Experiment result: symmetric key decryption 58 Figure 4.4 Experiment result: number of unicast 61 Figure 4.5 Experiment result: message size of unicast 63 Figure 4.6 Experiment result: number of unicast 64 Figure 4.7 Experiment result: message size of unicast 65 Figure 5.1 Complex structure of subgroups 69 vii List of Tables Table 2.1 DES, 3DES and AES 11 Table 2.2 Communication and computation cost of GDH 2.0 15 Table 2.3 Communication/Computation cost of Tree-Based key management 18 Table 2.4 Communication/Computation cost of GDH 2.0 and AT-GDH 20 Table 3.1 Communication cost of start-up 35 Table 3.2 Computation cost of start-up 35 Table 3.3 Computation cost at Join Event 38 Table 3.4 Communication cost at Join Event 38 Table 3.5 Computation cost at Leave Event (non-leader node) 41 Table 3.6 Communication cost at Leave Event (non-leader node) 41 Table 3.7 Computation cost at Leave Event (merge) 44 Table 3.8 Communication cost at Leave Event (merge) 45 Table 3.9 Computation cost at Leave Event (replicate a new leader) 47 Table 3.10 Communication cost at Leave Event (replicate a new leader) 48 Table 4.1 A summary of computation cost 52 viii Table 4.2 Computation cost comparison 53 Table 4.3 Summary of communication cost 59 Table 4.4 Communication cost comparison 60 ix Acknowledgements I am greatly indebted to my supervisor, Dr. Son Vuong. Completing this thesis would have been difficult without his inspiration and encouragement. I learnt a lot from Dr. Vuong in my years at UBC. I am also grateful to Dr. Konstantin Beznosov for being my second reader. Peng Peng The University of British Columbia August 2004 x Chapter 1 Introduction 1.1 Motivation Wireless networks are growing rapidly in recent years. Wireless technology is gaining more and more attention from both academia and industry. Most wireless networks used today, e.g. the cell phone networks and the 802.11 Wireless LAN, are based on the wireless network model with pre-existing wired network infrastructures. Packets from source wireless hosts are received by nearby base stations, then injected into the underlying network infrastructure and then finally transferred to destination hosts, as shown in Figure 1.1. [13] 1 Firewall Figure 1.1 802.11 Wireless L A N Another wireless network model, which is actively researched, is the ad-hoc network. This network is formed by only mobile hosts and requires no pre-existing network infrastructure. Hosts with wireless capability form an ad-hoc network instantly and packets can be delivered to any host in the network. Since there is no base station and no underlying network infrastructure in ad-hoc networks, some mobile hosts work as routers to relay packets from source to destination, as shown in Figure 1.2. It's very easy and economic to form an ad-hoc network in real time. Ad-hoc network is ideal in situations like battlefield or rescuer area where fixed network infrastructure is very hard to deploy. Figure 1.2 Ad-hoc networks. In ad-hoc network, intermediate nodes relay packets from source to destination 2 Group-oriented network applications can be easily conducted in this new network environment. For example, in a conference room, users can form an ad-hoc network instantly with their wireless devices, e.g. notebook computers, PDAs, or even cell phones, without requiring any pre-installed cables or base stations. They can use this fast setup ad-hoc network for conducting a videoconference, sharing files or even playing interactive games. Before the ad-hoc network concept can be widely accepted, several issues need to be resolved. For example, security is a major challenge. To secure group communication over an ad-hoc network, a group key (Kgroup) shared by all members of the group is needed. Packets will be encrypted with a group key Kgroup by the sender and decrypted with the same Kgwup by receivers. The group key Kgroup should always be kept confidential and should be updated timely whenever there are membership changes in the group. For example, if a new host joins the group, we should update the Kgroup so all past communication encrypted with the old Kgroup is kept secret to the new member. If a member node leaves, Kgroup should also be updated to keep future communications secret to the leaving node. Many group key establishment protocols, e.g. [1], [2], [3], [4], [5], [6] and [17] have been proposed. Protocols in [1], [2], [3] and [17] are designed for group key establishment problem in general, and protocols in [4], [5] and [6] are proposed for group key establishment problem in ad-hoc networks. Unfortunately, none of these protocols are adaptive to the key establishment problem in ad-hoc networks. Key management protocols proposed in [1], [2], [3] and [17] depends on a reliable central key server or key management nodes, where as key agreement protocols in [4], [5] and [6] require 3 exponentiation computation. Besides, they are not communication efficient. A common problem of these protocols is that by design, they did not take into account the unique features of a wireless ad-hoc network. For example, we know that wireless devices, e.g. PDAs, cell phones and notebooks, are usually lightweight, powered by batteries and do not have strong computing ability. So by design, computational load should be distributed among multiple hosts. Heavy computation work on a single host should be avoided. Secondly, radio signal used in wireless communication propagates in every direction in the air. So in wireless network, a local broadcast to all neighbors within the radio range uses no significant more time and resource than a unicast. A well-designed group key establishment protocol should take these features into consideration and try its best to be adaptive to the ad-hoc network environment. 1.2 Overview of P2P-HGKM Protocol The goal of our work is to propose a communication and computation efficient group key establishment protocol in ad-hoc network. The idea is to divide the multicast group into several subgroups, let each subgroup have its subgroup key shared by all members of the subgroup. Each subgroup has two leader nodes, and each leader is a joint leader of two subgroups. For example, in Figure 1.3, all member nodes are divided into three subgroups - 5/, S2 and S3, and M,9 is the joint leader of S] and S3. We can assume that all subgroups are linked in a ring structure, as shown in Figure 1.4. 4 © /i f © s, Sw §f* i^i* ] S 3 : M s , M e . M w M „ V 0 0 / ^~^) Member Node 7 .-'—<C \ \ W Leader Node \ o Non-Member Node © Figure 1.3 Members of multicast group are divided into subgroups. 5j V Mi M [M M 14 j M S2 tr-j Figure 1.4 Subgroups link in a ring structure Without the concept of subgroup, an update Kgroup would have to be encrypted and unicast to each individual host. This is neither computational nor communication 5 efficient. By introducing subgroups and subgroup keys, updated Kgroup can be encrypted with subgroup keys and multicast to the corresponding subgroups. For example, in Figure 1.5, KgwUp is updated by Mjg, encrypted with subgroup key (Kj) of subgroup Sj and multicast (Kgroup)Ki to 5/. When M8 - the other leader node of Si, receives this message, M8 decrypts (Kgroup)K, and gets Kgroup. Since M8 is also the leader of S2, M8 will then encrypt Kgroup with K2 and multicast (Kgroup)K2 to S2. In this way, Kgroup can be propagated along the subgroup ring and finally received by all members, as shown in Figure 1.5. Figure 1.5 Kgroup propagates along the subgroup ring 1.3 Thesis Contribution • We propose a new efficient method for solving the group key management problem in ad-hoc network. Our protocol provides efficient and reliable key management service and is well adaptive to the mobile environment of ad-hoc network. 6 • We introduce the idea of subgroup and subgroup key, and we uniquely link all subgroups into a ring structure. Our design eliminates the central key server. Instead all hosts work in a peer-to-peer fashion. We use P2P- HGKM as the name of our protocol. It stands for P2P Hierarchical Group Key Management Protocol. • We design and implement P2P-HGKM protocol using Java and conduct extensive experiments and theoretical analysis to evaluate the performance of our protocol. 1.4 Synopsis The rest of the thesis is organized as follows. Chapter 2 introduces some background knowledge, including multicast routing algorithms in ad-hoc network, the public key and symmetric key encryption system, and some related group key establishment protocols. Chapter 3 discusses the design and implementation details of the protocol. In Chapter 4, we evaluate the performance of the protocol and compare P2P- HGKM with several existing key establishment protocols. Finally in Chapter 5 we present concluding remarks and offer suggestions for possible future work. 7 Chapter 2 Background and Related Work 2.1 Multicast Routing in Ad-Hoc Network The routing problem in ad-hoc network has been an active topic for many years. Some unicast routing algorithms, e.g. [7], and multicast routing algorithms, e.g. [8] [9] and [10], have been proposed earlier. Cordeiro et.al. summarized current multicast protocols for ad-hoc networks in [11]. Our key management protocol uses multicast to send protocol messages. Hence an efficient multicast routing algorithm is the basis of our protocol. We used the On-Demand Multicast Routing Protocol proposed in [10] due to its simplicity, efficiency and its support for both multicast and unicast. ODMRP (On-Demand Multicast Routing Protocol) is a mesh-based protocol that uses a forwarding group concept (only a subset of nodes forward the multicast packets instead of using system wide broadcast). The multicast routes are established on demand 8 - when a group member has packets to send but there does not exist a route to the multicast group, the requesting node first broadcasts a Join-Query packet to the entire network, as shown in Figure 2.1. When an intermediate node receives this Join-Query packet, it stores the upstream node ID into its routing table. It also stores the source ID and the sequence number in its message cache to detect any potential duplicate. If the Join-Query message already exists, it is discarded; otherwise, the Join Query message is rebroadcast to neighboring nodes. Figure 2.1 ODMRP. Source node broadcasts Join-Query and waits Join-Reply from receivers Besides re-broadcasting the Join-Query packet when a multicast group member receives a Join-Query packet, they also broadcast a Join-Reply packet containing the upstream ID to its neighbors. When a neighbor node receives this Join-Reply packet, it checks if the upstream ID in Join-Reply packet matches its own node ID. If it does, the node realizes that it is on the path to the source and thus it belongs to the forwarding group (FG). The node sets its forwarding group flag (FG_FLAG) and then creates and 5*Join Query 9 broadcasts its own Join-Reply packet. So in this way, forwarding group members propagate the Join-Reply until it reaches the source node via the selected (shortest) path. After establishing the forwarding group (FG), members of the multicast group can multicast packets to the whole group via FG, and only nodes in the FG will rebroadcast data packets received. As long as the source node has data to send, it will periodically send Join-Query packets to refresh the forwarding group and the routes. As we will see in Chapter 3, most key management messages exchanged in our protocol are multicast messages, so we use ODMRP as the supporting multicast routing protocol for our system. Another reason for choosing ODMRP is because ODMRP supports unicast [12]. Hence we don't need to include another unicast routing protocol in our system, which greatly simplifies our design. We also combine ODMRP with our protocol by using some key management messages in our protocol for routing discovery. This further reduces the number of messages required in key update. 2.2 Public Key and Symmetric Key Encryption Modern cryptography systems include symmetric key algorithms and public key algorithms. In symmetric key algorithm, the same key is used for encryption and decryption. Many symmetric key algorithms have been developed and widely used, e.g. DES, Triple DES and AES. We summarize these algorithms in Table 2.1. 10 Key Length(bits) Plaintext (bits) Cipher Text (bits) Strong for use? DES 56 63 64 No longer 3DES 112 (2x 56) 64 64 Yes AES 128 128 128 Yes 128 256 128 Yes Table 2.1 DES, 3DES and AES Symmetric Key encryption algorithms, e.g. AES and 3DES, are widely used in massive data encryption because of their efficiency - they are much faster than most public key algorithms. Symmetric key algorithms require all parties to possess the secret key before communication. Thus we need a way to secretly distribute the key. This has always been a weak link. In 1976, two researchers at Stanford University, Diffie and Hellman, proposed a radically new kind of cryptosystem - the public key cryptosystem, to solve this problem [14]. In public key cryptosystem, a pair of keys - a public key and a private key is presented. The public key is openly known to all communication parties, while the private key is always kept confidential by the key owner. Deducing the private key from the public key should be exceedingly difficult. Figure 2.3 depicts how public key encryption works. If A wants to securely send a plain text P to B, A first acquires B's public key Eb from B or from a trusted third party. Then A will encrypt P with Eb and send (P)Eb to B. By receiving the encrypted message, B decrypts (P)Eb with its private key Db, and extracts the correct content of the message P - ((P) Eb) Db. (P)£„ P - Plain Text ( ( P ) E b ) D b = P £ 6 -Publ ic Key of B * D B - Private Key of B Figure 2.2 Public key encryptions 11 One of the widely used public cryptosystem is the RSA system, developed by Rivest, Shamir and Adleman in 1978 [15]. The RSA algorithm is based on the difficulty of factoring large numbers. The public and private key is at least 1024 bits in the RSA system for good security. Each block of plaintext for encryption and decryption is also 1024 bits long, versus 64 bits cipher in DES and 128-bits cipher in AES. Despite its strong security, there is a drawback of RSA system. The RSA algorithm takes more time for encryption and decryption than symmetric key algorithms. So in practice, RSA system is usually used for key distribution, instead of massive data encryption. Both symmetric key and public key encryption is used in our key management protocol. In our design, members of the multicast group G have group key - Kgwup. Kgroup is a symmetric key (128 bits AES key) and is for data encryption. Each member node also has the subgroup key(s) of the subgroup(s) they are in. For example, if Mj is the joint leader of both Si and S2, then Mi will have subgroup key Ki and K2. Subgroup key is also a 128 bit symmetric key, which is used to encrypt the updated key Kgroup. A subgroup key is shared by all members of the subgroup. As a result when there is a membership change in Si, Kt is also updated. Each node in our system (both group members and non-group members) also has a pair of public key (1024 bits RSA key): for node Mh £, is its public and Dt is its private key. Public key encryption is used to encrypt updated Kgwup or subgroup keys when there is no valid subgroup/group key to use. For example, when a node joins the multicast group, this new member does not have any subgroup key or group key, thus we use its public key for encryption. The key update at Leave Event also uses public encryption. We will describe this in detail in Chapter 3. 12 2.3 Group Key Establishment Protocols In general, key establishment protocols can be classified into two categories: key management (key distribution) and key agreement. In key management protocols, group key is usually created and updated by a central key server, and then securely distributed to all members. In key agreement protocols, each node contributes a fraction of the group key and the creation and update of group key is the joint work of all members. 2.3.1 Key Agreement Protocols In Key agreement protocols, [2], [16] and [17], each member contributes a fraction of the group key and the group key is constructed by the joint work of all members. Al l key agreement protocols are extensions of Diffie-Hellman key exchange [14]. Hence we will first discuss Diffie-Hellman key exchange. Then we will briefly discuss GDH 2.0(Group Diffie-Hellman) [2] as an example of key agreement protocol. Diffie-Hellman key exchange was first proposed in 1976 by Diffie and Hellman to solve the problem of establishing a shared secret key via an insecure channel. The key exchange protocol works like this: A picks x B picks y B computes (g* mod n)" mod n = gx» mod n n = g** mod n Figure 2.3 Diffie-Hellman key exchange n, g, g* mod n g* mod n A computes 13 If node A and B want to establish a shared key via an un-secure channel, they first agree on two large numbers, n and g where n is a prime and (n-l)/2 is also a prime, n and g can be public. Then A picks a large number x and keeps it secret, and B also picks a secret number y. A computes (gxmod n) and sends this to B. Similarly, B sends (g'mod n) to A. By receiving (gxmod n) from B, A computes ((gymod nf mod n). Similarly, B computes ((gxmod nf mod n) where (gxmod n) is from A. After the key exchange, both A and B have (g^mod n) and this is the established shared key. (((g'mod nfmod n) = ((gxmod nf mod n) = (g^mod n) ). The security of Diffie-Hellman key exchange lays in the fact that, deducing x from (gxmod n) is hard. So even if an eavesdropper has (gxmod n) and (gymod n) and g and n, he still cannot deduce either x or y, and thus cannot compute the shared key (g^mod n). Despite its elegance, Diffie-Hellman key exchange is vulnerable to man-in- the-middle attack. Michael Steiner, Gene Tsudik and Michael Waidner extended DH key exchange to N-Party key agreement - GDH 2.0 in [2]. Figure 2.4 is the GDH 2.0 algorithm and Figure 2.5 depicts how GDH 2.0 works in a group with 4 members. 14 Group Diffie-Hellman Algorithm (GDH 2.0) Roundi(l <i< n-l) 1. Member M, selects a random integer r, eZ*9 2. M, sends Mi+1: o^(Ffk=1 rk)axid of((Ftk=1 rk)/rj), V 1 <j < n Round n: 1. Member M„ selects a random r„ e Z*q 2. M„ sends each M, a number y, = o^((LTj=i rj)/ri). 3. Each member Mi then computes the final key as 5n = y , A r i = o^(ITj^rj). Figure 2.4 GDH 2.0 algorithm Figure 2.5 GDH 2.0 works in a group with 4 members. Message (n-l) unicast + 1 multicast Round n Exponentiation (i+1) for M{ (i < n) n for M„ Total number of exp. = 0(n2) Table 2.2 Communication and computation cost of GDH 2.0 15 GDH.2 performs well in wired network. But applying GDH.2 directly to the group key establishment problem in ad-hoc network may not yield the same result. Group key in key agreement protocols is a combination of contributions from all member nodes. For this reason, each membership change will lead to a change of the group key and will cause all members to conduct exponentiation computations. Generally, key agreement protocols are not scalable in large networks because • The cost for updating Kgroup at Join Event is same as Leave Event for key agreement protocols. But we know the key update at Join Event could be complete with much less cost if we use the existing group key (Kgroup_0id) to encrypt the updated Kgroup. • As shown in Figure 2.5, the last node in GDH 2.0 needs to do (AM) exponential computations, while the first node only needs two exponential computations. The unbalanced work load will make the last node a bottleneck of the key agreement protocol and a vulnerable node of the system. 2.3.2 Tree-Based Key Management Protocols In key management protocols, a central key management server is usually present in the system, and group key are initialized, updated and distributed by the key management server. Wong et.al. proposed a Tree-Based key management protocol in [1]. We will briefly introduce Wong's protocol as an example of key management protocol here. 16 Assuming a multicast group has n members, Mj through M„, and there is a central key server in the system that manages membership and keys. The central key server stores a key tree, as shown in Figure 2.6. Each node also stores all the keys from the leaf up to the root in the key tree. For example, in Figure 2.6. M 9 stores k9, kc and kwol. Figure 2.6 Tree-Based key management protocol When a new node joins the group, the key server adds this new member as a leaf node in the key tree, updates all the keys from the new node up to the K r o o t in the key tree and securely distributes them. For example, in Figure 2.6, if M 9 is the new member, then K c and K r 0 0 l in the key tree should be updated. Updated K c will be encrypted with Kc_oid and multicast to M 7 and M 8 ( ( K C ) K C M ^ > { M 7 , M g } ) . Updated K r o o t will be encrypted with Kroot_oid and multicast to the whole group { { K r o o t ) K r o o t oW=>G). Updated K r o o t and Xcwill be grouped together, encrypted with k9 and unicast to M 9 ( ( K r o o „ K C ) K 9 —> M 9 ) . Key update at node leaving is more complicated. Al l the keys possessed by the leaving node should be updated in order to secure future communication. For example, in Figure 2.6, if M 9 is the leaving node, then K c and K r o o t should be updated because they 17 are held by M9. KA and KB are not affected by the leaving node and can be used to encrypt the updated key(s). Updated Kroot is encrypted with KA for Mh M2, M3 ((Kroot)KA => {Mi, M2M3}), and encrypted with KB for M4M5M6 ((Krool)KB =>{M4, M5, M6}).Updated Kroot and Kc are grouped together, encrypted with k7 for M7i and encrypted k8 with for M8. {(Kroot, KC)K7 - M7 ; (Krool, KC)K8 -> M8) Join Leave Communication Cost h multicast + 1 unicast (h-1) x (d-1) multicast Computation Cost Request node: (h-l) symm deer Non-Req node: nxdl(d-Y) symm deer Key server: 2x(/z-l) symm encr Request node: 0 Non-Req node: nxd/(d-l) symm deer Key server: dx(h-l) symm encr * h - height of key tree; d - degree of key tree symm deer - symmetric decryption symm encr - symmetric encryption Table 2.3 Communication/Computation cost of Tree-Based key management The tree-based key management works efficiently in wired networks with a well- selected parameter d. But the protocol may not work well in general ad-hoc networks because the protocol requires a powerful and reliable key server. This requirement is very hard to satisfy in an ad-hoc network. Wireless hosts in ad-hoc networks are mobile and connections are not reliable. Also, as mentioned before, they are usually lightweight devices like PDAs and cannot be a key server for the whole system. Heavy computation load may totally weight down this wireless device and fail the whole key management protocols. 18 2.4 Related Work Protocols in [4], [5] and [6] are proposed for the key establishment problem in ad-hoc network and they are all key agreement protocols. Here we briefly discuss the AT-GDH protocol in [5]. The "Efficient Key Agreement for Ad-hoc Networks" (AT-GDH) proposed by Maarit in [5] is an extension of GDH 2.0 in ad-hoc network. The protocol has two steps. At the first step, a spanning tree is constructed, each member contributes a fraction to the group key and the contributions are gathered from leaf nodes up to the root, as shown in Figure 2.7. At the second step, the root node combines these key fractions and sends back the results to all nodes in the spanning tree. b) Step Lb Figure 2.7 Step 1 of AT-GDH algorithm. At step 1, contributions gather at the root node. 19 b) Step 2.b Figure 2.8 Step 2 of AT-GDH algorithm. At step 2, root sends back the combination of contributions to all nodes. GDH 2.0 • -. : AT-GDH Communication Cost JV-1 Unicast + 1 Multicast 2x N Unicast N Round . 2k x (logkN) Round Computation Cost 0(N2) Exponentiation. 0(NlogkN) Exponentiation Table 2.4 Communication/Computation cost of GDH 2.0 and AT-GDH Unicast in AT-GDH can be parallel and exponentiation computation is distributed with the introduction of tree structure. From Table 2.4 we can see that AT- GDH requires fewer rounds of message exchanges and less exponential computations than GDH 2.0. Despite this improvement in performance, AT-GDH still suffers from the following problems: • The cost of key update at Join Event is the same as Leave Event. 20 Root node in the tree structure does heavy computation work and failure of the root node will collapse the key agreement services. The root node becomes a single failure node in the system. The number of unicast and exponentiation computation is still at the order of 0(N) and 0(NlogkN). 21 Chapter 3 Design and Implementation 3.1 Overview of the P2P-HGKM System Our system is composed of many wireless hosts that form an ad-hoc network instantly, as discussed in Chapter 1. Some (or all) of these hosts are members of a multicast group G and they shares a group key (Kgroup) for secure group communication. To update Kgroup at Join Event, we can use the Kgroup before update to encrypt the updated Kgroup, and multicast (Kgroup)KgroupMto all group membeTs((Kgroup)Kgroupold => G). Updating Kgroup at leave event is more complicated and is the key question in key establishment problem. Because the leaving node also holds the old group key (Kgroupoid), so we cannot encrypt Kgroup with Kgroupoid or any key known to the leaving node, as we did at the key update of Join Event. A generic way to update Kgroup is to encrypt the 22 updated Kgmup with the public key (£,) of each member (A/,) and unicast encrypted (Kgroup)Ei to Mi. The generic algorithm requires (AM) public key encryptions and (AM) unicasts and this is very inefficient. So we introduce redundant keys and more complex structure in order to reduce the communication and computation cost for updating Kgroup at Leave Event. Our idea is to divide G into several subgroups based on geographic location, and let each subgroup have its subgroup key. Nodes in the same subgroup are close to each other and each subgroup has roughly the same number of nodes (M), as shown in Figure 3.1 (We assume all the nodes are evenly distributed in the system). We will discuss how we divide group G into subgroups in more details in Chapter 3.2.2. Figure 3.1 Multicast group G is divided into subgroups. 23 Each subgroup has two leader nodes, which are the key management nodes and membership management nodes of the subgroup. Each leader node is also a joint leader of another subgroup, e.g. in Figure 3.1. Mg is the joint leader of Si and 52. All the subgroups are linked by joint leader nodes into a ring structure, as shown in Figure 3.2 Figure 3.2 Subgroups are linked by joint leaders into a ring structure We chose the two-level ring structure because the ring structure is simple and easy to manage. And with the ring structure, updated key can be propagated simultaneously in two directions along the ring, as shown in Figure 3.3. By introducing subgroup and subgroup key, public encryption and unicasts at Leave Event are limited within one subgroup. For example, in Figure 3.3, if Af? is the leaving node, then both Kgroup and Ki should be updated. In our protocol, the subgroup leader with a smaller ID is responsible for the key update in this case (see more detailed discussion in Chapter 3.4.1). Here in our example, Ms is this leader node with a smaller ID (Mg's ID < M;9's ID), so Ms will be responsible for updating Kgroup and K;. Ms first 24 updates Kh encrypts Ki with Ei and E19 (the public key of M ; and M19) and unicasts (K])Ei and (K/)EI9 to Mi and M ; 9 individually. After updating Ki, Ms updates Kgroup, encrypts Kgroup with K2 and and propagates encrypted Kgroup along the subgroup ring, as shown in Figure 3.3. When M]7 - the other leader node of 52, receives this message, M ; 7 decrypts (Kgwup)K.2 and gets Kgroup. Since M]7 is also a leader of S3, M17 will then encrypt Kgroup with /if} and multicast (Kgr0up)K3 to 5^. In this way, Kgroup can be securely propagated along the subgroup ring and finally received by all members. Figure 3.3. Key update at Leave Event We implement our P2P-HGKM protocol and the supporting ODMRP protocol in Java. As shown in Figure 3.4, ODMRP provides multicast and unicast routing for both group oriented applications and our P2P-HGKM protocol. P2P-HGKM provides reliable and efficient group key management service to applications. Below ODMRP is the MAC layer of ad-hoc networks. 25 Routing Laye Figure 3.4 Software layer We know each wireless host has a unique identifier to identify itself from other hosts, such as the MAC address of network device. We can use this unique identifier as the ID in our system. In the following discussion, we still use 1 to 22 to number nodes in our system instead of actual MAC address for the reason of simplicity. In the remaining sections, we will discuss the specification of our P2P-HGKM protocol, including the start-up phase, key update at Join Event and key update and Leave Event. 3.2 Initialization of P2P-HGKM System At start-up, the P2P-HGKM system does not have a group key nor any subgroups. So the first thing the system needs to do is divide the group into subgroups, initialize the 26 group key and subgroup keys, then distribute these keys securely to all members. This phase has five steps: 1) Ms, the member node with the largest ID, is picked as the start node by running the bully election algorithm among all member nodes [18]. Ms multicasts a BUILD_SUBGROUP_REQUEST. Ms => G: BUILD_SUBGROUP_REQUEST. 2) Each member node Mj, receives the BlJILD_SUBGROUP_REQUEST, and sends back a reply REPLY_BUILD_SUBGROUP together with its public key (£,) to M,. V Mj, Mj € G, i jtj, Mj->MS: <REPLY_BUILD_SUBGROUP, Ej > 3) Ms divides all member nodes into subgroups based on REPLY_BUILD_SUBGROUP messages received. Then Ms multicasts the node-list of each subgroup to the group. Mi => G: <SC>, for all valid c. 4) By receiving the SUBGROUPJNFO messages from STEP 3, each member node stores the subgroup structures if it's in that subgroup. Then subgroup leaders are selected and they will initialize the subgroup keys and securely unicast the subgroup key to member of the subgroup. 5) The start node - Ms, initializes the group key (Kgroup), encrypts Kgroup and propagates Kgroup along the subgroup ring to all group members, as shown in Figure 3.3. 27 Details of each step are presented in the following sub sections. 3.2.1 Multicast the BUILD_REQUEST and Reply (Step 1 and 2) Figure 3.5 Broadcast the BUILD_SUBGROUP_REQUEST 1) 3Ms, Ms e G. M„ is selected as the start node. M„ the member node with the largest ID, is picked as the start node by running the bully election algorithm among all member nodes [18]. Ms will be responsible for multicasting BUILD_SUBGROUP_REQUEST (step 1), dividing multicast group G into subgroups (step 3), and initializing the group key (in step 5). 28 2) Ms G: BUILD_SUBGROUP_REQUEST Ms broadcasts BUILD_SUBGROUP_REQUEST. (Only messages along path 19->13- >16->9->20->21 is shown in Figure 3.5 to make the figure more readable.). The request message is also used as the ODMRP multicast route discovering message to further reduce the traffic. 3) \fMj,Mje G, s Mj->MS: {REPLY_BUILD_SUBGROUP, Es) As discussed in Chapter 2.1, by receiving the REQUEST message, each node will keep forwarding it to its neighbors. Each node also saves messages in a cache memory so that duplicate message will be discarded. Members of the multicast group (M7e G) will send back a REPLY_BUILD_SUBGROUP message, together with its public key (£,) to Ms. (as shown in Figure 3.5, M9 replies to M19) The REPLY_BUILD_SUBGROUP message goes backwards to the start node, similar to the way JOIN-REPLY message in ODMRP propagates. The REPLY message also brings back member nodes' IDs along the return path (in our example, the return path from M9 to M19 is <M9, M16>). So REPLY message from M9 has two fields: public key of M9 -E9, and list of member nodes in the return path - <M9, M16>. We will see how Ms uses the information in REPLY messages to divide G into subgroups in 3.2.2. 29 3.2.2 Dividing Group into Subgroups (Step 3) Leader Node (1)-(10): Order of pre- order traversal S , : . < M „ , Mv M3, Mj>, Leader Node: M ( s . M 8 S,: <M 8, M,e, Mf. Leader Node : M^M^ S3: <MiT,.Mu. M10, MI2. M,s>, Leader Node -M17. M19 Figure 3.6 Build subgroups With the REPLY messages in Step 1, Ms can divide G into subgroups. First, Ms inserts all member nodes in a tree structure rooted at Ms based on the return path in all REPLY messages. As shown in Figure 3.6, Mi9 is the root of the tree. Since the REPLY from M9 includes <M9, M16>, which means M9 comes after Mt6 in the return path, we will insert M9 as the child node of M!6, and M16 as child node of M!9 into the tree structure. Next, we will walk through the tree structure and divide all nodes into subgroups. We pre-define an average size of subgroup (M) based on the total number of members estimated in G. The value of M will affect the performance of the protocol. A large subgroup means more public key encryption and more unicast during key update, while a small subgroup means a high possibility of subgroup leader being the leaving node. We will have discussion further about this in Chapter 4. 30 The traversal of the tree is in pre order, taking every M node as a subgroup. The last node in each subgroup becomes the 2 n d leader as well as the 1st leader for the next subgroup (e.g. M8 is the 2 n d leader of Si and the 1st leader of S2). Also, the 1st of the first subgroup automatically becomes the 2 n d leader of the last subgroup (e.g. M19 is the 2 n d leader of S3). For example, in Figure 3.5, with M = 4, all nodes are divided into 3 subgroups: Subgroup 1: < M]9, Mi, M3, M8>. M / 9 , and M8 are subgroup leaders. Subgroup 2: < Mg, Mn, M9, M]7>. M8, and M / 7 are subgroup leaders. Subgroup 3: < M]7, M!4, Mw, M]2, MI9>. M]7, and M]9 are subgroup leaders. As mentioned before, all subgroups form a ring structure with subgroup leaders as the joint nodes, as shown in Figure 3.2. 31 3.2.3 Initialize and Distribute the Subgroup Key (Step 4) 1) Ms=> G: {<SC>} for all subgroups. After dividing G into subgroups, Ms multicasts how it made the division (the member list of each subgroup) to G. For example, in Figure 3.6, <5/> = <MI9, M3, M8> 2) VMjE G, if Mj& Sc, Mj stores <5C>. By receiving the message from 1), M, stores the subgroup information <SC>, if M,€ Sc. 3) Mi => Sc- {(KC)EP}, for V Mp € Sc, pA If Mi is the 1s t leader node of Sc, Mi will initialize Kc, encrypt Kc with the public key of subgroup members, combine all the encrypted Kc in one message and multicast it to Sc (Here we combine all encrypted keys into one message and use one multicast instead of multiple unicasts to save time and communication cost). 4) Mp £ Sc, p*j, (((Kc)Ep)Dp) = Kc If Mp is a member of Sc, Mp decrypts (KC)EP with Dp and get Kc. 32 Figure 3.7 Initialize and distribute subgroup and group key For example, in Figure 3.7, M!9 initializes K} for Si, encrypts Ki with the public key of Mi, M2 and M8 and multicasts <(Ki)Eh (K,)E3, (Ki)E8> to St. When Mj receives this message, Mj decrypt (Ki)Ej with D/ and get the subgroup key K] = ((Ki)Ei) Dj. 3.2.4 Initialize and Distribute the Group Key (Step 5) The last step of start-up phase is to initialize the group key (Kgmup) and distribute encrypted Kgroup along the subgroup ring. 1) Ms initializes K. group 33 2) S h M s £ Si. M s S i : ( K g r o u p ) K i M s encrypts K g r o u p with 5, 's subgroup, key and multicast to 5,. 3) When a leader node Mj (M,-e Si) receives ( K g r o u p ) K i , it decrypts ( K g r o u p ) K i with K t and gets K g r o u p , where K g r o u p = ((KgroUp)Ki)Ki. (This applies to all subgroup leaders.) 4) Because Mj is the joint leader of another subgroup, 3St, MjG S^ and M y e 5„ M;=> 5*: (Kgroup)Kk Joint leader works as a bridge of two subgroups and propagates K g r o u p along the subgroup ring structure to the whole group G, as shown in Figure3.8. Figure 3.8 Distribute K g r o u p along the subgroup ring 34 Num of Unicast N Size of Unicast Msg Nx(l + [E] + Nx[ID]) Num of Multicast 3xT + 1 Size of Multicast Msg 1 + T x ([K] + Mx[K] + 1 + Mx[E] + Mx[ID]) Round 7+4 [E] - key length of public key, [£] = 1024 Bits = 128 Bytes [K] - key length of symmetric key (Ksubgroup and Kgroup), [K] = 128 Bits = 16 Bytes [ID] - length of MAC address, [ID] = 12 Bytes T is the total number of subgroups, T~\ N/M ] Table 3.1 Communication cost of start-up Public Encryption Symmetric Encryption Symmetric Decryption (M-l) x T T N Table 3.2 Computation cost of start-up n - (* In our system, public key encryptions and public key decryptions always come in pairs. This means the number of public key encryptions is always equal to the number of public key decryptions in our system. So here, and in the rest of the thesis, we will not analysis the cost of public decryption.) The construction of subgroups requires a lot of communication/computation resources, as shown in Table 3.1 and 3.2. Fortunately, we only need to construct and initialize subgroups at the start-up of the system. We dynamically balance the size of subgroups (e.g. in Chapter 3.4.2) and rarely do re-initialization. 35 3.3 Key update at Join Event There are 11 steps of the key update process at Join Event: \)Mr^>G: {JOIN_REQUEST} Requesting member - Mr multicasts a JOIN_REQUEST message to G. 2) For VMj eFG & Mj gG: Mj forwards the JOINJREQUEST (FG is the forwarding group for multicast routing. G is the multicast group. See Appendix for definition.) For VMj eG, MJ is subgroup leader : Mj—> M,: {JOIN_REPLY}, Mj does not forward JOIN_REQUEST By receiving the JOIN_REQUEST, members of FG will forward JOIN_REQUEST to neighbours. Subgroup leaders will reply JOESLREPLY message to the requesting node, but they do not forward JOIN_REQUEST. 3) Mr-Mt: {JOIN_CONFrRM, Er) Assuming the first JOIN_REPLY is fromM,(M, is a subgroup leader), then Mr unicasts a JOIN_CONFIRM to Mti together with M r 's public key Er 4) After M, receives the JOIN_COMFIRM, M, add Mr into subgroup Sc (Assume M, € Sc) 5) M, updates Kc and Kgroup. 36 6) M t = > S c : { { K c ) K c _ o l d , < M r , E r >} M, encrypts updated K c with K C _ M , combines ( K c ) K c o i d with < M r E r > in one message, and multicasts it to S c . 7) M j € S c , by receiving { ( K c ) K c o i d , <M, £,>}, adds < M r , E r > to 5C and updates K c by decrypting ( K c ) K c o l d with the K c _ o l d . 8) M t - > M r : { ( K c ) E r , ( K g r o u p ) K c , < S C > } M , encrypts K c with E r and K g r o u p with K c . M , then combines ( K c ) E r , ( K g r o u p ) K c , and < 5C> in one message and unicasts it to Mr. 9) M r , receives { ( K c ) E r , ( K g r o u p ) E r , < S C > } , then stores < S C > and decrypts < ( K c ) E r , ( K g r o u p ) K c > to get K c and K g r o u p . 10) Af, => G : ( K g r o u p ) K g r o u p o i d M , encrypts K g r o u p with K g r o u p _ 0 i d and multicasts this to the whole group. 11) Mks G , k*r, by receiving ( K g r o u p ) K g r o u p o i d , updates K g r o u p by decrypting (Kgroup)Kgroup_old with K g r o u p _ 0 i d . 37 © Figure 3.9 K e y update at Join Event Event Public Encryption Symmetric Encryption Symmetric Decryption Join 1 3 M +N + 1 Table 3.3 Computation cost at Join Event N u m of Unicast 2 Size of Unicast M s g [E] + 2x[K]+Mx([E] + [ID]) N u m of Multicast 2 Size of Multicast M s g 2x[K] + [E] + HD] Round 4 Table 3.4 Communication cost at Join Event 38 3.4 Key Update at Leave Event There are two types of Leave Event - the leaving node is a non-leader node, or the leaving node is a leader node. For non-leader node Leave Event, the group key and subgroup key are updated and distributed by one of the subgroup leaders. For leader node leave, a new leader will be selected to replace the leaving leader, or if both subgroups are too small, they merge into a new subgroup. 3.4.1 Non-Leader Node Leave Assume: 1) Mi is the leaving node, and M t € Sc 2) M a and M b are leaders of Sc, and a < b The key update at non-leader node leave event has 5 steps: \ ) M i - > M a . {LEAVE_REQUEST} Mi unicasts a LEAVE_REQUEST to the subgroup leader of Sc with a smaller ID (here it is M a ) , then Mi leaves the group. 2) M a removes Mt from Sc. 3) VMj e Sc, Mj * M a , M a encrypts K c with Ej, ( K c ) E j Ma^Sc: { { ( K c ) E j } , M i ) for VMjSSc,j^a 39 Ma updates Kc. For each member A/,- in Sc, Ma encrypts Kc with the public key £}, combines all the encrypted Kc together with M/s ID into one message {{Kc)Ej, Mi}, and multicasts to Sc. 4) By receiving {{(Kc)Ej), Mi}, Mj(Mj s Sc,j*a) decrypts (Kc)Ej with D ; and get updated Kc = ((Kc)Ej)Dj. Mj also removes Af ; from its subgroup member list. 5) Ma updates Kgroup and multicasts Kgroup along the subgroup ring structure; this is same as the KsroUn distribution we discussed in 3.3.2. Figure 3.10 Non-leader node leave 40 Event Public Encryption Symmetric Encryption Symmetric Decryption Non-Leader Leave M T N Table 3.5 Computation cost at Leave Event (non-leader node) Num of Unicast 1 Size of Unicast Msg [ID] Num of Multicast T+ 1 Size of Multicast Msg Tx[K] + Mx[ID] + Mx[K] Round T+2 Table 3.6 Communication cost at Leave Event (non-leader Node) 3.4.2 Leader Node Leave - Merge When the leaving node is a subgroup leader, we will either select a node as the new leader, or we will merge the two subgroups into a new subgroup if both subgroups have too few members. Assume the leaving subgroup leader is Mi, and we know Mx is the joint node of two subgroups - 3Sa and 3Sb, Mi € Sa and Mi € Sb, and a < b. If [Sa] <ax SUBGROUP_SIZE and [Sb] < 1/3 x SUBGROUP_SIZE, or [Sa] = 2 or [Sb] = 2, (0< a < 1, a can be configurable. In our implementation, a = 1/3). We merge Sa and Sb to a new subgroup - Sa. Otherwise, we select a new joint leader (see the discussion in 3.4.3). The subgroup merging and key update has 4 steps: 41 1) Mi => Sa, Sb: {LEADERLEAVE, <a, [Sa]>, <b, [Sb]>} The leaving node Mt multicast a LEADER_LEAVE request to both Sa and Sb with ID and size of both subgroups. 2) Mjjri, if Mj € Sa, Mj, remove Mt from member list of Sa. if Mj e Sb, Mj, remove Mi from member list of Sb. By receiving the Leader_Leave request, members of Sa and Sb remove Mi from their subgroup node list. 3) 3MP, Mp € Sa, Mp is the leader of Sa and Mp *Mt. 3Mq, Ma s Sb, Mq is the leader of Sb and Mq #M ;. Mp=>Sb: {<Sa>,p,a} Ma^>Sa: {<Sb>,q,b} Since each subgroup has two subgroup leaders, we can find the remaining leader, Mp (Mp *Mj) for subgroup Sa, and Ma for Sb. Mp multicasts <5fl>, ID of Mp and subgroup ID of Sa to subgroup Sb. When members of Sb receives this message, they add the member list of Sa to their subgroup, replaces Mt with Mp as the new leader and sets a as the new ID a for the subgroup. Ma also sends {<Sb>, q, b} to Sa. When members of Sa receive {<Sb>, q, b), they set Ma as the new leader, and adds <Sb> to their member list. 42 After this message exchange, all members from former Sa and Sb have {<Sa> U <Sp>} as their member list, and have <MP, Mq> as the pair of subgroup leaders and the same subgroup ID - a. So they are merged to a new subgroup - Sa. 4) The leader node with smaller ID updates Ka and Kgroup. If Mp and Mq is the leader nodes of Sa and p < q, then Mp updates Ka and Kgroup and securely distributes <Ka, Kgroup>. This step is same as step 3, 4 and 5 in Non-Leader node leave 3.4.1. 43 Leaving Node (1) M , ^ > S , . S 2 . LEAVE_REQUEST (2) M9*>S3:{<S?,M„SJ Figure 3.11 Leader node leave and subgroup merge Event Public Encryption Symmetric Encryption Symmetric Decryption Non-Leader Leave M T N Table 3.7 Computation cost at Leave Event (merge) 44 Num of Unicast 0 Size of Unicast Msg 0 Num of Multicast T+4 Size of Multicast Msg [ID] + IxaxM x([E]+[ID]) + 2xax Mx[K]+ Tx[K] Round T+3 Table 3.8 Communication cost at Leave Event (merge) 3.4.3 Leader Node Leave - Select a new subgroup leader If the leaving node is a leader and the two subgroups do not satisfy the merging condition as discussed in 3.4.2, we select a new leader from the subgroup with more members. This node will be the new joint leader of both subgroups and will update the subgroup and group keys. There are 10 steps to select a new leader and update keys: 1) 2) is same as Step 1) and 2) in 3.4.2. 3) Assume [Sa] > [Sb], then the new leader will be selected from Sa (if [Sb] > [Sa], then the new leader will be selected from Sb) In step 1, the leaving node will send a leaving request together with the ID and size of both subgroups Sa and Sb. Assume Mp is the leader of Sa and Ma is the leader of Sb. By receiving the leave request from step 1, if [Sa] > [Sb], then Mp will select the new leader, otherwise, if [Sa] < [Sb], then Ma will select the new leader. BMh, Mh e Sa, Mh*Mi and Mh *MP (Here we assume Mp is the leader of Sa and Mq is the leader of Sb), Mp randomly picks a node Mh from Sa as the new leader. 45 4) Mp => Sa, Sb : <h, Eh, a> Mp multicast to Sa and Sb the selected new leader Mh and its public key Eh- 5) VMj e Sa, by receiving the message from Step 4, Mj set Mh as the new leader. 6) VMj e Sb, by receiving the message from Step 4,Mj adds < Mh, Eh> to Sb's subgroup member list and sets Mh as the new leader. 7) Mq -> Mh: < Sb> {Mq <= Sb and Mq is leader node.) Mq - the leader node of Sb unicasts <Sb> to Mh,. 8) By receiving messages from step 7, Mh creates and adds <Sb> as Sb's member list. 9) Mh updates Ka and multicasts it to Sa. This step is the same as step 3 and 4 in Non- Leader Node Leave. (3.4.1) 10) Mh updates Kb and multicasts it to subgroup Sb. This step is the same as steps 3 and 4 in Non-Leader Node Leave. (3.4.1) 11) Mh updates Kgroup and multicasts encrypted Kgroup to G along the subgroup ring. This step is the same as step 5 in Non-Leader Node Leave (3.4.1). 46 © I (1) «, 9=>S rS 2: {Mfp Eip 1} (Step 4) | (2)M,=>MM:{<Sj>><Stop7) ! <3) M,">S,: {(Kg) £J (Step 9) j <4)A^9=>S3:((>g£)(Step10) Figure 3.12 Leaver node leave and a new leader is selected Event Public Encryption Symmetric Encryption Symmetric Decryption Leader Leave (Replicate) 2xM T N Table 3.9 Computation cost at Leave Event (replicate a new leader) 47 Num of Unicast 1 Size of Unicast Msg Mx([E] + [ID]) Num of Multicast T+4 Size of Multicast Msg 2x[ID] + [E] + 2x Mx[K]+ Tx[K] Round T+4 Table 3.10 Communication cost at Leave Event (replicate a new leader) 48 Chapter 4 P2P-HGKM Performance and Evaluation In this chapter, we compare the performance of P2P-HGKM with some existing key establishment protocols, including GDH 2.0, AT-GDH and Tree-Based key management protocol. Theoretical analysis shows that our P2P-HGKM outperforms GDH 2.0 and AT-GDH in computation and communication cost. Performance of P2P- HGKM is also close to optimum key management protocols like Tree-Based key management protocol, and our P2P-HGKM shows more advantage in ad-hoc networks. We also study the relationship between the two parameters (Af and N) and the computation/communication cost. We did extensive experiments and the results justify our prediction. 49 4.1 P2P-HGKM Security Analysis Our P2P-HGKM protocol is secure at passive attack such as eavesdropping. This is because the algorithms (AES and RSA) and the key length (128 bits symmetric key and 1024 bits public key) we choose are considerably strong encryption algorithms. As far as the secret keys (the symmetric key for AES and the private key for RSA) are kept confidential, it's very hard for eavesdroppers to deduce any key from the encrypted packets. Active attack (falsification of data) from non-member nodes can affect the performance of P2P-HGKM, but cannot break the security of our protocol (At this step, we assume the active attacks are from non-member nodes, and all member nodes can be trusted. We will discuss the case of malicious members nodes right after this). As shown in Figure 1.2, intermediate nodes are required to relay packets from source to destination in ad-hoc networks. If an intermediate node is malicious, it can modify the packets before it rebroadcast. The solution to man-in-the-middle attack is to have all messages signed by source nodes. In our protocol, Join and Leave Request message (see Chapter 3.3 and 3.4) are sent and signed by the requesters. All other messages are sent and signed by subgroup leaders. In our system, if all member nodes maintain a list of valid subgroup leaders, then any falsified message from non-member nodes or the leaving node (at Leave Event) will be detected and reported. Attack from member nodes is very hard to detect and prevent. If the system detects some member node becomes malicious, it can immediately expel the malicious member from the group and update all the keys hold by the leaving node. 50 4.2 P2P-HGKM Experiment Overview We have designed and constructed the P2P-HGKM protocol as well as the test bed for experiment using Java. ODMRP is also implemented as the supporting routing protocol. At startup of the system, 50 nodes are created and are assumed to be randomly scattered in a 1000m x 1000m area. Radio range of wireless signal is 250 m. Then we randomly select N (N < 50) nodes as the group members of (G). A start node - Ms is elected by running bully algorithm among all member nodes. This Ms is responsible for building up the subgroup structure and distributing group and subgroup keys, as discussed in Chapter 3.2. In the following discussion, we use q to represent the percentage of Leave Events out of all membership change events. For example, in our simulation, every test run has a total of 20 membership change events - 10 Join Events and 10 Leave Events, so the percentage of Leave Event q = 0.5. There are two parameters - M and N that can affect the computation and communication cost of our protocol. We desire to study the link between these parameters and the protocol performance. We do theoretical analysis and extensive experiments to prove our predictions (see section in 4.3.2 and 4.4.2). M is the average size of subgroup. In our experiments, we increase M from 6 to 16 at the step of 2 to see how M affects the performance. We record the number of public encryption/decryption and symmetric encryption/decryption as the computation cost. We also record the number and message size of unicast/multicast as the communication cost of key update. We 51 repeat each case 50 times and use the average of the results to plot graphs (see 4.3 and 4.4 for the graphs.) N is the number of group member. We assume G is always divided into roughly N1/2 subgroups and each subgroup has roughly Nm members. In our experiments, N increases from 16 to 40 by 4 at each step. Again, we record the computation and communications cost, repeat and plot graphs using the average of the results. 4.3 Computational Cost An approximate measure of the computation costs is the number of key encryptions and decryptions required by a join/leave request. We summarize the computation cost from Chapter 3 and tabulate it in Table 4.1. Public Key Encryption Symmetric Key Encryption Symmetric Key Decryption Join 1 3 M+N+l Non-Leader Leave M T N Leader Leave (Merge) M T N Leader Leave (Replicate) 2xM T N Table 4.1 A summary of computation cost 4.3.1 Comparing with other protocols 52 P2P-HGKM GDH 2.0 AT-GDH Tree-Based Join 1 public enc + 1 public dec + 3 symm enc + M +N+1 symm dec 0(N2) exp. 0(NlogkN) exp. 2 x (n-l) symm enc (h-l)+ Nxd/(d-l) symm dec Overall: 0{N) symmetric decryption OCA'2) exp. 0(NlogkN) exp. O(A0 symmetric decryption Leave M public enc + M public dec + r NIM1 symm enc + N symm dec 0(N2) exp. 0(NlogkN) exp. (d-l) x h symm enc + Nxdl (d-1) symm dec Overall: 0(N) symmetric decryption + 0(M) public encryption 0(N 2) exp. 0(NlogkN) exp. 0(d x h) symmetric encryption 0(N) symmetric decryption enc - encryption ; dec - decryption ; exp - exponentiation h - height of the tree in Tree-Based protocol d - degree of the tree in Tree-Based protocol Table 4.2 Computation cost comparison. Comparing computation cost with other key establishment protocols We summarize the computation cost of P2P-HGKM, GDH 2.0, AT-GDH and the Tree-Based key management protocol in Table 4.2. From Table 4.2 we can see Diffie- Hellman key agreement protocols, e.g. GDH2.0 or AT-GDH, requires 0(NxlogkN) or 0(N2) exponential computation at each Join or Leave request. Our P2P-HGKM protocol outperforms GDH 2.0 and At-GDH with only 2 public encryption/decryption and O(A0 53 symmetric decryptions at Join Event; and 0{M) public encryption/decryption and O(A0 symmetric decryptions at Leave Event. This is because our protocol limits public key encryption/decryption within one subgroup. Key management protocols, e.g. Tree-Based Key management protocol, have a better computation cost performance than our P2P-HGKM protocol, as shown in Table 4.2. This is because Tree-Based protocol assumes that a reliable central key server is presented in the system. Our subgroup ring structure is not the optimal structure, but its performance is close to Tree-Based key management protocol. More importantly, our P2P-HGKM protocol works in a P2P fashion, thus avoiding the role of a single key server in our system. So our protocol is more applicable and reliable for ad-hoc networks than Tree-Based key management protocol. 4.3.2 Performance Among all Leave Events, non-leader node leaving happens at the possibility of (M-l) / M and leader node leaving happens as the possibility of 1/ M. In 3.4.2, we merge two small subgroups into one subgroup to balance subgroups and improve overall performance. The merging only happens when the leaving node is a leader node and both subgroups have too few members. This is a rare case from the experience of experiments, especially when Join Event happens as often as Leave Event. Also, the computation and communication cost at the case of "Subgroup Merge" is very close to the case of "Select a New Leader". So, for simplicity, we combine the case of "Subgroup Merge" with the case of "Select a New Leader" when we count the computation and communication cost. 54 In this section and in 4.3.2, we will first predict how M and N can affect the performance of P2P-HGKM. Then we use experiment data to plot graphs and testify our prediction. 1) Number of Public Encryption: 1 X (l-q) + M X ((M-l)/M) X q + 2 X M X (1/M) X q 1 +qxM \+qxNlr- Number of Public Encryption M t T qxM N T TqxNia Q I I L 1 ! I 6 8 10 12 14 16 Members per Subgroup (if) a)M 55 16 20 24 28 32 36 40 Members of Group (A1) b)N Figure 4.1 Experiment result: public key encryption/decryption 2) Number of Symmetric Encryption: 2x(l-q) + (N/M)xq 3 X (l-q) + (NX q) / M 3x(l-q) + q xNm Number of Symmetric Encryption M T I (Nxq)/M Nt Tq X Nm 5 6 120 B 10 0 *» s so H •Jj 60 u h g i •SO 1 in 20 0 8 10 12 14 Members per Subgroup (JO 18 100 •:•••. a eo s a ro I 60 & SO i 40 1 3C 20 to 0 it a)M 24 28 32 feobers of Group (A) 36 Figure 4.2 experiment result: symmetric key encryption 3) Number of Symmetric Decryption: (M + N)x(l-q) + Nxq N+(l-q)+ (l-q)xM (\-q) + N+(\-q)xNm 57 Number of Symmetric Decryption M T t (\-q)xM Nt T N +(!-<?) xNm § ° 90 0 "Z s w , , .—, __=— I | S60 I 1 1 840 1 1 820 I ' I 1 6 8 10 12 14 16 Nerabers per Subgroup (M) b)N Figure 4.3 Experiment result: symmetric key decryption 58 4.4 Communication Cost Approximate measure of communication cost in our key managements includes: the number of unicast, the number of multicast, and total number of rounds required for a Join or Leave request. We summary and tabulate the result from Chapter 3 in Table 4.3. Join Non-Leader Leave Leader Node Leave (Merge) Leader Node Leave (Replicate) Num of Unicast 2 / 0 1 Size of Unicast Msg [E] + 2x[K] + Mx([E] + UD]) [ID] 0 Mx([E] + [ID]) Num of Multicast 2 T + 1 T+4 T+4 Size of Multicast Msg 2x[K] + [E] + [ID] Tx[K] + Mx[ID] + Mx[K] [ID] + 2xaxM x([E]+[ID]) + 2xax Mx[K]+ Tx[K] 2x[ID] + [E] + 2x Mx[K]+ Tx[K] Round 4 T+2 T+3 T + 4 Table 4.3 Summary of communication cost 4.4.1 Comparing with other protocols 59 P2P-HGKM GDH 2.0 AT-GDH Tree-Based Join 2 Unicast 2 Multicast (JV-1) Unicast + 1 Multicast 2x N Unicast h multicast + 1 unicast 4 Round N Round 2k x (logkN) Round h Round Leave 2 Unicast 4+ T Multicast (N-l) Unicast 1 Multicast 2N Unicast O I ) x O I ) multicast 4 + T Round N Round 2kx(logkN) Round h Round Table 4.4 Communication cost comparison Comparing communication cost with other key establishment protocols As we can see from Table 4.4, our P2P-HGKM protocol outperforms GDH 2.0 and AT-GDH in the number of round and the number of messages. P2P-HGKM is not as good as Tree-Based key management protocol, but the performance is close and P2P- HGKM is more applicable and reliable in ad-hoc networks, as discussed before. 4.4.2 Performance Like in 4.2.2, we will study the effect of parameter Af, q and N on communication cost. ' -' 1) Number of Unicast: 60 2x(l-q) + qX(M-\)IM + (UM) xq 2-q Number of Unicast M T Unchanged <-> N T Unchanged <-> f 6 8 10 12 H 16 Members per Subgroup (tf) a) Af 35 30 20 15 to 16 20 24 28 32 36 40 Members of Group (A) b)W Figure 4.4 Experiment result: number of unicast 61 2) Size of Unicast ([E]+2[K]+Mx[E]+Mx[ID])x(\-q) + ((M-1)/M)x([ID]) Xq+ Mx([E]+[lD])x(\IM) X ([E]+2[K]x(l-q) + 2x[ID]xq) + ([E]+[lD])x(\-q)xM- [ID]xq IM ([E]+2[K]x(\-q) + 2x[ID]xq) + ([E]+[ID])x(l-q)xN1/2 - [ID]xq IN' jl/2 Message Size of Multicast M t T([E]+[ID])x(l-q)xM-[ID]xq/M N T t ([E]+[ID])x(\-q)xNm - [ID]xq 1 Nm 300  n i MIM ..in 2500 S 200 in « 1500 3 100  f -500 0 8 10 12 14 Members of Subgroup OO 1G a)M 62 I40OQ 120OO 10000 — - — • \ N « - " £ 8 0 ( ) 0 ; ; _ , tt | g0oo o  ; - -I —I J - J 1 16 20 24 28 32 36 40 Members of Group (P0 Figure 4.5 Experiment result: message size of unicast 3) Number of Multicast 2x(l-<?)+ (N/M)x((M-l)/M)xq + (4+N/M)x(l/M)xq (2-q) + qX(N+3)/M (2-q) + qX(Nm + ?>INm) Number of Multicast M T iqX{N+3)IM N T T qx{ Nm + 3I Nm) when N>3 63 3 8 10 12 14 16 Members per Subgroup (Jf) 120 MM- jmmmmmm 100 — — 1 — | 8 0 . ^Jl_ <- 6 0 - I s . 1 0 J X 16 20 24 28 32 36 Member* of Group (AT) b)N Figure 4.6 Experiment result: number of multicast 4) Size of Multicast: (2[K]+[E]+[ID])x(l-q) + (N/M x[K]+ Mx[ID] + Mx[K])x((M -1)/ M)xq + (2x[ID)+ [E] + 2xMx[K] + N/M x [K]) x (1/M) x q = (2-q)x[K]+[E]x(l-q)+[ID]x(l-2xq) + ([ID]+[K])XqxM + qx(Nx[K]+2x[ID]+[E])/M 64 (2-q)x[K]+[E]x(l-q)+[ID]x(l-2xq) + ([lD}+[K])xqxN1" + qx(2x[ID]+[E]) IN' Message Size of Multicast M T f ([ID]+[K])xqxM + qx(Nx[K]+2x[ID]+[E])/M Nt T ([lD]+[K\)xqxNm + qx(2x[ID]+[E]) 1 Nm w 50*0 1 400 2 3000 2C0 100 0 8 10 12 14 Msfcers pel" Subgroup 0 a)M 6000 5000 | 4000 £ 3000 5 2000 1000 0 16 20 24 28 32 36 40 Members of Group (A') b)/V Figure 4.7 Experiment result: message size of multicast 65 5) Round: 4x(l-q) + (N/M + 2)x((M-\)IM)Xq + (N/M+4)x(l/M)Xq (4 - 2xq) + qX(N+2) IM (4 - 2xq) + qx(Nm + 2 / Nm) Round M f iqX(N+2)IM Nt tqx{ Nm + 2I Nm) when N > 2 66 Chapter 5 Conclusion and Future Work 5.1 Conclusion To support dynamic secure group communication in ad-hoc networks, a group key KgroUp shared by all members of the group needs to be constantly updated whenever there is a membership change of the group, e.g. when a current member leaves or a new member joins the group. Many group key establishment protocols have been proposed and a few were proposed for ad-hoc networks, but they all have major shortcomings when applied to ad-hoc network environments. Wireless hosts in ad-hoc networks are mobile, and are usually lightweight, battery-powered devices. And using multicast in wireless network has advantage over multiple unicast - it takes less time and less resource. In this thesis, we proposed an efficient P2P hierarchical group key management protocol for ad-hoc networks. We introduced the concept of subgroups, each maintaining 67 its subgroup key and links with other subgroups in a simple ring structure. By dividing group G into subgroups, we limit unicast and public key encryption within one subgroup, thus greatly reducing the cost of group key update at node Leave Events. The distinguishing feature of our scheme lies in the fact that our scheme works in P2P, rather than a single key server. We implement our protocol and do extensive theoretical analysis and experiments. Both theoretical analysis and experiment show that our protocol provides efficient and reliable group key management services, and outperforms many existing group key establishment protocol in ad-hoc network. 5.2 Future Work As discussed in Chapter 3, subgroups are linked in a ring structure, and every joint leader connects two subgroups. Using a more complex structure of subgroups could be a viable future work. As shown in Figure 5.1, all the subgroups can be linked in a more complex structure, e.g. a cubic, and a subgroup leader can be a joint node of more than two subgroups. Updated Kgroup can be sent in more direction at the same time. Such complex structure would offer advantages in efficiency and scalability, but of course, managing such structures would be more complex. 68 Update ;^ro^ih 3 yjretSSorts simuitangously o Leader Node of 3 Subgroups S 3 Figure 5.1 Complex structure of subgroups Our protocol can merge two subgroups into a new subgroup when there are too few nodes in both subgroups, as discussed in 3.4.2. This is a way to dynamically balance subgroups without re-initialization. We know a balanced subgroup ring has a better performance at group key updates than an unbalanced subgroup ring. As future work, we could develop a way to automatically find those "fat" subgroups (subgroups with too many members) and split them into smaller subgroups. Our protocol handles key update at single node join or leave. It can be easily extended to multiple nodes cases by running the protocol multiple times. A more complex but efficient scheme for group key update at simultaneous multiple-node join/leave events can be explored in future research. 69 Appendix Notations used in P2P-HGKM protocol: Kgroup '• the group key shared by all members of the multicast group K g r o u p _ o i d • the group key before updating Ki: the subgroup key for subgroup i, shared by all members of the subgroup Koid : the subgroup key of 5, before updating Mi: node with ID i Et: public key of node i (Mi) Dt: provate key of node i (Ml) Si: Subgroup S,, i is ID of the subgroup. <5,> : node list of subgroup 5, Mi—>Mjr :{Rekey Msg} : M, unicast {Rekey Msg} to M, Mi => Sc:{Rekey Msg} : M, multicast {Rekey Msg} to subgroup S c M i = > G : {Rekey Msg} : M, multicast {Rekey Msg} to multicast group G 70 FG : Forwarding Group, only members of the forwarding group will forward multicast packages. N: The total number of node in the multicast group G M : The average number of node in each subgroup T: T is the total number of subgroups, T ~ [ NIM1 71 Bibliography [1] Chung Kei Wong, Mohamed Gouda, and Simon S. Lam. "secure group communication using key graphs" In Proceedings of ACM SIGCOMM '98, September 2- 4, 1998. [2] M. Steiner, G. Tsudik and M. Waidner, "Diffie-Hellman Key Distribution Extended to Groups " ACM CCS'96, March 1996 [3] Suvo Mittra: "Iolus: A Framework for Scalable Secure Multicasting". SIGCOMM 1997: 277-288 [4] Xiang-Yang Li, Yu Wang, Ophir Frieder, "Efficient Hybrid Key Agreement Protocol for Wireless Ad Hoc Networks", IEEE 11th International Conference on Computer Communications and Networks (ICCCN2002), Oct. 2002 [5] Maarit Hietalahti. "Efficient key agreement for ad-hoc networks". Master's thesis, Helsinki University of Technology, Department of Computer Science and Engineering, May 2001. 72 [6] Chun Zhang, Brian DeCleene, James F. Kurose, Donald F. Towsley: "Comparison of inter-area rekeying algorithms for secure wireless group communications". Perform. Eval. 49(1/4): 1-20 (2002) [7] Charles E. Perkins and Elizabeth M. Royer. "Ad hoc On-Demand Distance Vector Routing." Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100. [8] Elizabeth M. Royer and Charles E. Perkins. "Multicast Operation of the Ad hoc On- Demand Distance Vector Routing Protocol." Proceedings ofMobiCom '99, Seattle, WA, August 1999, pp. 207-218. [9] J.J. Garcia-Luna-Aceves and E.L. Madruga, "The Core Assisted Mesh Protocol", accepted for publication in IEEE Journal on Selected Areas in Communications, Special Issue on Ad-Hoc Networks, 1999. [10] M. Gerla, T.J. Kwon and G. Pei, "On Demand Routing in Large Ad Hoc Wireless Networks with Passive Clustering", Proceedings of IEEE WCNC 2000, Chicago, JL, Sep. 2000. [11] C. Cordeiro, H. Gossain, and Dharma P. Agrawal, "Multicast Over Wireless Mobile Ad Hoc Networks: Present and Future Directions," IEEE Network, special issue on Multicasting: An Enabling Technology, Vol. 17, No. 1, January/February 2003, pp. 52-59. [12] Sung-Ju Lee, William Su, Mario Gerla, "Exploiting the unicast functionality of the on-demand multicast routing protocol", WCNC 2000 - IEEE Wireless Communications and Networking Conference, no. 1, September 2000 pp. 1317-1322 73 [13] Cicso System: http://www.cisco.com/eri/US/about/ac 123/ac 147/ac 174/ac 177/about_cisco_ipj_archive_a rticle09186a00800c83e4.html [14] Whitfield Diffie and Martin E. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, vol. IT-22, no.6, pp.644-654, 1976 [15] R.L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21(2), pp. 120-126, 1978 [16] Klaus Becker and Uta Wille, "Communication complexity of group key distribution," in 5th ACM conference on Computer and Communication Security, Nov. 1998. [17] Yongdae Kim, Adrian Perrig, and Gene Tsudik. "Simple and fault-tolerant key agreement for dynamic collaborative groups." In ACM Conference on Computer and Communications Security, pp. 235-244, 2000 [18] Garcia-Molina, "Elections in Distributed computer Systems", IEEE Transactionson Computers, 1982, Vol C-31. No.l, pp 48-59 74

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 5 2
Japan 4 0
United States 4 0
Russia 2 0
City Views Downloads
Tokyo 4 0
Beijing 4 2
Mountain View 2 0
Unknown 2 2
Ashburn 1 0
Redmond 1 0
Shenzhen 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}

Share

Share to:

Comment

Related Items