idnits 2.17.1 draft-balenson-groupkeymgmt-oft-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 2 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** There are 6 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 984 has weird spacing: '...ings of the S...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 26, 1999) is 9190 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'Section 7' is mentioned on line 122, but not defined == Missing Reference: 'Ste96-7' is mentioned on line 128, but not defined == Missing Reference: 'Harn97a-b' is mentioned on line 151, but not defined == Missing Reference: 'Ken93' is mentioned on line 203, but not defined == Missing Reference: 'Eas96' is mentioned on line 206, but not defined == Missing Reference: 'Car98' is mentioned on line 219, but not defined == Unused Reference: 'Chi89' is defined on line 945, but no explicit reference was found in the text == Unused Reference: 'Hark98b' is defined on line 996, but no explicit reference was found in the text == Unused Reference: 'Harn97a' is defined on line 1000, but no explicit reference was found in the text == Unused Reference: 'Harn97b' is defined on line 1004, but no explicit reference was found in the text == Unused Reference: 'Mau98' is defined on line 1042, but no explicit reference was found in the text == Unused Reference: 'Orm' is defined on line 1071, but no explicit reference was found in the text == Unused Reference: 'Sch96' is defined on line 1098, but no explicit reference was found in the text == Unused Reference: 'Ste96' is defined on line 1115, but no explicit reference was found in the text == Unused Reference: 'Ste97' is defined on line 1120, but no explicit reference was found in the text == Unused Reference: 'Sti96' is defined on line 1124, but no explicit reference was found in the text == Unused Reference: 'Vis96' is defined on line 1128, but no explicit reference was found in the text == Outdated reference: A later version (-04) exists of draft-ietf-lsma-requirements-01 ** Downref: Normative reference to an Informational draft: draft-ietf-lsma-requirements (ref. 'Bag97') -- Possible downref: Non-RFC (?) normative reference: ref. 'Bal95' ** Downref: Normative reference to an Experimental RFC: RFC 1949 (ref. 'Bal96') ** Downref: Normative reference to an Historic RFC: RFC 2201 (ref. 'Bal97') -- Possible downref: Non-RFC (?) normative reference: ref. 'Bal98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ber91' -- Possible downref: Non-RFC (?) normative reference: ref. 'Blo90' -- Possible downref: Non-RFC (?) normative reference: ref. 'Blu92' -- Possible downref: Non-RFC (?) normative reference: ref. 'Blu97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Bur94' -- Possible downref: Non-RFC (?) normative reference: ref. 'Bur97' -- No information found for draft-canetti-secure- - is the name correct? -- Possible downref: Normative reference to a draft: ref. 'Can98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Chi89' -- Possible downref: Non-RFC (?) normative reference: ref. 'Cho94' -- No information found for draft-ietf- - is the name correct? -- Possible downref: Normative reference to a draft: ref. 'Dee98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ell97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Fia93' -- Possible downref: Non-RFC (?) normative reference: ref. 'Gon89' -- Possible downref: Non-RFC (?) normative reference: ref. 'Gon94' -- Possible downref: Non-RFC (?) normative reference: ref. 'Gon96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Hard97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Hark98a' -- Unexpected draft version: The latest known version of draft-ietf-ipsec-isakmp-oakley is -07, but you're referring to -08. (However, the state information for draft-ietf- is not up-to-date. The last update was unsuccessful) ** Downref: Normative reference to an Historic draft: draft-ietf-ipsec-isakmp-oakley (ref. 'Hark98b') ** Downref: Normative reference to an Experimental RFC: RFC 2094 (ref. 'Harn97a') ** Downref: Normative reference to an Experimental RFC: RFC 2093 (ref. 'Harn97b') -- Possible downref: Non-RFC (?) normative reference: ref. 'Harn98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Hay98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Hor' -- Possible downref: Non-RFC (?) normative reference: ref. 'Jus94' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ken81' -- Possible downref: Non-RFC (?) normative reference: ref. 'Keu96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Kru98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Kum95' -- Possible downref: Non-RFC (?) normative reference: ref. 'Kur98' -- Unexpected draft version: The latest known version of draft-ietf-ipsec-isakmp is -09, but you're referring to -10. (However, the state information for draft-ietf- is not up-to-date. The last update was unsuccessful) ** Downref: Normative reference to an Historic draft: draft-ietf-ipsec-isakmp (ref. 'Mau98') -- Possible downref: Non-RFC (?) normative reference: ref. 'Men97' -- Possible downref: Non-RFC (?) normative reference: ref. 'McG98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Mer79' -- Possible downref: Non-RFC (?) normative reference: ref. 'Mit97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Nac94' -- Unexpected draft version: The latest known version of draft-ietf-ipsec-oakley is -01, but you're referring to -02. (However, the state information for draft-ietf- is not up-to-date. The last update was unsuccessful) ** Downref: Normative reference to an Informational draft: draft-ietf-ipsec-oakley (ref. 'Orm') -- Possible downref: Non-RFC (?) normative reference: ref. 'Rei93' -- Possible downref: Non-RFC (?) normative reference: ref. 'Rei94' ** Downref: Normative reference to an Informational RFC: RFC 1321 (ref. 'Riv92') -- Possible downref: Non-RFC (?) normative reference: ref. 'Riv96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Rod97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Sch96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Sha-1' -- Possible downref: Non-RFC (?) normative reference: ref. 'She98' -- Possible downref: Non-RFC (?) normative reference: ref. 'Sta97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ste96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Ste97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Sti96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Vis96' ** Downref: Normative reference to an Informational draft: draft-wallner-key-arch (ref. 'Wal97') -- Possible downref: Non-RFC (?) normative reference: ref. 'Won97' Summary: 16 errors (**), 0 flaws (~~), 21 warnings (==), 53 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT D. Balenson, D. McGrew, A. Sherman 2 TIS Labs at Network Associates 3 February 26, 1999 5 Key Management for Large Dynamic Groups: 6 One-Way Function Trees and Amortized Initialization 7 9 Status of this Memo 11 This document is an Internet-Draft and is in full conformance 12 with all provisions of Section 10 of RFC2026. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six 19 months and may be updated, replaced, or obsoleted by other 20 documents at any time. It is inappropriate to use Internet-Drafts 21 as reference material or to cite them other than as "work in 22 progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 Copyright Notice 32 Copyright (C) The Internet Society (1999). All Rights Reserved. 34 Abstract 36 We present a scalable method for establishing group session keys 37 for secure large, dynamic groups such as multicast sessions. 38 Our method is based on a novel application of One-Way Function 39 Trees (OFTs). The number of keys stored by group members, the 40 number of keys broadcast to the group when new members are added 41 or evicted, and the computational efforts of group members, are 42 logarithmic in the number of group members. The method provides 43 perfect forward and backward security: evicted members cannot 44 read future messages, even with collusion by arbitrarily many 45 evicted members, and newly admitted group members cannot read 46 previous messages. 48 Contents 50 1. Introduction ................................................. 2 51 2. Previous Work ................................................ 3 52 2.1 Key Establishment Algorithms for Large Groups ................ 3 53 2.2 Managing Large Groups ........................................ 4 54 2.3 Authentication in Large Groups ............................... 4 55 2.4 Multicast Security ........................................... 5 56 3. Group Operations and Their Security Requirements ............. 5 57 3.1 Operations ................................................... 5 58 3.2 Security Requirements ........................................ 6 59 4. One-Way Function Trees ....................................... 7 60 4.1 Structure of an OFT .......................................... 7 61 4.2 Algorithms ................................................... 8 62 4.3 Properties .................................................. 10 63 4.4 Implementation Notes and Example ............................ 11 64 4.5 Comparisons with Other Leading Key-Establishment Methods .... 12 65 5. Amortized Group Induction ................................... 15 66 5.1 Induction Model ............................................. 15 67 5.2 Induction Algorithm ......................................... 16 68 5.3 An Example of Induction ..................................... 16 69 6. Conclusion and Open Problems ................................ 17 70 7. Security Considerations ..................................... 18 71 8. References .................................................. 18 72 9. Acronyms and Abbreviations .................................. 23 73 10. Authors' Addresses .......................................... 24 74 11. Acknowledgments ............................................. 24 76 1. Introduction 78 Efficiently managing cryptographic keys for large, dynamically 79 changing groups is a difficult problem. Every time a member is 80 evicted from a group, the group key must change; it may also be 81 required to change when new members are added. The members of 82 the group must be able to compute a new key efficiently, while 83 arbitrary coalitions of evicted members must not be able to obtain 84 it. Communication costs must also be considered. 86 Real-time applications, such as secure audio and visual broadcasts, 87 pay TV, secure conferencing, and military command and control, 88 need very fast re-keying so that changes in group membership are 89 not disruptive. To deal with large group sizes (e.g. 100,000 90 members), we seek solutions whose re- keying operations "scale" 91 well in the sense that time, space, and broadcast requirements 92 of the method grow at most logarithmically in the group size. 93 Key management for these applications should be able to take 94 advantage of efficient broadcast channels, such as radio broadcast 95 and Internet multicast. 97 We present a new practical algorithm for establishing shared, 98 secret group communications keys in large, dynamic groups. Our 99 algorithm [McG98, Hard97, Bal98], which is based on a novel 100 application of one-way function trees, scales logarithmically in 101 group size. In comparison with previously published methods, 102 our algorithm achieves a new low in the required broadcast size. 104 2. Previous Work 106 The broad and challenging problem of establishing keys for large 107 dynamic groups touches upon a large body of previous work, 108 including algorithms for key establishment, group management, 109 authentication in large groups, and multicast security. As for 110 key management, unfortunately very little work has been done on 111 this critical problem in the open literature (e.g. see Schneier 112 [Sch96, pp. 169-187]). 114 2.1 Key Establishment Algorithms for Large Groups 116 Prior methods for establishing keys in groups fall roughly into 117 five categories: simple methods that scale linearly in group 118 size, information- theoretic approaches, algorithms based on 119 group Diffie-Hellman key exchange, hybrid methods that trade off 120 information-theoretic security for reduced storage requirements, 121 scalable methods based on hierarchies, and other techniques. 122 Sherman [Bal98, Section 7], Kruus [Kru98], Menezes [Men97], and 123 Just [Jus94] survey some of these methods. 125 Unfortunately, the information-theoretic approaches [Blu92, Sti96, 126 Chi89] require exponential space to achieve forward secrecy 127 against arbitrarily many colluding evicted members. Although 128 the group Diffie-Hellman methods [Ste96-7, Bur97, Bur94] offer 129 attractive distributed functionality, they suffer from a linear 130 number of expensive public-key operations. Similarly, the hybrid 131 approaches [Fia93, Ber91] scale linearly or worse. As for other 132 techniques (e.g. [Blo90, Gon89]) that do not fall nicely into 133 any of the above categories, we have not found any that provide 134 adequate security. 136 Therefore, for large groups, the leading candidates are the 137 hierarchical methods, which scale logarithmically in group size. 138 There are two hierarchical methods that do not require trusted 139 internal nodes: the Logical Key Hierarchy (LHK) of Wallner, 140 Harder, and Agee [Wal97, Won97], and the One-Way Function Tree 141 (OFT) method of McGrew and Sherman [McG98]. OFT was developed 142 at TIS Labs at Networks Associates, Inc., as part of the DARPA-funded 143 Dynamic Cryptographic Context Management (DCCM) Project [Bal98]; 144 it is the subject of this document. 146 The hierarchical methods of Ballardie [Bal96, Bal97] and Harkins 147 [Hark98a] are scalable but require trusted routers. 149 In addition, the linear Single Key Distribution Center (SKDC) 150 approach is attractive for its simplicity -- at least for relatively 151 small groups (e.g. see [Harn97a-b, Harn98]). 153 2.2 Managing Large Groups 155 Managing large groups is important for group communications and 156 for a variety of other applications, including distributed 157 fault-tolerant computing and virtual private networks. Researchers 158 have addressed important group-management issues including defining 159 group membership, supporting distributed fault-tolerant applications, 160 and effecting decentralized dynamic group management. 162 An important problem in group management is the problem of defining 163 group membership. To support the design of secure, asynchronous, 164 distributed, fault-tolerant systems, Michael Reiter [Rei94] 165 devised a group-membership protocol that tolerates malicious 166 corruption of up to one third of the participants. This protocol 167 is useful in building systems that are robust against limited 168 failures (e.g. hardware failure of some nodes), and that through 169 threshold techniques distribute trust among two or more parties. 170 By contrast, a single group controller is a single point of 171 failure and hence not fault tolerant. 173 Although group keying is often used to secure group communications, 174 another application of group keying arises in security architectures 175 for distributed fault-tolerant computing. For example, Kenneth 176 Birman [Rei93] and his research group at Cornell have studied 177 how the notion of a secure process group can be used to effect 178 secure, distributed, fault-tolerant computing. Their efforts 179 include the ISIS, Horus [Hor], and Ensemble [Hay98] Systems, 180 which provide a framework and toolkit for developing distributed 181 applications. 183 Birman [Rod97] and his group have also applied similar ideas to 184 design a virtual private network that can handle network faults, 185 decentralized management, and dynamic membership. Unfortunately, 186 their "solution currently scales [only] to approximately 100 187 machines" [Rod97, p. 14]. Also, they claim, that for data 188 confidentiality, "[their] keys are so dynamic and short-lived 189 [changed once a minute] that the approach could be used with a 190 fairly weak cryptographic scheme" [Rod97, p. 1]. 192 Li Gong [Gon96, Keu96] designed and implemented a toolkit called 193 Enclaves for building secure user-level group applications. 194 Enclaves enable users to form virtual private networks on the 195 Internet dynamically. His methods, however, do not scale to 196 large groups. Other recent work in group management includes 197 research by Fenner [Fen97]. 199 2.3 Authentication in Large Groups 201 There are several ongoing projects to develop infrastructures to 202 support authentication. Among these are the following. The 203 X.509 [Ken93] approach is based on a hierarchical global name 204 space. By contrast, the SDSI/SPKI approaches of Rivest and 205 Lampson [Riv96], and Ellison [Ell97] are based on linked local 206 name spaces. The Secure DNS approach of Eastlake [Eas96] builds 207 on the existing DNS (Domain Name System). 209 In addition, there is work on batch authentication [Nac94], which 210 provides a way to verify many certificates simultaneously for 211 certificates signed by the same authority under the same signature 212 key. 214 2.4 Multicast Security 216 Securing multicast is an active area of research. Some examples 217 of this research are works by Kent [Ken81], Gong and Shachan 218 [Gon94], Ballardie and Crowcroft [Bal95], Deering [Dee98, Dee89], 219 Bagnall [Bag97], Mittra [Mit97], Caronni, et., al. [Car98], and 220 Canetti and Pinkas [Can98], which address issues, requirements, 221 architectures, protocols, and techniques. In addition, the works 222 by Ballardie [Bal96] and Harkins [Hark98a] on key establishment 223 discuss a variety of security problems and solutions for multicast. 224 Securing Mbone [Kum95] broadcasts is one driving application. 226 3. Group Operations and Their Security Requirements 228 We envision that the management of group communications keys will 229 take place in a setting in which there will be a communications 230 system, a set of possibly overlapping groups of individuals with 231 common purposes, and individual group members. A systems manager 232 will manage the communications system, and a group manager will 233 manage each group. We envision that groups will comprise a 234 hierarchy of subgroups, with subgroup and organizational managers 235 negotiating on behalf of subgroup members. 237 3.1 Operations 239 Associated with each role (system manager, group manager, 240 individual) is a set of operations, minimally including the 241 following operations. 243 Operations processed by the system manager: 245 - induct individual into system, 246 - evict individual from system, 247 - create group, and 248 - dissolve group. 250 Section 5 explains the concept of group induction. In short, 251 the most important results of system (or group) induction are 252 for an individual to establish a base system key known only to 253 the individual and the system (or group) manager, and for the 254 system (or group) manager to check the credentials of the 255 individual. 257 Operations processed by a group manager: 259 - add member(s) to group, 260 - remove member(s) from group, 261 - evict member(s) from group, 262 - initiate communications session, and 263 - terminate communications session. 265 This document focuses on the crucial operations of adding and 266 deleting members from a group. Note that our OFT method offers 267 some economy of scale when adding or deleting two or more 268 individuals simultaneously. There are two types of membership 269 deletions: a temporary removal (when the individual has not lost 270 his security privileges), and a permanent eviction as the result 271 of loss of security privileges. 273 Operations requested by individuals: 275 - request to join group, 276 - request to leave group, 277 - request to join session, 278 - request to leave session, and 279 - request to return to session. 281 It is possible that an individual might temporarily lose contact 282 with his group manager --for example, as might happen if an 283 airplane flies out of radio range of his group. Therefore, there 284 must be a way for such a member to re-synchronize key establishment 285 with the group. 287 3.2 Security Requirements 289 The primary security requirements for the group operations of 290 adding and deleting members are forward and backward security, 291 as quantified by the degree of forward or backward security 292 [Men97, pp. 528-529]. We say that a method has t-forward 293 security if and only if (iff) no t colluding evictees can read 294 any future communications traffic of the group. Similarly, a 295 method has t-backward security iff no group of t colluding new 296 members can read any previous group traffic. A method has perfect 297 forward (backward) security iff the method has t-forward (t-backward) 298 security for all t. 300 Backward security is optional. When a new member is added, the 301 group manager may choose to create a new group key, thus denying 302 the new member access to the old key and hence previous traffic. 303 We seek methods, such as OFT, that provide perfect forward 304 security, with the option of perfect backward security. 306 Carefully note our definitions of the phrases "perfect forward 307 security" and "perfect backward security." Our use of these 308 convenient phrases should not be confused with the different 309 requirement, as explained by Menezes et al. [Men97, p. 496], that 310 compromise of long-term keys does not reveal past session keys. 311 Similarly, our use of these phrases does not necessarily imply 312 information-theoretic "perfectly-secure key distribution" in the 313 sense used by Blundo et al. [Blu92]. 315 Two additional valuable security measures are degree of traceability 316 and degree of disclosure amplification. A method is t-traceable 317 iff more than t colluding members are required to leak plaintext 318 or session keys without being identified if leaked material is 319 discovered. Disclosure amplification refers to the extent of 320 unauthorized disclosure of internal state information (e.g. 321 subgroup keys) caused by the unauthorized disclosure of certain 322 other internal state information. 324 In addition, when specifying security requirements for particular 325 applications, it is important to understand the security needs 326 and assumptions with regard to any underlying cryptographic 327 primitives (e.g. one-way functions) and with regard to fundamental 328 types of cryptographic strength (e.g. information theoretic, 329 computational, quantum uncertainty). 331 4. One-Way Function Trees 333 A One-Way Function Tree (OFT) is a binary tree, each node x of 334 which is associated with two cryptographic keys: a node key k_x 335 and a blinded node key k'_x = g(k_x). The blinded node key is 336 computed from the node key using a one-way function g; it is 337 blinded in the sense that a computationally limited adversary 338 cannot find k_x from k'_x. 340 Although the concept of a one-way function tree is not new (e.g. 341 in 1979, Merkle [Mer79] proposed an authentication system based 342 on a similar idea), our application of this concept is novel. 344 4.1 Structure of an OFT 346 A group manager maintains a one-way function tree. Each leaf is 347 associated with a member of the group. The manager uses a 348 symmetric encryption function E to communicate securely with 349 subsets of group members, using unblinded keys as encryption keys 350 as explained below. 352 Each internal node of the tree has exactly two children. The 353 manager assigns a randomly chosen key to each member, securely 354 communicates this key to the member (using an external secure 355 channel), and sets the node key of the member's leaf to the 356 member's key. The interior node keys are defined by the rule: 358 k_x = f( g(k_left(x)), g(k_right(x)) ), (1) 360 where left(x) and right(x) denotes the left and right child of 361 the node x, respectively. The function g is one-way, and the 362 function f is a "mixing" function (e.g. XOR). McGrew and Sherman 364 [McG98] discuss the properties of f and g in detail. The node 365 key associated with the root of the tree is the group key, which 366 the group can use to communicate with privacy among group members 367 and/or authentication of group membership. 369 The security of the system depends on the fact that each member's 370 knowledge about the current state of the key tree is limited by 371 the following invariant: 373 OFT Security Invariant - each member knows the unblinded node 374 keys on the path from its node to the root, and the blinded 375 node keys that are siblings to its path to the root, and no 376 other blinded or unblinded keys. 378 This invariant is maintained by all operations that add members 379 to the group, and by all operations that delete members from the 380 group. 382 4.2 Algorithms 384 The operations of adding and evicting members rely on the 385 communication of new blinded key values, from the manager to all 386 members, after the node key associated with a leaf has changed. 387 To maintain security, each blinded node key must be communicated 388 only to the appropriate subset of members. If the blinded key 389 k'_x changes, then its new value must be communicated to all of 390 the members who store it. These members are associated with the 391 descendants of the sibling of x, and they know the unblinded node 392 key k_s, where s is the sibling of x. To provide the new value 393 of the blinded key to the appropriate set of members, and keeping 394 it from other members, the manager encrypts k'_x with k_s before 395 broadcasting k_x to the group. (Here and throughout, we shall 396 use the verb "broadcast" in the sense of "group broadcast" -- 397 sending a message from the group manager to all members of the 398 group.) 400 4.2.1 Adding a member 402 When a new member joins the group, an existing leaf node x is 403 split, creating new nodes left(x) and right(x). The member 404 associated with x becomes associated with left(x), and the new 405 member is associated with right(x). Both members are given new 406 keys. The old member gets a new key because their former sibling 407 knows the old blinded node key and could use this information in 408 collusion with another group member to find an unblinded key that 409 is not on his path to the root. The new values of the blinded 410 node keys that have changed are broadcast securely to the 411 appropriate subgroups, as described in the previous paragraph. 412 The number of blinded keys that must be broadcast to the group 413 is equal to the distance from x to the root plus two. In addition, 414 in a unicast transmission, the new member is given their set of 415 blinded node keys, using the external secure channel. In order 416 to keep the height h of the tree as low as possible, when a new 417 member is added, the leaf closest to the root is split. 419 4.2.2 Evicting a member 421 When the member associated with a leaf y is evicted from the 422 group, the member assigned to the sibling of y is reassigned to 423 the parent p of y and given a new leaf key value. If the sibling 424 s of y is the root of a subtree, then p becomes s, moving the 425 subtree closer to the root. In this case, one of the leaves of 426 this subtree is given a new key (so that the evictee no longer 427 knows the blinded key associated with the root of the subtree). 428 The new values of the blinded node keys that have changed are 429 broadcast securely to the appropriate subgroups. The number of 430 keys that must be broadcast is equal to the distance from y to 431 the root. 433 4.2.3 Initialization 435 Group initialization is the process through which the group 436 establishes an initial group communications key. For our OFT 437 method, this process involves two steps. First, the group manager 438 broadcasts some information to the group members needed to apply 439 the OFT key-updating procedures. Second, the members compute a 440 shared group communications key, which is needed to begin secure 441 group communications. 443 Group initialization is separate from group induction, which is 444 explained in Section 5. During group induction, each member 445 establishes an individual group base key known only by the member 446 and the group manager. Group initialization assumes that each 447 member has already established an individual group base key. 449 In the first step of OFT group initialization, the manager 450 broadcasts every blinded node key in the OFT to all group members. 451 In this broadcast, each blinded node key is encrypted by the 452 unblinded key of the sibling node, so that only members in the 453 sibling subtree can learn the blinded node key. All members 454 receive the entire broadcast, which consists of a sequence of 455 encrypted blinded node keys. The order in which the keys are 456 broadcast is determined by a postorder traversal of the OFT. 457 This procedure enables the members to associate the keys that 458 they need with the encrypted message parts they receive. 460 4.3 Properties 462 In this section we comment briefly on the security, resource 463 usage, and salient characteristic features of The OFT method. 464 For more details, see the paper by McGrew and Sherman [McG98]. 466 The security properties of OFT stem from the system invariant 467 stated in Section 4.1, from the strength of the component one-way 468 function, and from the random selection of leaf keys. In short, 469 OFT provides perfect forward secrecy and optional perfect backward 470 secrecy. Thus, arbitrary coalitions of evicted members cannot 471 directly compute the group communications key nor any unblinded 472 node key. 474 Evicted members have some information about the key tree but not 475 enough to compute directly any unblinded node key. After a member 476 is evicted, the keys along the path from the member's node to 477 the root change. After this change, the evictee knows only the 478 blinded keys of the siblings of the nodes along the path from 479 the evictee to the root. These blinded nodes are insufficient 480 to compute directly any unblinded key. 482 Interestingly, OFT is a centralized, member-contributory method. 483 OFT is centralized in the sense that the group manager plays a 484 special trusted role. OFT is member contributory in the sense 485 that each leaf can contribute entropy to the group communication 486 key. 488 The hierarchical nature of OFT distributes the computational 489 costs of re- keying among the entire group, so that the managers 490 computational burden is comparable to that of a group member. 491 Table 1 below summarizes the salient resource usage of adding or 492 deleting a member with OFT in terms of time, memory, number of 493 bits broadcast, and number of random bits needed. 495 Resource Measure Group Member Cost Group Manager Cost 497 Time h h 498 Memory hK 2nK 499 Bits broadcast 0 hK + h 500 Random bits generated 0 K 502 Table 1: Summary of resource usage of adding or deleting 503 a member with OFT. Here, n is the group size, K is the 504 size of a key in bits, and h is the height of the OFT (h 505 = lg n when the tree is balanced). Either the member or 506 the manager could generate the random bits needed at the 507 leaves. 509 4.4 Implementation Notes and Example 511 Several important engineering decisions must be made in the 512 implementation of the OFT algorithm: the choice of f and g, the 513 format of broadcasts by the manager, the representation of the 514 tree, and time-space tradeoffs by each member involving how many 515 unblinded ancestor keys to store. 517 The function g can be based on a cryptographic hash function such 518 as MD5 [Riv92] or SHA-1 [Sha-1]. It is possible that the node 519 keys do not need to be as large as the output size of the underlying 520 function. For example, MD5 has a sixteen-byte output, while DES 521 keys are only seven bytes long. The function g can be constructed 522 from MD5 by discarding some of the output, as is done by S/KEY, 523 so that the node keys (and thus the broadcasts) are smaller. 525 The function f does not need to be one-way; it needs only to mix 526 its inputs. This fact suggests that f(x,y) = x XOR y is a fast, 527 simple, and effective choice (XOR denotes the bitwise exclusive-or 528 function). 530 +----------@----------+ 531 | | 532 +-----@-----+ +-----#-----+ 533 | | | | 534 +--#--+ +--@--+ * * 535 | | | | 536 * * # @ 537 M 539 Figure 1: An example of an OFT key tree. The member at the 540 leaf labeled M knows the keys of the nodes labeled @ (including 541 the root key, which is used as the group key), and the blinded 542 keys of the nodes labeled #. 544 The representation of the tree and the formats of the messages 545 from the group manager are important but routine engineering 546 decisions. For example, the tree could be represented as a record 547 and pointer structure, or as a linear array. Message formats 548 for messages broadcast from the manager could explicitly include 549 node number information to identify which parts of a message 550 correspond to which subtrees, or such topological information 551 could be implicit in the ordering of the message parts. 553 4.5 Comparisons with Other Leading Key-Establishment Methods 555 In this section we briefly compare our OFT algorithm against the 556 two leading competing algorithms for establishing keys in large 557 dynamic groups: the Logical Key Hierarchy (LKH) of Wallner, 558 Harder, and Agee [Wal97], and the Single Key Distribution Center 559 (SKDC). As reviewed in Section 2, these two algorithms and OFT 560 are the main choices available to system engineers who do not 561 wish to trust network routers in large group applications. OFT 562 and LKH are appealing because their computation, broadcast, and 563 memory requirements scale logarithmically with group size. 564 Despite its linear complexity, SKDC is appealing for its simplicity. 566 As suggested in an observation attributed to Radia Perlman, the 567 add-member operation in LKH can be significantly improved by 568 computing the new group communications key as the result of 569 applying a one-way function to the current group communications 570 key. We shall refer to this refinement of LKH, which maintains 571 perfect backward security, as LKH+. Unfortunately, this refinement 572 applies neither to the delete-member operation nor to the OFT 573 algorithm -- in OFT, this refinement would violate the main system 574 invariant. Fortunately, in many applications, add-member is 575 performed much more frequently than is evict-member. Independently 576 of Perlman, V. Viswanathan [Vis96, pp. 25-26] also suggested a 577 similar constant-time member-parallel idea. 579 4.5.1 Comparison Criteria 581 The choice of which key-establishment algorithm should be used 582 can be answered meaningfully only in the context of the requirements 583 of particular applications. To assist engineers in making their 584 choices, we shall summarize some of the major properties of SDKC, 585 LHK, LKH+, and OFT in terms of selected quantitative comparison 586 criteria. These criteria include total delay, number of bits 587 broadcast, number of bits unicast, manager computation, maximum 588 member computation, number of random bits generated, and manager 589 and member memory requirements. Each of these methods provides 590 perfect forward security with the option of perfect backward 591 security. 593 The four leading candidate methods differ also in terms of required 594 primitives, security semantics, central versus contributory 595 flavor, and resynchronization capabilities (for dealing with 596 group members who temporarily are unable to receive manager 597 broadcasts). For example, SDKC and LKH require encryption 598 functions; LKH+ and OFT require encryption functions and one-way 599 functions. Although none of the authors of any of these methods 600 has provided a formal proof of security, some engineers may have 601 greater confidence in the security of methods with simpler security 602 semantics. Listed in increasing complexity of security semantics, 603 the methods are: SDKC, LKH, LKH+, OFT. With regard to the source 604 of entropy of random bits in common group communication keys, 605 SDKC, LKH, and LKH+ may be viewed as member non-contributory 606 methods because the group manager provides all of the entropy. 607 By contrast, OFT can be used in either a member non-contributory 608 or member-contributory fashion. Most applications have a need 609 to provide a resynchronization capability; some methods may 610 provide some degree of passive member-synchronization. 612 When asked why she based her LKH method on a keyed encryption 613 function rather than on a faster keyless one-way function (as 614 used in OFT), Wallner [private communication (11/19/97)] explained 615 that her motivating application was a radio communication system. 616 In this application, the available hardware supported a keyed 617 encryption function but not a keyless one-way function. Wallner 618 also remarked (without connection to the choice of encryption 619 function versus one-way function), that in her application, it 620 was very important to conserve battery power. Although these 621 considerations were important to her application, other applications 622 might have different requirements or available primitives; thus 623 the rationale for Wallner's choices do not necessarily apply to 624 other applications. 626 4.5.2 Quantitative Comparison of SKDC, LKH, LKH+, and OFT 628 Tables 2 and 3 summarize the time, broadcast, and space requirements 629 of each of the four leading candidate algorithms (SKDC, LKH, 630 LKH+, and OFT). Specifically, for each algorithm and for each 631 of the initialize, add- member, evict-member operations, Table 632 2 summarizes the total delay, number of bits broadcast, number 633 of bits unicast, manager time, maximum member time, and number 634 of random bits generated. Table 3 summarizes the manager and 635 member memory requirements. For more details, see McGrew and 636 Sherman [McG98]. 638 4.5.3 Summary 640 For moderate size groups, the simple SKDC may often be appealing. 641 For very large groups, however, many applications will likely 642 demand a method that scales logarithmically in total delay and 643 member memory usage. For such applications, especially if the 644 add-member is more frequent than the evict-member operation, the 645 LKH+ method looks very attractive for its constant-time add-member 646 and relatively simple security semantics. If for the application 647 it is critical to minimize the number of bits broadcast or the 648 number of random bits generated, or if a member-contributory 649 method is needed, then OFT may be the method of choice. 651 Initialization 652 RESOURCE MEASURE SKDC LKH LKH+ OFT 653 Total delay n 2n 2n 3n 654 Number of bits broadcast nK 2nK+h 2nK+h 2nK+h 655 Number of bits unicast 0 0 0 0 656 Manager computation n 2n 2n 3n 657 Max member computation 1 h h 2h 658 No. of random bits generated K 2nK 2nK nK 660 Add member 661 RESOURCE MEASURE SKDC LKH LKH+ OFT 662 Total delay n 2h 1 3h 663 Number of bits broadcast nK 2hK+h h hK+h 664 Number of bits unicast 0 0 K hK 665 Manager computation n 2h 1 3h 666 Max member computation 1 h 1 2h 667 No. of random bits generated K hK 0 K 669 Evict member 670 RESOURCE MEASURE SKDC LKH LKH+ OFT 671 Total delay n 2h 2h 3h 672 Number of bits broadcast nK+lg n 2hK+h 2hK+h hK+h 673 Number of bits unicast 0 0 0 0 674 Manager computation n 2h 2h 3h 675 Max member computation 1 h h 2h 676 No. of random bits generated K hK hK K 678 Table 2: Summary of time and communication usage of 679 initialization, add-member, and evict-member with the SKDC, 680 LKH, LKH+, and OFT key-establishment methods. Here, n is 681 the group size, K is the size of a key in bits, and h is the 682 height of the key tree (h = lg n when the tree is balanced). 683 Note that while LKH and LKH+ hve lower magnitudes of total 684 delay, the units of time for OFT are typically much smaller 685 because keyless one-way functions are much faster than are 686 keyed-encryption functions. 688 Memory Usage 689 RESOURCE MEASURE SKDC LKH LKH+ OFT 690 Manager storage nK 2nK 2nK 2nK 691 Max member storage 2K hK hK hK 693 Table 3: Summary of manager and member memory usage in the 694 SKDC, LKH, LKH+, and OFT Key-establishment methods. Here, 695 n is the group size, K is the size of a key in bits, and h 696 is the height of the key tree (h = lg n when the tree is 697 balanced). 699 5. Amortized Group Induction 701 Before a group can establish an initial group communications key, 702 the members must be inducted (enrolled) into the group. For 703 centralized key establishment methods including OFT, an important 704 objective of this induction step is for each member to establish 705 an individual base key known only to the member and the group 706 manager. The induction process also ensures that each member has 707 the necessary certificates to take advantage of the supporting 708 authentication infrastructure. The main computational goal of 709 induction is to minimize its total delay. 711 For each group member to establish a separate base key with the 712 Group Manager, the simplest approach is for the manager to engage 713 each member in a separate pairwise authenticated key exchange 714 protocol, such as the Internet Key Exchange (IKE) protocol [Har98, 715 Mau98, Orm]. Unfortunately, this simple approach scales linearly 716 in group size. 718 In this section we describe a new approach to group induction 719 due to Sherman [She98] that amortizes the relatively high cost 720 of a pairwise key exchange over multiple entries into groups. 721 This amortization saves time when many users become members of 722 two or more groups. We call this new approach "amortized 723 induction." An IBM team [Blu97] independently discovered a 724 similar idea in a network context. 726 5.1 Induction Model 728 Assume there is a universe of N individuals from which G groups 729 are formed, each group having at most n members. Assume further 730 that N is much smaller than Gn; that is, many individuals belong 731 to several groups. It is for this reasonable assumption that 732 amortized induction offers significant savings. 734 We assume that there is a system that administers multiple groups, 735 each of whose group communications key is established by a 736 key-establishment algorithm such as OFT. Each participant may 737 join one or more group. Each group has a group manager, and 738 there is a system manager who controls induction into the system. 739 For simplicity we shall describe the induction process in terms 740 of a single system manager, though the concept of system manager 741 can be extended to a more general system management function 742 which might be distributed. For each group, each member must 743 establish an individual base key known only to the member and 744 the group manager. 746 Amortized induction reduces the number of expensive pairwise key 747 exchanges from Gn to N, which can be a significant savings. 748 Amortized induction comes at the cost of Gn one-way function 749 applications by the system manager, but these function evaluations 750 are much faster than pairwise key exchanges. For example, a single 751 application of the MD5 hash function is approximately 1000 times 752 faster than a single ISAKMP/OAKLEY key exchange. 754 5.2 Induction Algorithm 756 Whenever an individual first enters the system, the member 757 establishes an individual system base key known only to the 758 individual and the system manager. For example, this step could 759 be carried out using the ISAKMP/OAKLEY Key-Exchange Protocol. 760 Thereafter, whenever the individual joins a group, the individual 761 can establish an individual group base key with the group manager 762 as a one-way function of the individual's system base key, the 763 individual's name, and the group name. 765 More specifically, let A be the group name. For each member M, 766 the group base key KA_M for M is computed as a one-way function 767 F of M's system base key K_M, the name of M, and the group name. 768 For example, 770 KA_M = F( K_M, M, A ), (2) 772 where F is a publicly known one-way function such as the hash 773 function MD5. The total member delay in this computation is 774 constant. 776 The function F must satisfy the following properties: it must be 777 easy to compute given its three inputs, and it must be infeasible 778 for anyone to compute the output given only the last two inputs 779 (even under an adaptive chosen plaintext/ciphertext attack). 781 Whenever a group manager is appointed, the group manager establishes 782 a manager key k_A known only to the group manager and the system 783 manager. For added security this key establishment could be 784 carried out using the same pairwise key-exchange protocol used 785 in the induction process; alternatively, it would be possible to 786 compute manager keys along the lines of Equation 2. 788 Whenever members of a group need to be inducted, the system 789 manager computes the group base keys and unicasts them to the 790 group manager, encrypted under the manager key k_A. The length 791 of this unicast is linear in the group size. Note that, unlike 792 the SKDC method, no group broadcast is required. Members of 793 different groups can be inducted in parallel. 795 5.3 An Example of Induction 797 To illustrate the amortized induction process, consider a toy 798 example in which there are three individuals Q, R, S and two 799 groups A = {Q, R} and B = {S}. 801 When Member Q is inducted into the system, he establishes a base 802 system key K_Q known only to Q and the system manager. Similarly, 803 Members R and S establish base system keys K_R and K_S, respectively. 804 At the appointment of Group Manager A, Manger A establishes a 805 manager key k_A known only to Manager A and to the system manager. 806 Similarly, Group Manager B shares a manager key k_B with the 807 system manager. 809 To induct members of Group A, the system manager computes the 810 group base keys KA_Q, and KA_R for Members Q and R, respectively, 811 and sends them to Manager A encrypted under manager key k_A. 812 For example, KA_Q = f(K_Q, Q, A) and KA_R = f(K_R,R,A). In 813 parallel, Members Q and R each computes his own group base key. 814 Members of Group B are similarly inducted. 816 6. Conclusion and Open Problems 818 We have presented and analyzed a new practical hierarchical 819 algorithm for establishing shared cryptographic keys for large, 820 dynamically-changing groups. Our algorithm is based on a novel 821 application of One-way Function Trees (OFTs). 823 Unlike all previously proposed solutions based on information 824 theory, public-key cryptography, hybrid approaches, or a single 825 key distribution center, our OFT algorithm has communication, 826 computation, and storage requirements, which scale logarithmically 827 with group size, for the add or evict operation. Each of the 828 aforementioned methods scale linearly or worse. 830 In comparison with the only other proposed hierarchical method 831 that does not depend on trusted routers - the Logical Key Hierarchy 832 (LKH) [Wal97] - - our OFT algorithm reduces by half the number 833 of bits broadcast by the manager per add or evict operation. 834 The user time and space requirements of OFT and LKH are roughly 835 comparable. For many applications, including multicasts, minimizing 836 broadcast size is especially important. 838 An improvement to the LKH method which we call LKH+ (see Section 839 4.5), however, offers a significant improvement to the add 840 operation in LKH, reducing the cost of the add-member operation 841 to one one-way function application, a unicast of one key, and 842 no broadcast. This improvement to LKH, together with LKH's 843 relatively simple security semantics, makes LKH+ an attractive 844 choice for many applications. 846 The OFT method is a centralized algorithm with the option of 847 member contributions to the entropy of the common communications 848 key. Its main advantages are that, in comparison with LKH+, it 849 reduces by a factor of two the number of bits required to be 850 broadcast for each evict-member operation. Our preliminary 851 security analysis of OFT [McG98] raises some interesting questions 852 about the security of function iterates, and that of bottom-up 853 one-way function trees. 855 It is important to realize that there are significant fundamental 856 limitations to achieving security in large groups -- one might 857 even say that a secure large group is an oxymoron. In most large 858 groups, it is very likely that at least one member is unreliable, 859 untrustworthy, malicious, or careless. Each member knows the 860 common communications key and the plaintext, which is the main 861 commodity being protected. Using multiple communications keys 862 for different subgroups would not enhance security since each 863 member would still have the plaintext. Any member could disclose 864 the plaintext. Consequently, in large groups, it becomes especially 865 important to detect traitors (e.g. through fingerprints and 866 watermarks [Kur98, Sta97, Cho94]) and to limit the loss caused 867 by disclosures (e.g. by rapid evictions and re-keying). 868 Special-purpose, physically secure hardware may play a role in 869 these objectives, by restricting access to communication keys, 870 complicating effective use of compromised keys, and providing 871 unique fingerprints. 873 Our OFT algorithm offers a practical approach with low broadcast 874 size to manage the demanding key establishment requirements of 875 secure applications for large, dynamic groups. 877 7. Security Considerations 879 This document proposes a new algorithm for securely establishing 880 a shared, secret group communications key in a large, dynamic 881 group. Section 4.4 describes the security properties of this 882 algorithm. 884 8. References 886 [Bag97] Bagnall, P., R. Briscoe, and A. Poppitt, "Taxonomy of 887 communication requirements for large-scale multicast applications," 888 Internet Draft (work in progress), draft-ietf-lsma-requirements-01.txt, 889 Internet Engineering Task Force (November 21, 1997). 891 [Bal95] Ballardie, Tony, and Jon Crowcroft, "Multicast-specific 892 threats and counter-measures," Proceedings of the Internet Society 893 1995 Symposium on Network and Distributed System Security, February 894 16-17, 1995, San Diego, California, IEEE Computer Society (1995), 895 2-14. 897 [Bal96] Ballardie, A., "Scalable multicast key distribution," 898 Request for Comments (RFC) 1949, Internet Engineering Task Force 899 (May 1996), 18 pages. 901 [Bal97] Ballardie, A. "Core based tree (CBT) multicast routing 902 architecture," Request for Comments (RFC) 2201, Internet Engineering 903 Task Force (September 1997), 14 pages. 905 [Bal98] Balenson, David M., Dennis K. Branstad, David A. McGrew, 906 and Alan T. Sherman, "Dynamic cryptographic context management 908 (DCCM): Report #1: Architecture and system design," TIS Report 909 No. 0709, TIS Labs at Network Associates, Inc., Glenwood, MD 910 (June 2, 1998). 121 pages. 912 [Ber91] Berkovitz, S., "How to broadcast a secret," Advances in 913 Cryptology: Proceedings of Crypto 91, Feigenbaum, ed,. LNCS 576, 914 Springer-Verlag (1991), 535-541. 916 [Blo90] Bloom, Joel, ed., X9.24-1990, "Financial services retail 917 key management," ANSI X9A3 (March 1990). 84 pages. 919 [Blu92] Blundo, Carlo, Alfred de Santis, Amir Herzberg, Shay 920 Kutten, Ugo Vaccaro, and Moti Yung, "Perfectly-secure key 921 distribution for dynamic conferences," Advances in Cryptology: 922 Proceedings of Crypto92, E. F. Brickell, ed., LNCS 740, 923 Springer-Verlag (1992), 471-486. 925 [Blu97] Blumenthal, Uri, Nguyen C. Hien, and Bert Wijnen, "Key 926 derivation for network management applications," IEEE Network 927 (May/June 1997), 26-29. 929 [Bur94] Burmester, Mike, and Yvo Desmedt, "A secure and efficient 930 conference key distribution system," Advances in Cryptology: 931 Proceedings of Eurocrypt 94, A. De Santis, ed., LNCS 950, 932 Springer-Verlag (1994), 275-286. 934 [Bur97] Burmester, Mike, and Yvo G. Desmedt, "Efficient and 935 secure conference key distribution," Secure Protocols, M. Lomas, 936 Ed., LNCS 1189, Springer-Verlag (1997), 119-130. [Revised and 937 expanded version of the corresponding Eurocrypt 94 paper by the 938 same authors.] 940 [Can98] Canetti, R. and B. Pinkas, "A taxonomy of multicast 941 security issues," Internet Draft (work in progress), 942 draft-canetti-secure- multicast-taxonomy-00.txt, Internet 943 Engineering Task Force (May 1998). 945 [Chi89] Chiou, Guang-Huei, and Wen-Tsuen Chen, "Secure broadcasting 946 using the secure lock," IEEE Transactions on Software Engineering, 947 15:8 (August 1989), 929-934. 949 [Cho94] Chor, B., A. Fiat, and M. Naor, "Tracing traitors," 950 Advances in Cryptology: Proceedings of Crypto 94, Y. G. Desmedt, 951 Ed., LNCS 839, Springer Verlag (1994), 257-270. 953 [Dee89] Deering, S., "Host Extensions for IP Multicasting," 954 Request for Comments (RFC) 1112, Internet Engineering Task Force 955 (August 1989). 17 pages. 957 [Dee98] Deering, S., D. Estrin, D. Farinacci, M. Handley, A, 958 Helmy, V. Jacobson, C. Liu, P. Sharma, D. Thaler, and L. Wei, 959 "Protocol independent multicast-sparse mode (PIM-SM): Motivation 960 and architecture," Internet Draft (work in progress), draft-ietf- 962 idmr-pim-arch-05.txt, Internet Engineering Task Force (August 4, 963 1998). 26 pages. 965 [Ell97] Ellison, C. M., "SPKI Requirements" (February 1997). 966 [For latest version, see http://www.clark.net/pub/cme/html/spki.html] 968 [Fen97] Fenner, W., "Internet group management protocol, version 969 2," Request for Comments (RFC) 2236, Internet Engineering Task 970 Force (November 1997). 24 pages. 972 [Fia93] Fiat, Amos, and Moni Naor, "Broadcast encryption," 973 Advances in Cryptology: Proceedings of Crypto93, D. R. Stinson, 974 ed., LNCS 773, Springer-Verlag (1993), 481-491. 976 [Gon89] Gong, Li, and David J. Wheeler F. R. S., "A matrix key 977 distribution scheme," Journal of Cryptology, 2:1 (1990), 51-59. 979 [Gon94] Gong, Li, and N. Shacham, "Elements of trusted multicasting," 980 Proceedings of the IEEE International Conference on Network 981 Protocols, Boston, Massachusetts (October 1994). 983 [Gon96] Gong, Li, "Enclaves: Enabling secure collaboration over 984 the internet," Proceedings of the Sixth USENIX Unix and Network 985 Security Symposium, San Jose, California (July 1996), 149-159. 987 [Hard97] Harding, Michael, David A. McGrew, and Alan T. Sherman, 988 "A new key-management algorithm for large dynamic groups," 989 transparencies from talk given by Alan Sherman at NSA (November 990 19, 1997). 8 pages. 992 [Hark98a] Harkins, Dan, and Naganand Doraswamy, "A secure, scalable 993 multicast key management protocol (MKMP)," Draft (work in progress), 994 cisco Systems and Bay Networks (March 1998). 20 pages. 996 [Hark98b] Karkins, D. and D. Carrel, "The Internet key exchange 997 (IKE)," Internet Draft (work in progress), draft-ietf-ipsec-isakmp- 998 oakley-08.txt, Internet Engineering Task Force (June 1998). 1000 [Harn97a] Harney, Hugh, Carl Muckenhirn, and Thomas Rivers, "Group 1001 key management protocol (GKMP) architecture," Request for Comments 1002 (RFC) 2094, Internet Engineering Task Force (July 1997). 1004 [Harn97b] Harney, Hugh, Carl Muckenhirn, and Thomas Rivers, "Group 1005 key management protocol (GKMP) specification," Request for Comments 1006 (RFC) 2093, Internet Engineering Task Force (July 1997). 1008 [Harn98] Harney, Hugh, and Eric Harder, "Multicast security 1009 management protocol (MSMP): Requirements and policy," Draft (work 1010 in progress), SPARTA, Inc. (February 23, 1998). 25 pages. 1012 [Hay98] Hayden, Mark Garland, "The Ensemble system," Ph.D. 1013 Dissertation, Department of Computer Science, Cornell University 1014 (January 1998). 106 pages. 1016 [Hor] The Horus Project, 1017 http://simon.cs.cornell.edu/Info/Projects/HORUS/. 1019 [Jus94] Just, Michael K., "Methods of multi-party cryptographic 1020 key establishment," MS Thesis, School of Computer Science, Carleton 1021 University (August 9, 1994). 77 pages. 1023 [Ken81] Kent, Stephen T., "Security requirements and protocols 1024 for a broadcast scenario," IEEE Transactions on Communications 1025 (June 1981). 1027 [Keu96] Keung, S., and L. Gong, "Enclaves in Java: APIs and 1028 implementations," Technical Report SRI-CSL-96-07, SRI International, 1029 Menlo Park, California (July 1996). 1031 [Kru98] Kruus, Peter, "A survey of multicast security issues 1032 and architectures," Proceedings 21st National Information Systems 1033 Security Conference, October 5-8, 1998, Arlington, VA, 408-420. 1035 [Kum95] Kumar, Vinay, Mbone Interactive Multimedia on the 1036 Internet, New Riders Publishing (Indianapolis, IN, 1995). 1038 [Kur98] Kurosawa, Kaoru, and Yvo Desmedt, "Optimum traitor 1039 tracing and asymmetric schemes with arbiter," Draft (work in 1040 progress), Spring 98). 13 pages. 1042 [Mau98] Maughan, Douglas, Mark Schertler, Mark Schneider, and 1043 Jeff Turner, "Internet security association and key management 1044 protocol (ISAKMP)," Internet Draft (work in progress), draft- 1045 ietf-ipsec-isakmp-10.txt, Internet Engineering Task Force (July 1046 3, 1998). 86 pages. 1048 [Men97] Menezes, Alfred J., Paul C. van Oorschot, and Scott A. 1049 Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1050 Florida (1997). 1052 [McG98] McGrew, David A., and Alan T. Sherman, "Key establishment 1053 in large dynamic groups using one-way function trees," TIS Report 1054 No. 0755, TIS Labs at Network Associates, Inc., Glenwood, MD (May 1055 1998). 13 pages. 1057 [Mer79] Merkle, Raph C., "Secrecy, authentication, and public-key 1058 cryptosystems," Technical Report No. 1979-1, Information Systems 1059 Laboratory, Stanford University, Palo Alto, CA (1979). 1061 [Mit97] Mittra, Suvo, "Iolus: A framework for scalable secure 1062 multicasting," Proceedings of the ACM SIGCOMM '97, September 14- 1063 18, 1997, Cannes, France. 11 pages. 1065 [Nac94] Naccache, David, David M'Raithi, Serge Vaudenay, and 1066 Dan Raphaeli, "Can D.S.A. be improved? Complexity trade-offs with 1067 the digital signature standard," Advances in Cryptology: Eurocrypt 1068 '94, Alfredo De Santis, Ed., LNCS 950, Springer-Verlag (1994), 1069 77-85. 1071 [Orm] Orman, Hilarie K., "The OAKLEY key determination protocol," 1072 Internet Draft (work in progress), draft-ietf-ipsec-oakley- 1073 02.txt, Internet Engineering Task Force. 48 pages. 1075 [Rei93] Reiter, Michael, Kenneth Birman, and Robert van Renesse, 1076 "A security architecture for fault-tolerant systems," Technical 1077 Report TR93-1354, Department of Computer Science, Cornell University 1078 (June 1993). 29 pages. 1080 [Rei94] Reiter, Michael K, "A secure group membership protocol," 1081 Proceedings of the IEEE Computer Society Symposium on Research 1082 in Security and Privacy, Oakland, California, May 14-16, 1994, 1083 IEEE Press (1994). 1085 [Riv92] Rivest, Ronald L., The MD5 Message-Digest Algorithm, 1086 Request for Comments (RFC) 1321, Internet Engineering Task Force 1087 (1992). 1089 [Riv96] Rivest, Ronald L., and Butler Lampson, "SDSI: A simple 1090 distributed security infrastructure," Version 1.1 (October 2, 1091 1996). 1093 [Rod97] Rodeh, Ohad, Ken Birman, and Mark Hayden, "Dynamic 1094 virtual private networks," Technical Report TR97-1654, Department 1095 of Computer Science, Cornell University (November 26, 1997). 16 1096 pages. 1098 [Sch96] Schneier, Bruce, Applied Cryptography: Protocols, 1099 Algorithms, and Source Code in C, John Wiley & Sons (New York, 1100 1996). 1102 [Sha-1] FIPS Publication 180-1, Secure hash standard, NIST, 1103 U.S. Department of Commerce, Washington, D.C. (April 1995). 1105 [She98] Sherman, Alan T., "A new amortized approach to group 1106 initialization: Refinements and analysis," TIS Report No. 0754, 1107 Trusted Information Systems, Inc. Glenwood, MD (March 26, 1998). 1108 12 pages. 1110 [Sta97] Staddon, Jessica Nicola, "A combinatorial study of 1111 communication, storage and traceability in broadcast encryption 1112 systems," PhD Dissertation, Dept. of Mathematics, Univ. of 1113 California, Berkeley, CA (September 1997). 43 pages. 1115 [Ste96] Steiner, Michael, Gene Tsudik, and Michael Waidner, 1116 "Diffie- Hellman key distribution extended to group communication," 1117 Proceedings of the 3rd ACM Conference on Computer and Communications 1118 Security, March 14-16, 1996. 7 pages. 1120 [Ste97] Steiner, M., G. Tsudik, and M. Waidner, "CLIQUES: A new 1121 approach to group key agreement," IBM Research Report RZ 2984 (# 1122 93030) (December 12, 1997). 17 pages. 1124 [Sti96] Stinson, D. R., "On some methods for unconditionally 1125 secure distribution and broadcast encryption," unpublished document 1126 (November 21, 1996). 35 pages. 1128 [Vis96] Viswanathan, Vaidhyanathan, "Unconditionally secure 1129 dynamic conference key distribution," MS Thesis, University of 1130 Wisconsin- Milwaukee (December 1996). 28 pages. 1132 [Wal97] Wallner, Debby M., Eric J. Harder, and Ryan C. Agee, 1133 "Key management for multicast: Issues and architectures," Internet 1134 Draft (work in progress), draft-wallner-key-arch-01.txt, Internet 1135 Engineering Task Force (September 15, 1998). 18 pages. 1137 [Won97] Wong, Chung Kei, Mohamed G. Gouda, and Simon S. Lam 1138 "Secure group communications using key graphs," Technical Report 1139 TR-97-23, Dept. of Computer Science, Univ. of Texas at Austin 1140 (July 28, 1997). 24 pages. 1142 9. Acronyms and Abbreviations 1144 DCCM Dynamic Cryptographic Context Management (a DARPA project [Bal98]) 1145 DNS Domain Name System 1146 GDH Group Diffie-Hellman (a Group key exchange protocol) 1147 LKH Logical Key Hierarchy 1148 LKH+ Logical Key Hierarchy, with improved constant-time add-member 1149 operation 1150 MSMP Multicast Security Management Protocol (an NSA/Sparta effort 1151 [Harn98]) 1152 NAI Network Associates, Inc. 1153 OFT One-Way Function Tree 1154 SKDC Single Key Distribution Center 1155 SMG Secure Multicast Group 1156 TIS Trusted Information Systems, Inc. 1157 XOR Bit-wise exclusive-or 1159 10. Authors' Addresses 1161 Note: All correspondence relating to this document should be 1162 sent to David Balenson. 1164 David Balenson 1165 TIS Labs at Network Associates, Inc. 1166 3060 Washington Road (Rt. 97) 1167 Glenwood, MD 21738 1168 USA 1170 Phone: +1 443 259 2358 1171 Fax: +1 301 854 4731 1172 Email: balenson@tislabs.com 1173 URL: www.nai.com/products/security/tis_research/ 1174 crypto/crypt_dccm.asp 1176 Dr. David A. McGrew 1177 Cisco Systems, Inc. 1178 170 West Tasman Drive 1179 San Jose, CA 95134-1706 1180 USA 1182 Phone: +1 408 525 8651 1183 Fax: +1 408 526 4952 1184 Email: mcgrew@cisco.com 1185 URL: www.cisco.com 1187 Dr. Alan T. Sherman 1188 Department of Computer Science and Electrical Engineering 1189 University of Maryland, Baltimore County (UMBC) 1190 1000 Hilltop Circle 1191 Baltimore, MD 21250 1192 USA 1194 Phone: +1 410 455 2666 1195 Fax: +1 410 455 3969 1196 Email: sherman@umbc.edu 1197 URL: www.csee.umbc.edu/~sherman 1199 11. Acknowledgments 1201 This work was done as part of the Dynamic Cryptographic Context 1202 Management (DCCM) project at TIS Labs at Network Associates, Inc. 1203 (formerly the Advanced Research & Engineering (AR&E) Division of 1204 Trusted Information Systems (TIS)). Support for the DCCM project 1205 was provided by the Defense Advanced Research Project Agency 1206 (DARPA) through Rome Laboratory under Contract No. F30602-97-C-0277. 1208 At the time of the work, David McGrew was a cryptography researcher 1209 and Alan Sherman was a contractor on sabbatical leave from The 1210 University of Maryland, Baltimore County (UMBC). McGrew and 1211 Sherman designed and analyzed the OFT algorithm; Sherman devised 1212 the amortized induction procedure; and Balenson assisted with 1213 project management and final document preparation. In October 1214 1998, McGrew became the head of the Cryptographic Software 1215 Development Group at cisco Systems. 1217 We would like to acknowledge contributions by several colleagues 1218 at TIS Labs. We are very grateful to Michael V. Harding for 1219 significant contributions to the original algorithm and for 1220 discussing implementation strategies with us. Dennis K. Branstad, 1221 Principal Investigator (former) of the DCCM Project, suggested 1222 the problem and provided constructive recommendations and technical 1223 guidance. Thanks also to Jay Turner for helpful comments, and 1224 to Sharon Osuna and Caroline Scace for editorial suggestions.