Internet Engineering Task Force S. Rafaeli INTERNET-DRAFT L. Mathy January, 2002 D. Hutchison Lancaster University LKH+2: An improvement on the LKH+ algorithm for removal operations draft-rafaeli-lkh2-oo.txt Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft 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: Several algorithms have been proposed to deal with the group key management problem. The most promising are those based on Logical Key Hierarchies (LKH). An LKH reduces the size of the rekey messages, reducing also the storage and processing requirements. An improved LKH algorithm called LKH+2 is described here. Using LKH+2, a group manager can use keys already in the tree to derive new keys. Using previously known keys saves information to be transmitted to members when a membership change occurs and new keys have to be created or updated. LKH+2 achieves K log_2 n message size (K is the size of a key) for leave operations. It is also shown that the LKH+2 algorithm does not increase the storage and processing requirements when compared to other LKH schemes. S. Rafaeli [Page 1] INTERNET-DRAFT January, 2002 Table of contents: 1 Introduction...........................................................2 2 Logical Key Hierarchy Algorithms.......................................3 2.1 General algorithm....................................................3 2.2 One-way function tree................................................5 2.3 One-way function chaining tree.......................................6 3 LKH+2 algorithm........................................................8 3.1 Basic Operation......................................................9 3.2 Summary..............................................................9 4 Security Considerations...............................................11 5 Conclusion............................................................11 Acknowledgements........................................................12 References.................................................... .........12 uthors Addresses.......................................................12 1 Introduction With IP multicast communication, a group message is transmitted to all members of the group. Efficiency is clearly achieved, as only one transmission is needed to reach all members. The problems start because any machine can join a multicast group and start receiving the messages sent to the group without the sender's knowledge. This characteristic raises concerns about privacy and security since not every sender wants to allow everyone to have access to its communication. Cryptographic tools can be used to protect group communication. An encryption algorithm takes input data (e.g. a group message) and performs some transformations on it using a key (where the key is a randomly generated number). This process generates a ciphered message. There is no easy way to recover the original message from the ciphered text other than by knowing the key [6]. When applying such technique, it is possible to run secure multicast sessions. Group messages are protected by encryption using a chosen key (group key). Only those who know the group key are able to recover the original message. However, distributing the group key to valid members is a complex problem. Although rekeying a group before the join of a new member is trivial (send the new group key to the old group members encrypted with the old group key), rekeying the group after a member leaves is far more complicated. The old key cannot be used to distribute a new one, because the leaving member knows the old key. A group manager must, therefore, provide other scalable mechanisms to rekey the group. Several researchers have studied the use of a Logical Key Hierarchy for the group key management problem. Using an LKH, the key distribution centre (KDC) maintains a tree of keys, where the internal nodes of the S. Rafaeli [Page 2] INTERNET-DRAFT January, 2002 tree hold key encryption keys (KEKs) and the leaves correspond to group members. Each leaf holds a KEK associated to that one member. Each member receives and maintains a copy of the KEK associated to its leaf and the KEKs correspondent to each ancestor node in the path from its parent node to the root. All group members share key held by the root of the tree. For a balanced tree, each member stores log_2 n + 1 keys, where n is the number of members. This hierarchy is explored to achieve better performance when updating keys. An algorithm is proposed here to efficiently build an LKH tree, which is called the LKH+2 algorithm. The LKH+2 algorithm achieves K log 2 n message size for removal operations keeping the storage and processing on oth, client and server sides to a minimum. These bounds are achieved using well-known techniques, such as a one-way function and the xor operator. In the remainder of this paper, {x}k denotes that x is encrypted with key k. 2 Logical Key Hierarchy Algorithms This section reviews a few proposals of LKH algorithms. 2.1 General algorithm In Wallner's approach [9], a KDC maintains a tree of keys. The nodes of the tree hold key encryption keys. The leaves of the tree correspond to group members and each leaf holds a KEK associated to that one member. Each member receives and maintains a copy of the KEK associated to its leaf and the KEKs correspondent to each node in the path from its parent leaf to the root. The key held by the root of the tree is the group key. For a balanced tree, each member stores at most log_2 n + 1 keys, where log_2 n is the height of the tree. For example, in Figure 1, member M knows all KEKs K. S. Rafaeli [Page 3] INTERNET-DRAFT January, 2002 K / \ / \ / \ O K / \ / \ / \ / \ O O K O / \ / \ / \ / \ O O O O K O O O / \ / \ / \ / \ / \ / \ / \ / \ O O O O O O O O O M O O O O O O Figure 1: Keys held by member M. Ancestors of a node are those nodes in the path from its parent node to the root. In this document, the set of ancestor of a node is called ancestor set and the set of siblings of the nodes are called sibling set (see Figure 2). A A - ancestor set / \ B - sibling set / \ A B / \ / \ B A O O / \ / \ / \ / \ O O B u O O O O Figure 2: Ancestor and sibling sets of member u. In a join operation, a joining member is associated with a leaf and the leaf is included in the tree. All KEKs in the nodes from the new leaf's parent in the path to the root are compromised and should be changed (backward confidentiality [8]). A rekey message is generated containing each of the new KEKs encrypted with its respective node's children KEK. The size of the message produced will be at most 2 log_2 n keys long, for a balanced tree. Figure 3 shows an example of the KEKs being affected. The new member receives the secret key kB and its leaf is attached to the node k34. The KEKs held by nodes k34, k14 and k, which are the nodes in kB's ancestor set, are compromised. New KEKs (k'34, k'14 and k') are generated. Finally, the KEKs are encrypted with each of its respective node's children KEK ({k'34}kA and kB; {k'14}k12 and k'34; and {k}k'14 and k58). S. Rafaeli [Page 4] INTERNET-DRAFT January, 2002 k' {k'}k'14 / \ {k'}k58 / \ k'14 k58 {k'14}k12 / \ / \ {k'14}k'34 k12 k'34 O O / \ / \ / \ / \ {k'34}kA O O kA kB O O O O {k'34}kB -^- Figure 3: Necessary encryptions when a member joins the tree in the basic LKH. Removing a member follows a similar process. When a member leaves (or is evicted from) the group, its parent node's KEK and all KEKs held by nodes in the path to the root are compromised and should be updated (forward confidentiality). A rekey message is generated containing each of the new KEKs encrypted with its respective node's children KEK. The exception is the parent node of the leaving member's leaf. The KEK held by this node is encrypted only with the KEK held by the remaining member's leaf. As the key held by the leaving member was not used to encrypt any new KEK, and all its known KEKs were changed, it is no longer able to access the group messages. Figure 4 presents what happens when a member leaves. Member kB is leaving the group and it knows KEKs k34, k14 and k. KEKs k'34, k'14 and k' are updated and encrypted with each of its respective children's KEKs. An exception is made for the k'34. This KEK is encrypted only with kA, which is the key of the remaining member of node k34. k' {k'}k'14 / \ {k'}k58 / \ k'14 k58 {k'14}k12 / \ / \ {k'14}k'34 k12 k'34 O O / \ / / \ / \ {k'34}kA O O kA kB O O O O Figure 4: Necessary encryptions when a member leaves the tree in the basic LKH. 2.2 One-way function tree An improvement in basic LKH approach is a one-way function tree (OFT) and was proposed by McGrew and Sherman [3]. This scheme reduces the size of the rekeying message from 2 log_2 n to only log_2 n. Here a node's KEKs is S. Rafaeli [Page 5] INTERNET-DRAFT January, 2002 generated rather than just attributed. The KEKs held by a node's children are blinded using a one-way function and then mixed together using a mixing function. The result of this mixing function is the KEK held by the node. This is represented by the following formula: k_i = f( g( k_left(i) ), g( k_right(i) ) ) (1) Where left(i) and right(i) denote respectively the left and right children of node i. The function g is one-way, and f is a mixing function: The message size reduction is achieved because in the standard scheme, when a node's key changes, the new key must be encrypted with its two children's keys, and in the OFT scheme, the blinded key changed in a node has to be encrypted only with the key of its sibling node. Figure 5 shows an example of this scheme. Member kB joins the group at node k34. It requires keys k34, k14 and k to be changed. The only values that must be transmitted are the blinded KEKs g(kB), g(k'34) and g(k'14). Each is respectively encrypted with kA, k12 and k58. The new KEKs can be calculated by every group member: k'34 = f(g(kA),g(kB)), k'14 = f(g(k12),g(k'34)) and k' = f(g(k'14),g(k58)). k' {g(k'14)}k58 / \ / \ k'14 k58 {g(k'34)}k12 / \ / \ k12 k'34 O O / \ / \ / \ / \ {g(kB)}kA O O kA kB O O O O Figure 5: Necessary encryptions when B joins the tree in the OFT scheme. Removing a member follows a similar process. The leaving member's node is removed from the tree and its sibling takes its parent place. A new key value is assigned to the sibling and then the multicast message is generated in the same way as in the join operation. Figure 6 presents what happens when a member leaves. Member kB is leaving the group and it knows KEKs k34, k14 and k. KEK k'34 is removed from the tree and KA takes its place. A new key value is assigned to KA and the S. Rafaeli [Page 6] INTERNET-DRAFT January, 2002 blinded version of this value is used to generate the new value of k14. Key k18 gets a new value based on k'14. The multicast message carries k'A encrypted with the old value of key kA, the blinded version of k'A encrypted with key k12 and the blinded version of k'14 encrypted with key k58. k' {g(k'14)}k58 / \ / \ k'14 k58 {g(k'A)}k12 / \ / \ k12 k'A O O {k'A}kA / \ / \ / \ O O O O O O Figure 6: Necessary encryptions when a member leaves the tree in the OFT scheme. 2.3 One-way function chaining tree Canetti et al [4] proposed a slightly different approach that achieves the same communication overhead. Their scheme uses a pseudo-random-generator (PRG) [6] to generate the new KEKs rather than a one-way function and it is applied only on users removal. The pseudo-random-generator, G(x), doubles the size of its input (x), and there are two functions, L(x) and R(x), that represent the left and right halves of the output of G(x) (i.e. G(x) = L(x)R(x), where |L(x)| = |R(x)| = |x|). When a user u leaves the group, the algorithm to rekey the tree goes as follows: * A new value r_v is associated to every node v from u to the root of the tree using r_p(u) = r, for the first node, and r_p(v) = R(r_v) for all other v (where p(v) denotes the parent of v). * The new keys are generated as k'_v = L(r_v). * Each r_p(v) is encrypted with key k_s(v) (where s(v) denotes the sibling of v) and sent off. From r_v, one can compute all keys k'_v, k'_p(v), k'_p(p(v)) up to the root node key. Taking into account the example of Figure 7, if kA leaves the group, keys k12, k14 and k will be assigned respectively new values r, R(r) and R(R(r)) and these values will be encrypted with kB, k34 and k58. Finally, the new KEKs k'12, k'14 and k' will be respectively L(r), L(R(r)) and L(R(R(r))). S. Rafaeli [Page 7] INTERNET-DRAFT January, 2002 k' k' = L(R(R(r))) and {R(R(r))}k58 / \ / \ k'14 k58 k'14 = L(R(r)) and {R(r)}k34 / \ / \ k'12 k34 O O \ / \ / \ / \ k'12 = L(r) and {r}kB kA kB O O O O O O Figure 7: Member kA leaves. 3 LKH+2 algorithm In the LKH+2 algorithm, a KDC maintains a tree of keys. The internal nodes of the tree hold KEKs and the leaves correspond to group members. Keys are indexed by randomly chosen numbers. Each leaf holds a secret key that is associated to that member. The root of the tree holds a common key to all members. Ancestors of a node are those nodes in the path from its parent node to the root. Each member knows only its own key (associated to its leaf node) and keys correspondent to each node in its ancestor set. For a balanced tree, each member stores log_2 n + 1 keys, where n is the number of members. In order to guarantee backward and forward secrecy [8], the keys related to joining members or leaving members should be changed every time the group membership changes. The new keys in the ancestor set of an affected leaf are generated upwards from the key held by the affected leaf's sibling up to the root. Using keys that are already in the tree can save information to be transmitted to members when a membership occurs and new keys have to be created or updated. The formula F(x, y) = h(x xor y) is used to generate keys from other keys, where h is a one-way hash function. The obvious functionality of function h is to hide the original value of x and y into value z in a way that if one knows only z he cannot find the original values x and y. The functionality of xor is to mix x and y and generate a new value. It is said that a key k_i can be REFRESHED by doing k'_i = F(k_i, i), where i is the index (or identifier) of key k_i; or key k_j can be UPDATED by deriving one of its children key by doing k'_j = F(k_i, j), where k_i is the key of j's either left or right child. The notations in the rest of this section are R{k_i} means refresh $k_i$ applying F(k_i, i) and U{k_i} means update $k_j$ applying F(k_i, j). S. Rafaeli [Page 8] INTERNET-DRAFT January, 2002 3.1 Basic Operation The LKH+2 algorithm is slightly different from the PRG algorithm proposed by Canetti [4]. In the LKH+2 algorithm, when member u leaves the group: * A new key r is associated to every node v from node s (node u's sibling) to the root of the tree using r_s = R(s) (REFRESH s), for the first node, and r_p(v) = U(r_v) (UPDATE r_v) for all other v (where p(v) denotes the parent of v); * Each r_p(v) is encrypted with key k_s(v) (where s(v) denotes the sibling of v) and sent off. From r_v, one can compute all keys k'_v, k'_p(v), k'_p(p(v)) up to the root node key. The example presented in Figure 8, shows member kA leaving the group. Keys kB, k12, k14 and k are assigned respectively new values R(kB), U(R(kB)), U(U(R(kB))) and U(U(U(R(kB)))). Member kB knows key kB, hence it can calculate all keys. The only values that need to be multicast are k'14 and k', which are encrypted with k34 and k58, respectively. k' k' = U(k'14) and {k'}k58 / \ / \ k'14 k58 k'14 = U(k'12) and {k'14}k34 / \ / \ k'12 k34 O O \ / \ / \ / \ k'B = R(kB) kA kB O O O O O O k'12 = U(k'B) Figure 8: Member kA leaves. 3.2 Summary This section summarises and compares the properties of LKH+2 with other LKH algorithms presented in section 2 in quantitative way. The comparison takes into account only removal operations. The equations for join operations are not shown here because LKH+2 algorithm does not improve other LKH algorithms regarding joined members. S. Rafaeli [Page 9] INTERNET-DRAFT January, 2002 Table 1 shows the size of messages for leave operations and storage requirements from both KDC and members. Table 2 identifies computations required from KDC and members during leave operations. The elements that appear in table 1 and 2 mean: +--------------------------------------------------------+ | n | number of member in the group | | a | degree of the tree | | d | height of the tree (for a balanced tree d=log_a n) | | m | cluster size | | H | hash function | | X | xor operation | | E | encryption operation | | D | decryption operation | | K | size of a key in bits | +--------------------------------------------------------+ Note that for a leaving operation, n excludes the leaving member. Table 1: Comparing LKH+2 algorithm with other LKH algorithms (message size and storage requirements). +----------+-------------------+---------------+------------+ | Scheme/ | Multicast | Storage | | Feature | Message | KDC | Member | +----------+-------------------+---------------+------------+ | LKH+2 | dK | (2n-1)K | (d+1)K | +----------+-------------------+---------------+------------+ | LKH | 2dK | (2n-1)K | (d+1)K | +----------+-------------------+---------------+------------+ | OFT | (d+1)K | (2n-1)K | (d+1)K | +----------+-------------------+---------------+------------+ | OFC | (d+1)K | (2n-1)K | (d+1)K | +----------+-------------------+---------------+------------+ S. Rafaeli [Page 10] INTERNET-DRAFT January, 2002 Table 2: Comparing LKH+2 algorithm with other LKH algorithms (processing power requirements). +----------+----------------+------------+ | Scheme/ | Leave processing | | Feature | KDC | Member | +----------+----------------+------------+ | LKH+2 | d(X+H+E) | d(X+H) | +----------+----------------+------------+ | LKH | 2dE | dD | +----------+----------------+------------+ | OFT | d(H+X+E) | D+d(H+X) | +----------+----------------+------------+ | OFC | d(PRG+E) | D + dPRG | +----------+----------------+------------+ 4 Security Considerations The security of the LKH+2 algorithm relies on the cryptographic properties of the h function. One-way hash functions, unfortunately, are not proven secure [2]; nevertheless, for the time being, there has not been any successful attack on either the full MD5 [5] or SHA [1] algorithms [7]. Taking into account the use of hash functions as function h, attacks on the hidden key are limited to brute-force attack. Such an attack can take 2^n hashes to find the original key, with n being the number of bits of the original key used as input. In order to guarantee forward secrecy, every time there is a membership change, the keys related to leaving members are changed. For example, when a member n leaves the tree, all keys in n's ancestor set are updated. Since n does not have access to their new values it does no longer has access to the group communication. 5 Conclusion Using one-way hash functions and xor operations, an efficient LKH algorithm can be constructed. The LKH+2 algorithm requires only K log_2 n message size for leaving operations. Additionally, LKH+2 requires the same key storage as other LKH protocols, and it requires much less computation to rekey the tree after membership changes. S. Rafaeli [Page 11] INTERNET-DRAFT January, 2002 Acknowledgements The work presented here was done within the context of ShopAware - a research project funded by the European Union in the Framework V IST Programme. References [1] NIST FIPS PUB 180-1. Secure Hash Standard. National Institute of Standards and Technology, U.S. Department of Commerce, DRAFT, May 1994. [2] S. Bakhtiari, R. Safavi-Naini, and J. Pieprzyk. Cryptographic Hash Functions: A Survey. Technical Report 95-09, Department of Computer Science, University of Wollongong, July 1995. [3] D. Balenson, D. McGrew, and A. Sherman. Key Management for Large Dynamic Groups: One-Way Function Trees and Amortized Initialization. IETF Internet draft (work in progress), August 2000. [4] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naorr, and B. Pinkas. Multicast Security: A Taxonomy and Some EÆcient Constructions. In Proc. of INFOCOM 99, volume 2, pages 708{716, New Yok, NY, USA, March 1999. [5] R. Rivest. The MD5 Message-Digest Algorithm. RFC 1321, April 1992. [6] B. Schneier. Applied Cryptography Second Edition: protocols, algorithms, and source code in C. John Wiley & Sons, Inc., 1996. ISBN 0- 471-11709-9. [7] W. Stallings. Cryptography and Network Security. Prentice{Hall, 1998. ISBN 0-138-69017-0. [8] M. Steiner, G. Taudik, and M. Waidner. Cliques: A new approach to group key agreement. Technical Report RZ 2984, IBM Research, December 1997. [9] D. Wallner, E. Harder, and R. Agee. Key Management for Multicast: Issues and Architectures. RFC 2627, June 1999. Authors Addresses Sandro Rafaeli Computing Department Lancaster University Lancaster, LA1 4YR, UK Email: rafaeli@comp.lancs.ac.uk Laurent Mathy Computing Department Lancaster University Lancaster, LA1 4YR, UK Email: laurent@comp.lancs.ac.uk S. Rafaeli [Page 12] INTERNET-DRAFT January, 2002 David Hutchison Computing Department Lancaster University Lancaster, LA1 4YR, UK Email: dh@comp.lancs.ac.uk S. Rafaeli [Page 13]