diff options
Diffstat (limited to 'doc/rfc/rfc2627.txt')
| -rw-r--r-- | doc/rfc/rfc2627.txt | 1291 |
1 files changed, 1291 insertions, 0 deletions
diff --git a/doc/rfc/rfc2627.txt b/doc/rfc/rfc2627.txt new file mode 100644 index 0000000..5ee2990 --- /dev/null +++ b/doc/rfc/rfc2627.txt @@ -0,0 +1,1291 @@ + + + + + + +Network Working Group D. Wallner +Request for Comments: 2627 E. Harder +Category: Informational R. Agee + National Security Agency + June 1999 + + + Key Management for Multicast: Issues and Architectures + +Status of this Memo + + This memo provides information for the Internet community. It does + not specify an Internet standard of any kind. Distribution of this + memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (1999). All Rights Reserved. + +Abstract + + This report contains a discussion of the difficult problem of key + management for multicast communication sessions. It focuses on two + main areas of concern with respect to key management, which are, + initializing the multicast group with a common net key and rekeying + the multicast group. A rekey may be necessary upon the compromise of + a user or for other reasons (e.g., periodic rekey). In particular, + this report identifies a technique which allows for secure compromise + recovery, while also being robust against collusion of excluded + users. This is one important feature of multicast key management + which has not been addressed in detail by most other multicast key + management proposals [1,2,4]. The benefits of this proposed + technique are that it minimizes the number of transmissions required + to rekey the multicast group and it imposes minimal storage + requirements on the multicast group. + +1.0 MOTIVATION + + It is recognized that future networks will have requirements that + will strain the capabilities of current key management architectures. + One of these requirements will be the secure multicast requirement. + The need for high bandwidth, very dynamic secure multicast + communications is increasingly evident in a wide variety of + commercial, government, and Internet communities. Specifically, the + secure multicast requirement is the necessity for multiple users who + share the same security attributes and communication requirements to + securely communicate with every other member of the multicast group + using a common multicast group net key. The largest benefit of the + + + +Wallner, et al. Informational [Page 1] + +RFC 2627 Key Management for Multicast June 1999 + + + multicast communication being that multiple receivers simultaneously + get the same transmission. Thus the problem is enabling each user to + determine/obtain the same net key without permitting unauthorized + parties to do likewise (initializing the multicast group) and + securely rekeying the users of the multicast group when necessary. + At first glance, this may not appear to be any different than current + key management scenarios. This paper will show, however, that future + multicast scenarios will have very divergent and dynamically changing + requirements which will make it very challenging from a key + management perspective to address. + +2.0 INTRODUCTION + + The networks of the future will be able to support gigabit bandwidths + for individual users, to large groups of users. These users will + possess various quality of service options and multimedia + applications that include video, voice, and data, all on the same + network backbone. The desire to create small groups of users all + interconnected and capable of communicating with each other, but who + are securely isolated from all other users on the network is being + expressed strongly by users in a variety of communities. + + The key management infrastructure must support bandwidths ranging + from kilobits/second to gigabits/second, handle a range of multicast + group sizes, and be flexible enough for example to handle such + communications environments as wireless and mobile technologies. In + addition to these performance and communications requirements, the + security requirements of different scenarios are also wide ranging. + It is required that users can be added and removed securely and + efficiently, both individually and in bulk. The system must be + resistant to compromise, insofar as users who have been dropped + should not be able to read any subsequent traffic, even if they share + their secret information. The costs we seek to minimize are time + required for setup, storage space for each end user, and total number + of transmissions required for setup, rekey and maintenance. It is + also envisioned that any proposed multicast security mechanisms will + be implemented no lower than any layer with the characteristics of + the network layer of the protocol stack. Bandwidth efficiency for + any key management system must also be considered. The trade-off + between security and performance of the entire multicast session + establishment will be discussed in further detail later in this + document. + + + + + + + + + +Wallner, et al. Informational [Page 2] + +RFC 2627 Key Management for Multicast June 1999 + + + The following section will explain several potential scenarios where + multicast capabilities may be needed, and quantify their requirements + from both a performance and security perspective. It will be + followed in Section 4.0 by a list of factors one must consider when + designing a potential solution. While there are several security + services that will be covered at some point in this document, much of + the focus of this document has been on the generation and + distribution of multicast group net keys. It is assumed that all + potential multicast participants either through some manual or + automated, centralized or decentralized mechanism have received + initialization keying material (e.g. certificates). This document + does not address the initialization key distribution issue. Section + 5 will then detail several potential multicast key management + architectures, manual (symmetric) and public key based (asymmetric), + and highlight their relative advantages and disadvantages (Note:The + list of advantages and disadvantages is by no means all inclusive.). + In particular, this section emphasizes our technique which allows for + secure compromise recovery. + +3.0 MULTICAST SCENARIOS + + There are a variety of potential scenarios that may stress the key + management infrastructure. These scenarios include, but are not + limited to, wargaming, law enforcement, teleconferencing, command and + control conferencing, disaster relief, and distributed computing. + Potential performance and security requirements, particularly in + terms of multicast groups that may be formed by these users for each + scenario, consists of the potential multicast group sizes, + initialization requirements (how fast do users need to be brought + on-line), add/drop requirements (how fast a user needs to be added or + deleted from the multicast group subsequent to initialization), size + dynamics (the relative number of people joining/leaving these groups + per given unit of time), top level security requirements, and + miscellaneous special issues for each scenario. While some scenarios + describe future secure multicast requirements, others have immediate + security needs. + + As examples, let us consider two scenarios, distributed gaming and + teleconferencing. + + Distributed gaming deals with the government's need to simulate a + conflict scenario for the purposes of training and evaluation. In + addition to actual communications equipment being used, this concept + would include a massive interconnection of computer simulations + containing, for example, video conferencing and image processing. + Distributed gaming could be more demanding from a key management + perspective than an actual scenario for several reasons. First, the + nodes of the simulation net may be dispersed throughout the country. + + + +Wallner, et al. Informational [Page 3] + +RFC 2627 Key Management for Multicast June 1999 + + + Second, very large bandwidth communications, which enable the + possibility for real time simulation capabilities, will drive the + need to drop users in and out of the simulation quickly. This is + potentially the most demanding scenario of any considered. + + This scenario may involve group sizes of potentially 1000 or more + participants, some of which may be collected in smaller subgroups. + These groups must be initialized very rapidly, for example, in a ten + second total initialization time. This scenario is also very + demanding in that users may be required to be added or dropped from + the group within one second. From a size dynamics perspective, we + estimate that approximately ten percent of the group members may + change over a one minute time period. Data rate requirements are + broad, ranging from kilobits per second (simulating tactical users) + to gigabits per second (multicast video). The distributed gaming + scenario has a fairly thorough set of security requirements covering + access control, user to user authentication, data confidentiality, + and data integrity. It also must be "robust" which implies the need + to handle noisy operating environments that are typical for some + tactical devices. Finally, the notion of availability is applied to + this scenario which implies that the communications network supplying + the multicast capability must be up and functioning a specified + percentage of the time. + + The teleconference scenario may involve group sizes of potentially + 1000 or more participants. These groups may take up to minutes to be + initialized. This scenario is less demanding in that users may be + required to be added or dropped from the group within seconds. From + a size dynamics perspective, we estimate that approximately ten + percent of the group members may change over a period of minutes. + Data rate requirements are broad, ranging from kilobits per second to + 100's of Mb per second. The teleconference scenario also has a + fairly thorough set of security requirements covering access control, + user to user authentication, data confidentiality, data integrity, + and non-repudiation. The notion of availability is also applicable + to this scenario. The time frame for when this scenario must be + provided is now. + +4.0 ARCHITECTURAL ISSUES + + There are many factors that must be taken into account when + developing the desired key management architecture. Important issues + for key management architectures include level (strength) of + security, cost, initializing the system, policy concerns, access + control procedures, performance requirements and support mechanisms. + In addition, issues particular to multicast groups include: + + + + + +Wallner, et al. Informational [Page 4] + +RFC 2627 Key Management for Multicast June 1999 + + + 1. What are the security requirements of the group members? Most + likely there will be some group controller, or controllers. Do + the other members possess the same security requirements as the + controller(s)? + + 2. Interdomain issues - When crossing from one "group domain" to + another domain with a potentially different security policy, + which policy is enforced? An example would be two users + wishing to communicate, but having different cryptoperiods + and/or key length policies. + + 3. How does the formation of the multicast group occur? Will the + group controller initiate the user joining process, or will the + users initiate when they join the formation of the multicast + group? + + 4. How does one handle the case where certain group members have + inferior processing capabilities which could delay the + formation of the net key? Do these users delay the formation + of the whole multicast group, or do they come on-line later + enabling the remaining participants to be brought up more + quickly? + + 5. One must minimize the number of bits required for multicast + group net key distribution. This greatly impacts bandwidth + limited equipments. + + All of these and other issues need to be taken into account, along + with the communication protocols that will be used which support the + desired multicast capability. The next section addresses some of + these issues and presents some candidate architectures that could be + used to tackle the key management problem for multicasting. + +5.0 CANDIDATE ARCHITECTURES + + There are several basic functions that must be performed in order for + a secure multicast session to occur. The order in which these + functions will be performed, and the efficiency of the overall + solution results from making trade-offs of the various factors listed + above. Before looking at specific architectures, these basic + functions will be outlined, along with some definition of terms that + will be used in the representative architectures. These definitions + and functions are as follows: + + + + + + + + +Wallner, et al. Informational [Page 5] + +RFC 2627 Key Management for Multicast June 1999 + + + 1. Someone determines the need for a multicast session, sets the + security attributes for that particular session (e.g., + classification levels of traffic, algorithms to be used, key + variable bit lengths, etc.), and creates the group access + control list which we will call the initial multicast group + participant list. The entity which performs these functions + will be called the INITIATOR. At this point, the multicast + group participant list is strictly a list of users who the + initiator wants to be in the multicast group. + + 2. The initiator determines who will control the multicast group. + This controller will be called the ROOT (or equivalently the + SERVER). Often, the initiator will become the root, but the + possibility exists where this control may be passed off to + someone other than the initiator. (Some key management + architectures employ multiple roots, see [4].) The root's job + is to perform the addition and deletion of group participants, + perform user access control against the security attributes of + that session, and distribute the traffic encryption key for the + session which we will call the multicast group NET KEY. After + initialization, the entity with the authority to accept or + reject the addition of future group participants, or delete + current group participants is called the LIST CONTROLLER. + + This may or may not be the initiator. The list controller has + been distinguished from the root for reasons which will become + clear later. In short, it may be desirable for someone to have + the authority to accept or reject new members, while another + party (the root) would actually perform the function. + + 3. Every participant in the multicast session will be referred to + as a GROUP PARTICIPANT. Specific group participants other than + the root or list controller will be referred to as LEAVES. + + 4. After the root checks the security attributes of the + participants listed on the multicast group participant list to + make sure that they all support the required security + attributes, the root will then pass the multicast group list to + all other participants and create and distribute the Net Key. + If a participant on the multicast group list did not meet the + required security attributes, the leaf must be deleted from the + list. + + Multiple issues can be raised with the distribution of the + multicast group list and Net Key. + + + + + + +Wallner, et al. Informational [Page 6] + +RFC 2627 Key Management for Multicast June 1999 + + + a. An issue exists with the time ordering of these functions. + The multicast group list could be distributed before or + after the link is secured (i.e. the Net Key is + distributed). + + b. An issue exists when a leaf refuses to join the session. + If a leaf refuses to join a session, we can send out a + modified list before sending out the Net Key, however + sending out modified lists, potentially multiple times, + would be inefficient. Instead, the root could continue + on, and would not send the Net Key to those participants + on the list who rejected the session. + + For the scenario architectures which follow, we assume the + multicast group list will be distributed to the group + participants once before the Net Key is distributed. Unlike + the scheme described in [4], we recommend that the multicast + group participant list be provided to all leaves. By + distributing this list to the leaves, it allows them to + determine upfront whether they desire to participate in the + multicast group or not, thus saving potentially unnecessary + key exchanges. + + Four potential key management architectures to distribute keying + material for multicast sessions are presented. Recall that the + features that are highly desirable for the architecture to possess + include the time required to setup the multicast group should be + minimized, the number of transmissions should be minimized, and + memory/storage requirements should be minimized. As will be seen, the + first three proposals each fall short in a different aspect of these + desired qualities, whereas the fourth proposal appears to strike a + balance in the features desired. Thus, the fourth proposal is the + one recommended for general implementation and use. + + Please note that these approaches also address securely eliminating + users from the multicast group, but don't specifically address adding + new users to the multicast group following initial setup because this + is viewed as evident as to how it would be performed. + +5.1 MANUAL KEY DISTRIBUTION + + Through manual key distribution, symmetric key is delivered without + the use of public key exchanges. To set up a multicast group Net Key + utilizing manual key distribution would require a sequence of events + where Net Key and spare Net Keys would be ordered by the root of the + multicast session group. Alternate (supersession) Net Keys are + ordered (by the root) to be used in case of a compromise of a group + participant(s). The Net Keys would be distributed to each individual + + + +Wallner, et al. Informational [Page 7] + +RFC 2627 Key Management for Multicast June 1999 + + + group participant, often through some centralized physical + intermediate location. At some predetermined time, all group + participants would switch to the new Net Key. Group participants use + this Net Key until a predetermined time when they need another new + Net Key. If the Net Key is compromised during this time, the + alternate Net Key is used. Group participants switch to the alternate + Net Key as soon as they receive it, or upon notification from the + root that everyone has the new Net Key and thus the switch over + should take place. This procedure is repeated for each cryptoperiod. + + A scheme like this may be attractive because the methods exist today + and are understood by users. Unfortunately, this type of scheme can + be time consuming to set up the multicast group based on time + necessary to order keying material and having it delivered. For most + real time scenarios, this method is much too slow. + +5.2 N Root/Leaf Pairwise Keys Approach + + This approach is a brute force method to provide a common multicast + group Net Key to the group participants. In this scheme, the + initiator sets the security attributes for a particular session, + generates a list of desired group participants and transmits the list + to all group participants. The leaves then respond with an initial + acceptance or rejection of participation. By sending the list up + front, time can be saved by not performing key exchanges with people + who rejected participation in the session. The root (who for this + and future examples is assumed to be the initiator) generates a + pairwise key with one of the participants (leaves) in the multicast + group using some standard public key exchange technique (e.g., a + Diffie-Hellman public key exchange.) The root will then provide the + security association parameters of the multicast (which may be + different from the parameters of the initial pairwise key) to this + first leaf. Parameters may include items such as classification and + policy. Some negotiation (through the use of a Security Association + Management Protocol, or SAMP) of the parameters may be necessary. + The possibility exists for the leaf to reject the connection to the + multicast group based on the above parameters and multicast group + list. If the leaf rejects this session, the root will repeat this + process with another leaf. + + Once a leaf accepts participation in the multicast session, these two + then choose a Net Key to be used by the multicast group. The Net Key + could be generated through another public key exchange between the + two entities, or simply chosen by the root, depending upon the policy + which is in place for the multicast group ( i.e. this policy decision + will not be a real time choice). The issue here is the level of + trust that the leaf has in the root. If the initial pairwise key + exchange provides some level of user authentication, then it seems + + + +Wallner, et al. Informational [Page 8] + +RFC 2627 Key Management for Multicast June 1999 + + + adequate to just have the root select the Net Key at this stage. + Another issue is the level of trust in the strength of the security + of the generated key. Through a cooperative process, both entities + (leaf and root) will be providing information to be used in the + formation of the Net Key. + + The root then performs a pairwise key exchange with another leaf and + optionally performs the negotiation discussed earlier. Upon + acceptance by the leaf to join the multicast group, the root sends + the leaf the Net Key. + + This pairwise key exchange and Net Key distribution continues for all + N users of the multicast group. + + Root/leaves cache pairwise keys for future use. These keys serve as + Key Encryption Keys (KEKs) used for rekeying leaves in the net at a + later time. Only the root will cache all of the leaves' pairwise + keys. Each individual leaf will cache only its own unique pairwise + Key Encryption Key. + + There are two cases to consider when caching the KEKs. The first + case is when the Net key and KEK are per session keys. In this case, + if one wants to exclude a group participant from the multicast + session (and rekey the remaining participants with a new Net Key), + the root would distribute a new Net key encrypted with each + individual KEK to every legitimate remaining participant. These KEKs + are deleted once the multicast session is completed. + + The second case to consider is when the KEKs are valid for more than + one session. In this case, the Net Key may also be valid for + multiple sessions, or the Net Key may still only be valid for one + session as in the above case. Whether the Net Key is valid for one + session or more than one session, the KEK will be cached. If the Net + Key is only valid per session, the KEKs will be used to encrypt new + Net Keys for subsequent multicast sessions. The deleting of group + participants occurs as in the previous case described above, + regardless of whether the Net Key is per session or to be used for + multiple sessions. + + A scheme like this may be attractive to a user because it is a + straightforward extension of certifiable public key exchange + techniques. It may also be attractive because it does not involve + third parties. Only the participants who are part of the multicast + session participate in the keying mechanism. What makes this scheme + so undesirable is that it will be transmission intensive as we scale + + + + + + +Wallner, et al. Informational [Page 9] + +RFC 2627 Key Management for Multicast June 1999 + + + up in numbers, even for the most computationally efficient + participants, not to mention those with less capable hardware + (tactical, wireless, etc.). Every time the need arises to drop an + "unauthorized" participant, a new Net Key must be distributed. + + This distribution requires a transmission from the Root to each + remaining participant, whereby the new Net Key will be encrypted + under the cover of each participant's unique pairwise Key Encryption + Key (KEK). + + Note: This approach is essentially the same as one proposal to the + Internet Engineering Task Force (IETF) Security Subworking Group [Ref + 1,2]. + + Also note that there exist multiple twists to an approach like this. + For example, instead of having the root do all N key exchanges, the + root could pass some of this functionality (and control) to a number + of leaves beneath him. For example, the multicast group list could + be split in half and the root tells one leaf to take half of the + users and perform a key exchange with them (and then distribute the + Net key) while the root will take care of the other half of the list. + (The chosen leaves are thus functioning as a root and we can call + them "subroots." These subroots will have leaves beneath them, and + the subroots will maintain the KEK of each leaf beneath it.) This + scales better than original approach as N becomes large. + Specifically, it will require less time to set up (or rekey) the + multicast net because the singular responsibility of performing + pairwise key exchanges and distributing Net Key will be shared among + multiple group participants and can be performed in parallel, as + opposed to the root only distributing the Net Key to all of the + participants. + + This scheme is not without its own security concerns. This scheme + pushes trust down to each subgroup controller - the root assumes that + these "subroot" controllers are acting in a trustworthy way. Every + control element (root and subroots) must remain in the system + throughout the multicast. This effectively makes removing someone + from the net (especially the subroots) harder and slower due to the + distributed control. When removing a participant from the multicast + group which has functioned on behalf of the root, as a subroot, to + distribute Net Key, additional steps will be necessary. A new + subroot must be delegated by the root to replace the removed subroot. + A key exchange (to generate a new pairwise KEK) must occur between + the new subroot and each leaf the removed subroot was responsible + for. A new Net Key will now be distributed from the root, to the + subroots, and to the leaves. Note that this last step would have + been the only step required if the removed party was a leaf with no + controlling responsibilities. + + + +Wallner, et al. Informational [Page 10] + +RFC 2627 Key Management for Multicast June 1999 + + +5.3 COMPLEMENTARY VARIABLE APPROACH + + Let us suppose we have N leaves. The Root performs a public key + exchange with each leaf i (i= 1,2, ..., N). The Root will cache each + pairwise KEK. Each leaf stores their own KEK. The root would provide + the multicast group list of participants and attributes to all users. + Participants would accept or reject participation in the multicast + session as described in previous sections. The root encrypts the Net + Key for the Multicast group to each leaf, using their own unique + KEK(i). (The Root either generated this Net Key himself, or + cooperatively generated with one of the leaves as was discussed + earlier). In addition to the encrypted Net Key, the root will also + encrypt something called complementary variables and send them to the + leaves. + + A leaf will NOT receive his own complementary variable, but he will + receive the other N-1 leaf complementary variables. The root sends + the Net Key and complementary variables j, where j=1,2,...,N and j + not equal to i, encrypted by KEK(i) to each leaf. Thus, every leaf + receives and stores N variables which are the Net key, and N-1 + complementary variables. + + Thus to cut a user from the multicast group and get the remaining + participants back up again on a new Net Key would involve the + following. Basically, to cut leaf number 20 out of the net, one + message is sent out that says "cut leaf 20 from the net." All of the + other leaves (and Root) generate a new Net Key based on the current + Net Key and Complementary variable 20. [Thus some type of + deterministic key variable generation process will be necessary for + all participants of the multicast group]. This newly generated + variable will be used as the new Net Key by all remaining + participants of the multicast group. Everyone except leaf 20 is able + to generate the new Net Key, because they have complementary variable + 20, but leaf 20 does not. + + A scheme like this seems very desirable from the viewpoint of + transmission savings since a rekey message encrypted with each + individual KEK to every leaf does not have to be sent to delete + someone from the net. In other words, there will be one plaintext + message to the multicast group versus N encrypted rekey messages. + There exists two major drawbacks with this scheme. First are the + storage requirements necessary for the (N-1) complementary variables. + Secondly, when deleting multiple users from the multicast group, + collusion will be a concern. What this means is that these deleted + users could work together and share their individual complementary + variables to regain access to the multicast session. + + + + + +Wallner, et al. Informational [Page 11] + +RFC 2627 Key Management for Multicast June 1999 + + +5.4 HIERARCHICAL TREE APPROACH + + The Hierarchical Tree Approach is our recommended approach to address + the multicast key management problem. This approach provides for the + following requisite features: + + 1. Provides for the secure removal of a compromised user from the + multicast group + + 2. Provides for transmission efficiency + + 3. Provides for storage efficiency + + This approach balances the costs of time, storage and number of + required message transmissions, using a hierarchical system of + auxiliary keys to facilitate distribution of new Net Key. The result + is that the storage requirement for each user and the transmissions + required for key replacement are both logarithmic in the number of + users, with no background transmissions required. This approach is + robust against collusion of excluded users. Moreover, while the + scheme is hierarchical in nature, no infrastructure is needed beyond + a server (e.g., a root), though the presence of such elements could + be used to advantage (See Figure 1). + + -------------------------- + | | + | S E R V E R | + | | + -------------------------- + | | | + | | . . . . | + - - - + |1| |2| |n| + - - - + + + Figure 1: Assumed Communication Architecture + + The scheme, advantages and disadvantages are enumerated in more + detail below. Consider Figure 2 below. This figure illustrates the + logical key distribution architecture, where keys exist only at the + server and at the users. Thus, the server in this architecture would + hold Keys A through O, and the KEKs of each user. User 11 in this + architecture would hold its own unique KEK, and Keys F, K, N, and O. + + + + + + + +Wallner, et al. Informational [Page 12] + +RFC 2627 Key Management for Multicast June 1999 + + + net key Key O + ------------------------------------- + intermediate | | + keys | | + Key M Key N + ----------------- -------------------- + | | | | + | | | | + Key I Key J Key K Key L + -------- -------- --------- ---------- + | | | | | | | | + | | | | | | | | + Key A Key B Key C Key D Key E Key F Key G Key H + --- --- --- --- --- ---- ---- ---- + | | | | | | | | | | | | | | | | + - - - - - - - - - -- -- -- -- -- -- -- +|1| |2| |3| |4| |5| |6| |7| |8| |9| |10| |11| |12| |13| |14| |15| |16| + - - - - - - - - - -- -- -- -- -- -- -- + users + + + + Figure 2: Logical Key Distribution Architecture + + We now describe the organization of the key hierarchy and the setup + process. It will be clear from the description how to add users + after the hierarchy is in place; we will also describe the removal of + a user. Note: The passing of the multicast group list and any + negotiation protocols is not included in this discussion for + simplicity purposes. + + We construct a rooted tree (from the bottom up) with one leaf + corresponding to each user, as in Figure 2. (Though we have drawn a + balanced binary tree for convenience, there is no need for the tree + to be either balanced or binary - some preliminary analysis on tree + shaping has been performed.) Each user establishes a unique pairwise + key with the server. For users with transmission capability, this can + be done using the public key exchange protocol. The situation is more + complicated for receive-only users; it is easiest to assume these + users have pre-placed key. + + Once each user has a pairwise key known to the server, the server + generates (according to the security policy in place for that + session) a key for each remaining node in the tree. The keys + themselves should be generated by a robust process. We will also + assume users have no information about keys they don't need. (Note: + There are no users at these remaining nodes, (i.e., they are logical + nodes) and the key for each node need only be generated by the server + + + +Wallner, et al. Informational [Page 13] + +RFC 2627 Key Management for Multicast June 1999 + + + via secure means.) Starting with those nodes all of whose children + are leaves and proceeding towards the root, the server transmits the + key for each node, encrypted using the keys for each of that node's + children. At the end of the process, each user can determine the + keys corresponding to those nodes above her leaf. In particular, all + users hold the root key, which serves as the common Net Key for the + group. The storage requirement for a user at depth d is d+1 keys + (Thus for the example in Figure 2, a user at depth d=4 would hold + five keys. That is, the unique Key Encryption Key generated as a + result of the pairwise key exchange, three intermediate node keys - + each separately encrypted and transmitted, and the common Net Key for + the multicast group which is also separately encrypted.) + + It is also possible to transmit all of the intermediate node keys and + root node key in one message, where the node keys would all be + encrypted with the unique pairwise key of the individual leaf. In + this manner, only one transmission (of a larger message) is required + per user to receive all of the node keys (as compared to d + transmissions). It is noted for this method, that the leaf would + require some means to determine which key corresponds to which node + level. + + It is important to note that this approach requires additional + processing capabilities at the server where other alternative + approaches may not. In the worst case, a server will be responsible + for generating the intermediate keys required in the architecture. + +5.4.1 The Exclusion Principle + + Suppose that User 11 (marked on Figure 2 in black) needs to be + deleted from the multicast group. Then all of the keys held by User + 11 (bolded Keys F, K, N, O) must be changed and distributed to the + users who need them, without permitting User 11 or anyone else from + obtaining them. To do this, we must replace the bolded keys held by + User 11, proceeding from the bottom up. The server chooses a new key + for the lowest node, then transmits it encrypted with the appropriate + daughter keys (These transmissions are represented by the dotted + lines). Thus for this example, the first key replaced is Key F, and + this new key will be sent encrypted with User 12's unique pairwise + key. + + Since we are proceeding from the bottom up, each of the replacement + keys will have been replaced before it is used to encrypt another + key. (Thus, for the replacement of Key K, this new key will be sent + encrypted in the newly replaced Key F (for User 12) and will also be + sent as one multicast transmission encrypted in the node key shared + by Users 9 and 10 (Key E). For the replacement of Key N, this new key + will be sent encrypted in the newly replaced Key K (for Users 9, 10, + + + +Wallner, et al. Informational [Page 14] + +RFC 2627 Key Management for Multicast June 1999 + + + and 12) and will also be encrypted in the node key shared by Users + 13, 14, 15, and 16 (Key L). For the replacement of Key O, this new + key will be sent encrypted in the newly replaced Key N (for Users 9, + 10, 12, 13, 14, 15, and 16) and will also be encrypted in the node + key shared by Users 1, 2 , 3, 4, 5, 6, 7, and 8 (Key M).) The number + of transmissions required is the sum of the degrees of the replaced + nodes. In a k-ary tree in which a sits at depth d, this comes to at + most kd-1 transmissions. Thus in this example, seven transmissions + will be required to exclude User 11 from the multicast group and to + get the other 15 users back onto a new multicast group Net Key that + User 11 does not have access to. It is easy to see that the system + is robust against collusion, in that no set of users together can + read any message unless one of them could have read it individually. + + If the same strategy is taken as in the previous section to send + multiple keys in one message, the number of transmissions required + can be reduced even further to four transmissions. Note once again + that the messages will be larger in the number of bits being + transmitted. Additionally, there must exist a means for each leaf to + determine which key in the message corresponds to which node of the + hierarchy. Thus, in this example, for the replacement of keys F, K, + N, and O to User 12, the four keys will be encrypted in one message + under User 12's unique pairwise key. To replace keys K, N, and O for + Users 9 and 10, the three keys will be encrypted in one message under + the node key shared by Users 9 and 10 (Key E). To replace keys N and + O for Users 13, 14, 15, 16, the two keys will be encrypted in one + message under the node key shared by Users 13, 14, 15, and 16 (Key + L). Finally, to replace key O for Users 1, 2 , 3, 4, 5, 6, 7, and 8, + key O will be encrypted under the node key shared by Users 1, 2 , 3, + 4, 5, 6, 7, and 8 (Key M). Thus the number of transmission required + is at most (k-1)d. + + The following table demonstrates the removal of a user, and how the + storage and transmission requirements grow with the number of users. + + + + + + + + + + + + + + + + + +Wallner, et al. Informational [Page 15] + +RFC 2627 Key Management for Multicast June 1999 + + +Table 1: Storage and Transmission Costs + +Number Degree Storage per user Transmissions to Transmissions +of users (k) (d+1) rekey remaining to rekey + participants of remaining + multicast group- participants of + one key per message multicast + (kd-1) group - + multiple keys + per message + (k-1)d + 8 2 4 5 3 + 9 3 3 5 4 + 16 2 5 7 4 + 2048 2 12 21 11 + 2187 3 8 20 14 +131072 2 18 33 17 +177147 3 12 32 22 + +The benefits of a scheme such as this are: + + 1. The costs of user storage and rekey transmissions are balanced + and scalable as the number of users increases. This is not the + case for [1], [2], or [4]. + + 2. The auxiliary keys can be used to transmit not only other keys, + but also messages. Thus the hierarchy can be designed to place + subgroups that wish to communicate securely (i.e. without + transmitting to the rest of the large multicast group) under + particular nodes, eliminating the need for maintenance of + separate Net Keys for these subgroups. This works best if the + users operate in a hierarchy to begin with (e.g., military + operations), which can be reflected by the key hierarchy. + + 3. The hierarchy can be designed to reflect network architecture, + increasing efficiency (each user receives fewer irrelevant + messages). Also, server responsibilities can be divided up + among subroots (all of which must be secure). + + 4. The security risk associated with receive-only users can be + minimized by collecting such users in a particular area of the + tree. + + 5. This approach is resistant to collusion among arbitrarily many + users. + + + + + + +Wallner, et al. Informational [Page 16] + +RFC 2627 Key Management for Multicast June 1999 + + + As noted earlier, in the rekeying process after one user is + compromised, in the case of one key per message, each replaced key + must be decrypted successfully before the next key can be replaced + (unless users can cache the rekey messages). This bottleneck could + be a problem on a noisy or slow network. (If multiple users are being + removed, this can be parallelized, so the expected time to rekey is + roughly independent of the number of users removed.) + + By increasing the valences and decreasing the depth of the tree, one + can reduce the storage requirements for users at the price of + increased transmissions. For example, in the one key per message + case, if n users are arranged in a k-ary tree, each user will need + storage. Rekeying after one user is removed now requires + transmissions. As k approaches n, this approaches the pairwise key + scheme described earlier in the paper. + +5.4.2 Hierarchical Tree Approach Options + +5.4.2.1 Distributed Hierarchical Tree Approach + + The Hierarchical Tree Approach outlined in this section could be + distributed as indicated in Section 5.2 to more closely resemble the + proposal put forth in [4]. Subroots could exist at each of the nodes + to handle any joining or rekeying that is necessary for any of the + subordinate users. This could be particularly attractive to users + which do not have a direct connection back to the Root. Recall as + indicated in Section 5.2, that the trust placed in these subroots to + act with the authority and security of a Root, is a potentially + dangerous proposition. This thought is also echoed in [4]. + + Some practical recommendations that might be made for these subroots + include the following. The subroots should not be allowed to change + the multicast group participant list that has been provided to them + from the Root. One method to accomplish this, would be for the Root + to sign the list before providing it to the subroots. Authorized + subroots could though be allowed to set up new multicast groups for + users below them in the hierarchy. + + It is important to note that although this distribution may appear to + provide some benefits with respect to the time required to initialize + the multicast group (as compared to the time required to initialize + the group as described in Section 5.4) and for periodic rekeying, it + does not appear to provide any benefit in rekeying the multicast + group when a user has been compromised. + + It is also noted that whatever the key management scheme is + (hierarchical tree, distributed hierarchical tree, core based tree, + GKMP, etc.), there will be a "hit" incurred to initialize the + + + +Wallner, et al. Informational [Page 17] + +RFC 2627 Key Management for Multicast June 1999 + + + multicast group with the first multicast group net key. Thus, the + hierarchical tree approach does not suffer from additional complexity + with comparison to the other schemes with respect to initialization. + +5.4.2.2 Multicast Group Formation + + Although this paper has presented the formation of the multicast + group as being Root initiated, the hierarchical approach is + consistent with user initiated joining. User initiated joining is + the method of multicast group formation presented in [4]. User + initiated joining may be desirable when some core subset of users in + the multicast group need to be brought up on-line and communicating + more quickly. Other participants in the multicast group can then be + brought in when they wish. In this type of approach though, there + does not exist a finite period of time by when it can be ensured all + participants will be a part of the multicast group. + + For example, in the case of a single root, the hierarchy is set up + once, in the beginnning, by the initiator (also usually the root) who + also generates the group participant list. The group of keys for each + participant can then be individually requested (pulled) as soon as, + but not until, each participant wishes to join the session. + +5.4.2.3 Sender Specific Authentication + + In the multicast environment, the possibility exists that + participants of the group at times may want to uniquely identify + which participant is the sender of a multicast group message. In the + multicast key distribution system described by Ballardie [4], the + notion of "sender specific keys" is presented. + + Another option to allow participants of a multicast group to uniquely + determine the sender of a message is through the use of a signature + process. When a member of the multicast group signs a message with + their own private signature key, the recipients of that signed + message in the multicast group can use the sender's public + verification key to determine if indeed the message is from who it is + claimed to be from. + + Another related idea to this is the case when two users of a + multicast group want to communicate strictly with each other, and + want no one else to listen in on the communication. If this + communication relationship is known when the multicast group is + originally set up, then these two participants could simply be placed + adjacent to one another at the lowest level of the hierarchy (below a + binary node). Thus, they would naturally share a secret pairwise + key. Otherwise, a simple way to accomplish this is to perform a + public key based pairwise key exchange between the two users to + + + +Wallner, et al. Informational [Page 18] + +RFC 2627 Key Management for Multicast June 1999 + + + generate a traffic encryption key for their private unicast + communications. Through this process, not only will the encrypted + transmissions between them be readable only by them, but unique + sender authentication can be accomplished via the public key based + pairwise exchange. + +5.4.2.4 Rekeying the Multicast Group and the Use of Group Key + Encryption Keys + + Reference [4] makes use of a Group Key Encryption Key that can be + shared by the multicast group for use in periodic rekeys of the + multicast group. Aside from the potential security drawbacks of + implementing a shared key for encrypting future keys, the use of a + Group Key Encryption Key is of no benefit to a multicast group if a + rekey is necessary due to the known compromise of one of the members. + The strategy for rekeying the multicast group presented in Section + 5.4.1 specifically addresses this critical problem and offers a means + to accomplish this task with minimal message transmissions and + storage requirements. + + The question though can now be asked as to whether the rekey of a + multicast group will be necessary in a non-compromise scenario. For + example, if a user decides they do not want to participate in the + group any longer, and requests the list controller to remove them + from the multicast group participant list, will a rekey of the + multicast group be necessary? If the security policy of the + multicast group mandates that deleted users can no longer receive + transmissions, than a rekey of a new net key will be required. If + the multicast group security policy does not care that the deleted + person can still decrypt any transmissions (encrypted in the group + net key that they might still hold), but does care that they can not + encrypt and transmit messages, a rekey will once again be necessary. + The only alternative to rekeying the multicast group under this + scenario would require a recipient to check every received message + sender, against the group participant list. Thus rejecting any + message sent by a user not on the list. This is not a practical + option. Thus it is recommended to always rekey the multicast group + when someone is deleted, whether it is because of compromise reasons + or not. + +5.4.2.5 Bulk Removal of Participants + + As indicated in Section 2, the need may arise to remove users in + bulk. If the users are setup as discussed in Section 5.4.1 into + subgroups that wish to communicate securely all being under the same + node, bulk user removal can be done quite simply if the whole node is + to be removed. The same technique as described in Section 5.4.1 is + performed to rekey any shared node key that the remaining + + + +Wallner, et al. Informational [Page 19] + +RFC 2627 Key Management for Multicast June 1999 + + + participants hold in common with the removed node. + + The problem of bulk removal becomes more difficult when the + participants to be removed are dispersed throughout the tree. + Depending on how many participants are to be removed, and where they + are located within the hierarchy, the number of transmissions + required to rekey the multicast group could be equivalent to brute + force rekeying of the remaining participants. Also the question can + be raised as to at what point the remaining users are restructured + into a new hierarchical tree, or should a new multicast group be + formed. Restructuring of the hierarchical tree would most likely be + the preferred option, because it would not necessitate the need to + perform pairwise key exchanges again to form the new user unique + KEKs. + +5.4.2.6 ISAKMP Compatibility + + Thus far this document has had a major focus on the architectural + trade-offs involved in the generation, distribution, and maintenance + of traffic encryption keys (Net Keys) for multicast groups. There + are other elements involved in the establishment of a secure + connection among the multicast participants that have not been + discussed in any detail. For example, the concept of being able to + "pick and choose" and negotiating the capabilities of the key + exchange mechanism and various other elements is a very important and + necessary aspect. + + The NSA proposal to the Internet Engineering Task Force (IETF) + Security Subworking Group [Ref. 3] entitled "Internet Security + Association and Key Management Protocol (ISAKMP)" has attempted to + identify the various functional elements required for the + establishment of a secure connection for the largest current network, + the Internet. While the proposal has currently focused on the + problem of point to point connections, the functional elements should + be the same for multicast connections, with appropriate changes to + the techniques chosen to implement the individual functional + elements. Thus the implementation of ISAKMP is compatible with the + use of the hierarchical tree approach. + +6.0 SUMMARY + + As discussed in this report, there are two main areas of concern when + addressing solutions for the multicast key management problem. They + are the secure initialization and rekeying of the multicast group + with a common net key. At the present time, there are multiple + papers which address the initialization of a multicast group, but + they do not adequately address how to efficiently and securely remove + a compromised user from the multicast group. + + + +Wallner, et al. Informational [Page 20] + +RFC 2627 Key Management for Multicast June 1999 + + + This paper proposed a hierarchical tree approach to meet this + difficult problem. It is robust against collusion, while at the same + time, balancing the number of transmissions required and storage + required to rekey the multicast group in a time of compromise. + + It is also important to note that the proposal recommended in this + paper is consistent with other multicast key management solutions + [4], and allows for multiple options for its implementation. + +7.0 Security Considerations + + Security concerns are discussed throughout this memo. + +8.0 REFERENCES + + 1. Harney, H., Muckenhirn, C. and T. Rivers, "Group Key Management + Protocol Architecture", RFC 2094, September 1994. + + 2. Harney, H., Muckenhirn, C. and T. Rivers, "Group Key Management + Protocol Specification", RFC 2093, September 1994. + + 3. Maughan, D., Schertler, M. Schneider, M. and J.Turner, "Internet + Security Association and Key Management Protocol, Version 7", + February 1997. + + 4. Ballardie, T., "Scalable Multicast Key Distribution", RFC 1949, + May 1996. + + 5. Wong, C., Gouda, M. and S. Lam, "Secure Group Communications Using + Key Graphs", Technical Report TR 97-23, Department of Computer + Sciences, The University of Texas at Austin, July 1997. + + + + + + + + + + + + + + + + + + + + +Wallner, et al. Informational [Page 21] + +RFC 2627 Key Management for Multicast June 1999 + + +Authors' Addresses + + Debby M. Wallner + National Security Agency + Attn: R2 + 9800 Savage Road STE 6451 + Ft. Meade, MD. 20755-6451 + + Phone: 301-688-0331 + EMail: dmwalln@orion.ncsc.mil + + + Eric J. Harder + National Security Agency + Attn: R2 + 9800 Savage Road STE 6451 + Ft. Meade, MD. 20755-6451 + + Phone: 301-688-0850 + EMail: ejh@tycho.ncsc.mil + + + Ryan C. Agee + National Security Agency + Attn: R2 + 9800 Savage Road STE 6451 + Ft. Meade, MD. 20755-6451 + + + + + + + + + + + + + + + + + + + + + + + + +Wallner, et al. Informational [Page 22] + +RFC 2627 Key Management for Multicast June 1999 + + +Full Copyright Statement + + Copyright (C) The Internet Society (1999). All Rights Reserved. + + This document and translations of it may be copied and furnished to + others, and derivative works that comment on or otherwise explain it + or assist in its implementation may be prepared, copied, published + and distributed, in whole or in part, without restriction of any + kind, provided that the above copyright notice and this paragraph are + included on all such copies and derivative works. However, this + document itself may not be modified in any way, such as by removing + the copyright notice or references to the Internet Society or other + Internet organizations, except as needed for the purpose of + developing Internet standards in which case the procedures for + copyrights defined in the Internet Standards process must be + followed, or as required to translate it into languages other than + English. + + The limited permissions granted above are perpetual and will not be + revoked by the Internet Society or its successors or assigns. + + This document and the information contained herein is provided on an + "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING + TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING + BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION + HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF + MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + + + + + + + + + + + + + +Wallner, et al. Informational [Page 23] + |