Internet Engineering Task Force Michael P. Howarth INTERNET-DRAFT Sunil Iyengar draft-irtf-gsec-lifecycle-00.txt Haitham Cruickshank July 2003 Zhili Sun University of Surrey, UK Expires end Jan 2004 Life cycle key management costs in secure multicast Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. ABSTRACT This Internet-Draft considers efficient key management for encrypted multicast traffic in large groups, where the group size and dynamics have a significant impact on the network load. We consider the life cycle key management costs of a multicast connection, and show for a Logical Key Hierarchy (LKH) how member pre-registration and periodic admission reduces the initialization cost, and how the optimum outdegree of a hierarchical tree varies with the expected member volatility and rekey factor. 1. INTRODUCTION Key management is a particular issue in securing multicast connections; this needs to scale effectively, particularly given the large number of multicast recipients (potentially of the order of millions). A number of scalable approaches have been proposed, and one in particular, Logical Key Hierarchy (LKH), is analyzed in detail here. We introduce the concept of the life cycle key distribution cost. This takes account not only of the cost of rekeying when users join or leave an established group, but also considers the costs of building a tree during initialization of a multicast group. We show for a Logical Key Hierarchy (LKH) how user pre-registration and periodic admission reduces this initialization cost, and show how the optimum outdegree of a hierarchical tree varies with the expected user volatility and rekey factor. Other authors have shown [15] that when a rekey occurs after each join or depart, a lower bound on the worst case key update costs is a logarithmic variation with group membership, N. Our work on the other hand, whilst conforming to this logarithmic function, shows how the optimum value of the tree outdegree k varies with the expected rekey frequency, taking into account both the cost of initially building the tree and the cost of rekeying over the lifetime of the multicast group. In [12] the optimum number of keys assigned to each group member is related to the probability of deletion of the individual member. Here, we assume each member is equally likely to join or leave the group, giving a tree with equal numbers of keys for each member. This Internet-Draft is organized as follows. Section 2 reviews related work in key management for multicast group security. In Section 3 we briefly review the operation of LKH in key management. Section 4 presents an analysis of life cycle key distribution costs. 2. RELATED WORK: KEY MANAGEMENT FOR MULTICAST TRAFFIC The process of securing and performing key management for unicast connections is well understood [5], [7], [11], but multicast security is more complex. In principle, a multicast connection could be regarded from the security perspective as a set of unicast connections, but this approach does not scale well for large groups. Protocols that manage the process of distributing keys in a multicast environment are under development [1], [3], [6]. The principal actors in multicast key management are the group controller (GC) and group members (GMs). The former is responsible for creating and distributing keys and rekeying (to maintain security) as appropriate; the group members are entities with access to the group keys. The GC need not be co-located with the multicast data source. Each group member has an initial one-to-one secure association with the group controller (using techniques such as Diffie-Hellman to create a shared secret known only to the two parties; or a pre-shared secret; or secret exchange using a public key system [13]). These secure associations are then used to create and share information about a group secure association between the group controller and all group members. The ultimate aim of the group secure association is to ensure that a single key, usually called the group traffic encryption key (GTEK), is known to the GC and all GMs, and to no entity outside the group: this key can then be used to encrypt the data multicast within the group. The multicast group may need to be rekeyed for any of a number of reasons: (1) The group key is usually updated regularly (typically every few seconds or minutes) to reduce the probability of successful cryptanalysis of the encrypted traffic. (2) The group key may also need to be changed on demand if it is determined that the key has been compromised. (3) Rekeying may be required when a new member joins the multicast group. This ensures that the member cannot decrypt encoded traffic sent prior to their joining (backward secrecy). (4) Rekeying may be required when an existing member departs from the multicast group. This ensures that the member cannot decrypt encoded traffic sent after they leave (forward secrecy). For large multicast groups that have frequent membership changes the cost of rekeying can be significant. Scalable rekeying is therefore an important problem that needs to be considered in order to support secure communications for large dynamic groups. We now consider rekey techniques for each of the four functions listed above. Several techniques exist for rekeying (1) and (3) above: two options are for the new group key to be encrypted with either (a) the old group key, or (b) a separate "control" key negotiated during session establishment. For (2) and (4) above a different rekeying approach is required since the old key is known by at least one user who is no longer to be a recipient of the multicast transmission. We now consider options for this rekeying. A number of multicast key management approaches have been developed with the objective of improving the scalability of group secure associations, by ensuring that parameters grow more slowly than the group size, N. Parameters considered include group controller encryption effort, memory requirements, network traffic, and group members' decryption effort and memory requirements. Key management techniques include a flat system, Iolus [8], the Logical Key Hierarchy, LKH [16], [17], and Kronos [14]. In the simplest approach, a flat system, the GC shares a unique key with each individual group member. The GTEK can then be sent to the members by encrypting it N times with each of the N unique keys. Thus both the GC key encryption load and the rekey traffic increase linearly with N. In Iolus [8], a multicast group is partitioned into several sub-groups. The group controller manages a tree of group sub-controllers, each of which manages a subset of the group membership. The advantage of this mechanism is that the rekey effort is shared between the sub-controllers, but the drawbacks of this approach are the large number of sub-controllers required in large groups, the need to trust the sub-controllers, and the delay caused by the need to rekey traffic as it passes through each sub-controller. LKH, described in more detail below, uses a set of keys arranged in a tree structure to reduce the cost of rekeying. For a tree of outdegree k and depth d, the number of rekeys transmitted on a member compromise is k.logk(N) - 1 where logk(x) means the log to base k of x; this compares favorably with the cost of N = k^d for a flat system. The system is also robust against collusion, in that no set of users together can read any message unless one of them could have read it individually. Improvements to LKH for the specific case of binary trees (k=2) have also been proposed in one-way function trees [2] [9], and by [4]: both these approaches reduce the number of rekeys required in the event of compromise of a user from 2.log2(N) - 1 to log2(N). Kronos is a further approach to reducing rekey traffic in large dynamic multicast groups. This approach recognizes that if two users depart and cause two rekey events to occur, some of the keys that change will be common to the two rekey events. Rekey traffic can therefore be saved by bundling changes together and rekeying, perhaps every few seconds. 3. REVIEW OF LKH Before analyzing LKH in detail, we initially briefly review the simple flat key management system. Consider N pairwise keys each shared between the group controller and one of the N group members (Figure 1): this represents the flat system described in Section 2. The pairwise keys are represented by the numbers, and the group key is represented by 'A'. If the group key is changed the new group key has to be encrypted with each member's unique pairwise key and then sent to that member; each of these encrypted keys is represented by one of the lines drawn in Figure 1. Thus for N members a total of N encrypted keys are generated and transmitted across the network. Key A | | ------------------------------------------------------------- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Figure 1: N pairwise keys (flat system) We contrast this with LKH, where a tree of keys is used. The tree is logical and does not have any mapping onto a physical network layout. In Figure 2 the keys are labeled A through O, each number again represents a member's pairwise key and the lines each represent encrypted keys sent across the network, as we shall now see. The group key is represented by 'O' and each member holds the keys on the path from the member's pairwise key (at a tree leaf) back to the root. Suppose now that Member 11 needs to be deleted from the multicast group. Then all of the keys held by Member 11 (keys F, K, N, O) must be changed and distributed to the members who need them, without permitting Member 11 or other unauthorized entities to obtain them. To do this, we must replace the keys held by Member 11, proceeding from the bottom up. Group 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 Figure 2: Hierarchical key tree The group controller chooses a new key for the lowest node (not the leaf, for which a unicast secure association exists between the GC and the GM), and then transmits it encrypted with the appropriate child keys. Thus for this example, the first key replaced is Key F, and this new key will be sent encrypted with Member 12's unique pairwise key. The second key replaced is Key K, which is sent encrypted with the newly replaced Key F (for Member 12) and also sent encrypted with key E (for Members 9 and 10). Key N is then sent encrypted in the newly replaced Key K (for Members 9, 10, and 12) and also encrypted in key L (shared by Members 13 through 16). Finally, Key O is replaced, and this new key is sent encrypted in the newly replaced Key N (for Members 9, 10, and 12 through 16) and also separately is encrypted in key M (shared by Members 1 to 8). 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. The seven keys sent represent a significant saving on the 16 keys that would need to be transmitted using the flat key system of Figure 1. In general, the number of transmissions required is the sum of the degrees of the replaced nodes. In a fully populated k-ary tree in which a GM sits at depth d, this is a total of k.d - 1 = k.logk(N) - 1 transmissions. The GTEK, used to encrypt data traffic, may, depending on the group security policy, either be key O (Figure 2), or it may be separately encrypted using key O and transmitted to all group members. In the analysis that follows we adopt the former approach and choose not to include the GTEK in the rekey count. 4. LIFE CYCLE COSTS 4.1. Introduction There is an implicit assumption in the LKH literature that user join/ leave rekeying is the principal cost of key management, with tree initialization costs being negligible. However, applications exist (such as file transfer) where the user population has a low volatility, and therefore the tree initialization costs become significant. Also, and distinctly, there may be some multicast groups (e.g. pay-per-view) where subscribers join the group at around the same time, with a high demand on the establishment of the group secure association. For our analysis, we divide the life cycle of a secure group connection into the following phases: * Initialization: members are authenticated to the GC and are issued with keys, including the group key used to encrypt data; * Data transfer: this comprises two rekey activities: o The GTEK is updated regularly, to reduce the probability of successful cryptanalysis of ciphertext; o Rekeying occurs when members join or depart, to ensure perfect backward or forward secrecy respectively, or when a key or member is compromised. * Termination: once the data transfer is complete the secure connection ends. We assume that the keys are simply discarded, since they are of no further use. We assume in this analysis that the entire LKH tree is populated during the initialization phase, that once the initialization phase is complete the LKH tree remains balanced [10] and that it remains nearly full as members join and depart. 4.2. Analysis As each GM joins a group the member is authenticated and a pairwise key for secure communication with the GC is established using a mechanism that in line with current approaches [6] is out of scope of this work. Our metric is the number of encrypted keys transmitted by the source: ignoring protocol overheads this is proportional to the key network traffic. We now consider the initialization cost. Three approaches are considered, in increasing order of cost, with generic cases and numerical examples being shown in Figure 3. For each of the three approaches we may either consider a static tree, in which the tree depth d is assumed fixed in advance; or we may consider a dynamic tree, in which the tree depth grows as the number of members increases, the depth being one when there are not more than k members, two when the number of members lies in the range k+1 to k^2 inclusive, and so forth. The initialization costs for each of the three approaches are as follows: * Case 1: assume each receiver has perfect memory: once a given key has been transmitted any receiver that is given the encoding key (even at a later time) can decrypt the encoded key. Although this assumption is not expected to be valid in practice, it provides a useful comparison in this analysis since it has the lowest initialization cost. As will be seen later it also corresponds to a useful category of tree building. It is shown in Appendix A that for both static and dynamic trees the total number of keys transmitted to admit N users to the group is: B1 = ( N - 1) . k / ( k - 1 ) ~ O(N) (1) * Case 2: transmit all the keys needed by a receiver at the time the receiver joins the group. Users do not require memory of previous transmissions and may even be switched off prior to joining the group. Keys are therefore in general transmitted multiple times, when different users require them. In this case, the total number of keys transmitted to admit N members to the group is O(N.logk(N)) with the exact expressions for a static tree being (Appendix A): B2static = N . logk(N) (2) For a dynamic tree it can be shown that the exact expression is: B2dynamic = ( N + 1 ) . logk(N) - ( N - 1 ) / ( k - 1 ) (3) * Case 3: rekey on each join: this ensures perfect backward secrecy is maintained as the tree is initialized. To ensure perfect backward secrecy as each member joins the group, not only must the group key be changed but also the keys that enable the joining receiver to decrypt ancestor keys must also be changed: if this is not done then a newly joined receiver with memory could obtain the previous group key and therefore decrypt transmissions that occurred prior to the user joining the group. The total number of keys transmitted to admit N users is also O(N.logk(N)), with the expressions for a static tree being (Appendix A): B3static = N . logk(N) . ( k + 1 ) / 2 (4) Again, for a dynamic tree it can be shown that the exact expression is: B3dynamic = N . logk(N) . ( k + 1 ) / 2 - ( N - k ) / (k-1) (5) Group key: Key M | ----------------------------------------------- | | | Key J Key K Key L | | | ----------------- -------------- -------------- | | | | | | Key A Key B Key C Key D . . . . . . . . . Key I | | | | | | ----- ----- ----- ------- ------- | | | | | | | | | | | | | | | 1 2 3 4 5 6 7 8 9 10 11 12 . . 25 26 27 Static tree join costs, for k=d=3: Member number: 1 2 3 4 5 6 7 8 9 10 11 12 . . 25 26 27 Case 1, perfect memory: 3 1 1 2 1 1 2 1 1 3 1 1 . . 2 1 1 Case 2, transmit keys as required: 3 3 3 3 3 3 3 3 3 3 3 3 . . 3 3 3 Case 3, perfect backwards secrecy: 3 4 5 4 5 6 5 6 7 4 5 6 . . 7 8 9 Static tree join costs, generic tree of outdegree k and depth d: Member number: 1 . k k+1 . 2k . . k^2 . . k^d-k+1 . k^d Case 1, perfect memory: d 1 1 2 1 1 . . 1 . . 2 . 1 Case 2, transmit keys as required: d d d d d d . . d . . d . d Case 3, perfect backwards secrecy: d d+1 . . . . . . d+2k-2 . . kd-k+1 . kd Figure 3. Tree initialization approaches 4.3. Implications The perfect memory approach has the lowest tree initialization cost. It also corresponds to a useful way of building a multicast tree: consider a multicast session that is advertised (perhaps using the Session Announcement Protocol, SAP) and for which potential members are invited (or required) to register in advance. Then, at the time the session is due to start the source knows the number N of members, and builds the tree in the following order: all lowest level keys (A..I, Figure 3) are sent encrypted with each recipient's pairwise key, then the second level keys (J..L, Figure 3), and so on up the tree. Each receiver can decrypt each key as it is received, and the tree initialization cost (1) is O(N). The second approach corresponds to members arriving intermittently. In this case the source cannot assume that a newly joining receiver has any key information, and all the keys required by each receiver have to be transmitted, with the initialization cost being O(N.logk(N)). The cost (2), (3) can however be reduced if joining receivers are grouped together (perhaps every few seconds) so that keys can be transmitted together. For example, if (Figure 3) members 25 and 26 join separately six keys are sent. However, if they join simultaneously only four keys are sent. This is similar to periodic rekeying [14], and since here we are predominantly initializing new users the required set of keys will be highly correlated and so significant savings can be realized. The savings for periodic rekeying have been quantified by [18]. 4.4. Volatility We now consider the life cycle cost of the group connection, which we define here as the sum of the cost of initializing the LKH tree and the cost of rekeying during the data transfer phase when group members join or depart. We further define the volatility alpha as the mean number of rekeys per GM. Thus a value of alpha=1 means that on average there is one rekey operation per GM during the lifetime of the secure transmission. The cost of each such rekey is R = k.logk(N) -1 when a GM departs or R = k.logk(N) when a GM joins: these functions have a minimum value at k=3 (noting that k can only take integer values). However, when we include both the initialization and rekey costs the optimum value of k that gives a minimum life cycle cost is different. For each initialization approach, the life cycle cost for static trees is: C1 = B1 + R.N.alpha = ( N - 1 ) . k / (k-1) + alpha . N . ( k . logk(N) - 1 ) (6) C2static = B2static + R.N.alpha = N . logk(N) + alpha . N . ( k . logk(N) - 1 ) (7) To ensure perfect backward secrecy we include the rekey cost on a user join, k.logk(N). Assuming equal number of joins and departs: C3static = B3static + R'.N.alpha = N . logk(N) . (k+1)/2 + alpha . N . ( k . logk(N)-0.5) (8) We differentiate these expressions (Appendix A) and use Newton-Raphson iteration to find the minimum cost as a function of k for a given alpha. Table 1 shows each cost as a function of alpha for static trees. To illustrate the effect of optimizing k, the table shows results both for a constant value k=3 and the life cycle cost when the tree outdegree is optimized for the given volatility. Table 2 shows the variation in the optimum value of k with volatility alpha. Table 3 shows how the total cost varies as a function of k for a sample value of alpha. ==================================================================== | | k = 3 | k optimized for min cost | |Volatility|-------------------------------------------------------| | alpha |1.Perfect|2. Tx as|3. PBS |1.Perfect|2. Tx as|3. PBS | | | memory | reqd | (int | memory | reqd | (int | | |(pre-reg)|(int arr|arrival)|(pre-reg)|(int arr|arrival)| ==================================================================== | 0.0001 | 1500 | 6290 | 12580 | 1020 | 1100 | 12410 | | 0.001 | 1520 | 6310 | 12590 | 1090 | 1560 | 12420 | | 0.01 | 1680 | 6470 | 12760 | 1400 | 2610 | 12590 | | 0.1 | 3280 | 8070 | 14410 | 3220 | 5870 | 14290 | | 1 | 19360 | 24150 | 30940 | 19340 | 23810 | 30940 | | 10 | 180130 | 184920 | 196210 | 179350 | 184560 | 195590 | ==================================================================== Table 1: life cycle cost as a function of volatility alpha (N = 1000 receivers) ================================================================ | Volatility | 1. Perf mem | 2. Tx as reqd | 3. PBS | | alpha | (pre-register)| (Intermittent | (Intermittent | | | | arrivals) | arrivals) | ================================================================ | 0.01 | 9 | 38 | 4 | | 0.1 | 4 | 9 | 4 | | 1 | 3 | 4 | 3 | | 10 | 3 | 3 | 3 | ================================================================ Table 2: optimum value of tree outdegree k as a function of volatility alpha (N = 1000 receivers) ================================================================ | Outdegree | 1. Perf mem | 2. Tx as reqd | 3. PBS | | k | (pre-register)| (Intermittent | (Intermittent | | | | arrivals) | arrivals) | ================================================================ | 2 | 3890 | 11860 | 16890 | | 3 | 3280 | 8070 | 14410 | | 4 | 3230 | 6880 | 14400 | | 6 | 3410 | 6070 | 15760 | | 10 | 4010 | 5900 | 19450 | | 20 | 5560 | 6820 | 28770 | ================================================================ Table 3: cost sensitivity illustrated for volatility alpha = 0.1 (N = 1000 receivers) We observe that: * Pre-registration has the lowest cost; * The intermittent arrival cost can be reduced significantly at low volatility by optimizing k; * Backward secrecy has the highest cost; * At low volatility, there are significant cost differences between the optimum value of k and the conventional value k=2 or k=3, for case 1 (perfect memory receivers) and case 2 (transmit keys at the time the receiver joins the group); * For frequent rekeying (alpha>>1) the curves converge and the cost is independent of the initialization approach (Table 1, Table 2). An example low volatility population is a corporate videoconference transmitted to employees, who might be expected not to leave the conference frequently. A significant example of zero volatility is a file transfer: it is not meaningful to leave and re-join since this will result in data loss. In this case, the volatility alpha=0, and the optimum key hierarchy is flat. Indeed, at low volatility the case 1 pre-registration (=perfect memory receivers) and case 2 intermittent arrival curves with k optimized converge to the same cost (Table 1). 4.5. Group key update The life cycle cost can also be considered taking into account rekeying to prevent cryptanalysis. Here we define the life cycle cost as the sum of the cost of initializing the LKH tree and the cost of regular GTEK updates during the data transfer phase. Let the lifetime of the group be T, and let the group update period be tau. Then the total number of changes of the group key over the life of the group is T / tau. If each new group key is encrypted with each of its children and then multicast (e.g. {M}J, {M}K, {M}L, Figure 3) the total number of keys transmitted due to group key updates is k.T / tau. We define a normalized rekey factor beta = T / N.tau; thus a group of 10^5 users with a lifetime of 3 hours and group key update period of 10 seconds has a beta = 0.01. The life cycle costs are then, for example for perfect memory / pre-registration: C1' = B1 + k.N.beta = ( N - 1 ) . k / ( k - 1 ) + k . N . beta (9) which has a minimum with respect to k when k = 1 + 1 / sqrt(beta). The life cycle costs are shown as a function of beta for static trees in Table 4, and the optimum value of k as a function of beta is shown in Table 5. We note that: * At low beta, when the number of rekeys per GM is low, the optimum value of k is >>3; * At high beta, rekeying to prevent cryptanalysis predominates over tree build costs, and so the optimum value of k is k=2 (noting that it is not meaningful for k to be less than 2). ==================================================================== | | k = 3 | k optimized for min cost | | Rekey |-------------------------------------------------------| | factor |1.Perfect|2. Tx as|3. PBS |1.Perfect|2. Tx as|3. PBS | | beta | memory | reqd | (int | memory | reqd | (int | | |(pre-reg)|(int arr|arrival)|(pre-reg)|(int arr|arrival)| ==================================================================== | 0.0001 | 1500 | 6290 | 12580 | 1020 | 1100 | 12400 | | 0.001 | 1500 | 6290 | 12580 | 1060 | 1500 | 12410 | | 0.01 | 1530 | 6320 | 12610 | 1210 | 2260 | 12440 | | 0.1 | 1800 | 6590 | 12880 | 1730 | 3980 | 12760 | | 1 | 4500 | 9290 | 15580 | 4000 | 8970 | 15550 | | 10 | 31500 | 36290 | 42580 | 22000 | 29970 | 34950 | ==================================================================== Table 4: life cycle cost as a function of rekey factor beta (N = 1000 receivers) ================================================================ | Rekey factor | 1. Perf mem | 2. Tx as reqd | 3. PBS | | beta | (pre-register)| (Intermittent | (Intermittent | | | | arrivals) | arrivals) | ================================================================ | 0.01 | 11 | 47 | 4 | | 0.1 | 4 | 12 | 3 | | 1 | 2 | 4 | 3 | | 10 | 2 | 2 | 2 | ================================================================ Table 5: optimum value of tree outdegree k as a function of rekey factor beta (N = 1000 receivers) 5. CONCLUSION We have considered life cycle key costs in multicast groups that use LKH for key management. We have shown how pre-registration can reduce the hierarchical tree initialization cost. When pre-registration is not feasible, periodic admission can reduce this cost. For applications with low volatility alpha, where the fraction of users joining and leaving the group over the connection lifetime is low, there is an optimum tree outdegree that varies with the volatility and gives the minimum life cycle key cost. Similarly, the optimum tree outdegree varies with the rekey factor beta that reflects the number of group key updates. This analysis therefore minimizes the key management traffic demand on a network. We have motivated our analysis with low-volatility application examples such as file transfer and videoconferences. 6. ACKNOWLEDGEMENT This work was supported by the EU Information Society Technologies GEOCAST project, IST 11754. 7. APPENDIX A: LKH TREE BUILDING COSTS 7.1. Perfect memory receivers For perfect memory receivers, each edge on the tree is transmitted once only. The number of keys is therefore independent of whether the tree has been built statically or dynamically, and for a fully populated tree, the total number of keys transmitted to admit N = k^d users to the group is therefore: B1 = k + k^2 + k^3 + .. + k^d = ( N - 1 ) . k / ( k - 1 ) . If the life cycle cost is given by C1 = B1 + R.N.alpha, where R is the rekey cost, R = k.logk(N) -1 and alpha is the volatility, then the minimum cost occurs when the partial derivative d C1 / d k = 0; assuming N>>1 this occurs at: f1 = 0 = -1 / ( k - 1 )^2 + alpha. ln(N).( ln(k) - 1 ) / ln(k)^2 where ln(x) means the natural log of x. 7.2. Transmit keys required for each receiver For a static tree, each joining receiver requires d keys to be transmitted, and the total number of keys transmitted is simply: B2static = N.d = N . logk(N) . The life cycle cost, C2static = B2static + R . N . alpha, has a minimum when the partial derivative d C2static / d k = 0, which occurs when: f2static = 0 = alpha . ln(k) - alpha - 1 / k . 7.3. Rekey on each join (perfect backward secrecy) In rekeying we assume that each changed key is transmitted k times encrypted with each of its k child keys. For a static tree the first k receivers join at a total cost (Figure 3) of x = k.d + k.(k-1)/2keys, and first k^2 receivers (1 through k^2) join at a total cost of k.x + k.(1+2+..(k-1)) = d.k^2 + (k-1).k^2. By induction the total cost of tree initialization is: B3static = d.k^d + (k-1) . k^d . d / 2 = N . logk(N) . (k+1) / 2 . The minimum life cycle cost C3static = B3static + R'.N.alpha where R' = k.logk(N) - 0.5 occurs at partial d C3static / d k = 0, i.e. f3static = 0 = ln(k) . (alpha + 0.5) - (alpha + 0.5 + 1 / 2 / k ) . 8. REFERENCES [1] J. Arrko et al., "MIKEY: Multimedia Internet KEYing,", IETF Internet Draft, work-in-progress, draft-ietf-msec-mikey-06.txt, Feb. 2003, expires Aug. 2003. [2] D. Balenson et al., "Key management for large dynamic groups: one-way function trees and amortized initialization", IETF Draft, work-in-progress, draft-balenson-groupkeymgmt-oft-00.txt, Feb. 1999. [3] M. Baugher et al., "The group domain of interpretation," IETF Internet Draft, work-in-progress, draft-ietf-msec-gdoi-08.txt, May 2003, expires Nov. 2003. [4] R. Canetti et al., "Multicast security: a taxonomy and some efficient constructions," Proc. IEEE INFOCOM 1999, pp. 708-716. [5] D. Harkins and D. Carrel, "The Internet Key Exchange," IETF RFC2409, Nov. 1998. [6] H. Harney, A. Schuett and A. Colegrove, "GSAKMP Light," IETF Internet Draft, work-in-progress, draft-ietf-msec-gsakmp-light-sec-01.txt, Jul. 2002, expires Dec. 2002. [7] D. Maughan et al., "Internet Security Association and Key Management Protocol (ISAKMP)", IETF RFC2408, Nov. 1998. [8] S. Mittra, "Iolus: a framework for scalable secure multicasting," Proc. SIGCOMM 1997, pp.277-288. [9] M.J. Moyer et al., "A survey of security issues in multicast communications," IEEE Network, Nov. 1999, pp.12-23. [10] M.J. Moyer et al., "Maintaining balanced key trees for secure multicast," IETF Internet-Draft, work-in-progress, draft-irtf-smug-key-tree-balance-00.txt, 25 Jun. 1999. [11] H. Orman, "The OAKLEY key determination protocol," IETF RFC2412, Nov. 1998. [12] R. Poovendran and J.S Baras, "An information-theoretic approach for design and analysis of rooted-tree-based multicast key management schemes," IEEE Trans. Information Theory, Vol. 47, No.7, 2001, pp.2824-2834. [13] B. Schneier, "Applied cryptography," John Wiley & Sons, 1996. [14] S. Setia et al., "Kronos: a scalable group re-keying approach for secure multicast," Proc. IEEE Symp. on Research in Security and Privacy 2000, pp.215-228. [15] J. Snoeyink, S. Suri and G. Varghese, "A lower bound for multicast key distribution," Proc. IEEE INFOCOM 2001, pp.422-431. [16] D. Wallner, E. Harder and R. Agee, "Key management for multicast: issues and architectures," IETF RFC2627, Jun. 1999. [17] C.K. Wong, M. Gouda and S.S. Lam, "Secure group communications using key graphs," IEEE/ACM Trans. Networking, Vol. 8 No. 1, 2000, pp.16-30. [18] Y.R. Yang et al., "Reliable group rekeying: a performance analysis," Comp. Comm. Review, Vol. 31, No. 4, 2001, pp.27-38. 9. AUTHORS' ADDRESSES Michael Howarth Sunil Iyengar Haitham Cruickshank Zhili Sun Centre for Communication Systems Research University of Surrey Guildford Surrey GU2 7XH UK Email: { m.howarth s.iyengar h.cruickshank z.sun } @surrey.ac.uk