A secret key establishment protocol for wireless networks using noisy channels

Abstract

An efficient protocol for establishing secret keys for neighboring nodes in a wireless network is presented in this paper. The security of the key generated by our protocol is based on the unpredictability of the noises in binary symmetric communication channels. The two nodes which try to establish a common secret key receive messages from a common source of random bit strings. Due to noises in the communication channel, the messages received by them, and most importantly the messages received by the eavesdropper, are not the same. We show that the two nodes can modify their messages in an efficient way to obtain a common string which contains enough uncertainty to the eavesdropper. Then, a secure universal hash function is applied to compute a secret key for extracting randomness from the common string. We prove that the probability for the eavesdropper to know the value of the key is negligible. One advantage of our proposed protocol is that the secret key rate is better than the known scheme in other models, such as the bounded storage model. Furthermore, our proposed protocol needs only to perform exclusive-or operations and compute hash values. Thus, it is a computationally light-weight protocol and suitable for devices with limited computing resources, such as sensors in sensor networks.

Keywords

Key agreement light-weight protocol wireless network random noise binary symmetric channel

1. Introduction

Security is an important issue in many applications of wireless networks. Plain data sent through public channels are vulnerable to attacks. Many techniques can be applied to protect sensitive data in the communication. Private secure communication channels are usually very expensive. A more practical method is to use encryption. Thus, encryption has become an essential tool to protect data in public communication channels. In this paper, we design a light-weight protocol for any pair of nearby nodes in a wireless network to establish a secret key for secure communication.

A wireless sensor network consists of a set of sensor nodes. Each sensor node has a set of devices for sensing and collecting data and a small antenna for transmitting collected data to other nodes in the network. In most cases, each sensor node has only limited computing power and limited storage. Therefore, in the design of protocols for a sensor network, light-weight computation is very important. One way to establish a secret key for secure communication is to pre-deploy a subset of secret keys selected from a given key pool to each sensor node. Two sensor nodes can establish a key in the field if the intersection of their pre-stored keys is not empty. However, in order to ensure non-empty intersection between any pair of sensor nodes, the number of pre-stored keys in each node cannot be too small, especially when the number of sensor nodes is large. This will cause problem for sensors with small amount of memory.

Our proposed protocol does not need to pre-store a set of keys. Instead, we use unpredictable noises in the communication channel as the main ingredient of security. Due to noises in the communication channel, the messages received by the communicating sensor nodes, and most importantly the message received by the eavesdropper, are unlikely the same. We design an efficient method for sensor nodes to adjust their received messages so that the adjusted messages are the same with very high probability. An eavesdropper can also adjust his received messages. However, we show that an eavesdropper must have uncertainty on the messages agreed by the sensor nodes. Therefore, the eavesdropper does not have enough information to compute the secret key. The security of our protocol does not depend on how much computing power the eavesdropper can use.

In the security analysis of our protocol, we apply Chernoff bounds and other techniques to derive an upper bound for the number of correct bits computed by the eavesdropper. We formally show that, with suitable selection of parameters, the eavesdropper does not have enough information to deduce the value of the secret key established by two sensor nodes. Thus, the established key shared by two sensor nodes is secure against the eavesdropper except leaking negligible amount of information about the secret key.

This paper is organized as follows. In Section 2, we survey related works. Our protocol is described in Section 3. Section 4 is devoted to the security analysis of our protocol. Section 5 shows how to select parameters in our protocol so that the protocol can be executed efficiently and securely. Section 6 shows the simulation result of our protocol. Finally, conclusions are given in Section 7.

2. Related works

There are two commonly used types of schemes for establishing secret key among sensor nodes. The first type is to pre-store a set of keys selected from a key pool. The other type is to compute the secret key by using the same random source. For the first type, a set of keys need to be pre-distributed in the sensor nodes before they are deployed. For the second type, a random source must be accessible by the two parties.

For the pre-deployment of keys, Eschenauer and Gligor proposed a method to assign a random subset of the keys to each sensor node. They proved that two neighboring sensor nodes can establish a shared key from their own key pools with very high probability [10]. Liu and Ning improved the basic random key pre-distribution scheme of Eschenauer and Gligor by using multiple random key pools for each sensor node [15]. Ren et al. discussed how to pre-distribute keys in large scale [19]. Miller and Vaidya proposed a key pre-distribution scheme which assumes that the communication channels between sensor nodes use the orthogonal frequency-division multiplexing technology [17]. Sensors with pre-stored keys have some drawbacks. For example, when the number of sensors is large, to ensure that each pair of sensors can share nonempty set of keys, the number of keys pre-stored in each sensor cannot be too small.

Secret keys can also be established after these sensor nodes were deployed. Tsai, Tzeng, and Zhou proposed a key establishment scheme for wireless sensor network in the bounded storage model [20]. Their first scheme requires special beacon node for broadcasting random bits. In their second scheme, some sensor nodes play the role of beacon nodes. The security of this model is based on that the random bits are too large to store in any available device which has only limited storage. For the purpose of establishing a secret key with high probability, each sensor node needs to store $2 \sqrt{k α}$ bits to ensure that they have at least k bits in common, where k is the security parameter and α is the length of the public random string. For $k = 128$ bits and $α = 10^{15}$ bits, the number of established secret key bit per broadcast random bit (secret key bit rate) of their scheme is $k / 2 \sqrt{k α} = 1.6 \times 10^{- 8}$ , which is very small. Our protocol can achieve secret key bit rate 0.0105 under the condition $p = 0.01$ , where p is bit error probability.

Noisy channel plays an important role in cryptography. Crepeau and Kilian presented some general techniques for establishing cryptographic strength of a wide variety of games. They showed that a noisy telephone line is in fact a very sophisticated cryptographic device [8]. Claude Crepeau proposed bit commitment and oblivious transfer schemes based on binary symmetric channels [7]. Crepeau, Morozov, and Wolf proposed an oblivious transfer scheme from almost any Noisy Channel [9]. Imai, Morozov, and Nascimento computed the OT capacity of the erasure channel for semi-honest adversary. For the malicious adversary, they gave its lower bound [12]. Palmieri and Pereira proposed an OT protocol based on channel delays only [18]. Cheong and Miyaji improved the scheme of Palmieri and Pereira to obtain an OT protocol in the malicious model [6].

Noisy channel can also be used to establish a common secret key. Wyner showed that the noise in the communication channel can be used to provide security in message transmission [23]. Ahmadi and Safavi-Naini focused on secret key capacity [2]. However, their model assumed that the eavesdropper has a binary symmetric channel with probability $p_{2}$ , which is different from the channel use by Alice and Bob. Alice and Bob communicate via a binary symmetric channel with error probability $p_{1}$ and $p_{1} < p_{2}$ . For the case $p_{1} ⩾ p_{2}$ , only some special cases work. That is, at least one of the inverse DMBC’s is in favor of Alice and Bob. A Discrete Memoryless Broadcast Channel (DMBC) $(X, Y, Z, P_{Y Z | X})$ is a channel that, for an input symbol x, returns two output symbols y and z according to the distribution $P_{Y Z | X}$ . Its corresponding inverse DMBC is $(Y, X, Z, P_{X Z | Y})$ where $P_{X Z | Y}$ is calculated as $P_{X Z | Y} = (P_{X} \cdot P_{Y Z | X}) / P_{Y}$ and $P_{Y} = \sum_{x, z} P_{X} \cdot P_{Y Z | X}$ . Therefore, the channel for the eavesdropper is a degraded version of Alice and Bob.

Mathur et al. proposed a method for two nodes to extract a secret key from a wireless channel [16]. Their protocol requires that the bit error probability $p_{e}$ to be extremely low, so that the probability $p_{k}$ that the key generated by the two parties does not match is acceptably small. For example, assuming key length is 128 bits long, in order to have a key-mismatch probability of $p_{k} = 10^{- 6}$ their bit-error probability $p_{e}$ is at most $10^{- 8}$ . Our scheme only requires p with $0.001 ⩽ p ⩽ 0.02$ , which is more realistic than their scheme. Their protocol also requires that the eavesdropper is more than $λ / 2$ away from both Alice and Bob so that the eavesdropper experiences the fading channel effect, where Alice and Bob are statistically independent of the fading, where λ is the wavelength [16]. In our scheme, the eavesdropper may have the same ability as Alice and Bob’s. We do not have extra restriction on the eavesdropper.

There were several schemes exploited physical properties of channels for establishing secret keys [3,4,11,14,22]. Mathur et al. proposed a protocol that allows two parties to establish a common cryptographic key by exploiting special properties of the channel: the underlying channel response between any two parties is unique and de-correlates rapidly in space [16]. For our scheme, the amount of uncertainty is from the noises over a public radio link. For 4G service at 1 gigabit per second with $4 \times 4$ transmit diversity under EVA 5 HZ channel at SNR of 17 dB [21], it corresponds to bit error rate $p = 10^{- 6}$ and each bit can generate $1.00002 \times 10^{- 6}$ entropy bits, so the amount of uncertainty is $0.000001 \times 10^{9} = 10^{3}$ bits per second.

Our protocol exploits the noisy property of channels. We assume that the eavesdropper uses a binary symmetric channel with the same error probability p, rather than a degraded one. Even the eavesdropper uses a degraded channel, our protocol still works. In fact, it is easier for the sensor nodes to collect common strings with enough uncertainty against the eavesdropper in a degraded channel.

We do not study how random messages are sent and received by the two parties to obtain the random bits. There are methods to do proper channel estimation to obtain “good” random bit strings [13].

3. The protocol

Consider the scenario that a set of sensor nodes are deployed in a field randomly. Each sensor node has no post-deployment knowledge about the other sensor nodes. All they can do is to communicate with its neighboring sensor nodes via their antennas.

In the application level of a computer communication network, it is generally required that a receiver can receive all messages in the communication without errors. However, errors may occur in the lower level of real-world communication systems. Noises and other factors often make message communication less reliable. An error correction code or even re-sending some parts of a long message is required to make sure that the received message is intact.

While in transmission of messages we try to reduce errors, in the secret key establishment, we use errors to derive secret key so that the eavesdropper cannot obtain the information about the secret key. Thus, we need raw data in the noisy communication channel. Nevertheless, this is required only in the first step of our protocol.

Our protocol assumes that the broadcast channel is a binary symmetric channel. The raw data bits received by a sensor node may be different from the broadcast bits. In a binary symmetric channel, the probability for a bit 0 to be received as 1 is the same as the probability for a bit 1 to be received as 0. They are both equal to p, $0 < p < 1$ .

Let K denote the secret key to be established by A and B for encryption, such as AES. Let s be the length of the key K. The value of s is usually regarded as the security parameter of the system. For example, the value of s can be 128, 192, or 256 for AES cryptosystem.

Fig. 1.

Basic steps of the protocol.

Our protocol is shown in Figs 1 and 2. Figure 1 contains the basic steps of establishing a common string of m bits between A and B. Figure 2 is the main protocol of computing K from r common m-bit strings between A and B.

In the basic steps (Fig. 1), A and B receive broadcast random bits by the same beacon node at the same time. Let the m bits received by A be $x_{1} x_{2} \dots x_{m}$ and the m bits received by B be $y_{1} y_{2} \dots y_{m}$ . Next, they compute pairwise parity bits for the received random bit stream. That is, A computes $z_{1} z_{2} \dots z_{m / 2}$ and B also computes $z_{1}^{'} z_{2}^{'} \dots z_{m / 2}^{'}$ , where $z_{i} = x_{2 i - 1} \oplus x_{2 i}$ and $z_{i}^{'} = y_{2 i - 1} \oplus y_{2 i}$ . A sends parity bits $z_{1} z_{2} \dots z_{m / 2}$ to B in a clear channel. Having received the parity bits from A, B compares them with his parity bits and tells A which parity bits are different. For each unmatched parity bit, B resets the corresponding two bits to 00. A also resets the corresponding two bits to 00. The unmatched bits can be discarded or set to any fixed value. After the basic steps, A and B have a common string of m bits with high probability.

Fig. 2.

The main protocol.

Step 1 in the main protocol, shown in Fig. 2, repeatedly executes the basic steps in Fig. 1 r times to establish a common bit string of $m r$ bits (r common m-bit strings). A and B apply a cryptographically strong hash function g to check whether their common string is the same or not. Finally, they apply a universal hash function f to extract a secret key.

Note that, in the basic steps of our protocol, if $z_{1} z_{2} \dots z_{m / 2} = z_{1}^{'} z_{2}^{'} \dots z_{m / 2}^{'}$ , we conclude that the two sequences $x_{1}, x_{2}, \dots, x_{m}$ and $y_{1}, y_{2}, \dots, y_{m}$ are equal with very high probability. Nevertheless, there is a very small probability for the two strings to be different. For security reasons, the protocol does not check if they are equal or not in the basic steps. The checking will be done by using a cryptographic hash function g (in Steps 2 and 3 of the main protocol) after A and B collect r such strings.

In the last step of the protocol, a universal hash function f is applied to their common bit string to extract randomness for the shared secret key K. The universal hash function f, from $Z_{2}^{m r}$ to $Z_{2}^{s}$ , is randomly selected from the universal class of hash family.

4. Analysis of the protocol

Let T be the number of times that the full protocol in Fig. 2 is executed until the common secret key K is established. The following theorem gives the expected value of T.

Theorem 1.
Let T be the random variable for the number of times executed until sensor nodes A and B successfully establish a common string of length $m r$ in the protocol. Then the expected value of T is $1 / ({(1 - 4 p^{2} {(1 - p)}^{2})}^{m r / 2})$ .
Proof.
Since the bit-flip probability is p, the probability that the two bits of A and B are different is $q = 2 p (1 - p)$ . The only case that $z_{i}$ is correct but $x_{i - 1} x_{i}$ and $y_{i - 1} y_{i}$ are different is that both bits $x_{i - 1} x_{i}$ (or $y_{i - 1} y_{i}$ ) are flipped. The probability that these two bits are flipped is $q^{2}$ . Since there are m bits at each run, the probability that the $m r$ bits that A received are the same with B’s is ${(1 - q^{2})}^{m r / 2}$ . Let $p^{'} = {(1 - q^{2})}^{m r / 2}$ . We have $Pr [T = t] = p^{'} {(1 - p^{'})}^{t - 1}$ . Hence, $\begin{matrix} E (T) = \sum_{t = 1}^{\infty} t p^{'} {(1 - p^{'})}^{t - 1} = p^{'} \sum_{t = 1}^{\infty} t {(1 - p^{'})}^{t - 1} = \frac{1}{p^{'}} . \end{matrix}$ □

Table 1
The average number T of times required for $m = 320$

$r = 20$ $r = 30$ $r = 40$

$p = 0.010$ 3.51 6.57 12.30

$p = 0.015$ 16.37 66.23 267.99

$p = 0.020$ 137.14 1606.07 18808.42

Table 1 shows the expected number of times T that the whole protocol needs to be executed. This number depends on the common string length m, the number of runs r and the bit-flip probability p. Here we assume that $m = 320$ . The values in Table 1 can be obtained from Theorem 1 for $1 / T = {(1 - 4 p^{2} {(1 - p)}^{2})}^{m r / 2}$ .

Table 2
The communication cost in bits for $m = 320$ and $p = 0.01$

$r = 20$ $r = 30$ $r = 40$

Communication cost 22464 63072 157440

Table 2 shows that our protocol can be executed very fast for $p ⩽ 0.01$ . For example, for $p = 0.01$ , $m = 320$ , $r = 30$ , the total number of communication cost is $m r T = 320 \times 30 \times 6.57 = 63702$ bits. For current WSN with 250 kbits/sec Zigbee, it can be done within 0.25 seconds. Even for $p = 0.02$ , $m = 320$ and $r = 20$ , the total number of communication bits is $m r T = 320 \times 20 \times 137.14 = 877696$ bits, it can be done within 3.5 seconds.

Now we shows that the corresponding m-bit string of the adversary in Fig. 1 is different from A’s and B’s by at least some amount. Since the bit-flip probability is p, the probability that the two bits of A and B are different is $q = 2 p (1 - p)$ . On average, the sensor node B has $m q$ different bits from the sensor A. The adversary also has $m q$ bits different from what the sensor A has on average.

If the ith parity bit of B is different from A’s parity bit, then the eavesdropper knows the value of the corresponding two bits, which will be reset to 00. On the other hand, if the ith parity bits of A and B are equal, and the eavesdropper’s parity bit is different from A’s and B’s, the eavesdropper will know that one of his two eavesdropped bits is correct and the other is incorrect. Nevertheless, he does not know which one is correct and which one is incorrect. He can only guess the correct value of the two bits. With probability $1 / 2$ he can make a correct guess. If the eavesdropper’s parity bit is equal to A and B, then the two eavesdropped bits is the same as A’s and B’s with probability ${(1 - q)}^{2}$ .

Since the probability for the ith parity bit of B being different from A is $2 q (1 - q)$ and the probability for the ith parity bit of B being equal to A is $q^{2} + {(1 - q)}^{2}$ , the probability that the eavesdropper eavesdrops the correct corresponding two bits is $\begin{matrix} 2 q (1 - q) + (q^{2} + {(1 - q)}^{2}) (2 q (1 - q) 1 / 2 + {(1 - q)}^{2}) . \end{matrix}$ Therefore, the eavesdropper has at most $\begin{matrix} l = (2 q (1 - q) + (q^{2} + {(1 - q)}^{2}) (2 q (1 - q) 1 / 2 + {(1 - q)}^{2})) m \end{matrix}$ correct bits for the common m-bit string of A and B on average. We show that the probability that the eavesdropper knows up to $(l / m + ε) m$ bits is negligible, where $0 < l / m + ε < 1$ .
Theorem 2.
Let $C \subset {1, 2, \dots, m}$ be the set of indices of the bits received by the eavesdropper and these bits are the same as A’s and B’s. Then $\begin{matrix} Pr [| C | ⩾ (l / m + ε) m] ⩽ e^{- (l / m) m {(\frac{ε}{l / m})}^{2} / 3} . \end{matrix}$
Proof.
Let $X_{i}$ be the indicator random variable for the ith bit. $X_{i} = 1$ if the eavesdropper gets the correct value for the ith bit and $X_{i} = 0$ , otherwise. $\begin{array}{rcl} Pr [| C | ⩾ (l / m + ε) m] & = & Pr [\sum_{i = 1}^{m} X_{i} ⩾ (l / m + ε) m] \\ = & Pr [\sum_{i = 1}^{m} X_{i} ⩾ (l / m) m (1 + \frac{ε}{l / m})] ⩽ e^{- (l / m) m {(\frac{ε}{l / m})}^{2} / 3} . \end{array}$ □

In the proof of the above theorem, we use the Chernoff bound to show that the probability that the adversary obtains information by a certain amount on average is very small. The Chernoff bound can be described as follows. Let $X_{i}$ be a set of independent and identically distributed random Boolean variables with $E (X_{i}) = θ$ , $1 ⩽ i ⩽ t$ . Then, almost all values of $\sum_{i = 1}^{t} X_{i}$ are around its mean $\begin{matrix} E (\sum_{i = 1}^{t} X_{i}) = t θ . \end{matrix}$ More precisely, for any $0 < ε ⩽ 1$ , $\begin{matrix} Pr [\sum_{i = 1}^{t} X_{i} ⩾ (1 + ε) t θ] ⩽ e^{- t θ ε^{2} / 3} . \end{matrix}$

The next theorem estimates the amount of uncertainty about the corresponding two bits $x_{2 k - 1} x_{2 k}$ when the eavesdropper has his own parity bits $z_{k}^{″}$ and sensor node A’s parity bits are $z_{k}$ , $1 ⩽ k ⩽ m / 2$ .
Theorem 3.
Let $S = {00, 01, 10, 11}$ . $X \in S$ is a random variable for the two bits corresponding to the parity bit $z_{k}$ . Then, the eavesdropper has uncertainty $\begin{matrix} (3 q^{2} - 3 q + 1) (\frac{{(1 - p)}^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{{(1 - p)}^{2}} + \frac{p^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{p^{2}}) + q (1 - q) \end{matrix}$ for X, where $q = 2 p (1 - p)$ .
Proof.
Let Y be the random variable such that
$Y = 0$ if the eavesdropper’s parity bit $z_{k}^{″}$ is not equal to A’s parity bit $z_{k}$ ,

$Y = 1$ if the eavesdropper’s parity bit is equal to $z_{k}$ , and

$Y = ⊥$ , if A and B have different parity bit.
Then $\begin{array}{rcl} H (X | Y) & = & Pr [Y = 1] H (X | Y = 1) \\ + Pr [Y = 0] H (X | Y = 0) \\ + Pr [Y = ⊥] H (X | Y = ⊥) . \end{array}$ The eavesdropper knows the two bits when A and B have different parity bit because these two bits will be 00. This implies that $\begin{matrix} H (X | Y = ⊥) = 0 . \end{matrix}$ Thus $\begin{matrix} H (X | Y) = Pr [Y = 1] H (X | Y = 1) + Pr [Y = 0] H (X | Y = 0) . \end{matrix}$ We have, $\begin{matrix} Pr [Y = 1] = 3 q^{2} - 3 q + 1, \end{matrix}$ and $\begin{matrix} Pr [Y = 0] = q (1 - q) . \end{matrix}$ Without loss of generality, we assume that the two received bits by the eavesdropper is $X^{'} = 00$ . By the above analysis, we can obtain the following probabilities: For the probability that $x_{2 k - 1} x_{2 k} = 00$ , conditioned on the eavesdropper’s parity bit $z_{k}^{″}$ equal to $z_{k}$ , $\begin{array}{rcl} Pr [X = 00 | Y = 1] & = & \frac{{(1 - p)}^{2} \cdot {(1 - p)}^{2} \cdot ({(1 - p)}^{2} + p^{2})}{{(1 - p)}^{2} \cdot {({(1 - p)}^{2} + p^{2})}^{2}} \\ = & \frac{{(1 - p)}^{2}}{{(1 - p)}^{2} + p^{2}} \end{array}$ For the probability that $x_{2 k - 1} x_{2 k} = 11$ , conditioned on the eavesdropper’s parity bit $z_{k}^{″}$ equal to $z_{k}$ , $\begin{array}{rcl} Pr [X = 11 | Y = 1] & = & \frac{p^{2} \cdot {(1 - p)}^{2} \cdot ({(1 - p)}^{2} + p^{2})}{{(1 - p)}^{2} \cdot {({(1 - p)}^{2} + p^{2})}^{2}} \\ = & \frac{p^{2}}{{(1 - p)}^{2} + p^{2}} \end{array}$ For the probability that $x_{2 k - 1} x_{2 k}$ is 01, conditioned on the eavesdropper’s parity bit $z_{k}^{″}$ not equal to $z_{k}$ , $\begin{matrix} Pr [X = 01 | Y = 0] = \frac{p (1 - p) \cdot {(1 - p)}^{2} \cdot 2 p (1 - p)}{{(1 - p)}^{2} \cdot {(2 p (1 - p))}^{2}} = \frac{1}{2} . \end{matrix}$ For the probability that $x_{2 k - 1} x_{2 k}$ is 10, conditioned on the eavesdropper’s parity bit $z_{k}^{″}$ not equal to $z_{k}$ , $\begin{matrix} Pr [X = 10 | Y = 0] = \frac{p (1 - p) \cdot {(1 - p)}^{2} \cdot 2 p (1 - p)}{{(1 - p)}^{2} \cdot {(2 p (1 - p))}^{2}} = \frac{1}{2} . \end{matrix}$ Thus, $\begin{matrix} H (X | Y = 1) = \frac{{(1 - p)}^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{{(1 - p)}^{2}} + \frac{p^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{p^{2}}, \end{matrix}$ and $\begin{array}{rcl} H (X | Y = 0) = 1 . \end{array}$ This implies that $\begin{array}{rcl} H (X | Y) & = & (3 q^{2} - 3 q + 1) (\frac{{(1 - p)}^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{{(1 - p)}^{2}} \\ + \frac{p^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{p^{2}}) + q (1 - q) \\ = & (3 q^{2} - 3 q + 1) (\frac{{(1 - p)}^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{{(1 - p)}^{2}} \\ + \frac{p^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{p^{2}}) + q (1 - q) . \end{array}$ □

Therefore, the amount of uncertainty to the eavesdropper for a common m-bit string (in Fig. 1) is $h = m H (X | Y) / 2$ . If we have r such common strings, the amount of uncertainty to the eavesdropper is $h r$ .

In the next theorem, with proper parameter setting, we show that the key K established by A and B is s-bit secure against the eavesdropper. Note that $K = f (W)$ is the extracted key from the $m r$ -bit common string W between A and B. W is established in Step 1 of Fig. 2. In proving the next theorem, we need privacy amplification.

Let F be a random variable for a function f randomly chosen from the universal hash family $f : {0, 1}^{n} \to {0, 1}^{s}$ , $s < n$ . It can be shown that
Theorem 4 (Privacy amplification [5]).

	$r = 20$	$r = 30$	$r = 40$
$p = 0.010$	3.51	6.57	12.30
$p = 0.015$	16.37	66.23	267.99
$p = 0.020$	137.14	1606.07	18808.42

	$r = 20$	$r = 30$	$r = 40$
Communication cost	22464	63072	157440

For any $δ > 0$ , for all sufficiently large n, random R and W, W is a common $n = m r$ -bit string with entropy s between A and B, $v = n (H_{b} (p) - δ) - s$ , $\begin{matrix} H (F (W) | {BS}_{p} (R), F) ⩾ s - \frac{2^{- v}}{ln 2} . \end{matrix}$

Theorem 5.
Suppose that A and B have collected a common string which contains s bits of uncertainty to the eavesdropper. Assume that the hash functions f is randomly chosen from a universal hash family. Then, after the protocol, the eavesdropper has almost s bits of uncertainty about the value of key K.
Proof.
Let R be the random variable for the random string broadcast by the beacon node. Let ${BS}_{p} (R)$ be the random variable for the string received by the eavesdropper. W is the agreed $m r$ -bit string between A and B.

Because $H (F (W) | {BS}_{p} (R), F) = s$ means that given ${BS}_{p} (R)$ and F, the eavesdropper almost has s-bit uncertainty about $F (W)$ . The last term is exponentially close to 0.

We cannot use the privacy amplification theorem directly to prove the security for $K = F (W)$ because A has sent the parity bits in the protocol. However, we can apply the theorem with some modification.

For any $δ > 0$ , for all sufficiently large $n = m r$ , for $v^{'} = n (h - δ) - v$ , where $\begin{array}{rcl} h & = & \frac{1}{2} ((3 q^{2} - 3 q + 1) (\frac{{(1 - p)}^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{{(1 - p)}^{2}} \\ + \frac{p^{2}}{{(1 - p)}^{2} + p^{2}} log \frac{{(1 - p)}^{2} + p^{2}}{p^{2}}) + q (1 - q)) \end{array}$ and $q = 2 p (1 - p)$ , the entropy about the key $F (W)$ to the eavesdropper is bounded by $\begin{matrix} H (F (W) | Z, {BS}_{p} (R), F) ⩾ s - \frac{2^{- v^{'}}}{ln 2} \approx s . \end{matrix}$ Note that our hash function f is from $m r$ bits to s bits. □

It can be seen in Theorem 5 that the hash functions f can be public, even to the eavesdropper. The privacy amplification theorem provides a lower bound on the entropy of the hash value $f (W) = K$ under the condition of knowing f and noisy input ${BS}_{p} (R)$ . Although partial information about the common bit string W is known by the eavesdropper, we actually use the hash of the common bit string. By the privacy amplification theorem, the eavesdropper’s information about K is reduced to a very small amount.
5. Selecting parameters

The purpose of the repeated execution of the basic steps in Step 1 of Fig. 2 is to accumulate sufficient uncertain bits against the eavesdropper. The value r should be properly chosen so that the $m r$ -bit common string of A and B will have at least s uncertain bits to the eavesdropper.

Table 3
The entropy of the r m-bit common string to the eavesdropper

Entropy $r = 20$ $r = 30$ $r = 40$

$p = 0.010$ 67 100 134

$p = 0.015$ 101 151 202

$p = 0.020$ 135 203 271

Entropy	$r = 20$	$r = 30$	$r = 40$
$p = 0.010$	67	100	134
$p = 0.015$	101	151	202
$p = 0.020$	135	203	271

Table 3 shows entropy for some possible r and $p = 0.010, 0.015, 0.020$ .

The values in Table 3 can be derived from Theorem 3. First we compute the uncertainty to the eavesdropper for a single run. Then we multiply it by the number of runs r to get the final result.

For example, for $r = 30$ and bit-flip probability $p = 0.01$ , after executing the protocol, the common string will have 100 bits of uncertainty to the eavesdropper. This is the security of the established key K between A and B. In general, for our protocol to run successfully for $s = 160$ , it is always possible to select the parameters for $m = 320$ , when $0.001 ⩽ p < 0.02$ . This shows that our protocol is practical in current technology. For the case that the error rate is very small, i.e. $p < 0.001$ , the two sensor nodes can randomly flip some bits to make the same effect as $p = 0.001$ . It was shown that the possible range for p is from $0.2 %$ to $4 %$ with maximal ratio combining decision feedback equalizer (MRCDFE) [1]. Our choices of p’s are within this range.

6. Simulation

We use programs to simulate the noisy channel and the protocol. Assume that a beacon node broadcasts random bits. The first step is to simulate nodes A and B to receive the random bits broadcast by the beacon node. A, B and the eavesdropper receive each random bits independently with specified error rate p. The second step is to compute the exclusive-or of the bit strings received by A and B. Node A sends the parity bit string to B and B sends back those positions with different parities. Then, A and B compute the key by the steps specified in the protocol.

The simulation program judges whether the protocol succeeds by checking whether the received strings of A and B are the same after adjusting the strings by using the parity bits.

Figure 3 shows the successful rate of the basic step of the protocol for different bit flip probability p, assuming $m = 256$ and 320. The simulation performs 1000 times and the averages are taken. In addition to the results of simulation, theoretical rates are also plotted. The lines $256 t$ and $320 t$ are theoretical results and the lines $256 s$ and $320 s$ are the simulation results. We can see that they agree quite nicely.

Figure 4 is the number of entropy bits for different bit flip probability p, assuming $m = 256, 320$ and $r = 20$ . The theoretical values are also shown in the figure. The lines $256 t$ and $320 t$ are theoretical results and the lines $256 s$ and $320 s$ are the simulation results. They agree quite nicely, too.

Fig. 3.

Simulation results for success rate.

Fig. 4.

Simulation results for entropy bits.

7. Conclusions

We have presented a protocol for two sensor nodes to compute a secret key in a binary symmetric channel in wireless sensor networks. The secrecy of the key is established by using the uncertainty of the messages received by the two sensor nodes and the eavesdropper.

We are able to prove formally that the eavesdropper’s information about the secret key K is negligible. Thus, the key computed by two sensor nodes is secure in the sense that the eavesdropper does not have enough information to compute the secret key. This is different from the computational security of public key systems, such as the Diffie–Hellman key exchange protocol.

We have used the scenario of wireless sensor networks to describe our method. This scenario is one of the possible applications of our method. Any two parties who share a common noisy channel can use our method to establish a secret key. The only setting that needs to be changed is the way the two parties collect the random bit strings.

Footnotes

Acknowledgment

This research is supported in part by the MOST project 104-2221-E-009-112-MY3.

References

Z.K.

Adeyemo and

T.I.

Raji, Bit error rate analysis for wireless links using adaptive combining diversity, Journal of Theoretical and Applied Information Technology 20(1) (2010), 58–65.

Ahmadi and

Safavi-Naini, Secret keys from channel noise, in: Advances in Cryptology: Proceedings of the 30th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2011, Springer-Verlag, Berlin, 2011, pp. 266–283.

Aono,

Higuchi,

Ohira,

Komiyama and

Sasaoka, Wireless secret key generation exploiting reactance-domain scalar response of multipath fading channels, IEEE Transactions on Antennas and Propagation, 53(11) (2005), 3776–3784. doi:10.1109/TAP.2005.858853.

Azimi-Sadjadi,

Kiayias,

Mercado and

Yener, Robust key generation from signal envelopes in wireless networks, in: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS ’07, ACM, New York, NY, USA, 2007, pp. 401–410. doi:10.1145/1315245.1315295.

C.H.

Bennett,

Brassard,

Crepeau and

U.M.

Maurer, Generalized privacy amplification, IEEE Transactions on Information Theory 41(6) (1995), 1915–1923. doi:10.1109/18.476316.

K.-Y.

Cheong and

Miyaji, Unconditionally secure oblivious transfer based on channel delays, in: Proceedings of the 13th International Conference on Information and Communications Security, ICICS 2011, Springer-Verlag, Berlin, 2011, pp. 112–120.

Crépeau, Efficient cryptographic protocols based on noisy channels, in: Advances in Cryptology: Proceedings of the 16th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’97, Springer-Verlag, Berlin, 1997, pp. 306–317.

Crepeau and

Kilian, Achieving oblivious transfer using weakened security assumptions (extended abstract), in: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 42–52.

Crepeau,

Morozov and

Wolf, Efficient unconditional oblivious transfer from almost any noisy channel, in: Proceedings of Fourth Conference on Security in Communication Networks, SCN ’04, Springer-Verlag, 2004, pp. 47–59.

10.

Eschenauer and

V.D.

Gligor, A key-management scheme for distributed sensor networks, in: Proceedings of the 9th ACM Conference on Computer and Communications Security, CCS ’02, ACM, New York, NY, USA, 2002, pp. 41–47.

11.

A.A.

Hassan,

W.E.

Stark,

J.E.

Hershey and

Chennakeshu, Cryptographic key agreement for mobile radio, Digital Signal Processing 6(4) (1996), 207–212. doi:10.1006/dspr.1996.0023.

12.

Imai,

Morozov and

A.C.A.

Nascimento, On the oblivious transfer capacity of the erasure channel, in: 2006 IEEE International Symposium on Information Theory, 2006, pp. 1428–1431. doi:10.1109/ISIT.2006.262082.

13.

Jana,

S.N.

Premnath,

Clark,

S.K.

Kasera,

Patwari and

S.V.

Krishnamurthy, On the effectiveness of secret key extraction from wireless signal strength in real environments, in: Proceedings of the 15th Annual International Conference on Mobile Computing and Networking, MobiCom ’09, ACM, New York, NY, USA, 2009, pp. 321–332.

14.

Koorapaty,

A.A.

Hassan and

Chennakeshu, Secure information transmission for mobile radio, IEEE Communications Letters, 4(2) (2000), 52–55. doi:10.1109/4234.824754.

15.

Liu and

Ning, Establishing pairwise keys in distributed sensor networks, in: Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS ’03, ACM, New York, NY, USA, 2003, pp. 52–61. doi:10.1145/948109.948119.

16.

Mathur,

Trappe,

Mandayam,

Ye and

Reznik, Radio-telepathy: Extracting a secret key from an unauthenticated wireless channel, in: Proceedings of the 14th Annual International Conference on Mobile Computing and Networking, MobiCom ’08, 2008, ACM, New York, NY, USA, pp. 128–139.

17.

M.J.

Miller and

N.H.

Vaidya, Leveraging channel diversity for key establishment in wireless sensor networks, in: Proceedings of the 25th IEEE International Conference on Computer Communications, INFOCOM 2006, 2006, pp. 1–12.

18.

Palmieri and

Pereira, Building oblivious transfer on channel delays, in: Proceedings of the 6th International Conference on Information Security and Cryptology, Inscrypt 2010, Springer-Verlag, Berlin, 2011, pp. 125–138. doi:10.1007/978-3-642-21518-6_10.

19.

Ren,

Zeng and

Lou, A new approach for random key pre-distribution in large-scale wireless sensor networks, Wireless Communication and Mobile Computing 6(3) (2006), 307–318. doi:10.1002/wcm.397.

20.

S.-C.

Tsai,

W.-G.

Tzeng and

K.-Y.

Zhou, Key establishment schemes against storage-bounded adversaries in wireless sensor networks, IEEE Transactions on Wireless Communications 8(3) (2009), 1218–1222. doi:10.1109/TWC.2009.081048.

21.

U.E.

Uyoata and

J.M.

Noras, BER performance of 2x2 and 4x4 transmit diversity MIMO in downlink LTE, International Journal of Computer Applications 108(9) (2014), 23–28. doi:10.5120/18941-9693.

22.

Wilson,

Tse and

R.A.

Scholtz, Channel identification: Secret sharing using reciprocity in ultrawideband channels, IEEE Transactions on Information Forensics and Security 2(3) (2007), 364–375. doi:10.1109/TIFS.2007.902666.

23.

A.D.

Wyner, The wire-tap channel, Bell System Technical Journal 54(8) (1975), 1355–1387. doi:10.1002/j.1538-7305.1975.tb02040.x.