Cascaded Events. Since network disruptions are random and unpredictable, it is natural to consider the possibility of so-called cascaded membership events. (In fact, cascaded events and their impact on group and multi-round protocols are often considered in group communication literature, but, alas, not often enough in the security literature.) A cascaded event occurs, in a simplest form, when one membership change occurs while another is being handled. Here event means any of: join, leave, partition, merge or any combination thereof. For example, a partition can occur while a prior partition is being dealt with, resulting in a cascade of size two. In principle, cascaded events of arbitrary size can occur if the underlying network is highly volatile. We claim that the TGDH partition protocol is self-stabilizing, i.e., robust against cascaded network events. This property is notable and rare as most multi-round cryptographic protocols are not geared towards handling of such events. In general, self-stabilization is a very desirable feature since lack thereof requires extensive and complicated protocol “coating” to either: 1) shield the protocol from cascaded events, or 2) xxxxxx it sufficiently to make the protocol robust with respect to cascaded events (essentially, by making it re-entrant). The high-level pseudocode for the self-stabilizing protocol is shown in Figure 11. The changes from Figure 10 are minimal (lines 18 – 19 are added). Instead of providing a formal proof of self-stabilization we demonstrate it with an example. Figure 12 shows an example of a cascaded partition event. The first part of the figure depicts a partition of , , and from the prior group of ten members . This partition normally requires two rounds to complete the key agreement. As described in Section 5.4, every member constructs the same tree after completing the initial round. The middle part shows the resulting tree. In it, all non-leaf nodes except must be recomputed as follows:
1. First, and both compute , and compute while and compute . All bkeys are broadcasted by each sponsor and .
2. Then, as all broadcasts are received, and compute and . The bkeys are broadcasted by the sponsor .
3. Finally, all broadcasts are received and and compute . Suppose that, in the midst of handling the first partition, another partition (of and ) takes place. Note that, regardless of which round (1,2,3) of the first partition is in progress, the departure of and does not affect the keys (and bkeys) in the sub...
Cascaded Events. Since network disruptions are random and unpredictable, it is natu- ral to consider the possibility of so-called cascaded membership events. In fact, cascaded events and their impact on group protocols are of- ten considered in group communication literature, but, alas, frequently neglected in the security literature. Furthermore, the probability of a cascaded event is much higher on a wide area network. A cascaded event occurs when one membership change occurs while another is be- ing handled. For example, a partition can occur while a prior partition is processed, resulting in a cascade of size two. We claim that the STR partition protocol is self-stabilizing, i.e., ro- bust against cascaded network events. In general, self-stabilization is a very desirable feature since lack thereof requires extensive and compli- cated protocol ”coating” to either 1) shield the protocol from cascaded events, or 2) xxxxxx it sufficiently to make the protocol robust with respect to cascaded events (essentially, by making it re-entrant). The latter is often very complicated and inefficient as seen from [AKNR+01]. receive msg (msg type = membership event) construct new tree while there are missing blinded keys if (I can compute any missing keys and I am the sponsor) compute missing blinded keys broadcast new blinded keys endif receive msg if (msg type = broadcast) update current tree else (msg type = membership event) construct new tree endwhile Based on view synchrony discussed in Section 2, we provide an infor- mal proof that the above protocol terminates on any finite number of consecutive cascaded events. Due to view synchrony, every member has the same membership view. We can further assume that the ordering of members in the group communication system is same as that of the key tree. By Remark 1, at least a member, say Mi can compute the group key if all of the blinded session randoms are known. All members can then compute the group key using the broadcast message of the member Mi by Remark 2. Hence, it is enough to show that at least one member knows every other member’s session random, eventually. In the above pseudocode, the sponsor is the node below the lowest node whose blinded session random is missing. Now, if a sponsor Ms cannot compute the group key since some of the blinded keys are missing, it broadcasts the key tree which includes every blinded session random and blinded keys Ms knows. Then the sponsor of the next round will be the one who owns the missin...
Cascaded Events. Since network disruptions are random and unpredictable, it is natural to consider the possibility of so-called cascaded membership events. (In fact, cascaded events and their impact on group protocols are often considered in group communication literature, but, alas, not often enough in the security literature.) A cascaded event occurs, in its simplest form, when one membership change occurs while another is being handled. Event here means any of: join, leave, partition, merge or a combination thereof. For example, a partition can occur while a prior partition is being dealt with, resulting in a cascade of size two. In principle, cascaded events of arbitrary size can occur if the underlying network is highly volatile. As discussed before, STR protocol requires at most two rounds. One might wonder why robustness against cascaded failure is important for only a 2-round protocol. We give couple of examples that illustrate (potential) failure of the STR protocol. • Suppose a network partition breaks a group G into groups G1 and G2. The sponsor MG1 breaks G1 into two other groups G1 (containing MG1 ) and G2. Based on the partition protocol
1 1 description, the members in group G2 still wait for the message from MG1 to process the previous partition. • Suppose a merge event happens whereby groups G1 and G2 to form a single group G. The sponsors MG1 and MG2 in each group broadcast their tree information. In the next round, while a sponsor computes the missing bkeys, a member M1 originally in group G1 leaves the group. If the leaving member is the sponsor, the STR protocol cannot proceed for every other member is waiting for the message from this member. The protocols described above cannot cope with these situations. However, we can modify the protocol in Fig. 9 to handle such cascaded events. We claim that the STR protocol is self-stabilizing, i.e., robust against cascaded network events. This is quite rare as most multi-round cryptographic protocols are not geared towards handling of such events. In general, self-stabilization is a very desirable feature since lack thereof requires extensive and complicated protocol ”coating” to either 1) shield the protocol from cascaded events, or 2) xxxxxx it sufficiently to make the protocol robust with respect to cascaded events (essentially, by making it re-entrant). The high-level pseudocode for the self-stabilizing protocol is shown in Fig. 10. The changes from Fig. 9 are minimal (lines 15 – 18 are added).
Cascaded Events. Since network disruptions are random and unpredictable it is natural to consider the possibility of so-called cascaded membership events. (In fact, this is typically done in group communication literature, but, alas, not often enough in the security literature.) A cascaded event occurs when a join, leave, merge or partition takes place while a prior event is being handled. We claim that the TGDH partition protocol is self-stabilizing, i.e., robust against cascaded network events. This is quite rare as most multi-round cryptographic protocols are not geared towards handling of such events. In general, self-stabilization is a very desirable feature since lack thereof requires extensive and complicated protocol ”coating” to either 1) shield the protocol from cascaded events, or 2) xxxxxx it sufficiently to make the protocol robust with respect to cascaded events (essentially, by making it re-entrant). The high-level pseudocode for the self-stabilizing protocol is shown in figure 11. The changes from fig- ure 10 are minimal. Instead of providing a formal proof of self-stabilization (which we omit due to submission page limitations) we demonstrate it with an example. Figure 12 shows an example of a cascaded partition event. The first part of the figure depicts a partition of M1, M4, and M7 from the prior group of ten members [M1::M10]. This partition normally requires two rounds to complete the key agreement. As described in section 5.4, every receive msg (msg type = membership event) construct new tree while there are missing blinded keys if (I can compute any missing keys) /* sponsor? */ compute missing blinded keys broadcast new blinded keys endif receive msg if (msg type = broadcast) update current tree else (msg type = membership event) construct new tree endwhile /* as many as possible */ /* including own broadcast */ <0,0> <0,0> <1,0> <1,1> <1,0> <1,1> <2,0> <2,1> <2,2> M8 <2,3> <2,0> M2 <2,1> <2,2> M9 <2,3> M10 <3,0> <3,1> <3,2> <3,3> <3,6> <3,7> <3,2> <3,3> <0,0> <1,0> <1,1> <2,0> <2,1> <2,2> <2,3> <3,0> <3,1> <3,2> <3,3> <3,4> <3,5> <3,6> <3,7> M3 M6 M7 M8 M9 M10 M2 M3 M5 M6 M9 M10 M5 M6 M1 M2 M4 M5 member constructs the same tree after completing the initial round. The middle part shows the resulting tree. In it, all non-leaf nodes except Kh2;3i must be recomputed as follows:
1. First, M2 and M3 both compute Kh2;0i, M5 and M6 compute Kh2;1i while M8; M9 and M10 compute Kh1;1i. All blinded keys are broadcasted by each sponsor M2; M5 and M8.
2. Then, a...
