.1. La.r....v‘ . It A . 5r 7. L1? . .. awn. ; z 7 i ppm . . .4— ‘ 1 1V. , 1.343;}. n... , .,. .2... ... .. a3! “1?“ : .. hurl.” u... .31 .iii. 7!; X . a F zit“: , 1):... I 3.5.33 lunar-3mg.“ .151. n \ nu. .2... .. : . 9,14. ., L... .orgurd‘awm fig”? . e.‘ 2 (Mn ADAPTI Doctoral This is to certify that the dissertation entitled VE KEY MANAGEMENT FOR SECURE GROUP COMMUNICATION presented by BRUHADESHWAR BEZAWADA has been accepted towards fulfillment of the requirements for the degree in COMPUTER SCIENCE AND ENGINEERING Mel Idliw. Major Professor’s Signature Oct 2‘3", 0 5 Date MSU is an Affinnative Action/Equal Opportunity Institution LIBRARY Michigan State University' PLACE IN RETURN Box to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 2/05 p:/ClRC/DateDue.indd-p.1 ADAPTIVE KEY MANAGEMENT FOR SECURE GROUP COMMUNICATION By Bruhadeshwar Bezawada A DISSERTATION Submitted to Michigan State University in partial fulfillment Of the requirements for the degree Of DOCTOR OF PHILOSOPHY Department Of Computer Science and Engineering 2005 ABSTRACT ADAPTIVE KEY MANAGEMENT FOR SECURE GROUP COMMUNICATION By Bruhadeshwar Bezawada Group communication is the core of many modern networking applications. Ex- amples of such applications are, conferencing applications, event notification systems, stock quote dissemination and Internet TV programming. In applications such as these, it is necessary to secure the transmitted information from unauthorized access as the data is sensitive or requires the users to pay for it. The current approach to secure group communication is tO encrypt it using a cryptographic key, called the group key, that is known only to the users in the group. Group communication is dynamic in nature. Users can be added to and revoked from the group during the sessions. When membership changes occur, it is necessary to change the group key to reflect the current membership. If the group key is not changed, any revoked( respec- tively, added) users can access future( respectively, past) group communication. A group controller changes the group key and distributes it to the users. AS the group controller needs to interrupt the group communication during the rekeying process, expediting this process is an important problem in secure group communication. In this dissertation, we address the problems of single user revocation, multi— ple user revocation and key update distribution in secure group communication. Specifically, we focus on the aspect of adapting to the storage and computational requirements Of the users while reducing the duration of interruption to the group communication. Our contributions in this dissertation are as follows: 0 We describe group key management algorithms which adapt tO the storage and computational requirements Of the users. Depending on the tolerances of the users, the group controller chooses the appropriate group key management algo- rithm. We describe techniques which allow the group controller to change the group key management algorithm at run-time tO reflect current user require- ments. 0 In our single user revocation algorithms, we identify the tradeOff between the duration Of interruption and the number Of keys stored by each user. We Show that our algorithms reduce the duration of interruption to the group communi- cation when compared tO the existing solutions. 0 In our multiple user revocation algorithms, we identify the tradeoff between the cost of rekeying while addressing the issue of collusion. We show that some existing algorithms are instances Of our algorithms. 0 We describe key update distribution algorithms, in which the key updates sent by the group controller are delivered tO only those users who need them. Our al- gorithms reduce the amount Of bandwidth needed to distribute the key updates tO the users. 0 We describe a generic algorithm tO revoke users in adhOC networks. We Show that our revocation algorithm is successful in revoking users Operating in differ- ent network settings. We have performed extensive simulated experiments to validate and prove the effectiveness Of our algorithms. The results Of our experiments are helpful to system developers for choosing an appropriate group key management algorithm for their applications. We have considered various scenarios that require adaptation in secure group communication and described instances of our algorithms that are suitable for such scenarios. © Copyright by BRUHADESHWAR BEZAWADA 2005 TO my parents, sister, and grandparents for their love and affection ACKNOWLEDGMENTS First, I would like tO thank the almighty God for giving me courage throughout my life. I want to thank everyone who has contributed to my education. I am very thankful to my wonderful advisor, Dr.Sandeep Kulkarni, without whom I could not have achieved my dream. He is a wonderful guide and a mentor Of the highest quality. I want to thank the faculty of the Computer Science and Engineering Department at the Michigan State University. In particular, I would like to thank: Dr.McKinley, Dr.Stirewalt, Dr.Radha( ECE), Dr.Dillon, Dr.Cheng, Dr.Weinshank, Dr.Esfahanian, Dr.Torng, and Dr.Weng, for providing an excellent foundation for my education and guiding me in the right direction. I want to thank Mrs.Linda Moore and the rest of the staff Of the Computer Science and Engineering Department Office for handling all my administrative tasks with patience and cheerfulness. I want to thank all my colleagues at the Software Engineering and Network Sys- tems Laboratory. Specifically, I would like to thank: Karun Biyani, Umarnaheswaran( Mahesh) Arumugam, Ali Ebnenasir, Chiping Tang, Limin Wang, Borzoo Bonakdar- pour, Min Deng, and Sascha Konrad. I want to thank my friends Mr.Vinay Shankam, and Mr.NandagOpal Ancha, for always encouraging me to never give up. NO words of gratitude can ever sum up the contribution of my family towards my life. I want to thank: my father Mr.Sathyanarayana, my grand-father Mr.Jagannadham, my grand- mother Mrs.Bhanumati, my aunt Mrs.Sujatha, and my uncle Mr.Dilip Kumar. Their support and encouragement has been immense and immeasurable. And last, but cer- tainly not the least, I want to thank my dearest friends, my mother Mrs.Anuradha, and my Sister Ms.Vishnu Priya, without whose love, support, and cheerfulness I would not have achieved any of my goals. Thank you. vi TABLE OF CONTENTS LIST OF FIGURES 1 Introduction 1.1 Group Security vs Unicast Security ..................... 1.2 Current Challenges in Secure Group Communication ........... 1.3 Our Contributions .............................. 1.4 The Organization Of the Dissertation ................... 2 Group Key Management and Distribution 2.1 Problems in Group Key Management .................... 2.2 Problem Of Key Update Distribution .................... 3 Algorithms for Single User Revocation 3.1 Our Approach ................................. 3.2 Our Family of Algorithms .......................... 3.2.1 Computing Critical Cost .......................... 3.2.2 Computing Non-critical Cost at the Lowest Level ............ 3.2.3 Computing Non-critical Cost at Other Levels .............. 3.3 Examples Of Key Management Algorithms ................. 3.3.1 Logical Keys Upper Half .......................... 3.3.2 Complementary Keys Upper Half ..................... 3.3.3 Complete Complementary Keys ...................... 3.3.4 Complete Logical and Complementary Keys ............... 3.4 Ttadeoff in Reducing Non-critical Cost Further .............. 3.5 Providing Adaptivity ............................. 3.6 Summary ................................... 4 Algorithms for Multiple User Revocation 4.1 The Basic Structure ............................. 4.2 The Hierarchical Key Management Algorithm ............... 4.3 Performance Analysis ............................. 4.4 Adapting tO Variable Storage Capabilities Of Users ............ 4.5 Adapting to Computational Capabilities of Users ............. 4.6 Summary ................................... vii ix HQDCDHH 1 13 13 18 20 21 23 24 25 26 31 32 33 33 34 35 37 39 41 43 45 50 5 Key Distribution Algorithms 67 5.1 Our Approach: The Descendant Tracking Scheme ............. 68 5.1.1 Forwarding Key Update Messages Encrypted with Logical Keys . . . . 70 5.1.2 Forwarding Key Update Messages Encrypted with Complementary Keys 71 5.2 User Identifier Assignment Algorithm .................... 72 5.3 Performance Analysis ............................. 73 5.4 Application to Security Of Interval Multicast ................ 77 5.5 Summary ................................... 80 6 User Revocation in Adhoc Networks 87 6.1 Combining Secret Instantiation with Group Key Management ...... 88 6.2 Instance of Revocation Algorithm ...................... 90 6.2.1 The Square Grid Protocol ......................... 90 6.2.2 Logical Key Hierarchy ........................... 92 6.2.3 Combining Of Square Grid with Logical Key Hierarchy ......... 93 6.3 Evaluation ................................... 94 6.3.1 Group Key Distribution With Routing Support ............. 95 6.3.2 Local Group Key Distribution ....................... 98 6.3.3 Authentication ............................... 101 6.4 Summary ................................... 102 7 Related Work 103 7.1 Group Key Management Algorithms .................... 103 7.1.1 Logical Key Management Algorithms ................... 104 7.1.2 Broadcast Encryption Algorithms ..................... 120 7.1.3 Distributed Key Management Algorithms ................ 127 7.2 Key Distribution Algorithms ......................... 133 8 Summary 137 8.1 Our Contributions .............................. 137 8.2 Future Work ................................. 139 BIBLIOGRAPHY 143 viii 2.1 3.1 3.2 3.3 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 LIST OF FIGURES Representation Of users in the multicast tree ................ Representation Of users and keys ...................... Representation of key levels ......................... Complexity of the algorithms for 46 (d=4, h=6) users .......... Partial view Of the basic structure ...................... Partial view Of hierarchical key management structure .......... Hierarchy for (a) degree=2 (b) degree=3 (c) degree-=4 .......... Comparison Of rekeying cost for revoking (a) one user (b) 10 users Comparison Of rekeying cost for revoking (a) 25 users (b) 100 users Comparison Of theoretical upper bounds vs experimental results Of the rekeying cost to revoke (a) 25 users (b) 100 users. (Note that the X-axis is in logarithm-base10 scale) ................... Partial view Of a hierarchy with variable degrees .............. Rekeying cost for (a) 25% (b) 50% low storage users ........... Rekeying cost for (a) 25% (b) 50% low storage users ........... Average key changes per user for (a) 25% (b) 50% low storage users Average key changes per user for (a) 25% (b) 50% low storage users Rekeying cost for (a) 25% (b) 50% low storage users ........... Rekeying cost for (a) 25% (b) 50% low storage users ........... Average key changes per user for (a) 25% (b) 50% low storage users Average key changes per user for (a) 25% (b) 50% low storage users Rekeying cost for (a) 25% (b) 50% low storage users ........... ix 19 24 35 43 45 51 52 53 54 55 56 57 58 59 60 61 62 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 Average key changes per user for (a) 25% (b) 50% low storage users Partial view Of a hierarchy combined with key graphs ........... Rekeying cost for (a) 1024 (b) 512 users in a degree 3 key tree ...... Rekeying cost for (a) 1024 (b) 512 users in a degree 4 key tree ...... Rekeying cost for (a) 1024 (b) 512 users in a degree 5 key tree ...... Average key changes per user for group Of (a) 1024 (b) 512 users in a degree 3 key tree ............................. Average key changes per user for group Of (a) 1024 (b) 512 users in a degree 4 key tree ............................. Average key changes per user for group Of (a) 1024 and (b) 512 users in a degree 5 key tree ............................. DT entries at intermediate nodes R1 and R2( cf. Figure 2.1) ...... KBRR for 256 users in a) LKH ) CKH c) LKH+CKH ........ (b KBRR for 512 users in a) LKH (b) CKH c) LKH+CKH ........ LKH b) CKH c) LKH+CKH ........ LKH ( ( KBRR for 768 users in a) LKH (b) CKH (c) LKH+CKH ........ ( TBRR for 512 users in ( ( ( ( ( TBRR for 256 users in (a) (a () ( w)CKH ,5 £6 Uzzn U33” Figure 2.1: Representation of users in the multicast tree In secure interval multicast, the group controller sends a message securely to a sub— set of the group users using the shared keys known to these users. However, due to broadcasting, all the messages are delivered to all the users. Thus, there is a need to reduce the bandwidth usage during secure interval multicast. In this dissertation, we describe an efficient descendant tracking technique to address the problem of key update distribution and data dissemination in secure interval multicast. We Show that, in our approach, the intermediate nodes only need to store a small amount of information which can be updated in an efficient manner. We describe forwarding techniques for distributing key updates in several group key management algorithms. 19 Chapter 3 Algorithms for Single User Revocation In the group key management algorithms that require users to store additional shared keys, to revoke a single user, the group controller distributes a new group key and a new shared keys( for the shared keys known to the revoked user). This process suggests that the cost of rekeying can be split into two parts: critical cost ——-the cost to change the group key, and non-critical cost ——the cost to change the other shared keys that the users need to maintain. The group communication can proceed when each user has the new group key. Thus, the first part, changing the group key, is on the critical path to restoring the group communication after a user has been revoked. By contrast, the second part, changing the other keys, is on the non-critical path; the process of rekeying on the non-critical path can be done in background, i.e., after the group communication is restored. Based on the above discussion, we outline our basic approach for single user re- vocation in Section 3.1 and describe our assumptions of the system and the intruder. Specifically, in this section, we describe the nature of our key management technique. In Section 3.2, using our basic approach, we describe a family of algorithms for single 20 user revocation. We describe, in detail, the tasks performed by the group controller to revoke a user and calculate the corresponding critical and non-critical costs. Note that regardless of whether a user is revoked or has voluntarily left, the group con- troller needs to perform these tasks. Our algorithms identify the tradeoff between the total cost of rekeying( critical+non—critical cost) and the duration of interruption to the group communication. In Section 3.3, we describe four members from our family of algorithms. We show that, our algorithms reduce the duration of interruption to the group communication while keeping the total cost of rekeying manageable. In Section 3.4, we describe alternate approaches to reduce the non-critical cost further. In Section 3.5, we describe scenarios in which our algorithms can provide adaptivity. Finally, in Section 3.6, we summarize the chapter. 3. 1 Our Approach Our approach to single user revocation is based on the use of logical keys [3] and complementary variables( or keys) [2]( of. Section 7 .1). The critical cost in the complementary key technique is 0(1). However, the total( critical + non-critical) cost in this technique involves sending 0(n) keys to 0(n) users and requires 0(n2) encryptions. By contrast, in [3], the keys are arranged in a tree and the critical( respectively, total) cost of rekeying is 0(dh) where d is the degree of the tree and h. is the height of the tree. We propose a new approach that incorporates both these approaches to reduce the critical cost while keeping the non-critical( respectively, total) cost manageable. Arrangement of Keys and Users. Similar to the logical key hierarchy scheme [3]( cf. Section 7.1), we arrange the users and the keys in a tree( cf. Figure 3.1). We use d to denote the number of children of a node in the tree and h to denote the height of the tree. The leaf nodes in this tree correspond to the users in the group. 21 Since we combine the logical key hierarchy and the complementary keys, each node may be associated with a key related to one or both techniques. We use k,c to denote the key associated with the logical key hierarchy at node at. And, we use cm to denote a complementary key associated with the node a: in the key tree. We use dummykey to denote a temporary key; such a key is discarded after the rekeying is complete. kg . Level 0 (root) . O O Level 1 k 1 . k2 k3 1(4 . . O O Level 2 1‘1 1 k12 k13 1‘14 <——— Level 3 0 O O C111 C112 C113 C114 C Q 9) +____ Level4(h) k1“ c1112 C1113 C1114 111 [(1112 1113 kn“, [41111] [11112IP1113][-'1114] Figure 3.1: Representation of users and keys For the levels where we use the logical key hierarchy, the user obtains the keys of its ancestors at these levels in the key tree. For the levels where we use the complemen- tary keys, the user gets the keys associated with the siblings of its ancestors; it does not get the keys associated with its ancestors. We will use the term complementary key hierarchy to collectively denote the levels in the key tree where complementary keys are used. Note that at level 0( root), only logical keys can be used; the logical key at level 0 is the group key. Also, at the lowest level( h‘h level), logical keys must be used( alone or with complementary keys). The key at this level is known only to the corrasponding user and the group controller. An Illustrative Example. As an illustration, in Figure 3.1, we have shown 22 a partial key tree of height 4. The logical keys are used at levels 0,1,2 and 4, and the complementary keys are used at levels 3 and 4. Note that in this case, at the lowest level, both logical and complementary keys are used. In this system, user umg gets the group key( kg), the keys associated with the logical key hierarchy, k1,k11 and k1112, and the keys associated with the complementary key hierarchy, c112, c113, 0114, 01111, 01113 and 01114- 3.2 Our Family of Algorithms In this section, using our basic approach, we describe a family of algorithms. Towards this end, we present different ways of arranging logical and complementary keys in a key tree( cf. Figure 3.1). Each arrangement results in an algorithm in this family. Hence, for each arrangement, we identify how these keys are used when a user is revoked from the group, and identify the corresponding critical and non-critical cost. Outline of Key Management Tasks. When a user is revoked, the group controller first changes the group key and distributes it securely to the un—revoked users. This is achieved by using the keys that are associated with the ancestor( respectively, the siblings of the ancestor) of the revoked user. After changing the group key, the group controller changes the other keys that the revoked user had. Towards this end, the group controller begins from the lowest level in the key tree. Then, the new keys at the lowest level are used to change the keys at the next level, and so on. Since this process is bottom-up, the cost of changing keys at a level depends on the keys used at the next lower level. Furthermore, while changing the group key, the cost incurred at a given level depends only on the keys at that level. While changing the remaining keys, we separately consider the cost of changing keys at the lowest level and the cost of changing keys at other levels. 23 Organization. We proceed as follows. First, in Section 3.2.1, we compute the critical cost based on the keys used at a given level. Then, in Section 3.2.2, we compute the non-critical cost for changing the keys at the lowest level. Finally, in Section 3.2.3, we compute the non-critical cost for changing the keys at other levels. 0 ~—— Level 0 (root) Cu] Cu2 cud kul ku2 O kud <-————— Level j +——— Level j+1 it] II Ct] d Ctdl Ctdd t1 1' kn d ktdl ktdd I l «— Level h [j Revoked user Figure 3.2: Representation of key levels In our algorithms, without loss of generality, we assume that the revoked user is the leftmost user in the key tree( cf. Figure 3.2). Also, we use kz, c1,( unprimed) to denote the old keys and use kg, c’x( primed) to denote the corresponding new keys. If a key k1. is not changed during rekeying, k; is the same as k3. Unless otherwise Specified, while computing critical and non-critical costs, we refer to Figure 3.2. 3.2.1 Computing Critical Cost In this section, we compute the critical cost in changing the group key using the keys at a given level, say u. Let kul, hug, . . . , kud be the logical keys( if used) at this level. Likewise, let cu], cug, . . . ,cud be the complementary keys( if used) at this level. Next, 24 we consider three cases based on the types of keys used at level u. Case 1.1: Logical keys at level u. To distribute the new group key, kg, using the keys at level u, the group controller selects those keys at level u that are not shared with the revoked user. Then, it encrypts the new group key with these keys. Thus, the group controller sends the following messages: k..2(k;,). ku3(k;), . . . , k.d(k;) Based on the above calculation, the critical cost for level u is (d— 1) encryptions. And, the number of messages sent is (d— 1). Case 1.2: Complementary keys at level u. Once again, in this case, the group controller selects those keys at level u that the revoked user does not have. For the case where complementary keys are used at level u, cul suffices for this purpose. Thus, the group controller sends the following message: Cu1(k;) Thus, the critical cost for level u is one encryption. The number of messages sent is one. Thus, the critical cost is low when complementary keys are used. Case 1.3: Logical and complementary keys at level ii. In this case, the solution is identical to that in Case 1.2. Theorem 3.1 For each level, if the group controller distributes the new group key using the appropriate case as given above then all the remaining users will get the new group key. And, the revoked user will not get the new group key. El 3.2.2 Computing Non-critical Cost at the Lowest Level Once again, let kh1,l€h2,. ..,khd be the logical keys at the lowest level. Likewise, let Cm, Chg, . . . , chd be the complementary keys( if used) at this level. As mentioned in Section 3.1, we must use logical keys at this level; the logical key at this level is 25 the personal key of the user and it is shared only between the user and the group controller. Hence, we consider the two cases based on the types of keys used at the lowest level. Case 2.1: Logical keys at level h. In this case, no keys need to be changed as the revoked user only has the key km. And, no other user in the system has this key. Thus, the non-critical cost for this case is zero. Case 2.2: Logical and complementary keys at level h. In this case, the comple— mentary keys at level h need to be changed. For the user located at Chg, this can be achieved by sending the following message( Similar messages are sent for the users located at 0,3, . . . ,chd.): kh2(c,h3tc,h43 - - - .61...) Thus, the non-critical cost for this case is (d—1)(d——2) encryptions. And, the number of messages sent is (d — 1). 3.2.3 Computing Non-critical Cost at Other Levels As mentioned above, the cost of changing the keys at a level( other than the lowest level) depends on the keys used at that level and the keys used at the next lower level. Therefore, in this section, we consider different cases based on the keys arranged at two consecutive levels, say j and j+1( cf. Figure 3.2). For the following discussion, we call these the upper level( u) and the lower level( l) respectively. We use ku1,ku2, . . . , kud to denote the logical keys at the upper level and, likewise, km,k,12, . . . , km to denote the logical keys at the lower level. Similarly, we use Cu1,Cu2, . . . ,cud to denote the Complementary keys at the upper level and C(11,C(12,. . . ,Cud to denote the comple- mentary keys at the lower level. Note that keys kn... are in the tree rooted at kul, keys km. are in the tree rooted at kug, and so on. We proceed as follows. First, we consider the case where logical keys are used at 26 the upper level. Then, we consider the case where complementary keys are used at the upper level. Finally, we consider the case where both keys are used at the upper level. Logical Keys at the Upper Level. We consider three cases based on the keys used at the lower level. Case 3.1.1: Logical keys at the lower level. The key kul needs to be changed at the upper level. The group controller can achieve this by sending the following messages( Note that Since we are using the new keys at the lower level, by induction, the revoked user does not have them.): “110351), ’l12(kii1)v ' ' ° v l1d(kh1) Based on the above calculation, the non-critical cost is d encryptions. The number of messages sent is d. The number of users rooted at kul is dh'j. Each of these users decrypts one of the above messages to Obtain kill. Thus, the total number of decryptions by the users in this case is dh—j. Special subcase at level (h—l). If the group controller is changing the logical key at level (h-l), then the number of users that need the new logical key at level (h—l) is (d— 1). Thus, it would be possible to save one encryption and one message while changing keys at level (h—l). A similar subcase also applies to Cases 3.2.1 and 3.3.1. Case 3.1.2: Complementary keys at the lower level. In this case, we can use two Complementary keys to send a message to all the users rooted at kul. Observe that each user in the subtree rooted at kul has at least one of these keys. Thus, the group Controller sends the following messages: 41131.1), 61120911) Thus, the non-critical cost in this case is two encryptions. The number of messages sent is two. The number of decryptions by the users is dh‘j. 27 Special subcase at level (h—l). If the group controller is changing the logical key at level (h— 1) and if complementary keys are used at level h then we can use cm to send the new key to the users rooted at kul. Thus, it would be possible to save one encryption and one message while changing keys at level (h— 1). A similar subcase also applies to Cases 3.1.3, 3.2.2, and 3.3.2. And, in Case 3.2.2, the reduction is two encryptions and two messages. Case 3.1.3: Complementary and logical keys at the lower level. This case is identical to Case 3.1.2. In fact, we observe that the logical keys at the lower level do not affect the non—critical cost. Hence, in the following two arrangements, we omit the discussion for the case where both types of keys are used at the lower level. Complementary Keys at the Upper Level. Once again, we consider two cases based on the keys used at the lower level. Case 3.2.1: Logical keys at the lower level. The keys known to the revoked user at the upper level are, Cug, cu3, . . . , cud and, hence, the group controller needs to change them. To distribute the new keys to the users rooted at cm, the lower level keys, kfu, [12, . . . , kfld, are selected. The group controller needs to encrypt the new keys, c’u2, c’u3, . . . , cj‘d, with each of these keys and send them to these users. However, the direct approach for. sending these keys is expensive in terms of the number of encryp- tions performed by the group controller. Hence, we propose a technique that reduces the encryption cost for the group controller. In this technique, the group controller, first, sends a dummy key encrypted with each of the logical keys at the lower level. Since this dummy key is now known to all the users( except the revoked user) rooted at Culy the group controller uses this key to distribute the new complementary keys. Thus, the group controller sends the following messages: k[11(dummykey1), . . . , k[1d(dummykey1) dummykey1(c’u2, du3, . . . , 4",) The new keys also need to be sent out to users rooted at c112,cfi,3, . . .,c,’ud. For 28 example, the users rooted at c’u2 need to get 4,3,6“, . . . , c’ud. The group controller achieves this by distributing a dummy key to the users and then using this dummy key to distribute the new keys. The group controller sends the following messages to users rooted at c’u2( Similar messages are sent for users rooted at c113, . . . ,c’ud.): k121(dummykey2), . . . , k12d(dummykey2) dummykeyflcllsv Clu4’ - . . aciid) Based on the above calculation, the non-critical cost is d—l—(d—1)(2d—1) encryptions. The number of messages sent is d(dI—1). The number of users rooted at Cal is (1” . Each of these users decrypts one message to obtain the dummy key and (d—l) decryptions to obtain the new keys. Thus, the number of decryptions by the users rooted at cm is dh‘j(d). Also, the users rooted at cug, cu3, . . . , cud decrypt one message each to obtain the dummy key and (d—2) decryptions to obtain the new keys. The number of decryptions by these users is dh‘j (d—1)(d-—1). Thus, the total number of decryptions by the users in this case is dh‘j(dQ—d+1). Case 3.2.2: Complementary keys at the lower level. As in Case 3.1.2, two comple- mentary keys at the lower level are sufficient for distributing the new keys. As before, the group controller initially distributes a dummy key using two complementary keys from the lower level. Then, it uses the dummy key to distribute the new keys at the upper level. Thus, for the users rooted at 01,, the group controller sends the following messages( Similar messages are sent for users rooted at cfifl, c’u3, . . . ,c’ud.): Clll (dummykeyg), 6112(dummykeys) dummykey3(C/u2’ 6:133 ‘ ' ‘ I dud) Thus, the non-critical cost is (d+1)+(d—1)d encryptions. The number of messages sent is 3d. The number of decryptions by users is d” (dQ—d+1). Complementary and Logical Keys at the Upper Level. Once again, we Consider two cases based on the keys used at the lower level. 29 Case 3.3.1: Logical keys at the lower level. The group controller needs to change c.,,2, 0,,3, . . . , cud and kul. First, the group controller sends k;1 using keys at the lower I ‘U. level. Then, it uses k 1 to send c’u2, c113, . . . ,c’ud. Thus, the group controller sends the following messages for users rooted at cal: kl11(k‘ll1)’ l12(ki11)"°'3 "'lidlkinl kill (d112, C/u3’ ' ' ' ’ dud) The group controller also needs to distribute some of the new keys to the users rooted at 404,3, . . .,c’ud. The group controller uses the keys, ku2,ku3, . . . ,kud, to send the new keys to these users. Thus, the group controller sends the following message for users rooted at k,,2( Similar messages are also sent to users rooted at [91137 ku4a - ° ' Ikud-): ku2(C_’u3, 0114’ ' ' ' IC’ud) Based on the above calculation, the non-critical cost is (2d—1)+(d—1)(d—-2) encryptions. The number of me ssages sent is 2d. The number of decryptions by users is dh’j(d2-2d+2). Case 3.3.2: Complementary keys lower level. To distribute km, the group controller uses two complementary keys from the lower level and sends the following messages: 411(kL1),d12(kL1) The group controller then uses kin to distribute the new complementary keys, C112, 61,3, . . . ,cfiwh by sending the following message: kh1(C’2IC/3v°"’c’ud) u u For users rooted at du2,du3, . . . , c’ud, the group controller uses the keys ku2, ku3, . . . ,kud to distribute the new keys. For example, for users rooted at cfia, the group controller sends the following message( Similar messages are sent to users 1‘00th at C113, "43 ° ‘ ' I Clud’): 30 ku2(C, 3? Cii4’ ' ' ° ’ C/Ud) U Thus, the non-critical cost is (d+1)+(d—1)(d—2) encryptions. The number of messages sent is (d+ 2). The number of decryptions by users is dh‘7(d2—2d+ 2). Observations. Based on the costs computed in this section, we observe the following: 1. If complementary keys are used at a level then the critical cost is reduced for that level. 2. If complementary keys are used at level j+1 then adding logical keys at that level does not affect the cost of changing keys at level j. 3. If complementary keys are used at level j then adding logical keys at level j reduces the cost of changing keys at level j. We use these observations to enable the group controller to dynamically change the algorithm for key distribution. Theorem 3.2 For each level, if the group controller distributes the new keys using the appropriate case given above then all the remaining users get the required new keys. And, the revoked user will not get any of the new keys. [3 3.3 Examples of Key Management Algorithms Based on the keys used at different levels of the key tree, we get a different algorithm for dealing with security in a dynamic group. In this section, we present four of these algorithms. We proceed as follows. In Section 3.3.1, we present the first algorithm where the user has logical keys for the upper % levels and complementary keys for the lower g levels. In Section 3.3.2, we present the second algorithm where the user has 31 complementary keys for the upper % levels and logical keys for the lower % levels. In Section 3.3.3, we present the third algorithm where the user has complementary keys for every level in the key tree. Finally, in Section 3.3.4, we present the fourth algorithm where the user has both logical and complementary keys for every level in the key tree. 3.3.1 Logical Keys Upper Half In this algorithm, for each user, the group controller maintains logical keys at levels 1, . . . , g and complementary keys at levels ~’21+1, 3+2, . . . , h of the key tree. Note that, as stated in Section 3.1, at the h“ level, now there are complementary keys as well as logical keys. Critical cost. Observe that Case 1.1 applies for distributing the new group key for levels, 1, . ..,-’25 and Case 1.2 ( or Case 1.3) applies for levels %+1, g+2, . . . ,h. Thus, the critical cost is 9% encryptions. And, the number of messages sent is 42’1. Non-critical cost. From Case 2.2, the non—critical cost for the lowest level is (d—1)(d—2) encryptions and (d —1) messages. Observe that Case 3.2.2 applies( for changing keys) at levels (h- 1) to (-'25+1). Also, as discussed in Case 3.1.2, it is possible to reduce the encryptions and messages by two while changing keys at level (h—l). Thus, the non-critical cost for these levels is (dz—1)+(d2+1)(%—2) encryptions and (3d—2) +3d(% —2) messages. Case 3.1.2 applies at level %. The non-critical cost. for this level is two encryptions and two messages. Case 3.1.1 applies for levels (% ~ 1) to 1. The non-critical cost for these levels is d(% —1) encryptions and d(%—1) messages. Combining the rekeying costs for individual levels, the non-critical cost of this algorithm is %(d2+d+1)—4d+l encryptions. And, the number of messages sent is (2dh—3d—1). 32 3.3.2 Complementary Keys Upper Half In this algorithm, for each user, the group controller maintains complementary keys at levels 1, 2, . . . , g and logical keys at levels 525+1, g+2, . . . , h of the key tree. Critical cost. Case 1.2 applies for levels 1,2, . . . ,g and Case 1.1 applies for 43 2 encryptions. And, the number of levels %+I, g+2, . . . , h. Thus, the critical cost is messages sent is 12’1. Non—critical cost. As we discussed in Section 3.2.2, the group controller need not change the logical keys at the lowest level. Case 3.1.1 applies for levels (h—l) to (lg-+1). Also, as we discussed in Case 3.1.1, it is possible to reduce the number of encryptions and messages by one while changing the keys at level (h— 1). Thus, the non-critical cost for these levels is (d—1)+d(%—2) encryptions and (d—1)+d(%- ) messages. Case 3.2.1 applies for level %. The non-critical cost for this level is (2d2—2d+1) encryptions and d(d+1) messages. Case 3.2.2 applies for levels g—l) to 1. The non-critical costs for these levels is (d2+1) g—l) encryptions and 3d( g-l) messages. Combining the rekeying costs for individual levels, the non-critical cost of this algorithm is %(d2+d+1)+d2—3d—1 encryptions. And, the number of messages sent is (d2+2dh—3d — 1). 3.3.3 Complete Complementary Keys In this algorithm, the user has complementary keys for every level( except level 0) in the key tree. Critical cost. Case 1.2 ( or Case 1.3) applies for all the levels. Thus, the critical cost is h encryptions. And, the number of messages sent is h. Non-critical cost. Case 2.2 applies for the lowest level. Thus, the non-critical Cost for the lowest level is (d—1)(d—2) encryptions and (d -—1) messages. Case 3.2.2 8applies for levels (h— 1) to 1. Also, as we discussed in Case 3.1.2, it is possible to reduce the encryptions and messages by two while changing the keys at level (h— 1). Thus, the non-critical cost for these levels is (d—1)+(d—1)d+(d2+l)(h-—2) encryptions 33 and (3d—2) +3d(h—-2) messages. Combining the rekeying costs for the individual levels, the non-critical cost of this algorithm is h(d2+1)—3d——1 encryptions. And, the number of messages sent is (3dh—2d—3). 3.3.4 Complete Logical and Complementary Keys Critical cost. Case 1.3 applies for all the levels in the key tree. Thus, the critical cost is h encryptions. And, the number of messages sent is h. Non- critical cost. Case 2.2 applies for the lowest level. Thus, the non-critical cost for the lowest level is (d—1)(d—2) encryptions and (d—1) messages. Case 3.3.2 applies for levels (h—l) to 1. Also, as we discussed in Case 3.1.1, it is possible to reduce the encryptions and the number of messages by one while changing the keys at level (h—1). Thus, the non-critical cost for these levels is d+(d—1)(d—2)+((d+1)+(d—1)(d—2))(h—2) encryptions and d+1+(d+2)(h—2) messages. Combining the rekeying costs for the individual levels, the non-critical cost of this algorithm is h(d2—2d+3)—d—2 encryptions. And, the number of messages sent is (dh+2h-4). Summary. Now, we summarize the results from this section, in Figure 3.3, and compare these results to those in [2,3]. In [3], the group key is distributed last and, hence, the critical cost is the same as the total cost. We Show the performance of our algorithms on a sample group of size 46. From the results for the sample group, we Observe that: 1. The critical cost in our algorithms is lower than the algorithm in [3] and the total cost of rekeying is reasonable. For this group, we see that the critical cost in [3] is 23 encryptions whereas it is 6 encryptions in the algorithm of Section 3.3.4. 2. Although one can achieve a critical cost of 1 encryption by using the comple- mentary variables algorithm in [2], the non-critical cost in [2] increases by orders 34 [3] [2] Algo. 3.3.1 Algo. 3.3.2 Algo. 3.3.3 Algo. 3.3.4 Critical (messages) 23 1 12 12 6 6 Critical (encryptions) 23 1 12 12 6 6 Total (messages) 23 4096 47 63 67 38 Total (encryptions) 23 >107 60 78 95 66 Figure 3.3: Complexity of the algorithms for 46 (d=4, h=6) users of magnitude when compared with our algorithms. 3. The algorithms in Section 3.3.3 and Section 3.3.4 have the lowest critical cost among all algorithms. 3.4 Tradeoff in Reducing Non-critical Cost Fur- ther In the algorithms presented in Section 3.3, the group controller distributes the new group key before distributing any other keys. In this section, we show that this fact can be used to further reduce the non-critical cost. We describe two approaches to reduce the non-critical cost and discuss the tradeoff involved in them. Our approaches are variations of those proposed in [4,5]. First approach. Let k denote one of the keys that the revoked user, u, shared with Other users. When u is revoked, the group controller can change this key by sending the following message( where k; is the new group key and k’ is the new version of key kt): kflMV» 35 Though this message can be received by every user in the group, only those users who have the old key k and the new group key k; can obtain k’. As we can see, the cost of this approach is less; only two encryptions( respectively, one message) for every key that the revoked user had. For example, using this approach the non-critical cost of the algorithm in Section 3.3.1, for a group size of 46, is reduced from 48 to 24 encryptions and the number of messages sent is reduced from 35 to 12. Second approach. The users can also generate the new key by using a one-way hash function, say f, that is known to all users. Thus, the users can generate the new key by using the following function: k’ = f (k,k;) If the group controller uses this approach then the non-critical cost( in terms of encryptions/ messages) is zero as far as the group controller is concerned. If the number of users is 46 then the use of this approach in the algorithm in Section 3.3.4 will reduce the total encryptions / messages to 6. By contrast, 23 encryptions / messages are required for the solution in [3]. Moreover, even though the algorithm in [2] can be used to reduce the cost to one, the number of keys stored by each user to achieve this cost is 46. By contrast, our algorithm in Section 3.3.4 reduces the critical cost to 6 encryptions / messages while keeping the number of keys stored by users to 25. ( Note that the reduction achieved using this approach is not compatible with [3]; in [3], the new group key is distributed after all the other keys have been distributed.) Tradeoff. Compared to the algorithms in Section 3.3, the above approaches reduce the total cost of rekeying. However, collusion poses a difficulty in these ap- PI‘Oaches. Consider users um and un who are currently part of the group. Now, Consider the case when um is removed from the group. In this case, the group con- trOIIer changes all the keys that um is aware of. Now, if um obtains the new group key k; from un then um also gets the new versions of the keys it had. With these keys, essentially, um continues to be a part of the group. Further, consider the case 36 when an is removed from the group, at a later time. The group controller changes the group key and distributes the new group key, kg, to all the users in the group. Since um is effectively still in the group, um will get kg. If u, gets kg from um then un will also get the new versions of the keys it had. Thus, it would be impossible to remove um and un. By contrast, in the algorithms presented in Section 3.3, knowledge of the new group key by um or un does not enable them to learn about the other keys. It follows that if collusion is unlikely in a given system, then our algorithms provide a significant reduction in the total cost of rekeying while ensuring that the number of keys that the users maintain is small. And, if collusion is an issue, then our algorithms provide a significant reduction in the critical cost while ensuring that the total cost of rekeying is manageable. We note that the problem of user collusion in our solutions is not as serious as that in [4, 5]. In [4,5], it is possible for two colluding users to compromise all the shared keys that the group controller maintains. By contrast, in our solutions, given any two users, they can compromise only a small subset of the shared keys. 3.5 Providing Adaptivity The proposed combination of logical keys and complementary keys also enables the group controller to change the algorithm for key distribution at run-time. There are Several motivations that can necessitate such a change. We describe some of these motivations next and show how our algorithms can be adapted to accommodate them. Need to reduce critical cost. If the changes in application requirements make it necessary to reduce the critical cost during group reorganization( i.e., if the application requires that the interruption during group reorganization be reduced), IEllen the group controller can achieve this by increasing the number of complementary keys used in the algorithm for key distribution. To change the algorithm for key dis- 37 tribution thus, the group controller needs to choose the level at which complementary keys are added. If the group controller chooses to add complementary keys at level j, then it can determine the cost of such addition by considering the keys used at level j+1. The cost of such addition can be determined by choosing the appropriate case from Section 3.2. 1. For low values of j, the number of keys that the group controller needs to add is small. However, adding complementary keys at those levels increases the number of decryptions that users need to perform during group reorganization. For high values of j, the number of subtrees is large and, hence, the number of keys that the group controller needs to add is high. In this case, the group controller can give low priority to the task of generating and sending these keys, as the underlying group communication can continue without them; these keys are useful in reducing the critical cost when a user leaves the group. Need to reduce non-critical cost. If the changes in application requirements make it necessary to reduce the non-critical cost( respectively, the total cost) during group reorganization, then the group controller can achieve this by increasing the prOportion of the logical keys. It can achieve this in two ways: (1) increase the logical keys or, (2) remove some complementary keys. As we can see from the results in Sections 3.2.2 and 3.2.3, combining the logical and complementary keys reduces the non-critical cost. More specifically, for the case where both logical and complementary keys are used at level j, the cost of changing these keys is less than the case where only complementary keys are used at level j( cf. Section 3.2.3). Thus, if the users can maintain additional logical keys then the group controller can reduce the non-critical cost by adding logical keys at a level that already uses complementary keys. The group controller can also reduce the non-critical cost by removing some of the complementary keys. This approach is desirable if the users cannot maintain the 38 additional keys. For removing these keys, it suffices that the group controller does not distribute them during subsequent rekeying. User Profiling. Our algorithms can be extended to adapt to the users’ behavior in a group. If the group controller is aware of profiles of different users in the system then the group controller can change the algorithm for key distribution accordingly. For example, if some users are more likely to leave the group than other users, then these users can be grouped together in one subtree. As an illustration, consider the arrangement shown in Figure 3.1. If users rooted at k1 are expected to be transient, the group controller can add a complementary key, c1, at that level. However, the corresponding complementary keys c2, c3, . . . ,cd are not added. N ow, if the user rooted at k1 leaves, the group controller can send just one message, cl(kg), to the users rooted at k2, k3, . . . , kd. Thus, these users will receive the new group key quickly. Based on the above discussion, it follows that our approach for combining logical and complementary keys allows the group controller to adapt the algorithm for key distribution based on user requirements and / or profiles. 3.6 Summary In this chapter, we described a family of algorithms that identified the tradeoff be- tween the critical cost, the cost to change the group key so that the group communi- cation is restored, and the non-critical cost, the cost to change other shared keys so that future changes in group membership are handled quickly. These algorithms are based on logical keys [3] and complementary keys [2]. Based on the application requirements for critical cost and non-critical cost, the group controller can choose an appropriate algorithm from this family. Moreover, we Showed that if the user requirements change then, the group controller can adapt the 39 algorithm for key distribution accordingly. We expect that our algorithms will fit in nicely with frameworks such as [15]. In these frameworks, certain users interact with the rest of the group through a proxy. The proxy deals with the limitations —such as smaller computing power, bandwidth or higher probability of message loss —associated with the devices that these users have. In such systems, it would be feasible to form two trees, one where the proxies act as users and one where the proxies act as the group controllers for the users interacting through them. In the former tree, it would be possible to use a complex algorithm(s) as described in Section 3.3. And, in the latter tree, one could use a simple scheme such as that in [1,3] to deal with device limitations as well as the fact that the number of users controlled by a proxy are much smaller than the entire group. In the next chapter, we will motivate the need to revoke multiple users. We present a family of algorithms that achieve this. Similar to our algorithms for single user revocation, we show that our algorithms for multiple user revocation can provide adaptation to the storage and computational requirements of the users. 40 Chapter 4 Algorithms for Multiple User Revocation In many applications, it is necessary to revoke multiple users Simultaneously. The causes for this depend on the application context. For example, it is necessary to revoke many users at the conclusion of a pay-per-view event. These users may have temporarily subscribed for the pay-per-view event, e.g., a live sporting event, but not for other programs that are transmitted by the group controller. This will prevent the revoked users from accessing other pay-per-view programs. However, the revoked users may collude and decrypt the group key updates using their combined keys. Thus, it is important to address the issue of collusion when revoking multiple users from the group. One approach to revoke multiple users is to associate a key with every non-empty subset of users in the group, i.e., complete key assignment. Thus, if one or more users are revoked, the group controller can use the key associated with the subset of the remaining users to encrypt the new group key and transmit it to the users. The advantage of this approach is that the communication overhead is only one message for revoking any number of users. Also, this technique is collusion resistant to any 41 number of revoked users. However, the number of keys stored by the group controller and the users is exponential in the size of the group. We note that, though the storage in this technique is high, the communication cost of this approach is optimal. Also, the storage cost in logical key hierarchy based approaches [3,16] is quite low. We develop multiple user revocation algorithms by combining the best features of these approaches, i.e., low communication cost in complete key assignment and low storage cost in the logical key hierarchy. In Section 3.4, we described an approach for updating the shared keys using one- way functions once the new group key is distributed. We follow this approach to update shared keys for multiple user revocation as explicit transmission of the shared keys can result in a high non-critical cost for the group controller. Moreover, it may not be necessary to update many shared keys as all the users knowing that shared key may have been revoked. Hence, the un-revoked users in the group use the one- way function approach to update the necessary shared keys. Thus, for multiple user revocation, we focus on the efficient distribution of the new group key to the users, i.e., reducing the critical cost. We note that, in this chapter, when we refer to rekeying cost we imply the cost of distributing only the new group key, i.e., the critical cost. We proceed as follows. In Section 4.1, we describe the basic structure Of our revocation algorithms. In Section 4.2, using the basic structure, we describe our family of hierarchical algorithms for multiple user revocation which achieve the objectives of low critical cost and manageable storage cost. In our algorithms, the storage cost at the group controller is linear and the storage cost at the users is logarithmic in the size of the group. Also, we show that some existing algorithms( e.g., [2,3]), including a class of our single user revocation algorithms, are members of this family. In Section 4.3, using simulation, we Show the performance of our algorithms and compare them with other existing approaches. Our algorithms provide adaptivity when the users are heterogeneous in nature. Specifically, we describe two scenarios where our algorithms 42 can provide heterogeneity, low user storage and limited computational capability. In Section 4.4, we Show that by varying the degree in different parts of the hierarchy, the group controller can adapt to low storage requirements of users. We show the simulation results on some test cases of the variations in the degree of the hierarchy. In Section 4.5, we show that our algorithms can be combined with existing algorithms to adapt to low computational requirements of the users. In particular, we Show the effect of combining the logical key hierarchy [3] with our algorithms. Finally, in Section 4.6, we summarize the chapter. 4.1 The Basic Structure We arrange a group of K users as children of a rooted tree as shown in Figure 4.1. Let R be the root node. We use the tuple, (R,u1,u2, . . . ,uK), to denote the basic structure. \ I ([3 U2 U1 UK Figure 4.1: Partial View of the basic structure The key management algorithm we use for the basic structure is the complete key graph algorithm from [3]. In this algorithm, for every non-empty subset of users the group controller provides a unique shared key which is known only to the users in the subset. The group controller gives these keys to the users at the time of joining the 43 group. Of the keys that a user, say u,, receives, (1) one key is associated with the set {u1, ug . . . , uK} and hence, is known to all the users, and (2) one key is associated with the set {iii}. The former key, say k3, is the group key whereas the latter key is the personal key. Thus, the number of keys stored by the group controller are 2K -1 and the number 2K‘1. Now, we consider the process of rekeying in this of keys held by each user is scheme when one or more users are revoked from the group. The proof of the following theorem describes the rekeying process for user revocation. Theorem 4.1 In the basic structure, when one or more users are revoked, the group controller can distribute the new group key securely to the remaining users using at most one encrypted transmission. Proof. We consider 3 possible cases of user revocation from the basic structure. Case 0. When no users are revoked, the group controller sends the new group key using the current group key that is known to all the users. Although, this trivial case is not important for the basic scheme, it is important for the hierarchical algorithm we describe in Section 4.2. Case 1. When m < K users are revoked from the group and the group controller needs to distribute the new group key to the remaining K — m users. The group controller uses the shared key, kK_m associated with the remaining subset of K - m users to send the new group key. Thus, the group controller transmits k K_m{kg}. As the revoked users do not know kK_m, only the current users will be able to decrypt this message. Case 2. All users are revoked from the group. The group controller does not need to distribute the new group key and thus, does not send any messages. [II We note that, once the new group key is distributed, the current users update the necessary shared keys using the one-way function technique we described in Section 3.4. However, the basic structure requires the group controller and the users to store 44 a large number of keys which is not feasible if the group is large. In the Section 4.2, we present our hierarchical algorithm to reduce the number of keys stored at the group controller and the users. Our hierarchical algorithm preserves some attractive com- munication properties of the basic structure while reducing the storage requirement for the shared keys. 4.2 The Hierarchical Key Management Algorithm In our hierarchical algorithm, we compose smaller basic structures in a hierarchi- cal fashion. To illustrate the hierarchical structure, consider the sample structure (R, R1, R2, . . . , Rd) shown in Figure 4.2, where each R,, 0 g i g (1, further consists of the basic structure (R,,u,-1, 21,2, . . . ,u,d). The parameter d is the number of elements in a basic structure and can be considered as the degree of the hierarchy. We note that, the degree can be different for different nodes in the hierarchy( cf. Section 4.4). However, for the sake of simplicity, in this section, we assume that the nodes in the hierarchical structures have a uniform degree d. R <——— Level 0 <—— Levell h-l) QRl OR2 . Rd ( A /~~ Udd Cf <——-——- Level 2 (h) U Figure 4.2: Partial view of hierarchical key management structure Now, each of the basic structures of the form (R,,u,-1,u,-2, . . . ,u,d) is associated 45 with the shared keys as described in Section 4.1. The structure at next higher level, (R, R1, R2, . . . , Rd), is also associated with shared keys. The personal key associated with R,, 1 S i S d in structure (R, R1, R2, . . . , Rd) is the same as the group key of the structure (R,,u,-1,u,-2, . . . , u,d). Further, the structure (R, R1, R2, . . . , Rd) is associated with shared keys. Now, each user in the basic structure (Rd, u,1, u,2, . . . ,u,d) is pro- vided with any shared key that is provided to R,- in the structure (R, R1, R2, . . . , Rd). To illustrate our hierarchical algorithm, we consider four examples for d=N, 2, 3, 4. In the hierarchical structure, we denote the key associated with a subset {a, b, . . . , 2} by kab...z- Erample 0. When d = N, the key management algorithm corresponds to the basic structure( cf. Section 4.1) with K = N. Thus, the number of keys maintained by the group controller are 2N — 1 and the number of keys maintained by each user are 2N‘1. Erample 1. In Figure 4. 3(a ,we Show a hierarchy with d— —— 2. R QR! RI/ZRZ 0R3 . R4 / RB/fi: ©C/’lfil\\ :k cf 0 OO \O OO ‘. Lu... .1 Figure 4.3: Hierarchy for (a) degree=2 (b) degree=3 (c) degree=4 Consider that the shared keys associated with (R, R1,R2) are {k3, k3,, k3,}, and the shared keys associated with (R1,u11,u12) are (km, kuu, ku12}- Then, in this scheme, user u“, knows the shared keys km, kg, and kn. We note that, the hierarchical algorithm for d = 2 corresponds to the logical key hierarchy proposed in [2,3]. Example 2. In Figure 4.3(b), we Show a partial view of a sample hierarchy with 46 d = 3. Consider that the shared keys associated with (R, R1, R2, R3) are, {k3, k3,, k3,, kR3, leRzr kR1R3I kR2R3}7 and the Shared keys associated with (R1,u11,u12,u13) are, {kum kn”, km, kunum kunum, loam”, k3,}, then, the shared keys known to user all are, {kum kunulz, kunum, k3,, leR,, [“121st kg}. We note that, the hierarchy for d = 3 corresponds to our complementary key hierarchy from Chapter 3. Example 3. In Figure 4.3(c), we show a partial view of a sample hierarchy with d = 4. Consider that the shared keys associated with (R, R1, R2, R3, R4) are, {km/:31, (€32, kits, kn.“ leRza kR1R3, leRu kRzRar kR2R47 kR3R41 leRzRar leRzR.“ kR1R3R4I kR2R3R4} and, the shared keys associated with (R1, um, um, u13, um) are, {kum km, km, km, kunulz’ kunulgi kuuum, ku12u13, ku12u14a km...“ kunmum, 161.111.121.14, kunulguma kuuumum, k3,}. Then, the shared keys known to user all are, {kum kunum, kunuls, kuuuuy 331.111.121.13, kunmuw 191.111.131.14, (CR1, kRIRQ, kR1R3, lem, kR1R2R3) knlngm, kRIRaRu k3}. Now, we describe the process of rekeying for user revocation for an arrangement with h levels. Theorem 4.2 In our hierarchical key management algorithm, when r users are re- voked from a hierarchical structure with h levels, the group controller can distribute the new group key securely to the remaining users using at most h.r encrypted trans- missions. Proof. We mark all the nodes which are the ancestors of the revoked users. At each level, a marked node, R,- can be considered to be revoked from the structure, (R, R1 . . . ,R,, . . . ,Rd). As an illustration, in the hierarchy with d = 4 in Figure 4.3(c), if um, mm are revoked users, then we mark R1 and R4. We consider an to be revoked from the basic structure, (R1,u11,u12,u13,u14) and R1 to be revoked from the structure (R, R1, R2, R3, R4). Similarly, mm is revoked from the basic structure, (R4, u41, u42, u43, v.44) and R4 is revoked from the structure, (R, R1, R2, R3, R4). To send the new group key, at the lowest level( level h), the group controller 47 needs to send at most one message( cf. Theorem 4.1 from Section 4.1) for the basic structures from which users are revoked. As the number of basic structures from which users are revoked is at most r, the rekeying cost due to the h“ level is r. We note that, the number of encryptions and messages will be lower if more than one user is revoked from the same basic structure. At the next higher level( level h — 1), the number of revoked nodes, i.e., marked nodes, is at most r. At this level, to send the new group key, the group controller sends at most one encrypted message for each structure. Based on the key distribution in the hierarchical algorithm, this message is decrypted by the users which are children of the non-revoked nodes in each such structure. As the number of such structures at this level is at most r, the group controller sends at most r messages for this level. Further, in the worst case, the group controller sends r messages for all the levels in the hierarchy. Thus, for r revoked users, the cost of distributing the new group key is at most h.r encrypted transmissions. El We note that, at the highest level( level 1), there is only one structure. As this scenario is similar to user revocation from a basic structure, using Theorem 4.1 at this level, the group controller sends at most one encrypted message for the new group key. Therefore, we can reduce the total rekeying cost from Theorem 4.2 to (h — 1).r + 1. Thus, we have: Theorem 4.3 In our hierarchical key management algorithm, when r users are re- voked, the group controller can distribute the new group key securely to the remaining users using at most (h — 1).r + 1 encrypted transmissions. CI The upper bounds in Theorems 4.1 and 4.2 are tight for a small number of revoked users. If the number of revoked users is 0(N) where N is the group size, then the group controller can distribute the group key by only considering the structures at the lowest level. The group controller sends at most one message for each basic structure. As there are N / d basic structures at the lowest level, the group controller sends at 48 most N / d messages. Theorem 4.4 In our hierarchical key management algorithm, for revoking any number of users, the group controller can distribute the new group key securely to the remaining users using at most N / d encrypted transmissions. El We can combine the results in Theorems 4.2 and 4.4 as follows. To revoke r users, for k lower levels in the hierarchy, the group controller uses the result from Theorem 4.2 and sends at most (h — k).r encrypted messages. At level k, for each of the d""‘1 structures, the group controller uses the result from Theorem 4.4 and sends at most dk‘l encrypted messages. Therefore, we can also say that the rekeying cost in our hierarchical key management algorithm is bounded by (h — k).r + d"‘1 where ISkSh. We note that, all the results we derived give upper bounds on the rekeying cost for revoking users. Thus, the minimum of these bounds is still an upper bound. The simulation results Show that, on an average, the performance of our algorithms is slightly better than these bounds. Some of the basic structures in the hierarchical structure may have less than (1 users. To revoke users, the group controller assumes that all the basic structures( cf. Section 4.1) are full. This assumption allows the group controller to distribute the group key according the rekeying techniques we described in Theorems 4.2, 4.3 and 4.4. We note that, in this model, the rekeying cost for the group controller does not increase and is determined by the actual number of revoked users. For a full hierarchical structure with h levels of hierarchy, the group controller stores, (%)(2d — 1) keys and, each user stores h.(2d‘1) keys. Thus, in the hierarchical structure, for small values of d, the user needs to store 0(h) keys as against 0(2N’1) keys in the basic structure. 49 4.3 Performance Analysis We compare the performance of our algorithms with the algorithms in [7, 8]. In [8], the group controller uses the key graphs technique described in [3]( cf. Chapter 7 for description of the algorithm). To revoke a user, the group controller recursively distributes the changed keys at the higher levels in the key tree using the changed keys at the lower levels. To revoke multiple users, instead of sequentially distributing the changed keys for each revoked user, the group controller processes all the key updates in a single step. This reduces the cost of changing a key multiple times if it is known to multiple revoked users. In [7], the group controller maintains a key tree similar to [8]. Each node in the key tree is associated with a public key and a private key pair. To revoke multiple users, the group controller traverses the tree and determines the common ancestors of the remaining users. The group controller uses the public keys of these ancestors to send the new group key to the remaining users. The remaining users use the private keys known to them and determine the new group key from the information sent by the group controller( cf. Chapter 7 for more details). We note that, there are other algorithms, namely, the sub-set difference revocation schemes in [17,18], which address the issue of multiple user revocation in the context of broadcast encryption. These algorithms require the users to perform additional computation to recover the group key. In our algorithms, the users only need to decrypt one key update message to recover the group key. Moreover, in these algo- rithms, the group controller needs to keep track of the past revocation events as the current revocation event is a cumulative process which includes all past revocation events( cf. Chapter 7 for more details). Due to these reasons we have not compared our algorithms with these schemes. Methodology of Experiments. We denote the algorithm from [8] by Batch LKH, the algorithm from [7] by Resilient LK H and our algorithm by Our Algorithm. In the 50 simulations, we assume that the algorithms maintain full and balanced hierarchies( respectively, trees) of keys. For each experiment, we selected a random set of users to be revoked from the group, and recorded the number of encrypted messages sent by the group controller for the new group key. Cost of Revoking a Single User Cost of Revoking 10 Users 100 I I I I I I 300 I I I I I I Batch LKH —+— Batch LKH + RESIIIenI LKH "‘X"‘ Resilient LKH "-X--- a, 30 - Our Algorithm degree=3 mi ~ -- - a, 250 ' Our Algorithm degree=3 *1 '1 8, Our Algorithm degree=4 ~~B - - 3, Our Algon'thm degree=4 .9... 3 Our Algorithm degree=5 -~-l~- g 200 _ Our Algorithm degree=5 - -l~- 1 In In 1% 60 g 3 if“) ' z 40 *- - a: g g 100 - O O UCJ 20 r— -I If] .x -------- * 50 . _ . . - XML-I; .-.....-......-......--~------~o~--o-----—1‘ PM“ ' 0 F "I" l l l l l 1 l 0 I l I J l L J l 0 2000 4000 6000 8000 1000012000140001600018000 0 2000 4000 6000 8000 1000012000140001600018000 Group Size Group Size (a) (b) Figure 4.4: Comparison of rekeying cost for revoking (a) one user (b) 10 users We Simulated the algorithms with degrees 3, 4 and 5. For each experiment, we computed the average cost of user revocation over 100 trials. The results are shown in Figures 4.4-4.5. Regarding our algorithms, we consider degrees 3, 4 and 5. We also experimented with these degree values for the algorithms in [7,8] and selected the version with the minimal cost. Based on these figures, as the degree of the hierarchy increases, the rekeying cost reduces due to the reduction of the height h of the hierarchy. From these results, we observe that our algorithms perform much better than the existing solutions. Specifically, the cost of rekeying in our algorithm is 66% — 79% less than that of [8] and 43% — 74% less than that of [7]. Finally, the algorithm in [8] is an optimization 51 Cost of Revoking 25 Users Cost 01 Revoking 100 Users 700 I I 1 r n r I 2000 r I I I I I I Batch LKH -+- Batch LKH ——+— 600 - ResilientLKH -----x - Resilient LKH ----x 0) Our Algorithm degree=3 -~-II~ a, Our Algorithm degree=3 ...*, 8, Our Algorithm degree=4 ----- B 0 1500 - Our Algorithm degree=4 ---------a A 500 - - - a . 3 Our Algonthm degree=5 -~-I-- 3 Our Algonlhm degree=5 ~4— ‘” I» g 400 . g B a 1000 - 5 300 - .5 o 200 - 0 ,fi [5. 500 0 l J 1 l l l M l 0 i l l l l l l l l 0 2000 4000 6000 80001000012000140001600018000 0 2000 4000 6000 80001000012000140001600018000 Group Size Group Size (a) (b) Figure 4.5: Comparison of rekeying cost for revoking (a) 25 users (b) 100 users to the logical key hierarchy in [3] for handling multiple user revocations. Hence, our algorithm reduces the rekeying cost to a value that is less than that in [3]. Another important observation in this context is illustrated in Figure 4.6. Specif- ically, in this figure, we compare the upper bound identified in Section 4.2 with the experimental value. As shown in Section 4.2, the upper bound for rekeying cost is the minimum of (h — k).r + dk‘l, where 1 _<_ k S h. From this figure, it follows that the experimental value is a close estimate to the upper bound that is computed analytically. For this reason, the group controller can use this analytical estimate in deciding the choice of degree that should be chosen so that the rekeying cost remains within acceptable limits. 52 Comparison to Theoritical Bounds Comparison to Theoritical Bounds 300 . - ....n, . - . ...., - - 900 . -. ...n, . . ...", . ..fi" degree=3, actual cost ——I—— degree=3. actual cost ——+— degree=3, upper bound "”“X 800 " degree=3, upper bound "xw- i a, 250 ' degree=4. actual cost mar-- ‘ a, 700 L degree=5, actual cost -----* _ 3: degree=4, upper bound """ B“ 8, degree=4, upper bound We 3 200 _ degree=5, actual cost ---I- _ g 600 _ degree=5, actual cost -+- _ 3 degree=5, upper bound "0" g degree=5, upper bound --o-- E 2 500 '- ’X " a 150 - ~ B 5 g 400 — ’ - S 100 ~ I g 300 ~ . O 0 IE 6 200 - . 50 - - 100 ~ a 0 I I LIIIIII I I IIIIIII I I IIIII o I I IIIIIII I I IIIIIII I I IIIIII 100 1000 10000 100000 100 1000 10000 100000 Group Size Group Size (a) (b) Figure 4.6: Comparison of theoretical upper bounds vs experimental results of the rekeying cost to revoke (a) 25 users (b) 100 users. (Note that the X-axis is in logarithm-baselO scale) 4.4 Adapting to Variable Storage Capabilities of Ilsers Our algorithms also enable the group controller to deal with heterogeneous set of users that have different storage capabilities. We illustrate this by a simple example. Consider the case where the basic structure at the root level has a degree 2, the trees rooted at the left child of the root can only maintain a small number of keys, and the users rooted at the right child of the root can maintain a large number of keys. Now, we can use a smaller degree for the tree rooted at the left child and a larger degree for the tree rooted at the right child. With such a design, the users in the left tree will receive only a small number of keys whereas the users in the right tree will receive a large number of keys. It follows that for the right tree, the group controller can take advantage of reduced rekeying cost provided by the use of a tree with larger degree, while still allowing users with lower storage capabilities to participate in the 53 R QT 8142 : TI: "5% L U U Figure 4.7: Partial view of a hierarchy with variable degrees group communication. Further, based on the above discussion, we can use a higher degree for the basic structure at the root to accommodate users with multiple storage requirements. In such a key tree structure, the users rooted at each child node have the same storage capabilities. Thus, by partitioning the group at the basic structure, the group con- troller can deal with heterogeneous users in a fine-grained manner. In Figure 4.7, we show an example of a hierarchy with variable degrees. In this figure, the root node has degree 2 with two children S and T. The hierarchy under S has a smaller degree than the hierarchy under T. Users with low storage can be placed under S and the users with higher storage can be placed under T. In this section, we evaluate the performance of our algorithms when the group controller uses variable degrees in the key tree. Specifically, we examined three cases of variations in the degree of the key tree, 2, 3 and 4 variations in the degree of the key tree. For example, a variation of degree 2 implies that the root node has degree 2 and each child node has a different degree. Users with lower( respectively, higher) storage requirements are placed in the key tree with a lower( respectively, higher) degree. We evaluate our algorithms using simulations on groups of size 1024, 512 and 54 256 users. Case 1. Two Variations in Key Tree Degree. In this case, the basic structure at the root has a degree of two and, the key tree rooted at the left child node has a smaller degree than the tree rooted at the right child node. We considered the cases when the degrees, for the left and right child nodes respectively, are (2, 4) and (2,5). For these key tree structures, we compared the rekeying cost and the work done by the users( to change all the revoked keys) to the scenario when the degree of key tree is uniform. In Figures 4.8-4.9, we show the rekeying cost when 25% and 50% of users have low storage cost. From these results, we observe that, when using these key tree structures, the overall rekeying cost for the group controller does not increase significantly from the case where the key tree has a uniform degree. Rekeying Cost 300 250 200 150 100 0 0 (2,4)-Degree Combination N: 1024, Degree= (2, 4) —+— N:1024, ree: 4 ---x--- N: 512, Degree: (2,4) ------ i N=512, Degree=4 '''''' a---- N: 256, ,Degree=(2=,4):fiO +- _ egree N: 256 102030 40 506070 8090100 Number of Revoked Users (at) Rekeying Cost 400 350 300 250 200 1 50 (2,4)-Degree Combination ' N'=10'24,D ree:(2,4) -+— e N: 1024, eg ree: -4 -----x .. I N: 512, Degree: (2,4) war-- N= 512 Degree=4 ...... BM. _) N: 256, ,Degrgeam):0 +- egree- - - 4 N=256, 0 102030 40 50 60 70 8090100 Number 01 Revoked Users (‘0) Figure 4.8: Rekeying cost for (a) 25% (b) 50% low storage users In Figure 4.10-4.11, we show the work done by the users to change the shared keys( using the one-way hash function approach from Section 3.4). We note that, the average number of key changes is considerably smaller for these key structures as the degree of one of the key trees is smaller and causes a portion of the users to perform 55 (2,5)-Degree Combination (2,5)-Degree Combination 300 U I l I I I I 350 l l I I l I I N: 1024, D ree:(2,5) —+— N:1024,Der ree:(2,4) —+—— N:1024, egree: 5 ------X 300 - N:1024, egree: 5---X--- . 250 ' N: 512, Degree: (2,5) -~-¥-- " N=512, Degree (2,4) War N=512, Degree:5 a 25 N=512, Degree:5- We 75 _ N: 256,0 ree:(2,5)- 4- _ 7, 0' N: 255 Der ree:(2,4)_‘ 4- ~ 200 8 N:256, egree: 8 N:256, egree: a a 200 - .g 150 - g % g 150 - 100 - E m 100 - 50 - 50 .. 0 1’1" l l J L I J l l 0 0102030405060708090100 0102030405060708090100 Number 01 Revoked Users Number of Revoked Users (a) (b) Figure 4.9: Rekeying cost for (a) 25% (b) 50% low storage users lesser key changes. From these results, we note that, along with the users with smaller storage, we can also place users with lower computational capability in the key tree with the smaller degree. This result is especially useful for mobile environments where users have sufficient storage capability but have limited battery power for computational purposes. We explore adaptation to computational capabilities in Section 4.5. Case 2. Three Variations in Key Tree Degree. In this case, the basic structure at the root node has a degree of 3. This indicates that there are three kinds of re- quirements( storage and / or computational) for the users in the group. We considered the degree combinations, (2,4, 5) and (3, 4, 5) for the three children of the root node. In Figures 4.12-4.13, we Show the rekeying cost and, in Figures 4.14-4.15, we show the work done by the users. As in Case 1, we note that, the rekeying cost does not increase significantly for the group controller. Furthermore, the average number of key changes by the users is smaller than in Case 1 as a majority of the users store a smaller number of keys. 56 (2,4)-Degree Combination (2,4)-Degree Combination 50 I I r 60 I I I I 1 1 I N:1024, Degree- (24) ——+—— N:1024, De ee- (2 4) ——+—— N=1024 fee-'- 4 "‘§"' N=1024 egree: 4 ..-.x--. 50 _ N= 512 D99l99= (24) """ 7 50 ' N=512, Degree (2,4) was 4 N=512, Deg fee=4 """ B """ N=512, Degree=4 ....Bu... 40 - N= 255 D 99=(2 4)-. a" - 40 - N:256, De ree: (2,4) --+- A N=256 egree= N:256, egree:4 :4.— Average Work Done <40 0 I Average Work Done 00 O l 20 - 20 . 10 - 10 - 0 0 , 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 Number of Revoked Users Number 01 Revoked Users (80 (b) Figure 4.10: Average key changes per user for (a) 25% (b) 50% low storage users Case 3. Four Variations in Key Tree Degree. In this case, the group controller maintains a degree of 4 for the basic structure at the root. This kind of scenario occurs when the capabilities of users vary considerably across the entire group. We considered the degree combination of (2,3, 4,5). We Show the rekeying cost in Figure 4.16 and the average number of key changes in Figure 4.17. 4.5 Adapting to Computational Capabilities of Ilsers To adapt to the computational capabilities of the users, our hierarchical algorithm can be combined with the logical key hierarchy in [3]. Combining logical key hierarchy with our algorithms achieves a tradeoff between the rekeying cost and the work done by the users. Depending on the current configuration of users, the group controller can use the appropriate combination of these algorithms. Inn this section, we evaluate the effect of combining logical key hierarchy with our 57 (2,5)-Degree Combination (2,5)-Degree Combination 100 I I I I I T I I I 100 I I I T I N:1024,D ree:(2,5) —+— N: 1024, D ree:(2,4) —+— N:1024, egree:5 -----x N: 1024, egree: 5---X--- 30 I N: 512, Degree: (2,5) wi- - 80 - N: 512, Degree: (2,4) ------ - g N=512, Degree=5 ----- B~~ g N=512, Degree=5 "-8 o N: 256, Degree-(2,5 5)- +- 8 N:256, D ree:(2,4) --+- g 60 _ N: 256 egree: x 60 L N:256, egree=5 --e-- - 8 6 3 3 S 40 - 3 4o - 9 B 0 O > > < 20 - < 20 - 0 l l l l l I 1 J L 0 l I l l l l l l L 0102030405060708090100 0102030405060708090100 Number 01 Revoked Users Number of Revoked Users (3) (b) Figure 4.11: Average key changes per user for (a) 25% (b) 50% low storage users algorithms. To combine these algorithms, we partition the key tree into two parts. In the first partition, for the key tree starting from the leaf nodes up to a height, say hl, the group controller maintains keys from the logical key hierarchy. For this partition, the rekeying of the users is done using the algorithms from [3,19], re the group controller distributes the shared keys and then, distributes the group key. In the second partition, for the key tree starting from hl + 1 to h( the height of the key tree), the group controller maintain the keys from our algorithms. For this partition, the rekeying is done using our algorithms, i.e., the group controller only distributes the group key and the users change the shared keys locally. Note that it is more effective to use our algorithms at higher levels as they can be used to send the group key to a larger number of users. Hence, in this discussion, we only consider the case where the logical keys are used at lower levels in the key tree and keys from our algorithms are used at higher levels in the key tree. In Figure 4.18, we show an example of combining the logical key hierarchy with our algorithms. In this figure, our algorithms are used at the root node, i.e., the tuple (R, R1, R2, R3, R4) is an instance 58 (2,4,5)-Degree Combination (2,4,5)-Degree Combination 300 I I I fl I I I I 350 I I I I I I h I N: 1024, Degree: (2,4,5) —+— N: 1024, Degree: (2,4,5) —+— N:1024, Degree:4 ------x 300 _ N:1024, Degree:4 ------x . 250 - N:512,Degree=(2,4,5) -----¥ ‘ N=512,Degree=(2,4,5) Wt N=512, Degree:4 e~- 2 N=512, Degree:4 --------e 1;,- 200 _ N:256,Degree=(2,4,5) ~+- . 7, 50 " N:256, Degree: (2,4,5) -~+- ‘ 8 N:256,Degree=4 ~e~ _ 8 200 N:256,Degree:4 -0, - I: 150 - g g g 150 " A! 100 - I m 100 ~ ................. ' J 50 '- 50 _ ........... 0 0 I I I I I I L I I 7 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 Number of Revoked Users Number 01 Revoked Users (a) (b) Figure 4.12: Rekeying cost for (a) 25% (b) 50% low storage users of our basic key structure( cf. Section 4.1). We use logical keys at the other levels in this hierarchy. Thus, the user Um knows the logical keys, K111, K11, K1 and, the keys known to R1 from the basic structure (R, R1, R2, R3, R4). For Simplicity, we used a uniform degree throughout the key tree, i.e., both the logical key hierarchy and our algorithm had the same degree. We considered the effect of these algorithms when the key tree has degree 3, 4, and 5. We compared the rekeying cost and the work done by the users in these combined algorithms against the case when these algorithms are used in a stand-alone manner, i.e., only logical key hierarchy or only our algorithms are used. In Figures 4.19-4.21, we show the rekeying cost for the combined algorithms. We denote the logical key hierarchy algorithm by LK H . For example, LK H = 25% indicates that logical keys are used from height 0( leaf nodes) to height [g] in the key tree and keys from our algorithms are used from height [4}] + 1 to h( root) in the key tree. Also, LK H = 0% denotes that only keys from our algorithms are used in the key tree and LK H = 100% denotes that only keys from the logical key hierarchy are used in the key tree. In Figures 4.22- 59 (3,4,5)-Degree Combination (3,4,5)-Degree Combination 300 I I T T T I I I I 300 I I m I I I I F I N:1024, Degree: (3,4,5) —+— N: 1024, Degree: (3,4,5) —+— N:1024, Degree=5 ~-----x N:1024, Degree=5 -----X 250 ' N:512,Degree=(3,4,5) ......x ‘ 250 ~ N:512,Degree=(3,4,5)-"~II-1 N=512, Degree=5 ------ e-~~ N=512, Degree=5 --..-.B 75 200 __ N:256, Degree=(3,4,5) "‘.’“' _ ‘5 200 _ N:256, Degree=(3,4,5) ""’" 8 N:256,Degree=5 --0-- 8 N:256,Degree:5 we: I Eiw- Eim- I > >4 0 ,,,,,, l o {I - """ r 5 I 100 I. . ....... a: 100 h 50 __ —_’,'. ____ _______ .0.-.-.-.-._._4> 50 __ 0 ”I“ l l l l l l l l 0 0102030405060708090100 0102030405060708090100 Number 01 Revoked Users Number of Revoked Users (a) (b) Figure 4.13: Rekeying cost for (a) 25% (b) 50% low storage users 4.24, we Show the average number of key changes by the users. From these results, we note that, the combination of logical key hierarchy and our algorithms provide a tradeoff between the rekeying cost with the work done by the users. Depending on the tradeoffs acceptable in the group and the requirements of the users, the group controller can choose to use the appropriate combination of these algorithms. 4.6 Summary In this chapter, we presented a family of algorithms that provide a tradeoff between the number of keys maintained by the users and the rekeying cost for the group controller while providing collusion resistance to revoked users. We showed that our algorithms reduce the cost of rekeying by 43% —79% when compared with the previous solutions in [7,19] while keeping the number of keys manageable. Our algorithms enable the group controller to deal with heterogeneous set of users that have different storage capabilities. We showed that this can be achieved by vary- 60 (2,4,5)-Degree Combination (2,4,5)-Degree Combination 60 M I I l I I I U 60 I I I I I I M N: 1024, Degree: (2,4,5) —4—— N: 1024, Degree: (2,4,5) -—+— N:1024, Degree:4 ------x N:1024, Degree:4 ------x 50 ' N=512,Degree:(2,4,5) -:-- ~ 50 ' N:512,Degree=(2,4,5) ......,, ‘ N=512, Degree:4 WB- N=512, Degree:4 .--...B- a 40 L N:256, Degree: (2,4,5) --4-- , ,5 40 _ N:256, Degree: (2,4,5) -+- . 8 N:256, Degree:4 -~e-- 8 N:256, Degree:4 --e-- .3 :3 30 > >. g 2 II E 20 10 0 l l l l I l l J l 0 0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100 Number 01 Revoked Users Number 01 Revoked Users ('4) (b) Figure 4.14: Average key changes per user for (a) 25% (b) 50% low storage users ing the degree of the hierarchy used by the group controller. Also, our algorithms can be combined with the logical key hierarchy [3] to reduce the computational overhead of the users. For example, they are suitable for resource constrained scenarios like overlay multicast applications. In overlay multicast [20—22], the end nodes perform the processing and forwarding of multicast data without using IP multicast support. As these tasks result in increased overhead at the end nodes, reducing traffic is an im- portant problem for overlay multicast. Using simulation results, we showed that it is possible to achieve a tradeoff between the rekeying cost and computational overhead of the users. 61 Average Work Done Rekeying Cost 100 80 40 20 0 0 (3,4,5)-Degree Combination I l I W U W I I N : 1024, Degree: (3,4,5) —+— N:1024, Degree=5 -----X N:512,Degree=(3,4,5) -----* .l N=512, Degree=5 ------ e ----- N: 256, Degree: (3,,4 5)- 1 - N: 256, Degree: 5- 1 l l l I l l l l 10 20 30 40 50 60 70 80 90 100 Number of Bevoked Users (81) (3,4,5)-Degree Combination 100 I I I I I I I I N : 1024, Degree: (3,4,5) —+— N:1024, Degree =5 ------x 30 c N =512, Degree: (3,4,5) " if - 8 N=512, Degree=5 B--. 8 N = 256, Degree: (3,4,5) -....- E 60 ~ N:256, Degree=5 -.0__ _ o . 3 8: E 40 7 o > . < 20 ~ 0 010 20 30 40 50 60 70 80 90100 Number 01 Revoked Users (b) Figure 4.15: Average key changes per user for (a) 25% (b) 50% low storage users 350 250 150 (2,3,4,5)~Degree Combination lN : 1'024, begrée: (213,45) —+—~' N:1024, De ree:4 ------x _ N : 512, Degree : l2,3,4,5) ------x N=512, Deglee=4 ..... B N: 256,ND2egGee:-(2,3,,45)-1- Degree: i 1020 30 40 50 60 70 80 90100 Number of Revoked Users (84) Figure 4.16: Rekeying cost for ( (2,3,4,5)Degree Combination 350 , I F T I I I N = 1024. Degree: (2,3,4,5) —+— 300 [- N:1024,D ree:4 ---x-- _ N=512, Degree: 2,,,345) ...... N=512, Degree:4 ...... (3.... N: 256, Degree- (2345) 4 i N:256, Degree:4 . . E N 8 ES Rekeying Cost é I Ii I". II II '5. I3. It: 'IIIIIIIII 0 0102030405060708090100 Number 01 Revoked Users (b) a) 25% (b) 50% low storage users 62 Average Work Done 0') O U! o A o (A) o N O 10 (2,3,4,5)-Degree Combination ' N = 512, Degree = ' N ='1024,'oegn'ae: (5,345) 4— N:1024, De ree = 4 ---x-- (2,3,4,5) --x-- ‘ N=512, Degree:4 ------ B ----- N = 256, Degree: (2,3,4,5) --+— - N:256, Degree = 4 --e-- J l l l l l I L L 10 20 30 405060 7080 90100 Number of Revoked Users (21) Average Work Done 60 50 40 30 20 10 0 0 (2,4)-Degree Combination l i F I l l I N = 1024, Degree: (2,3,4,5) —+— N:1024, De ree : 4 ------x N = 512, Degree = (2,3,4,5) M, N=512, Degree:4 ------ B N = 256, Degree: (2,3,4,5) -~-l-- ‘ N:256, Degree = 4 -- 0- ! l l I l l l l l 102030405060708090 Number of Revoked Users (b) Figure 4.17: Average key changes per user for (a) 25% (b) 50% low storage users 100 Figure 4.18: Partial view of a hierarchy combined with key graphs 63 Rekeying Cost Rekeying Cost Hybrid Key Tree Hybrid Key Tree I I I I I I I l I I I I I I 700 LKH=0% ——+—— LKH=0% —-+~— ’ LKH=25% -----x 500 _ LKH=25% ----x-- _ LKH=50°/o “--.-4 LKH=50°/e ....,.,... LKH=75% 0 «- LKH=75% 0 - 60° ' LKH=100% ------ _ LKH=100% :-~ 4oo — _4 500 ~ ,,,: .. ’ JD 400 - 0 _ g 300 - _ 0 - fl ..-.u _ I], ,’I [3‘ u". t .9" 300 - , a: _- ..... ‘3‘ 0C 200 - 200 100 - 100 o l l J l l l l l L o l l l l l l J l I o 10 20 30 4o 50 so 70 80 90 100 o 10 20 30 4o 50 60 7o 80 90100 Revoked Users Revoked Users (a) (b) Figure 4.19: Rekeying cost for (a) 1024 (b) 512 users in a degree 3 key tree Hybrid Key Tree Hybrid Key Tree 700 _ ' ' ' iKHéoo/o ‘—+'—— _ ' ' ' 1 [KEN/e '-—+'— LKH=25% -----r< 500 - LKH=25% ------x . LKH=50% a: LKH=50% .-4... LKH=75°/e 0 LKH=75°/e ----- 0 ----- 50° ' LKH=100% —--- J. LKH=100% ------ 400 e ’4 .. r" ,1 I, 500 it :5 ,"’- - - 300 - m 400 1’ g 0- g ’0‘ 0 ..... l’.’ J! E; If" _..ril 300 - ._ 0' .. - a) 0 W. ,, .1: CE 200 _ [I] . 4 200 ’0 4x- 100 — " . 100 x o l J l l L L I l l l l l l l l I J L o 10 20 30 4o 50 60 70 so 90100 0 10 20 30 4o 50 60 7o 80 90100 Revoked Users Revoked Users (60 (b) Figure 4.20: Rekeying cost for (a) 1024 (b) 512 users in a degree 4 key tree 64 Hybrid Key Tree Hybrid Key Tree 600 I r r r j I I I LKH=0°/o —+— LKH-45% -----.x LKH=50°/o Mare 500 _ LKH=75°/°. ..... 8“" .4 LKHBIOO‘Yo -,_.__,_ ,4 _ 4oo - _ m , O o .3 300 > d) x d) a: 200 100 0 010 20 30 40 50 60 7O 80 90100 Revoked Users (b) Figure 4.21: Rekeying cost for (a) 1024 (b) 512 users) in a degree 5 key tree I l T 1 I T I LKH=0°/o ——+——- 700 - LKH-129% '--)<--- "i are? = ‘7, ------ E} 600 - LKH=100°/o "‘. I‘ll-4‘ 500 4 x1," _, '63 , ’ _. JD 0 z, i 0 [I . c» 400 . ’- ..Ct - .E . , 5. I"! . f, 300 )- l,’ ,B it ............. if m I, .It“ I . ________ 4: 200 - ...-"Di .'*.'l 100 — ,,x O 0 10 20 30 40 50 60 70 80 90 100 Revoked Users (8) Hybrid Key Tree 50 l I T T r j I LKH=0°/o —+—- 45 ) LKH=25% -----.x LKH=50% --..“ 40 F LKH=75% W LKH=100°/o ---I---- " 35 )- .4 ‘9' o 30 '- .. c g 25 - 0 § 20 . D 15 - 10 b ’ .. ' ,. I3 xi-“."- .8” B" 5 ’§~"ZL0.---:---.e---r--.---,,_- .-., 0 I L L 1 1 l l l J 0 10 20 30 40 50 60 70 80 90 100 Revoked Users (3) Hybrid Key Tree 50 I l I f I I r LKH=O°/° __+_._ 45 - LKH=259/° ---x-—- d LKH=50°/° -.....* 40 ~ LKH3100°/o '--l- " 35 r- - ‘9’ o 30 e A S .3 25 - + E‘ 8 20 — d o 15 - 10 - ,, 0 - 1 ‘ A 1 L L4 1 I l l 010 20 304050 60 708090100 Ftevoked Users (b) Figure 4.22: Average key changes per user for group of (a) 1024 (b) 512 users in a degree 3 key tree 65 so 45 40 35 Decryption Cost Hybrid Key Tree I I I I I I T I LKH=0°/e ———+—— _ LKH=25% -—--x- 1 LKH=50% -.--..,, LKH=75% B , t LKH=100% -—-- ( Hybrid Key Tree 50 f f I I I I I LKH=O% —+— 45 __ LKH=25°/o “'X““ _, LKH=50% “““ *‘ ' ' ' LKH=75% D » 4° ' LKH=100% ----—- ‘ 35 - - Decryption Cost 0 0 0 10 20 30 40 50 60 7O 80 90100 0 10 20 30 40 50 60 70 80 90100 Revoked Users (at) Revoked Users (b) Figure 4.23: Average key changes per user for group of (a) 1024 (b) 512 users in a degree 4 key tree 80 7O 60 50 4o Decryption Cost 30 20 10 Hybrid Key Tree I I I f T I I I LKH=0°/e —+— L LKH=25% ------x LKH=50% ..._,,. LKH=75% ~70 - LKH=1O - -- - --0---~-~—-:--—-~--~~I-—-~--- ' L 1 1 1 l L L 1 I 0 0 1O 20 30 40 50 60 70 80 90100 Revoked Users (6)) Hybrid Key Tree 80 I I I I I I I LKH=0°/o —r—— LKH=25% ---x--- 70 - LKH=50% ~~~n--- ~ LKH=75% B LKH=10 ---I -- 60 I. .. Decryption Cost _- 1' -.-... -_ 1- - midi-1-7-7.1”- -i-.._,1_._._.l._..- T O 10 20 30 40 50 60 70 80 90100 Revoked Users (b) Figure 4.24: Average key changes per user for group of (a) 1024 and (b) 512 users in a degree 5 key tree 66 Chapter 5 Key Distribution Algorithms In this chapter, we address the issue of key distribution in group key management algorithms. The motivation for developing key distribution algorithms is that, in the group key management algorithms( [3,6, 16, 23]), different subsets of users share different keys. When users are revoked, to encrypt a new key, the group controller uses a shared key known to a particular subset of users and broadcasts it to the group. All the users in the group receive this encrypted message, but only the users belonging to the subset of the shared key can decrypt this message. Thus, the users are interested only in a fraction of the key update messages, i.e., the messages encrypted with the shared keys they possess. This shows that, broadcasting of all key updates results in additional network traffic and in wastage of network resources. In applications like wireless networks and overlay multicast, to improve performance, there is a critical need to reduce such network overhead. To address these problems, there is a need for key distribution algorithms using which, a majority of the messages are delivered to a subset of users only if they encrypted with a key known to that subset. In Section 5.1, we describe our descendant tracking scheme that enables the in- termediate nodes( cf. Figure 2.1) to approximately track its descendants. Using the descendant tracking information the intermediate nodes forward the key updates only 67 if their descendants need the key updates. In Section 5.2, we describe our algorithm for assigning identifiers to users. Using our assignment algorithm, the group con- troller arranges users close to each other in the key tree if they are close to each other in the multicast tree. Our identifier assignment algorithm can be used to improve the performance of the key distribution algorithm in Section 5.1 as well as that of a previous solution in [24]. In Section 5.3, using simulation, we show the performance of our algorithms and compare it with a previous solution [24]. In section 5.4, we show the application of our key distribution algorithm to the scenario of secure interval multicast [13]. Finally, in Section 5.5, we summarize the chapter. 5.1 Our Approach: The Descendant Tracking Scheme A simple method to track descendents is to store the identity of each descendant user and forward the key update message only if any descendant user needs this key. However, this straightforward solution requires each intermediate node to store a large amount of information, especially in large groups. Thus, there is a need for an efficient descendant tracking scheme which can address the key distribution problem. To describe our descendant tracking scheme, first, we define the steady state con- figuration of the multicast tree( cf. Figure 2.1). Then, we describe the technique used at the intermediate nodes to update the descendant tracking information to ac- count for group membership changes. In Sections 5.1.1-5.1.2, we describe how keys encrypted with logical and complementary keys are forwarded by the intermediate nodes using the descendant tracking information. Although we only describe forward— ing mechanisms for logical and complementary keys, our techniques can be extended in a straightforward manner to forward keys in other group key management algo— rithms [6,7,16,23] as well. Our key distribution algorithms consist of the descendant 68 tracking scheme and the forwarding mechanisms used by the intermediate nodes to forward keys encrypted with logical and complementary keys. Steady State Configuration. At each intermediate node, we store a h x d matrix called DT( Descendant Tracker), where h and d are, respectively, the height and degree of the key tree. Each element in DT is a single bit. Thus, the informa- tion kept in DT is very small, even for large groups. For example, for a group of 1024 users, where the group controller maintains a key tree of degree 4 and height 5, each intermediate node stores only 20 bits of information in DT. To track a de- scendant user with identifier rim-2”,“ at an intermediate node, we set the elements, DT[1, 2'1], DT[2,z’2], . . . , DT[h, z’h], to 1. For example, in Figure 5.1, we show the DT entries at the intermediate nodes R1 and R2 from Figure 2.1. (1 (degree) —> d (degree) —+ (1 (degree) ———- htheight) 1 2 3 4 Mbeight) 1 2 3 4 h(height) 1 2 3 4 l 1 O l l 0 4 1 O 1 0 O 1 0 l l 0 2 l 1 1 0 (OR) 2 l 0 0 O __. 2 l l l 0 3 l O 0 0 3 l 0 O O 3 l 0 0 0 4 1 O 0 0 4 l 0 0 0 4 l O 0 0 R] entries for users U(2211, 331 1, 3111) Before disjuction, R2 entries for U2111 Combined entries at R2 Figure 5.1: DT entries at intermediate nodes R1 and R2( cf. Figure 2.1) Tasks for Join. When a new user joins the group, the group controller dis- tributes any keys, the new user needs, using a secure unicast channel. Also, the group controller distributes the new keys to the current users, where the intermediate nodes perform appropriate forwarding( cf. Sections 51.1-51.2), using the existing DT entries. The new user receives its identifier from the group controller and pro- vides this information to its local intermediate node. The local intermediate node updates its DT matrix. Further, if the DT matrix has changed, it propagates this information to its ancestors in the multicast tree. 69 Tasks for Leave. When a user leaves the group, we do not update the DT entries at the intermediate nodes immediately. We perform an update of the DT entries only when the number of group membership changes exceeds a threshold level. Although this could cause some messages to traverse extra links, updating the DT matrix periodically allows us to achieve a tradeoff between the processing overhead and the amount of bandwidth reduced. 5.1.1 Forwarding Key Update Messages Encrypted with Logical Keys In a key tree with only logical keys [3], each user knows all the keys associated with its ancestors. Thus, based on the naming scheme of the key tree from Figure 3.1( cf. Section 3.1), the label of every key a user knows is a prefix of the user’s identifier. Now, consider the case when some user, say u1112( cf. Figure 3.1), leaves the group. The group controller changes all the keys known to 141112 and distributes them to the remaining users who need these keys. The new keys generated by the group controller are kin: ’11, k’l and, kg. To send these keys, the group controller sends, k1111(k[11), k1113(k(11),k1114(k(11),k1,,(kil),k112( i1), (91130511), 16114061), kidki), ($12031), 1613090 k14(k(), k’1(k;), k2(k;), k3(k;) and 14409;). The approach for a joining user is similar. To determine if a key update is needed by any descendants of an intermediate node, we need to determine whether the label of the encrypting logical key is a prefix of at least one descendant in the intermediate node’s DT matrix. To allow the intermediate nodes to make this identification, the group controller includes the label of the encrypting logical key in the key update message and transmits it to the users. For example, to send k12(k’1), the group controller appends the label 12, to the encrypted message. To identify if the label 11,..lk of the encrypting logical key is a prefix to any descendant user, an intermediate node checks whether the DT elements, DT[1, 11],. . . ,DT[k, 1),] are all set to 1. 70 5.1.2 Forwarding Key Update Messages Encrypted with Complementary Keys We note that, in a key tree with only complementary keys( cf. Section 3.3.3), each user knows the keys associated with the siblings of its ancestor. Thus, the labels of these keys differ in the last position from any prefix of the user’s identifier. For example, a user u1113( cf. Figure 3.1), knows the complementary keys, 01111, c1112, c1114, c112, c113, 0114, cm, c13, 614, c2, c3, c4, the group key kg and the personal key k1113. Now, we consider the case when this user leaves the group. The group controller generates new keys for all the keys known to 111113 and distributes them to the other users who need them. The rekeying method used by the group controller for distributing complementary keys is similar to the method for distributing logical keys. The group controller encrypts the changed complementary keys at the higher levels using the changed complementary keys at the lower level. For example, to distribute c’12, the group controller generates the messages, c312(c’12), c113(c’12). To determine if a key update is needed by a descendant of an intermediate node, we need to determine whether the label of the encrypting complementary key differs in the last position from a prefix of a descendant’s identifier. As in the case of transmitting keys encrypted with logical keys, the group controller appends the label of the encrypting complementary key to the key update message. Thus, to distribute c’112(c’12), the group controller appends the label 112 to the message. To verify that the label l1, l2,.., 1,, of the encrypting complementary key is matched, an intermediate node checks whether the entries, DT[l, l1], DT[2, lg], ..., DT[k — l, (,,,-1] and any entry DT[k, (,,] where p 7e k, are set to 1. As an illustration, the intermediate node U1211( cf. Figure 2.1), on receiving the message [c’lz(c’2), 12] forwards it, as the entries, DT [1, 1], DT[2, 3] are set to 1. These entries correspond to the prefix 13, of a descendent user 1312, which differs in the last position from 12, the label of the encrypting complementary key. 71 5.2 User Identifier Assignment Algorithm Our key distribution algorithms route the key update messages based on the iden- tity of the descendants. The performance of these algorithms can be improved if the distribution of leaf nodes( group users) in the multicast tree corresponds to the distribution of the leaf nodes in the key tree. In this ideal scenario, users close to each other in the multicast tree will need almost the same key update messages and hence, the cost of key distribution would be low. While such a scenario is not always possible, one heuristic to achieve a near ideal scenario is to assign a joining user a logical identifier that is closer to the logical identifiers of users who are close to this user in the multicast tree. In this section, we use this heuristic to describe a user identifier assignment algorithm. When a user sends a join request, the group controller communicates with this user using a secure unicast channel and learns about the location of the user in the multicast tree. Now, the group controller can use a program such as mtrace [25] to identify other nearby users in the multicast tree and record their logical identifiers. The group controller selects a user u,,,2n,-,, at the first intermediate node which is clos- est to the joining user. To assign an identifier to the joining user, the group controller selects an identifier rim-2”,? such that 2,,, aé it and 1 g p,t S d, i.e., the identifiers differ in the last position. The group controller assigns this identifier to the joining user, if it is not already assigned to any other user. If this attempt fails, the group controller repeats this process with another user at the first intermediate node. As an illustra- tion, consider that the group controller selects the user 111111 at the first intermediate node. The group controller generates the identifiers 1112,1113, 1114, which differ in the last position with 1111. If any of these identifiers are still available, the group controller assigns one of them to the joining user. If no more users exist at the first intermediate node, the group controller selects users at the second intermediate node and so on. 72 In our assignment algorithm, as the intermediate nodes are further away from the joining user, the group controller successively moves up the position at which the identifiers differ. For example, the group controller selects a user, inn-,,,,“ at the second intermediate node, and tries to assign the joining user, u,,,-.,,_,:p,,, such that ip % ik, i.e., the identifiers now differ in the second last position. As an illustration, consider that the group controller selects the user 712111 at the second intermediate node. The group controller generates the identifiers, 2121,2131,2141, which differ in the second last position with 2111 and tries to assign one of these identifiers to the joining user. If the users are found at the third intermediate node, the group controller tries to assign identifiers which differ in the third last position and so on. The group controller repeats this process until it successfully assigns an identifier or stops, if the only users found are very close to itself. In case the group controller finds that the only intermediate nodes with users are very close to itself, the group controller assigns the next available identifier to the joining user. We do not select the logical identifiers of users close to the group controller due to two reasons. The first reason is that these users are not in the proximity of the joining user. The second reason is that these users, being close to the group controller, receive almost all of the key update traffic anyway and, thus, there would be no performance gain if the joining user is logically closer to these users. 5.3 Performance Analysis In this section, we evaluate the performance of our key distribution algorithms and compare them with a previous solution [24]. We note that, the previous solution, called LKH W, was proposed in the context of secure group communication in adhoc networks. We describe details of this algorithm next. 73 CUl For Clll 98' UP 01 lit? C8 to to] but Previous solution. In [24], to distribute the changed keys in the key tree, the group controller encrypts the keys at the higher levels using changed keys at the lower levels. For example, when ulm leaves( cf. Figure 3.1), to distribute a new key k], the group controller generates the messages k[1(k(), k12(k(), k13(k]) and k14(k]), where the key k], is already distributed using keys further down in the key tree. Before transmitting these messages, the group controller broadcasts the identifier of the leaving user to the current users. Using this information and knowledge of the structure of the key tree, each user calculates the level numbers of the changed keys it needs. This information is propagated towards the group controller. Upon reception of replies, the group controller transmits the key update messages and includes the level number, at which the key is changed, in each message. When an intermediate node receives a key update message with a level number I, it forwards the message to its descendants only if some descendant of I had requested that key. The main shortcoming of this key distribution algorithm is that, it is executed for every membership change which causes delay at the users for receiving key updates. We note that, this problem is not present in our algorithms, as the intermediate nodes maintain static information about the identities of their descendants. Methodology of Experiments. We simulated our algorithms using the NS2 net- work simulator [26]. We performed experiments on randomly generated network topologies for groups of 256, 512 and 768 users. We used the CBT [27] protocol to build the multicast tree with the group controller as the root node. For each experi- ment, we selected a random set of users to join or leave the group and recorded the number of messages in the multicast tree over the entire multicast session. We define the following metrics to measure the performance of our algorithms: 0 K ey update Bandwidth( KB W). This is the number of links traversed by each key update message, i.e., this is the network bandwidth used by the key update messages. 74 Total Bandwidth( TB W). This is the number of links traversed by all messages exchanged over the multicast tree. This metric includes the key update band- width and the control messages exchanged among the intermediate nodes. Key update Bandwidth Reduction Ratio{ KBRR). This ratio is the measure of key update bandwidth saved using our algorithms as against using broadcast. We calculate it as follows: (K B Wb-roarlcast " K B Woptimised / K B Wbroadcast)*100 Total Bandwidth Reduction Ratio( TBRR). This ratio is the measure of total bandwidth saved using our algorithms as against using broadcast. We calculate it as follows: (TB Wbroadcast _ TB Woptimi sed / TB Wbroadcast) * 100 Per Hop Bandwidth Reduction Rati0( PBRR). This ratio is the hop wise breakup of the TBRR for a given network topology. This metric gives an overview of the performance of our algorithms as function of the network dis- tance away from the group controller. We conducted experiments on three key management algorithms. The first al- gorithm is the logical key hierarchy algorithm( LKH) in [3]. The second and third algorithms are the algorithms from Chapter 3. In the second algorithm, the group controller uses complementary keys at every level in the key tree. We refer to this algorithm as complementary key hierarchy( CKH). In the third algorithm, the group controller uses both logical and complementary keys at every level in the key tree. We refer to this algorithm as logical+complementary key hierarchy( LKH+CKH). For comparison purposes we also simulated the previous key distribution solution from [24]. We use the following notation to refer to the various key distribution algorithms: 75 o Id-based: Our key distribution algorithm from Section 5.1. o Id-based—cluster‘. Combination of algorithms in Sections 5.1 and 5.2. o Level-based: The key distribution algorithm from [24] that we described at the beginning of this section. 0 Level-based-clustert Combination of algorithms in [24] and 5.2. In Figures 5.2-5.4, we plot the K BRR for groups of 256, 512 and 768 users. From these figures, we observe that the K BRR achieved in our key distribution algorithm is in the range of 20—55%. Bandwidth Reduction Ratio -‘ N (0 8 0'1 O? \I O O O O O O O I I I ld-based —+—— ld—based-cluster --.---.., , Level-based ----' -- _ Level-based—cluster o L 20 40 60 80 100 c Number of Leaving Users (3) Bandwidth Reduction Ratio \1 o 70 I 'ld-based —'~— [Id-based _'._ 60 Id-based—cluster ~---*-- , 2 60 _ Id~based~ciuster ---»--- , Level-based ''''' - a Level-based ,,,-.. Level—based-ciuster a II Level-based—oluster ,,, J 50 ’ g 50 t 40 ' "“" ‘3' 40 ~ * p g I Mir 30 5 30 4 :9 2‘ ---------------- 20 - g 20 /\t g .21/ 10» m 10 ,/ . .A‘ _v' / o ' 1 1 1 1 0 l 1 L 1 1 0 20 40 60 80 100 0 20 40 60 80 100 Number of Leaving Users Number of Leaving Users (b) (c) Figure 5.2: KBRR for 256 users in (a) LKH (b) CKH (c) LKH+CKH In Figures 5.5—5.7, we plot the TBRR for groups of 256, 512 and 768 users. The TBRR achieved is in the range of 20-45%. We observe that using our identifier assign- ment algorithm improves the K BRR and TBRR of our key distribution algorithm as well as that of the level based key distribution algorithm [24]. In Figures 5.8-5.13, we plot the PBRR, for K BRR and T BRR, for a group of 768 users. A random set of 100 users leave this group during the session. The leaf nodes in this group are at a distance of up to 6 hops from the group controller. The 76 70 T T 70 I T 70 I I ld-based + Id-based —+-— td-based —+— .9 50 _ Id-based—ciuster --—--+ , 9 50 , ld-based—oiuster ---"... , _g 60 _ Id-based-cluster ---—--* , a Level-based -----n- a Level-based ~~~-~ a Level-based - ~ I! Level-based—ciuster ~ 0 (I Level-based—cluster - 0- ,, (I Level-basedciuster . e c 50 r c 50 ’ ‘ c 50 ' .0 2 2 3 4o . 8 4o - 8 4o - ‘D 'O D a? a” 6‘6 5 3° 1' 5 30 - 'n... 5 30 E i E " E ,7 """""" 4.- % 20 . 4 g 20 - ,,,, % 20 - ..4- t 5 5 5,271! g .. r- m10~ m10rf/ m10- i o 1 1 1 o 1 1 L 0 1 1 L 0 50 100 150 200 0 50 100 150 200 0 50 100 150 200 Number of Leaving Users Number of Leaving Users Number of Leaving Users (6)) (b) (C) Figure 5.3: KBRR for 512 users in (a) LKH (b) CKH (c) LKH+CKH PBRR value for Hop Number 1 indicates the K BRR( respectively, TBRR) observed between hop 0( group controller) and hop 1( immediate children of group controller) and so on. From Figures 5.8-5.13, we observe that the Level-based algorithm causes more link stress near the group controller due to the responses by the users for each membership change. We note that, this problem is remedied by using our identifier assignment algorithm which reduces the link stress near the group controller in this algorithm. 5.4 Application to Security of Interval Multicast The concepts used in our key distribution algorithms can also be used in other secure multicast applications, especially in applications that require data to be securely transmitted to only a subset of group users. One such application is the security of interval multicast, described in [13]. In this application, the group controller securely multicasts data to a selected interval( subset) of users. To send a message to the interval of users, the group controller identifies the key(s) that are shared among 77 70 r a 70 r v 70 1 i ld-based —+-— ld-based -+- ld-based ....— 2 60 F Id-based—duster ~+~ , 2 60 _ Id-based-cluster ----*-- , 2 50 _ Id-based—duster ---*--- , a: LeveLbased ----- . ii Level-based ------- a Level-based m. I Level-based-cluster .9 a: Level-based-cluster ~ 6 r 03 Level-based-cluster -- 9 c 50 ' i c 50 t ‘ c 50 i .9 .9 .9 Sm- 84oL Swi '0 ‘O 'O Q) d) 0 E 30 ' ___________ . ._ 11 E 30 ' ' I 41 E 30 I g 4' 1' r: -------- . a L a 32°" . s20 . a202, m 10 - w m 10 - ,I/ m 10 - J', .1; o 1 1 1 0 l 1 1 1 o 1 1 1 0 50 100 150 200 0 50 100 150 200 0 50 100 150 200 Number oi Leaving Users Number of Leaving Users Number of Leaving Users (a) (b) (c) Figure 5.4: KBRR for 768 users in (a) LKH (b) CKH (c) LKH+CKH these users in the key tree. The group controller encrypts the message with each of the keys and broadcasts it. As the keys selected to encrypt the message are known only to the users in the interval, only those users can decrypt that message(s). An example of an interval multicast scenario is when this subset of users subscribe to a premium program in addition to the content being sent to the entire group. To illustrate the concept of interval multicast, consider the Figure 5.14 in which the users are arranged in a logical key hierarchy. In this figure, the users U12 to U23 is an interval of users as they have consecutive ids in the key tree. To send a secure message to this interval, the group controller selects the keys that are known only to the users in this interval. For this example, the group controller selects the keys, K12, K13 and K 2 to encrypt the message. We note that, in the secure interval multicast algorithm [13], all the group users receive the encrypted message(s) due to the broadcast even if they do not need that message(s). To reduce bandwidth utilization, we reuse the techniques from Section 5.1. Hence, the bandwidth usage in the security of interval multicast algorithm can be reduced if the encrypted messages are distributed to only those users who need them. 78 \l O \l O Id-based —+—— i ld-based—ciuster ----»-- 1 Level-based ----- ---~ ( Level-basedcluster a - . Id-based —+— ld-based—ciuster ---._-.,. , Level-based . _ Level-based—ciuster ~ .9 ld-based —r-— 60 id-based—duster ----x~-- , Level-based ----- ----- _ Level-based—ciuster ”a a, O I 8 88 I 1_ 88 N o I N o I Bandwidth Reduction Ratio w o Bandwidth Reduction Ratio 00 o p Bandwidth Reduction Ratio o: O i O I d o I \ l l 0 20 40 60 80 100 0 20 4O 60 80 100 0 20 40 60 80 100 O O o l— Number oi Leaving Users Number oi Leaving Users Number of Leaving Users (80 (b) (c) Figure 5.5: TBRR for 256 users in (a) LKH (b) CKH (c) LKH+CKH Towards this end, we reuse the techniques used in our key distribution algorithms to distribute data to the interval of users. For key distribution, during group setup, the intermediate nodes use the descendent tracking scheme from Section 5.1 and the cor- responding forwarding techniques. Now, the descendant tracking information can be reused to distribute data to the interval of users. The group controller generates the encrypted messages that need to be sent to the selected interval. Before transmitting the encrypted messages, the group controller includes the label of the encrypting key with each message. For example, to distribute kn (data), the group controller includes the label, 11( logical key, cf. Section 5.1.1), along with the encrypted message. The intermediate nodes use the forwarding technique described in Section 5.1.1( respec— tively, Section 5.1.2 for complementary key), and forward this message only if there are descendents who know this key. In Figures 5.15-5.16, we show the performance of our key distribution algorithm for the security of interval multicast. The key management algorithm used is the logical key hierarchy algorithm. Again, we note that, using our key distribution algorithm there is bandwidth saving of up to 25% in the interval multicast. Furthermore, using 79 70 70 \l o ld-Ibased '—+—— Id-rbased '—.—— ld-based 1+— 9 60 ld-based-cluster ------* q 9 60 _ id-based-cluster ~-*--- 4 _9 60 _ ldbased-ciuster -------v+ . a Level-based . ~» ‘5 Level-based - -~ ‘5 Level-based - ~ II Level-based-cluster . a (I Level-based—cluster . a (I Level-based-ciuster -- a c 50 ' c 50 * c 50 - 9 .9 .9 g 40 . g 40 ~ g 40 r “O '0 ‘O a? a” a? n 30 L. 30 . 'o..1. I 30 ~ § § 20 '1 :6 2 ~* """""" w... 20 ' " , , 0 " I, .. ------- \agd! E E E "A” I. m 10 . 11:10 m 10 r- f ' / ./ 0 1 1 L 0 L 1 1 0 ’ 1 1 1 0 50 100 150 200 0 50 100 150 200 0 50 100 150 200 Number oi Leaving Users Number of Leaving Users Number of Leaving Users (a) (b) (c) Figure 5.6: TBRR for 512 users in (a) LKH (b) CKH (c) LKH+CKH our ID assignment algorithm improves the performance by a small margin. Due to similarity of results we have only shown the results for two group sizes 256 and 512. 5.5 Summary In this chapter, we addressed the problem of distributing key updates to users in se- cure dynamic groups. Towards this end, we described a descendant tracking scheme to track the descendants of the intermediate nodes in the multicast tree. In our de- scendant tracking scheme, each intermediate node stores a small information about its descendants. Next, we described the forwarding mechanisms used by the interme- diate nodes based on the descendant tracking information. Each intermediate node forwards an encrypted key update message only if it believes that its descendants know the encrypting key. Using simulation results we showed that our key distribu- tion algorithms reduce the bandwidth needed for distributing key updates in the key management algorithms in [3,16] by up to 55% when compared to the broadcast of key updates. 80 \J O 70 r , Id-based —+— 60 _ ld-based-dusier ------» , Level-based ...... -~ ( Level-based—ciusier‘ a - ‘ ld-based —+— ld-based-ciusier ------* . Level-based . ~- _ Level-based—ciusier — a ld-based —+— 60 , id-basedciusier -*--- , Level-based ----+ “ _ Level-based—ciuster — a 03 O 50 01 O 40- «h o t m 30- 'i 20- Bandwidth Reduction Ratio N (A) O O Bandwidth Reduction Ratio 10* Bandwidth Reduction Ratio _s o ' o p- P O b- p— y- 0 50 100 150 200 0 50 100 150 200 0 50 100 150 200 Number oi Leaving Users Number oi Leaving Users Number oi Leaving Users (8) (b) (C) Figure 5.7: TBRR for 768 users in (a) LKH (b) CKH (c) LKH+CKH Also, we described an algorithm for assigning identifiers to group users so that users who are physically close in the multicast tree are assigned logically close iden- tifiers. We showed that our assignment algorithm improves the performance of our key distribution algorithms as well as that of the previous solution in [24]. Using our key distribution algorithms, we described a solution to distribute data messages in secure interval multicast [13]. Interval multicast occurs so often in secure multi- cast applications that reducing bandwidth during this phase is critical for improving performance. Note that we have not addressed the correctness and performance of our key distribution algorithms in the face of multicast tree failures and repairs. We note that, this is not a serious issue as we perform periodic updates of the DT matrix which handles any changes in the descendant information for an intermediate node. If any users fail to receive key updates because of multicast tree reconfiguration, the group controller simply retransmits them to the users once the multicast tree stabilizes and the DT matrices are updated. Furthermore, for our key distribution algorithms, it is not necessary that all the intermediate nodes store the DT matrices. 81 140 . ld-based ;— . 140 ~ Id-based '—+— . 140 L Irfised ;— . 9 ld-based-ciusier -------I _9 ld-based—cluster ----I-- .9 ld-based~ciusier --..-_,. 16 120 . Level-based I -- . a; 120 . Level-based '* - ‘6 120 ~ LeVel-based .....m g E Level-basedclusier a CI Level-based—ciusier 0 rr Level-based-ciuster ~~o 5 100» ~ ,5 100» ,3 100» § ,1 ‘g‘ g E 80» 1’ E 30+ )r E ao~ 5 60 « 5 so» /1' 5 so- % 40 P 4 g 40 __ ’ / _1 g 40 i- ., ' g ,. g j g m 20‘ i m 20'l i m 20 0 l o .l 1 1 0 ”/17 1 L 1 3 1 1.5 2 2.5 3 1 1.5 2 2.5 3 Hop Number Hop Number Hop Number (a) (b) (C) Figure 5.8: PBRR (KBRR) for 256 users in (a) LKH (b) CKH (c) LKH+CKH We note that, a few selected nodes at appropriate points in the multicast tree are sufficient. 82 Bandwidth Reduction Ratio Bandwidth Reduction Ratio 140 - 120 - id-based —+—— . ld-based-cluster -----I Level-based ---- Level-based-ciuster a 2.5 3 Hop Number (3) Bandwidth Reduction Ratio 140 ~ id-based ——+—' ld-based-ciusier "-..... l 120 - Level-based .... .. 1 Level-based-dusier o 100 r- 80 ~ 60 . 40 — 20 i 0 1r" 1 1-5 2 2.5 3 Hop Number (b) Bandwidth Reduction Ratio 140 - f ld-based —'—+— _ ld-based-ciuster --_,__.,, 120 - Level-based ...... .. . Level-based—ciuster ~ 5 100 r 4 80 " + ,1: 60 i 2.4.. // .11 40* _ i 20 » 42/ 1 Hop Number (0) Figure 5.9: PBRR (KBRR) for 512 users in (a) LKH (b) CKH (c) LKH+CKH 140 - Q 100 ' ld-based —~— 4 id-basedciusier ---I--- Level-based ----- I--~~ . Level-based-ciuster a 7 L41 J l 1 l I 11.5 2 2.5 3 3.5 4 4.5 5 Hop Number (a) Bandwidth Reduction Ratio 140 120 ~ 100 'Id-based —.—' ‘ . idbased-ciusier "....t. Level-based-duster o , g’ ' "/1 1 1 1 1 L 1 Level-based I-- 1 11.5 2 2.5 3 3.5 4 4.5 5 Hop Number (13) 83 Bandwidth Reduction Ratio 140- ' 'ld-base'dLJ—q id-based-dusier -.-—...r 120 - Level-based ..... .... q Level-based-cluster -~a 100 - 80 ~ 60 . 4o . 20 . Off 1 l 1 1 1 1 4 11.52 .53 544.55 Hop Number (c) Figure 5.10: PBRR (KBRR) for 768 users in (a) LKH (b) CKH (c) LKH+CKH Bandwidth Reduction Ratio Bandwidth Reduction Ratio 140 . ld-based L.— ‘ id-based-ciusier ---..r-- 120 L Level-based ..... ...... fi Level-based-ciuster a 100 i 80 60 4o . 20 ~ .. 0 ¥ ‘ 1 1 2.5 3 Hop Number (3) Bandwidth Reduction Ratio 140 - ld-based —+——-' . ld-based-duster --.---... 120 - Level-based ....... Level-basedciusier . .5, 100 - 80 . 60 4o . 20 . 0 I," 1 L Hop Number 0)) Bandwidth Reduction Ratio id-based -'—+— . 14o - Id-based—cluster ----..» 120 - Level-based ..... ...... ‘ Level-based-ciuster - ~a 100 i 80 - 60‘ {I}; 40 I 1 20 - ',. 0 in/ 1 J 1 l 1-5 2 2.5 3 Hop Number (C) Figure 5.11: PBRR (TBRR) for 256 users in (a) LKH (b) CKH (c) LKH+CKH Id-based 3+— . 140 . Id-based-cluster ---I~-- 120 . Levelcbased "1 ” . Level-based-ciuster Ia ., 100 . 80 F ,7“ J so - // ’u'lx J) 2.5 3 Hop Number (a) Bandwidth Reduction Ratio 140 E; 80 60 40 20- ’ Level-based-dusier - a 100 - id-based ._+_ . ld-based-duster ---I-- Level-based ------I - . 11 / [00/ l 1 1.5 2 2.5 3 ”Op Number (b) Bandwidth Reduction Ratio 140 I id-based .14.. . ld-based-ciuster ----me 120 - Level-based -.-... _ Level-based-ciuster - ~e -. 100 i . 80 ~ .11 50 ~ , . 40 ' 3,11 0 L"! 1 1 1 1-5 2 2.5 3 Hop Number (c) Figure 5.12: PBRR (TBRR) for 512 users in (a) LKH (b) CKH (c) LKH+CKH 84 Bandwidth Reduction Ratio 140 - I j 'ld-baseIi L;— , ld-based-clusier «mt 120 - Level-based ----- .. .. ‘ Level-basedciusier ~ 8 100 - 4 80 r w”! +——-—-"“’ 60 - 4 40 I ‘ Ii 20 _ I 11.5 2 2.5 3 3.5 4 4.55 Hop Number (81) Bandwidth Reduction Ratio 140» ‘ rid-based L; . id-based-duster --....t 120 . Level-based .. . Level-based-ciuster ~90 - 100 - 80 ~ ___,_..‘i 60- /;\/ 40 . j ,. i _________ .1. 20 - // 0 [.11 1 19 1 1 11.5 2 2.5 3 3.5 4 4.55 Hop Number (b) 140 . I j fild-baseld Ln:- ~ 0 ld—based-ciusier ---I-- ‘5 120 . Level-based ......” . a: Level-baseddusier ~ ’8 ,5 100 - § .8 80 r- .. [I fly--..fl‘ _________ i 3%- 60 h l/IV’ .. _f’ II a 40 - / . C ,I/ 8 20 b .’/‘ l L l l I 1 11.5..22533544.55 HopNumber (C) Figure 5.13: PBRR (TBRR) for 768 users in (a) LKH (b) CKH (c) LKH+CKH E‘fli R R Ein LK13J JK21JJK22JJK23J K32J D33 J m {Uniivni iUfl EELUJIJ Bfli‘bzii‘bai 1 Figure 5.14: Secure interval multicast 85 Reduction Ratio Reduction Ratio Algorithm : LKH Algorithm : LKH 40 r 35 . I ld-tliasedl —Fl— . .0 35 I I I ld-tliasedI —+l— . 30 _ Id-based-cluster -----x _ ‘3 30 _ Id-based-cluster ---x-- - 25 _ x ------ are ------ r ------ r ------ at. _ 0:3 - 20 - - .g - 15 - - g . 10 + - 8 ~ 5 .. - tr . 0 l l l l l l 0 20 40 60 80 100 120 140 0 20 40 60 80 100 120 140 interval Size Interval Size (a) (b) Figure 5.15: KBRR for (a) 256 (b) 512 users during interval multicast Algorithm : LKH Algorithm : LKH 4'0 i l i r l i 40 l l l I h T 35 - ld-based + - 9 35 - Id-based —+— q 30 _ ld-based-cluster ------>< _ “5 30 _ ld-based—cluster ------x - 25 - >9 ------ at ------ $- ----- 4.9 we 7 E 25 - - 20 ~ - g 20 - - 15 v - g 15 - - 10 _ . 8 10 - . 5 - ~ (I 5 r ‘ 0 l l l l l l 0 1 l l l l l 0 20 40 60 80 100120140 0 20 40 60 80 100120140 Interval Size Interval Size (a) (b) Figure 5.16: TBRR for (a) 256 (b) 512 users during interval multicast 86 Chapter 6 User Revocation in Adhoc Networks In this chapter, we extend our group key management algorithms to revoke users from adhoc networks. We note that, our group key management algorithms cannot be directly applied to adhoc networks as there are several limitations in adhoc networks. These limitations may include, lack of efficient broadcast mechanism, lack of routing infrastructure, lower capabilities of users and lossy network links. Hence, to address these issues, our group key management algorithms need to be suitably modified for revoking users in adhoc networks. In the group key management algorithms [4, 5, 16, 23] to revoke users, the group controller distributes a new group key to all the users. Using the new group key, the remaining users can update the shared keys using the one-way function approach described in Section 3.4. However, in adhoc networks, due to lack of efficient broadcast mechanisms, it may not be possible to distribute the group key in an efficient manner. An alternate approach for distributing the group key is to initially send the group key to a subset of users [28]. Now, this subset of users can distribute the group key securely to the other users in the group. However, for such group key distribution, 87 the users in the adhoc network need to be able to communicate securely among them- selves. This problem of establishing secure channels among users in adhoc networks is addressed by secret instantiation protocols [IO—12,29]. In this chapter, for user revocation in adhoc networks, we propose an algorithm that combines the secret instantiation protocols [10—12, 29] and the group key man- agement algorithms [3,5, 7,9, 16,23]. Depending upon the protocols used for secret instantiation and group key management, we get different properties for revocation. We proceed as follows. In Section 6.1, we describe our revocation algorithm. The attractive feature of our revocation algorithm is that the group controller is only briefly involved in establishing the group key and the bulk of the group key distribution is done by the users themselves. In Section 6.2, we illustrate an instance of our revocation algorithm. In Section 6.3, we evaluate the performance of our revocation algorithm in two network scenarios, i.e., netWorks with routing support and those without any routing support. Using experimental results, we show that it is possible to achieve revocation in both these scenarios. Finally, in Section 6.4, we summarize the chapter. 6.1 Combining Secret Instantiation with Group Key Management The goal of the secret instantiation protocol is to provide an initial collection of secrets to users such that the users can utilize them to communicate securely. These protocols can be probabilistic [10] or deterministic [11,12]. Furthermore, these protocols may require communicating nodes to depend on intermediate users [10] or they may assume that intermediate users are not trusted [11,12]. ( By trust in intermediate users, we mean that they can( or are required to) decrypt and re—encrypt messages they forward. In all the protocols [10—12], the intermediate users are trusted to route the messages. 88 However, in [11,12], they cannot decrypt them.) We recall that, in the group key management algorithm, a group of users shares a group key ———known to all the users, along with some other secrets ——shared by different subsets of users. When one or more users are revoked from the group, the group key should be changed in such a way that only the remaining users in the group can access the new group key. The distribution of this new group key is facilitated by the other secrets that the remaining users possess. Additionally, these algorithms change any other secrets that the revoked users had in such a way that the changed secrets are not available to the revoked users. Examples of these algorithms include [2,3,5,7, 17] and our revocation algorithms from Chapters 3 and 4. In our approach, we combine the secret instantiation protocol and the group key management algorithm as follows: initially, each user is associated with secrets from both protocols. Now, the users utilize the secrets from the secret instantiation proto- col to establish secure communication. When users are revoked, in the first step, the group controller uses the group key management algorithm to send the new group key. However, instead of sending the new group key to all users, the group controller sends it selectively to a subset of users. Especially, in adhoc networks it is desirable to minimize the number of messages sent by the group controller as broadcast is an unreliable operation in these networks. Subsequently, in the second step, other users can obtain the group key from this subset of users using the secrets from the secret instantiation protocol. Since the secret instantiation protocol enables two users to establish a common secret for communication, it can be used to provide authenti- cation and confidentiality. Note that the second step of the group key distribution can occur in parallel. Finally, the compromised secrets( i.e., secrets from the secret instantiation protocol and the group key management algorithm that are known to the revoked users) are changed locally( cf. Section 3.4) so that the revoked users cannot access them. 89 We only consider those group key management algorithms that ensure that only the remaining users get the new group key and any other secrets they shared with revoked users( e.g., [2,3,5, 7, 16, 23]). Now, depending upon the protocol used for secret instantiation, the resulting protocol will provide probabilistic/ deterministic security where intermediate nodes are trusted/untrusted. Specifically, if we use the deterministic protocol from [11, 12], where intermediate users are not trusted, then the resulting revocation algorithm will guarantee that after revoking users( up to a certain limit) the remaining users can communicate with deterministic security. Likewise, if we use the probabilistic protocol from [10], where intermediate users are trusted, then the resulting algorithm will guarantee that, after revoking users, the remaining users can communicate with probabilistic security. 6.2 Instance of Revocation Algorithm Now, we illustrate an instance of our revocation algorithm in which we use the square grid protocol from [12] for secret instantiation and the logical key hierarchy [3] for group key management. We show that, our algorithm retains the property of deter- ministic security. We proceed as follows. In Section 6.2.1, we describe the square grid protocol [12]. In Section 6.2.2, we describe the logical key hierarchy algorithm [3]( cf. Chapter 7 for more details). In Section 6.2.3, we describe the combination of these two protocols. 6.2.1 The Square Grid Protocol In the square grid protocol [12], 72. users are arranged in a logical square grid of size fl x J77. Each location, (2', j), 0 S i, j < V5, in the grid is associated with a user um) and a grid secret k(i,j)- Each user knows all the grid secrets that are along its row and column. For example, in Figure 6.1, the grid secret associated with (1, 1) is 90 known to users at locations (j, 1), (1, j), 0 S j S 3. Additionally, each user maintains a direct secret with users in its row and column. This direct secret is not known to any other user. For example, user u(1,2) shares a direct secret with user, u(1,3), which is located in the same row( cf. Figure 6.1). (0,0) <0,1> (0,2) <03) <1, 1> as <1,» <2,> as <2,2> <2,3> (3" (3,1) (3,2) <13) Figure 6.1: Square grid protocol: A node marked ( j, k) is associated with user WM) and grid secret ICU-,,,) Now, consider the case where user A wants to set up a session key with user B. Let the locations of A and B be (j1,k1) and (j2,k2) respectively. In this case, A selects the session key and encrypts it using the following secret selection protocol. Secret selection protocol for session key establishment for users at (j1,k1) and (j2,k2) // If users are neither in same row nor in same column If 0179.72 /\ k1¢k2) Use the grid secrets log-,,,”) and [€02,160 Else // If users are in the same row or column Use the direct secret between ”mm and “(72,k2) Along with the encrypted session key, A also sends its own grid location( in plain 91 text) to B. If multiple secrets are selected by A then a combination of those secrets( using hash functions like MD5) is used to encrypt the session key. Theorem 6.1 The above secret selection protocol ensures that the collection of secrets used by two communicating users is not known to any other user in the system. Hence, the above protocol can be used for establishing the session key. ( cf. [12] for proof.) [II 6.2.2 Logical Key Hierarchy In the logical key hierarchy [3] algorithm, the secrets are arranged as the nodes of a rooted tree and the users are associated with the leaf nodes of this tree. Each user receives the secrets that are on the path from itself to the root node. As an illustration, in Figure 6.2, we show the logical key hierarchy for the system of 16 users from the square grid of Figure 6.1. Thus, in this arrangement, user U03 receives the secrets K [0,0]_[0,3] and K0. K[1,0]-[1,3 U0,0 U0,1 U0,2 U0,3 1,0 U1,1 U1,2 U1,3 2,0 U2,1 22 U2,3 U3,0 U3,1 U3,2 U3,3 Figure 6.2: Logical key hierarchy 92 6.2.3 Combining of Square Grid with Logical Key Hierarchy To combine the algorithms in Sections 6.2.1 and 6.2.2, we arrange the users in the square grid protocol and the logical key hierarchy algorithml. The users receive secrets from both these protocols. As an illustration, we consider the square grid arrangement in Figure 6.1, which consists of 16 users. Each user receives 0(Jfi) secrets from the square grid protocol. Next, we instantiate a logical key hierarchy of degree 2 in two steps. In the first step, we treat an entire row of users, from the square grid protocol, as a leaf node in the logical key hierarchy, i.e., a leaf node is a row of users from the square grid. As an illustration, in Figure 6.3, we show the first step of this instantiation in which each of leaf node is associated with an entire row of users from the square grid protocol( cf. Figure 6.1). For example, in this arrangement, the row users U (0,0) — U<0,3) are given the secrets, K[0,0]_[0,3], K [0,0]-[1,3] and K0. U[om-[0,3] U[1.01413] U[2,01-[2,31 U[3.0]-[3,3] Figure 6.3: First stage of the instantiation of logical key hierarchy In the second step, we instantiate the logical key hierarchy for each row of the users, i.e., each leaf node is a single user from a row in the square grid protocol and all the leaf nodes are from the same row. As an illustration, in Figure 6.4, we show k 1Note that, except for the special case considered in Figure 6.8, the user organization in the grid and key hierarchy is logical. This organization does not affect the physical deployment of users. 93 190,0] K1911 K{0.2} K{0,31 U[0.01 U[0.11 U[0.21 ”(0.31 Figure 6.4: Second stage of the instantiation of logical key hierarchy. Note that, the root node, K [0,0]-“),3], is the same as the key K [0,0]-“),3] in Figure 6.3. the second step of instantiation for the users U (0,0) — U(0,3), who are in the first row of the square grid protocol in Figure 6.1. For example, in this instantiation, user U (0,0) is given the secrets, K [0,0], K[0,0]_[0,1] and K [0,0]-“),3]. The number of secrets a user receives in the logical key hierarchy is log n. Hence, the total number of secrets that the user needs to store in our revocation algorithm is still O(\/7—z). 6.3 Evaluation We consider two scenarios of revocation. In the first scenario( cf. Section 6.3.1), there is an underlying support for routing, e.g., from [30,31], and hence, a user can send messages to any other user. In the second scenario( cf. Section 6.3.2), we consider the case where the users can only send messages to their neighbors. In the former case, the group controller can use the routing support to transmit the group key to the initial set of users. In the latter case, to transmit the group key, the group controller can use the multicast tree( e.g., built using a protocol such as described in [32]), if such a tree is available. Otherwise, the group controller broadcasts the encrypted group key. Although all the users may receive this message, only the subset of users who know the appropriate shared secret, with which the group key is encrypted, can 94 obtain the group key. 6.3.1 Group Key Distribution With Routing Support We consider two cases of revocation for the scenario when users are able to communi- cate with any other user in the network with the help of underlying routing layer. In the first case, the revoked users are located in r < \/r_z rows and in the second case, the revoked users are located in r = \/r_z rows. Also, we consider a special case of revocation when the square grid is only partially full, i.e., some locations in the grid are not assigned to any user. Case 1. Since the number of rows containing revoked users is < \/T—L, there will be atleast one row in the square grid which does not contain any revoked users. To distribute the group key, we observe that, if users along a row in the square grid know the group key, they can send the group key to other users in their columns using the direct secrets. Since the direct secrets are unique for any given pair of users, this technique guarantees deterministic security. The group controller selects a row(s) of users not containing revoked users and uses the shared secret of this row(s) to transmit the group key. Specifically, the group controller uses the shared secrets from the logical key hierarchy shown in Figure 6.3. As an illustration, we consider revocation of the users, Um», U0», and U(2,2), from the square grid shown in Figure 6.1. Now, to transmit the group key, the group controller selects a row of users, in this example U(3,0)-U(3,3), which does not contain any revoked users and uses the corresponding shared secret, K [3,0]_[3,3]( cf. Figure 6.3). Once these users receive the group key, they use the direct secrets along their respective columns in the square grid to send it to other un—revoked users. For example, to send the group key, user U<3.0) uses the direct secret between itself and user U<2.0)- Similarly, users U<3,1)-U(3,3), send it to users in their columns. To reduce the work done by each user for sending the group key, we use a divide and 95 conquer approach. When a user U,- receives the group key from the group controller, it partitions the users in its column into two parts and sends the group key, along with the partition information, to a user Uj. Now, U, is responsible for sending the group key to the first part. And, UJ- is responsible for sending the group key to the second part. Continuing divide and conquer in this manner, it suffices for a user to send atmost logn messages. Note that, in this approach, some users may receive multiple copies of the group key, but the number of messages sent by each user is bounded by log n. Furthermore, the group controller includes an authentication message( cf. Section 6.3.3) which is used by the users in the network to verify the authenticity of the group key they receive from other users. Theorem 6.2 The above revocation process guarantees deterministic security if the revoked users are located in atmost r < \/T—l rows. D Case 2. When every row contains atleast one revoked user, the group controller cannot use any shared secrets associated with the rows( cf. Figure 6.3). For this case, the group controller sends the new group key to the users in a selected row using a shared secret from the logical key hierarchy of that row( cf. Figure 6.4). Towards this, the group controller locates a shared secret that is known to a maximum number of non-revoked users from the same row. The group controller uses this secret to send the group key to these users. As an illustration, we consider the revocation of users, U(0,0>: U(1,1), U93) and U(3,3), from the network. In this example, the group controller selects the shared secret K [0,2]-“),3] from the logical key hierarchy associated with the row of users U (0,0) — U<0.3)- We note that, the group controller could have chosen any of the other shared keys from the logical key hierarchies of the other rows as, for this example, the maximum number of non-revoked users sharing a key along any row is 2. The group controller sends the group key to U (0,2) and U(0,3) using this shared secret. Now, these users use the direct secrets along their row and columns to send the group key to the other non-revoked 96 users. For example, user U(0,2) sends the group key to user U (0,1) in its row and then proceeds to transmit the group key to users in its column. In the worst case scenario of revocation, where users from a single row are not able to cover the entire group, the group controller sends the group key to users in different rows. Grid=32x32 Grid=32x32 Actual Users: 512 Gfid=32x32 Actual User8= 256 100‘ 1 I I I I 1 I 100 mI IyT I 11 le I 100 XI Tgl I I I I‘ll ll -------- X "" A A K M A A E 80- - g? 30- . E 30- . 8 60- I 3 so- - 8 60, - 0 o 0 II 40- I r 40- ~ I: 40- - \o 20 _ Revoked Users=50 —+— . °\o 20 _ Revoked Users=50 -—+— . o\° 20 _ Revoked Users=50 -—I— _ ° Revoked Users=880 --X--- Revoked Users=100 -----x Revoked UseIs=100 ------x 0 I I I I I I I 0 I I I I l I l I I 0 I I I I I I I I J 1152253354455 02468101214161820 02468101214161820 Number of Senders Number of lnitiaJ Senders Number of Initial Senders (a) (b) (c) Figure 6.5: Group key recovery with routing support for square grid (a) 100 (b) 50 (c) 25% full To evaluate the effectiveness of our group key distribution, we have conducted experiments on the revocation of 50 and 880 users from a group of size 1024 users arranged in a 32x32 grid. The results are as shown in Figure 6.5(a). We note that, when the number of revoked users is less than 85% of the group size, the group controller only needs to send the group key to a single non-revoked user to achieve 100% group key distribution. In the extreme case of revocation, say for 880 users, the group controller needs to send the group key to a small number of users from different rows, to achieve complete group key distribution. Special Case. We consider a special case of revocation in the grids that are only partially filled with users, i.e., some grid locations are empty. This case occurs when a higher grid size, greater than the initial set of users, is chosen for accommodating new users who may join the network at a later stage. We have considered the grids 97 that are 25 and 50% filled and, simulated the revocation of 50 and 100 users. We show the results of our experiments in Figures 6.5(b)-(c). We note that, even for such grids, the group key recovery is 100%. 6.3.2 Local Group Key Distribution In this section, we consider group key distribution when a user is limited to sending messages to only users in its neighborhood. We use the term neighborhood to denote users within a certain hop distance, typically, 1— 3 hops from a user. A user can learn about these nodes by querying its immediate neighbors for a list of their neighbors. Thus, the number of nodes in the neighborhood depends upon the network density and the number of hops. Now, depending on the information available with the group controller, we con- sider two cases. In the first case, the group controller has no knowledge about the neighborhood relations of the users, i.e., the group controller does not know which users are in the neighborhood of a user. In the second case, the group controller knows which users are in the neighborhood of a user. Case 1. To send the group key, initially, the group controller randomly selects a set of un—revoked users. The number of these selected users is based on the average neighborhood size of the users. Once the selected users receive the group key, they transmit the group key to users in their neighborhood with whom they share direct or grid secrets from the secret instantiation protocol. To illustrate our technique, we have considered revocation of 20, 50, and 100 users from a group of 1024 users arranged in a 32x32 square grid. We note that, to revoke 20 users, the group controller can use the technique we described in Section 6.3.1 as the revoked users are along < 32 rows. However, complete group key distribution may not be guaranteed due to the limited communication capabilities of the users. We show the results of our experiments for different neighborhood sizes in Figures 6.6(a)- 98 RevokedUsers=20 RevokedUseIs=50 RevokedUseIs=100 250IIIIIIIII 250TIIIIF7II 250IrIIIITII 5+ 5+ 5+ 3200- 10+ 3200- 10 +4 5200- 10+ grso- 3:31 grso- 33 ..... S ..... - érso- fig ..... 3....- £100 -n .5] ......... s I a $1001, ............ 8 g; ......... sun-H1001, .............. n "g ......... Qwfl °\° 5OI/‘i/x"’lL—_fl1E °\° 50- l E °\0 50' l I OIIILIIIJJ 0.. IIIIIII 0W 02468101214161820 02458101214161820 02468101214161820 Number of Initial Senders Numwoi Initial Senders Number of Initial Senders (a) (b) (C) Figure 6.6: Group key recovery with only local transmissions for (a) 20 (b) 50 (c) 100 user revocation (c). When the neighborhood of users is around 5 — 10 users, for a sparse network, the number of users recovering the group key is only around 3 — 60%. When the neighborhood size is around 25 -—~ 35 users, the group key recovery is 100%, depending on the number of revoked users and the number of initial senders contacted( cf. Figure 6.6(a)-(c)). Thus, to obtain 100% distribution of group key, the neighborhood size should be 25 — 35 users. This can be achieved by contacting neighbors within a certain hop distance until the number of nodes in this neighborhood increases to the desired value. Also, note that a user only contacts a subset of the users in this neighborhood; it only has to contact nodes with whom it can communicate securely in spite of possible collusion among the revoked users. Case 2. When the group controller has information about the neighborhood of users, to send the group key, the group controller chooses the initial set of users in such a way that the users they can reach is non-overlapping. Towards this, first, the group controller selects a un-revoked user and computes all the users who are covered by this user and, its neighbors. Now, to select the next sender, the group controller selects a un-revoked user who is not in the set covered by the previous sender and 99 its neighborhood. Further, the group controller repeats this process until the entire group is covered and then, transmits the group key to the set of the selected users. RevokedUsers=20 RevokedUsers=50 RevokedUsers=100 250IIIIIrIrr 250ITIIIIIII 250rIIIIIIII 5—+- L 5—I— 5+ e200 10 --*--* 2,200 10 er 3200' 10----‘* ° 25 ”if 0 25 ....* o 25 ...*. g 150 - g 150 - - g 150 r a I? [M * ......... * ................. [ g 1w . * ......... * ......... * ......... l[ E [M .. (”n/x, ......... * ........ .} oIIIIIIIIL 0,. IIIIIII 0.1111141 02468101214161820 02468101214161820 0m2468101214161820 NumberoilnilialSendeIs NumberoilnitiaISendm Numberoilnitial Senders (a) (b) (c) Figure 6.7: Group key recovery in local transmissions with neighborhood information As in Case 1, we have considered the revocation of 20, 50, and 100 users from the same network topology consisting of 1024 users arranged in the 32x32 grid. From the results in Figure 6.7, we observe that, for a neighborhood size of 25 users, the group controller achieves 100% group key recovery by contacting only a small set of initial senders. Special Case. We consider a special case of revocation in which the square grid of the users matches the actual physical topology of the network, i.e., the logical topology and the physical topology of the networks is the same. Such a case occurs in static networks where the nodes are deployed in this manner to achieve optimal network coverage. For this special case, we limited the neighborhood of users to only immediate neighbors. The results of our experiments are shown in Figure 6.8. As in Case 2, the group controller achieves 100% group key recovery by contacting only a small set of initial senders. 100 Grid = 32x32 OneHop—Neighborhood T l I l l f I 100 “,39 * ....... x )E"/ at; 80 r- *3 - § so » " - é‘c’ Revoked Users=20 —+—— 20 ' Revoked Users=50 --->6-- ' Revoked Users=100 - - are - - 0 l J l l l I 11.5 2 2.5 3 3.5 4 4.5 5 Number of Initial Senders Figure 6.8: Group key recovery in physical grid topology using one-hop neighbors 6.3.3 Authentication Note that, based on the properties of the square grid and, the logical key hierarchy algorithms, our revocation algorithm ensures confidentiality. We have not addressed the issue of authentication in specific detail as there are several approaches to achieve authentication. One approach is to use public-key authentication. In this approach, the group controller generates a oneway hash of the group key, encrypts this hash value with its private key and sends this value, along with the( encrypted) group key, to the initial selected users. When a user sends the group key to another user using the secrets in the grid protocol, it includes the encrypted hash value sent by the group controller along with the group key. Using the public key of the group controller, the users recover the one-way hash of the group key from this value and use it to verify the validity of the group key. Note that, as the users can only recover the one-way hash of the group key, the revoked users cannot obtain the group key. Another approach is to use a one-way hash chain technique which is similar to the TESLA protocol from [33]. A one-way hash chain consists of a sequence of values, h(s), 112(3), . . . , hm(s), where h is a one—way hash function and s is a random seed. The group controller gives the hash value hm(s) to the users at the time of initial 101 deployment. Also, the users and the group controller are loosely synchronized. At the time of revocation, the group controller broadcasts a hash of the group key which is signed by a hash value, h"(s), where k < m, which can be revealed only at the current time interval. Now, when users receive the group key from other users, they use h" (s) to generate the signature of the group controller and thus, verify the validity of the group key. We note that, a similar authentication model was also employed in the GKMPAN protocol [28]. Depending on the application requirements, the group controller selects the appropriate authentication protocol. 6.4 Summary In this chapter, to revoke users from adhoc networks, we described a revocation al- gorithm that combined the secret instantiation protocols [10—12,29] and group key management algorithms [3,5, 7,16,17,23]. In our algorithm, the security of the revo— cation depends on the combination of the protocols used. We illustrated an instance of our revocation algorithm by combining the square grid protocol [12] and the logical key hierarchy [3] algorithm. Furthermore, we con- sidered two scenarios of group key distribution. In the first scenario, routing support exists in the network and the user can send messages to any other user in the net- work. In the second scenario, no routing support exists and a user can transmit to only users in its neighborhood. Using simulation results, we showed that, it is possible to achieve complete group key distribution in both scenarios. 102 Chapter 7 Related Work In this chapter, we present a survey of research performed on the problem of secure group communication. We classify the related work into, group key management algorithms and key distribution algorithms. In section 7.1, ‘we describe current group key management algorithms. The focus of these algorithms is to reduce the number of encryptions and the number of rekeying messages by the group controller during membership changes. In Section 7.2, we describe key distribution algorithms. The focus of these algorithms is distribute keys to users in an efficient and reliable fashion. 7 .1 Group Key Management Algorithms We describe three important classes of group key management algorithms: logical key management algorithms, Broadcast encryption algorithms and distributed key management algorithms. In logical key management and broadcast encryption algo- . rithms, a trusted group controller is in charge of handling the group membership tasks of adding and removing users. In distributed key management algorithms, there is no central group controller. Group membership changes and key management tasks are performed by selected users or a group of trusted servers. 103 7 .1.1 Logical Key Management Algorithms Logical key management algorithms are thus named as the group controller arranges the users in logical subgroups and associates a different key with each such logical subgroup. In these algorithms, each user of the group the following keys: (1) personal key, (2) the group key, and (3) shared keys. The personal key of a user is known only to that user and the group controller. The group controller uses this key to communicate securely with the user. The group key is known to all the users in the group and is used to encrypt data sent to the group. Each user also receives the keys of the logical subgroups to which it belongs. These keys are called shared keys as they are shared with all the users in a logical subgroup. The shared keys are useful in reducing the cost of rekeying for the group controller when group membership changes. Logical Key Hierarchy. Logical key hierarchy was first suggested by Wallner, Harder and Agee [2] and a more general version was proposed independently by Wong, Gouda and Lam [3]. In logical key hierarchy, the group controller arranges the users and keys of the system in a rooted binary tree. The nodes of the tree correspond to the keys and the users are associated with the leaves of the tree. I“‘- ' I if I'I I' (mourn. 10151016107] Us] Figure 7.1: Logical key hierarchy When the group is initialized, each user receives the group key and the necessary shared keys. Each user knows the shared keys that are on the path from the user 104 to the root node. In other words, each shared key is known to all the users that are descendants of that node. The root node corresponds the group key and is known to all the users in the group. For example, in Figure 7.1, user U1 knows the keys, K1, K12, K1234 and K3. The number of keys known to each user are, logN + 1 and the number of keys stored by the group controller are 2N — 1, where N is the group size. Revoking a user. To revoke a user from the group, the group controller performs the following tasks: (1) changes the group key and, (2) changes the shared keys known to the revoked user. The group controller multicasts the new keys securely to the remaining users using the shared keys not known to the revoked user. For example, consider that user U1 is revoked from the logical key hierarchy in Figure 7.1. The group controller generates new keys for K12, K1234 and K a, which are known to the revoked user. The group controller sends the following messages to distribute the new keys: . To U2: K2(K{2) T0 U23 Ki2(Kl234) To U3,41 K34(Kl234) T0 U2,3,43 Ki234(Kf;) To U5,6,7,81 K5678(Kf;) To distribute a new key at each level the group controller uses the keys at the lower level which are not known to the revoked user. Once the keys at a level are updated, the new keys are used to update the keys at the higher levels. Thus, in a binary logical key hierarchy, the cost of revoking a user in logical key hierarchy is logg(N) encryptions and log2(N) messages. Adding a user. To add a user to the group, the group controller performs tasks that are similar to those when revoking a user. The group controller creates a new 105 leaf node in the binary key tree, either, (1) by creating a new sibling node for an existing leaf node of degree 1 or, (2) by splitting an existing leaf node of degree 2. Case 1. When the new user is added as the sibling of an existing leaf node, the group controller generates new keys for the all the nodes that are on the path from the new user to the root. The group controller sends the new keys to the new user by encrypting them with the personal key of the new user. To send the new keys to the remaining users, the group controller encrypts each new key with the corresponding old key, i.e., the key that is being replaced is used to encrypt the new replacement key. This way the group controller ensures that only users who knew the older version of the shared key can decrypt the newer version of that key. Case 2. When the binary tree does not contain any leaf nodes with degree 1, the group controller selects a leaf node with degree 2. The‘group controller creates a new node and inserts it between the leaf node and its parent node. Thus, the original leaf node is now the child node of the newly created intermediate node. The new user is now added as the other child of the newly created node. The group controller generates new keys for the necessary nodes, including the newly created node, and distributes them securely using the method described in Case 1. Complementary Variables. This technique was proposed by Wallner, Harder and Agee, alongside the logical key hierarchy technique [2] In this technique, the group controller maintains a set of N variables, K1, K2, . . . ,KN. A user U,- receives all the variables from this set except the variable K ,-. In other words, all users, other than U,-, know the variable K,. Thus, the group controller and the users store 0(N) variables. Using this distribution, to revoke a user U,, the group controller encrypts the new group key with K ,- and multicasts it to the group. All users except U,- will be able to decrypt this message. The cost of revocation using complementary variables is 0(1) messages and encryptions. This technique, however, is infeasible as the number of keys stored at the user is very high. Moreover, this technique suffers from the 106 problem of user collusion. Any two users in the system can pool in their keys and obtain all the group key updates. Versakey Framework. In the logical key hierarchy [2] and key graphs [3], the group controller stores 0(N) keys. To reduce the number of keys stored at the group controller, the Versakey framework was proposed by Waldvogel, Caronni, Sun, Weiler and Plattner [4]. In the Versakey framework, for group of size 2W, the group controller maintains a table of 2W + 1 keys. One entry in the table holds the group key known to all the users. Each other entry, k, in the table holds two keys: k.bv(0) and k.b,,(1), where, by, denotes the bit-value. Each user is assigned a unique W-bit binary ID and each user receives the key, k.b,,(:r), if the kth bit value in its ID is equal to bv(:c). Thus, the number of keys stored at the group controller is 0(log N). As an illustration, in Figure 7.2, we show the table that the group controller maintains for a group of 23 users. Each user is associated with a 37bit ID. For example, user 101, receives the keys, K1.1, K 2.0 and K 3.1, from this table. Bit#l ——> KLO Kl.l Bit“ —’ [(2.0 K2.1 Bit # 3 —> K3.0 K3.1 KEK Table W=3 Figure 7.2: Table of keys in Versakey framework Revolving a user. To revoke a user from the group, the group controller generates a new group key. For example, to revoke user 101, the group controller encrypts the new group key with the keys that this user does not know, i.e., K 1.0, K 2.1 and K 3.0 and multicasts these messages to the user. Each user in the group knows atleast one of these keys as the ID of the revoked user differs from the ID of any other user in atleast one-bit location. 107 To update the shared keys known to the revoked user, the group controller gener- ates new shared keys, K1.1’, K 2.0’ , and K1.1’. To securely distribute a new shared key, the group controller performs dual encryption, first with the older version of the shared key and then, with the new group key. For example, to send K 1.1’ , the group - controller first encrypts it with K1.1 and then, encrypts this message with the new group key. Thus, only the current group users who know the older version of the shared key can decrypt this message. In the Versakey framework, the cost at the group controller for revoking a user is, 2W messages and 3W encryptions. Drawbacks of Versakey. The Versakey framework does not work in some scenar- ios of multiple user revocation. For example, if users 010 and 101 need to be revoked from the group simultaneously, the group controller cannot find the necessary keys to encrypt the new group key. Moreover, this scheme is susceptible to collusion among users. Two users can exchange information among themselves to remain the group permanently. For example, when a user :3 is revoked from the group, the group con- troller updates the shared keys known to :12. However, if some other user y were to provide :1: with the new group key, then, a: can obtain all the newer versions of the shared keys. Thus, a: continues to be part of the group even after it is revoked and can obtain any future group key updates. Now, if y were to be removed from the group, y can obtain the new group key from a: and consequently obtain all the newer versions of its shared keys. Thus, a: and y continue to be part of the group until the group controller re—initializes the group. Boolean Minimization Techniques. A solution similar to the Versakey framework [4], was proposed by Chang, Engel, Kandlur, Pendarakis and Saha [5]. The main feature of the solution in [5] is that, boolean minimization techniques are used to reduce the cost of revoking multiple users. Another important feature of this solution is that the new versions of the shared keys are not distributed by the group controller. They are computed by the users themselves using the new group key. This 108 technique reduces the total number of messages sent by the group controller while slightly increasing the computation at the users. The key management technique used by the group controller is identical to that of the Versakey framework. Each user is assigned an W—bit ID, Xw_1, X W2, . . . , X0. The bit value X,- is denoted by 2:,- when Xi=1 and if, when X,=0. The set of keys received by the user are denoted by Kw_.1 , Kw_2, . . . , K0. The key K,- is denoted by k,- when X,=1 and by E, when X,=O. Note that, k,- and E, are two different keys which are represented this way to suit boolean optimization techniques. User revocation. To revoke a single user the group controller uses the same technique used in the Versakey framework. The group controller encrypts the new group key with keys not known to the revoked user and multicasts these messages to the group. Thus, the cost of revoking a single user is 0(W) messages and encryption. To update the shared keys that are known to the revoked user, the group controller and the users use a one-way hash function f as follows: K,+1 = f (K,, K 3), where K ,-+1 and K,- are the newer and older versions of the shared key respectively, and K ,3 is the new group key. To revoke multiple users, instead of revoking each user sequentially, a more efficient strategy is employed. The group controller computes the minimum number of keys that are known to the remaining group users using boolean minimization techniques. To find this set of keys, the group controller defines a boolean membership function, m() is such that m(q) = 1 if the user with ID c,- belongs to the current group, and m(q) = 0 if the user has been revoked. The group controller generates the function, m(Xg, X1, X0): c1+ c2 + . . . + Cj, where each c,- is of the form, XZXIXO and the user c,- is part of the current group. The resulting boolean membership function can be viewed as a Sum of Product Expressions( SOPE) over the user IDs. For example, if two users, have a bit value X,- common in the same position 2', in their IDs, it translates to a common key, K ,-, known to these users. Thus, the problem of finding 109 Input Output x2 x1 x0 C0 -» 0 0 0 1 Cl —» 0 0 1 1 C2 —> o 1 0 1 C3 -> o 1 1 0 C4 —-» 1 o 0 1 cs —> 1 0 1 1 C6» 1 1 o 1 C7 —- 1 1 1 0 Figure 7.3: Boolean membership function, m. the minimum set of keys to cover the entire group translates to that of minimizing the boolean membership function, i.e., the SOPE expression. The minimized boolean expression determines the keys that the group controller can use to send the new group key. SOPE expressions can either, be minimized using Karnaugh maps for a small number of variables or by using Quine—McCluskey minimization technique for large number of variables. For example, consider that two users, 03 with ID 011 and c7 with ID 111, are revoked from the group simultaneously. A table is generated using the boolean mem- bership function. The table generated for the leaving of users c3 and c7 is shown in Figure 7.3. The table shows that the membership function evaluates to 0 for c3 and 0;, while it is 1 for the remaining users. The Karnaugh map for the resulting table is shown in Figure 7.4. The resulting minimum size expression is 70 + 71, where the ’+’ denotes the logical OR. This expression shows that it is sufficient for the group controller to encrypt the new group key with E0 and F1. The remaining users in the group know atleast one of these keys and can decrypt the new group key. Thus, in the boolean minimization technique requires 0(log N) storage by the group controller and the users, and 2 log N messages for rekeying the group. However, this technique suffers from the same drawbacks as 110 the Versakey framework. XIXO XIXO X2 00 01 ll 10 X2 00-01 ll 10 0 1 1 0 1 "0“:1'5 [ 1; 0 {'1'” 1 1 1 o 1 1 .1:___1__: o j_1__ a) Karnaugh Map b) Prime Implicants Figure 7.4: Minimization using Karnaugh maps. One-way function trees. McGrew and Sherman propose a solution [6], based on the use of one-way functions, to reduce the size of the rekeying messages when compared to that of the logical key hierarchy [2] and [3]. Similar to the spirit of key tree based solutions [2,3], the group controller constructs a binary key tree and associates the users with the leaves of the tree. The main contribution of the one-way function tree solution is that, the key tree is constructed bottom-up. The users are associated with the leaf nodes of the key tree. Each node, :1: in the key binary tree is associated with two keys: k, and k;. The value, k; 2: g(k_.c), is the blinded value of k2, obtained by passing k3, through a one-way function 9. Although it is easy to compute k; from km, it is computationally infeasible to calculate k,c from k;. Now, each internal key node in the binary tree is generated as follows: k1. = f (9(k31eft), g(er,-ght)), where f is a mixing function. In other words, a node key, k3, is a combination of the the blinded values of its left and right child node keys. At the time of group initialization, each user is assigned to a leaf node and given the unblinded value of that node. Also, each user also receives all the blinded keys of the siblings of the nodes on the path from itself to the root. Thus, if necessary, each user is able to generate all the unblinded values of the keys from itself to the root node. The number of keys stored by each user is log N + 1 which is the same as the number of keys stored in the logical key hierarchy [2] and key graphs [3] solutions. A one-way function tree is shown in Figure 7.5. The grey nodes denote the blinded 111 values of keys known to user v and the black nodes denote the unblinded values of keys known to it. Root key . / o E 1E Figure 7.5: One-way function tree. User join. When a user, u, joins the controller splits up an existing leaf node v. The controller sets u as left child of the split node and v as the right child of the split node as shown in Figure 7.6. The group controller sends new private keys to each of the users. Since, the users have new private keys, all the blinded keys of the siblings from these users to the root are changed. The group controller distributes the new blinded values to the appropriate subsets as follows: to send a blinded value k; to descendants of a sibling node k,, the group controller encrypts k; with k, and broadcasts it. The new user receives the necessary blinded keys from the group controller in a secure unicast channel. The number of messages sent by the group controller is h + 2, which include the unicast messages sent to u and v. The joining user is able to compute all the necessary keys with the given information. User revocation. To revoke a user from the group, the controller deletes the node associated with this user and its sibling, p, becomes associated with its parent node. This node p is now given a new private key value if it is a leaf node. Otherwise, if p is not a leaf node, then one of the leaf nodes in its subtree is given new private key value so that the blinded key of p is changed. Again, the group controller broadcasts the appropriate blinded keys securely using the same technique used in the join op- 112 Figure 7.6: One way function tree, after user 11 joins. eration. The number of messages for revoking a user is h + 1. The one—way function tree achieves a new lower bound on the number of rekeying messages while slightly increasing the computation at the users. Authentication and Revocation Techniques. . Authentication is an im- portant requirement in group communication setting, especially, when the group has multiple senders. The group key cannot be used to authenticate different senders as any one in the group can sign packets with the same group key. On the other hand, identifying all senders and storing all the necessary keys to authenticate the senders is not a scalable solution. To address this problem of authenticating multiple senders, Canetti, Garay, Micciancio, Naor and Pinkas [14] proposed techniques for au- thentication based on message authentication codes( MACS). In the same paper, the authors propose a user revocation technique that is similar to the one-way function tree techniques [6]. Single source authentication. Authentication is achieved by shared keys instead of using public-key infrastructure. The sender maintains a set of keys, I = e(w + 1)log(1/q), R = (K1, K2, . . . , K1) and each user, u, maintains a subset of these keys v = elog(l/q). The sender computes a MAC —message authentication code, using each of the keys it holds. Computing a MAC is less expensive than using a public key to Sign the signature. Each user verifies a subset these packets using the set of 113 keys it possesses. Using this technique, the authors have shown that the probability of forging a message is atmost q + q’ for a coalition of w users, where q’ is the probability of computing the output of a MAC without knowing the key used. The authors show that, by increasing the number of key by 4—times, the per-message probability( non- forgeable) can be increased to q and the coalition resistance probability to q. Multiple source authentication. To achieve multiple source authentication a set of l pseudo—random functions, (f1, f2, . . . , f,) are used. Each user receives a set of v keys from chosen from a pool of l = O(wlog(1/q)) primary keys with a probability 1/(w + 1). Every sender, u, receives a set of l secondary keys as follows , S“ = (fk,(u), flew), . . . , fk,(u)), i.e., the keys of each sender are tied to the identity of the sender. Now, using this set of keys, each sender computes the MAC of every message and each receiver, v, computes the secondary keys of u that it possesses in common with u. Using these secondary keys, the receiver can verify the MACS. The probability of message forgeability and computational overhead are the same as in the case of the single source authentication with the slight addition of computing the secondary keys on the receiver side. The advantage of this technique is that it allows for a dynamic set of sources and no coalitions of senders can break this scheme. Revocation of users. The key management scheme is similar to the [2], [3] and, follows the same technique as that of one-way function tree described in [6]. However, instead of one—way functions, the authors use a pseudo—random generator G (11:) which doubles its input into two equal halves, L(:z:) and R(:r). All the users are arranged in a binary tree and each user, u, is associated with a random value r. Every node, v, on the path from u to the root, is associated with a value defined as follows, rpm == R(r,,) = R'“"'”', where p(v) denotes the parent of node v. The keys are defined by k” = L(r,,) = L(R'“'“l”"1(r)). So, given r,,, a user, u can compute all kv’s. To remove a node, u, from the group, the group controller changes the value rpm. This, in effect, changes all the keys from, s(u) to the root node, where s(u) is the sibling of 114 u. The new p(u) is unicasted to u. The group controller sends the changed R(r,,)’s to all the siblings of the ancestors of u, by encrypting them with the corresponding, ks(,.)’s, for all v’s from u to the root. This technique has the complexity of logN bits which is the same as the complexity of one-way function trees [6]. Communication and Storage Tradeoffs. Canetti, Malkin and Nissam [34] proposed algorithms that tradeoff the communication complexity with the number of keys stored at the group controller and the users. The bounds established in this work are as follows: 0 Upper bound between center storage and communication. For user storage, b + 1 keys, the communication is 0(lm1/b -— b) and center storage multiplied by communication length is approximately O(n). 0 Upper and lower bounds between user storage and communication. A com- munication lower bound for a user storage of atmost b + 1 keys is atleast nl/b messages. The authors combine the communication efficient tree-based solutions of [2,3,14] with the storage efficient linear solution of [1] and present constructions which achieve these bounds. The set of users are split up into 777. disjoint subsets. Each subset is assigned as the leaf of an a-ary tree. The interior nodes of the a-ary tree correspond to keys. Each user belonging to a leaf node( one subset of users) receives all the keys from itself to the root node. The group controller revokes users in two phases, (1) removes the user from the leaf node he belongs according to the scheme of [1] and, (2) distributes changed keys in the tree using the scheme of [14]. The storage cost of the user and the center are, loga(%) +1 and {ii—i, respectively. The communication cost is m —- 1 + (a — 1)logafi. The maximal communication cost using this scheme is 2 anb — b where b + 1 denotes the maximal number of keys held by any user. 115 Information Theoretic Analysis of Key Tree Algorithms. In the algo- rithms described in [4,5], if two users were to collude then, all the keys in the system are revealed. Whereas in [2,3], collusion is not a problem and these systems can revoke any number of users. In [35], the authors describe an information theoretic analysis of these algorithms and show that they are extreme solutions to the prefix-coding problem in rooted trees. Prefix-coding of key storage. Each user is arranged as the leaf of a rooted D-ary tree. The ID of each user is codeword of logDN numbers, which is obtained by concatenating the positions of the ancestors of the user. The group controller associates a key with each node in the key tree. Each user receives all the keys that are present in its ID. For example, in a binary key tree, each ID is of logDN bits and each user receives logDN + 1 keys. Given this formulation, the condition for user revocation is that no assigned codeword should be a prefix of another codeword and no two users must have the same codeword. If the codeword lengths are denoted by, l,, then, a key management algorithm satisfies these requirements if it satisfies Kraft’s inequality: 232:1v D“ s 1 The converse statement is true, i.e., given a set of codewords satisfying this re- quirement, it is possible to find a rooted tree in which it is possible to revoke any user. Thus, the problem of selecting an optimal number of keys stored at the user is equivalent to the problem of selecting the optimal codeword length in the prefix- coding problem. Using the results of information theory, the optimal codeword length is given by Shannon’s entropy. If a user revocation has the probability, p,, then the optimal codeword length, is given by: l,- = 409010.- The algorithms in [2—5] assign equal probabilities of revocation to all the users and hence result in the maximum entropy, i.e., maximum length of the codeword which 116 corresponds to higher number of keys. Moreover, the authors show that the schemes in [4,5] are not collusion resistant for groups beyond 4 users. Optimization Based Key Management. In [14], authors described a key management algorithm which can achieve sub—linear center storage of 0(5371)‘ The open problem posed in [14] was, whether or not it is possible to retain 0(logN) communication bound with sub-linear center storage ? The problem is to optimize the storage cost: (1+ 3);)? w.r.t M, subject to the communication constraint: M —- 1+ (a —— 1)loga-g- S fllogaN, where 5 2 1, all the terms in the equations have the same meaning as those described in [14]. In [35], the authors address this problem by posing it as a constraint optimization problem. They observe that, since storage decreases monotonically with respect to the cluster size M, it is sufficient to find the values of M that satisfies the update communication constraint and the largest value of M will be the solution for opti- mizing the constraint equations. The authors use standard equation solving meth- ods for finding optimal values of M. The storage required at the group controller is S = (a_l()%;:i\2)fig N and the optimal cluster value is M = (fl — A)logeN, where A = fl. For these values, the group controller is able to achieve sub-linear storage as well as logarithmic communication cost. Efficient Revocation Schemes for Secure Multicast. Applications like conferencing require that the participating users be capable of forming arbitrary sub- groups. Whereas, in applications like stock quote dissemination, pay-TV etc., only the group controller is capable of forming subgroups. The former applications are termed dynamic group initiator based applications while the latter are termed static group initiator based applications. In [7], the authors describe key establishment and revocation schemes for addressing both these kind of applications. 117 Dynamic initiator scheme. A group controller initializes the system and estab— lishes the keys in the system. The group controller arranges the keys in the system as the nodes of a d-ary balanced tree. The users are arranged as the leaf nodes of this tree. Each node in the key tree is associated with a public-key, private-key pair. To each user, the group controller sends all the private-keys on the path from the user to the root and posts all the public-keys on a publicly available bulletin board. To send a message to a select subset, a dynamic group initiator, sends the message encrypted with the public keys that cover the receiver subset. The target receiver set use the corresponding secret keys to recover the message. To find a covering key set for the receivers, the group initiator first marks the non-target receivers as being revoked from the group and finds the most common ancestral nodes for the target receiver set. The storage in this scheme is long + 1 keys. To revoke one user, i.e., to send a message to the rest of the group while excluding this user, the group initiator sends (d - 1)long — 1 messages. The best case rekeying cost is O, i.e., when the target set has a single common ancestor and, the worst case rekeying cost is (1 — %)N — 1. Static Initiator Scheme. The static initiator scheme is an extension of the dynamic initiator scheme, except that the public keys are are not necessary as the group initiator has complete knowledge of all the keys in the system. The group initiator finds a key cover as before, i.e., by revoking non-target set receivers and encrypts the message with the secrets keys from this cover. The rekeying and storage costs of this scheme are similar to the dynamic initiator case. Secure Rekeying Scheme with Key Recovery One important requirement of rekeying in secure multicast is that the users need to be able to recover the group key updates even if they are off-line during the rekeying period. In [9], the authors describe revocation schemes, using one-way hash chains, which enable users to recover a group key even if they were off-line when that particular group key was transmitted. Rekeying scheme. To revoke or add a. single user, the group controller generates 118 the group key as, f "(3), where, f () is a hash function and fr(s) denotes the hashing of s by r—times. To recover the group key, the users who know f k(s), where, k < r, need to hash this value, r — k times. The group controller selects the keys that are the siblings of the ancestors of the revoked user( or ancestors in the case of joining user). To send a hash value at level i, the group controller encrypts, f i(r), with all the keys selected at that level and transmits these messages. Thus, the users need to receive only at — 1 messages to recover the new group key. This advantage comes at slightly added computation at the users in the form of oneway hashing. To revoke a single user, the number of messages sent by the group controller is (d — 1)long( respectively, to add a user the group controller sends long messages). Recovery scheme. The recovery scheme is based on redundancy. The group key, K,, in a session, i, is split into two parts, P,- and S,. A simple construction for, K,- = P,- ®S,-. P,- is included in t session packets sent before session i and S,- is included in t session packets sent after session i. For example, for t = 2, i = 4, packet, P4 is included with session packets of 2 and 3 which are encrypted with K 2 and K 3 respectively. Thus, a user going off-line during t sessions can still recover all the missed session keys. The cost of this scheme is 2t messages while the computation at each user is t XOR operations. Kronos Framework. Kronos [36] is a periodic rekeying scheme. This scheme is aimed at those groups which have very high frequency of leaves and joins, and which would increase the key management overhead at the group controller. The idea is to periodically rekey the group ignoring the group membership changes. The pe- riod of rekeying is selected to reflect the group dynamics or application requirements. The scheme is a distributed key management, similar to [37] as there are intermedi- ate nodes which manage individual subgroups. The individual subgroup controllers themselves can use hierarchical key management algorithms like [3—6], for scalable rekeying. This scheme provides an important abstraction, that of uninterrupted data 119 transmission, which is important in many multimedia transmissions. The decoupling of membership changes and rekeying achieves better service with the tradeoff that a few non-members continue to receive data for a small period of time. 7 .1.2 Broadcast Encryption Algorithms The term Broadcast encryption was coined by Fiat and N aor in their paper [38] of the same title. Broadcast encryption addresses the problem of protecting media content that is broadcast or distributed to a set of users. For example, a typical broadcast encryption application is a cable TV pay-per-view program. Only a valid set of users are allowed access to the program in a limited time—frame. Note that, the target receivers are different for different programs and the target set are selected from the same universe of users. The center distributes a key management block to each user. Before distributing a program the center generates a session key which can be derived with only those keys held by the target receivers and transmits this key. A valid user can generate the session key using only the key management information. Thus, the main parameters that need to be reduced in broadcast encryption are, the length of transmission of the session key, the size of user storage and the computation at the user. Moreover, a broadcast encryption scheme must address attacks by coalitions of users who can attempt to recover a session key for the session that they do not belong. The state of the art works in broadcast encryption are the SDR [17] —— subset difference revocation scheme and the LSD [18] —layered SDR schemes. Other improvements of these schemes have been described in [39—41]. Broadcast Encryption. Fiat and Noar [38] presented a broadcast encryption algorithm which provided resistance against an arbitrary, but, fixed number of col— luding users. The number of keys held by the users in their scheme is proportional to the size of the colluding users. Using their algorithms, the center can broadcast a secret to an arbitrary subset of users while providing collusion resistance against a 120 fixed size subset of users. K-resilient scheme. To construct a k-resilient scheme, the authors use a 1- resilient scheme as the basis. In the 1-resilient scheme the center can broadcast a secret to any coalition of users while being resistant to a collusion of 1-user. To extend this to k-resilience, the center uses a set of l one-way hash functions such that, some f,- is one-to—one for a coalition of up to k users. The center constructs, R(i, j) 1~resilient schemes, where 1 g i g l and 1 S j g m. Each user 1 receives a subset of keys from these 1-resilient scheme, R(i, f,(:r)). To send a message to a target set T, the center generates M = QZ] M,- messages and broadcasts them using the 1-resilient scheme R(i, j)]f,(:r) = j where :r E T. A coalition [S] = k cannot recover a message i as there exists a one-way function f,- which is one-to-one for some i on S. Each user in the coalition belongs to a different l-resilient scheme and cannot obtain any message sent with that scheme. Moreover, the center sends the messages using keys from the schemes to which these users do not belong. Even if one user from the coalition were to receive a message m,, he cannot decrypt it since it requires two users to break the scheme with which m, is encrypted. The coalition users may obtain all miak’s but cannot get m,- and hence cannot get M. Hence, this scheme is k-resilient. Transmission and storage costs. The storage at each user is 0(k log k log n) and the transmission length is 0(k2 log2 k log n). However, compared to many other latter schemes, this scheme requires an impractical number of keys to be stored at the users. Combinatorial Bounds in Broadcast Encryption. In [42], Luby and Staddon described tradeoffs between the number of keys held by the users and the transmission length required. In [38], Fiat and Naor describe similar tradeoffs while considering a fixed size set of colluding users. In [42], the authors describe construc- tions and tradeoffs for a fixed size set of target receivers. The authors use several the- orems from extremal set theory to establish the storage and communication bounds. 121 We only state the bounds here and refer the interested reader to the original paper for more details. Let t denote the maximum transmission length for a universe of n users with the size of the privileged set equal to n -— m. OR-framework. The authors describe an OR-framework, in which, each user belonging to the privileged set needs to know atleast one key from this framework. The center encrypts the message with all the keys from the framework and only users belonging to the privileged set can decrypt the message. The average number of keys n 1/: in the OR-framework is L377. AND-framework. In the AND-framework, each user needs to have all the keys with which the message is encrypted in order to recover the message. The center encrypts the key with a combination of all the necessary keys. The number of keys n-l stored by the users is (m/t). Again, as in [38], the number of keys held by each user is quite high in these schemes. Key Management for Restricted Multicast Using Broadcast Encryp- tion. The schemes described in [38] and [42] are strictly secure, in that, no user outside the target set is allowed to receive the broadcast message. In [43], the authors relax this requirement and allow some additional users to receive the broadcasted mes— sage. They show that, relaxing the strict security requirement lowers the number of transmitted messages and the number of keys that the users need to store. The work of [43] is based on the results of [42]. Again, due to the mathematical complexity involved in the constructions, we only state the key results without loss of continuity. We refer the interested reader to [43] for more details on the constructions of the key management schemes. Transmissions and storage cost. Let tmax(S) denotes the maximum number of transmissions and f denotes the number of free users allowed per transmission. If the number of keys per user is O(log n) then, tmax(S) 2 (MW). If the number of keys per user is 0(n‘) then, tmax(S) Z Sufi). 122 Revocation and Tracing Schemes for Stateless Receivers. In [17], the authors describe a subset-cover framework. In subset-cover framework, the privileged users are considered as a union of several disjoint subsets. Each subset is associated with a key known only to the users in that subset. The framework is similar to that of the OR-framework described in [42]. In [17], the authors describe key management constructions which achieve a new bound on transmissions required to revoke r users from a universe of N users. In one scheme, each user needs to store log N keys and the transmission length is r log N keys. In a second scheme each user need to store 0(log2N) keys and the transmission length is 0(r). The second bound on the transmission is a major improvement in broadcast encryption. This scheme has been adopted for practical implementation in many existing broadcast encryption algorithms. Key management schemes. In the subset-cover framework the center first finds all the disjoint subsets which cover all the users. Each subset is associated with a key which can derived by only those users in that subset. First subset-cover algorithm. The users are arranged as the leaves of a binary key tree, similar to the scheme described in [2]. Each user receives all the keys from itself to the root node. The storage at each user in this scheme is logN + 1. The The center first constructs a steiner tree which consists of all the revoked users. The cover is determined by finding all the subtrees that are not part of the steiner tree. The minimum number of subtrees can be determined by selecting the roots of nodes that are adjacent to the steiner tree nodes which have an outdegree of 1. The authors show that there are rlog N / r such nodes in the key tree. Second subset-cover algorithm. The users are considered as being arranged as the leaves in a binary tree. The subset difference is 31;,- = S,- -— Sj consists of all the users that are in rooted at S,- but not at 53-. Each such subset is assigned a key Lu. Given this description of subsets, the cover is determined by first marking out 123 a directed steiner tree ST(R) which consists of all the revoked nodes as the leaves. To find the first subsets, the center selects two leaf nodes v,- and vj from ST(R) such that, the least common ancestor of v, and v,- does not contain any other leaf from ST(R). If v, and vk are descendants of v,- and vj respectively, then, the subsets Sz,,-( v1 7E vi) and Sk,j( vk 71$ Uj) are two subsets for the final subset cover. To find the next subsets, the descendants of v are removed from ST(R) and v is made a leaf in ST(R). The process is repeated on this new ST(R). The number of resulting subsets from this method is 2r -— 1 as the number of subsets after each iteration are increased by 2 and there is only one subset possible near the root. To assign keys to the subsets the center considers all possible subsets that a user is part of in the key tree. For every ancestor in the key tree up to the root, each user is part of log N subtrees. The center assigns each of these subtrees an independent key. Consider the subtree rooted at a node v,- with a label LABELi. Given the parent’s label the labels of the left and right child nodes are GL(LABEL,-) and GR(LABEL,-) respectively, which are the left and right outputs of a pseudo-random generator G on LABEL,. There is a third output from C termed CM which is used as the key assigned to LABEL,. Thus, in this construction, given the label of a root node all the labels of the children can be computed. Given such a labeling, the subset Sm- is assigned the label GM(L,-,j). For each complete subtree T,- of which a user u is a part of, the user receives all the labels of all the siblings of its ancestors. Given this information a user it can compute all the keys for subsets in which u appears. Each user has perform atmost log N computations on using C to recover the subset key. The number of keys stored by each user is (log N (log N + 1)) / 2. The experimental results on subset cover framework show that the number of subsets required is 1.25r and the average number of subsets is 1.38r. LSD-Layered Subset Difference Revocation Scheme. The LSD scheme is an improvement over the subset difference revocation scheme. In [18], the authors 124 1+C) keys, where, e 2 0. To achieve show that the user only needs to store 0(log this bound, in their framework, the authors further split each subset generated by the subset difference revocation into two more subsets. Since the original subset was a cover for the subset-cover scheme, these new subsets are also part of the cover. The difference is that the users only need to store the keys for these new subsets of which they are part of. This requirement reduces the number of keys that the users store, depending on the number of subsets that are generated by the center. The communication cost, however, is slightly higher than the subset difference scheme and is around 4r — 2. Experimental values show that this value is around 2r. The authors also describe lower communication bounds, but the storage at the users increases considerably. Storage-Efficient Stateless Group Key Revocation. The subset difference revocation scheme implements an efficient hashed key-chain, i.e., given an intermedi- ate value in this chain, any user can determine the resulting key. In [40], Wang, Ning and Reeves describe another stateless group revocation scheme which is similar to the subset difference revocation scheme but requires the users to store only 2 log N keys. Dual-directional key chain( DDK C). In [40], the authors propose the use of key chains. A key chains has the property that any consecutive key in the chain can be derived by knowing any of its predecessor keys. Each key, K .—+1 = H (Ki) where, H is a one-way hash function. In [40], for a set of 1, 2, . . . , M users the authors use two key chains. The first chain, the forward key chain( FK C), starts with user 1 at the head. Each user receives the key associated with its location. Thus, user 1 has key F and user M has key HM‘1(F). The second key chain, the backward key chain( BK C), starts in the opposite direction, i.e., with user M as the head of the key chain. Thus, user M has key B and user 1 has key H M ”(3). The storage at each user is 2 keys. To revoke a user u, from this set up, the group controller encrypts the new session with two keys, one from the FK C and the other from BK C. In the F K C, the group 125 controller chooses H“1(F) to encrypt the session key and in the BK C, the group controller uses HIV-(“1)(B) to encrypt the session key. Users in the F K C which occur before u,- can decrypt the session key by computing H"-1 and similarly, the users in BK C occurring before u,-( in the backward direction) can decrypt the session by computing H N ‘(i‘1)(B). Each user has to perform atmost M — 1 computations to recover the session key. K ey Chain Tree Revocation scheme. The storage at the users can be reduced by using the DDKCs in a hierarchical fashion. The users are arranged as the leaves of balanced binary tree. A subgroup C,- is considered as the subgroup consisting of a collection of all the users rooted at i. Every C,- is associated with a DDK C. Thus, each user is associated with log N DDKCs from itself to the root and stores 210g N keys. A set of R revoked users divides the users into atmost R + 1 contiguous blocks. To find the cover for the un-revoked users, the center selects the intermediate nodes which consist of only one revoked node. Since there are R revoked users the number of resulting sets is R. For each set rooted at i containing a revoked node r, the group controller sends 2 messages using the FK C and BK C keys associated with i to revoke r. Thus, the communication cost is atmost 2R. The users have perform atmost N — 1 one-way computations to recover the session key. The authors describe further improvement on this scheme, called the layered key chain tree, to reduce the computational cost at the users by to x/N. However, the communication cost using this improvement is increased to 4r. Efficient ’Ii'ee-based Revocation in Groups of Low-state Devices. In [39], the authors describe a scheme similar to the DDK C scheme described in [40]. The key management and communication costs are similar to the those in [40]. Fur- ther, in [39], the authors describe an improvement, called the stratified subset dif- ference scheme( SSD), to reduce the computational cost at the users. The technique is to partition the binary tree into I: levels, starting from the root, and to associate 126 additional labels with each complete subtree rooted at the nodes occurring at the boundary of the partitions. The users store the keys associated with the partitions as well. The storage at the users increases by a factor of k, but the computation is reduced to atmost nl/k. The communication cost is also increased by a factor of k. Note on SDR and Related Schemes. We note that, SDR and other schemes that have been proposed based on the one-way hash chain technique are one-time revocation schemes. For example, if users r1 are revoked at a particular time instant t1 and the center needs to revoke users r2 at another time instant t2 > t1, then, the center needs to send messages that revoke r1 and r2. This is one of the main differences between multicast key management schemes and broadcast encryption schemes. The stateful nature of multicast schemes preserves performance over many revocations, whereas, the stateless nature of broadcast encryption scheme, by large, results in better performance for one-time revocation only. Improvements to extend broadcast encryption schemes to preserve performance is an open problem. 7 .1.3 Distributed Key Management Algorithms Key management algorithms which rely on a single entity to handle membership changes and key management tasks are prone to a single-point failure. To eliminate the dependency on a centralized entity, the functionality of the group controller can be distributed among several entities. There are several schemes which perform such distribution of key management tasks. We discuss some important frameworks and algorithms in this section. Iolus: A Framework for Scalable Secure Multicasting. The Iolus frame- work [37] was the first scheme to approach the problem of scalability in key man- agement for large groups. In the Iolus framework, the group is divided into smaller groups, called subgroups, each of which is managed by a group security agent( GSA). Each of these GSAs then connect with each other in a tree like fashion, with the 127 group security controller( GSC) at the top of the hierarchy. The hierarchy of groups form one single large multicast group. An example Iolus based hierarchy is shown in Figure 7.7. _m .o o .-’ \ 0 Figure 7.7: Iolus framework. GSC is group security controller. GSA’s are group security agents. G1, G2, G3, G4 are the subgroups. Key management tasks. The GSAs manage the key management tasks within their subgroups. Users belonging to the same subgroup share a common key, called the subgroup key. When a user joins the group, the GSA generates a new subgroup key and sends it to the new user. To send the new subgroup key to the current users and to any parent subgroups, the GSA encrypts it with the current subgroup key and multicasts it. If a user leaves the subgroup, the current subgroup key is changed to prevent that user from accessing future communication. The GSA generates a new subgroup key and encrypts it with the individual private keys of the remaining users and sends these messages to them. The new subgroup key is also sent to any parent group of this subgroup. By localizing the task of adding and removing users, the Iolus framework manages to scale the key management tasks for large groups. Also, failure of a few GSAs is handled efficiently by electing new GSAs from the remaining members of the subgroup. 128 Data encryption. Data transmission in the Iolus framework can be done in two ways. In the first method, the sender encrypts the data with its local subgroup key and multicast it to the subgroup. The subgroup controller listening to the multicast can then decrypt it and re—encrypt to send it to any other child subgroups it has. In the second method, the sender encrypts the data with is private key and unicasts it to the subgroup controller. The subgroup controller decrypts this packet and encrypts it with the subgroup key and multicasts it to its subgroup and to its parent subgroup, if any. Thus the Iolus framework provides a platform for building scalable and secure protocols for large dynamic groups. A Scalable Extension of Group Key Management Protocol. The use of a hierarchy of group controllers is also suggested in [44]. To solve the problem of failure of a centralized group controller, [44] uses a panel of three group controllers. One group controller is the active member, which performs the validation of joining users and other access control list management tasks. When a new group key needs to be generated, atleast two group controllers agree upon the new group key. The active controller distributes the new group key to the group, encrypted with each member’s private key. The constraint on the group key generation is that no pair of group controllers can participate in consecutive group key updates. If any group controller on the panel is compromised the other two controllers can inform a security manager who is in charge of the session and request for a new group controller on the panel. Scalability. To make the key management scalable, the multicast group is clustered into smaller groups which are arranged in a hierarchy. Each subgroup has its own panel of three subgroup controllers. A main panel is at the head of the hierarchy and is in charge of the group key generation. The subgroup controllers are in charge of managing membership of their subgroups, data routing and distributing the group key generated by the main panel. However, the subgroup controllers themselves cannot 129 generate the group key. Any compromise in the subgroup controllers is handled by the security manager. This scheme is similar to the Iolus framework with the main difference being the introduction of redundant sub-group controllers Scalable Secure One-to-Many Group Communication Using Dual En- cryption. In the hierarchical subgrouping schemes in [37,44], the subgroup con- trollers are also members of the multicast group, i.e. they have access to the data. But in some scenarios it may be desirable to have some non-members, or participant network nodes, as subgroup controllers. One such scenario is when the multicast is being done on a fixed network infrastructure with a dynamic set of recipients. The support nodes remain the same but, the users keep changing for different services or programs. To address such scenarios, a dual-encryption scheme is described in [45]. The scheme works in a similar fashion to the Iolus framework. The difference being that the subgroup controller may or may not be a member of the multicast. An example hierarchy is shown in Figure 7.8. , / Root key Participant——+ /\M Member 11 10 O \‘1 I I. Key Group 1 K; Group 2 Figure 7.8: Dual encryption scheme with hierarchical subgrouping. Participant,P, is not part of key group. While member M, is part of its key group. Key management. Each of the subgroups have a subgroup key, which is generated and distributed by the subgroup controller. Also, each member of a subgroup belongs 130 to a key group. So, there are as many key groups as the number of subgroups. A unique key is associated with each keygroup. The members of the group have the data encryption key, subgroup key of their subgroup, and the key of their keygroup. The subgroup controller belongs to the key group of the subgroup it controls, if it is a member of the multicast and hence receives the unique key. If the subgroup controller is only intended for subgroup management, i.e., it does not have access to data, then it does not belong to any key group and does not receive the key of key group. Membership tasks. If any user leaves the group, the subgroup controller changes the subgroup key and sends it to each user in a secure unicast channel. If any user joins a subgroup, it is assigned to a subgroup controller and a keygroup. The new user receives the data encryption key and the key of its key group from the top level group manager. The subgroup controller changes the current subgroup key and sends it to the joining member. The other members of the group receive the new subgroup key, encrypted with the old subgroup key. Thus, the subgroup controller does not possess the key of the key group to which its own subgroup belongs. Data encryption. If a data packet needs to be transmitted, the top level group controller generates multiple data packets, one each for the members in the top level subgroup. Each data packet is first encrypted with the data encryption key. To trans- mit the data to a subgroup, the group controller uses the subgroup key of that partic- ular subgroup and the key of that keygroup, to encrypt the data packet. The group controller sends the data packet to the subgroup controller who in turn transmits the packet to the members of its subgroup. Since non-member subgroup controllers do not have the key of the key group they cannot access the data. This kind of dual encryption ensures that the data is safe from non-member subgroup controllers. Scalable Secure Group Communication over IP Multicast. Overlay multicast [20—22,46], is an important research area. In overlay multicast, the group users form an overlay network and implement multicast functionality without the help 131 of the underlying network. The group users run a multicast routing protocol among themselves using the metrics of the overlay links and establish the multicast data paths. The data is communicated via unicast. In overlay multicast, the problem of key management can addressed by integrating it with the multicast protocol. In [47], the authors describe a key management algorithm which is based on the overlay composition of the group. Overlay structure. In [47], the users are arranged in layers. Each layer is composed of several clusters. Each cluster also has a cluster leader. The cluster leaders at a lower level combine to form the cluster leaders at a higher layer. The clusters are of fixed size, between k and 2k — 1, for a fixed constant k. Key management. The users at each layer share a layer key. Also, the users of all the clusters share a cluster key. Since all the users belong to the lowest layer, the lowest layer key is used as the group key. The cluster leader establishes a pair-wise shared key with members of the cluster. User revocation. When a user is revoked from the group, say from the lowest layer, the cluster leader generates a new cluster key and distributes it to the remaining users of the cluster. A key server generates a new group key and sends it to the highest layer users by encrypting it with that layer key. The cluster leaders at this layer send the new key to their clusters using their cluster keys. Cluster leader revocation. To revoke a cluster leader, the users of the cluster elect a new cluster leader. The new cluster leader generates a new cluster key and sends it to the users in the cluster. The new cluster leader also joins its next higher layer. The next higher layer requires a new layer key. The cluster leader at the higher layer requests the key server for a layer key. After receiving the layer key, the cluster leader unicasts the new layer key to members of its cluster. Also, the key server sends the new group key encrypted with the new layer key( at the higher level). The new group key is sent to the members of the lowest layer by their cluster leaders. 132 User join. When a user joins the group, the cluster leader generates a new cluster key and sends it to the new user. To send the cluster key to the remaining users the cluster leader encrypts it with the old cluster key. The key server sends the new group key to the highest layer and it is propagated by the cluster leaders to the lower layers. Rekeying and storage cost. The storage at a user depends on the size of the cluster and the number of layers to which it belongs. The maximum storage at a user is (k + 1)logkN. The rekeying cost per member is S 2. Note on Distributed Key Management Schemes. Distributed key man- agement schemes depend on the users or several trusted entities for correct operation. In the current Internet scenario, the deployment of these schemes poses a number of challenges. Also, the efficiency of these schemes is a major concern. They are mostly suitable for interactive video gaming or small scale multicast applications where the performance degradation is not noticeable. However, these schemes offer the ro- bustness and fault-tolerance that centralized schemes may not offer while sacrificing efficiency. An open problem in this area is to develop distributed key management algorithms which do not sacrifice efficiency. 7 .2 Key Distribution Algorithms Key distribution is an important problem in secure group communication. In group key management algorithms, the users need to receive all the key updates in order to be able to resume secure group communication. In algorithms like [2,3], the users need to receive several intermediate key updates before they are able decrypt the current group key. The group controller needs to ensure that the users receive all these key updates in a reliable manner. Group key management algorithms have characteristic features which are important in determining the use of the appropriate 133 protocol for achieving reliability. Many algorithms have been proposed [48—52], to achieve reliability in group key management algorithms. In this section, we describe some important algorithms that address the problem of key distribution in group key management algorithms. ELK : A New Protocol for Efficient Large-group Key Distribution. An efficient technique to recover from lost key updates is described by Perrig, Song and Tygar in [53]. The protocol, called ELK, reduces the size of the key update messages while increasing the computation required at the users. Key management. The key management algorithm used is the LKH [2, 3], algorithm using a binary key tree. The key tree construction is similar to that of the one-way function tree( OFT) [6], in that, a parent key is generated by contributions from the left child and the right child keys. However, unlike OFT, each user knows only the keys from itself to the root node. Key updates. Consider a key K, that needs to be updated from a contribution of n1 bits from the left child key and a contribution of n2 bits from the right child. If the users below the right child need to update the key, they need to know the n1 bits from the left child key. When membership changes, the group controller transmits the necessary key updates. Key recovery. To recover from a lost key update, the group controller adds a small message called hint for every key being updated. The hint is derived using a pseudo-random function over the updated key and is attached to the data packets. The size of the hint is much smaller than the key update. To recover a key update, the users on the right launch a brute force to compute the contribution of n1 bits from the left child key. This requires them to generate atmost 2‘"l combinations. Using each combination, along with the n2 bits they know, the right child users generate all possible values of the new key update. To verify whether they have generated the right key, they use the hints sent by the group controller. This way the users are able 134 to recover from losses without having to request additional communication from the group controller. Other contributions. The authors also describe other efficient techniques, like a zero—broadcast join of a user and aggregation of broadcast messages for multiple leaves. The only drawback of ELK is the amount of computation that is performed at the users. Protocol Design for Scalable and Reliable Group Rekeying. To achieve reliable key distribution, in [54], the authors describe techniques which combine re- dundancy, multicast and unicast retransmissions. The redundancy is achieved by a pro-active FEC algorithm using Reed-Solomon Erasure codes. These techniques are shown to yield good performance while introducing slightly higher bandwidth in the network. Multicast phase. Multicasting of the rekey messages with the redundant packets is done in the first few rounds. The coding of packets is done in a way such that each user needs only one packet block to receive all the necessary keys. Most users are able recover the necessary information during this phase. Moreover, the multicasting is done by interleaving packets of uncorrelated information, so that in a burst loss all information pertaining to a certain message is not lost. Unicast phase. After one to two rounds of multicast the server switches to unicast mode to deliver rekey messages to users still needing them. This is done when the server’s bandwidth overhead is smaller for unicasting as compared to multicasting to this set of users. A Comparative Performance Analysis for Reliable Group Rekey Trans- port Protocols for Secure Multicast. In the LKH algorithm, keys which are closer to the root node are shared by a larger number of users. In [55], the authors use this property to implement a redundancy based reliable multicast protocol for key distribution. The redundancy factor is determined by the relative importance of the 135 keys being transmitted. Also, the authors describe a batch-oriented retransmission phase for lost rekey messages based on the number of NACKS received. Weight keys and transmission phase. In the first phase, the redundancy factor for higher level keys is set to a larger value than the keys at a lower level. Thus, the replication of the higher level keys is more than the replication of the lower level keys. Once the replication is done, the group controller multicasts these rekey messages. Batched key retransmission phase. The batched key retransmission phase relies on the observation that each user is interested in atmost one key per level of the key tree. The rekey messages are packets that contain more than one key and include keys that are already received by the user. Instead of retransmitting rekey messages based on the NACKs for every user, the group controller waits for all the NACKS from the users and aggregates this information. Based on the aggregated information the group controller creates new packets containing those keys that are required by the users. Thus, batched key retransmission reduces bandwidth usage while achieving the reliability. Note on Key Distribution Algorithms. The reliable key distribution al- gorithms exploit the specific structure of the key tree and control the redundancy parameters in the reliable multicast protocols. These algorithms have been proposed for IP multicast scenario where it is difficult to change the underlying network in- frastructure to support such explicit functionality. However, in overlay multicast applications, the end users are responsible to perform such tasks as key recovery and retransmission. In these scenarios, it is possible to develop more robust and efficient reliable multicast protocols. In overlay multicast, these approaches are not suitable as they incur additional routing and processing overhead at the users. Thus, for overlay multicast, the problem of key distribution requires solutions that do not incur unreasonable routing and computational overhead. 136 Chapter 8 Summary In this dissertation, we proposed key management and key distribution algorithms for secure group communication. Specifically, we addressed the challenges of scalability, heterogeneity, and adaptivity in secure group communication. In this chapter, we summarize our contributions and present some future directions. We proceed as follows, in Section 8.1, we discuss our contributions. In Section 8.2, we discuss future directions of our work. 8.1 Our Contributions Our contributions in this dissertation are two fold. First, we described revocation algorithms for secure groups. Second, we described key distribution techniques for these algorithms. We note that, these algorithms achieve scalable and adaptive secure group communication. Revocation Algorithms. We identified some challenges that are not addressed by existing group key management algorithms. These challenges include, but are not limited to, scalability, variable storage capabilities of the users, variable computa- tional capabilities of the users and heterogeneous network media. To address these challenges, we presented two families of user revocation algorithms in Chapters 3-4. 137 Also, in Chapter 6, we extended our revocation algorithms to address the issue of user revocation in adhoc networks. Our algorithms identified the tradeoffs between the pa- rameters which characterize the requirements of the application and the requirements of the users. We identified two costs involved in the process of revocation: critical cost ——the cost of distributing the new group key and non-critical cost —the cost of distributing the new shared keys. The family of algorithms we described in Chapter 3 identified the tradeoff between the critical cost and non-critical cost. Our algorithms are based on different arrangement of complementary keys [2] and logical keys [3]. Specifically, we showed that it is possible to reduce the duration of interruption to the group communication while keeping the total cost of rekeying manageable. Depending on the requirements of the group controller and the users, the group controller can use the appropriate key management algorithm to achieve the required critical and non- critical cost. Moreover, we showed that our algorithms can be modified at run-time to adjust to the variable requirements of the users and the group controller. The family of algorithms we described in Chapter 4 identified the tradeoff be tween the number of keys stored at the users and the rekeying cost. A key feature of these algorithms is their ability to revoke multiple users from the group while being resistant to collusion among these users. We showed that the logical key hierarchy from [2,3] and a specific instance of the algorithms from Chapter 3 are members of this family of algorithms. We showed that by varying the degree of the hierarchy in these algorithms it is possible to accommodate users having low storage and provide a low rekeying cost for users having high storage. Finally, we showed that our algo- rithms can be combined with the logical key hierarchy [3] to reduce the computational overhead of the users. Such a combination is effective in accommodating users with low computational capability in a heterogeneous group. In Chapter 6, we described an algorithm for revocation of users from secure adhoc 138 networks. In our algorithm, we combined the group key management algorithms [3,5, 7,9,16,23] with the secret instantiation protocols [10—12,29]. We focused on the critical aspect of group key distribution to revoke the users. Specifically, the revocation is complete once the group key is securely distributed to the un—revoked users. We considered different network settings and showed that our algorithm achieves complete group key distribution in these settings. Key Distribution Algorithms. In Chapter 5, we described algorithms to dis- tribute keys to only those users who need them. Our approach is based on an efficient descendant tracking technique used by the intermediate nodes in the multicast tree. Based on the descendant tracking information, the intermediate nodes selectively for- ward the key updates to only those descendants who need them. We showed that our descendant tracking technique requires a small amount of storage and computation from the intermediate nodes. Using extensive simulation results, we showed that our algorithms reduce the bandwidth usage in our revocation algorithms from Chapter 3 as well as for existing revocation algorithms in [3]. Furthermore, in Section 5.4, we described the application of our algorithms to the general scenario of secure interval multicast [13]. In secure interval multicast, the group controller securely transmits data to a selected subset of users. We showed that, our key distribution algorithms reduce the bandwidth usage in the secure interval multicast as well. 8.2 Future Work Next, we describe some future directions of our research. Specifically, we are extending our work to address problems in two important network applications: adhoc network multicast and overlay multicast applications. Adhoc Networks. Security in adhoc networks is an important issue. Adhoc networks have limitations when compared to wired networks. Some of the limita- 139 tions of adhoc networks may include, but not limited to, small storage, low battery power, limited computational power, lossy and noisy links. For example, a sensor network is an adhoc network composed of low power sensors operating in a lossy environment. Typical attacks on sensor networks include, capture of nodes, denial of service and data corruption. We intend to extend our preliminary algorithms( cf. Section 6) to address these issues. In particular, we are focusing on the problems of key management and collusion in secure adhoc networks Key Management. To deve10p and implement key management algorithms to suit a multitude of limitations is challenging. Fhrthermore, the environment of the adhoc networks keeps changing due to the mobility of the adhoc nodes. This im- plies that there is a need for adaptive key management algorithms which address these changes. We are currently exploring the application of our key management algorithms to implement security in adhoc networks. We have identified two diffi- culties in applying our algorithms to implement security in adhoc networks. First, the availability of a group controller at all times is not possible in adhoc networks. Our algorithms need to be modified to consider this issue. Second, the limited stor- age at the adhoc nodes places a bound on the number of keys that may be given to them. This is a major difficulty as this factor determines the type of key management algorithm that can be used for revocation. We are currently focusing on extending our algorithms to implement security in adhoc networks while taking into consider— ation these challenges. Our goals are to achieve adaptable, distributed and stateless security in adhoc networks. Collusion. To achieve user-to-user security in adhoc networks, the users share keys selected from a single key pool. This issue is the focus of secret instantiation protocols [10—12,29]. Thus, an adhoc network is a group of users with specialized requirements of security, i.e., node-to-node confidentiality, within the group. Further- more, the security achieved by these protocols is probabilistic, i.e., the communication 140 among users is secure only up to a degree of collusion by the users. Hence, it is im- portant to address the issue of collusion when revoking users from adhoc networks. We have shown that, in the presence of a centralized group controller, collusion can be handled efficiently using our algorithms from Section 4. However, in adhoc networks, collusion is difficult to handle due to the non-availability of a centralized controller all the time. Due to this limitation, it is necessary to determine the bounds of the probabilistic security guarantees provided by shared key algorithms. These guarantees enable the deployment of a particular secret instantiation protocol when some knowledge of the system users and the environment is available. To determine these bounds, there is a need for a formal model which quantifies the bounds of the secret instantiation protocols. Towards this, we are developing a formal model to determine the collusion resistance offered by various secret instantiation protocols. This model will be useful for system designers who need certain deterministic guaran- tees from the secret instantiation protocols. Furthermore, this model will enable the group controller to determine the appropriate group key management algorithm that is required to revoke users who are using a particular secret instantiation protocol. Overlay Multicast. Overlay multicast [20—22,46] is an alternative to IP multicast for achieving group communication. The support for multicast is essentially provided by the end nodes themselves and no network support for multicast is assumed. Over- lay multicast is not as efficient as IP multicast due to unavoidable redundancy of links in the overlay multicast tree. When the multicast tree is built, some network paths occur more than once in the multicast tree causing redundancy. Also, the computational overhead at the users is high as the users need to perform additional computational tasks like, data forwarding, end-node routing table updates and mem- bership handling. Thus, there are two important issues to be addressed in overlay multicast (1) reducing the redundancy of links and, (2) reducing the computational overhead at the end nodes. We note that, the first problem is more closely related to 141 the construction of the overlay network structure and is a problem that is better left to the network protocols community. The second problem, is important in the context of secure group communication and thus, there is a need to address this problem. One way to improve efficiency of overlay multicast is by reducing the workload of the users. This is especially important in secure group communication as the nodes have to perform the additional tasks of encryption and decryption of data. Thus, there is need for adaptive key management algorithms to improve the efficiency in overlay multicast. In this dissertation, we have shown that our key management algorithms can adapt to the requirements of the operating environment and the users. Along the same line, we are extending our key management algorithms to suit the specific needs of overlay multicast applications. Specifically, we are exploring the development of key management algorithms that can adapt to the varying network topologies in overlay multicast. Furthermore, we are also considering the issues like node-to—node authentication and digital signatures which are important in overlay networks. 142 BIBLIOGRAPHY 143 Bibliography [1] H.Harney and C.Muckenhirn. Group key management protocol (GKMP) speci- fication. RFC 2093, July 1997. [2] Debby M. Wallner, Eric J. Harder, and Ryan C. Agee. Key management for multicast: Issues and architectures. RFC 2627. [3] Chung Kei Wong, Mohamed Gouda, and Simon S. Lam. Secure group commu- nications using key graphs. IEEE/A CM Transactions on Networking, 2000. [4] Marcel Waldvogel, Germano Caronni, Dan Sun, Nathalie Weiler, and Bernhard Plattner. The versakey framework: Versatile group key management. IEEE Journal on Selected Areas in Communications, 1999. [5] Isabella Chang, Robert Engel, Dilip Kandlur, Dimitrios Pendarakis, and Deban- jan Saha. Key management for secure internet multicast using boolean function minimization techniques. In Proceedings IEEE Infocomm ’99, volume 2, pages 689—698, March 1999. [6] Alan T. Sherman and David A. McGrew. Key establishment in large dynamic groups using one-way function trees. IEEE Thans. Software Eng, 29(5):444—458, 2003. [7] Hartono Kurnio, Safavi-Naini Rei, and Huaxiong Wang. Efficient revocation schemes for secure multicast. In International Conference on Information Se- curity and Cryptology 2001, Lecture Notes in Computer Science, volume 2288, pages 160—177, December 2002. [8] Xiaozhou Steve Li, Yang Richard Yang, Mohamed G. Gouda, and Simon S. Lam. Batch rekeying for secure group communications. In WWW, pages 525—534, 2001. [9] Hartono Kurnio, Reihaneh Safavi-Naini, and Huaxiong Wang. A secure re-keying scheme with key recovery property. In ACISP, pages 40—55, 2002. [10] Laurent Eschenauer and Virgil D. Gligor. A key-management scheme for dis— tributed sensor networks. In ACM Conference on Computer and Communica- tions Security, pages 41—47. ACM, 2002. 144 [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] Li Gong and David J. Wheeler. A matrix key-distribution scheme. Journal of Cryptology, 2(1):51-59, 1990. Sandeep S. Kulkarni, Mohamed G. Gouda, and Anish Arora. Security instantia- tion in ad-hoc networks. Special Issue of Elsevier Journal of Computer Commu- nications on Dependable Wireless Sensor Networks, 2005. A Preliminary Version Appears in WorkshOp on Dependability Issues in Wirel ess Ad Hoc Networks and Sensor Networks (DIWANS), June 2004, Florence, Italy. Mohamed G. Gouda, Chin-Tser Huang, and E.N.Elnozahy. Key trees and the security of interval multicast. In 22nd International Conference on Distributed Systems, pages 467—468, 2002. R.Canetti, J.Garay, G.Itkis, D.Micciancio, M.Naor, and B.Pinkas. Multicast security: A taxonomy and efficient authentication. In Proc. of INF OCOMM ’99, March 1999. P. K. McKinley and A. P. Mani. A study of proxy—based adaptive forward error correction for c ollaborative computing on wireless lans. IEEE Symposium on Applications and the Internet (SAINT), San D iego, California, January 2001. Sandeep S. Kulkarni and Bezawada Bruhadeshwar. Adaptive rekeying for se— cure multicast. IEEE/IEICE Special issue on Communications: Transactions on Communications, E86—B(10):2948—2956, October 2003. Dalit Naor, Moni Naor, and Jeffery Lotspiech. Revocation and tracing schemes for stateless receivers. Electronic Colloquium on Computational Complexity (E000), (043), 2002. Dani Halevy and Adi Shamir. The lsd broadcast encryption scheme. In Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Confer- ence, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science. Springer, 2002. X. Steve Li, Yang Richard Yang, Mohamed Gouda, and Simon S. Lam. Batch updates of key trees. In Proceedings of the Tenth International World Wide Web Conference (WWWIO), Hong Kong, China, May 2001. Y.-H.Chu, S.G.Rao, S.Seshan, and H.Zhang. A case for end system multicast. IEEE Journal on Selected Areas in Communications, 20(8):1456—1471, October 2002. [21] B.Zhang, S.Jamin, and L.Zhang. Host multicast: A framework for delivering multicast to end users. In IEEE INF OCOM, March 2000. [22] J .Liebeherr, M.Nahas, and W.Si. Application-layer multicasting with delaunay triangulation overlays. IEEE Journal on Selected Areas in Communications, 20(8):1472-—1488, October 2002. 145 [23] Sandeep S. Kulkarni and Bezawada Bruhadeshwar. Rekeying and storage cost for multiple user revocation. In 12th Annual Network and Distributed System Security Symposium, pages 45-54, San Diego, California, February 2005. [24] Di Pietro, L. V. Mancini, Y. W. Law, S. Etalle, and P. J. M. Havinga. Lkhw: A directed diffusion-based secure multicast scheme for wireless sensor networks. In 32nd Int. Conf. on Parallel Processing Workshops (ICPP), pages 397—406, October 2003. [25] Bill Fenner and Steve Casner. A traceroute facility for ip multicast. Internet Draft, July 2000. [26] Ns. ucb/lbnl/vint network simulator - ns (version 2). http://www- mash.cs . berkeley.edu/ns. [27] A.J.Ballardie, P.F.Francis, and J .Crowcroft. Core based trees. In Proceedings of the ACM SICCOMM, October 1993. [28] Sencun Zhu, Sanjeev Setia, Shouhuai Xu, and Sushi] Jajodia. kapan: An efficient group rekeying scheme for secure multicast in ad-hoc networks. In Mo- biQuitous, pages 42—51. IEEE Computer Society, 2004. [29] Donggang Liu and Peng Ning. Establishing pairwise keys in distributed sensor networks. In Proceedings of the 10th ACM Conference on Computer and Com- munications Security, CCS 2003, Washingtion, DC, USA, October 27-30, 2003. ACM, 2003. [30] David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, 5:153—181, 1996. [31] G. Chakrabarti and S. Kulkarni. Load balancing and resource reservation in ad-hoc networks. Ad-Hoc Networks, 2004. To Appear. [32] Elizabeth M. Belding-Royer and Charles E. Perkins. Multicast operation of the ad-hoc on-demand distance vector routing protocol. In M OBI COM, pages 207— 218, 1999. [33] Adrian Perrig, Ran Canetti, J. D. Tygar, and Dawn Xiaodong Song. Efficient authentication and signing of multicast streams over lossy channels. In IEEE Symposium on Security and Privacy, pages 56—73, 2000. [34] Ran Canetti, Tal Malkin, and Kobbi Nissim. Efficient communication-storage tradeoffs for multicast encryption. In E UROCRYPT, pages 459—474, 1999. [35] Radha Poovendran and John S. Baras. An information-theoretic approach for design and analysis of rooted-tree-based multicast key management schemes. IEEE Transactions on Information Theory, 47(7):2824—2834, 2001. 146 [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] S. Setia, Samir Koushish, and Sushil J ajodia. Kronos: A scalable group re—keying approach for secure multicast. In IEEE Symposium on Security and Privacy, pages 215—228, 2000. S.Mittra. Iolus: A framework for scalable secure multicasting. In Proc. ACM SICCOMM ’97, pages 277—288, 1997. A.Fiat and M.Naor. Broadcast encryption. In Advances in Cryptology - CRYPTO’QS’, number 773 in LNCS, pages 480—491. Springer—Verlag, 1994. Michael T. Goodrich, Jonathan Z. Sun, and Roberto Tamassia. Efficient tree- based revocation in groups of low-state devices. In Advances in Cryptology - CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Bar- bara, California, USA, August, volume 3152 of Lecture Notes in Computer Sci- ence. Springer, 2004. Pan Wang, Peng N ing, and Douglas S. Reeves. Storage-efficient stateless group key revocation. In Information Security, 7th International Conference, IS C 2004, Palo Alto, CA, USA, September 27-29, 2004, Proceedings, volume 3225 of Lecture Notes in Computer Science. Springer, 2004. Nam-Su Jho, Jung Hee Cheon, Myung-Hwan Kim, and Eun Sun Yoo. Broadcast encryption 1r. Proceedings of Eurocrypt ’05, Cryptology ePrint Archive, Report 2005 / 073, 2005. http : //eprint . iacr . org/. M. Luby and J .Staddon. Combinatorial bounds for broadcast encryption. In Advances in Cryptology - EUROCRYPT’98, number 1403 in LNCS, pages 512— 526, Espoo, Finland, 1998. Springer-Verlag. Michel Abdalla, Yuval Shavitt, and Avishai Wool. Key management for restricted multicast using broadcast encryption. IEEE/A CM Transactions on Networking, 8(4), August 2000. R. Poovendran, S. Ahmed, S. Corson, and J. S. Baras. A scalable extension to group key management protocol. In Proceedings of the 2nd ATIRP Conference, College Park, MD, February 1998. Lakshminath R. Dondeti, Ashok Samal, and Sarit Mukherjee. A dual encryption protocol for scalable secure multicasting. In Proceedings of the Fourth IEEE Symposium on Computers and Communications (ISCC 1999), 6-8 July 1999, Sharm El Sheik, Red Sea, Egypt, pages 2—9, 1999. Suman Banerjee, Bobby Bhattacharjee, and Christopher Kommareddy. Scalable application layer multicast. In Proceedings of the ACM SI CCOMM 2002 Confer- ence on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 19-23, 2002, Pittsburgh, PA, USA. ACM, 2002. 147 [47] [48] [49] [50] [51] [52] [53] [54] [55] Suman Banerjee and Bobby Bhattacharjee. Scalable secure group communication over ip multicast. In 9th International Conference on Network Protocols (I CNP 2001), 11-14 November 2001, Riverside, CA, USA. IEEE Computer Society, 2001. John C.-H. Lin and Sanjoy Paul. Rmtp: A reliable multicast transport protocol. In INFOCOM, pages 1414—1424, 1996. Sally Floyd, Van Jacobson, Ching-Gung Liu, Steven McCanne, and Lixia Zhang. A reliable multicast framework for light—weight sessions and application level framing. IEEE/ACM Trans. Netw., 5(6):784—803, 1997. Donald F. Towsley, James F. Kurose, and Sridhar Pingali. A comparison of sender-initiated and receiver-initiated reliable multicast protocols. IEEE Journal on Selected Areas in Communications, 15(3):398—406, 1997. Sanjoy Paul, Krishan K. Sabnani, John C.-H. Lin, and Supratik Bhattacharyya. Reliable multicast transport protocol (rmtp). IEEE Journal on Selected Areas in Communications, 15(3):407—421, 1997. Dan Rubenstein, Sneha Kumar Kasera, Donald F. Towsley, and James F. Kurose. Improving reliable multicast using active parity encoding services (apes). In INFOCOM, pages 1248—1255, 1999. Adrian Perrig, Dawn Xiaodong Song, and J. D. Tygar. Elk, a new protocol for efficient large-group key distribution. In IEEE Symposium on Security and Privacy, pages 247—, 2001. X. Brian Zhang, Simon S. Lam, Dong-Young Lee, and Yang Richard Yang. Protocol design for scalable and reliable group rekeying. IEEE/A CM Trans. Netw., 11(6):908—922, 2003. Sanjeev Setia, Sencun Zhu, and Sushil Jajodia. A comparative performance analysis of reliable group rekey transport protocols for secure multicast. In Per- formance Evaluation, special issue on the Proceedings of Performance 2002, vol- ume 49, pages 21—41, Rome, Italy, 2002. 148 IIIIIIIIIIIIIIIIIIIIIIIjI 3