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 G R A D U A T E 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: Department of The University of British Columbia Vancouver, B C ^,00 4 Canada grad.ubc.ca/forms/?formlD=THS p a g e 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 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 iii 8 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) 3.2.3 Initialize and Distribute the Subgroup Key (Step 4) 32 3.2.4 Initialize and Distribute the Group Key (Step 5) 33 30 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 Chapter 4 45 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 iv 52 4.3.2 4.4 Chapter 5 Performance 54 Communication Cost 59 4.4.1 Comparing with other protocols 4.4.2 Performance 59 60 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 aringstructure 5 Figure 1.5 K 6 group propagates along the subgroup ring 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 vi 24 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 K 34 group along the subgroup ring 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 viii 52 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 (K ) shared by all members of group the group is needed. Packets will be encrypted with a group key K group decrypted with the same K gwup by receivers. The group key K group by the sender and 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 K group communication encrypted with the old K group member node leaves, K group so all past is kept secret to the new member. If a 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/, S and S , and M, is the joint leader of S] and S . We can assume 2 3 9 3 that all subgroups are linked in a ring structure, as shown in Figure 1.4. 4 © © Sw s, i^i* §f* ] S 3 : M s , M e . M w M " 0 0/ ^~^) 7 /i f . ' — < C \ \ W \ o V Member Node Leader Node Non-Member Node © Figure 1.3 Members of multicast group are divided into subgroups. 5j V [M i M M M 14 j M tr-j S 2 Figure 1.4 Subgroups link in a ring structure Without the concept of subgroup, an update K group 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 K group can be encrypted with subgroup keys and multicast to the corresponding subgroups. For example, in Figure 1.5, is updated by Mjg, encrypted with subgroup key K p gwU multicast (K to 5/. When M )Ki group M 8 decrypts (K 8 and gets K )K, group encrypt K group . group of subgroup Sj and the other leader node of Si, receives this message, Since M is also the leader of S , 8 with K and multicast (K 2 (Kj) )K group 2 2 to S . In this way, 2 K group M 8 will then can be propagated along the subgroup ring and finally received by all members, as shown in Figure 1.5. Figure 1.5 K group 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 P2PHGKM 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 P2PHGKM 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. 5*Join Query 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 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 E from B or from a trusted third party. Then A will encrypt P with E and b b send (P)E to B. By receiving the encrypted message, B decrypts (P)E with its private b b key D , and extracts the correct content of the message P - ((P) E ) D . b b (P)£" ((P)E )D * b b =P P - Plain Text £ - P u b l i c Key of B D - Private Key of B 6 B Figure 2.2 Public key encryptions 11 b 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 - K . gwup K group 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 S , then Mi will have subgroup key Ki and K . Subgroup key is also 2 2 a 128 bit symmetric key, which is used to encrypt the updated key K . A subgroup key group is shared by all members of the subgroup. As a result when there is a membership change in Si, K is also updated. t 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 M £, is its public and D is its private h key. Public key encryption is used to encrypt updated K t gwup 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. All 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 n, g, g* mod n g* mod n B computes (g* mod n)" mod n = g » mod n A computes x n = g** mod n Figure 2.3 Diffie-Hellman key exchange 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 (g mod n) and sends this to B. Similarly, B sends (g'mod n) to A. By x receiving (g mod n) from B, A computes ((g mod nf mod n). Similarly, B computes x y ((g mod nf mod n) where (g mod n) is from A. After the key exchange, both A and B x x have (g^mod n) and this is the established shared key. (((g'mod nfmod n) = ((g mod nf x mod n) = (g^mod n) ). The security of Diffie-Hellman key exchange lays in the fact that, deducing x from (g mod n) is hard. So even if an eavesdropper has (g mod n) and (g mod n) and g x x y 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-inthe-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* 2. M, sends M : o^(Ff i+1 k=1 9 r )axid of((Ftk=1 r )/rj), V 1 <j < n k k 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 5 = y , r i = o^(ITj^rj). A n 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(n ) 2 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 K group 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 encrypt the updated • K (K _i) group 0 d to . group 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 stores k , k and k . 9 9 c wol 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 and securely distributes them. For example, in Figure 2.6, if M K c and K r 0 0 l in the key tree should be updated. Updated K and multicast to M and M 7 Kroot_oid 8 ( ( K C ) K C M ^ > { M 7 and multicast to the whole group { { K , r o o t ) K r o o t r o o ( ( K r o o t in the key tree " K C ) K K _oid c will be encrypted with t =>G). Updated K 9 9 o will be encrypted with c oW grouped together, encrypted with k and unicast to M o is the new member, then 9 Updated K M g } ) . r 9 r —> M o o 9 t and Xcwill be ) . Key update at node leaving is more complicated. All the keys possessed by the leaving node should be updated in order to secure future communication. For example, in Figure 2.6, if M is the leaving node, then 9 K 17 c and K r o o t should be updated because they are held by M . K and K are not affected by the leaving node and can be used to encrypt 9 A B the updated key(s). Updated K root is encrypted with K for M M , M ((K )K => {Mi, A and encrypted with K for M M M M2M3}), B 4 5 h 2 3 root A ((K )K =>{M , M , M}).Updated K 6 rool B 4 6 5 root and K are grouped together, encrypted with k for M and encrypted k with for M . c 7 7i 8 8 {(K , K )K - M ; (K , K )K -> M ) root C 7 7 rool C 8 8 Join Communication Cost Computation Cost h multicast + 1 unicast Leave (h-1) x (d-1) multicast Request node: (h-l) symm deer Request node: 0 Non-Req node: nxdl(d-Y) symm deer Non-Req node: nxd/(d-l) symm deer Key server: 2x(/z-l) symm encr 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 wellselected 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 Communication Cost Computation Cost • -. AT-GDH : JV-1 Unicast + 1 Multicast 2x N Unicast N Round . 2k x (log N) Round 0(N ) Exponentiation. 0(Nlog N) Exponentiation 2 k k 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 ATGDH 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(Nlog N). k 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 (K ) for secure group communication. group To update K at Join Event, we can use the K group group updated K , and multicast (K )K group Updating K group group to groupM before update to encrypt the all group membeTs((K )K group groupold => G). 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 so we cannot encrypt K group (K i ), groupo d with K id or any key known to the leaving node, as we groupo did at the key update of Join Event. A generic way to update K group 22 is to encrypt the updated K gmup (K )Ei group with the public key (£,) of each member (A/,) and unicast encrypted 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 K group 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 5 . All the 2 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-levelringstructure 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 K group 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; 's ID), so M will be responsible for updating 9 s 24 K group and K . ; M s first updates K encrypts Ki with Ei and E (the public key of M ; and M ) and unicasts h 19 19 (K])Ei and (K/)E to Mi and M ; individually. I9 9 After updating Ki, M updates K s propagates encrypted K group , encrypts K group group with K and 2 and along the subgroup ring, as shown in Figure 3.3. When M ]7 the other leader node of 52, receives this message, M ; decrypts (K )K.2 and gets K 7 gwup Since M is also a leader of S3, M will then encrypt K ]7 (K up)K3 gr0 17 to 5^. In this way, K group group . group with /if} and multicast 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 M A C 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) M , the member node with the largest ID, is picked as the start node by running the s bully election algorithm among all member nodes [18]. M multicasts a BUILD_SUBGROUP_REQUEST. s M => G: BUILD_SUBGROUP_REQUEST. s 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->M : <REPLY_BUILD_SUBGROUP, Ej > S 3) M divides all member nodes into subgroups based on REPLY_BUILD_SUBGROUP s messages received. Then M multicasts the node-list of each subgroup to the group. s Mi => G: <S >, for all valid c. 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 - M , initializes the group key (K ), encrypts K s K group group group and propagates 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) 3M , M e G. M" is selected as the start node. s s 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]. M will be responsible for multicasting s BUILD_SUBGROUP_REQUEST (step 1), dividing multicast group G into subgroups (step 3), and initializing the group key (in step 5). 28 2) M s G: BUILD_SUBGROUP_REQUEST M broadcasts BUILD_SUBGROUP_REQUEST. (Only messages along path 19->13s >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->M : {REPLY_BUILD_SUBGROUP, E ) S s 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 (Me G) will send 7 back a REPLY_BUILD_SUBGROUP message, together with its public key (£,) to M . s (as shown in Figure 3.5, M replies to M ) 9 19 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 M 9 to M is <M , M >). So REPLY message from M has two fields: public key of M -E , 19 9 16 9 9 9 and list of member nodes in the return path - <M , M >. We will see how M uses the 9 16 information in REPLY messages to divide G into subgroups in 3.2.2. 29 s 3.2.2 Dividing Group into Subgroups (Step 3) Leader Node (1)-(10): Order of preorder traversal S,:.<M", M v M , Mj>, Leader N o d e : M 3 S , : <M , M, , M . 8 e 3 iT Leader Node : f S : <M ,.M . ( s . M 8 M^M^ M , M . M, >, Leader Node -M . u 10 I2 s 17 M 19 Figure 3.6 Build subgroups With the REPLY messages in Step 1, M can divide G into subgroups. First, M s s inserts all member nodes in a tree structure rooted at M based on the return path in all s REPLY messages. As shown in Figure 3.6, M is the root of the tree. Since the REPLY i9 from M includes <M , M >, which means M comes after M in the return path, we will 9 9 16 9 t6 insert M as the child node of M , and M as child node of M into the tree structure. 9 !6 16 !9 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 leader as well as the 1 leader for the next nd st subgroup (e.g. M is the 2 leader of Si and the 1 leader of S ). Also, the 1 of the first nd st st 8 2 subgroup automatically becomes the 2 leader of the last subgroup (e.g. M is the 2 nd nd 19 leader of S3). For example, in Figure 3.5, with M = 4, all nodes are divided into 3 subgroups: Subgroup 1: < M , Mi, M , M >. M , and M are subgroup leaders. ]9 3 8 / 9 8 Subgroup 2: < Mg, Mn, M , M >. M , and M / are subgroup leaders. 9 ]7 8 7 Subgroup 3: < M , M , M , M , M >. M , and M are subgroup leaders. ]7 !4 w ]2 I9 ]7 ]9 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) M => G: {<S >} for all subgroups. s C After dividing G into subgroups, M multicasts how it made the division (the member list s of each subgroup) to G. For example, in Figure 3.6, <5/> = <M , M , M > I9 3 8 2) VMjE G, if Mj& S , Mj stores <5 >. C c By receiving the message from 1), M, stores the subgroup information <S >, if M,€ S . C c 3) Mi => S - {(K )E }, for V M € S , pA c C P p c If Mi is the 1 leader node of S , Mi will initialize K , encrypt K with the public key of st c c c subgroup members, combine all the encrypted K in one message and multicast it to S c c (Here we combine all encrypted keys into one message and use one multicast instead of multiple unicasts to save time and communication cost). 4) M £ S , p*j, (((Kc)E )D ) = K p c p p c If M is a member of S , M decrypts (K )E with D and get K . p c p C P 32 p c Figure 3.7 Initialize and distribute subgroup and group key For example, in Figure 3.7, M initializes K for Si, encrypts Ki with the public !9 } key of Mi, M and M and multicasts <(Ki)E (K,)E , (Ki)E > to S . When Mj receives 2 8 h 3 8 t 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 (K ) and distribute gmup encrypted K group along the subgroup ring. 1) M initializes K. group s 33 S 2) M s h M £ s Si. encrypts K M g r o S i : s u p ( K g r o u p ) K i with 5, 's subgroup, key and multicast to 5,. 3) When a leader node Mj (M,-e Si) receives gets K g r o u p , where K g r o u p = ((Kgro )Ki)Ki. Up ( K g r o u p ) K i , it decrypts ( K g r o u p ) K i with K t and (This applies to all subgroup leaders.) 4) Because Mj is the joint leader of another subgroup, 3St, MjG S^ and M e 5" M => 5*: y ; (Kgroup)Kk Joint leader works as a bridge of two subgroups and propagates K g r o u p ring structure to the whole group G, as shown in Figure3.8. Figure 3.8 Distribute K g r o u p 34 along the subgroup ring along the subgroup Num of Unicast N Size of Unicast Msg Nx(l + [E] + Nx[ID]) Num of Multicast 3xT Size of Multicast Msg +1 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 (K and K ), [K] = 128 Bits = 16 Bytes [ID] - length of MAC address, [ID] = 12 Bytes T is the total number of subgroups, T~\ N/M ] subgroup group 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: \)M ^>G: {JOIN_REQUEST} r Requesting member - M multicasts a JOIN_REQUEST message to G. r 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) M -M : r t {JOIN_CONFrRM, E ) r Assuming the first JOIN_REPLY is fromM,(M, is a subgroup leader), then M unicasts a r JOIN_CONFIRM to M together with M 's public key E ti r r 4) After M, receives the JOIN_COMFIRM, M, add M into subgroup S (Assume M, € S ) r 5) M, updates K and K . c group 36 c c M 6) t = > S : c { { K ) K _ c c o l , d < M ,E r >} r encrypts updated K with K M, c _ C , M combines ( K c ) K c o i with < d M E r r > in one message, and multicasts it to S . c 7) M j € S , c by receiving decrypting ( K M 8) - > M t : r ) K c { ( K c c o ) E l r ( K g r o u ) K p c K r c i o K _ c , c encrypts K with E and M , ) K c with the d , { ( K o l d < S g r o u p C <M, £,>}, adds < M , d r , E r > to 5 and updates C K c by . > } with K c . M , then combines ( K c ) E , r ( K g r o u p ) K c , and < 5 > C in one message and unicasts it to M . r 9) ( K M g r u p receives , ) K c > Af, => 10) M , o r to encrypts K 11) Ms k (Kgroup)Kgroup_old K get G: ( K g G , g r o { ( K r o u p u p c c ) E , r ( K K and ) K g r o u with K p g o r g r i d o u o p g r o u p . _ 0 i u d p ) E r , g r o u p _ 0 i d C then stores > } , < S C > and decrypts < ( K c ) E r , and multicasts this to the whole group. k*r, by receiving with K < S ( K g r o u p ) K . 37 g r o u p o i d , updates K g r o u p by decrypting © Figure 3.9 K e y update at Join Event Event Public Encryption Join 1 Symmetric Encryption Symmetric Decryption 3 M +N + 1 Table 3.3 Computation cost at Join Event N u m of Unicast Size of Unicast M s g N u m of Multicast Size of Multicast M s g Round 2 [E] + 2x[K]+Mx([E] + [ID]) 2 2x[K] + [E] + HD] 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 € S t c 2) M and M are leaders of S , and a < b a b c The key update at non-leader node leave event has 5 steps: {LEAVE_REQUEST} \ ) M i - > M a . Mi unicasts a LEAVE_REQUEST to the subgroup leader of S with a smaller ID (here it c is M ) , then Mi leaves the group. a 2) M removes M from S . a 3) t e S , Mj VMj c M ^S : a c c * M { { ( K c a , M a encrypts K with Ej, ) E j } , M i ) ( K c for VMjSS ,j^a c 39 c ) E j M updates K . For each member A/,- in S , M encrypts K with the public key £}, a c c a c combines all the encrypted K together with M/s ID into one message {{K )Ej, Mi}, and c c multicasts to S . c 4) By receiving {{(K )Ej), Mi}, Mj(Mj s S ,j*a) decrypts (K )Ej with D and get updated c c c ; K = ((K )Ej)Dj. c c Mj also removes Af from its subgroup member list. ; 5) M updates K a group and multicasts K group along the subgroup ring structure; this is same as the K n distribution we discussed in 3.3.2. sroU 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 M is the joint node of x two subgroups - 3S and 3S , Mi € S and Mi € S , and a < b. a b a b If [S ] <ax SUBGROUP_SIZE and [S ] < 1/3 x SUBGROUP_SIZE, or [S ] = 2 a b a or [S ] = 2, (0< a < 1, a can be configurable. In our implementation, a = 1/3). We merge b S and S to a new subgroup - S . Otherwise, we select a new joint leader (see the a b a discussion in 3.4.3). The subgroup merging and key update has 4 steps: 41 1) Mi => S , S : { L E A D E R L E A V E , <a, [S ]>, <b, [S ]>} a b a b The leaving node M multicast a LEADER_LEAVE request to both S and S with ID and t a b size of both subgroups. 2) Mjjri, if Mj € S , Mj, remove M from member list of S . a a t if Mj e S , Mj, remove Mi from member list of S . b b By receiving the Leader_Leave request, members of S and S remove Mi from their a b subgroup node list. 3) 3M , M € S , M is the leader of S and M *M . P p a p a p t 3M , M s S , M is the leader of S and M #M . q a b q b q ; M =>S : {<S >,p,a} p b a M ^>S : {<S >,q,b} a a b Since each subgroup has two subgroup leaders, we can find the remaining leader, M (M p p *Mj) for subgroup S , and M for S . M multicasts <5 >, ID of M and subgroup ID of S a a b fl p p a to subgroup S . When members of S receives this message, they add the member list of b b S to their subgroup, replaces M with M as the new leader and sets a as the new ID a for a t p the subgroup. M also sends {<S >, q, b} to S . When members of S receive {<S >, q, b), they set M a b a a as the new leader, and adds <S > to their member list. b 42 b a After this message exchange, all members from former S and Sb have {<S > U <Sp>} as a a their member list, and have <M , M > as the pair of subgroup leaders and the same P q subgroup I D - a. So they are merged to a new subgroup - S . a 4) The leader node with smaller I D updates If M p and M q K and K a . group is the leader nodes of S and p < q, then M a securely distributes <K , K >. a group p updates K and K a group and This step is same as step 3, 4 and 5 i n Non-Leader node leave 3.4.1. 43 Leaving Node (1) M , ^ > S , . S . L E A V E _ R E Q U E S T 2 (2) M *>S :{<S?,M"SJ 9 3 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 [ID] + IxaxM x([E]+[ID]) + 2xax Mx[K]+ Tx[K] Size of Multicast Msg T+3 Round 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 [S ] > [S ], then the new leader will be selected from S (if [S ] > [S ], then the a b a b a new leader will be selected from S ) b In step 1, the leaving node will send a leaving request together with the ID and size of both subgroups S and S . Assume M is the leader of S and M is the leader of S . By a b p a a b receiving the leave request from step 1, if [S ] > [S ], then M will select the new leader, a b p otherwise, if [S ] < [S ], then M will select the new leader. a b a BM , M e S , M *Mi and M *M (Here we assume M is the leader of S and M is the h h a h h P p leader of S ), M randomly picks a node M from S as the new leader. b p h 45 a a q 4) M => S , S : <h, E , a> p a h b M multicast to S and S the selected new leader M and its public key Ehp a b h 5) VMj e S , by receiving the message from Step 4, Mj set M as the new leader. a h 6) VMj e S , by receiving the message from Step 4,Mj adds < M , E > to S 's subgroup b h h b member list and sets M as the new leader. h 7) M -> M : < S > {M <= S and M is leader node.) q h b q b q M - the leader node of Sb unicasts <S > to M ,. q b h 8) By receiving messages from step 7, Mh creates and adds <S > as Sb's member list. b 9) M updates K and multicasts it to S . This step is the same as step 3 and 4 in Nonh a a Leader Node Leave. (3.4.1) 10) M updates K and multicasts it to subgroup S . This step is the same as steps 3 and 4 h b b in Non-Leader Node Leave. (3.4.1) 11) M updates K h group and multicasts encrypted K group 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) «, =>S S : {M E 9 | r 2 fp ip 1} (Step 4) (2)M,=>M :{<Sj>><Stop7) M ! <3) M,">S,: {(Kg) £J (Step 9) j <4)A^ =>S :((>g£)(Step10) 9 3 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 Size of Multicast Msg Round T+4 2x[ID] + [E] + 2x Mx[K]+ Tx[K] 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 P2PHGKM 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 - M is s elected by running bully algorithm among all member nodes. This M is responsible for s 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 N 1/2 subgroups and each subgroup has roughly N m 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 Join P2P-HGKM GDH 2.0 AT-GDH Tree-Based 1 public enc + 1 public dec + 3 symm enc + M +N+1 symm dec 0(N ) exp. 0(Nlog N) 2 x (n-l) symm enc 2 k exp. (h-l)+ Nxd/(d-l) symm dec Overall: 0{N) symmetric decryption M public enc + Leave M public dec + r NIM1 symm enc + N symm dec OCA') exp. 0(Nlog N) 0(N ) exp. 0(Nlog N) 2 2 k exp. O(A0 symmetric decryption k exp. (d-l) x h symm enc + Nxdl (d-1) symm dec Overall: 0(N) symmetric decryption + 0(M) public encryption 0(N ) exp. 2 0(Nlog N) k 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 DiffieHellman key agreement protocols, e.g. GDH2.0 or AT-GDH, requires 0(Nxlog N) or k 0(N ) exponential computation at each Join or Leave request. Our P2P-HGKM protocol 2 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 \+qxN lr Number of Public Encryption M t N T T qxM TqxN ia Q I I 6 L 8 1 ! I 10 12 14 M m eb s r e per S u b g r o u p (if) a)M 55 16 16 20 24 28 32 36 M m eb s r eof G o r u p (A ) 40 1 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 3x(l-q) + q q) / M xN m Number of Symmetric Encryption MT Nt I (Nxq)/M Tq X N 56 m 120 B 0 100 *» sH so •Jj 60 u h g •SO i 1 in 2 0 0 8 10 1 2 1 4 M m eb s r e per S u b g r o u p J O ( 18 a)M 100 •:•••. a eo s a ro 60 I SO & i 4 0 1 3C 20 to 0 24 28 32 36 feobers of G o r u p A () it 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)xN m 57 Number of Symmetric Decryption M T t (\-q)xM Nt T N +(!-<?) xN m § ° 0 "Z 900 s w , I | S60 840 I 820 I .—, , __ — = 1 1 I ' 6 1 1 1 8 10 N e r a b e r s per 12 14 S u b g r o u p (M) b)N Figure 4.3 Experiment result: symmetric key decryption 58 16 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 Num of Unicast Size of Unicast Msg Num of Multicast Size of Multicast Msg Round Non-Leader Leave 2 [E] + 2x[K] + Mx([E] + UD]) 2 2x[K] + [E] + [ID] 4 Leader Node Leave Leader Node (Merge) Leave (Replicate) / 0 [ID] 0 T+ 1 T+4 Tx[K] + Mx[ID] + Mx[K] T+2 Mx([E] + [ID]) T+4 [ID] + 2xaxM 2x[ID] + [E] + 2x x([E]+[ID]) + 2xax Mx[K]+ Tx[K] Mx[K]+ Tx[K] T+3 Table 4.3 Summary of communication cost 4.4.1 Comparing with other protocols 59 1 T+4 Join Leave P2P-HGKM GDH 2.0 AT-GDH Tree-Based 2 Unicast (JV-1) Unicast + 2x N Unicast h multicast + 2 Multicast 1 Multicast 4 Round N Round 2k x (log N) Round h Round 2 Unicast (N-l) Unicast 2N Unicast 4+ T Multicast 1 Multicast OI) x OI) multicast 4 + T Round N Round 1 unicast k 2kx(log N) Round h Round k 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 P2PH G K M 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 MT Unchanged <-> N T Unchanged <-> f 6 8 10 M m eb s r e per 12 H S u b g r o u p (tf) 16 a) Af 35 30 20 15 to 16 20 24 28 32 36 M m eb s r e of G o r u p A () 40 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 jl/2IN' ([E]+2[K]x(\-q) + 2x[ID]xq) + ([E]+[ID])x(l-q)xN - [ID]xq 1/2 Message Size of Multicast M t T([E]+[ID])x(l-q)xM-[ID]xq/M NT t ([E]+[ID])x(\-q)xN - [ID]xq 1 N m 3 0 0 0 0 n m i MIM ..in 2 5 0 0 0 S 2 0 0 0 0 in « 1 5 0 0 0 3 1 0 0 0 0 f 5 0 0 0 0 8 10 12 14 M m eb s r e of S u b g r o u p OO a)M 62 1G I40OQ 120OO 10000 — N £ tt | - — • \ «-" 80()0 ; _ ; , g oo 0 o —I - -I ; 16 20 J J24 28 1 32 36 40 M m eb s r e of G o r u p (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(N m + ?>IN ) m Number of Multicast MT NT iqX{N+3)IM T qx{ N + 3I N ) when N>3 m m 63 8 10 1 2 1 4 M m eb s r ep e r S u b g r o u p (Jf) 3 120 MM- jmmmmmm 100 | 80 <- 6 0 1 6 — — 1 — ^Jl_ . - I s . J 10 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])xqxN " + qx(2x[ID]+[E]) IN' 1 Message Size of Multicast MT f ([ID]+[K])xqxM + qx(Nx[K]+2x[ID]+[E])/M Nt T ([lD]+[K\)xqxN + qx(2x[ID]+[E]) 1 N m m w 5 0 0 * 0 1 4 0 0 0 2 3000 2 C 0 0 1 0 0 0 0 8 1 0 1 2 1 4 M c s f e r s p e " l S u b g r o u p 0 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(N + 2 / N ) m m Round M Nt iqX(N+2)IM f tqx{ N + 2I N ) when N > 2 m m 66 Chapter 5 Conclusion and Future Work 5.1 Conclusion To support dynamic secure group communication in ad-hoc networks, a group key Kg p roU 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 K group 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 S Leader Node of 3 Subgroups 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 K g r o u p the group key shared by all members of the multicast group '• _oid • 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 E : public key of node i (Mi) t D : provate key of node i (Ml) t Si: Subgroup S,, i is ID of the subgroup. <5,> : node list of subgroup 5, :{Rekey Msg} : M, unicast {Rekey Msg} to M, Mi—>Mjr Mi => S :{Rekey Msg} : M, multicast {Rekey Msg} to subgroup S c M i = > G : c {Rekey Msg} : M, multicast {Rekey Msg} to multicast group 70 G 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 24, 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 OnDemand 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
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
P2p-hgkm : an efficient hierarchical group key management protocol for mobile ad-hoc networks Peng, Peng 2004-12-31
Item Metadata
- Media
- [if-you-see-this-DO-NOT-CLICK]
- ubc_2004-0593.pdf [ 6.42MB ]
- [if-you-see-this-DO-NOT-CLICK]
- 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
- Original Record: 1.0051627 +original-record.json
- Full Text
- 1.0051627.txt
- Citation
- 1.0051627.ris
Full Text
Citation Scheme:
Usage Statistics
|United States
|Saint Petersburg
|Mountain View
|University Park
|Kuala Lumpur
|{[{ mDataHeader[type] }]}
|{[{ month[type] }]}
|{[{ tData[type] }]}
Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
async >
Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


text: Item is not available Find Another One Others Looked At... Beretta CX4 Storm 9MM SELLER: WROzzy 0 $849.00 Beretta ARX-160, .22 LR Carbine SELLER: Alpha Omega Services 1 $549.00 THE NEW BERETTA ARX 100 ARX100 5.56 556 ... SELLER: AA Tactical 1 $1,649.99 Beretta ARX-100 LEO/MIL SELLER: Jays Guns II 1 $1,699.99 Beretta ARX160 .22LR Tactical Rifle **Ne... SELLER: PERRYS GUN SHOP 1 $559.99 Guns Rifles Beretta Rifles Storm Beretta CX Strom | 72 | 105 | Lc | 343.8588ms Beretta CX4 Strom For Sale from Security and Police Equipment | Positive feedback: 97% View | Verified Seller | 1052 Completed Sales View Sellers Items This item is no longer available. Description Shipping and Payment More Info This is a new in the box CX4 Storm in 9mm. The gun comes with two magazines, cleaning rod and brushes, accessory rail and tool, and all factory paperwork. The gun has a lifetime replacement guarantee from Davidson's. The magazines are compatable with beretta handgun magazines. The Beretta Cx4 Storm semiautomatic carbine is a sporting or personal defense firearm with a particulary captivating appearance and simplicity of use. The blowback type locking system and the bolt safety ensure reliability, great stability and precision in follow up shot. The extractor, the ejector and the cocking handle are easily reversible for right and left hand use. The manual safety button and the magazine release button can also be reversed from one side of the carbine to the other. The cold hammer forged barrel is chrome lined and made of high resistance steel for maximum resistance to corrosion and increased barrel life. Extensive use of technopolymers has allowed the development of a light and technically advanced firearm as well as equipping it with very modern an ergonomic lines. Rounded forms are snag free, facilitating handling and rapid shouldering and aiming. We accept credit cards for payment, but we add a 3% fee for there use. Money orders and cashier's checks are also accepted. Actual Cost Trades Accepted: No Security and Police Equipment, has been in business since 1974. We are a Police Officer family owned business, and pride ourselves that we only sell quality products. The three day return policy applies to new and used firearms, and buyer must pay return shipping. New firearms once fired are non returnable, and all warranty issues \"MUST\" be handled by the manufacturer, or \"Wholesaler\" depending on who warrants it ! !We are Gold Master Law Enforcement Dealers. Officers and Departments MUST call for Police pricing etc. All pries quoted are cash price, all other payment requires a 3% Fee.We also carry a large line of civilian firearms, and a complete line of sporting goods, inc Condition: New In Box Caliber: 9 mm (other) Location: MN Share Item Item #: 976948540 This item is no longer available. Price: Shipping: See Description (or Arrange local transfer) Accepted Payment Methods: Returns: No Returns Security and Police Equipment Seller Since: Jan. 2003 Seller Level: Gold Seller + This seller is an FFL City: Farmington State: MN More Items from this Seller ( 132 items total | View All ) Advantage Arms Magazine .... $16.00 Full Details Add To Cart Advantage Arms .22 LR Con... $270.00 Full Details Add To Cart Beretta 92 20 Round Magaz... $30.00 Full Details Add To Cart Mc | 15.5264ms -- 4649 Your Recently Viewed Items

subset: commoncrawl


text:
TomTom Runner. Colour of product: Grey, Waterproof up to: 50 m, Protection features: Water resistant. Languages support: DEU, ENG, ESP, FRE, ITA. Display resolution: 144 x 168 pixels, Display size (HxV): 21.8 x 24.9 mm (0.86 x 0.98"). Battery life: 10 h. Weight: 50 g
Stay motivated and reach your running goals with the TomTom Runner GPS watch. Get easy access to the information you need to track your progress and boost your performance. Sync, analyse and share your stats on popular sport sites or apps.Designed for Runners- Extra-Large DisplaySee your key running stats at-a-glance. View distance, run time and pace on a high-resolution and high-contrast display.- Ultra-Slim DesignRun with a lightweight watch designed for runners. The slim design comfortably fits all wrist sizes.- One-Button ControlNavigate easily through menus with the intuitive One-Button Control. Get started quickly and keep moving with easy access to watch functions and your key stats.- Super-Tough DisplayRun with a durable, scratch-resistant display. Super-tough scratch and impact-resistant display stays easy to read, run after run.- Vibration AlertsStay focused on your run with milestone alerts. Hear beeps and feel vibrations to get milestone, lap and training alerts, even when listening to your music.- Multiple Comfort Strap OptionsCustomise your watch to suit your style. Choose from a variety of Comfort Strap colors and shapes and to suit your taste or mood.Graphical Training Partner- Graphical Training PartnerTrain more effectively with full-screen graphics. View your training performance at-a-glance with three unique graphical training modes.- RaceRace yourself: Compare your current run with past performances. See in "real-time" where you are compared to your best or last run so you can continue to improve, run after run.- Challenge yourselfSee that you are on track to achieve your goals. Set a distance, time or calorie goal and check your progress in a simple full screen graphic.- ZonePace yourself: Instantly see if you are in the right training zone. Set a target for pace or heart rate* and see in a simple full screen graphic how you are tracking throughout your run. *Heart Rate Monitor included.Run Anytime, Anywhere- Indoor TrackerTrack your run indoors and on a treadmill. The TomTom Runner's built-in sensors count your strides so you can monitor your pace and distance.- Waterproof up to 165 feet / 5ATMRun in all kinds of weather. The TomTom Runner is waterproof up to 165 feet / 5ATM and as weather-ready as you are.- Up to 10 Hour Battery Life [GPS Mode]Run more, recharge less, with up to 10 hour battery life [GPS Mode].- QuickGPSFix TechnologyGet out on your run faster. QuickGPSFix helps your watch find your precise location quickly so you can start your run.Connect Easily- Desk DockCharge and sync your watch. The Desk Dock connects to your PC or Mac easily, quickly and reliably.- Multi-Platform CompatibilitySync, analyse and share your stats on popular running sites or apps. Easily upload information about your runs to track progress against your goals. Learn more about TomTom MySports and data compatibility.- Bluetooth® Smart ConnectivityConnect to sensors using the latest wireless technology. The TomTom Runner uses Bluetooth® Smart Technology to connect to the TomTom Heart Rate Monitor* and other compatible Bluetooth® Smart accessories. *Heart Rate Monitor included.- Heart Rate MonitorMeasure the intensity of your workout. Use the optional Bluetooth® Smart Heart Rate Monitor* to understand if you're training within the right zone for weight control, performance or speed. Speed up or slow down to stay in your training zone. *Heart Rate Monitor included.


text:
Custom built ranch home on 3.47 acres with beautiful mountain view. 4-5 bedroom, 2 full bath, formal dining, Hickory Hardwood Floor, Tile, Custom Hickory Kitchen cabinets, Granite counter tops, stainless steel appliances. Viessman boiler with zoned radiant heat. Basement is partially finished currently with 1 bedroom and family area, leaving plenty of space for additional rooms to fit your needs. Off the back deck you can sit and enjoy the tranquility of this location and the beautiful mountain views. Landscaped yard with plenty of flat areas to entertain the kids or enjoy some gardening. Only minutes from Lake Champlain and bridge to Vermont. This home offers too many amenities to list them all. Make an appointment to come see them for yourself. Truly a magnificent home!
Listing Courtesy of Glebus Realty Inc.


text:
Countable and Uncountable Nouns 4
In this ESL countable and uncountable nouns worksheet, learners examine the list of 30 nouns and identify those that are uncountable nouns. Students may also write sentences using each of the words.
4th - 7th English Language Arts 11 Views 26 Downloads
Resource Details
Start Your Free Trial
Save time and discover engaging curriculum for your classroom. Reviewed and rated by trusted, credentialed teachers.Try It Free
Grammar, Usage, and Mechanics
If you're planning on teaching grammar in your fifth or sixth grade class, take a look at a packet of language arts activities that would be perfect for any grammar lesson. Covering skills such as parts of speech, sentence and paragraph...
5th - 6th English Language Arts CCSS: Adaptable
Greek and Latin Roots, Prefixes, and Suffixes
How can adding a prefix or suffix to a root word create an entirely new word? Study a packet of resources that focuses on Greek and Latin roots, as well as different prefixes and suffixes that learners can use for easy reference
3rd - 8th English Language Arts CCSS: Adaptable
Making an Argument: Effective use of Transition Words
Work on using transition words in context by prompting elementary and middle schoolers to write their own persuasive essays using transition words. They explore new forms of transition words and examine how they are used in an editorial...
5th - 9th English Language Arts CCSS: Adaptable
Seeing Words in a New Way
What's the best resource to use when looking up words? Use Visual Thesaurus to see a word's meaning. The class accesses the interactive website and then compares and contrasts the difference between using a traditional dictionary and the...
6th - 12th English Language Arts CCSS: Adaptable
What Members Say
- Cedar Grove, TN


text:
Dismiss NoticeLike to discuss POLITICS? Come join us at PUNNDITS.com!If you like discussing politics and other related topics then your new home (hopefully) for doing just that can be found on Punndits.com! Come join us and help us grow Punndits into a wonderful and safe place to discuss politics with everyone.
Meet the Members!!!
Discussion in 'Members Zone' started by jterrell, Aug 24, 2005.
Page 1 of 2
Page 1 of 2


text:
Cape Cod Baseball League
Check out the next crop of baseball all-stars
10 Venues, Throughout The Cape, MA 02601
26 people saved this
College stars show off their game every summer at the Cape Cod Baseball League. Over a thousand pro players got their start here, and Major League Baseball has provided financial support to the Cape League for over 40 years. Because it draws top-tier college players, the level of play is often considered the equivalent of high-A Minor League Baseball. Teams include: Bourne Braves, Brewster Whitecaps, Chatham Athletics, Cotuit Kettleers, Falmouth Commodores, Harwich Mariners, Hyannis Mets, Orleans Cardinals, Wareham Gatemen, Y-D Redsox
Of Note:
- Amenities: Accessible Facilities
Franklin County CiderDays
Franklin County CiderDays runs November 4 - 6, 2016 Hard cider, America's beverage of choice during colonial...
Search All Listings Here.


text:
Full Day Snowboard Lessons including lunch from 9:15 am - 2:15 pm.
Full Day Ski Lessons including lunch from 9:15 am -2:15 pm.
Lesson Information:
Children divided into small groups based on skill levels of new & experienced.
Approximately 1 coach to 8 children.
Activities start for child upon entrance to their designated area.
Golden Explorers (Ski/3-5 yrs.)
Half-day Ski Lessons from 9:15-11:45 No Lunch
Half-day Ski Lessons from 9:15-12:15 with Lunch
Full Day Ski Lessons from 9:15- 2:15 with Lunch/Rest
Parents can enjoy 'fun in the snow' while their young children spend the day at Lil' Buckaroo Day Care on-site at RRSA. Children from six months to 4 years of age are provided a full day of child care - complete with activities, crafts, snacks and lunch, rest time, and outdoor play. Reservations not required but there are a limited number of slots available each day. Contact us today for more information AND to ensure a space for your child. We want the whole family to have a great vacation at Red River Ski & Summer Area. Full Day - $85, Half Day - $55.
Full Day Ski Lessons including lunch from 9:15 am - 2:15 pm.
Approximately 1 coach to 6 children.
Full Day Snowboard Lessons including lunch from 9:15am - 2:15 pm.
Drop off at the Youth Center between 8:30 am and 9:00 am.
Pick up IN RED TENT AT 2:15 pm.
No Storage for extra clothing.
Recommended Choice:
The child must have independent toilet skills.
No diapers or pull ups are accepted.
With private lessons in this age group we recommend 1 student per lesson.
A 2-hour lesson is the best choice as it allows students the time to gain new skills and receive coaching with feedback on various terrain. If there are multiple students the lesson will be on the terrain that the least experienced student is capable of for safety reasons.
3 Hour and 15 minute class starting at 9:00 am.
3 Hour and 15 minute class starting at 12:45 pm.
Allow adequate time to complete registration/purchase process particularly during peak season (1 hour recommended)
3 Hour and 15 minute class starting at 9:00AM
3 Hour and 15 minute class starting at 12:45PM
Take the Tour!
Our Snow Coach Dinner Tour has exceeded all expectations! Great food and a cozy mountain experience in the Red River Ski & Summer Area's snow cat makes for a memorable experience.
Choices for Adult Lessons
First timer skiers and snowboarders can choose Class Lessons or Private Lessons. For guests who have skied before, we offer Private Lessons.
Torchlight Parade & Fireworks and Rail Jam
Every Saturday and Holidays, 7 pm prior to daylight savings time – 8 pm after March 12, 2017 during ski season.
Location: The FACE at the Red River Ski & Summer Area
The TRIPLE PLAY CARD is back by popular demand! This $99 pass is valid for use any 3 days in January and February. The best part is it is a direct to lift pass so upon arrival, you are ready to hit the slopes! Offer expires November 1, 2016. Shipping charges apply to this item.
Winter Snow Tubing opens Tuesday afternoon, November 22, 2016, the day before RRSA opens for skiing and riding. Starting on November 23, 2016 there will be winter tubing offered on weekends only until December 9, 2016 when we open for daily snow tubing throughout all of December. January we limit days and times of tubing. It is best to call for days and times during January. We are open Febraury and March daily for winter tubing through March 18, 2016. All winter tubing sessions are one hour in length and are on a first come first serve basis.


text:
Professional Boiler Repairs in Minocqua, WI
Fast Boiler Repairs in Minocqua, WI
Reliable Boiler Repairs in Minocqua, WI
Long Lasting Boiler Repairs in Minocqua, WI
Finding the best boiler repair Minocqua, WI can offer is crucial if there is any type of problem with your boiler at home. If you have a very old boiler in your home, it may be necessary to pay for repair services so you can get it working properly again. If you detect a metallic smell by your boiler, it may mean that there is a gas or oil leak. A gas or oil leak can be a very serious problem and potentially dangerous, which is why you will have to hire professionals to fix it as soon as possible.
Average Costs For Boiler Repair
Complete Projects
Find the Best Costs for Boiler Repair - Minocqua
A Tree Menu specialist on boilers in Minocqua will be able to fix whatever is wrong with your boiler at home. A Minocqua boiler repair service is necessary if there is anything wrong with your boiler. A small problem with a boiler can quickly become serious, which is precisely why you will need to get it taken care of before it is much more expensive to fix. If your boiler has started making any unusual noises, this is another sign that you will have to hire Tree Menu to come to your house and take a look at it right away.
What zipcode
do YOU NEED
Elastomeric Roof Coating Companies in?
Boiler Repair in Minocqua FAQ
What are the benefits of boiler repair services in Minocqua, WI?
Boiler repair services in Minocqua, WI are important for those who want to keep their boiler in good condition for as long as possible. Those who do not get the necessary repairs done to their boiler over time will find that they will need to buy a new one before long. If you want to avoid spending a lot of money on a new boiler sooner than necessary, it is imperative that you take advantage of Minocqua boiler repair services. By getting these repairs done you will also be able to keep your home as energy-efficient as possible.
Is a professional needed for Minocqua boiler repair work?
Unless you have the necessary skills and experience with boiler repair work, you will need to pay for professional Minocqua boiler repair services. Our professionals will have everything needed to fix your boiler so that it is once again in perfect working order. It is extremely important that you pay for these services and that you hire legitimate professionals to do the work. While you might be inclined to attempt doing this work yourself to save some money, you could end up actually making the problem with your boiler even worse.
Are professional boiler repair services in Minocqua, WI expensive?
You will find that Minocqua boiler repair services are actually usually quite affordable, especially when you take advantage of them as soon as you notice there is a problem with yours. The sooner you hire one of our Minocqua boiler repair professionals to do this work for you, the more money you will end up saving in the long term. It is important to look at the money you spend on these services as an investment in your boiler, because that is exactly what it is. By paying for boiler repair services in Minocqua, WI you will be able to keep the same boiler for years to come.
Hammond Plumbing and Heating Inc986 Po Box Minocqua, WI 54548
Meade's Electric & Heating LLC10145 Wisconsin 70 Woodruff, WI 54568
HVAC Plus1745 Thorofare Rd Minocqua, WI 54548
Great Northern Plumbing & Heating8797 Earls Ct Minocqua, WI 54548
Northland Heating Inc6000 State Rd 51 Hazelhurst, WI 54531
Smokey's Heating Inc1248 Old 51 S Woodruff, WI 54568
- AC Companies Minocqua
- AC Repair Minocqua
- Air Conditioning Repair Minocqua
- Air Duct Cleaning Minocqua
- Furnace Repair Minocqua
- Heat Pumps Minocqua
- Heating Repair Minocqua
- Humidifier Minocqua
- HVAC Minocqua


text:
For our full list of events and workshops for teachers, learning and development professionals and policy analysts, see below.
Our Annual Events
Learning at Work Week - 16th-22nd May 2016
Family Learning Festival 15th-30th Oct 2016
Policy seminars
How to Design Powerful Learning Campaigns for your Workplace
Campaign for Learning
Central London
Coaching to create a learning mindset a practical workshop
Campaign for Learning 24 Greencoat Place London SW1
Technology & Engagement Series for Schools & Organisations working with families
Recording and materials of three online sessions available to buy now!
Purchase one or all three sessions
1. Delivering a programme of digitally-based
family learning activities
2. Getting parents through the door
3. Developing a whole-school parental
engagement approach
Community and family learning
Family Learning Festival - 2017!
Across the UK
Family Learning Festival - 2017!
Across the UK
© 1998-2010 Campaign for Learning


text:
First Team All-Americans
When you think of soldiers and especially those killed in action, you generally conclude most came from the poorer parts of town. But with five young servicemen cut down in their primes, Irvine is the Orange County hometown with the most war dead from the conflicts in Iraq and Afghanistan. It's also the fourth best place to live in the country, according to new Money magazine rankings that would have placed Irvine higher were real estate not so expensive there.
According to figures compiled by the Iraq Coalition Casualty Count (and subject to immediate change that could blow this roster out of whack), the next OC towns, with three war dead each, are Anaheim, Fullerton, Orange, Placentia and Santa Ana. Two each from Huntington Beach and Mission Viejo gave the ultimate sacrifice, while one apiece called Costa Mesa, Garden Grove, San Clemente, San Juan Capistrano, Westminster and Yorba Linda home.
Broken down by Orange County high schools the young heroes attended, two each went to Irvine High, Mission Viejo High, Sunny Hills High in Fullerton and Valley High in Santa Ana. Schools with a lone war dead (so far) are Calvary Chapel High School of Santa Ana, El Dorado High of Placentia, Esperanza High of Anaheim, Garden Grove High, Huntington Beach Continuing Adult Education School, Huntington Beach High, Loara High of Anaheim, Newport Harbor High of Newport Beach, Saddleback High of Santa Ana, San Clemente High, Trabuco Hills High of Mission Viejo, Valencia High of Placentia, Western High of Anaheim and Westminster High School.
There has been only one man who called Orange County home killed in action this year. Orange's Brandon A. Meyer, the son of a Lutheran pastor, was one of five soldiers killed in Mosul on Jan. 28 when their convoy was hit by a roadside explosive.
Get the This Week's Top Stories Newsletter
Every week we collect the latest news, music and arts stories — along with film and food reviews and the best things to do this week — so that you'll never miss OC Weekly's biggest stories. Every week we collect the latest news, music and arts
In Case You Missed It
Upcoming Events
Anaheim Ducks
TicketsFri., Oct. 28, 7:00pm
Anaheim Ducks v. Columbus Blue Jackets
TicketsFri., Oct. 28, 7:00pm
Ontario Fury v Tijuana Atletic Baja
TicketsSun., Oct. 30, 3:05pm
Anaheim Ducks v. Pittsburgh Penguins
TicketsWed., Nov. 2, 7:30pm
Popular Stories
Sponsor Content


text:
"The only true limit to the Internet
is the number of IP addresses."
Bob Evans
Not all IP addresses are alike, choose Legacy IP space.
Interop was a great tradeshow for us last month. Market demand is here. We leased much more space than we anticipated. It's best to get your deal done ASAP while you can lock prices for your business plans.
Everyone agrees IPv4 address cost will rise. Act now! Predicted monthly costs to $40 per IP address before IPv6 becomes a popular standard. Wholesale prices are well under $2 based on volume and time commitment. If you need IPv4 space for temporary renumbering a special fee can be arranged.
Current Pricing
Legacy address space current price per IP address in quantities of /24, /23 or /22 is 6.3 cents per day. Or $1.90 per IP address per month.
Cloud and Data Center Small IPv4 Subnets
Need small subnets for Cloud and Data Center service connections ? We deliver fast !
Instant availability
A simple contract, no outside approvals needed.
No Red tape
Legacy space is not subject to RIR rules.
World-wide usage
Works in RIPE, ARIN, APNIC etc. Legacy addresses are not subject to RIR region origination rules.
Clean, No blacklisted IPs on RBLs
No spammers allowed. All mail services must be community acceptable standards.
Favorable lease option renewal
Your annual option to continue or cancel without obligation.
Fixed annual percentage increase
As prices rise you save and know your coast.
These work with any & multiple ISPs
Letter of Authorization provided. You control BGP announcements.
You're in control with reverse DNS
We SWIP your contact information and DNS servers in the ARIN database.
Read the FAQ for plenty of detailed information.
Call us at M-F 9AM-5PM Pacific 213-342-2878
2635 Park Blvd. Palo Alto , CA 94306


text:
Sharing Presentations & Documents
Sharing PDFs
On this topic
With 3CX WebMeeting you can convert your presentations and documents to PDFs in advance so that they will run from the server in high resolution during the meeting. Users can save their PowerPoint presentations or Documents as PDFs so that they can be shared during a 3CX WebMeeting.
Step 1: Share a PDF
- While holding a meeting, click the "Share Doc" button on the top left of your screen.
- Click "Upload" and navigate to the PDF you want to share. Select it and click "Open".
Your PDF will be shared in high definition. To navigate between slides use the "Next" and "Previous" buttons. To stop sharing, click the "Share Doc" button again.
Shared Documents Repository
All PDFs that are uploaded to 3CX WebMeeting and used during a web conference are automatically saved in the Shared Documents Repository.
You can access the repository by following the steps below:
- Open up 3CX WebMeeting in a new tab.
- Click on "Share PDF"
- Click on "Manage Documents" in the bottom left corner.
- A pop up will appear with all your saved PDFs.


text:
- Home
- Shop by Brand
- Michael Gerald
- Michael Gerald Young Men
- Michael Gerald T-Shirts
Young Men: Michael Gerald T-shirts1 Items Found
Young Men: Michael Gerald T-shirts
Belk Michael Gerald Young Men: Michael Gerald T-shirts
If you're looking for guys t-shirts from your favorite designer brand Michael Gerald, then check out our collection at Belk.com. We carry the latest in designer fashion from your favorite brands including Michael Gerald, and we know you'll find something to love in this collection! Looking for specific? Narrow your search for guys t-shirts by using the filters on the left. And remember, Belk offers free shipping on qualifying orders!