1 1. Introduction Ad hoc networks are a hot research topic. The enabling technology for this field includes: (1) Reduction in size of chips and the nodes that hold them (2) Dramatic improvements in wireless communication speed, bandwidth, and reliability. Because they can, people want to move about freely, with their computers turned on and connected. Ad hoc networks are a natural result of user demand meeting the enabling technology. Highly mobile devices that dynamically organize ad hoc networks, intercommunicate, pass information to other wireless users, and then dissolve characterize ad hoc networks. An essential characteristic of ad hoc networks is the ability to dynamically form communications groups. The inherently chaotic nature of these groups complicates protecting communications security for these groups. There are many proposed cryptographic solutions for group communication in the literature [STW00, STW96, AST00, AST98, FW93, BD95, HK89]. Unfortunately, most of these protocols either require structure that is neither desired nor available in ad hoc networks, or are resource intensive. In this paper, we derive a simple, efficient family of protocols specifically to support ad hoc networks. Computer Science Department Florida State University [email protected] A Family of Protocols for Group Key Generation in Ad Hoc Networks AbstractWith the pervasive distribution of highly mobile computing devices, establishing dynamic networks among these mobile nodes is a growing demand. This new field of study has come to be known as ad hocnetworking. Because of the nature of ad hoc networks, protecting communication in this environment isdifficult, with solutions based on cryptographic techniques. Most existing group key management techniquesare not suited to the ad hoc network environment. In this paper we give a family of efficient cryptographic protocols for establishing secure groups in the adhoc network environment. We begin by detailing the foundational protocol based on the Diffie-Hellman key exchange and show how this protocol is efficient and secure. We go on to give protocols for group join andexclusion, and a corresponding set of authenticating group protocols based on our foundational protocol. Keywords: Cryptographic Protocols, Ad Hoc Networking, Security, Conference KeyEstablishment, Group Keys Alec Yasinsac Vikram Thakur Stephen Carter Ilkay Cubukcu2 2. Ad Hoc Network Group Key Establishment We first outline the environment that we consider for ad hoc group establishment. Our vision is a set of communicating nodes characterized by highly dynamic membership, with short membership duration and a large number of joins and drops. Such dynamic group membership is illustrated in Figure 1. The primary communication medium is wireless broadcast, where most communicating parties receive each message. Messages are relayed [routed] by some nodes, but not necessarily by all. These networks may be densely populated, where nodes receive a high volume of, sometimes rebroadcast, messages. They may also be sparse, where most communication is comprised of relayed point-to-point messages, and where single links may connect sub-groups, so loss of a single link can separate large subgroups. The communication medium is not as important here as is the flavor of the environment that we envision. Ad hoc networks may be connected by any number of heterogeneous communications medium, including radio, infrared, laser, and even dynamic wire and fiber-optic links. We go so far as to point out that fixed communications sites may join in the ad hoc networks, but draw the line where any dependence is given to such existing infrastructure. Specifically, we consider networks as being ad hoc if they have no required, permanent infrastructure. While towers (as those that support cellular networks) are not required, we do not exclude their presence from the environment. Still, we consider that most nodes have short range, low power transmission capability. Our emphasis is on the "ad hocness" of the network. Members come and go at varying paces and with varying throughput requirements and capabilities. The environment that we describe demands efficient protocols, that limit both the number and size of messages and in the number of computations required in each round. As we noted earlier, there have been a number of different group management and group key established protocols proposed in the literature. The most widely published protocol structure is that proposed by Steiner, et al [STW00]. We now give a quick overview of the CLIQUES approach to group key establishment. 2.1. Overview of CLIQUES CLIQUES is a family of protocols for contributory and authenticated group key distribution, based on the Diffie-Hellman (DH) key exchange process [DH76]. In the most simple of the CLIQUES protocols (IKA.2 [STW00]), the key computation proceeds from node to node, with each node raising the previous computations to the power of their private DH value. The final node in the computation string generates the values that each previous node needs in order to compute the final (group) key and transmits all these values in a broadcast message. ABCDEF GABCDEFGABCDEF GFigure 1b Time = T2 Figure 1c Time = T3 Figure 1a Time = T13 While innovative in their approach, there are a number of characteristics of these protocols that limit their utility in ad hoc networks. First, the station-to-station nature of the suite necessitates serial execution of the computations. For a large number of nodes in a highly dynamic environment, this is a critical inefficiency. Additionally, in order to execute a serial computation, the nodes must be serialized. Most critically, the final node in the computation must recognize their position. Such architectural limitations prove both tricky and restrictive, properties that do not fit well in the dynamic, ad hoc environment 2.2. An Optimal Ad Hoc Group Key Agreement Protocol The CLIQUE family of protocols is based on the DH computation with the number of messages and computations on the order of n, the number of nodes. We now offer a foundational protocol, also based on the DH computation, that avoids much of the restrictive nature of the CLIQUES protocols. Most essentially, (1) There is no requirement for serialization and (2) The number of messages required is optimal. 2.2.1 The Foundational Protocol In addition to its efficiency, our protocol family is simple. The fundamental