Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

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

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
ubc_2004-0593.pdf [ 6.42MB ]
Metadata
JSON: 1.0051627.json
JSON-LD: 1.0051627+ld.json
RDF/XML (Pretty): 1.0051627.xml
RDF/JSON: 1.0051627+rdf.json
Turtle: 1.0051627+rdf-turtle.txt
N-Triples: 1.0051627+rdf-ntriples.txt
Original Record: 1.0051627 +original-record.json
Full Text
1.0051627.txt
Citation
1.0051627.ris

Full Text

P 2 P - H G K M : A n Efficient Hierarchical Group Key Management Protocol for Mobile Ad-Hoc Networks by Peng Peng B.Sc, Peking University, 2000  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science  in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) we accept this thesis as conforming to the required standard  The University of British Columbia  July 2004 © Peng Peng, 2004  UBCl  ml  FACULTY OF 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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
United States 9 0
China 7 6
Japan 4 0
Russia 3 0
Malaysia 2 0
Brazil 1 0
Canada 1 0
Ukraine 1 0
Germany 1 3
City Views Downloads
Unknown 6 3
Ashburn 5 0
Beijing 5 4
Tokyo 4 0
Shenzhen 2 2
Mountain View 2 0
Saint Petersburg 1 0
Kuala Lumpur 1 0
Redmond 1 0
University Park 1 0
Toronto 1 0

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

Share

Embed

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"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051627/manifest

Comment

Related Items