INTERNET-DRAFT Josep Pegueroles IRTF GSEC WG Juan Hernandez-Serrano Francisco Rico-Novella Expires: December, 2003 Miguel Soriano June 2003 Adapting GDOI for balanced batch-LKH Status of this Memo This document is an Internet-Draft and is subject to 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 document presents a new algorithm method for rekeying multicast groups. It takes advantage of the mathematical properties of modular reduction in order to reduce the number of messages needed for rekeying. Moreover the technique is very suitable for batch processing. It achieves greater bandwidth reduction than other existing batch techniques. Batch processing techniques are specially suitable for benchmarks scenarios where a great amount of users can join or leave the group at once (typically single source broadcast). One of the most important items to take into account when performing batch rekeying is that key trees must be kept balanced all the time. Current methods for batch rekeying assure tree balancing by adding an additional method to usual rekeying. We propose a batch rekeying method that allows members to change their position in the key tree. This change has to be notified to single members with the updated keys. An adaptation of the GDOI protocol in order to contain this information is finally proposed. Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 1] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 Table of Contents 1. Introduction........................................................2 1.1 Logical Key Tree Schemes........................................3 2. Reducing Key Storage................................................4 3. Reducing latency....................................................4 3.1 Broadcast Encryption............................................5 3.2 LKH with minimum latency........................................5 3.2.1 Initialization stage......................................6 3.2.2 Multicasting stage........................................6 3.2.3 Recovery Stage............................................7 3.3 Security Analysis...............................................7 3.3.1 Attacks and attackers.....................................7 3.3.1.1 Rejected Member.....................................7 3.3.1.2 Collusion of rejected members.......................7 3.3.1.3 Collusion of authorized members.....................8 3.3.1.4 Members through successive rekeyings................8 3.3.2 Parameters Restrictions...................................9 3.4 Evaluation......................................................9 4. Application to batch rekeying......................................10 4.1 Lam-Gouda batch rekeying.......................................10 4.2 Proposed technique for batch-LKH...............................11 4.2.1 Lam-Gouda with Improved LKH..............................11 4.2.2 Balancing Batch LKH......................................12 4.2.3 Balanced LKH for batch rekeyings.........................13 4.2.3.1 Mark Rekeying Nodes................................13 4.2.3.2 Prune Tree.........................................13 4.2.3.3 Make New Rekey tree................................14 4.2.3.4 Construct and Send Rekey Messages..................14 4.2.4 Further considerations...................................14 5. GDOI adaptation....................................................14 6. Acknowledgements...................................................17 7. Author's Address...................................................17 8. References.........................................................17 1.0 Introduction When adding security features to multicast communications a common secret shared by all the multicast group members is needed. The shared key provides group secrecy and source authentication. This key must be updated every time membership in the group changes, if so Forward and Backward Secrecy (FS and BS) are provided [1] Traditionally the update is performed by a centralized trusted third party called the Key Server (KS)[2]. Some important parameters when performing multicast rekeying are: number of keys to store by the KS, number of keys to deliver in the Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 2] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 initialization stage, bandwidth required for updating the keys and latency for updating the session key [3]. In multicast security field, several works prevent new group members or leaving members from accessing data sent before they joined or after they leave. The simplest way the KS can deliver a new session key to the members is throw a secret unicast connection with each of the remaining members of the group [4][5]. This solution presents the worst behavior respecting efficiency parameters. All figures have a dependency on the number of members in the multicast group (N), so we say that these problems are order N (O(N)). 1.1 Logical Key Tree Schemes In [6][7][8] Logical Key Tree Schemes were presented as the way of reducing number of messages for rekeying to O(log2(N)), where N is the number of members in the multicast group. Figure 1: Balanced and complete Logical Key Binary Tree ______ | | |K(1,1)| |______| | _______________|_______________ ___|__ __|___ | | | | |K(2,1)| |K(2,2)| |______| |______| | | _______|______ _______|______ ___|__ __|___ ___|__ __|___ | | | | | | | | |K(3,1)| |K(3,2)| |K(3,3)| |K(3,4)| |______| |______| |______| |______| | | | | ___|__ __|___ ___|__ __|___ ___|__ __|___ ___|__ __|___ ___|__ __|___ ___|__ __|___ | || || || || || || || | |K(4,1)||K(4,2)||K(4,3)||K(4,4)||K(4,5)||K(4,6)||K(4,7)||K(4,8)| |______||______||______||______||______||______||______||______| ____ ____ ____ ____ ____ ____ ____ ____ / \ / \ / \ / \ / \ / \ / \ / \ | M1 | | M2 | | M3 | | M4 | | M5 | | M6 | | M7 | | M8 | \____/ \____/ \____/ \____/ \____/ \____/ \____/ \____/ Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 3] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 Key tree schemes use two types of encryption keys: Session Encryption Keys (SEK) and Key Encryption Keys (KEK). SEKs are used to cipher the actual data that multicast groups exchange, for example, video streams in multicast videoconference sessions. KEKs are used to cipher the keying material that members need in order to get the SEK. Normally, KEKs are structured in logical binary trees. We will adopt the next criterion as naming convention for the rest of the draft. Tree nodes will be referenced as (level number, position at level), so we will refer to root node as (1,1); sons of root node will be (2,1) and (2,2) and so on. An example of key tree is shown in Fig.1. Key in node (X,Y) will be noted as K(X,Y). 2. Reducing Key Storage In [9] a variation of the logical key tree method was presented in order to reduce the number of keys the KS has to store. This technique reduces the key storage requirement of the group controller by constructing the keys in tree nodes by means of a pseudo-random function only known by the KS. When rekeying is needed, the KS does not send the updated key themselves but the required information that single users need in order to update them. A simple example is explained next. Consider the binary tree in which keys in node (x,y) are generated according to the expression K(x,y) = Fr1(2^x+y) XOR r. Fr1 denotes a pseudo-random function with random seed r1 and r is another random number needed for updating the key. When membership changes, the KS sends to all the members that need to update their keys the parameter P = r XOR r'. Using P, each single member, only has to compute K'(x,y) = K(x,y) XOR P = Fr1(2^x+y) XOR r' in order to update his keys. As neither Fr1(2^x+y) nor r is known by anyone but the KS, past and future keys cannot be computed with the only knowledge of (x,y) or P. P is delivered to the remaining members according to LKH rules [6]. Therefore, the number of messages needed for rekeying is O(log2N). Besides that, the KS only has to store two random seeds plus the session key, say {r1,r} and SEK. Latency in this system is also the number of messages delivered by the KS to update the session key, that is to say, O(log2(N)) 3. Reducing latency In our proposed method we pretend to combine the above explained technique together with LKH delivering method with a broadcast Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 4] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 encryption solution. We achieve reducing bandwidth even more and reduce latency to a single message (although the actual number of bits does not differ very much). As in optimal key storage method, the KS has only to store two random seeds. 3.1 Broadcast Encryption The rekeying problem discussed in multicast communications is indeed a slight modification of the previously stated broadcast encryption problem. Its goal is to allow a central site to broadcast secure transmissions to an arbitrary set of recipients while minimizing key management related transmissions. Several schemes have been presented and also still being studied [10][11]. Those allow a center to broadcast a secret to any subset of privileged users out of a universe of an arbitrary size so that users not in the privileged set cannot learn anything about the secret. The main difference between broadcast and multicast encryption is that the Key Server does not know the identity of possible intruders in broadcast scenarios. In the multicast encryption problem, on the contrary, one knows which of the possible attackers must avoid since the multicast group is limited and known a priori by definition. Broadcast encryption methods are mainly based on mathematical principles. In this work we propose to study the multicast rekeying problem in the same way in order to reduce the order of the number of required messages and overcome latency problems. Let M={m1,m2,...,mN} be a multicast group of N members. Consider a set of functions F=³{f1,f2,...,fN} generated by the KS. Each member mi only shares the secret fi with the KS. Let A be the subset of authorized members to whom the secret wants to be delivered. We want these functions to have the next properties: * Given a secret, k, it is easy to find a parameter, p, such that fi(p)=fj(p)=k for all i and j in A. * The knowledge of p does not reveal any information about k any member not belonging to the authorized group A. If such properties are given, the only multicast of a single message will suffice to deliver the new session key, k. The proposed algorithm is based in this behavior. 3.2 LKH with minimum latency The multicast rekeying consists of three stages: initialization, Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 5] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 multicasting and recovering. In the first one the Key Server generates all the secrets to deliver and sends them to the group members. Multicasting stage takes place every time a new shared session key is needed, in this stage the KS sends by the multicast channel the enough data for the authorized members to recompute the new session key, that is to say, the recovering stage. 3.2.1 Initialization stage Consider a dynamic multicast group of size N. A Key Server who shares a secret with each of the members in the group manages the communication. The KS constructs a LKH-like logical tree of keys following the next rules. Each node in the tree is a different random number generated according to expression K(x,y) = Fr1(2^x+y) XOR r. As in LKH, each member is located at the leaves of the tree and knows every KEK from his leaf to the root. 3.2.2 Multicasting stage When a new key must be agreed. The KS computes a public parameter according to the expression r2*S+(r XOR r'). Figure 2: Member M3 leaves the multicast group ______ | | |K(1,1)->K'(1,1) |______| | _______________|_______________ ___|__ __|___ | | | | |K(2,1)->K'(2,1) |K(2,2)| |______| |______| | | _______|______ _______|______ ___|__ __|___ ___|__ __|___ | | | | | | | | |K(3,1)| |K(3,2)->K'(3,2)|K(3,3)| |K(3,4)| |______| |______| |______| |______| | ____ | | ___|__ / \ ___|__ __|___ ___|__ __|___ | M4 | ___|__ __|___ ___|__ __|___ | || | \____/ | || || || | |K(4,1)||K(4,2)| |K(4,5)||K(4,6)||K(4,7)||K(4,8)| |______||______| |______||______||______||______| ____ ____ ____ ____ ____ ____ / \ / \ / \ / \ / \ / \ | M1 | | M2 | | M5 | | M6 | | M7 | | M8 | \____/ \____/ \____/ \____/ \____/ \____/ Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 6] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 r2 is the result of a pseudo random function, different to Fr1 , and used to avoid collusion attacks of authorized members, we will discuss about it in future sections. S denotes the product of all KEKs in the subset of all sibling nodes of the updated path. (r XOR r') is the blinded parameter that remaining users will use to compute the updated tree. As an example, consider that M3 in Fig 2 leaves the group. The parameter P will look as follows P = r2*K(4,4)*K(3,1)*K(2,2)+(r XOR r'). 3.2.3 Recovery Stage When recovering the key, each member will do a modular reduction of P modulo one of the KEKs in his path to the root. As this random number will be included in the product of KEKs, the operation performed by the authorized user will lead to the secret (r XOR r'). With this parameter each user can compute the updated tree following the expression P = ( r2*K(4,4)*K(3,1)*K(2,2) + (r XOR r') )mod_K(3,1) = (r XOR r') 3.3 Security Analysis Next, the security level of the proposed method will be discussed and compared to other existing methods like LKH. Traditionally, multicast rekeying algorithms have three possible attackers: a rejected member, a collusion of members and an authorized member during successive rekeyings. The only way that the system can be broken if any factor of S in the rekeying message is found. If a malicious agent knows one of these factors he will be able to reduce modulo this factor and obtain the delivered secret (r XOR r'). 3.3.1 Attacks and attackers 3.3.1.1 Rejected Member A single rejected member does not know any factor since, by definition, his secret keys are not included in the rekeying message. Moreover, the secrets he knew while he was an authorized member of the group will not be used in any future rekeying message because all these secrets were updated when it leaved the group. 3.3.1.2 Collusion of rejected members A collusion of rejected members cannot learn anything about the factors since as they are already rejected, their secrets cannot be used to construct the rekeying message. Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 7] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 3.3.1.3 Collusion of authorized members The collusion of authorized members consists in one member revealing anyone of his secret set of keys to another member. This is obviously also a security flaw in LKH. However, it would be possible for two authorized attackers to find a factor not belonging to their set of secrets if the parameter r2 would not be considered. Again, imagine M3 is leaving the group. Suppose r2 is not included in expression P = r2*K(4,4)*K(3,1)*K(2,2)+(r XOR r'). Two colluding members, e.g. M1 and M4, may cooperate to know K(2,2) through the rekeying message. See the following steps: i) M1 obtains the secret by reducing modulo his authorized secret K(3,1) ii) M1 obtains S by subtracting (r XOR r') from P = r2*S+(r XOR r') iii) M1 divides K(3,1) from S and gives the result K(4,4)*K(2,2) to M4. iv) M4 divides K(4,4) from the data given by M1 and obtains K(2,2). As M1 and M4 know the secret (r XOR r'), they could update K(2,2) and be prepared to decipher the rekeying message when they leave the group. This security flaw is overcome by the introduction of random number r2 in expression P = r2*K(4,4)*K(3,1)*K(2,2)+(r XOR r'). Then the only way M4 has to know K(2,2) is by factorizing K(2,2)*r2 that it is considered a hard problem if they have prime factors large enough. Later in this section we will discuss how can be assured that large prime numbers compose K(X,Y). 3.3.1.4 Members through successive rekeyings Another relevant threat in our system is what an authorized member can learn about factors during successive rekeyings. If random numbers were reused for different messages an authorized user could easily find a factor by just using great common divisor algorithm. See an example. Message 1 (member 3 rejected in Fig 2): P = K(4,4)*K(3,1)*K(2,2)+(r XOR r') Message 2 (member 2 rejected in Fig 2): P = K(4,1)*K(3,2)*K(2,2)+(r' XOR r'') Every authorized user during these two messages can easily compute K(4,4)*K(3,1)*K(2,2) and K(4,1)*K(3,2)*K(2,2) by simply finding the secret and subtracting it from P. Using these two products, it is easy to find K(2,2) as gcd(K(4,4)*K(3,1)*K(2,2),K(4,1)*K(3,2)*K(2,2)). For Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 8] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 this reason, all the random numbers in the key tree should be updated every time a rekeying is done. If only LKH mechanisms were used to update these numbers a critical increase in the bandwidth requirement of the system will occur. To avoid this, the optimal key storage update mechanism is used. In every rekeying, the entire tree is updated and all random numbers are recomputed, so two different messages for different rekeyings will have different factors in the message and gcd() algorithm cannot be used. Moreover, the update mechanism for Optimal Key Storage delegates the update of the tree to individual users by only delivering a new secret parameter to them so no updating messages are involved. 3.3.2 Parameters Restrictions Of course, our proposed method requires some restrictions over the parameters to work properly. First of all, (r XOR r')mod_K(X,Y) = (r XOR r') implies (r XOR r') < K(X,Y) for every random number K(X,Y). This condition should be easily assured by many simple mechanisms, for instance, the bit length. In the other hand, as previously stated, random numbers K(X,Y) should be composed by large prime numbers. This condition makes factorization of a difficult problem. It is important to note that our method does not require K(X,Y) numbers to be large primes. If they are not prime, the system could even be more secure because the factorization of would not reveal anything about K(X,Y) but their factors, and the finding of K(X,Y) could only be done by means of the testing of combinations of these factors. In any case [12] gives many information of how can be assured that a large random number is composed by primes of a certain bit length with a chosen probability. 3.4 Evaluation Finally, in Table I we show the figures of the most significant parameters in multicast rekeying. It is shown how the proposed method greatly improves efficiency for almost every parameter. We have to remark that messages to update and latency have been reduced to the minimum. Latency is measured in number of absolute packets needed for rekeying. This definition takes into account that the important figure in latency is the time difference from which the first receiver obtains the updated key till the last receiver obtains the last rekeying message for updating the tree. If no propagation or transmission delay is considered, this figure is only the number of different rekeying packets needed. Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 9] Internet Draft draft-irtf-msec-gdoi-batch-lkh-00.txt June, 2003 We have to say that, although we only use one packet for rekeying, it is larger because it is the product of log2N factors. This is why it is also important to compare the real bandwidth usage normalized by the length of the message. In our proposed method this figure shows very similar behavior to LKH. In spite of that, the use on a single packet reduces the work overhead and consistently the total amount of bits. TABLE I ____________________________________________________________________ | | Rekeying Method | | Efficiency Figures |__________________________________________| | | Trivial | LKH | OKS | Proposed | |_________________________|_________|__________|__________|__________| | | | | | | |Keys to initially deliver| N | O(2N) | O(2N) | O(2N) | |Messages to update | N | O(log2N) | O(log2N) | 1 | |Stored Keys by KS | N | O(2N) | 3 | 3 | |Stored Keys by User | 1 | O(log2N) | O(log2N) | O(log2N) | |Latency | N | O(log2N) | O(log2N) | 1 | |_________________________|____________________|__________|__________| 4. Application to batch rekeying Individual rekeying is relatively inefficient, especially when requests are frequent. Consider two leaves that happen one after another. The key server generates two sets of new keys (group key and auxiliary keys) for these two leaves. These two leaves, however, might temporally happen so close to each other that the first set of new keys are actually not used and are immediately replaced by the second set of new keys. When requests are frequent, like during the startup or teardown of a multicast session, many new keys may be generated and distributed, while not used at all. This is a waste of server cost. To address the above problem, the use of periodic batch rekeying was proposed [13]. In batch rekeying algorithms join and leave requests are collected during a time interval and processed in a batch. Since the KS does not rekey immediately, a leaving member will remain in the group till the end of the batch period, and a new member will have to wait the same time to be accepted. However, this batch period can be adapted to dynamics in the multicast group. On the other hand, batch rekeying techniques increase efficiency in number of required messages thus it takes advantage of the possible overlap of new keys for multiple rekey requests, and thus reduces the possibility of generating new keys that will not be used. 4.1 Lam-Gouda batch rekeying Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 10] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 Lam, Gouda et al. presented a very simple marking algorithm that updates the key tree and generates a rekey subtree. Briefly, their system can be summarized as follows. After each rekey interval the KS collects all Join and Leave requests and processes them according to the two possible cases. If the number of leavings is greater or equal than the number of joinings, new members are allocated in the places of the departed members. Empty leaves are marked as null. All node keys in the path from the replaced leaves to the root are updated following the rules in LKH. If the number of joinings is greater than the number of leavings a rekey subtree is constructed with all the remaining new members left after applying the algorithm described above. The rekey subtree is allocated under the departed user node with the smallest height. The algorithm explained in the previous section aims to keep the tree balanced through different batches by allocating the rekey subtree under the shallowest node in each rekeying. However, this rebalancing system is only valid when the number of joinings and leavings are very similar, in any other case a periodic rebalancing algorithm is needed. 4.2 Proposed technique for batch-LKH Next we present how our technique must be adapted when used jointly with Lam-Gouda batch rekeying and Balanced Batch. 4.2.1 Lam-Gouda with Improved LKH In Lam-Gouda batch rekeying, members are located in the same position of the tree during all the group life. The only changes permitted are up and down the tree level if sibling members leave the group. In any case, the set of keys that each member has from his position to the root is always the same. In such scenario, the proposed improved LKH technique can be straightly applied cause the only information that members need in order to update the keys is r XOR r'. In such scenario, the proposed improved LKH technique can be straightly applied cause the only information that members need in order to update the keys is r XOR r'. We will better explain the adaptation of Improved LKH to Lam-Gouda Batch rekeying thorough a simple example. Consider Fig. 3 in which M2 and M6 leave the group. All the keys that have been compromised must be updated. Using Lam-Gouda LKH next messages should be multicasted: Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 11] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 K(4,1){K'(3,1), K'(2,1), K'(1,1)}; K(3,2){K'(2,1), K'(1,1)}; K(4,5){K'(3,3), K'(2,2), K'(1,1)}; K(3,4){K'(2,2), K'(1,1)}. It is easy to proof that the length of this message (normalized to the minimum message length) follows the behavior L*( (log_2(N/L)) + (log_2(N/L)+1) + (log_2(N/L)+2) + ... + log_2(N) ) Figure 3: Members M2 and M6 leave the multicast group ______ | | |K(1,1)->K'(1,1) |______| | _______________|_______________ ___|__ __|___ | | | | |K(2,1)->K'(2,1) |K(2,2)->K'(2,2) |______| |______| | | _______|______ _______|______ ___|__ __|___ ___|__ __|___ | | | | | | | | |K(3,1)->K'(3,1)|K(3,2)| |K(3,3)->K'(3,3)|K(3,4)| |______| |______| |______| |______| ____ | ____ | / \ __|___ / \ __|___ | M1 | ___|__ __|___ | M5 | ___|__ __|___ \____/ | || | \____/ | || | |K(4,3)||K(4,4)| |K(4,7)||K(4,8)| |______||______| |______||______| ____ ____ ____ ____ / \ / \ / \ / \ | M3 | | M4 | | M7 | | M8 | \____/ \____/ \____/ \____/ On the other hand, using the improved LKH algorithm, the message is with length following L*log_2(N/L) where N is the total number of members and L the number of Leavings in each batch. This corresponds to the worst case behavior, where leavings occur in the most spread way in the tree positions. 4.2.2 Balancing Batch LKH In Lam-Gouda we did not allow members to change their position during the group life (at least members always belong to the same tree brach). That is to say, they always have the same keys in his path to the root. This allows us the usage of the updating factor because members only Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 12] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 have to know it to change their set of keys. Contrary to that, Balanced Batch need the redistribution of reusable subtrees. This does not permit us only to distribute the updating factor because usually, after a batch, the key path to the root of remaining members will change. This force us to distribute not the updating factor but the updated keys themselves, although we can use the same mechanism using products of random numbers. This method is expected to present worse behavior than Lam-Gouda with improved LKH. But, on the other side, it keeps the tree balanced all the time. However, performance of such method is better than Balanced LKH without improvement mechanism. We will leave for future works the study and comparison of these cases. 4.2.3 Balanced LKH for batch rekeyings We proposed a new batch rekeying algorithm that keeps the tree balanced for every batch [14]. The algorithm updates not only node keys but also node naming or position, so rekeying nodes can change their original position after each batch following a very simple rule. The KS computerized system does not have much more processing load cause he only has to update the position of the nodes using simple rules. Besides that, keeping the tree balanced reduces the total amount of required program memory. In the other side, the new algorithm slightly increases the number of operations to be done by individual members, cause they have to know all the time the position in the tree that they are occupying in order to update it properly. However, this increase is not significant for single multicast members, even if they are devices with low computation capability. The details of the balanced batch-LKH algorithm can be found in [14] but next, we will briefly describe the atomic steps the KS and the individual members must follow to carry out the algorithm. 4.2.3.1 Mark Rekeying Nodes In the first step, nodes that should be removed have to be pointed out. After collecting the leaving requests, all nodes from leaving members leaves to root need to be updated, so they are marked for deletion. Notice that no replacement with joining members is carried out. This is why the important figure in this algorithm is the reusing of subtree nodes, and in Lam-Gouda algorithm replaced nodes and its siblings also have to be updated. 4.2.3.2 Prune Tree The prune action is very simple, it consists in deleting the marked nodes Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 13] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 and keep the subtree structures that remain unchanged. After this action, the KS has to manage three types of elements: remaining subtrees (structures with more than one members), joining members and siblings of leaving members. As the tree is a binary tree, siblings of leaving members cannot reuse any KEK but his individual key, so they should be treated the same way as new joining members. 4.2.3.3 Make New Rekey tree Now, the KS has to construct the new rekey tree balanced following the next recursive criterion. Group all trees of depth j in twos. If any element is left, group it with tree of depth j+1 and treat the result as a tree of depth j+2. The criterion must begin with trees of minimum depth, that is to say, single elements, and be repeated until just only one tree is resulted. 4.2.3.4 Construct and Send Rekey Messages Finally, the rekeying messages have to be sent. These messages should include three information fields: destination node, new position of destination node and rekeying material. The destination node is the node to which sons the message is addressed. This field is used by single members to decide whether the rekeying message concerns to them or not. The new position is the renaming field of the message. Using this information, users can rename themselves and their keying material. The rules used for renaming are explained in [14]. The Rekeying material field is the actual data of updated keys, calculated, for example, according to LKH. On the other hand, the multicast member, basically only has to decide if a multicast rekeying message is sent to him, receive it and update his position and keying material. 4.2.4 Further considerations It is important to note that the most important function from all the above described ones is the update of the tree. This function shows the main differences between the balanced batch LKH algorithm and the Lam-Gouda technique. In the update tree step of the algorithm, subtrees that can be reused are treated the way they lead to a minimum number of rekeying messages and balanced new key tree. 5. GDOI adaptation The proposed algorithm should be included in the Group Domain of Interpretation [15] in order to take advantage of all his key management Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 14] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 features. Mainly, the adoption of this technique, only affects the packets to be sent in the GDOI PHASE 2 when PUSH and PULL messages are needed. Basically, the packet format for an LKH update array is as follows 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! LKH Version ! # of LKH Keys ! RESERVED ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! LKH ID ! RESERVED2 ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Key Handle ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! LKH Keys ! ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ it is used to send to the members the keys that they must update. Fields are better explained in [15] but it basically consists in a LKH version identifier followed by a set of LKH keys. Each LKH key follows the next packet format. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! LKH ID ! Key Type ! RESERVED ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Key Creation Date ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Key expiration Date ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Key Handle ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! ! ~ Key Data ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Where LKH ID is the position of the key in the tree, key handle is an unique identifier used to address the key and Key Data is the actual key value. If balanced batch wants to be supported. The new position of key nodes in the new tree must also be notified. This implies that LKH ID will change from one batch to another. If this information is sent to the group, a change in the packet format and a bandwidth increase will be needed. Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 15] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 In order to avoid this, the LKH implementation in GDOI developed in the Technical University of Catalonia [16], does not use LKH ID for positioning nodes in the tree, but only the key handle in order to locate the key to update in the whole tree (for the server) or in the key vector (for every member). Actually, the LKH ID of the above mentioned packets is incorrectly maintained when different rekeyings have happened. So we consider it not only unnecessary but misleading. In fact, we implemented LKH in GDOI following the draft [15] recommendation but we did not use LKH ID at all. All the above explained variations of LKH could easily be implemented using only the Key Handle as an identifier to locate the key in the key vector of the members. The change of position does not affect the members cause they really do not need to know where they are located in the key tree. On the other hand, the Key Server cannot use the LKH ID because, as we have mentioned before, it is incorrect after the first rekeying; so, the key handle is also used to find the key in the tree and rebuild the tree when necessary. According to that, and in order to simplify the LKH packet format we propose to change the LKH update array to the following 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! LKH Version ! # of LKH Keys ! RESERVED ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! RESERVED ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! LKH Keys ! ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ And construct each LKH key as next 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! Key Handle ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Key Creation Date ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Key expiration Date ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Key Type! RESERVED ! +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ! ! ~ Key Data ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 16] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 6. Acknowledgements The authors thank Bernat Pegueroles and Oscar Burgos who contribute to the development of the first testbed of LKH. Bernat has added LKH functionality to Brian Weis GDOI implementation. Oscar developed the java Class tree for a multiplatform implementation of LKH. This work has been partially funded by the Spanish research council under project CICYT TIC2002-00818 7. Author's Address Josep Pegueroles c/ Jordi Girona 1-3 Modul C3 CAMPUS NORD 08034 Barcelona (+34) 934016012 josep.pegueroles@entel.upc.es Juan Hernßndez-Serrano c/ Jordi Girona 1-3 Modul C3 CAMPUS NORD 08034 Barcelona (+34) 934017089 jserrano@entel.upc.es Francisco Rico-Novella c/ Jordi Girona 1-3 Modul C3 CAMPUS NORD 08034 Barcelona (+34) 934016021 telfrn@entel.upc.es Miguel Soriano c/ Jordi Girona 1-3 Modul C3 CAMPUS NORD 08034 Barcelona (+34) 934016011 soriano@entel.upc.es 8. References [1] Wallner, Harder, Agee. Key Management for Multicast: Issues and Architectures. RFC2627. 1998 Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 17] Internet Draft draft-irtf-gsec-gdoi-batch-lkh-00.txt June, 2003 [2] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, it Multicast security: A taxonomy and some efficient constructions INFOCOM 99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 2, pp. 708-716, 1999. [3] R. Canetti, B. Pinkas. I-D irtf-smug-taxonomy-01. A taxonomy of multicast security issues, Aug 2000 [4] H. Harney, C. Muckenhir. RFC2094 Group Key Management Protocol Architecture. July 1997 [5] D. Harkins, N. Doroswamy.A Secure Scalable Multicast Key Management Protocol (MKMP). [6] H. Harney, E. Harder. I-D. Harney-sparta-lkhp-sec-00. Logical Key Hierarchy Protocol(LKH). Mar 99 [7] D.Balenson, D. McGrew, A. Sherman. I-D. Irtf-smug-groupkeymgmt- oft-00 Key Management for Large Dynamic Groups: One-Way Function Trees and Amortized Initialization. Aug 2000 [8] Canetti, Malkin, Nissim. Efficient Communication Storage Tradeoffs for Multicast Encryption. EurocryptÆ99 p 456-470 1999 [9] Bin, Jian-Hua. Optimal Key Storage for Secure Multicast. Department of Electronic Engineering, Shangai Jiaotong University. [10]Tzong-Sun Wu and Tzong-Chen Wu. Improvement of Chang-Wu broadcasting cryptosystem using geometric properties of lines. Electronics Letters, 6th Nov 1997, vol 33, No 23. [11]Hung-Min Sun. Security of broadcasting cryptosystem in computer networks. Electronics Letters, 25th Nov 1999, vol 35, No 24. [12]Menezes, Oorschot , Vanstone. Handbook of Applied Cryptography. CRC Press. 1996. ISBN: 0-8493-8523-7 [13]Li, Yang, Gouda, Lam. Batch Rekeying for Secure Group Communications. ACM SIGCOMM 2001, San Diego, August 2001 [14]Pegueroles, Rico-Novella. Balanced Batch LKH: New Proposal, Implementation and Performance Evaluation. IEEE Symposium on Computers and Communications - ISCC'2003, 2003 [15]M. Baugher, T. Hardjono, H. Harney, B. Weis, Group Domain of Interpretation for ISAKMP, draft-ietf-msec-gdoi-08.txt, May 2003, Work in Progress [16]http://isg.upc.es/gsec/lkh_gdoi.html Pegueroles, Hernßndez-Serrano, Rico-Novella, Soriano [Page 17]