idnits 2.17.1 draft-wallner-key-arch-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** 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 an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 532 instances of too long lines in the document, the longest one being 8 characters in excess of 72. ** There are 7 instances of lines with control characters in the document. ** The abstract seems to contain references ([1,2,4]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 337 has weird spacing: '...ers and multi...' == Line 648 has weird spacing: '...message multi...' == Line 695 has weird spacing: '...ll need stora...' == Line 696 has weird spacing: '...equires trans...' == Line 768 has weird spacing: '...If this commu...' -- 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 (July 1, 1997) is 9768 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Missing reference section? '1' on line 663 looks like a reference -- Missing reference section? '2' on line 663 looks like a reference -- Missing reference section? '4' on line 867 looks like a reference -- Missing reference section? 'Ref 1' on line 399 looks like a reference Summary: 15 errors (**), 0 flaws (~~), 5 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Debby M. Wallner 2 Category: Informational Eric J. Harder 3 Ryan C. Agee 4 National Security Agency 5 July 1, 1997 6 Expire in six months 8 Key Management for Multicast: Issues and Architectures 9 11 Status of this memo 13 This document is being submitted as an Informational RFC (Request for 14 Comment) to the Internet Engineering Task Force (IETF) for consideration 15 as a method for the establishment of multicast communication sessions. 16 Comments and suggestions for improvements are requested and should be 17 addressed to the authors. The views expressed in this paper are those of 18 the authors and do not necessarily reflect the views of the U.S. Department 19 of Defense or any of its agencies. Distribution of this document is 20 unlimited. 22 Abstract 24 This report contains a discussion of the difficult problem of key 25 management for multicast communication sessions. It focuses on two main 26 areas of concern with respect to key management, which are, initializing 27 the multicast group with a common net key and rekeying the multicast group. 28 A rekey may be necessary upon the compromise of a user or for other reasons 29 (e.g., periodic rekey). In particular, this report identifies a technique 30 which allows for secure compromise recovery, while also being robust against 31 collusion of excluded users. This is one important feature of multicast 32 key management which has not been addressed in detail by most other 33 multicast key management proposals [1,2,4]. The benefits of this proposed 34 technique are that it minimizes the number of transmissions required to 35 rekey the multicast group and it imposes minimal storage requirements on 36 the multicast group. 38 1.0 MOTIVATION 40 It is recognized that future networks will have requirements that will 42 Wallner et. al. Informational [Page 1] 43 strain the capabilities of current key management architectures. One of 44 these requirements will be the secure multicast requirement. The need for 45 high bandwidth, very dynamic secure multicast communications is increasingly 46 evident in the Department of Defense as well as the Internet communities. 47 Specifically, the secure multicast requirement is the necessity for multiple 48 users who share the same security attributes and communication requirements 49 to securely communicate with every other member of the multicast group using 50 a common multicast group net key. The largest benefit of the multicast 51 communication being that multiple receivers simultaneously get the same 52 transmission. Thus the problem is to enable each user to determine/obtain 53 the same net key without permitting unauthorized parties to do likewise 54 (initializing the multicast group) and securely rekeying the users of the 55 multicast group when necessary. At first glance, this may not appear to be 56 any different than current key management scenarios. This paper will show, 57 however, that future multicast scenarios will have very divergent and 58 dynamically changing requirements which will make it very challenging from a 59 key management perspective to address. 61 2.0 INTRODUCTION 63 The networks of the future will be able to support gigabit bandwidths for 64 individual users, to large groups of users. These users will possess 65 various quality of service options and multimedia applications that include 66 video, voice, and data, all on the same network backbone. The desire to 67 create small groups of users all interconnected and capable of communicating 68 with each other, but who are securely isolated from all other users on the 69 network is being expressed strongly by users in a variety of communities. 71 The key management infrastructure must support bandwidths ranging from 72 kilobits/second to gigabits/second, handle a range of multicast group sizes, 73 and be flexible enough for example to handle such communications 74 environments as wireless and mobile technologies. In addition to these 75 performance and communications requirements, the security requirements of 76 different scenarios are also wide ranging. It is required that users can be 77 added and removed securely and efficiently, both individually and in bulk. 78 The system must be resistant to compromise, insofar as users who have been 79 dropped should not be able to read any subsequent traffic, even if they 80 share their secret information. The costs we seek to minimize are time 81 required for setup, storage space for each end user, and total number of 82 transmissions required for setup, rekey and maintenance. It is also 83 envisioned that any proposed multicast security mechanisms will be 84 implemented no lower than any layer with the characteristics of the network 85 layer of the protocol stack. Bandwidth efficiency for any key management 86 system must also be considered. The trade-off between security and 87 performance of the entire multicast session establishment will be discussed 88 in further detail later in this document. 90 The following section will explain several potential scenarios where 91 multicast capabilities may be needed, and quantify their requirements from 92 both a performance and security perspective. It will be followed in 93 Section 4.0 by a list of factors one must consider when designing a 94 potential solution. While there are several security services that will be 96 Wallner et. al. Informational [Page 2] 97 covered at some point in this document, much of the focus of this document 98 has been on the generation and distribution of multicast group net keys. It 99 is assumed that all potential multicast participants either through some 100 manual or automated, centralized or decentralized mechanism have received 101 initialization keying material (e.g. certificates). This document does not 102 address the initialization key distribution issue. Section 5 will then 103 detail several potential multicast key management architectures, manual 104 (symmetric) and public key based (asymmetric), and highlight their relative 105 advantages and disadvantages (Note:The list of advantages and disadvantages 106 is by no means all inclusive.). In particular, this section emphasizes our 107 technique which allows for secure compromise recovery. 109 3.0 MULTICAST SCENARIOS 111 There are a variety of potential scenarios that may stress the key 112 management infrastructure. These scenarios include, but are not limited to, 113 wargaming, law enforcement, Multicast Backbone (MBONE), command and control 114 conferencing, disaster relief, and distributed computing. Potential 115 performance and security requirements, particularly in terms of multicast 116 groups that may be formed by these users for each scenario, consists of the 117 potential multicast group sizes, initialization requirements (how fast do 118 users need to be brought on-line), add/drop requirements (how fast a user 119 needs to be added or deleted from the multicast group subsequent to 120 initialization), size dynamics (the relative number of people joining/ 121 leaving these groups per given unit of time), top level security 122 requirements, and miscellaneous special issues for each scenario. While 123 some scenarios describe future secure multicast requirements, others have 124 immediate security needs. 126 As examples, let us consider two scenarios, wargaming and MBONE. 128 The wargaming scenario deals with the Defense Department's need to simulate 129 a wartime scenario for the purposes of training and evaluation. In 130 addition to actual communications equipment being used, this concept would 131 include a massive interconnection of computer simulations containing, for 132 example, video conferencing and image processing. Wargaming could be more 133 demanding from a key management perspective than an actual wartime scenario 134 for several reasons. First, the nodes of the simulation net may be 135 dispersed throughout the country. Second, very large bandwidth 136 communications, which enable the possibility for real time simulation 137 capabilities, will drive the need to drop users in and out of the simulation 138 quickly. This is potentially the most demanding scenario of the ones 139 listed. This scenario may involve group sizes of potentially 1000 or more 140 participants, some of which may be collected in smaller subgroups. These 141 groups must be initialized very rapidly, for example, in a ten second total 142 initialization time. This scenario is also very demanding in that users may 143 be required to be added or dropped from the group within one second. From 144 a size dynamics perspective, we estimate that approximately ten percent of 145 the group members may change over a one minute time period. Data rate 146 requirements are broad, ranging from kilobits per second (simulating 147 tactical users) to gigabits per second (multicast video). The wargaming 149 Wallner et. al. Informational [Page 3] 150 scenario has a fairly thorough set of security requirements covering access 151 control, user to user authentication, data confidentiality, and data 152 integrity. It also must be "robust" which implies the need to handle noisy 153 operating environments that are typical for some tactical devices. Finally, 154 the notion of availability is applied to this scenario which implies that 155 the communications network supplying the multicast capability must be up 156 and functioning a specified percentage of the time. 157 The MBONE scenario may involve group sizes of potentially 1000 or more 158 participants. These groups may take up to minutes to be initialized. This 159 scenario is less demanding in that users may be required to be added or 160 dropped from the group within seconds. From a size dynamics perspective, we 161 estimate that approximately ten percent of the group members may change over 162 a period of minutes. Data rate requirements are broad, ranging from 163 kilobits per second to 100's of Mb per second. The MBONE scenario also has 164 a fairly thorough set of security requirements covering access control, user 165 to user authentication, data confidentiality, data integrity, and 166 Non-Repudiation. The notion of availability is also applicable to this 167 scenario. The time frame for when this scenario must be provided is now. 169 4.0 ARCHITECTURAL ISSUES 171 There are many factors that must be taken into account when developing the 172 desired key management architecture. Important issues for key management 173 architectures include level (strength) of security, cost, initializing the 174 system, policy concerns, access control procedures, performance requirements 175 and support mechanisms. In addition, issues particular to multicast groups 176 include: 178 1. What are the security requirements of the group members? Most likely 179 there will be some group controller, or controllers. Do the other 180 members possess the same security requirements as the controller(s)? 182 2. Interdomain issues - When crossing from one "group domain" to another 183 domain with a potentially different security policy, which policy is 184 enforced? An example would be two users wishing to communicate, but 185 having different cryptoperiods and/or key length policies. 187 3. How does the formation of the multicast group occur? Will the group 188 controller initiate the user joining process, or will the users 189 initiate when they join the formation of the multicast group? 191 4. How does one handle the case where certain group members have inferior 192 processing capabilities which could delay the formation of the net key? 193 Do these users delay the formation of the whole multicast group, or do 194 they come on-line later enabling the remaining participants to be 195 brought up more quickly? 197 5. One must minimize the number of bits required for multicast group net 198 key distribution. This greatly impacts bandwidth limited equipments. 200 Wallner et. al. Informational [Page 4] 201 All of these and other issues need to be taken into account, along with the 202 communication protocols that will be used which support the desired 203 multicast capability. The next section addresses some of these issues and 204 presents some candidate architectures that could be used to tackle the key 205 management problem for multicasting. 207 5.0 CANDIDATE ARCHITECTURES 209 There are several basic functions that must be performed in order for a 210 secure multicast session to occur. The order in which these functions will 211 be performed, and the efficiency of the overall solution results from making 212 trade-offs of the various factors listed above. Before looking at specific 213 architectures, these basic functions will be outlined, along with some 214 definition of terms that will be used in the representative architectures. 215 These definitions and functions are as follows: 217 1. Someone determines the need for a multicast session, sets the security 218 attributes for that particular session (e.g., classification levels of 219 traffic, algorithms to be used, key variable bit lengths, etc.), and 220 creates the group access control list which we will call the initial 221 multicast group participant list. The entity which performs these 222 functions will be called the INITIATOR. At this point, the multicast 223 group participant list is strictly a list of users who the initiator 224 wants to be in the multicast group. 226 2. The initiator determines who will control the multicast group. This 227 controller will be called the ROOT (or equivalently the SERVER). Often, 228 the initiator will become the root, but the possibility exists where 229 this control may be passed off to someone other than the initiator. 230 (Some key management architectures employ multiple roots, see [4].) 231 The root's job is to perform the addition and deletion of group 232 participants, perform user access control against the security 233 attributes of that session, and distribute the traffic encryption key 234 for the session which we will call the multicast group NET KEY. After 235 initialization, the entity with the authority to accept or reject the 236 addition of future group participants, or delete current group 237 participants is called the LIST CONTROLLER. This may or may not be the 238 initiator. The list controller has been distinguished from the root for 239 reasons which will become clear later. In short, it may be desirable 240 for someone to have the authority to accept or reject new members, 241 while another party (the root) would actually perform the function. 243 3. Every participant in the multicast session will be referred to as a 244 GROUP PARTICIPANT. Specific group participants other than the root or 245 list controller will be referred to as LEAVES. 247 Wallner et. al. Informational [Page 5] 248 4. After the root checks the security attributes of the participants 249 listed on the multicast group participant list to make sure that they 250 all support the required security attributes, the root will then pass 251 the multicast group list to all other participants and create and 252 distribute the Net Key. If a participant on the multicast group list 253 did not meet the required security attributes, the leaf must be 254 deleted from the list. 256 Multiple issues can be raised with the distribution of the multicast 257 group list and Net Key. 259 a. An issue exists with the time ordering of these functions. The 260 multicast group list could be distributed before or after the link 261 is secured (i.e. the Net Key is distributed). 263 b. An issue exists when a leaf refuses to join the session. If a 264 leaf refuses to join a session, we can send out a modified list 265 before sending out the Net Key, however sending out modified 266 lists, potentially multiple times, would be inefficient. Instead, 267 the root could continue on, and would not send the Net Key to 268 those participants on the list who rejected the session. 270 For the scenario architectures which follow, we assume the multicast 271 group list will be distributed to the group participants once before 272 the Net Key is distributed. Unlike the scheme described in [4], we 273 recommend that the multicast group participant list be provided to all 274 leaves. By distributing this list to the leaves, it allows them to 275 determine upfront whether they desire to participate in the multicast 276 group or not, thus saving potentially unnecessary key exchanges. 278 Four potential key management architectures to distribute keying material 279 for multicast sessions are presented. Recall that the features that are 280 highly desirable for the architecture to possess include the time required 281 to setup the multicast group should be minimized, the number of transmissions 282 should be minimized, and memory/storage requirements should be minimized. 283 As will be seen, the first three proposals each fall short in a different 284 aspect of these desired qualities, whereas the fourth proposal appears to 285 strike a balance in the features desired. Thus, the fourth proposal is the 286 one recommended for general implementation and use. 288 Please note that these approaches also address securely eliminating users 289 from the multicast group, but don't specifically address adding new users to 290 the multicast group following initial setup because this is viewed as 291 evident as to how it would be performed. 293 5.1 MANUAL KEY DISTRIBUTION 295 Through manual key distribution, symmetric key is delivered without the use 296 of public key exchanges. To set up a multicast group Net Key utilizing 297 manual key distribution would require a sequence of events where Net Key and 298 spare Net Keys would be ordered by the root of the multicast session group. 300 Wallner et. al. Informational [Page 6] 301 Alternate (supersession) Net Keys are ordered (by the root) to be used in 302 case of a compromise of a group participant(s). The Net Keys would be 303 distributed to each individual group participant, often through some 304 centralized physical intermediate location. At some predetermined time, all 305 group participants would switch to the new Net Key. Group participants use 306 this Net Key until a predetermined time when they need another new Net Key. 307 If the Net Key is compromised during this time, the alternate Net Key is 308 used. Group participants switch to the alternate Net Key as soon as they 309 receive it, or upon notification from the root that everyone has the new Net 310 Key and thus the switch over should take place. This procedure is repeated 311 for each cryptoperiod. 313 A scheme like this may be attractive because the methods exist today and are 314 understood by users. Unfortunately, this type of scheme can be time 315 consuming to set up the multicast group based on time necessary to order 316 keying material and having it delivered. For most real time scenarios, this 317 method is much too slow. 319 5.2 N Root/Leaf Pairwise Keys Approach 321 This approach is a brute force method to provide a common multicast group 322 Net Key to the group participants. In this scheme, the initiator sets the 323 security attributes for a particular session, generates a list of desired 324 group participants and transmits the list to all group participants. The 325 leaves then respond with an initial acceptance or rejection of participation. 326 By sending the list up front, time can be saved by not performing key 327 exchanges with people who rejected participation in the session. The root 328 (who for this and future examples is assumed to be the initiator) generates a 329 pairwise key with one of the participants (leaves) in the multicast group 330 using some standard public key exchange technique (e.g., a Diffie-Hellman 331 public key exchange.) The root will then provide the security association 332 parameters of the multicast (which may be different from the parameters of 333 the initial pairwise key) to this first leaf. Parameters may include items 334 such as classification and policy. Some negotiation (through the use of a 335 Security Association Management Protocol, or SAMP) of the parameters may be 336 necessary. The possibility exists for the leaf to reject the connection to 337 the multicast group based on the above parameters and multicast group list. 338 If the leaf rejects this session, the root will repeat this process with 339 another leaf. 341 Once a leaf accepts participation in the multicast session, these two then 342 choose a Net Key to be used by the multicast group. The Net Key could be 343 generated through another public key exchange between the two entities, or 344 simply chosen by the root, depending upon the policy which is in place for 345 the multicast group ( i.e. this policy decision will not be a real time 346 choice). The issue here is the level of trust that the leaf has in the 347 root. If the initial pairwise key exchange provides some level of user 348 authentication, then it seems adequate to just have the root select the Net 349 Key at this stage. Another issue is the level of trust in the strength of 350 the security of the generated key. Through a cooperative process, both 351 entities (leaf and root) will be providing information to be used in the 353 Wallner et. al. Informational [Page 7] 354 formation of the Net Key. 355 The root then performs a pairwise key exchange with another leaf and 356 optionally performs the negotiation discussed earlier. Upon acceptance by 357 the leaf to join the multicast group, the root sends the leaf the Net Key. 359 This pairwise key exchange and Net Key distribution continues for all N 360 users of the multicast group. 362 Root/leaves cache pairwise keys for future use. These keys serve as Key 363 Encryption Keys (KEKs) used for rekeying leaves in the net at a later time. 364 Only the root will cache all of the leaves' pairwise keys. Each individual 365 leaf will cache only its own unique pairwise Key Encryption Key. 367 There are two cases to consider when caching the KEKs. The first case is 368 when the Net key and KEK are per session keys. In this case, if one wants to 369 exclude a group participant from the multicast session (and rekey the 370 remaining participants with a new Net Key), the root would distribute a new 371 Net key encrypted with each individual KEK to every legitimate remaining 372 participant. These KEKs are deleted once the multicast session is 373 completed. 375 The second case to consider is when the KEKs are valid for more than one 376 session. In this case, the Net Key may also be valid for multiple sessions, 377 or the Net Key may still only be valid for one session as in the above case. 378 Whether the Net Key is valid for one session or more than one session, the 379 KEK will be cached. If the Net Key is only valid per session, the KEKs will 380 be used to encrypt new Net Keys for subsequent multicast sessions. The 381 deleting of group participants occurs as in the previous case described 382 above, regardless of whether the Net Key is per session or to be used for 383 multiple sessions. 385 A scheme like this may be attractive to a user because it is a 386 straightforward extension of certifiable public key exchange techniques. 387 It may also be attractive because it does not involve third parties. Only 388 the participants who are part of the multicast session participate in the 389 keying mechanism. What makes this scheme so undesirable is that it will be 390 transmission intensive as we scale up in numbers, even for the most 391 computationally efficient participants, not to mention those with less 392 capable hardware (tactical, wireless, etc.). Every time the need arises to 393 drop an "unauthorized" participant, a new Net Key must be distributed. This 394 distribution requires a transmission from the Root to each remaining 395 participant, whereby the new Net Key will be encrypted under the cover of 396 each participant's unique pairwise Key Encryption Key (KEK). 398 Note: This approach is essentially the same as one proposal to the Internet 399 Engineering Task Force (IETF) Security Subworking Group [Ref 1,2]. 401 Also note that there exist multiple twists to an approach like this. For 402 example, instead of having the root do all N key exchanges, the root could 403 pass some of this functionality (and control) to a number of leaves beneath 404 him. For example, the multicast group list could be split in half and the 406 Wallner et. al. Informational [Page 8] 407 root tells one leaf to take half of the users and perform a key exchange 408 with them (and then distribute the Net key) while the root will take care of 409 the other half of the list. (The chosen leaves are thus functioning as a 410 root and we can call them "subroots." These subroots will have leaves 411 beneath them, and the subroots will maintain the KEK of each leaf beneath 412 it.) This scales better than original approach as N becomes large. 413 Specifically, it will require less time to set up (or rekey) the multicast 414 net because the singular responsibility of performing pairwise key exchanges 415 and distributing Net Key will be shared among multiple group participants 416 and can be performed in parallel, as opposed to the root only distributing 417 the Net Key to all of the participants. 419 This scheme is not without its own security concerns. This scheme pushes 420 trust down to each subgroup controller - the root assumes that these 421 "subroot" controllers are acting in a trustworthy way. Every control 422 element (root and subroots) must remain in the system throughout the 423 multicast. This effectively makes removing someone from the net (especially 424 the subroots) harder and slower due to the distributed control. When 425 removing a participant from the multicast group which has functioned on 426 behalf of the root, as a subroot, to distribute Net Key, additional steps 427 will be necessary. A new subroot must be delegated by the root to replace 428 the removed subroot. A key exchange (to generate a new pairwise KEK) must 429 occur between the new subroot and each leaf the removed subroot was 430 responsible for. A new Net Key will now be distributed from the root, to 431 the subroots, and to the leaves. Note that this last step would have been 432 the only step required if the removed party was a leaf with no controlling 433 responsibilities. 435 5.3 COMPLEMENTARY VARIABLE APPROACH 437 Let us suppose we have N leaves. The Root performs a public key exchange 438 with each leaf i (i= 1,2, ..., N). The Root will cache each pairwise KEK. 439 Each leaf stores their own KEK. The root would provide the multicast group 440 list of participants and attributes to all users. Participants would accept 441 or reject participation in the multicast session as described in previous 442 sections. The root encrypts the Net Key for the Multicast group to each 443 leaf, using their own unique KEK(i). (The Root either generated this Net 444 Key himself, or cooperatively generated with one of the leaves as was 445 discussed earlier). In addition to the encrypted Net Key, the root will 446 also encrypt something called complementary variables and send them to the 447 leaves. A leaf will NOT receive his own complementary variable, but he 448 will receive the other N-1 leaf complementary variables. The root sends the 449 Net Key and complementary variables j, where j=1,2,...,N and j not equal to 450 i, encrypted by KEK(i) to each leaf. 452 Thus, every leaf receives and stores N variables which are the Net key, and 453 N-1 complementary variables. 455 Thus to cut a user from the multicast group and get the remaining 456 participants back up again on a new Net Key would involve the following. 457 Basically, to cut leaf number 20 out of the net, one message is sent out 459 Wallner et. al. Informational [Page 9] 460 that says "cut leaf 20 from the net." All of the other leaves (and Root) 461 generate a new Net Key based on the current Net Key and Complementary 462 variable 20. [Thus some type of deterministic key variable generation 463 process will be necessary for all participants of the multicast group]. This 464 newly generated variable will be used as the new Net Key by all remaining 465 participants of the multicast group. Everyone except leaf 20 is able to 466 generate the new Net Key, because they have complementary variable 20, but 467 leaf 20 does not. 469 A scheme like this seems very desirable from the viewpoint of transmission 470 savings since a rekey message encrypted with each individual KEK to every 471 leaf does not have to be sent to delete someone from the net. In other 472 words, there will be one plaintext message to the multicast group versus N 473 encrypted rekey messages. There exists two major drawbacks with this 474 scheme. First are the storage requirements necessary for the (N-1) 475 complementary variables. Secondly, when deleting multiple users from the 476 multicast group, collusion will be a concern. What this means is that these 477 deleted users could work together and share their individual complementary 478 variables to regain access to the multicast session. 480 5.4 HIERARCHICAL TREE APPROACH 482 The Hierarchical Tree Approach is our recommended approach to address the 483 multicast key management problem. This approach provides for the following 484 requisite features: 486 1. Provides for the secure removal of a compromised user from the 487 multicast group 489 2. Provides for transmission efficiency 491 3. Provides for storage efficiency 493 This approach balances the costs of time, storage and number of required 494 message transmissions, using a hierarchical system of auxiliary keys to 495 facilitate distribution of new Net Key. The result is that the storage 496 requirement for each user and the transmissions required for key replacement 497 are both logarithmic in the number of users, with no background 498 transmissions required. This approach is robust against collusion of 499 excluded users. Moreover, while the scheme is hierarchical in nature, no 500 infrastructure is needed beyond a server (e.g., a root), though the presence 501 of such elements could be used to advantage (See Figure 1). 503 -------------------------- 504 | | 505 | S E R V E R | 506 | | 507 -------------------------- 508 | | | 509 | | . . . . | 510 - - - 511 |1| |2| |n| 512 - - - 514 Figure 1: Assumed Communication Architecture 516 The scheme, advantages and disadvantages are enumerated in more detail 517 below. Consider Figure 2 below. This figure illustrates the logical key 518 distribution architecture, where keys exist only at the server and at the 519 users. Thus, the server in this architecture would hold Keys A through O, 520 and the KEKs of each user. User 11 in this architecture would hold its own 521 unique KEK, and Keys F, K, N, and O. 523 net key Key O 524 ------------------------------------- 525 intermediate | | 526 keys | | 527 Key M Key N 528 ----------------- -------------------- 529 | | | | 530 | | | | 531 Key I Key J Key K Key L 532 -------- -------- --------- ---------- 533 | | | | | | | | 534 | | | | | | | | 535 Key A Key B Key C Key D Key E Key F Key G Key H 536 --- --- --- --- --- ---- ---- ---- 537 | | | | | | | | | | | | | | | | 538 - - - - - - - - - -- -- -- -- -- -- -- 539 |1| |2| |3| |4| |5| |6| |7| |8| |9| |10| |11| |12| |13| |14| |15| |16| 540 - - - - - - - - - -- -- -- -- -- -- -- 541 users 543 Figure 2: Logical Key Distribution Architecture 545 We now describe the organization of the key hierarchy and the setup process. 546 It will be clear from the description how to add users after the hierarchy 547 is in place; we will also describe the removal of a user. Note: The passing 548 of the multicast group list and any negotiation protocols is not included in 549 this discussion for simplicity purposes. 551 We construct a rooted tree (from the bottom up) with one leaf corresponding 552 to each user, as in Figure 2. (Though we have drawn a balanced binary tree 553 for convenience, there is no need for the tree to be either balanced or 554 binary - some preliminary analysis on tree shaping has been performed.) Each 555 user establishes a unique pairwise key with the server. For users with 556 transmission capability, this can be done using the public key exchange 557 protocol. The situation is more complicated for receive-only users; it is 558 easiest to assume these users have pre-placed key. 560 Once each user has a pairwise key known to the server, the server generates 561 (according to the security policy in place for that session) a key for each 562 remaining node in the tree. The keys themselves should be generated by a 563 robust process. We will also assume users have no information about keys 564 they don't need. (Note: There are no users at these remaining nodes, (i.e., 565 they are logical nodes) and the key for each node need only be generated by 566 the server via secure means.) Starting with those nodes all of whose 567 children are leaves and proceeding towards the root, the server transmits 568 the key for each node, encrypted using the keys for each of that node's 569 children. At the end of the process, each user can determine the keys 570 corresponding to those nodes above her leaf. In particular, all users hold 571 the root key, which serves as the common Net Key for the group. The storage 572 requirement for a user at depth d is d+1 keys (Thus for the example in 573 Figure 2, a user at depth d=4 would hold five keys. That is, the unique Key 574 Encryption Key generated as a result of the pairwise key exchange, three 575 intermediate node keys - each separately encrypted and transmitted, and the 576 common Net Key for the multicast group which is also separately encrypted.) 578 It is also possible to transmit all of the intermediate node keys and root 579 node key in one message, where the node keys would all be encrypted with the 580 unique pairwise key of the individual leaf. In this manner, only one 581 transmission (of a larger message) is required per user to receive all of 582 the node keys (as compared to d transmissions). It is noted for this 583 method, that the leaf would require some means to determine which key 584 corresponds to which node level. 586 It is important to note that this approach requires additional processing 587 capabilities at the server where other alternative approaches may not. In 588 the worst case, a server will be responsible for generating the intermediate 589 keys required in the architecture. 591 5.4.1 The Exclusion Principle 593 Suppose that User 11 (marked on Figure 2 in black) needs to be deleted from 594 the multicast group. Then all of the keys held by User 11 (bolded Keys F, K, 595 N, O) must be changed and distributed to the users who need them, without 596 permitting User 11 or anyone else from obtaining them. To do this, we must 597 replace the bolded keys held by User 11, proceeding from the bottom up. The 598 server chooses a new key for the lowest node, then transmits it encrypted 599 with the appropriate daughter keys (These transmissions are represented by 600 the dotted lines). Thus for this example, the first key replaced is Key F, 601 and this new key will be sent encrypted with User 12's unique pairwise key. 603 Since we are proceeding from the bottom up, each of the replacement keys 604 will have been replaced before it is used to encrypt another key. (Thus, for 605 the replacement of Key K, this new key will be sent encrypted in the newly 606 replaced Key F (for User 12) and will also be sent as one multicast 607 transmission encrypted in the node key shared by Users 9 and 10 (Key E). For 608 the replacement of Key N, this new key will be sent encrypted in the newly 609 replaced Key K (for Users 9, 10, and 12) and will also be encrypted in the 610 node key shared by Users 13, 14, 15, and 16 (Key L). For the replacement of 611 Key O, this new key will be sent encrypted in the newly replaced Key N (for 612 Users 9, 10, 12, 13, 14, 15, and 16) and will also be encrypted in the node 613 key shared by Users 1, 2 , 3, 4, 5, 6, 7, and 8 (Key M).) The number of 614 transmissions required is the sum of the degrees of the replaced nodes. In a 615 k-ary tree in which a sits at depth d, this comes to at most kd-1 616 transmissions. Thus in this example, seven transmissions will be required 617 to exclude User 11 from the multicast group and to get the other 15 users 618 back onto a new multicast group Net Key that User 11 does not have access 619 to. It is easy to see that the system is robust against collusion, in that 620 no set of users together can read any message unless one of them could have 621 read it individually. 623 If the same strategy is taken as in the previous section to send multiple 624 keys in one message, the number of transmissions required can be reduced 625 even further to four transmissions. Note once again that the messages will 626 be larger in the number of bits being transmitted. Additionally, there must 627 exist a means for each leaf to determine which key in the message 628 corresponds to which node of the hierarchy. Thus, in this example, for the 629 replacement of keys F, K, N, and O to User 12, the four keys will be 630 encrypted in one message under User 12's unique pairwise key. To replace 631 keys K, N, and O for Users 9 and 10, the three keys will be encrypted in one 632 message under the node key shared by Users 9 and 10 (Key E). To replace 633 keys N and O for Users 13, 14, 15, 16, the two keys will be encrypted in 634 one message under the node key shared by Users 13, 14, 15, and 16 (Key L). 635 Finally, to replace key O for Users 1, 2 , 3, 4, 5, 6, 7, and 8, key O will 636 be encrypted under the node key shared by Users 1, 2 , 3, 4, 5, 6, 7, and 8 637 (Key M). Thus the number of transmission required is at most (k-1)d. 639 The following table demonstrates the removal of a user, and how the storage 640 and transmission requirements grow with the number of users. 642 Table 1: Storage and Transmission Costs 644 Number Degree Storage per user Transmissions to Transmissions to 645 of users (k) (d+1) rekey remaining rekey remaining 646 participants of participants of 647 multicast group - multicast group - 648 one key per message multiple keys per 649 (kd-1) message 650 (k-1)d 651 8 2 4 5 3 652 9 3 3 5 4 653 16 2 5 7 4 654 2048 2 12 21 11 655 2187 3 8 20 14 656 131072 2 18 33 17 657 177147 3 12 32 22 659 The benefits of a scheme such as this are: 661 1. The costs of user storage and rekey transmissions are balanced and 662 scalable as the number of users increases. This is not the case for 663 [1], [2], or [4]. 665 2. The auxiliary keys can be used to transmit not only other keys, but 666 also messages. Thus the hierarchy can be designed to place subgroups 667 that wish to communicate securely (i.e. without transmitting to the 668 rest of the large multicast group) under particular nodes, eliminating 669 the need for maintenance of separate Net Keys for these subgroups. 670 This works best if the users operate in a hierarchy to begin with 671 (e.g., military operations), which can be reflected by the key 672 hierarchy. 674 3. The hierarchy can be designed to reflect network architecture, 675 increasing efficiency (each user receives fewer irrelevant messages). 676 Also, server responsibilities can be divided up among subroots (all of 677 which must be secure). 679 4. The security risk associated with receive-only users can be minimized 680 by collecting such users in a particular area of the tree. 682 5. This approach is resistant to collusion among arbitrarily many users. 684 As noted earlier, in the rekeying process after one user is compromised, in 685 the case of one key per message, each replaced key must be decrypted 686 successfully before the next key can be replaced (unless users can cache the 687 rekey messages). This bottleneck could be a problem on a noisy or slow 688 network. (If multiple users are being removed, this can be parallelized, so 689 the expected time to rekey is roughly independent of the number of users 690 removed.) 692 By increasing the valences and decreasing the depth of the tree, one can 693 reduce the storage requirements for users at the price of increased 694 transmissions. For example, in the one key per message case, if n users are 695 arranged in a k-ary tree, each user will need storage. Rekeying after one 696 user is removed now requires transmissions. As k approaches n, this 697 approaches the pairwise key scheme described earlier in the paper. 699 5.4.2 Hierarchical Tree Approach Options 701 5.4.2.1 Distributed Hierarchical Tree Approach 703 The Hierarchical Tree Approach outlined in this section could be distributed 704 as indicated in Section 5.2 to more closely resemble the proposal put forth 705 in [4]. Subroots could exist at each of the nodes to handle any joining or 706 rekeying that is necessary for any of the subordinate users. This could be 707 particularly attractive to users which do not have a direct connection back 708 to the Root. Recall as indicated in Section 5.2, that the trust placed in 709 these subroots to act with the authority and security of a Root, is a 710 potentially dangerous proposition. This thought is also echoed in [4]. 712 Some practical recommendations that might be made for these subroots include 713 the following. The subroots should not be allowed to change the multicast 714 group participant list that has been provided to them from the Root. One 715 method to accomplish this, would be for the Root to sign the list before 716 providing it to the subroots. Authorized subroots could though be allowed 717 to set up new multicast groups for users below them in the hierarchy. 719 It is important to note that although this distribution may appear to 720 provide some benefits with respect to the time required to initialize the 721 multicast group (as compared to the time required to initialize the group as 722 described in Section 5.4) and for periodic rekeying, it does not appear to 723 provide any benefit in rekeying the multicast group when a user has been 724 compromised. 726 It is also noted that whatever the key management scheme is (hierarchical 727 tree, distributed hierarchical tree, core based tree, GKMP, etc.), there 728 will be a "hit" incurred to initialize the multicast group with the first 729 multicast group net key. Thus, the hierarchical tree approach does not 730 suffer from additional complexity with comparison to the other schemes with 731 respect to initialization. 733 5.4.2.2 Multicast Group Formation 735 Although this paper has presented the formation of the multicast group as 736 being Root initiated, the hierarchical approach is consistent with user 737 initiated joining. User initiated joining is the method of multicast group 738 formation presented in [4]. User initiated joining may be desirable when 739 some core subset of users in the multicast group need to be brought up on- 740 line and communicating more quickly. Other participants in the multicast 741 group can then be brought in when they wish. In this type of approach 742 though, there does not exist a finite period of time by when it can be 743 ensured all participants will be a part of the multicast group. 745 For example, in the case of a single root, the hierarchy is set up once, in 746 the beginnning, by the initiator (also usually the root) who also generates 747 the group participant list. The group of keys for each participant can then 748 be individually requested (pulled) as soon as, but not until, each 749 participant wishes to join the session. 751 5.4.2.3 Sender Specific Authentication 753 In the multicast environment, the possibility exists that participants of 754 the group at times may want to uniquely identify which participant is the 755 sender of a multicast group message. In the multicast key distribution 756 system described by Ballardie [4], the notion of "sender specific keys" is 757 presented. 759 Another option to allow participants of a multicast group to uniquely 760 determine the sender of a message is through the use of a signature process. 761 When a member of the multicast group signs a message with their own private 762 signature key, the recipients of that signed message in the multicast group 763 can use the sender's public verification key to determine if indeed the 764 message is from who it is claimed to be from. 766 Another related idea to this is the case when two users of a multicast group 767 want to communicate strictly with each other, and want no one else to listen 768 in on the communication. If this communication relationship is known when 769 the multicast group is originally set up, then these two participants could 770 simply be placed adjacent to one another at the lowest level of the 771 hierarchy (below a binary node). Thus, they would naturally share a secret 772 pairwise key. Otherwise, a simple way to accomplish this is to perform a 773 public key based pairwise key exchange between the two users to generate a 774 traffic encryption key for their private unicast communications. Through 775 this process, not only will the encrypted transmissions between them be 776 readable only by them, but unique sender authentication can be accomplished 777 via the public key based pairwise exchange. 779 5.4.2.4 Rekeying the Multicast Group and the Use of Group Key Encryption Keys 781 Reference [4] makes use of a Group Key Encryption Key that can be shared by 782 the multicast group for use in periodic rekeys of the multicast group. 783 Aside from the potential security drawbacks of implementing a shared key for 784 encrypting future keys, the use of a Group Key Encryption Key is of no 785 benefit to a multicast group if a rekey is necessary due to the known 786 compromise of one of the members. The strategy for rekeying the multicast 787 group presented in Section 5.4.1 specifically addresses this critical 788 problem and offers a means to accomplish this task with minimal message 789 transmissions and storage requirements. 791 The question though can now be asked as to whether the rekey of a multicast 792 group will be necessary in a non-compromise scenario. For example, if a 793 user decides they do not want to participate in the group any longer, and 794 requests the list controller to remove them from the multicast group 795 participant list, will a rekey of the multicast group be necessary? If the 796 security policy of the multicast group mandates that deleted users can no 797 longer receive transmissions, than a rekey of a new net key will be 798 required. If the multicast group security policy does not care that the 799 deleted person can still decrypt any transmissions (encrypted in the group 800 net key that they might still hold), but does care that they can not encrypt 801 and transmit messages, a rekey will once again be necessary. The only 802 alternative to rekeying the multicast group under this scenario would 803 require a recipient to check every received message sender, against the 804 group participant list. Thus rejecting any message sent by a user not on 805 the list. This is not a practical option. Thus it is recommended to always 806 rekey the multicast group when someone is deleted, whether it is because of 807 compromise reasons or not. 809 5.4.2.5 Bulk Removal of Participants 811 As indicated in Section 2, the need may arise to remove users in bulk. If 812 the users are setup as discussed in Section 5.4.1 into subgroups that wish 813 to communicate securely all being under the same node, bulk user removal can 814 be done quite simply if the whole node is to be removed. The same technique 815 as described in Section 5.4.1 is performed to rekey any shared node key that 816 the remaining participants hold in common with the removed node. 818 The problem of bulk removal becomes more difficult when the participants to 819 be removed are dispersed throughout the tree. Depending on how many 820 participants are to be removed, and where they are located within the 821 hierarchy, the number of transmissions required to rekey the multicast group 822 could be equivalent to brute force rekeying of the remaining participants. 823 Also the question can be raised as to at what point the remaining users are 824 restructured into a new hierarchical tree, or should a new multicast group 825 be formed. Restructuring of the hierarchical tree would most likely be the 826 preferred option, because it would not necessitate the need to perform 827 pairwise key exchanges again to form the new user unique KEKs. 829 5.4.2.6 ISAKMP Compatibility 831 Thus far this document has had a major focus on the architectural trade-offs 832 involved in the generation, distribution, and maintenance of traffic 833 encryption keys (Net Keys) for multicast groups. There are other elements 834 involved in the establishment of a secure connection among the multicast 835 participants that have not been discussed in any detail. For example, the 836 concept of being able to "pick and choose" and negotiating the capabilities 837 of the key exchange mechanism and various other elements is a very important 838 and necessary aspect. 840 The NSA proposal to the Internet Engineering Task Force (IETF) Security 841 Subworking Group [Ref. 3] entitled "Internet Security Association and Key 842 Management Protocol (ISAKMP)" has attempted to identify the various 843 functional elements required for the establishment of a secure connection 844 for the largest current network, the Internet. While the proposal has 845 currently focused on the problem of point to point connections, the 846 functional elements should be the same for multicast connections, with 847 appropriate changes to the techniques chosen to implement the individual 848 functional elements. Thus the implementation of ISAKMP is compatible with 849 the use of the hierarchical tree approach. 851 6.0 SUMMARY 853 As discussed in this report, there are two main areas of concern when 854 addressing solutions for the multicast key management problem. They are the 855 secure initialization and rekeying of the multicast group with a common net 856 key. At the present time, there are multiple papers which address the 857 initialization of a multicast group, but they do not adequately address how 858 to efficiently and securely remove a compromised user from the multicast 859 group. 861 This paper proposed a hierarchical tree approach to meet this difficult 862 problem. It is robust against collusion, while at the same time, balancing 863 the number of transmissions required and storage required to rekey the 864 multicast group in a time of compromise. 866 It is also important to note that the proposal recommended in this paper is 867 consistent with other multicast key management solutions [4], and allows for 868 multiple options for its implementation. 870 7.0 REFERENCES 872 1. Harney, Hugh; Muckenhirn, Carl; and Rivers, Thomas; "Group Key 873 Management Protocol Architecture," dtd September 1994, Sparta, Inc. 875 2. Harney, Hugh; Muckenhirn, Carl; and Rivers, Thomas; "Group Key 876 Management Protocol Specification," dtd September 1994, Sparta, Inc. 878 3. Maughan, Douglas; Schertler, Mark; Schneider, Mark; and 879 Turner, Jeff; "Internet Security Association and Key Management 880 Protocol, Version 7" dtd. 21 February 1997. 882 4. Ballardie, A.; "Scalable Multicast Key Distribution," dtd May 1996. 884 Address of Authors 886 The authors are with: 888 National Security Agency 889 Attn: R2 890 9800 Savage Road STE 6451 891 Ft. Meade, MD. 20755-6451 893 1. Debby M. Wallner 894 Phone: 301-688-0331 895 E-mail: dmwalln@orion.ncsc.mil 897 2. Eric J. Harder 898 Phone: 301-688-0850 899 E-mail: ejh@tycho.ncsc.mil 901 3. Ryan C. Agee