Appendix 14.A. Secure Group Communication

For the secure link-state routing protocol problem, we have recently proposed a novel key chain–based secure group key management scheme [18]. Our approach captures the merits of both centralized and distributed approaches and targets minimizing the communication and delay overhead due to key management that is critical in link-state flooding. Briefly, a set of secrets are first distributed to each user (node) from a centrally controlled key server before the secure group communication phase. During the actual communication, every group member can self-derive desired group/subgroup keys and then communicate with any possible subgroups without any help from the key server. Our work in many-to-many secure group communication [18] helps to develop secure link-state routing protocols [22] to construct future reliable and trusted routing frameworks [17].

14.A.1. Using One-Way Function Chain to Build Key Chain

In order to reduce the storage overhead, we build a key forest structure via multiple key chains. Each “tree” (a linear key chain) in the key forest structure represents a particular key derivative relation among all group members. Here, we first show how we can use a one-way function to construct a one-way function chain, and subsequently, to form a key chain. Finally, we present how to systematically distribute key elements from multiple key chains to each group member.

We start with function h(.), which is a one-way function that maps an arbitrary-length message M to a fixed-length message MD. It satisfies the following properties:

A one-way function chain (OFC) is a sequence of values with the linear derivative relations among these values. Thus, we use h^j(.) to denote the result of one-way function h(.) on a message j times. The outputs of the multiple oneway operations construct an OFC. An OFC maintains a linear derivative relation among multiple values (i.e., h^j(.) can derive h^r(.) when j < r).

Consider message M_i to be the ith initial key element that is used by a user to generate the cryptographic key denoted by k_i0, where k_i0 = f(M_i), and where f(.) is a key-generating function. This key-generating function is publicly known and generates the exact length of the cryptographic key. Thus, we have the following relation:

k_ij = f(h^j(M_i)) (j > 0)

Since h(.) is publicly known, we know that the derivative relations of an OFC are:

M_i ⇒ h¹(M_i) ⇒ ... ⇒ h^j(M_i) ⇒ ... ⇒ h^r(M_i)

(1 < j < r)

Then, using function f(.), the key chain derivative relations corresponding to the above are (see also Figure 14.9):

Equation 14.1

The derivative relations among multiple keys form a linear hierarchical structure from the top level (k_i0) to the bottom level (k_ir). In Figure 14.9, a straightforward key allocation example is shown that is composed of six keys (r = 5). If we allocate a key to each group member from u_c to u_{c + 5}, each group member can derive its lower-level keys. Then, a key chain can be formed by six subgroups, denoted by S_i0 to S_i5 (Figure 14.9). Note that these subgroups are noncolluding subgroups, that is, a subset of members cannot collude or partner to derive the keys used by a specific subgroup unless at least one of the members belongs to that subgroup.

14.A.2. Key Distribution

We extend the linear structure of a key chain to a nonlinear structure by combining multiple key chains (a key forest). These properties provide critical ingredients to our keying science due to efficiency and flexibility. We describe how to utilize graph theory to model our key distribution scheme.

Assigning more than one key from multiple key chains to a user is very similar to arranging the group members’ positions in different key chains. To give a more visualized view of our scheme, we consider every group member to be a vertex of a graph K(E,V), that is, each group member in U is mapped to a vertex in V: v_c ∈ V, u_c = v_c and c = {1, 2, ..., n}. Assume that a group has n members thus, we can associate them to n vertices in a graph, and when n is odd, we can write n = 2s+1 for some s. These n vertices can form a fully connected graph that we refer to as K_2s+1. We now state the following important graph theory result [23] that is applicable in our work.

Theorem 14.A.1 The fully-connected graph K_2s+1 is the sum of s spanning cycles, where s ∈ N. (For Proof, refer to Harary [23], p. 89.)

Theorem 14.A.1 states that any fully connected graph K_2s+1 can be constructed by s independent spanning cycles. These s spanning cycles have no overlapping edges, and each cycle has exactly n edges. Since our keying scheme is based on a sequence of one-way function values, we use the term Hamiltonian cycles instead of spanning cycles. A Hamiltonian cycle visits each vertex exactly once in sequence. There are many ways to create s independent Hamiltonian cycles. We present an algorithm that creates s Hamiltonian cycles for graph K_2s+1, where 2s+1 is a prime.

For any group of users U(|U| = n and n = 2 s + 1, s ∈ N), we can always find s Hamiltonian cycles (or spanning cycles or permutation cycles) that have no overlapping edges. For illustration, we use an overall group with seven members. This illustration is important due to its connection to the key agreement protocol described later.

14.A.2.1. An Example of Keying Protocol

Consider seven group members as seven vertices in a graph as shown in Figure 14.10. Using Algorithm 14.A.1, we can build three separate Hamiltonian cycles. Node 1 is the starting point of each of these Hamiltonian cycles. The group key distribution requires two levels of cycle tours: the node-level tour and the chain-level tour. Figure 14.11 shows the two-level tour of key distribution based on the first Hamiltonian cycle shown in Figure 14.10. For example, the key distribution tour starts from the node-level tour and the beginning node is u₁. Then the tour goes to the chain-level tour: The first key element in chain 1 (the head of the key chain c1) is distributed to u₁; the second key element in chain 2 (c2) is distributed to u₁; this process continues until the seventh key element in chain 7 (c7) is distributed to u₁. After the chain-level tour is complete, the key distribution tour goes back to the node-level tour and visits node u₂. Next, the tour goes to the chain-level tour: The first key element in chain 2 is distributed to u₂, the second key element in chain 3 is distributed to u₂, and so on, until the seventh key element in chain 1 is distributed to u₂. The key distribution tour then goes back to the node-level tour and visits node u₃. This process is continued until the tour is complete at node 7. Thus, each Hamiltonian cycle corresponds to a set of key chains. For n = 7 and s = 3, we need 3 × 7 = 21 key chains in total and each group member possesses 21 keys.

Figure 14.10. An example of Hamiltonian cycles for seven nodes (n = 7, s = 3).

[View full size image]

Figure 14.11. An example of a key distribution tour for seven group members (n = 7, s = 3).

[View full size image]

Algorithm 14.A.1. (Hamiltonian cycles creation algorithm)

Initial: Given n entities: v1, v2, ..., vn, where n = 2s + 1, s ϵ N
								Procedures: Construct a set of s paths denoted by Pt, on the points
								v1, v2, ..., v2s+1 as follows:
								1. Create s paths: Pt = v1vt+1v2t+1v3t+1 ... v2st+1, where
								t = { 1, ..., s}. All the subscripts are taken as integers
								(mod 2s+1).
								2. The Hamiltonian cycle Zt is then constructed by joining
								v1 to the endpoints of Pt.
								End

In Table 14.5, each group member has 21 keys (in a column) that belong to three different cycles (for ease of readability, we only list subscripts (i_j) of the k_ij in each row). Here, is a key chain that is constructed by following the tth Hamiltonian cycle (t = { 1,2,..., s}) to allocate keys to group members. Similarly, we can add notation^(t) to key .

Figure 14.10 shows that any two group members are connected by a direct link and they both can derive a two-member subgroup key to form a secure communication channel. For example, if we randomly select u₁ and u₄, then, for Hamiltonian cycle 3, u₁ and u₄ are adjacent, and in the third key chain, u₄ has the key k₁₁⁽³⁾ and u₁ can derive it from its k₁₀⁽³⁾. These relations can be applied to any combination of two group members. Note that these Hamiltonian cycles cannot cover every combination of selected group members. In a Hamiltonian cycle with n entities, the number of ι different group members in a continuous path is n, where ι <n. Thus, in a group with n members, using Algorithm 14.A.1 there will be s cycles formed. The number of adjacent members in s cycles is s × n. In the example, when s = 3, the number of three-member subgroups is and s × n = 21. Thus, we can infer that three Hamiltonian cycles cannot completely cover every possible combination of subgroup members. We have developed a novel way to build relations among the cycles to solve this problem—this is accomplished through the key agreement protocol described next.

14.A.3. Key Agreement Protocol

We can use a session key k′ to encrypt data and use subgroup keys as key-encrypting keys (KEKs) to encrypt the session key that is attached to the encrypted data. Multiple subgroup keys can be used as KEKs to fulfill desired subgroup composition. Using the encrypting function E(.) and decrypting function D(.), we can encrypt the data to be transmitted as follows:

Equation 14.2

(i₁ ... i_r ϵ {1, 2, ..., n – 1}; j₁ ... j_r ϵ {1, 2, ..., n – 1}; t₁ ... t_r ϵ {1, 2, ..., s})

The receivers check the key chain list {i₁, ..., i_r} to see if they belong to the group. The checking method is straightforward: A receiver compares each element in the list with j_k in the key chains that he or she possesses; he or she belongs to the group if and only if j_r ≥ j_k; and then he or she can use one-way function j_r – j_k times on the key to derive key . To decrypt the data received, the receiver first decrypts the session key:

Equation 14.3

and then uses k to decrypt the received cypher data:

Equation 14.4

We have proved the following key result (see [18] for a proof).

Theorem 14.A.2 Using the proposed key agreement protocol, s sets of key chains can be built where group size is n and s = (n – 1)/2. For those arbitrarily selected subgroup members, we can always find b (0 ≤b≤s) encryption relations that provide secure subgroup communication.

In the seven-member example, if we consider subgroup members u₂, u₆, and u₇, we cannot find any continuous path in the three Hamiltonian cycles for these three group members. We prune graph K₇ to K₃, which is shown in Figure 14.12. When u₂ wants to send messages to subgroup {u₂, u₆, u₇}, u₂ sends out the cyphertext as follows:

The encrypted session key is attached to the cyphertext. Only u₆ and u₇ can decrypt the encrypted session key and thus can decrypt the message. In the worst case, the number of encryption/decryption operations is equal to the number of Hamiltonian cycles. We have proved that based on the predistributed keys, a group member can derive all possible subgroup keys (for proof, see Huang and Medhi [18]). It is important to note that this subgroup keying scheme can completely avoid KDC being involved in the subgroup’s communication, and the secure subgroup’s communication can be freely accomplished.

It may be noted that the work described here is for a group with n members where n is odd. We can easily take care of a group with an even number of members by adding a fictitious member to increase the group size to an odd number of members.

14.A.4. Assessment

For assessment of our key agreement protocol, we use S to represent the desired subgroup that user u_i ϵ S wants to set up, where S ⊂ U and |S| = L. User u_i (the sender) is required to find r (1 ≤ r ≤ L) keys to encrypt session key k′, then, the session key is used to encrypt the message. To find the minimal number of subgroup keys to cover all possible desired group members is an NP-complete problem (can be reduced from the minimal set covering the problem). We have developed two heuristic search algorithms to find subgroup keys:

For details, refer to Huang and Medhi [18].

Using either the addition or the eviction algorithm, each group member can derive the desired subgroup keys. We have tested the addition and eviction subgroup key-searching algorithms. Through regression fitting, we have found that the function f(L) = a+bL+cL ln (L) matches our results from this test. The test results and curve-fitting function are shown in Figure 14.13(a) (results are shown for an overall group size of 251 and 503 members). In Figure 14.13(b), we compare our scheme with three typical shared key–based group keying scheme: a nave scheme, subset difference scheme [24], and one-way function tree–based scheme [25]. In terms of communication overhead in a networking environment requiring frequent subgroup formations, our key chain–based scheme performs better than these schemes.

Figure 14.13. Performance of keying protocol: (a) addition/eviction algorithm complexity, and (b) comparison of the number of key messages for many-to-many communication schemes.

[View full size image]