INTERNET-DRAFT D. Balenson, D. McGrew, A. Sherman NAI Labs, Network Associates, Inc. August 25, 2000 Key Management for Large Dynamic Groups: One-Way Function Trees and Amortized Initialization Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved. Abstract We present and implement a scalable method for establishing group session keys for secure large, dynamic groups such as multicast sessions. Our method is based on a novel application of One-Way Function Trees (OFTs). The number of keys stored by group members, the number of keys broadcast to the group when new members are added or evicted, and the computational efforts of group members, are logarithmic in the number of group members. The method provides perfect forward and backward security: evicted members cannot read future messages, even with collusion by arbitrarily many evicted members, and newly admitted group members cannot read previous messages. In comparison with the Logical Key Hierarchy (LKH) of Wallner et al., our algorithm roughly halves the number of bits that need to be broadcast to members in order to re-key after a member is added or evicted. In addition, and unlike LKH, our algorithm has the option of being member contributory in that members can be allowed to contribute entropy to the group key. Running on a Pentium with 64 MB of RAM, our prototype has handled groups with up to 100,000 members. Balenson, McGrew, Sherman expires February 25, 2001 [Page 01] INTERNET-DRAFT August 25, 2000 Contents 1. Introduction ................................................ 02 2. Previous Work ............................................... 03 2.1 Key Establishment Algorithms for Large Groups ............... 03 2.2 Managing Large Groups ....................................... 05 2.3 Authentication in Large Groups .............................. 06 2.4 Multicast Security .......................................... 06 3. Group Operations and Their Security Requirements ............ 06 3.1 Operations .................................................. 07 3.2 Security Requirements ....................................... 07 4. One-Way Function Trees ...................................... 08 4.1 Structure of an OFT ......................................... 09 4.2 Algorithms .................................................. 11 4.3 Properties .................................................. 13 4.4 Enhanced OFT+ and LKH+ Algorithms ........................... 14 4.5 Comparisons with Other Leading Key-Establishment Methods .... 15 5. Design Choices, Implementation Issues, and Experience ....... 18 5.1 Design Choices .............................................. 18 5.2 Implementation Issues and Experience ........................ 18 6. Amortized Group Induction ................................... 20 6.1 Induction Model ............................................. 20 6.2 Induction Algorithm ......................................... 21 6.3 An Example of Induction ..................................... 22 7. Conclusion and Open Problems ................................ 22 8. Security Considerations ..................................... 24 9. References .................................................. 24 10. Acronyms and Abbreviations .................................. 31 11. Authors' Addresses .......................................... 31 12. Acknowledgments ............................................. 32 1. Introduction Efficiently managing cryptographic keys for large, dynamically changing groups is a difficult problem. Every time a member is evicted from a group, the group key must change; it may also be required to change when new members are added. The members of the group must be able to compute a new key efficiently, while arbitrary coalitions of evicted members must not be able to obtain it. Communication costs must also be considered. Real-time applications, such as secure audio and visual broadcasts, pay TV, secure conferencing, military command and control, and controlling access to the Global Positioning System (GPS) service need very fast re-keying so that changes in group membership are not disruptive. To deal with large group sizes (e.g. 100,000 members), we seek solutions whose re-keying operations "scale" well in the sense that time, space, and broadcast requirements of the method grow at most logarithmically in the group size. Key management for these applications should be able to take advantage of efficient broadcast channels, such as radio broadcast and Internet multicast. Balenson, McGrew, Sherman expires February 25, 2001 [Page 02] INTERNET-DRAFT August 25, 2000 We present a new practical algorithm for establishing shared, secret group communications keys in large, dynamic groups. Our algorithm [McG98, Hard97, Bal98, Bal98b], which is based on a novel application of one-way function trees, scales logarithmically in group size. In comparison with previously published methods, our algorithm approximately halves the required broadcast size. Significantly, our algorithm has the option of being member contributory in that members can be allowed to contribute entropy to the group key. This document describes our algorithm, compares it with other approaches, and discusses implementation issues based on our implementation of this algorithm. 2. Previous Work The broad and challenging problem of establishing keys for large dynamic groups touches upon a large body of previous work, including algorithms for key establishment, group management, authentication in large groups, and multicast security. As for key management, unfortunately very little work has been done on this critical problem in the open literature (e.g. see Schneier [Sch96, pp. 169-187]). 2.1 Key Establishment Algorithms for Large Groups Prior methods for establishing keys in groups fall roughly into five categories: simple methods that scale linearly in group size, information- theoretic approaches, algorithms based on group Diffie-Hellman key exchange, hybrid methods that trade off information-theoretic security for reduced storage requirements, scalable methods based on hierarchies, and other techniques. Sherman [Bal98, Section 7], Kruus [Kru98], Menezes [Men97], and Just [Jus94] survey some of these methods. Unfortunately, the information-theoretic approaches [Blu92, Sti96, Chi89] require exponential space to achieve forward secrecy against arbitrarily many colluding evicted members. Although the group Diffie-Hellman methods [Ste96-7, Bur97, Bur94, Ate98] offer distributed functionality, which might be attractive for some applications, they typically suffer from a linear number of expensive public-key operations. Similarly, the hybrid approaches [Fia93, Ber91] scale linearly or worse. As for other techniques (e.g. [Blo90, Gon89]) that do not fall nicely into any of the above categories, we have not found any that provide adequate security. When the network is a tree, group Diffie-Hellman methods can require only a logarithmic number of operations [Bur97]. Nevertheless, distributed computation is not appropriate for all applications, and the basic unit of cost for all Diffie-Hellman methods still includes expensive public-key operations. Therefore, for large groups, the leading candidates are the hierarchical methods, which scale logarithmically in group size. Balenson, McGrew, Sherman expires February 25, 2001 [Page 03] INTERNET-DRAFT August 25, 2000 Recently, three hierarchical methods have been proposed: the Logical Key Hierarchy (LKH) of Wallner, Harder, and Agee [Wal97, Harn99b], the One-Way Function Tree (OFT) of McGrew and Sherman [McG98], and the One-Way Function Chain (OFC)of Canetti et al. [Can99b, Section 4.2]. LKH is a top-down method in that it "pushes" new group keys down the key tree; OFT and OFC are bottom-up methods in that they derive new group keys from the leaves up to the root. In comparison with LKH, the bottom-up OFC and OFT methods broadcast approximately 50% less bits during a single member evict operation. Only OFT, however, has the option of being member contributory. The first Internet Draft on the LKH algorithm appeared in July 1997, authored by Wallner, Harder, and Agee [Wal97]. The name LKH (suggested by Sherman) was adopted by Harney and Harder [Harn99b] in their 1999 implementation of the algorithm. In July 1997, Wong et al. [Won97, Won98] analyzed generalizations of LKH, and in 1998, Caronni et al. [Car98] independently published a similar idea to LKH. OFT was developed at TIS Labs at Networks Associates, Inc., as part of the DARPA-funded Dynamic Cryptographic Context Management (DCCM) Project [Bal98]. In November 1997, Sherman [Hard97] made the first presentation on OFT. The OFT algorithm is the subject of this document. Importantly, in 1999, Canetti et al. [Can99b, Section 4.2] propose a variation of OFT, which we refer to as One-Way Function Chain (OFC). In OFC, there is always a functional relationship among the node secrets along the path in the key tree from some leaf to the root. OFC shares the broadcast reduction of OFT over LKH; additionally, OFC is slightly simpler than OFT. Canetti claims (without formal written proof) that both LKH and OFC can be proven secure in the sense that a computationally limited adversary cannot distinguish between an actual set of OFC messages versus a set of randomly chosen fake messages. Recent work by Canetti et al. [Can99], which mentions OFT, gives a generalization and improvement of LKH based on a storage- communication tradeoff. They show that, for a group of n users with user storage of b+1 keys, re-keying can be done by broadcasting O((b n^(1/b)) - b) keys with manager storage of approximately O(n). They also prove a lower bounds of b+1 member storage and n^(1/b) keys broadcast, which is tight for constant b. An interesting special case of their tradeoff is O(lg n) member storage, O(lg n) keys broadcast, and O(n/(lg n)) manager storage. [Note: "n^e" denotes n raised to the e-th power, and "lg" denotes log base 2.] Balenson, McGrew, Sherman expires February 25, 2001 [Page 04] INTERNET-DRAFT August 25, 2000 Selcuk, McCubbin, and Sidhu [Sel00] note that, if the a priori member eviction probabilities are known, then these probabilities can be used to advantage by placing members with high eviction probabilities near the root of any key tree. Poovendran and Baras [Poo99] also studied similar ideas. Unfortunately, for most applications, such probabilities are likely not to be known. The hierarchical methods of Ballardie [Bal96, Bal97] and Harkins [Hark98a] are scalable but require trusted routers. In addition, the linear Single Key Distribution Center (SKDC) approach is attractive for its simplicity -- at least for relatively small groups (e.g. see [Harn99a, Harn99c, Harn97a-b]). 2.2 Managing Large Groups Managing large groups is important for group communications and for a variety of other applications, including distributed fault-tolerant computing and virtual private networks. Researchers have addressed important group-management issues including defining group membership, supporting distributed fault-tolerant applications, and effecting decentralized dynamic group management. An important problem in group management is the problem of defining group membership. To support the design of secure, asynchronous, distributed, fault-tolerant systems, Michael Reiter [Rei94] devised a group-membership protocol that tolerates malicious corruption of up to one third of the participants. This protocol is useful in building systems that are robust against limited failures (e.g. hardware failure of some nodes), and that through threshold techniques distribute trust among two or more parties. By contrast, a single group controller is a single point of failure and hence not fault tolerant. Although group keying is often used to secure group communications, another application of group keying arises in security architectures for distributed fault-tolerant computing. For example, Kenneth Birman [Rei93] and his research group at Cornell have studied how the notion of a secure process group can be used to effect secure, distributed, fault-tolerant computing. Their efforts include the ISIS, Horus [Hor], and Ensemble [Hay98] Systems, which provide a framework and toolkit for developing distributed applications. Birman [Rod97] and his group have also applied similar ideas to design a virtual private network that can handle network faults, decentralized management, and dynamic membership. Unfortunately, their "solution currently scales [only] to approximately 100 machines" [Rod97, p. 14]. Also, they claim, that for data confidentiality, "[their] keys are so dynamic and short-lived [changed once a minute] that the approach could be used with a fairly weak cryptographic scheme" [Rod97, p. 1]. Balenson, McGrew, Sherman expires February 25, 2001 [Page 05] INTERNET-DRAFT August 25, 2000 Li Gong [Gon96, Keu96] designed and implemented a toolkit called Enclaves for building secure user-level group applications. Enclaves enable users to form virtual private networks on the Internet dynamically. His methods, however, do not scale to large groups. Other recent work in group management includes research by Fenner [Fen97]. 2.3 Authentication in Large Groups There are several ongoing projects to develop infrastructures to support authentication. Among these are the following. The X.509 [Ken81] approach is based on a hierarchical global name space. By contrast, the SDSI/SPKI approaches of Rivest and Lampson [Riv96], and Ellison [Ell97] are based on linked local name spaces. The Secure DNS approach of Eastlake [Eas97] builds on the existing DNS (Domain Name System). In addition, there is work on batch authentication [Nac94], which provides a way to verify many certificates simultaneously for certificates signed by the same authority under the same signature key. 2.4 Multicast Security Securing multicast is an active area of research. Some examples of this research are works by Kent [Ken81], Gong and Shachan [Gon94], Ballardie and Crowcroft [Bal95], Deering [Dee98, Dee89], Bagnall [Bag99], Mittra [Mit97], Caronni, et al. [Car98], and Canetti and Pinkas [Can98], which address issues, requirements, architectures, protocols, and techniques. In addition, the works by Ballardie [Bal96] and Harkins [Hark98a] on key establishment discuss a variety of security problems and solutions for multicast. Securing Mbone [Kum95] broadcasts is one driving application. 3. Group Operations and Their Security Requirements We envision that the management of group communications keys will take place in a setting in which there will be a communications system, a set of possibly overlapping groups of individuals with common purposes, and individual group members. A systems manager will manage the communications system, and a group manager will manage each group. We envision that groups will comprise a hierarchy of subgroups, with subgroup and organizational managers negotiating on behalf of subgroup members. Some of the above mentioned works on multicast security (e.g. Canetti and Pinkas [Can98]) and on group management (e.g. Harney and Harder[Harn99a]) also provide relevant background for the requirements of OFT group operations. Balenson, McGrew, Sherman expires February 25, 2001 [Page 06] INTERNET-DRAFT August 25, 2000 3.1 Operations Associated with each role (system manager, group manager, individual) is a set of operations, minimally including the following operations. Operations processed by the system manager: - induct individual into system, - evict individual from system, - create group, and - dissolve group. Section 5 explains the concept of group induction. In short, the most important results of system (or group) induction are for an individual to establish a base system key known only to the individual and the system (or group) manager, and for the system (or group) manager to check the credentials of the individual. Operations processed by a group manager: - add member(s) to group, - remove member(s) from group, - evict member(s) from group, - initiate communications session, and - terminate communications session. This document focuses on the crucial operations of adding and deleting members from a group. Note that our OFT method offers some economy of scale when adding or deleting two or more individuals simultaneously. There are two types of membership deletions: a temporary removal (when the individual has not lost his security privileges), and a permanent eviction as the result of loss of security privileges. Operations requested by individuals: - request to join group, - request to leave group, - request to join session, - request to leave session, and - request to return to session. It is possible that an individual might temporarily lose contact with his group manager -- for example, as might happen if an airplane flies out of radio range of his group. Therefore, there must be a way for such a member to re-synchronize key establishment with the group. 3.2 Security Requirements The primary security requirements for the group operations of adding and deleting members are forward and backward security, as quantified Balenson, McGrew, Sherman expires February 25, 2001 [Page 07] INTERNET-DRAFT August 25, 2000 by the degree of forward or backward security [Men97, pp. 528-529]. We say that a method has t-forward security if and only if (iff) no t colluding evictees can read any future communications traffic of the group. Similarly, a method has t-backward security iff no group of t colluding new members can read any previous group traffic. A method has perfect forward (backward) security iff the method has t-forward (t-backward) security for all t. Backward security is optional. When a new member is added, the group manager may choose to create a new group key, thus denying the new member access to the old key and hence previous traffic. We seek methods, such as OFT, that provide perfect forward security, with the option of perfect backward security. Carefully note our definitions of the phrases "perfect forward security" and "perfect backward security." Our use of these convenient phrases should not be confused with the different requirement, as explained by Menezes et al. [Men97, p. 496], that compromise of long-term keys does not reveal past session keys. Similarly, our use of these phrases does not necessarily imply information-theoretic "perfectly-secure key distribution" in the sense used by Blundo et al. [Blu92]. Two additional valuable security measures are degree of traceability and degree of disclosure amplification. A method is t-traceable iff more than t colluding members are required to leak plaintext or session keys without being identified if leaked material is discovered. Disclosure amplification refers to the extent of unauthorized disclosure of internal state information (e.g. subgroup keys) caused by the unauthorized disclosure of certain other internal state information. In addition, when specifying security requirements for particular applications, it is important to understand the security needs and assumptions with regard to any underlying cryptographic primitives (e.g. one-way functions) and with regard to fundamental types of cryptographic strength (e.g. information theoretic, computational, quantum uncertainty). 4. One-Way Function Trees A One-Way Function Tree (OFT) is a binary tree, each node x of which is associated with two cryptographic keys: a node key k_x and a blinded node key k'_x = g(k_x). The blinded node key is computed from the node key using a one-way function g; it is blinded in the sense that a computationally limited adversary cannot find k_x from k'_x. Although the concept of a one-way function tree is not new (e.g. in 1979, Merkle [Mer79] proposed an authentication system based on a similar idea), our application of this concept is novel. Balenson, McGrew, Sherman expires February 25, 2001 [Page 08] INTERNET-DRAFT August 25, 2000 4.1 Structure of an OFT A group manager maintains a one-way function tree. Each leaf is associated with a member of the group. The manager uses a symmetric encryption function E to communicate securely with subsets of group members, using unblinded keys as encryption keys as explained below. A randomly-chosen key is assigned to each member. This key is shared with the manager (via an external secure channel), and the key is assigned as the node key of the member's leaf. A variety of choices are possible governing who chooses the keys. In particular, the key could be chosen by the manager, member, or a combination thereof (see Section 4.3). 4.1.1 The Original OFT Structure Each internal node of the tree has exactly two children. The interior node keys are defined by the rule: k_x = f( g(k_left(x)), g(k_right(x)) ), (1) where left(x) and right(x) denotes the left and right child of the node x, respectively. The function g is one-way, and the function f is a "mixing" function (e.g. XOR). The node key associated with the root of the tree is the group key, which the group can use to communicate with privacy among group members and/or authentication of group membership. The security of the system depends on the fact that each member's knowledge about the current state of the key tree is limited by the following invariant: OFT Security Invariant - each member knows the unblinded node keys on the path from its node to the root, and the blinded node keys that are siblings to its path to the root, and no other blinded or unblinded keys. This invariant is maintained by all operations that add members to the group, and by all operations that delete members from the group. See Figure 1. Balenson, McGrew, Sherman expires February 25, 2001 [Page 09] INTERNET-DRAFT August 25, 2000 +----------@----------+ | | +-----@-----+ +-----#-----+ | | | | +--#--+ +--@--+ * * | | | | * * # @ Figure 1: An example of an OFT key tree. The member at the leaf labeled M knows the keys of the nodes labeled @ (including the root key, which is used as the group key), and the blinded keys of the nodes labeled #. McGrew and Sherman [McG98] discuss the properties of f and g in detail and give some preliminary observations regarding the security of OFT. A rigorous proof of the necessary and sufficient properties of f and g needed to satisfy formal security requirements for OFT remains an open problem. In comparison with LKH, there is necessarily some loss in entropy of the group key in OFT and OFC as a result of the functional relationships among node keys. We estimate this loss in entropy to be very small (less than one bit for group sizes of 10 million). 4.1.2 An Improved OFT Structure Given the (claimed) provable security properties of Canetti's [Can99b] OFC algorithm, we believe that the security of OFT (at least in a provability sense) can be improved by adapting some of the detailed functional relationships of OFC to OFT. This Section briefly outlines how this technical modification to OFT would work and introduces new convenient terminology that can be used to describe the three hierarchical methods (LKH, OFT, OFC) in a common framework. Each node v in the key tree has a node secret x_v and a node key k_v. The group key is the node secret of the root, which is functionally related to the node secrets of the other nodes. The node keys are used only as encryption keys for broadcast communications from the manager. Let H be any length-doubling pseudorandom function, and let f || g = H, where || denotes concatenation. Thus, for any input y, f(y) is the left half of H(y), and g(y) is the right half. (These functions are separate from the f and g from Section 4.1.1.) Now, under suitable assumptions on H, we have that f and g are computationally independent, which fact facilitates security proofs. Let v be an interior node in the key tree, and let L and R be, respectively, the left- and right- children of v. In both OFT and Balenson, McGrew, Sherman expires February 25, 2001 [Page 10] INTERNET-DRAFT August 25, 2000 OFC, we have that k_v = g(x_v) (similarly, k_L = g(x_L) and k_R = g(x_R)). In OFT, the node secret for v is computed as follows: x_v = f(x_L) XOR f(x_R), (2) where XOR denotes bitwise exclusive-or. By contrast, in OFC, if the edge (x_L, x_v) lay on the current chain, then it would be true that x_v = f(x_L). A typical manager broadcast in OFT would include a component such as E(k_R, f(x_L)). With the improved OFT structure, in the foregoing broadcast component we have that k_R and f(x_L) are computationally independent. 4.2 Algorithms The operations of adding and evicting members rely on the communication of new blinded key values, from the manager to all members, after the node key associated with a leaf has changed. To maintain security, each blinded node key must be communicated only to the appropriate subset of members. If the blinded key k'_x changes, then its new value must be communicated to all of the members who store it. These members are associated with the descendants of the sibling of x, and they know the unblinded node key k_s, where s is the sibling of x. To provide the new value of the blinded key to the appropriate set of members, and keeping it from other members, the manager encrypts k'_x with k_s before broadcasting it to the group. (Here and throughout, we shall use the verb "broadcast" in the sense of "group broadcast" -- sending a message from the group manager to all members of the group.) Because the utility of OFT is not restricted to multicast environments, throughout we sometimes refer to "unicast" transmissions, as for example to implement the add-member operation. In typical multicast environments, where no unicast is possible, such unicast messages would be sent as multicasts. 4.2.1 Adding a member As shown in Figure 2, when a new member joins the group, an existing leaf node x is split, creating new nodes left(x) and right(x). The member associated with x becomes associated with left(x), and the new member is associated with right(x). Both members are given new keys. The old member gets a new key because their former sibling knows the old blinded node key and could use this information in collusion with another group member to find an unblinded key that is not on his path to the root. The new values of the blinded node keys that have changed are broadcast securely to the appropriate subgroups, as described in the previous paragraph. The number of blinded keys that must be broadcast to the group is equal to the distance from x to the root plus two. In addition, in a unicast transmission (see last paragraph of Section 4.2), the new member is Balenson, McGrew, Sherman expires February 25, 2001 [Page 11] INTERNET-DRAFT August 25, 2000 given their set of blinded node keys, using the external secure channel. In order to keep the height h of the tree as low as possible, when a new member is added, the leaf closest to the root is split. before after +---------+---------+ +---------@---------+ | | | | +----+----+ +----+----+ +----@----+ +----#----+ | | | | | | | | +--+--+ * * * +--#--+ +--@--+ * * | | X | | | | * * * * # @ X New Figure 2: Inserting a new member into an OFT key tree. Via a unicast, the newly added member (New) is informed of the blinded keys of the nodes labeled # and of the unblinded keys of nodes labeled @. Via a multicast, the other members who need to know are informed of the blinded keys at nodes labeled @. 4.2.2 Evicting a member As shown in Figure 3, when the member associated with a leaf y is evicted from the group, the member assigned to the sibling of y is reassigned to the parent p of y and given a new leaf key value. If the sibling s of y is the root of a subtree, then p becomes s, moving the subtree closer to the root. In this case, one of the leaves of this subtree is given a new key (so that the evictee no longer knows the blinded key associated with the root of the subtree). The new values of the blinded node keys that have changed are broadcast securely to the appropriate subgroups. The number of keys that must be broadcast is equal to the distance from y to the root. before after +---------+---------+ +---------@---------+ | | | | +----+----+ +----+----+ +----@----+ +----+----+ | | | | | | | | +--+--+ +--*--+ * * +--+--+ @ * * | | | | | | X * * * * * * X M Figure 3: Evicting a member from an OFT key tree. When member M is evicted, M's sibling X is assigned a new key, which in turn alters the keys at nodes labeled @. Via a multicast, the other members who need to know are informed of the new blinded keys at nodes labeled @. Balenson, McGrew, Sherman expires February 25, 2001 [Page 12] INTERNET-DRAFT August 25, 2000 4.2.3 Initialization Group initialization is the process through which the group establishes an initial group communications key. For our OFT method, this process involves two steps. First, the group manager broadcasts some information to the group members needed to apply the OFT key-updating procedures. Second, the members compute a shared group communications key, which is needed to begin secure group communications. Group initialization is separate from group induction, which is explained in Section 6. During group induction, each member establishes an individual group base key known only by the member and the group manager. Group initialization assumes that each member has already established an individual group base key. In the first step of OFT group initialization, the manager broadcasts every blinded node key in the OFT to all group members. In this broadcast, each blinded node key is encrypted by the unblinded key of the sibling node, so that only members in the sibling subtree can learn the blinded node key. All members receive the entire broadcast, which consists of a sequence of encrypted blinded node keys. As discussed in Section 5, there are some implementation choices that need to be made concerning how members parse broadcast messages to extract the information they need. In particular, each member needs to associate nodes in the key tree with new node keys communicated from the group manager as encrypted parts of broadcast messages. One solution is to rely on the order in which the keys are broadcast--for example, a postorder traversal of the OFT. In many applications, however, it may be preferable (redundantly) to include node numbers in such broadcast messages, as we did in our prototype. 4.3 Properties In this section we comment briefly on the security, resource usage, and salient characteristic features of The OFT method. For more details, see the paper by McGrew and Sherman [McG98]. The security properties of OFT stem from the system invariant stated in Section 4.1, from the strength of the component one-way function, and from the random selection of leaf keys. In short, OFT provides perfect forward security and optional perfect backward security. Thus, arbitrary coalitions of evicted members cannot directly compute the group communications key nor any unblinded node key. Evicted members have some information about the key tree but not enough to compute directly any unblinded node key. After a member is evicted, the keys along the path from the member's node to the root change. After this change, the evictee knows only the blinded keys of the siblings of the nodes along the path from the evictee to the root. These blinded nodes are insufficient to compute directly any unblinded key. Balenson, McGrew, Sherman expires February 25, 2001 [Page 13] INTERNET-DRAFT August 25, 2000 Interestingly, OFT is a centralized, member-contributory method. OFT is centralized in the sense that the group manager plays a special trusted role. OFT is member contributory in the sense that each leaf can contribute entropy to the group communication key. The hierarchical nature of OFT distributes the computational costs of re- keying among the entire group, so that the managers computational burden is comparable to that of a group member. Table 1 below summarizes the salient resource usage of adding or deleting a member with OFT in terms of time, memory, number of bits broadcast, and number of random bits needed. Resource Measure Group Member Cost Group Manager Cost Time h h Memory hK 2nK Bits broadcast 0 hK + h Random bits generated 0 K Table 1: Summary of resource usage of adding or deleting a member with OFT. Here, n is the group size, K is the size of a key in bits, and h is the height of the OFT (h = lg n when the tree is balanced). Either the member or the manager could generate the random bits needed at the leaves. 4.4 Enhanced OFT+ and LKH+ Algorithms As suggested in an observation attributed to Radia Perlman, the add-member operation in LKH can be significantly improved to run in constant time. The method is to compute the new group communications key by applying a one-way function to the current group communications key; to unicast the group key to the new member; and to broadcast that this update has been done. We shall refer to this refinement of LKH, which maintains perfect backward security, as LKH+. Unfortunately, this refinement does not apply to the delete-member operation. Fortunately, in many applications, add-member is performed much more frequently than is evict-member. Independently of Perlman, V. Viswanathan [Vis96, pp. 25-26] also suggested a similar constant-time member-parallel add-member idea. A similar refinement is also possible for OFT, which we shall call OFT+. For both LKH+ and OFT+, the add-member operation advances the group communications key and marks (i.e. places on a list) the specified member to be added at the next full re-key (e.g. typically at the next evict-member operation). Thus, the work of adding new Balenson, McGrew, Sherman expires February 25, 2001 [Page 14] INTERNET-DRAFT August 25, 2000 members is deferred until the next re-key. Two savings, however, are possible. First, there is an economy of scale when adding multiple members, especially when the new members will be placed compactly in the same section of the key tree. Second, a newly added member might be evicted before the next re-key. The cost of the deferred add-member operations is given by the size of the so-called CAT (Common Ancestor Tree) of the members (see [McG98, Sections 3.3 and 5.3]). In practice, the cost of adding R new members at once (assuming they will be placed compactly in the same section of the tree) is approximately 2R + lg (n/R), where n is the number of nodes in the key tree. 4.5 Comparisons with Other Leading Key-Establishment Methods In this section we briefly compare our OFT algorithm against the two leading competing algorithms for establishing keys in large dynamic groups: the Logical Key Hierarchy (LKH)[Harn99b, Wal97], and the Single Key Distribution Center (SKDC). As reviewed in Section 2, these two algorithms and OFT are the main choices available to system engineers who do not wish to trust network routers in large group applications. OFT and LKH are appealing because their computation, broadcast, and memory requirements scale logarithmically with group size. The enhanced algorithms LKH+ and OFT+ (described in Section 4.4) are especially appealing for their constant-time add-member operations. Despite its linear complexity, SKDC is appealing for its simplicity. 4.5.1 Comparison Criteria The choice of which key-establishment algorithm should be used can be answered meaningfully only in the context of the requirements of particular applications. To assist engineers in making their choices, we shall summarize some of the major properties of SDKC, LHK, LKH+, OFT, and OFT+ in terms of selected quantitative comparison criteria. These criteria include total delay, number of bits broadcast, number of bits unicast, manager computation, maximum member computation, number of random bits generated, and manager and member memory requirements. Each of these methods provides perfect forward security with the option of perfect backward security. The five leading candidate methods differ also in terms of required primitives, security semantics, central versus contributory flavor, and resynchronization capabilities (for dealing with group members who temporarily are unable to receive manager broadcasts). For example, SDKC and LKH require encryption functions; LKH+ and OFT require encryption functions and one-way functions. Although none of the authors of any of these methods has provided a formal proof of security, some engineers may have greater confidence in the security of methods with simpler security semantics. Listed in increasing complexity of security semantics, the methods are: SDKC, LKH, LKH+, OFT, OFT+. With regard to the source of entropy of random bits in Balenson, McGrew, Sherman expires February 25, 2001 [Page 15] INTERNET-DRAFT August 25, 2000 common group communication keys, SDKC, LKH, and LKH+ may be viewed as member non-contributory methods because the group manager provides all of the entropy. By contrast, OFT and OFT+ can be used in either a member non-contributory or member-contributory fashion. Most applications have a need to provide a resynchronization capability; some methods may provide some degree of passive member-synchronization. When asked why she based her LKH method on a keyed encryption function rather than on a faster keyless one-way function (as used in OFT), Wallner [private communication (11/19/97)] explained that her motivating application was a radio communication system. In this application, the available hardware supported a keyed encryption function but not a keyless one-way function. Wallner also remarked (without connection to the choice of encryption function versus one-way function), that in her application, it was very important to conserve battery power. Although these considerations were important to her application, other applications might have different requirements or available primitives; thus the rationale for Wallner's choices do not necessarily apply to other applications. 4.5.2 Quantitative Comparison of SKDC, LKH, LKH+, OFT, and OFT+ Tables 2 and 3 summarize the time, broadcast, and space requirements of each of the five leading candidate algorithms (SKDC, LKH, LKH+, and OFT). Specifically, for each algorithm and for each of the initialize, add- member, evict-member operations, Table 2 summarizes the total delay, number of bits broadcast, number of bits unicast, manager time, maximum member time, and number of random bits generated. Table 3 summarizes the manager and member memory requirements. For more details, see McGrew and Sherman [McG98]. In typical multicast environments, where no unicast is possible, the add-member unicast messages of LKH+, OFT, and OFT+ would be sent as multicasts. 4.5.3 Summary For moderate size groups, the simple SKDC may often be appealing. For very large groups, however, many applications will likely demand a method that scales logarithmically in total delay and member memory usage. For such applications, especially if the add-member is more frequent than the evict-member operation, the OFT+ and LKH+ methods look very attractive for their constant-time add-member. LKH+ and OFT+ are similar algorithms, with LKH+ offering relatively simpler security semantics, and with OFT+ requiring fewer bits to transmit for re-keying. If for the application it is critical to minimize the number of bits broadcast or the number of random bits generated, or if a member-contributory method is needed, then OFT+ may be the method of choice. Balenson, McGrew, Sherman expires February 25, 2001 [Page 16] INTERNET-DRAFT August 25, 2000 Initialization RESOURCE MEASURE SKDC LKH LKH+ OFT OFT+ Total delay n 2n 2n 3n 3n Number of bits broadcast nK 2nK+h 2nK+h 2nK+h 2nK+h Number of bits unicast 0 0 0 0 0 Manager computation n 2n 2n 3n 3n Max member computation 1 h h 2h 2h No. of random bits generated K 2nK 2nK nK nK Add member RESOURCE MEASURE SKDC LKH LKH+ OFT OFT+ Total delay n 2h 1 3h 1 Number of bits broadcast nK 2hK+h h hK+h h Number of bits unicast 0 0 K hK K Manager computation n 2h 1 3h 1 Max member computation 1 h 1 2h 1 No. of random bits generated K hK 0 K 0 Evict member* RESOURCE MEASURE SKDC LKH LKH+ OFT OFT+ Total delay n 2h 2h 3h 3h Number of bits broadcast nK+h 2hK+h 2hK+h hK+h hK+h Number of bits unicast 0 0 0 0 0 Manager computation n 2h 2h 3h 3h Max member computation 1 h h 2h 2h No. of random bits generated K hK hK K K (* For LKH+ and OFT+, if R add-member actions have been deferred, then the evict-member operation will additionally broadcast [2R + lg(n/R)]K bits. See Section 4.4.) Table 2: Summary of time and communication usage of initialization, add-member, and evict-member with the SKDC, LKH, LKH+, OFT, and OFT+ key-establishment methods. Here, n is the group size, K is the size of a key in bits, and h is the height of the key tree (h = lg n when the tree is balanced). Note that while LKH and LKH+ have lower magnitudes of total delay, the units of time for OFT are typically much smaller because keyless one-way functions are much faster than are keyed-encryption functions. Memory Usage RESOURCE MEASURE SKDC LKH LKH+ OFT OFT+ Manager storage nK 2nK 2nK 2nK 2nK Max member storage 2K hK hK hK hK Table 3: Summary of manager and member memory usage in the SKDC, LKH, LKH+, OFT, and OFT+ Key-establishment methods. Here, n is the group size, K is the size of a key in bits, and h is the height of the key tree (h = lg n when the tree is balanced). Balenson, McGrew, Sherman expires February 25, 2001 [Page 17] INTERNET-DRAFT August 25, 2000 5. Design Choices, Implementation Issues, and Experience In this section we identify important engineering decisions that must be addressed in the implementation of the OFT algorithm. We also discuss some of the lessons learned from our prototype implementation. 5.1 Design Choices Several important engineering decisions must be made in the implementation of the OFT algorithm: the choice of f and g, the format of broadcasts by the manager, the representation of the tree, and time-space tradeoffs by each member involving how many unblinded ancestor keys to store. The function g can be based on a cryptographic hash function such as MD5 [Riv92] or SHA-1 [Sha-1]. It is possible that the node keys do not need to be as large as the output size of the underlying function. For example, MD5 has a sixteen-byte output, while DES keys are only seven bytes long. The function g can be constructed from MD5 by discarding some of the output, as is done by S/KEY, so that the node keys (and thus the broadcasts) are smaller. The function f does not need to be one-way; it needs only to mix its inputs. This fact suggests that f(x,y) = x XOR y is a fast, simple, and effective choice (XOR denotes the bitwise exclusive-or function). Of course, the functions f and g must not interact pathologically so as, for example, to undo g. The representation of the tree and the formats of the messages from the group manager are important engineering decisions. For example, the tree could be represented as a record and pointer structure, or as a linear array. We recommend that message formats for messages broadcast from the manager explicitly include node number information to identify which parts of a message correspond to which subtrees. 5.2 Implementation Issues and Experience The NAI prototype implementation of the OFT+ algorithm was carried out in 1999, for the DCCM OFT Toolkit. The purpose of this Java implementation is to demonstrate proof of concept and to gain insight into implementation issues. The prototype uses the following parameter choices: the key size is 128 bits; f is XOR; and g is SHA-1 with 160 bits of output. For simplicity, and to avoid ever having to change a member's node number in the key tree, the prototype uses the following alternate implementation of OFT operations: the key tree is constructed with all leaves always on the lowest level. Thus, initially, the key tree is allocated for a certain maximum size. To grow beyond this size, the tree could be doubled in size by inexpensively making the current Balenson, McGrew, Sherman expires February 25, 2001 [Page 18] INTERNET-DRAFT August 25, 2000 tree the left subtree of a new tree and broadcasting the new root node number. The NAI prototype raised three important implementation issues: adapting messaging for unreliable communications, node numbering, and node storage explosion. To implement the OFT algorithm in the multicast environment for which it was intended requires some messaging adaptations. The finite maximum transmission unit in this connectionless environment requires that messages be sent in packets. UDP packets can arrive out of order or fail to arrive. All messages need to be protected for confidentiality, integrity, and authentication. The prototype protects its internal messages using the Blowfish encryption and with SHA-1-based integrity and authentication checks. As an example of a messaging implementation detail, note that to encrypt a 160-bit SHA-1 output with a 128-bit block cipher requires some type of chunking. The prototype applies the Blowfish algorithm in ECB mode with no padding to 128-bit data blocks. These blocks are protected using the standard authentication and integrity mechanisms for all OFT messages; alternatively, one might use some type of block chaining (e.g. CBC mode). During the course of OFT operations, it is necessary to be able to refer to members by their names and to refer to key tree nodes by their topological positions. Also, it is necessary to be able to map between member names and their associated nodes. To this end it is convenient to maintain node numbers. Moreover, since there is no efficient reliable way to inform members of any changes in their node numbers, it is especially convenient if the node numbers never change. For these reasons, in the prototype, member names are equated with node numbers, and node numbers never change. Because OFT is intended for very large groups, the amount of storage allocated per node in the key tree significantly affects the total amount of memory used. We refer to this issue as the node storage explosion. Care must be taken not to squander memory on elaborate node structures. For example, on space considerations alone, the tree-balancing strategies of Moyer et al. [Moy99] are unlikely to be wise engineering choices for today's technology. In addition, the following two lessons were learned. First, it is important but nontrivial for a member to verify when it has the correct group key. A member might compute the wrong group key for two reasons: The member might never receive some key-update messages. Also, in a sequence of key-update messages, the member might not have any way of knowing that additional key-update messages are yet to come. These situations are complicated by the unreliable nature of the multicast environment. We view these key-synchronization issues as orthogonal to OFT; that is, these issues exist in many communications systems for a variety of reasons Balenson, McGrew, Sherman expires February 25, 2001 [Page 19] INTERNET-DRAFT August 25, 2000 and should be solved as part of the standard key management service. For example, one solution is to attach confidential key checksums to keying data, which is what the prototype does. Another solution, which the prototype also uses, is to allow members to send resynchronization request messages to the group manager. Second, it is important that the components be appropriately matched and coordinated. For example, inefficiencies can arise if the keysize is not a multiple of the blocksize of the encryption function used for confidentiality. Currently, the prototype has handled groups of up to 100,000 members on a Pentium with 64 MB of RAM, with adjustments to the swap space. The maximum possible group is limited by two factors: the size of the initial message, and the node storage explosion. 6. Amortized Group Induction Before a group can establish an initial group communications key, the members must be inducted (enrolled) into the group. For centralized key establishment methods including OFT, an important objective of this induction step is for each member to establish an individual base key known only to the member and the group manager. The induction process also ensures that each member has the necessary certificates to take advantage of the supporting authentication infrastructure. The main computational goal of induction is to minimize its total delay. For each group member to establish a separate base key with the Group Manager, the simplest approach is for the manager to engage each member in a separate pairwise authenticated key exchange protocol, such as the Internet Key Exchange (IKE) protocol [Hark98b, Mau98, Orm]. Unfortunately, this simple approach scales linearly in group size. In this section we describe a new approach to group induction due to Sherman [She98, Bal98b] that amortizes the relatively high cost of a pairwise key exchange over multiple entries into groups. This amortization saves time when many users become members of two or more groups. We call this new approach "amortized induction." An IBM team [Blu97] independently discovered a similar idea in a network context. 6.1 Induction Model Assume there is a universe of N individuals from which G groups are formed, each group having at most n members. Assume further that N is much smaller than Gn; that is, many individuals belong to several groups. It is for this reasonable assumption that amortized induction offers significant savings. Balenson, McGrew, Sherman expires February 25, 2001 [Page 20] INTERNET-DRAFT August 25, 2000 We assume that there is a system that administers multiple groups, each of whose group communications key is established by a key-establishment algorithm such as OFT. Each participant may join one or more group. Each group has a group manager, and there is a system manager who controls induction into the system. For simplicity we shall describe the induction process in terms of a single system manager, though the concept of system manager can be extended to a more general system management function which might be distributed. For each group, each member must establish an individual base key known only to the member and the group manager. Amortized induction reduces the number of expensive pairwise key exchanges from Gn to N, which can be a significant savings. Amortized induction comes at the cost of Gn one-way function applications by the system manager, but these function evaluations are much faster than pairwise key exchanges. For example, a single application of the MD5 hash function is approximately 1000 times faster than a single ISAKMP/OAKLEY key exchange. 6.2 Induction Algorithm Whenever an individual first enters the system, the member establishes an individual system base key known only to the individual and the system manager. For example, this step could be carried out using the IKE Key-Exchange Protocol. Thereafter, whenever the individual joins a group, the individual can establish an individual group base key with the group manager as a one-way function of the individual's system base key, the individual's name, and the group name. More specifically, let A be the group name. For each member M, the group base key KA_M for M is computed as a one-way function F of M's system base key K_M, the name of M, and the group name. For example, KA_M = F( K_M, M, A ), (2) where F is a publicly known one-way function such as the hash function MD5. The total member delay in this computation is constant. The function F must satisfy the following properties: it must be easy to compute given its three inputs, and it must be infeasible for anyone to compute the output given only the last two inputs (even under an adaptive chosen plaintext/ciphertext attack). Whenever a group manager is appointed, the group manager establishes a manager key k_A known only to the group manager and the system manager. For added security this key establishment could be carried out using the same pairwise key-exchange protocol used in the induction process; alternatively, it would be possible to compute manager keys along the lines of Equation 2. Balenson, McGrew, Sherman expires February 25, 2001 [Page 21] INTERNET-DRAFT August 25, 2000 Whenever members of a group need to be inducted, the system manager computes the group base keys and unicasts them to the group manager, encrypted under the manager key k_A. The length of this unicast is linear in the group size. Note that, unlike the SKDC method, no group broadcast is required. Members of different groups can be inducted in parallel. 6.3 An Example of Induction To illustrate the amortized induction process, consider a toy example in which there are three individuals Q, R, S and two groups A = {Q, R} and B = {S}. When Member Q is inducted into the system, he establishes a base system key K_Q known only to Q and the system manager. Similarly, Members R and S establish base system keys K_R and K_S, respectively. At the appointment of Group Manager A, Manager A establishes a manager key k_A known only to Manager A and to the system manager. Similarly, Group Manager B shares a manager key k_B with the system manager. To induct members of Group A, the system manager computes the group base keys KA_Q, and KA_R for Members Q and R, respectively, and sends them to Manager A encrypted under manager key k_A. For example, KA_Q = f(K_Q, Q, A) and KA_R = f(K_R,R,A). In parallel, Members Q and R each computes his own group base key. Members of Group B are similarly inducted. 7. Conclusion and Open Problems We have presented and analyzed a new practical hierarchical algorithm for establishing shared cryptographic keys for large, dynamically-changing groups. Our algorithm is based on a novel application of One-way Function Trees (OFTs). Unlike previously proposed solutions based on information theory, public-key cryptography, hybrid approaches, or a single key distribution center, our OFT algorithm has communication, computation, and storage requirements, which scale logarithmically with group size, for the add or evict operation. Each of the aforementioned methods typically scales linearly or worse (see Section 2.1). In comparison with the first proposed hierarchical method that does not depend on trusted routers -- the Logical Key Hierarchy (LKH) -- our OFT algorithm reduces by approximately half the number of bits broadcast by the manager per add or evict operation. By contrast, LKH has relatively simpler security semantics than does OFT. The user time and space requirements of OFT and LKH are roughly comparable. For many applications, including multicasts, minimizing broadcast size is especially important. Balenson, McGrew, Sherman expires February 25, 2001 [Page 22] INTERNET-DRAFT August 25, 2000 The One-Way Function Chain (OFC) variation of OFT recently due to Canetti, et al. [Can99b] is a very attractive proposal for its simplicity, broadcast size (similar to OFT), and provable security. The exact savings in broadcast size of OFT over LKH depends on the parameter choices in the OFT and LKH implementations, including the key lengths and the output sizes of the one-way function, encryption function, and mixing function. If the one-way function expands its input more than does the encryption function, then the savings in broadcast size will be less than a factor of two. For example, using 128-bit group keys and the 160-bit SHA-1 one-way function, our prototype OFT achieves a savings in broadcast size over LKH of (2 x 128) / 160 = 1.6, which is slightly less than two. Although a reduction in broadcast size of one half may seem relatively small, we conjecture that the performance of the LKH algorithm may be approaching theoretical limits and therefore only relatively small improvements may be possible. Canetti et al. [Can99] give some evidence supporting this conjecture by proving upper and lower bounds with gap of at most O(b) = O(lg n), where b is a parameter (see Section 2.1). Refinements to the OFT and LKH methods which we call OFT+ and LKH+ (see Section 4.4), offer significant performance improvements. Specifically, in OFT+ and LKH+, the cost of the add-member operation one one-way function application, a unicast of one key, and one short broadcast. There is also a deferred cost for the next re-key operation. These improvement to OFT and LKH make OFT+ and LKH+ attractive choices for many applications. It is possible to implement the OFT algorithm with k-ary trees, as studied in LKH by Canetti et al. [Can99]. The optimal choice of k depends on what cost metric is to be minimized. The choice k = 2 minimizes broadcast size for single member eviction. By contrast, to minimize total manager computation, Wong et al. [Won98] show experimentally that k = 4 is best in LKH. We suspect that a similar result may also hold for OFT. McGrew and Sherman [McG98] discuss and analyze savings that are possible by separately batching multiple add or multiple evict operations. Similar and possibly even greater savings may be possible by batching adds and evicts together, as also suggested by Yang (personal correspondence 6/22/99). The OFT method is a centralized algorithm with the option of member contributions to the entropy of the common communications key. Its main advantages are that, in comparison with LKH+, it reduces by a factor of two the number of bits required to be broadcast for each evict-member operation. It is also the only proposed scalable member-contributory method. Our preliminary security analysis of OFT [McG98] raises some Balenson, McGrew, Sherman expires February 25, 2001 [Page 23] INTERNET-DRAFT August 25, 2000 interesting questions about the security of function iterates, and that of bottom-up one-way function trees. Formally proving the security of key-establishment algorithms is a difficult problem, even in the two-party case (e.g. see Bellare and Rogaway [Bel93]). It is important to realize that there are significant fundamental limitations to achieving security in large groups -- one might even say that a secure large group is an oxymoron. In most large groups, it is very likely that at least one member is unreliable, untrustworthy, malicious, or careless. Each member knows the common communications key and the plaintext, which is the main commodity being protected. Using multiple communications keys for different subgroups would not enhance security since each member would still have the plaintext. Any member could disclose the plaintext. Consequently, in large groups, it becomes especially important to detect traitors (e.g. through fingerprints and watermarks [Kur98, Sta97, Cho94]) and to limit the loss caused by disclosures (e.g. by rapid evictions and re-keying). Special-purpose, physically secure hardware may play a role in these objectives, by restricting access to communication keys, complicating effective use of compromised keys, and providing unique fingerprints. Our OFT algorithm offers a practical approach with low broadcast size to manage the demanding key establishment requirements of secure applications for large, dynamic groups. 8. Security Considerations This document proposes a new algorithm for securely establishing a shared, secret group communications key in a large, dynamic group. Sections 3.2, 4.1, and 4.3 describe the security properties of this algorithm. 9. References [Ate98] Ateniese, Giuseppe, Michael Steiner, and Gene Tsudik, "Authentication group key agreement and friends" in Proceedings of the 5th Conference on Computer & Communications Security, ACM Press (1998), 17-26. [Bag99] Bagnall, P., R. Briscoe, and A. Poppitt, "Taxonomy of communication requirements for large-scale multicast applications," Internet Draft (work in progress), draft-ietf-lsma-requirements-03. txt, Internet Engineering Task Force (May 14, 1999). 25 pages. [Bal95] Ballardie, Tony, and Jon Crowcroft, "Multicast-specific threats and counter-measures," Proceedings of the Internet Society 1995 Symposium on Network and Distributed System Security, February 16-17, 1995, San Diego, California, IEEE Computer Society (1995), 2-14. Balenson, McGrew, Sherman expires February 25, 2001 [Page 24] INTERNET-DRAFT August 25, 2000 [Bal96] Ballardie, A., "Scalable multicast key distribution," Request for Comments (RFC) 1949, Internet Engineering Task Force (May 1996), 18 pages. [Bal97] Ballardie, A. "Core based tree (CBT) multicast routing architecture," Request for Comments (RFC) 2201, Internet Engineering Task Force (September 1997), 14 pages. [Bal98] Balenson, David M., Dennis K. Branstad, David A. McGrew, and Alan T. Sherman, "Dynamic cryptographic context management (DCCM): Report #1: Architecture and system design," TIS Report No. 0709, TIS Labs at Network Associates, Inc., Glenwood, MD (June 2, 1998). 121 pages. [Bal98b] Balenson, David M., David A. McGrew, and Alan T. Sherman, "Key management for large dynamic groups: One-way function trees and amortized initialization," Advanced Security Research Journal - NAI Labs, Vol. 1, No. 1 (fall 1998), 27-46. [Bel93] Bellare, Mihir, and Phillip Rogaway, "Entity authentication and key distribution," Advances in Cryptology: Proceedings of Crypto 93, Douglas R. Stinson, ed., LNCS 773, Springer-Verlag (1993), 232-249. [Ber91] Berkovitz, S., "How to broadcast a secret," Advances in Cryptology: Proceedings of Crypto 91, Feigenbaum, ed,. LNCS 576, Springer-Verlag (1991), 535-541. [Blo90] Bloom, Joel, ed., X9.24-1990, "Financial services retail key management," ANSI X9A3 (March 1990). 84 pages. [Blu92] Blundo, Carlo, Alfred de Santis, Amir Herzberg, Shay Kutten, Ugo Vaccaro, and Moti Yung, "Perfectly-secure key distribution for dynamic conferences," Advances in Cryptology: Proceedings of Crypto92, E. F. Brickell, ed., LNCS 740, Springer-Verlag (1992), 471-486. [Blu97] Blumenthal, Uri, Nguyen C. Hien, and Bert Wijnen, "Key derivation for network management applications," IEEE Network (May/June 1997), 26-29. [Bur94] Burmester, Mike, and Yvo Desmedt, "A secure and efficient conference key distribution system," Advances in Cryptology: Proceedings of Eurocrypt 94, A. De Santis, ed., LNCS 950, Springer-Verlag (1994), 275-286. [Bur97] Burmester, Mike, and Yvo G. Desmedt, "Efficient and secure conference key distribution," Secure Protocols, M. Lomas, Ed., LNCS 1189, Springer-Verlag (1997), 119-130. [Revised and expanded version of the corresponding Eurocrypt 94 paper by the same authors.] Balenson, McGrew, Sherman expires February 25, 2001 [Page 25] INTERNET-DRAFT August 25, 2000 [Can98] Canetti, R. and B. Pinkas, "A taxonomy of multicast security issues," Internet Draft (work in progress), draft-canetti-secure-multicast-taxonomy-00.txt, Internet Engineering Task Force (May 1998). 13 pages. [Can99] Canetti, Ran, Tal Malkin, and Kobbi Nissim, "Efficient communication-storage tradeoffs for multicast encryption" in Advances in Cryptology: Proceedings of Eurocrypt 99, Springer-Verlag (1999), 459-474. [Can99b] Canetti, R., Juan Garey, Gene Itkis, Daniele Micciancio, Moni Naor, and and B. Pinkas, "Multicast security: A taxonomy and efficient constructions," Infocom99 (1999), 20 pages. [Car98] Caronni, Germano, Marcel Waldvogel, Dan Sun, and Bernhard Plattner, "Efficient security for large and dynamic multicast groups" in Proceedings of the Seventh Workshop on Enabling Technologies (WET ICE 98), IEEE Computer Society Press (1998). 20 pages. http://skip.incog.com/wetice98/HacknSlash.htm [Chi89] Chiou, Guang-Huei, and Wen-Tsuen Chen, "Secure broadcasting using the secure lock," IEEE Transactions on Software Engineering, 15:8 (August 1989), 929-934. [Cho94] Chor, B., A. Fiat, and M. Naor, "Tracing traitors," Advances in Cryptology: Proceedings of Crypto 94, Y. G. Desmedt, Ed., LNCS 839, Springer Verlag (1994), 257-270. [Dee89] Deering, S., "Host Extensions for IP Multicasting," Request for Comments (RFC) 1112, Internet Engineering Task Force (August 1989). 17 pages. [Dee98] Deering, S., D. Estrin, D. Farinacci, M. Handley, A, Helmy, V. Jacobson, C. Liu, P. Sharma, D. Thaler, and L. Wei, "Protocol independent multicast-sparse mode (PIM-SM): Motivation and architecture," Internet Draft (work in progress), draft-ietf-idmr-pim-arch-05.txt, Internet Engineering Task Force (August 4, 1998). 26 pages. [Eas97] Eastlake, Donald E., 3rd, and Charles W. Kaufman, "Domain name system security extensions," Request for comments (RFC) 2065, Internet Engineering Task Force (January 1997). [Ell97] Ellison, C. M., "SPKI Requirements" (February 1997). [For latest version, see http://www.clark.net/pub/cme/html/spki.html] [Fen97] Fenner, W., "Internet group management protocol, version 2," Request for Comments (RFC) 2236, Internet Engineering Task Force (November 1997). 24 pages. Balenson, McGrew, Sherman expires February 25, 2001 [Page 26] INTERNET-DRAFT August 25, 2000 [Fia93] Fiat, Amos, and Moni Naor, "Broadcast encryption," Advances in Cryptology: Proceedings of Crypto93, D. R. Stinson, ed., LNCS 773, Springer-Verlag (1993), 481-491. [Gon89] Gong, Li, and David J. Wheeler F. R. S., "A matrix key distribution scheme," Journal of Cryptology, 2:1 (1990), 51-59. [Gon94] Gong, Li, and N. Shacham, "Elements of trusted multicasting," Proceedings of the IEEE International Conference on Network Protocols, Boston, Massachusetts (October 1994). [Gon96] Gong, Li, "Enclaves: Enabling secure collaboration over the internet," Proceedings of the Sixth USENIX Unix and Network Security Symposium, San Jose, California (July 1996), 149-159. [Hard97] Harding, Michael, David A. McGrew, and Alan T. Sherman, "A new key-management algorithm for large dynamic groups," transparencies from talk given by Alan Sherman at NSA (November 19, 1997). 8 pages. [Hark98a] Harkins, Dan, and Naganand Doraswamy, "A secure, scalable multicast key management protocol (MKMP)," Draft (work in progress), cisco Systems and Bay Networks (March 1998). 20 pages. [Hark98b] Harkins, D. and D. Carrel, "The Internet key exchange (IKE)," Internet Draft (work in progress), draft-ietf-ipsec-isakmp- oakley-08.txt, Internet Engineering Task Force (June 1998). [Harn97a] Harney, Hugh, Carl Muckenhirn, and Thomas Rivers, "Group key management protocol (GKMP) architecture," Request for Comments (RFC) 2094, Internet Engineering Task Force (July 1997). [Harn97b] Harney, Hugh, Carl Muckenhirn, and Thomas Rivers, "Group key management protocol (GKMP) specification," Request for Comments (RFC) 2093, Internet Engineering Task Force (July 1997). [Harn99a] Harney, Hugh, and Eric Harder, "Multicast security management protocol (MSMP): Requirements and policy," Draft (work in progress), draft-harney-sparta-msmp-sec-00.txt, SPARTA, Inc. (March 1999). 26 pages. [Harn99b] Harney, Hugh, and Eric Harder, "Logical Key Hierarchy Protocol," Internet Draft (work in progress), draft-harney-sparta-lkhp-sec-00.txt, Internet Engineering Task Force (March 1999). 22 pages. [Harn99c] Harney, Hugh, and Eric Harder, "Group Secure Association Key Management Protocol" Draft (work in progress), draft-harney-sparta-gsakmp-sec-00, SPARTA, Inc. (April 1999). 35 pages. Balenson, McGrew, Sherman expires February 25, 2001 [Page 27] INTERNET-DRAFT August 25, 2000 [Hay98] Hayden, Mark Garland, "The Ensemble system," Ph.D. Dissertation, Department of Computer Science, Cornell University (January 1998). 106 pages. [Hor] The Horus Project, http://simon.cs.cornell.edu/Info/Projects/HORUS/. [Jus94] Just, Michael K., "Methods of multi-party cryptographic key establishment," MS Thesis, School of Computer Science, Carleton University (August 9, 1994). 77 pages. [Ken81] Kent, Stephen T., "Security requirements and protocols for a broadcast scenario," IEEE Transactions on Communications (June 1981). [Keu96] Keung, S., and L. Gong, "Enclaves in Java: APIs and implementations," Technical Report SRI-CSL-96-07, SRI International, Menlo Park, California (July 1996). [Kru98] Kruus, Peter, "A survey of multicast security issues and architectures," Proceedings 21st National Information Systems Security Conference, October 5-8, 1998, Arlington, VA, 408-420. [Kum95] Kumar, Vinay, Mbone Interactive Multimedia on the Internet, New Riders Publishing (Indianapolis, IN, 1995). [Kur98] Kurosawa, Kaoru, and Yvo Desmedt, "Optimum traitor tracing and asymmetric schemes with arbiter," Draft (work in progress), spring 98). 13 pages. [Mau98] Maughan, Douglas, Mark Schertler, Mark Schneider, and Jeff Turner, "Internet security association and key management protocol (ISAKMP)," Internet Draft (work in progress), draft- ietf-ipsec-isakmp-10.txt, Internet Engineering Task Force (July 3, 1998). 86 pages. [McG98] McGrew, David A., and Alan T. Sherman, "Key establishment in large dynamic groups using one-way function trees," TIS Report No. 0755, TIS Labs at Network Associates, Inc., Glenwood, MD (May 1998). 13 pages. [A revised version of this paper has been conditionally accepted to appear in the IEEE Transactions on Software Engineering.] [Men97] Menezes, Alfred J., Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, Florida (1997). [Mer79] Merkle, Raph C., "Secrecy, authentication, and public-key cryptosystems," Technical Report No. 1979-1, Information Systems Laboratory, Stanford University, Palo Alto, CA (1979). Balenson, McGrew, Sherman expires February 25, 2001 [Page 28] INTERNET-DRAFT August 25, 2000 [Mit97] Mittra, Suvo, "Iolus: A framework for scalable secure multicasting," Proceedings of the ACM SIGCOMM '97, September 14- 18, 1997, Cannes, France. 11 pages. [Moy99] Moyer, M. J., J. R. Rao, and P. Rohatgi, "Maintaining Balanced Key Trees for Secure Multicast," Internet Draft (work in progress), draft-irtf-smug-key-tree-balance-00.txt, Internet Engineering Task Force (June 25, 1999). 16 pages. [Nac94] Naccache, David, David M'Raithi, Serge Vaudenay, and Dan Raphaeli, "Can D.S.A. be improved? Complexity trade-offs with the digital signature standard," Advances in Cryptology: Eurocrypt '94, Alfredo De Santis, Ed., LNCS 950, Springer-Verlag (1994), 77-85. [Orm] Orman, Hilarie K., "The OAKLEY key determination protocol," Internet Draft (work in progress), draft-ietf-ipsec-oakley- 02.txt, Internet Engineering Task Force. 48 pages. [Poo99] Poovendran, R., and J. S. Baras, "An information theoretic analysis of rooted-tree based secure multicast key distribution schemes" in Advances in Cryptology: Proceedings of Crypto 99, M. Wiener, ed., LNCS 1666, Springer-Verlag (1999), 624638. [Rei93] Reiter, Michael, Kenneth Birman, and Robert van Renesse, "A security architecture for fault-tolerant systems," Technical Report TR93-1354, Department of Computer Science, Cornell University (June 1993). 29 pages. [Rei94] Reiter, Michael K, "A secure group membership protocol," Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy, Oakland, California, May 14-16, 1994, IEEE Press (1994). [Riv92] Rivest, Ronald L., The MD5 Message-Digest Algorithm, Request for Comments (RFC) 1321, Internet Engineering Task Force (1992). [Riv96] Rivest, Ronald L., and Butler Lampson, "SDSI: A simple distributed security infrastructure," Version 1.1 (October 2, 1996). [Rod97] Rodeh, Ohad, Ken Birman, and Mark Hayden, "Dynamic virtual private networks," Technical Report TR97-1654, Department of Computer Science, Cornell University (November 26, 1997). 16 pages. [Sch96] Schneier, Bruce, Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons (New York, 1996). [Sel00] Selcuk, A., C. McCubbin, and D. Sidhu, Probabilistic Optimization of LKH-Based Multicast Key Distribution Schemes, Internet Draft (work in progress), (January 2000), 10 pages. Balenson, McGrew, Sherman expires February 25, 2001 [Page 29] INTERNET-DRAFT August 25, 2000 [Sha-1] FIPS Publication 180-1, Secure hash standard, NIST, U.S. Department of Commerce, Washington, D.C. (April 1995). [She98] Sherman, Alan T., "A new amortized approach to group initialization: Refinements and analysis," TIS Report No. 0754, Trusted Information Systems, Inc. Glenwood, MD (March 26, 1998). 12 pages. [Sta97] Staddon, Jessica Nicola, "A combinatorial study of communication, storage and traceability in broadcast encryption systems," PhD Dissertation, Dept. of Mathematics, Univ. of California, Berkeley, CA (September 1997). 43 pages. [Ste96] Steiner, Michael, Gene Tsudik, and Michael Waidner, "Diffie-Hellman key distribution extended to group communication," Proceedings of the 3rd ACM Conference on Computer and Communications Security, March 14-16, 1996. 7 pages. [Ste97] Steiner, M., G. Tsudik, and M. Waidner, "CLIQUES: A new approach to group key agreement," IBM Research Report RZ 2984 (#93030) (December 12, 1997). 17 pages. [Sti96] Stinson, D. R., "On some methods for unconditionally secure distribution and broadcast encryption," unpublished document (November 21, 1996). 35 pages. [Vis96] Viswanathan, Vaidhyanathan, "Unconditionally secure dynamic conference key distribution," MS Thesis, University of Wisconsin- Milwaukee (December 1996). 28 pages. [Wal97] Wallner, Debby M., Eric J. Harder, and Ryan C. Agee, "Key management for multicast: Issues and architectures," Internet Draft (work in progress), draft-wallner-key-arch-01.txt, Internet Engineering Task Force (September 15, 1998). 18 pages. [Won97] Wong, Chung Kei, Mohamed G. Gouda, and Simon S. Lam "Secure group communications using key graphs," Technical Report TR-97-23, Dept. of Computer Science, Univ. of Texas at Austin (July 28, 1997). 24 pages. [Won98] Wong, Chung Kei, Mohamed Gouda, and Simon S. Lam "Secure group communications using key graphs" in Proceedings of SIGCOMM 98, ACM Press (1998), 68-79. Balenson, McGrew, Sherman expires February 25, 2001 [Page 30] INTERNET-DRAFT August 25, 2000 10. Acronyms and Abbreviations DCCM Dynamic Cryptographic Context Management (a DARPA project [Bal98]) DNS Domain Name System GDH Group Diffie-Hellman (a Group key exchange protocol) LKH Logical Key Hierarchy LKH+ Logical Key Hierarchy, with improved constant-time add-member operation MSMP Multicast Security Management Protocol (an NSA/Sparta effort [Harn99]) NAI Network Associates, Inc. OFC One-Way Function Chain OFT One-Way Function Tree OFT+ One-Way Function Tree, with improved constant-time add-member operation SKDC Single Key Distribution Center SMG Secure Multicast Group TIS Trusted Information Systems, Inc. XOR Bit-wise exclusive-or 11. Authors' Addresses Note: All correspondence relating to this document should be sent to David Balenson. David Balenson NAI Labs, Network Associates, Inc. 3060 Washington Road (Rt. 97) Glenwood, MD 21738 USA Phone: +1 443 259 2358 Fax: +1 301 854 4731 Email: david_balenson@nai.com URL: www.nailabs.com Dr. David A. McGrew Cisco Systems, Inc. 170 West Tasman Drive San Jose, CA 95134-1706 USA Phone: +1 408 525 8651 Fax: +1 408 527 7099 Email: mcgrew@cisco.com URL: www.cisco.com Balenson, McGrew, Sherman expires February 25, 2001 [Page 31] INTERNET-DRAFT August 25, 2000 Dr. Alan T. Sherman Department of Computer Science and Electrical Engineering University of Maryland, Baltimore County (UMBC) 1000 Hilltop Circle Baltimore, MD 21250 USA Phone: +1 410 455 2666 Fax: +1 410 455 3969 Email: sherman@umbc.edu URL: www.csee.umbc.edu/~sherman 12. Acknowledgments This work was done as part of the Dynamic Cryptographic Context Management (DCCM) project at NAI Labs, Network Associates, Inc. (formerly the Advanced Research & Engineering (AR&E) Division of Trusted Information Systems (TIS)). Support for the DCCM project was provided by the Defense Advanced Research Project Agency (DARPA) through the Air Force Research Laboratory under Contract No. F30602-97-C-0277. At the time of the work, David McGrew was a cryptography researcher at NAI Labs and Alan Sherman was a contractor on sabbatical leave from The University of Maryland, Baltimore County (UMBC). McGrew and Sherman designed and analyzed the OFT algorithm; Sherman devised the amortized induction procedure; and Balenson assisted with project management and final document preparation. In October 1998, McGrew became the head of the Cryptographic Software Development Group at Cisco Systems; now he is in the research division. The prototype OFT implementation was carried out by Pete Dinsmore, Michael Ferguson, Mike Heyman, Peter Kruus, Matt Mundy, and Caroline Scace. We would like to acknowledge contributions by several colleagues at what was TIS Labs. We are very grateful to Michael V. Harding for significant contributions to the original algorithm and for discussing implementation strategies with us. Dennis K. Branstad, Principal Investigator (former) of the DCCM Project, suggested the problem and provided constructive recommendations and technical guidance. Thanks also to Jay Turner and Michael Ferguson for helpful comments, and to Sharon Osuna and Caroline Scace for editorial suggestions. Balenson, McGrew, Sherman expires February 25, 2001 [Page 32] -------------------------------------------------------------