A Key Distribution Scheme for WSN Based on Hash Chains and Deployment Knowledge

Abstract

Based on the deployment knowledge and the irreversibility of some hash chains, a novel pairwise key distribution scheme (DKH-KD) for wireless sensor networks is proposed. In DKH-KD scheme, before the nodes in the network are deployed, the offline server constructs a number of hash chains and uses the values from a pair of reverse hash chains to establish their pairwise keys among the nodes in the same region, while, among the neighbor nodes in the different regions, some pairs of the hash chains based on the deployment knowledge are employed to establish the pairwise keys. These procedures make the attackers hard to break the network and ensure that the probability of the pairwise key establishment is close to 1. Compared with the Dai scheme and the q-composite's scheme, our analyses show that DKH-KD scheme can improve the probability of the pairwise key establishment and the invulnerability more efficiently.

1. Introduction

Compared with traditional networks, a wireless sensor network (WSN) is an acentric, self-organizing, multichannel routing, distribution-intensive, and dynamic topological network. There exist a large number of resource-limited nodes in a WSN. WSNs have been widely used for a variety of purposes and situations, such as in smart homes, environmental monitoring and medical surveillance, national defense and national security, and other sensitive areas. At the same time, due to the fact that the sensor nodes in the network are resource-limited in their storage spaces, communication capability, and computing power, WSNs face many security challenges [1–3]. To an extraordinary degree, these security issues reside in the security of the keys used in WSNs. Therefore, to design a safe and reliable key management scheme for WSNs is the crucial point of these security issues, while the key distribution is one of the core steps of the key management.

In 2002, Eschenauer and Gligor proposed a key distribution strategy (denoted as “E-G scheme” for short) for the large-scale distributed sensor networks (DSNs) [4]. In E-G scheme, the precondition that makes any two nodes communicate with each other is that the two nodes must have at least one shared key chain from their own key pool. Some previous work improved the E-G scheme. Such as in [5], the improved scheme required that any two nodes must have at least q the same keys to communicate with each other, but it is more secure than the E-G scheme. The pairwise key predistribution scheme described in [6] was based on Blom-matrix with threshold characteristics and a binary symmetric polynomial. Although this scheme improved the security significantly, the node's energy consumption also increased. In [7], a deterministic key distribution scheme was proposed. This scheme adopted an incomplete block design and a finite projective plane to construct the pairwise keys, and its advantage was that any two adjacent nodes could establish a shared pairwise key, but it has the disadvantage that the nodes would lose some storage space and their security was also reduced. In [8], a combinatorial design solution was introduced based on a generalized quadrangle. This solution made up the shortcomings of the scheme given in [7], but it also reduced the node's local connection probability. Because the nodes within the same region will more likely become their adjacent nodes than the nodes deployed in different regions do, some improved pairwise key distribution schemes were proposed based on the deployment knowledge in [9–11]. These schemes had a relative balance between the local connection probability and the security. Based on the deployment knowledge and some hash chains, in this paper, a key distribution scheme for WSNs is proposed.

The remainder of this paper is organized as follows. Some notations and hash chains are given in Section 2. Some related key distribution schemes for WSNs are introduced in Section 3. Based on the deployment knowledge and some hash chains, a novel key distribution scheme, called DKH-KD, is proposed in Section 4. In Section 5, based on our simulating results, we make the performance analysis on our scheme. Finally, some conclusion remarks are made in Section 6.

2. Notations and Hash Chains

2.1. The Notations

Some notations with their implications are introduced in “Notation” section, and they are to be used in our following discussions.

2.2. Hash Chain

(For a seed s, a generated hash chain may be fore-and-aft symmetric; that is, its reverse hash chain becomes the same to the hash chain. It will result in some potential safety hazard to our scheme. In order to prevent this phenomenon, we can check whether the obtained hash value is equal to some previous hash values when we compute the hash value. If it happens, then we reselect the seed s and regenerate the hash chain, or we can make the hash value plus 1 or minus 1 and then compute the next hash value. If our selected hash function is a cryptographically secure hash, then fore-and-aft the symmetric hash will be produced in a very small probability.)

Definition 1.

By randomly selecting a seed s and a hash function $h(x)$ , one can generate a logic value chain as follows:

$$\begin{array}{cc}& V_i=h\left(V_{i-\mathrm{1}}\right)=h^{\mathrm{2}}\left(V_{i-\mathrm{2}}\right)=\cdots =h^{i-\mathrm{1}}\left(V_{\mathrm{1}}\right)=h^{i-\mathrm{1}}\left(h\left(s\right)\right),\\ V_{\mathrm{0}}=s,\end{array}$$

(1)

where $V_i$ denotes the hash value in the chain, $i=\mathrm{1},\mathrm{2},\dots ,n$ . Here, $h(x)$ may be chosen as a hash function SHA-2 or SHA-3. Then, $\{V_i\hspace{0.17em}|\hspace{0.17em}i=\mathrm{1},\dots ,n\}$ is called a hash chain and its structure is shown as in Figure 1.

Figure 1

A hash chain.

2.3. Reverse Hash Chain

Definition 2.

Let $v_{\mathrm{1},m}$ and $v_{\mathrm{2},m}$ denote the mth hash value of the hash chains $C_{\mathrm{1}}$ and $C_{\mathrm{2}}$ , respectively. Suppose that the two hash chains have the same length n. If for any positive integer $m\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le m\le n)$ , their mth hash values of $C_{\mathrm{1}}$ and $C_{\mathrm{2}}$ are $v_{\mathrm{1},m}$ and $v_{\mathrm{2},n-m}$ , respectively, then we call $C_{\mathrm{1}}$ and $C_{\mathrm{2}}$ a pair of the reverse hash chains.

2.4. GetHash Function

Definition 3.

Suppose that $h_{\mathrm{1}}$ and $h_{\mathrm{2}}$ are two different hash functions and set $H=\{h_{\mathrm{1}},h_{\mathrm{2}}\}$ . Let C be the input hash chain and let $C^{\prime }$ be the output hash chain. Suppose that $h\in H$ is the hash function of the output hash chain $C^{\prime }$ and both of the lengths of $C^{\prime }$ and C are n. Then, as Figure 2 shows, the $GetHash$ function is defined to be a function that makes C become $C^{\prime }$ through h as follows:

$GetHash:(C,h)\to C^{\prime }$ , where $C^{\prime }$ is the following hash chain:

$$\begin{array}{cc}& v_{\mathrm{1}}^{\prime }=h\left(v_n\right),\hspace{1em}\hspace{1em}{v}_{\mathrm{2}}^{\prime }=h\left(v_{\mathrm{1}}^{\prime }\right),\dots ,v_n^{\prime }=h\left(v_{n-\mathrm{1}}^{\prime }\right).\end{array}$$

(2)

That is, the $GetHash$ function makes the nth value of C the input seed of $C^{\prime }$ and then generates the hash chain $C^{\prime }$ . We denote it as $C^{\prime }=GetHash(C,h)$ .

Figure 2

The model of $GetHash$ function.

2.5. Network Model

The traditional key distribution technologies are generally used in some large-scale wireless sensor networks. But these technologies had some inherent disadvantages. For example, in order to ensure a certain local connection probability, the nodes must store a large number of keys. Usually, two adjacent nodes have stored a lot of meaningless key relative information of other nonadjacent nodes and it will waste the nodes’ storage space. What is more, if these nodes are caught by an attacker, then they will seriously threaten the other nodes’ security.

Most of the current key distribution schemes cannot ensure the local connection probability and security well at the same time. Since deploying nodes in batch will hide the nodes’ location information, it can efficiently ensure the local connection probability and security simultaneously. In fact, deploying nodes in batch has some good characteristics, such as the nodes deployed in different batches may become adjacent nodes, and the probability of the nodes deployed in the same batch becoming neighbors is greater than that of the nodes deployed in adjacent batches becoming neighbors. Using the deployment feature can improve the local connection probability but will not reduce the network security. The network model using the deployment knowledge can be described as in Figure 3. We use $cell$ to denote a square area with the side length d. Let $cel{l}_{〈i,j〉}$ denote the square area numbered as $〈i,j〉$ .

Figure 3

The network model based on the deployment knowledge.

3. Some Related Schemes

In this section, we introduce the basic random key distribution scheme and two improved key distribution schemes that we will deal with in our newly proposed key distribution scheme.

The E-G scheme is a basic key distribution scheme for sensor networks and it consisted of three phases, that is, key predistribution, shared-key discovery, and path-key establishment.

• (1)

The key predistribution phase was composed of the five off-line steps; that is, (1) generating a large key pool, (2) randomly drawing some keys out of the key pool to establish the key ring of each sensor node, (3) loading the key ring into the memory of each node, (4) saving the key identifiers of a key ring and the associated sensor identifier on a trusted controller node, and (5), for each node, loading the ith controller node with the key shared with that node. The key predistribution phase ensures that only a small number of keys need to be placed on each node's key ring to ensure that any two nodes share a key with a chosen probability.

(2)

The shared-key discovery phase takes place during DSN initialization in the operational environment where every node discovers its neighbors in wireless communication range with which it shares keys. In this phase, any two nodes will discover whether they share a key.

(3)

The path-key establishment phase assigns a path-key to the selected pairs of the sensor nodes in wireless communication range that do not share a key but are connected by two or more links at the end of the shared-key discovery phase.

Chan et al. proposed a random key predistribution scheme for sensor networks in 2003 [5]. This scheme was an improved version of the E-G scheme and it is a well-known probabilistic key predistribution scheme, generally called the q-composite scheme for short. This scheme can achieve greatly strengthened security under small scale attack while trading off increased vulnerability in the face of a large scale physical attack on network nodes. The q-composite scheme uses a key pool and requires any two nodes to compute a pairwise key for their communication from at least q predistributed keys they share.

The structure of the q-composite scheme is similar to that of the E-G scheme but differs only in the size of the selected key pool S and the fact that multiple keys were used to establish communications between two nodes instead of just one key.

In its initialization phase, that is, in the key predistribution phase, a key pool set S is selected from the total key space; then, for each node, multiple keys are randomly chosen from S and stored into the node's key ring. In the key-setup phase, each node must discover all shared keys it possesses with each of its neighboring nodes. After its key discovery, each node can identify every neighbor node with which it shares at least $q(>\mathrm{1})$ keys and then uses the hash value of the all shared keys with the neighbor node to produce their pairwise keys. The authors showed that the q-composite scheme could greatly strengthen the key predistribution's strength against smaller-scale attacks by trading off some large-scale network attacks.

Based on a polynomial-based scheme over a finite field, Dai and Xu proposed an improved key predistribution scheme for WSNs using deployment knowledge [12]. We called it “Dai scheme” for short. Similar to basic key distribution scheme, it also consisted of three phases: key predistribution, shared-key discovery, and path-key establishment.

The Dai scheme includes two parts: the group-based node deployment and the polynomial-based key predistribution. The strategy of the group-based node deployment is to divide the nodes into several groups $G_{i,j}$ , and the nodes in each group are deployed into a specific region, such as into a square grid cell. In its polynomial-based key predistribution part, the setup server randomly generated a big master polynomial pool S composed of symmetrical bivariate polynomials. The master polynomial pool S was then divided into smaller polynomial pools $S_{i,j}$ corresponding to the deployment groups. After that, for each sensor node in $G_{i,j}$ , some polynomials were selected from the corresponding polynomial pool $S_{i,j}$ and loaded into the memory of this node. There should be at least one polynomial between two nodes so that these two nodes can directly set up the shared keys.

The authors claimed that their scheme would achieve a high connectivity and enhance the resilience against node capture by increasing the size of security threshold.

In 2013, Bechkit et al. proposed a hash-based mechanism to enhance the network resiliency of key predistribution schemes for WSNs [13]. This mechanism can be applied to the existing pool based key predistribution schemes to enhance the network resiliency. To achieve this goal, the authors introduce a new method based on one way hash chain to conceal the keys such that the disclosure of some keys that reveals only the derived versions which cannot be used to compromise other links in the network using the backward keys. This mechanism was called HC. HC was applied to the q-composite scheme and the symmetric balanced incomplete block design scheme [8] to develop a new probabilistic key predistribution scheme and a new deterministic key management scheme. The authors showed that their approach would enhance the resiliency up to 40% without introducing any new storage or communication overheads except for inducing some computational overhead.

4. A Key Distribution Scheme Based on Deployment Knowledge and Hash Chain

In this section, using the deployment knowledge and some hash chains, we will describe a novel key distribution scheme called DKH-KD for short. In DKH-KD scheme, by using the irreversible characteristic of the hash function and the deployment knowledge, the nodes in the same $cell$ can construct a reverse hash chain corresponding to each hash chain in $cell$ . while the adjacent nodes in the different $cell\text{s}$ can construct a serial of new hash chains by adopting $GetHash$ function and the hash chains deployed in the adjacent $cell\text{s}$ .

In our following discussion, we suppose that the nodes will not be physically captured in a short time period $T_{\min }$ as they are deployed in the network. There are three stages in the key distribution of our DKH-KD scheme: (1) the construction of the hash chains; (2) the key relative information distribution in the nodes; (3) the generation of the pairwise keys. The detailed construction procedures will be described in the following subsections.

4.1. Constructing the Hash Chains

Since the irreversibility of the hash function is the important guarantee of our DKH-KD scheme's security, it is very important to construct the effective hash chains. Let the number of $cell\text{s}$ in the network be $M\times N$ and $C_{〈i,j〉}$ the hash chain set used in $cel{l}_{〈i,j〉}$ , where $\mathrm{1}\le i\le M$ , $\mathrm{1}\le j\le N$ . In Figure 3, $M=N=\mathrm{4}$ . The hash chains are constructed as follows.

(1) The Forward Hash Chains

Step 1.

If $i=j=\mathrm{1}$ , then $cel{l}_{〈\mathrm{1},\mathrm{1}〉}$ selects a random number $s_{\mathrm{1}}$ as the seed and then use the hash function $h=h_{\mathrm{1}}$ to construct the hash chain $C_{〈\mathrm{1},\mathrm{1},\mathrm{1}〉}$ with the length n.

Step 2.

If $i=\mathrm{1}$ , $\mathrm{2}\le j\le N$ , then $cel{l}_{〈\mathrm{1},j〉}$ uses the hash chain $C_{〈\mathrm{1},j-\mathrm{1},\mathrm{1}〉}$ and $GetHash$ function to generate the hash chain $C_{〈\mathrm{1},j,\mathrm{1}〉}$ as $C_{〈\mathrm{1},j,\mathrm{1}〉}=GetHash(C_{〈\mathrm{1},j-\mathrm{1},\mathrm{1}〉},h)$ .

Step 3.

If $\mathrm{2}\le i\le M$ , $j=\mathrm{1}$ , then $cel{l}_{〈i,\mathrm{1}〉}$ uses the hash chains $C_{〈i-\mathrm{1},\mathrm{1},\mathrm{1}〉}$ , $C_{〈i-\mathrm{1},\mathrm{2},\mathrm{1}〉}$ and $GetHash$ function to generate the hash chains $C_{〈i,\mathrm{1},\mathrm{1}〉}$ , $C_{〈i,\mathrm{1},\mathrm{2}〉}$ ; that is, $C_{〈i,\mathrm{1},\mathrm{1}〉}=GetHash(C_{〈i-\mathrm{1},\mathrm{1},\mathrm{1}〉},h)$ , $C_{〈i,\mathrm{1},\mathrm{2}〉}=GetHash(C_{〈i-\mathrm{1},\mathrm{2},\mathrm{1}〉},h)$ .

Step 4.

If $\mathrm{2}\le i\le M$ , $\mathrm{2}\le j\le N$ , then $cel{l}_{〈i,j〉}$ uses the hash chains $C_{〈i,j-\mathrm{1},\mathrm{1}〉}$ , $C_{〈i-\mathrm{1},j-\mathrm{1},\mathrm{1}〉}$ , $C_{〈i-\mathrm{1},j,\mathrm{1}〉}$ , $C_{〈i-\mathrm{1},j+\mathrm{1},\mathrm{1}〉}$ , and $GetHash$ function to generate the hash chains $C_{〈i,j,\mathrm{1}〉}$ , $C_{〈i,j,\mathrm{2}〉}$ , $C_{〈i,j,\mathrm{3}〉}$ , and $C_{〈i,j,\mathrm{4}〉}$ as in the following:

$$\begin{array}{l}{C}_{〈i,j,\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{1}〉}=GetHash(C_{〈i,j-\mathrm{1,1}〉},h),\\ C_{〈i,j,\mathrm{2}〉}=GetHash\left(C_{〈i-\mathrm{1},j-\mathrm{1},\mathrm{1}〉},h\right),\\ C_{〈i,j,\mathrm{3}〉}=GetHash\left(C_{〈i-\mathrm{1},j,\mathrm{1}〉},h\right),\\ C_{〈i,j,\mathrm{4}〉}=GetHash\left(C_{〈i-\mathrm{1},j+\mathrm{1},\mathrm{1}〉},h\right)\\ \phantom{hhhhhhhhhihhhhhhhhh}(j\ne N),\end{array}$$

(3)

(2) Reverse Hash Chains

Step 5.

If $i=M$ , $j=N$ , then $cel{l}_{〈M,N〉}$ selects a random number $s_{\mathrm{2}}$ as the seed and uses the hash function $h=h_{\mathrm{2}}$ to construct the hash chain ${\overleftarrow{C}}_{〈M,N,\mathrm{4}〉}$ with the length n.

Step 6.

If $i=M$ , $\mathrm{1}\le j\le N-\mathrm{1}$ , then $cel{l}_{〈M,j〉}$ uses the hash chain $C_{〈M,j+\mathrm{1},\mathrm{1}〉}$ and $GetHash$ function to generate the reverse hash chain ${\overleftarrow{C}}_{〈M,j,\mathrm{4}〉}$ as ${\overleftarrow{C}}_{〈M,j,\mathrm{4}〉}=GetHash(C_{〈M,j+\mathrm{1},\mathrm{1}〉},h)$ .

Step 7.

If $\mathrm{1}\le i\le M-\mathrm{1}$ , $j=N$ , then $cel{l}_{〈i,N〉}$ uses the hash chains $C_{〈i+\mathrm{1},N,\mathrm{1}〉}$ ,  $C_{〈i+\mathrm{1},N-\mathrm{1},\mathrm{1}〉}$ and $GetHash$ function to generate the hash chains $C_{〈i,N,\mathrm{4}〉}$ and $C_{〈i,N,\mathrm{5}〉}$ to get $C_{〈i,N,\mathrm{4}〉}=GetHash(C_{〈i+\mathrm{1},N,\mathrm{1}〉},h)$ and $C_{〈i,N,\mathrm{5}〉}=GetHash(C_{〈i+\mathrm{1},N-\mathrm{1},\mathrm{1}〉},h)$ .

Step 8.

If $\mathrm{1}\le i\le M-\mathrm{1}$ , $\mathrm{1}\le j\le N-\mathrm{1}$ , then the hash chains $C_{〈i,j+\mathrm{1},\mathrm{1}〉}$ , $C_{〈i+\mathrm{1},j+\mathrm{1},\mathrm{1}〉}$ , $C_{〈i+\mathrm{1},j,\mathrm{1}〉}$ , $C_{〈i+\mathrm{1},j-\mathrm{1},\mathrm{1}〉}$ , and $GetHash$ function are used to generate the reverse hash chains ${\overleftarrow{C}}_{〈i,j,\mathrm{5}〉}$ , ${\overleftarrow{C}}_{〈i,j,\mathrm{6}〉}$ , ${\overleftarrow{C}}_{〈i,j,\mathrm{7}〉}$ , and ${\overleftarrow{C}}_{〈i,j,\mathrm{8}〉}$ ; that is, they are the following:

$$\begin{array}{cc}& {\overleftarrow{C}}_{〈i,j,\mathrm{5}〉}=GetHash\left(C_{〈i,j+\mathrm{1},\mathrm{1}〉},h\right),\\ {\overleftarrow{C}}_{〈i,j,\mathrm{6}〉}=GetHash(C_{〈i+\mathrm{1},j+\mathrm{1},\mathrm{1}〉},h),\\ {\overleftarrow{C}}_{〈i,j,\mathrm{7}〉}=GetHash(C_{〈i+\mathrm{1},j,\mathrm{1}〉},h),\\ {\overleftarrow{C}}_{〈i,j,\mathrm{8}〉}=GetHash\left(C_{〈i+\mathrm{1},j-\mathrm{1},\mathrm{1}〉},h\right).\end{array}$$

(4)

According to the above Steps 1 to 8, the all needed hash chains have been constructed in the whole networks. As in Figure 4, each $cell$ contains 3 to 8 hash chains according to its different positions. The above method for constructing hash chains can make any adjacent $cell$ in the network have two hash chains relating to the deployment knowledge. The key relative information stored in advance for all the nodes in $cell\text{s}$ can be produced from these hash chains.

Figure 4

The structure of the hash chains in $cell\text{s}$ .

4.2. Key Relative Information Distribution for the Nodes

After the hash chains of $cell\text{s}$ in the network have been established, the offline server can start to distribute the key relative information for the nodes in the network. The key relative information is not the pairwise key but the messages for the establishment of the pairwise keys. The offline server only works in the key initialization phase for the distribution of the nodes’ key relative information.

Assume that U is the kth node in one cell. Then the offline server will distribute the kth hash value for some hash chain in U, and it also needs to distribute the ( $n-k$ )th hash value for another hash chain. This value will be used in a reverse hash chain. As shown in the above subsection, each cell has at least three hash chains, and it must be ensured that each key relative message is assigned only once in the distribution process.

The allocation algorithm can be described as shown in Algorithm 1.

Algorithm 1: The offline server distributes key relative information for the nodes in $$cel{l}_{〈r,s〉}$$ .

Input: The hash chain set $$C_{〈r,s〉}$$ , one hash chain $$C_{〈r,s,b〉}\in C_{〈r,s〉}$$ .

Output: The key relative information for the nodes in $$cel{l}_{〈r,s〉}$$ .

(1) Set $$\text{Nod}{\text{e}}_{〈r,s,k〉}$$ be the kth node in $$cel{l}_{〈r,s〉}$$ ;

(2) Set NodeNum:= the number of the nodes in $$cel{l}_{〈r,s〉}$$ ;

(3) Set ChainNum:= the number of the hash chain in $$C_{〈r,s〉}$$ ;

(4) Initialize $$k=\mathrm{1}$$ , $$t=\mathrm{1}$$

 While (k <= NodeNum) {

  While (t <= ChainNum) {

   if ( $$C_{〈r,s,t〉}$$ == $$C_{〈r,s,b〉}$$ ) {

    (a) flag = True; //Mark that the values of this hash chain will be cooperatively used with the reverse hash chain;

    (b) Store the following six messages

  $$〈r,s,t〉$$ , $$〈i_r,j_s,y_t〉$$ , $$vi{d}_{〈r,s,t〉(\mathrm{1})}$$ , $$id{h}_{〈r,s,t〉}$$ , $$flag$$ , $$V_{〈r,s,t〉(n-k)}$$ in $$\text{Nod}{\text{e}}_{〈r,s,k〉}$$

   }

   else {

    (c) flag = False; //Mark that this chain is a common hash chain;

    (d) Store the following six messages

  $$〈r,s,t〉$$ , $$〈i_r,j_s,y_t〉$$ , $$vi{d}_{〈r,s,t〉(\mathrm{1})}$$ , $$id{h}_{〈r,s,t〉}$$ , $$flag$$ , $$V_{〈r,s,t〉(k)}$$ in $$\text{Nod}{\text{e}}_{〈r,s,k〉}$$

   }

   t++;

  }

  k++;

 }

(5) End.

According to Algorithm 1, $\text{Nod}{\text{e}}_{〈r,s,k〉}$ saves six parameters: (1) the serial number $〈r,s,t〉$ of the hash chain; (2) the input hash chain's serial number $〈i_r,j_s,y_t〉$ of the hash chain $C_{〈r,s,t〉}$ ; (3) the subscript $vi{d}_{〈r,s,t〉(\mathrm{1})}$ of the first hash value in this hash chain; (4) the serial number $id{h}_{〈r,s,t〉}$ of the corresponding hash function; (5) the mark $flag$ ; (6) the $k\text{th}$ or $(n-k)\text{th}$ pairwise key value of the hash chain $C_{〈r,s,t〉}$ .

4.3. The Establishment of the Pairwise Keys

After the key relative information distribution process is completed, the nodes will immediately begin to establish the pairwise keys. Table 1 shows the hash chain information stored in one node after the key distribution Algorithm 1 has been implanted. From Table 1, we know that the adjacent nodes in the same $cell$ can use the values of a pair of the reverse hash chains to establish the pairwise key while the nodes in the adjacent $cell\text{s}$ can employ the value of the hash chain associated with deployment to establish the pairwise keys.

Table 1

The key related information of one hash chain.

The key relative information of a hash chain stored in nodes
$$〈r,s,t〉$$	$$〈i_r,j_s,y_t〉$$	$$vi{d}_{〈r,s,t〉(\mathrm{1})}$$	$$id{h}_{〈r,s,t〉}$$	$$flag$$	$$V_{〈r,s,t〉(m)}$$ or $$V_{〈r,s,t〉(n-m)}$$

In the initialization phase, the nodes broadcast the key related information except $V_{〈r,s,t〉(m)}$ and $V_{〈r,s,t〉(n-m)}$ . Suppose that $h_{\mathrm{1}}$ and $h_{\mathrm{2}}$ are two hash functions and $H=\{h_{\mathrm{1}},h_{\mathrm{2}}\}$ . For the nodes in the wireless sensor network, their pairwise keys can be established in the two cases: (1) establishing the pairwise keys for the adjacent nodes in the same $cell$ ; (2) establishing the pairwise keys for the adjacent nodes in the adjacent $cell\text{s}$ .

(1) Establishing the Pairwise Key for the Adjacent Nodes in the Same $Cell$ . Let U and V be two adjacent nodes in the same $cell$ . Then, U and V will use a pair of the reverse hash chain key-values to establish the pairwise key. From Section 4.2, we know that every node has stored a hash value with its $flag$ being true. Suppose that this hash value belongs to the hash chain $C_{〈i,j,b〉}$ . From the stored hash values, randomly select another value and suppose that it belongs to the hash chain $C_{〈i,j,a〉}$ . Then, the two hash values can be cooperated to establish a pairwise key.

Let U and V be two nodes. Suppose that the key-value pairs stored in the nodes U and V are $\{k{u}_{m_{\mathrm{1}}},k{u}_{n-m_{\mathrm{1}}}\}$ and $\{k{v}_{m_{\mathrm{2}}},k{v}_{n-m_{\mathrm{2}}}\}$ with their subscripts being $\{u_{vid〈i,j,a〉(m_{\mathrm{1}})},u_{vid〈i,j,b〉(n-m_{\mathrm{1}})}\}$ and $\{v_{vid〈i,j,a〉(m_{\mathrm{2}})},v_{vid〈i,j,b〉(n-m_{\mathrm{2}})}\}$ , respectively. Let the two hash chains $C_{〈i,j,a〉}$ and $C_{〈i,j,b〉}$ use the two hash functions $h_{\mathrm{1}}$ and $h_{\mathrm{2}}$    $(h_{\mathrm{1}},h_{\mathrm{2}}\in H)$ , respectively. Let $f(x,y)$ be a 2-variable hash function extended from some 1-variable hash function (e.g., suppose that $f_{\mathrm{1}}$ and $f_{\mathrm{2}}$ are two different 1-variable hash functions and we define $f(x,y)=f_{\mathrm{1}}(x)\oplus f_{\mathrm{2}}(y)$ ; then $f(x,y)$ is a 2-variable hash function). The establishment process of their pairwise key for the nodes U and V can be described as in the following.

Step 1.

Node U establishes a pairwise key with Node V.

• (a)

If $u_{vid〈i,j,a〉(m_{\mathrm{1}})}<v_{vid〈i,j,a〉(m_{\mathrm{2}})}$ , then U computes $k_{uv}=f(k_{\mathrm{1}},k_{\mathrm{2}})$ and set the result $k_{uv}$ to be the pairwise key, where $k_{\mathrm{1}}=h_{\mathrm{1}}(k{u}_{m_{\mathrm{1}}}{)}^{\begin{array}{c}\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ v_{vid〈i,j,a〉(m_{\mathrm{2}})}-u_{vid〈i,j,a〉(m_{\mathrm{1}})}\end{array}}$ and $k_{\mathrm{2}}=k{u}_{n-m_{\mathrm{1}}}$ .

(b)

If $u_{vid〈i,j,a〉(m_{\mathrm{1}})}>v_{vid〈i,j,a〉(m_{\mathrm{2}})}$ , then U computes $k_{uv}=f(k_{\mathrm{1}},k_{\mathrm{2}})$ and set the result $k_{uv}$ to be the pairwise key, where $k_{\mathrm{1}}=h_{\mathrm{2}}(k{u}_{n-m_{\mathrm{1}}}{)}^{u_{vid〈i,j,b〉(n-m_{\mathrm{1}})}-v_{vid〈i,j,b〉(n-m_{\mathrm{2}})}}$ and $k_{\mathrm{2}}=k{u}_{m_{\mathrm{1}}}$ .

Step 2.

Node V establishes a pairwise key with Node U.

• (a)

If $v_{vid〈i,j,a〉(m_{\mathrm{2}})}<u_{vid〈i,j,a〉(m_{\mathrm{1}})}$ , then V computes $k_{vu}=f(k_{\mathrm{1}},k_{\mathrm{2}})$ and set the result $k_{vu}$ to be the pairwise key, where $k_{\mathrm{1}}=h_{\mathrm{1}}(k{v}_{m_{\mathrm{2}}}{)}^{u_{vid〈i,j,a〉(m_{\mathrm{1}})}-v_{vid〈i,j,a〉(m_{\mathrm{2}})}}$ and $k_{\mathrm{2}}=k{v}_{n-m_{\mathrm{2}}}$ .

(b)

If $v_{vid〈i,j,a〉(m_{\mathrm{2}})}>u_{vid〈i,j,a〉(m_{\mathrm{1}})}$ , then V computes $k_{vu}=f(k_{\mathrm{1}},k_{\mathrm{2}})$ and set the result $k_{vu}$ to be the pairwise key, where $k_{\mathrm{1}}=h_{\mathrm{2}}(k{v}_{n-m_{\mathrm{2}}}{)}^{u_{vid〈i,j,b〉(n-m_{\mathrm{1}})}-v_{vid〈i,j,b〉(n-m_{\mathrm{2}})}}$ and $k_{\mathrm{2}}=k{v}_{m_{\mathrm{2}}}$ .

(2) Establish the Pairwise Key for the Adjacent Nodes in the Adjacent $Cell\text{s}$ . Let U and V be two adjacent nodes in the adjacent $cell\text{s}$ . From Sections 4.1 and 4.2, we know that U and V can find two hash chains $C{u}_{〈r,s,t〉}$ and $C{v}_{〈r,s,t〉}$ , respectively. And the hash chain $C{u}_{〈r,s,t〉}$ is constructed by the hash chain $C{v}_{〈i_r,j_s,y_t〉}$ and $GetHash$ function, while the hash chain $C{v}_{〈r,s,t〉}$ is constructed by the hash chain $C{u}_{〈i_r,j_s,y_t〉}$ and $GetHash$ function. Let the hash chains stored in the nodes U and V be, respectively, $\{C{u}_{〈r,s,t〉},C{u}_{〈i_r,j_s,y_t〉}\}$ and $\{C{v}_{〈r,s,t〉},C{v}_{〈i_r,j_s,y_t〉}\}$ , and their used hash function sets are $\{h_{\mathrm{1}},h_{\mathrm{2}}\}$ and $\{h_{\mathrm{3}},h_{\mathrm{4}}\}$ , respectively. Suppose that the key-value pairs stored in the nodes U and V are $\{k{u}_{m_{\mathrm{1}}},k{u}_{m_{\mathrm{2}}}\}$ and $\{k{v}_{m_{\mathrm{3}}},k{v}_{m_{\mathrm{4}}}\}$ , respectively. The establishment of the pairwise keys for the adjacent nodes U and V can be described as in the following.

Step 1.

Node U establishes a pairwise key with Node V: after Node U has received the broadcast messages including the subscripts from Node V, it can establish pairwise keys as follows:

• (a)

U computes $k_{\mathrm{1}}=h_{\mathrm{2}}(k{u}_{m_{\mathrm{2}}}{)}^{u_{vid〈i_r,j_s,y_t〉(n)}-u_{vid〈i_r,j_s,y_t〉(m_{\mathrm{2}})}}$ if $u_{vid〈i_r,j_s,y_t〉(n)}>u_{vid〈i_r,j_s,y_t〉(m_{\mathrm{2}})}$ ; otherwise it computes $k_{\mathrm{1}}=h_{\mathrm{2}}(k{u}_{m_{\mathrm{2}}}{)}^{u_{vid〈i_r,j_s,y_t〉(m_{\mathrm{2}})}-u_{vid〈i_r,j_s,y_t〉(n)}}$ ;

(b)

U computes $k_{\mathrm{2}}=h_{\mathrm{1}}(k_{\mathrm{1}}{)}^{v_{vid〈r,s,t〉(m_{\mathrm{4}})}-v_{vid〈r,s,t〉(\mathrm{1})}}$ if $v_{vid〈r,s,t〉(m_{\mathrm{4}})}>v_{vid〈r,s,t〉(\mathrm{1})}$ ; otherwise, it computes $k_{\mathrm{2}}=h_{\mathrm{1}}(k_{\mathrm{1}}{)}^{v_{vid〈r,s,t〉(\mathrm{1})}-v_{vid〈r,s,t〉(m_{\mathrm{4}})}}$ ;

(c)

U computes its pairwise key as $k_{uv}:k_{uv}=f(k_{\mathrm{2}},k{u}_{m_{\mathrm{1}}})$ .

Step 2.

Node V establishing pairwise key with Node U: after node V has received the broadcast message including the subscripts from U, it can establish pairwise key as follows:

• (a)

V computes $k_{\mathrm{3}}=h_{\mathrm{4}}(k{v}_{m_{\mathrm{3}}}{)}^{v_{vid〈i_r,j_s,y_t〉(n)}-v_{vid〈u_r,j_s,y_t〉(m_{\mathrm{3}})}}$ if $v_{vid〈i_r,j_s,y_t〉(n)}>v_{vid〈u_r,j_s,y_t〉(m_{\mathrm{3}})}$ ; otherwise it computes $k_{\mathrm{3}}=h_{\mathrm{4}}(k{v}_{m_{\mathrm{3}}}{)}^{v_{vid〈i_r,j_s,y_t〉(m_{\mathrm{3}})}-v_{vid〈u_r,j_s,y_t〉(n)}}$ ;

(b)

V computes $k_{\mathrm{4}}=h_{\mathrm{1}}(k_{\mathrm{3}}{)}^{u_{vid〈r,s,t〉(m_{\mathrm{4}})}-u_{vid〈r,s,t〉(\mathrm{1})}}$ if $u_{vid〈r,s,t〉(m_{\mathrm{4}})}>u_{vid〈r,s,t〉(\mathrm{1})}$ ; otherwise it computes $k_{\mathrm{4}}=h_{\mathrm{1}}(k_{\mathrm{3}}{)}^{u_{vid〈r,s,t〉(\mathrm{1})}-u_{vid〈r,s,t〉(m_{\mathrm{4}})}}$ ;

(c)

V computes its pairwise key as $k_{vu}:k_{vu}=f(k_{\mathrm{4}},k{v}_{m_{\mathrm{4}}})$ .

After their pairwise keys have been established, the nodes will delete all the predistribution messages.

5. Performance Analysis

In this section, we will give detail performance analyses on our key distribution scheme. We have described that Bechkit et al. proposed a hash-based mechanism (HC) to improve the q-composite scheme and the combinatorial design version of the key predistribution scheme. The authors claimed that HC was a hash-chain based approach, but in fact it was a technique that applies a hash function multiple times on the shared keys between neighboring nodes. That is, their hash-based mechanism is totally different from our method which applies the hash chains as Figure 1 shows. In a HC based key predistribution scheme, each node has to compute a large number of hash values in order to establish the shared keys with its neighboring nodes. HC definitely strengthens the sensor network's ability against node capture attacks, but it increases some amount of computation cost and energy consumption. Since a HC based key predistribution scheme just adds many hash operations, we will not consider the two HC based key predistribution schemes HC (q-composite) and HC (SBIBD) described in [13] but the original q-composite scheme in our following discussions.

5.1. Network Simulation Parameters

To analyze the performance of our DKH-KD scheme, we will compare it with the q-composite scheme and the Dai scheme.

The Dai scheme constructed the node pairwise key by using the deployment knowledge and a polynomial pool, while the q-composite scheme is an improved scheme based on the E-G scheme, where the neighbor nodes can construct their pairwise keys if and only if they have at least q common predistribution secret key.

The following are our network simulation parameters.

• (1)

The cell scale is $M\times N$ , $M=N=\mathrm{10}$ , the length of the side is $d=\mathrm{100}\hspace{0.17em}\text{m}$ .

(2)

The network node number is set to be $S_w=\mathrm{10000}$ .

(3)

In the Dai scheme and the q-composite scheme, the key pool size is $\left|S\right|=\mathrm{100000}$ , the secret key shared factors in the Dai scheme are $\lambda =a=b=\mathrm{0.125}$ , and the polynomial's degree is $t=\mathrm{24}$ .

5.2. Probability of the Local Connectivity

Theorem 4.

In DKH-KD scheme, all the neighbor nodes in the network can establish their pairwise keys; that is, the probability that the neighbor nodes in the network can successfully establish their pairwise keys is 1.

Proof.

(1) According to the node key predistribution algorithm given in Section 4.3, we know that the neighbor nodes’ pairwise keys in the same cell are constructed by using the hash values in the same pair of the reverse hash chains, and each node in the network stores the hash values of a pair of reverse hash chains. Hence, the neighbor nodes in the same cell can establish their pairwise keys as long as they are, respectively, within their counterparts’ emission radius; that is, the probability that any two neighbor nodes in the same cell will establish the pairwise key is 1.

(2) As described in Section 4.3, the neighbor nodes’ pairwise keys in the adjacent cells are established by using the hash values in a pair of special hash chains.

Let $cel{l}_a$ and $cel{l}_b$ be two adjacent cells, then such a pair of the special hash chains can be constructed as Figure 5 shows. The hash chain $C_{\mathrm{1}}^{\prime }$ in $cel{l}_b$ is constructed by using the $GetHash$ function from the hash chain $C_{\mathrm{1}}$ in   $cel{l}_a$ , while the hash chain $C_{\mathrm{2}}^{\prime }$ in $cel{l}_a$ is constructed by using $GetHash$ function from the hash chain $C_{\mathrm{2}}$ in $cel{l}_b$ . Hence, their pairwise keys of the neighbor nodes in the adjacent cells can be generated by the stored hash values of the hash chains   $\{C_{\mathrm{1}},C_{\mathrm{2}}^{\prime }\}$ and the hash chains $\{C_{\mathrm{1}}^{\prime },C_{\mathrm{2}}\}$ , respectively. Therefore, the probability that any two neighboring nodes in the adjacent cells will establish their pairwise keys is also 1.

To sum up, any two neighboring nodes can construct their pairwise keys, that is, the network local connectivity's probability is 1. This completes the proof.

Figure 5

Hash chains that applied in the adjacent cells.

In DKH-KD scheme, each node will delete all the distributed information except the stored neighbor nodes’ pairwise keys and the messages of two pairs of the hash chains as soon as the nodes complete the establishment of the pairwise keys. Hence, the number of the pairwise keys stored in a node is equal to the number of the neighbor nodes plus 4.

Here, we will evaluate the local connection probability based on the average number of the pairwise keys stored in a node. For the convenience of our analysis, we assume that, after the nodes have been deployed, the average number of the neighbor nodes of a node is ${\bar{N}}_{nb}=((\pi \times R^{\mathrm{2}})/(M\times N\times d^{\mathrm{2}}))\times S_w$ . That is, the number of the average pairwise keys stored in a node is ${\bar{N}}_{nb}+\mathrm{4}$ because a node still stores a pair of hash message (the hash value and its subscript) when all the pairwise keys have been established and the related messages have been deleted, while the corresponding average number of the polynomials stored in a node in the Dai scheme is $m={\bar{N}}_{nb}/(t+\mathrm{1})$ with t the degree of the adopted polynomials. When the deploy area and the cell scale are determined, the average number of the pairwise keys stored in a node is proportional to the square of the emission radius. For the three schemes DKH-KD, Dai, and q-composite, Figure 6 shows that their node's local connection probability when their node emission radiuses are different but their average numbers of their stored pairwise keys are the same. When the emission radius is fixed, and the nodes storage space consumption of the Dai and the q-composite schemes are the same, the network node local connectivity probability in our DKH-KD is higher than that of the Dai scheme and the q-composite scheme. For example, if $R=\mathrm{50}\hspace{0.17em}\text{m}$ , then, for $q=\mathrm{1,2},\mathrm{3}$ , the local connection probability in the q-composite scheme are 0.065, 0.0018, and $\mathrm{3.6}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{5}}$ , respectively, while the local connection probability in the Dai scheme is 0.081. If $R=\mathrm{100}\hspace{0.17em}\text{m}$ , then, for $q=\mathrm{1,2},\mathrm{3}$ , the local connection probability in the q-composite scheme are 0.6281, 0.259, and 0.0772, respectively, while the local connection probability in the Dai scheme achieves the maximum value 0.4483. But in our DKH-KD, no matter how long the emission radius is, the local connectivity probability can reach to 1.

Figure 6

Local connectivity probability under different radiuses.

5.3. Security Analysis

Theorem 5.

In DKH-KD scheme, if no nodes are captured within a short time $T_{min}$ , then the initial node keys will be impregnable in theory; that is, the probability that the network link will be broken is close to 0.

Proof.

(1) Within the same cell, the pairwise keys stored in the neighbor nodes are constructed through a pair of reverse hash chain values and they will not be exposed if some nodes are captured. In addition, the irreversibility of our used hash functions also ensures that the capture of some nodes will not break the network connectivity. The reasons are as follows. First, our scheme is proposed based on a supposition that the nodes will not been physically captured within the time $T_{\min }$ as they are deployed in the network, and it means that the hash values in the nodes will not be exposed as the nodes are establishing the pairwise keys. Second, after the nodes delete the predistribution messages, the stored two hash values in the nodes are different from the hash values of the hash chains used for the establishment of the initial pairwise keys. Hence, the other neighbor nodes can know at most one hash chain's hash values; that is, it is impossible for an adversary to obtain the hash values shared by any two neighboring nodes. In addition, the properties of the reverse hash chains make it clear that the exposure of one hash value will not affect the security of the other keys.

(2) Within the adjacent cells, the capture of some nodes will also not destroy the network connectivity. This is because of the following three reasons. (1) In any two adjacent cells, there certainly exist two hash chains as shown in Figure 5, and it can still ensure the remaining node network link's security if some nodes have been physically captured because the adversary cannot simultaneously obtain two hash values of a pair of hash chains. (2) After the nodes have constructed the key relative information, they delete all the predistribution messages (by the off-line server) including the subscript message of the first hash values of the hash chains. Hence, based on the supposition that no nodes will be physically captured in the time $T_{\min }$ and on the pairwise key establishment method given in Section 4.3, an adversary cannot obtain the hash values stored in the neighbor nodes because he does not know the subscript information of the first hash values, even if some nodes are exposed later.

To sum up, our DKH-KD scheme is theoretically secure. That is, when some nodes in the adjacent cells are physically captured, the probability that the network link will be broken is close to 0. This completes the proof of Theorem 5.

Figure 7 shows the probability that the network link is broken with the number of the captured nodes for the three schemes DKH-KD, Dai, and q-composite when $R=80$  m. When the number of the captured nodes is about 1000, the broken probability of the q-composite scheme with $q=1$ , 2, 3 is 0.9338, 0.9008, and 0.8658, respectively, while that of the Dai scheme is close to 0. When the number of the captured nodes is about 5700, the network link of the q-composite scheme will certainly be broken, while the broken probability of the Dai scheme is 0.0867, but that of our DKH-KD scheme is always equal to 0. Figure 7 also shows that with the number of the captured nodes becoming larger, the broken probability of the q-composite scheme becomes closer to 1, while that of the Dai scheme becomes greater, but that of our DKH-KD scheme remains close to 0. That is, our DKH-KD scheme is superior to both the q-composite scheme and the Dai scheme in security.

Figure 7

The probability of the network link broken to the captured node number at $R=80$  m.

5.4. Storage Analysis

In the early period of the deployment, the number of the key relative messages distributed by the off-line server for a node is related to the position of the $cell$ to which the node belongs. The more the hash chains in a $cell$ , the more the key relative messages stored in the nodes belonging to this $cell$ . Table 1 shows that a hash chain needs to store 7 key relative messages (each key-value pair $V_{〈r,s,t〉(k)}$ includes 2 messages), and so a node in the network's initial phase needs to store $\mathrm{7}x$ key relative messages, where x denotes the number of the hash chains in a node, such as $x=\mathrm{3},\mathrm{4},\mathrm{5},\mathrm{6}$ or 8 as in Figure 4. Since the nodes will delete some key messages after their pairwise keys are established, the number of the key messages stored in the nodes is variable before and after the establishing of their pairwise keys. While in the Dai scheme or the q-composite scheme, the number of the keys stored in the nodes is predetermined since they have no message deleting steps. Below we will analyze the node storage messages about our scheme, the Dai scheme, and the q-composite scheme.

After their pairwise keys have been established, the actual number of the keys (pairwise keys) stored in one node is equal to its neighbor node number plus 2 hash values and their subscripts, while a node's neighbor node number is related to its emission radius. Table 2 shows the average number (denoted as K) of the keys stored in one node in our DKH-KD scheme at different emission radiuses (denoted as R) in meter. Table 3 shows the number of the keys stored in a node in the schemes Dai and q-composite at different local connection probabilities for $R=40$  m.

Table 2

Average number of the keys stored in a node in DKH-KD under different radius R.

R	20	40	60	80	100
K	13	50	113	201	314

Table 3

The number of the keys stored in a node in Dai and q-composite under different local connection probabilities with R = 40 m.

Scheme		Local connection probabilities
		0.15	0.31	0.54	0.69
Dai		79	129	204	279
q-composite	q = 1	118	183	269	332
	q = 2	252	334	>400	>400

As Tables 2 and 3 show, when the local connection probability is 0.15 or 0.69, then the number of the keys stored in a node in the Dai scheme is 19 or 279, respectively. While the number of the keys stored in a node in the q-composite scheme are 118 for $q=1$ or 252 for $q=2$ and 332 for $q=1$ or an integer bigger than 400 for $q=2$ , respectively. For $R=100$  m, then the number of the keys stored in a node in the Dai scheme or in the q-composite scheme is the same as that for $R=40$  m, while the number of the keys stored in a node in our DKH-KD is 314. The keys stored in our DKH-KD are more than that stored in the Dai scheme or in the q-composite scheme, but the local connection probability remains 1, which shows that in our DKH-KD, every node can establish the pairwise keys with its neighbor nodes, while both the Dai scheme and the q-composite scheme cannot ensure that their local connection probabilities remain 1. In DKH-KD scheme, the node ultimately only stores the established pairwise keys except for the four key relative messages and has almost no redundant key information. But both the Dai scheme and the q-composite scheme do not delete any key relative information.

In summary, our DKH-KD scheme has some advantages over both the Dai scheme and the q-composite scheme in the storage space.

5.5. Energy Consumption Analysis

The security of our DKH-KD scheme is based on the irreversibility of our used hash chains. The establishment of the nodes’ pairwise keys is completed by computing the hash values many times. Hence, the average number of computing the hash values for the hash function will be a measure for the node's energy consumption.

According to the key distribution algorithm and the structure of the hash chains, the same values in the hash chain can be used only once. Hence, between the two hash values in the same chain, the number of computing the hash values can be counted as in the following.

Let n be the length of the hash chain, then the probability that a hash value is selected is $\mathrm{1}/n$ , and the number of computing the hash values in a chain is 1 to $n-\mathrm{1}$ . Because every value of the hash chain can be used only once, the probability that the other hash value is selected is $\mathrm{1}/(n-\mathrm{1})$ if a value in a hash chain is selected. Hence, the probability that executing the hash functions i times is $i(n-i)/n(n-\mathrm{1})$ . Therefore, the average number T of executing the hash function between two hash values is

$$\begin{array}{cc}& T={\displaystyle \sum }_{i=\mathrm{1}}^{n-\mathrm{1}}\frac{i(n-i)}{n(n-\mathrm{1})}=\frac{\mathrm{1}}{n(n-\mathrm{1})}{\displaystyle \sum }_{i=\mathrm{1}}^{n-\mathrm{1}}i(n-i)=\frac{n+\mathrm{1}}{\mathrm{6}}.\end{array}$$

(5)

Because any two hash chains between the adjacent $cell\text{s}$ are established by the $GetHash$ function through two different hash functions, respectively, but the last value of one hash is the input seed of the other hash chain. Hence, we can regard the two hash chains as a hash chain with the length $\mathrm{2}n$ . Let $T_{\mathrm{1}}$ denote the average number of executing the hash functions of the adjacent nodes in the same $cell$ , and let $T_{\mathrm{2}}$ denote the average number of executing the hash functions of the adjacent nodes in the adjacent $cell$ ; then $T_{\mathrm{1}}=(n+\mathrm{1})/\mathrm{6}$ , $T_{\mathrm{2}}=(\mathrm{2}n+\mathrm{1})/\mathrm{6}$ . Thus, the average number $\text{NF}$ of one node's executing the hash functions is proportional to $(T_{\mathrm{1}}+T_{\mathrm{2}})/\mathrm{2}=(\mathrm{3}n+\mathrm{2})/\mathrm{12}$ . Since the number of the nodes in a $cell$ is related to the emission radius, $\text{NF}$ is related to the emission radius and the length of the hash chains.

Figure 8 shows the relationship of the average number $\text{NF}$ to the length n of the used hash chains and the different emission radiuses R.

Figure 8

The average times of executing hash functions under different hash chain lengths.

As shown in Figure 8, if the emission radius R is a definite value, then $\text{NF}$ is proportional to the length n of the hash chain. Because in our scheme, the length n of the hash chains in a $cell$ is set to be equal to the number of the nodes in the $cell$ (generally, the length of the hash chains is proportional to the number of the nodes in the $cell$ ), it can lower the value of $\text{NF}$ by reducing the number of the nodes in the $cell$ . For example, if $R=\mathrm{40}\hspace{0.17em}\text{m}$ and $n=\mathrm{53}$ , then $\text{NF}=\mathrm{241}$ , and if $n=\mathrm{29}$ , then $\text{NF}=\mathrm{73}$ . Based on the following two facts, our DKH-KD scheme is efficient in energy consumption for the pairwise key establishment in WSNs.

(1) On one hand, if the emission radius of the nodes becomes shorter, then the number of the adjacent nodes will become less and the value of $\text{NF}$ will also become smaller. Table 4 shows that the average number of the node's neighbor nodes with the different lengths n of the hash chain and the different emission radius R. In general, there are 20 to 30 neighbor nodes for a node in WSNs. For example, when $n=\mathrm{89}$ and $R=\mathrm{80}$  m, the average number of the neighbor nodes is 178.95, while in practical applications, such cases are relatively rare. But in the practical deployment phase, the average number of the neighbor nodes can be appropriately adjusted by altering the emission radius and the length of the hash chain. That is, the value of $\text{NF}$ can also be controlled by the emission radius and the length of the hash chain.

Table 4

The number of the node's neighbors under the different hash chain lengths and the different launch radius R.

Number of node's neighbors
	$n=\mathrm{5}$	$n=\mathrm{17}$	$n=\mathrm{29}$	$n=\mathrm{41}$	$n=\mathrm{53}$	$n=\mathrm{65}$	$n=\mathrm{77}$	$n=\mathrm{89}$
$$R=\mathrm{20}$$	0.63	2.12	3.6	5.15	6.67	8.17	9.68	11.18
$$R=\mathrm{40}$$	2.51	8.56	14.58	20.61	26.64	32.67	38.70	44.734
$$R=\mathrm{60}$$	5.65	19.23	32.80	46.37	59.94	73.51	87.08	100.66
$$R=\mathrm{80}$$	10.05	34.18	58.31	82.44	106.56	130.69	154.82	178.95

(2) On the other hand, the energy consumption for executing the hash function once is very low. We take CrossBow node and Ember node as the nodes for our discussion. They will, respectively, consume 154 μJ and 75 μJ to execute a SHA-1 function once [14]. If $R=\mathrm{40}$  m, $n=\mathrm{53}$ , and $\text{NF}=\mathrm{241}$ , then the nodes CrossBow and Ember will consume 37.1 mJ and 18.0 mJ to establish their pairwise keys, respectively.

6. Conclusion

For the security consideration, the node's key management plays a critical part in wireless sensor networks. This paper proposes pairwise key distribution schemes (DKH-KD) based on deployment knowledge and hash chains. We analyze in detail the performance of our scheme in its local connectivity, security, storage, and energy consumption, and it shows that our DKH-KD scheme can be realized with the local connection probability reaching to 1 and the nodes’ security can been significantly improved. Compared with the Dai scheme and the q-composite scheme, our scheme has certain advantages in the local connected probability, security, and storage capacity. But if some nodes in the network are physically captured during a short time period $T_{\min }$ as they are deployed, then our key distribution scheme will be faced with the security threatening that some key messages may be exposed.

In 2012, Stevens introduced that he implemented a differential path attack which is considered to be the most efficient attack against SHA-1 [15]. He claimed that he had a fully working near-collision attack against full SHA-1 working with an estimated complexity equivalent to $2^{57.5}$ SHA-1 compressions. SHA-2 is the successor of SHA-1 and has four kinds of hash functions: SHA224, SHA256, SHA384, and SHA512. Although SHA-2 is similar to SHA-1 in their structures, but until recently those attacks against SHA-1 have not been successfully extended to SHA-2. Compared with SHA-1, SHA-2 will consume some more energy in the hardware implementation [16]. Now, a lot of work has been done to optimize the hardware implementation of SHA-2 and SHA-3 on the resource-constrained hardware platforms [17–21]. For example, when computing a message digest by a SHA-2, the energy consumption is always below 5 μJ per message block [18]. These results can be applied to provide higher security levels for both servers and mobile devices, such as the wireless sensor nodes, which require high-speed and low-energy implementations. Thus, to reduce the energy consumption, we can employ SHA-2 or SHA-3 to construct the hash chains for our DKH-KD scheme.