Anti-collusive Self-healing Key Distribution Scheme with Revocation Capability

INTRODUCTION

Currently, wireless network has more applications in military operations, rescue missions, etc., where there are usually no network infrastructure supports and the adversaries may intercept, tamper even partially interrupt the communication. It is necessary to encrypt and authenticate the messages in the communication. Group key can be used to establish secure communication over an unreliable channel in wireless network.

In mobile wireless networks, users may move in or out of range frequently so that the topology of network dynamically changes with frequent membership changes. Therefore, group key must be re-keyed accordingly. When some legal users lost their keys due to network faults and then requested those keys from the group manager, not only the burden of the group manager was increased but also the wireless network traffic, as well. In order to make legal nodes recover their lost legal keys without asking the group manager, the research on self-healing key distribution started in 2002.

An important concept is session, which is a fixed interval of time. The group manager divides the total lifetime of group communication into certain number of sessions. Each session has a session key. At the beginning of group communication, the group manager sends personal secret information to each of initial group users. The group manager can add users to or remove users from the group at the beginning of each session. The central concept of self-healing key distribution is to broadcast some packets about key so that the legal users can recover their lost session keys due to network failure without requesting help from the group manager. It can decrease the work load on the group manager and reduce the network traffic. The self-healing key distribution scheme must guarantee that only legal users can recover their lost legal session keys but illegal users can not.

Our contributions in this study are as follows; first, we propose an efficient key distribution scheme with self-healing property and revocation capability for secure group communication in wireless network. Present scheme is based on dual directional hash chain so that it has significant improvement in terms of both communication and storage cost compared with those previous schemes which are not based on hash chains. Second, random numbers are used in the process of achieving the important factor for computing session keys. Therefore, our scheme can resist the collusion of revoked users and newly joined users, while the previous schemes based on hash chains can not totally overcome such flaw.

Self-healing key distribution with revocation was first introduced by Staddon et al. (2002). In terms of entropy theory, definitions and lower bounds on resources were provided. Liu et al. (2003) generalized the definition 2 in the scheme (Staddon et al., 2002) and provided a more efficient construction. Blundo et al. (2004) showed an attack applied to the first construction in scheme (Staddon et al., 2002) and presented a new scheme different from those methods (Liu et al., 2003; Staddon et al., 2002). In the scheme (Blundo et al., 2004), a user can recover all the lost legal session keys simply by using the current broadcast messages. Hong and Kang (2005) changed the redundant mode of session key. All the above schemes are based on Shamir’s secret sharing technique. Saez (2005a, b) adopted vector space secret sharing instead of Shamir’s secret sharing to realize the self-healing key distribution (Saez, 2005a) and sponsorization (Saez, 2005b). More et al. (2003) proposed a sliding-window self-healing key distribution scheme. Zou and Dai (2006) adopted a new revocation polynomial to make illegal users get wrong random values. Dutta and Mukhopadhyay (2007a, b) and Dutta et al. (2007b, 2008) did not divide session keys into two polynomials but concealed the session keys directly. Jiang et al. (2007) proposed a concept of dual directional hash chain. Other schemes (Dutta et al., 2007a; Shi et al., 2007) were also based on hash chain, which could reduce the communication cost and storage cost. However, these schemes (Dutta et al., 2007a; Jiang et al., 2007; Shi et al., 2007) can not resist collusion between revoked users and newly joined users. In order to overcome this drawback, Tian et al. (2008) proposed a scheme based on vector space secret sharing and one-way hash chains. However, the scheme was invalid for resisting collusion of newly joined users and revoked users whose lifetimes did not expire. In this study, we devote to totally solve the collusion in self-healing key distribution schemes based on hash function.

PRELIMINARIES

The notations used in the study are defined below:

A Dual Directional Hash Chain (DDHC) consists of two one-way hash chains with equal length, a Forward Hash Chain (FHC) and a Backward Hash Chain (BHC). First, GM generates two random key seeds, FS and BS, from finite field F_q. Then GM repeatedly applies the same one-way function H on each key seed to produce two hash chains of equal length m. So, the DDHC is denoted by {H(FS),…, Hⁱ(FS),…, H^m(FS)} and {H(BS),…, Hⁱ(BS),…, H^m(BS)} (Jiang et al., 2007).

We state the following definitions (Dutta et al., 2007a; Tian et al., 2008) that are aimed to computational security for session key distribution, according to the security model in scheme (Liu et al., 2003).

Definition 1: Let t,i ∈ {1,…,n} and j ∈ {1,…,m}

Definition 2: D guarantees t-wise forward secrecy and backward secrecy if:

Definition 3: D resist collusion if for disjoint set B and C, where B ⊂R_v ∪ … ∪ R₁, C ⊂J_s ∪ … ∪ J_m and |B ∪ C|≤ t, it is infeasible for collusion B ∪ C to get any information about K_j, where v<j<s.

To sum up, definition 1 defines a self-healing key distribution scheme with revocation capability. Definition 2 defines both forward secrecy and backward secrecy. Definition 3 defines resisting collusion property.

PROPOSED SCHEME

The lifetime of group communication is divided into m sessions, where a session is a fixed interval of time. The scheme considers all of operations taking place in a finite field F_q, where q is a large prime number (q>m). The scheme never allows the revoked users to rejoin the group in later sessions. Let H: F_q → F_q be a cryptographically secure one-way hash function.

The self-healing key distribution scheme consists of five procedures, i.e., setup, broadcast, key recovery, adding new members and self-healing, which are defined as follows:

Setup: GM randomly picks two initial key seeds, FS and BS, from F_q. In the pre-processing time, it repeatedly applies the one-way function H on FS and BS to produce DDHC of equal length m. For 1≤ j≤ m, the j-th session key is computed by:

where c_j is a random number corresponding to session j.

For m sessions, GM chooses, independently and uniformly at random, m t-degree(t<m,n) polynomials h₁(x),h₂(x),…, h_m(x) ∈ F_q[x] and generates m random numbers r₁,r₂,…,r_m ∈ F_q, respectively corresponding to h₁(x),h₂(x),…, h_m(x).

For 1≤ i≤ m, each user u_i whose lifetime is from session l to session v receives the private secrets corresponding to his legal sessions. The private secrets include set S_i = {h_l(u_i),h_l+1(u_i),…, h_v(u_i)}, set r ={r_l,r_l+1,…,r_v}, forward key seed SFK_i=H(FS)^l and backward key seed SBK_i=H(BS)^m-v+1. GM and u_i communicate through secure channel.

Broadcast: Let R_j be the set of all users revoked in and before sessions j, where |R_j|=z_j<t. In the j-th session GM firstly produces random number c_j in the finite field F_q. Secondly, GM produces the revocation polynomial A_j(x)= ∏ ^zj_i=1(x-u_i), where u_i ∈ R_j and the broadcast polynomial W_j(x)=A_j(x)c_j+h_j(x), where the polynomial h_j(x) plays the role of masking polynomial. Thirdly, GM produces the set C_j = {c_jr₁(c₁+c₂), c_jr₂(c₂+c₃), …, c_jr_j-2(c_j-2+c_j-1), c_jr_j-1c_j-1}. Finally, GM broadcasts the message B_j = {W_j(x),C_j,_,R_j}.

Key recovery: When a non-revoked user u_i receives the j-th broadcast message B_j, u_i firstly evaluates A_j(u_i) and subsequently recovers c_j = (W_j(u_i)-h_j(u_i))/A_j(u_i). Secondly, u_i computes the j-th forward key Fk_j = H(SFK_i)^j-l and backward key BK_j=H(SBS)^v-j. Finally, u_i computes the j-th session key K_j=(FK_j+BK_j)c_j.

Adding group member: When a new user u_i expects to join the group and to be active from session l to session v, u_i must get in touch with GM. The GM computes u_i’s private secrets, i.e., set S_i = {h_l(u_i), h_l+1(u_i),…, h_v(u_i)}, SFK_i = H(FS)¹ and SBK_i = H(BS)^m-v+1. Finally, the GM sends {S_i,r = {r_l,r_l+1,…,r_v}, SFK_i, SBK_i} to u_i via secure channel between GM and u_i.

Self-healing: Suppose user u_i whose lifetime is from session l to session v receives broadcast message B_j1 in session j₁, but not message B_j for session j, where 1≤ l<j<j₁≤ v≤ m user u_i can recovers the lost session key K_j as follows:

Firstly, u_i repeatedly applies the one-way function H on each of his two key seeds, SFK_i and SBK_i obtained in joining process, until u_i gets the forward key Fk_j = H(SFK_i)^j-l and the backward key Bk_j = H(SBK_i)^v-j for session j.

Secondly, for broadcast message B_j1 ={W_j1(x),C_j1,R_j1}, user u_i computes c_j1 from W_j1(u_i) by his private secret h_j1(u_i). By dividing each item of set C_j1 by c_j1, user u_i obtains a new set C_j1’ ={r₁(c₁+c₂),r₂(c₂+c₃),…, r_j1-2(c_j1-2+c_j1-1), r_j1-1c_j1-1}.

Thirdly, user u_i has a private secret set r’ = {r_l,…,r_j, r_j+1,…, r_j1-1,…, r_v}. Therefore, By using the private secret set r’= = {r_j, r_j+1,…, r_j1-1}, where r’= ⊂r’, user u_i can compute c_j as follows:

Finally, K_j=(FK_j+BK_j)c_j.

SECURITY ANALYSIS

Present study shows that proposed scheme realizes a self-healing key distribution with revocation capability and resisting collusion property. Now, we will prove that our scheme satisfies all the conditions required by definition 1, 2 and 3.

Theorem 1: The scheme is secure, self-healing key distribution scheme with t-revocation capability with respect to definition 1.

Proof 1: The scheme is a session key distribution with privacy.

Proof 2: The scheme has t-revocation capability.

Let R = R_j ∪ … ∪ R₁ (|R|<t) be the set of revoked users in and before session j. For user u_i ∈ R, because the revocation polynomial A_j(u_i) is always zero, user u_i can not compute c_j from broadcast polynomial W_j(u_i). Therefore, coalition R must attack the masking polynomial h_j(x) to get c_j. For the size of the coalition R is t at most, the colluding users only have at most t points on the masking polynomial h_j(x). But the degree of the polynomial h_j(x) is t. Hence coalition R can not recover h_j(x). Because there is no information of c_j, it is infeasible for the coalition R to compute session key K_j.

Proof 3: The scheme has self-healing capability, as is described in the fifth step of proposed scheme.

Theorem 2: The scheme achieves t-wise forward security and backward security with respect to definition 2.

Proof 1: Let R=R_j ∪ … ∪ R₁ (|R|<t) be a coalition of revoked users colluding in and before session j. In order to attack t-degree polynomial h_j(x), coalition R needs at last t+1 points on h_j(x). But the size of coalition R is t at most. Hence coalition R can not recover h_j(x). Furthermore, because of the one-way property of BHC, it is computationally infeasible to compute Bk_v = H(BS)^m-v+1 from Bk_j = H(BS)^m-j+1 for j<v. Therefore, the scheme guarantees the t-wise forward security.

Proof 2: Let J = J_j ∪ … ∪ J_m (|J|<t) be a coalition of joined users colluding from session j. For session key K_j1, where j₁<j, coalition J requires at least t+1 points on polynomial h_j1(x) to attack t-degree polynomial h_j(x). However, the size of coalition J is t at most. Hence coalition J can not recover h_j(x). Furthermore, because of the one-way property of FHC, it is computationally infeasible to compute Fk_j1 = H(FS)^j1 from Fk_j = H(FS)^j. Therefore, the scheme guarantees the t-wise backward security.

Theorem 3: The scheme resists collusion of revoked users and newly joined users with respect to definition 3.

Proof: Let B ⊂R_v ∪ … ∪ R₁ be a set of users revoked from group before session v and let D ⊂J_s ∪ … ∪ J_m be a set of users who joined the group from session s, where v<s. Set B and set D are disjointed. Set L ⊂B ∪ D, where |B ∪ D|<t, is a coalition of users colluding to attempt to get the session key K_j for session j, where v<j<s. the coalition L can easily compute forward key FK_j and backward key BK_j for session j via the property of DDHC. Therefore, it is necessary for coalition L to get c_j. Because the size of coalition L is t at most, the coalition L can not have at least t+1 point on t-degree masking polynomial h_j(x). Therefore, it is infeasible for the coalition L to get c_j by attacking masking polynomial h_j(x). Furthermore, in order to get c_j, the coalition L can resort to working on i-th broadcast set C_i for session i, where i>j. However, without the knowledge of private secret set {r_v+1, r_v+2,…, r_j,…, r_s-1} for session r_v+1, r_v+2,…, r_j,…, r_s-1, the coalition L can not get c_j from i-th broadcast set C_i. Therefore, it is infeasible for the coalition L to compute the session key K_j without the knowledge of random number c_j for session j. As a result, the scheme resists the collusion of revoked users and newly joined users.

PERFORMANCE ANALYSIS

In order to evaluate the performance of the proposed method, we will compare the communication complexity and storage cost between our scheme and the previous self-healing session key distribution schemes.

At the j-th session, the broadcast message B_j consists of t-degree broadcast polynomial W_j(x), set C_j and revocation set R_j. The size of set C_j is j-1. The communication cost for the broadcast of revocation set R_j can be ignored because the identity of users can be selected from a small finite field (Hong and Kang, 2005). Therefore, the communication cost of our scheme is O((t+j)logq) for session j.

In the process of joining group, user u_i who is legal from session j to session v obtains his private secrets, i.e., set S_i, set r, forward key seed SFK_i and backward key seed SBK_i. The size of set S_i and the size of set r are both l-v+1. Therefore, the storage cost of user u_i is a constant, O((2l-2v+4))logq),corresponding to his lifetime from session l to session v.

We compare the communication complexity and storage cost of our scheme with the previous schemes not based on one-way hash chain. The results are listed in Table 1. The schemes (Dutta and Mukhopadhyay, 2007a, b; Dutta et al., 2007b) do not have the capability of resisting collusion.

Table 1:	Comparison between our scheme and previous schemes not based on one-way hash chain

Table 2:	Comparison between our scheme and previous schemes based on one-way hash chain

The communication complexity of our scheme is O((t+j)logq) while those of the other schemes are more than or equal to O((t+j+1)logq). Furthermore, the storage cost of a user in our scheme is (2l-2v+4))logq which corresponds to his lifetime. Although the two schemes (Zou and Dai, 2006; Dutta et al., 2007b) are more efficient than ours in terms of storage cost, proposed scheme is more efficient than theirs in terms of the communication complexity. According to the comparison results in Table 1, we conclude that our scheme is more efficient than the previous schemes not based on one-way hash chain.

We compare the communication complexity and storage cost of our scheme with previous schemes based on one-way hash chain. The results are shown in Table 2. Although the two schemes (Jiang et al., 2007; Shi et al., 2007) are better than our scheme in term of communication complexity and storage cost, the users in the schemes (Jiang et al., 2007; Shi et al., 2007) can not be revoked by GM and will exit only with their lifetimes expiring. Furthermore, these two schemes can not resist the collusion of newly users and detached users. Although the scheme (Dutta et al., 2007a) has the revocation capability, it can not resist the collusion of newly joined users and revoked users. The scheme (Tian et al., 2008) can resist the collusion of newly joined users and revoked users whose lifetimes have expired. However, the scheme (Tian et al., 2008) can not resist the collusion of newly joined user and revoked users whose lifetimes do not expire. From the comparison in Table 2, although the communication cost and storage cost of proposed scheme are slightly increased, only our scheme can resist collusion of newly joined user and revoked users no matter whether their lifetimes expire or not.