# A Multihop Key Agreement Scheme for Wireless Ad Hoc Networks

Authors: Zhuo Hao; Sheng Zhong; Nenghai Yu
Journal: The Scientific World Journal
 (2013)

---

## Abstract

A number of key agreement schemes based on wireless channel characteristics have been proposed recently. However, previous key agreement schemes require that two nodes which need to agree on a key are within the communication range of each other. Hence, they are not suitable for multihop wireless networks, in which nodes do not always have direct connections with each other. In this paper, we first propose a basic multihop key agreement scheme for wireless ad hoc networks. The proposed basic scheme is resistant to external eavesdroppers. Nevertheless, this basic scheme is not secure when there exist internal eavesdroppers or Man-in-the-Middle (MITM) adversaries. In order to cope with these adversaries, we propose an improved multihop key agreement scheme. We show that the improved scheme is secure against internal eavesdroppers and MITM adversaries in a single path. Both performance analysis and simulation results demonstrate that the improved scheme is efficient. Consequently, the improved key agreement scheme is suitable for multihop wireless ad hoc networks.


---

## Body

## 1. Introduction

Network security (see, e.g., [1, 2]) has been studied extensively. In wireless networks, security problems are especially critical, because wireless channels are inherently broadcast channels. When a pair of nodes communicate with each other, nearby nodes within the communication range may be able to overhear their messages. In order to prevent eavesdropping, messages are often encrypted before being sent. Hence, key agreement is of great importance for security of wireless networks.Recently, Mathur et al. [3] propose a novel key agreement scheme for wireless networks, which is based on the secrecy of the wireless channel itself. In their scheme, the two communicating nodes send probe signals to each other and measure the channels. Then, they extract secret bits from the channel measurements using a level-crossing algorithm. Because of the reciprocity of the channel, the two nodes can extract the same key from their own channel measurements. Any eavesdroppers that are more than half a wavelength away from both nodes can get no knowledge of the key, because their experienced channels are independent of the channel between the two communicating nodes. The broad applicability of this security alternative has been validated by Jana et al. [4], through a series of experiments in real environments.However, both Mathur et al.’s and Jana et al.’s schemes require that two nodes are within the communication range of each other in order to establish a key. This requirement cannot always be satisfied. In many realistic scenarios, intermediate nodes are needed for relaying messages, because the end nodes cannot communicate directly.In this paper, we show that it is feasible to build key agreement schemes based on wireless channel measurements inmultihop wireless networks. We show that, by extracting secrets from the phase characteristics (it is feasible to extract secrets from phase characteristics—please see Section 3 for details) of channels, two end nodes that are more than one hop away from each other can establish a key between them. We propose a basic key agreement scheme for this purpose and show that it is secure against external eavesdroppers (i.e., eavesdroppers out of the paths connecting the two nodes). After that, we show that the basic scheme is subject to internal eavesdropping and Man-in-the-Middle (MITM) attacks. Therefore, we propose an improved key agreement scheme to prevent these two attacks. The improved scheme is based on the assumption that the network is biconnected. The secrets are extracted from two disjoint paths between the two end nodes. The improved scheme is secure against internal eavesdroppers and MITM adversaries in a single path. (Please see Section 5.3, Remark 7 for the possibility that adversaries control more than a single path.) In both the basic and the improved schemes, we follow the standard assumption [3–6] that adversaries are more than half a wavelength away from all the participating nodes. We give a theoretical analysis of the key agreement probability and show that it is affected by communication SNRs, sampling rates, and quantization parameters. We simulate the improved scheme in GlomoSim [7] and show that the established key has strong randomness and the key agreement efficiency is high.In summary, we have the following contributions.(i)
We propose a basic multihop key agreement scheme and prove that it is secure against external eavesdroppers.(ii)
Since the basic scheme is not secure against internal eavesdroppers or MITM adversaries, we propose an improved multihop key agreement scheme, and prove that this improved scheme is secure against internal eavesdroppers and MITM adversaries in a single path between the two nodes.(iii)
We give both performance analysis and simulation results of the improved scheme. The results show that the improved scheme is very efficient and the established key has strong randomness.The rest of this paper is organized as follows. In Section2, we review the related work. In Section 3, we present technical preliminaries. In Section 4, we present the basic multihop key agreement scheme and give a security analysis. In Section 5, we describe the improved multihop key agreement scheme and prove its security. In Sections 6 and 7, we show that the improved scheme is efficient by both theoretical analysis and simulation results. Finally, we conclude in Section 8.


## 2. Related Work

Key agreement based on channel characteristics is firstly proposed in Hershey et al. [8], in which the secret key is extracted from the phase differences of continuous waves. After that, Hassan et al. [9] propose to use phase differences between two orthogonal subcarriers as extracted secrets. Tope and McEachen [10] propose a key generation scheme based on polarity of power envelope differences. Recently, a lot of schemes [3–6, 11–22] are proposed to enhance the security and/or improve the performance. In particular, Mathur et al. [3] propose a scheme to extract secret bits from wireless channel measurements. They design a level-crossing algorithm to increase the bit consistency rate. They do experiments using both customized 802.11 platform and off-the-shelf 802.11 network cards. In order to validate the effectiveness of the key extraction schemes based on signal strengths, Jana et al. [4] carry out extensive experiments in various environments. They propose adaptive quantization method to improve the performance. Patwari et al. [6] propose a high-rate uncorrelated bit extraction scheme based on fractional interpolation, decorrelation transformation and multibit adaptive quantization. Ye et al. [5] propose a secret key extraction approach that is suited for more general channel state distributions. Zhang et al. [21] find that mobility patterns have important impact on the correlation of channel measurements at the end nodes. They show that more diffusion in the mobility brings less correlation in the measured channel impulse responses. Gollakota and Katabi [23] propose a secret communication method based on receiver’s jamming. Their method eliminates the reliance on channel variance and has high secret communication speed.There are also many analytical works [24–27] that provide theoretical analysis of secret key exchange protocols and propose improved algorithms. In addition, secret key extraction schemes from UWB (Ultra-WideBand) channels are proposed in [28–31]. Croft et al. [32] propose a secret bit extraction scheme for wireless sensors, while Ali et al. [33] develop a key extraction approach in body area networks.It is important to note that all the previous  approaches focus on one single channel between two nodes. Therefore, they have the requirement that the two nodes are within the communication range of each other. In contrast, in this paper, we propose schemes that are suitable for multihop networks, in which nodes can be out of the communication range of each other. Consequently, our proposed schemes can be used for key agreement in multihop wireless networks.Recently Wang et al. [34] propose a group key agreement scheme in wireless networks. Wang et al.’s scheme is based on the phase characteristics of wireless channels. They use phase randomness for bit generation and remove the reliance on the node mobility. According to Ren et al. [35], phase-based methods [8, 9, 16, 34] have three advantages compared to RSS-based methods [3–6], including having uniform distribution, providing high resolution phase estimation, and enabling phase accumulation across multiple nodes. Similar to [34], the schemes proposed in this paper are also based on channel phase randomness. However, our proposed schemes consider a completely different setting, in which the involved nodes can be more than one hop away from each other. In fact, allowing nodes to be multiple hops away from each other is a major technical challenge addressed in this paper. Hence, our schemes are independent from, and complementary to, the results in [34].


## 3. Technical Preliminaries

In a typical multihop mobile ad hoc network, there are no infrastructures. Each node is both an end host and a router. Denote the nodes in the network by{N1,N2,…,Na}. If node Ni is within the communication area of Nk, then we say Ni is a neighbor of Nk. Without loss of generality, we assume that wireless channels are symmetric; that is, whenever a node Ni is a neighbor of Nk, Nk is also a neighbor of Ni. Just as in previous work [3, 4], we assume the channel between any two neighboring nodes to be reciprocal. (This assumption implies that our work is most suitable for a homogeneous network. If the network is heterogeneous, then our work needs to be modified before it can be applied.) Denote the channel from Ni to Nk by hik(t), and denote the channel from Nk to Ni by hki(t). Then the channel reciprocity indicates that hik(t)=hki(t) for any time t.We use the phase characteristics of both the initial signals and the channel as a random source to extract the shared secret key from. (Note that using the channel phase characteristics as a source of randomness is a feasible approach, which has been adopted in existing work, e.g., [34]. A possible way to implement this can be found in [35].) From the channel reciprocity, we know that within the channel coherence time, the channel between two nodes can be assumed to be invariant. We divide the channel coherence time to equal time slots: T1,T2,…,Td. Let the length of each time slot be TS, and denote the coherence time of the channel by CT. Let d=⌊CT/TS⌋.During one time slotTk, when Ni sends the initial signal to Nj, we denote the signal sent from Ni by si(t). si(t) has the following representation:
(1)si(t)=Ci(t)ej(ωc(t-t0)+ϕ(t)).
In (1), Ci(t) is the amplitude of si(t). ωc and ϕ(t) are the center frequency and the initial phase of si(t), respectively. We emphasize that it is feasible to send a signal with a given phase ϕ(t)—in fact, some existing schemes like [34] already include such operations. In order to implement such an operation, one can use analog-to-digital converters [35].Definition of Adversaries.  In this paper, we consider three different kinds of adversaries: internal eavesdropper, external eavesdropper, and MITM adversary. Here both internal eavesdroppers and external eavesdroppers refer to passive adversaries that eavesdrop messages and attempt to figure out the established key. The difference between these two types of adversaries is that an internal eavesdropper is an intermediate node in a path selected for transmitting messages for key agreement, while an external eavesdropper is not an intermediate node in any such path. Unlike these two types of passive adversaries, an MITM adversary is an active adversary who controls one or more node in a path selected for transmitting messages for key agreement and carries out an MITM attack. A little more formally, we have the following definitions.Definition 1.
A multihop key agreement scheme is secure against a set of external eavesdroppers if, assuming all involved nodes follow the protocol faithfully, all signals overheard by this set of eavesdroppers are statistically independent from the final key generated by this scheme.Definition 2.
A multihop key agreement scheme is secure against a set of internal eavesdropper if, assuming all involved nodes follow the protocol faithfully, all packets received by this set of eavesdroppers, together with all signals overheard by this set of eavesdropper, are statistically independent from the final key generated by this scheme.Definition 3.
A multihop key agreement scheme is secure against a set of MITM adversaries if, assuming all involved nodes except this set of MITM adversaries follow the protocol faithfully, the final keys different nodes obtain are consistent; furthermore, all packets received by this set of MITM adversaries, together with all signals overheard by this set of adversary, are statistically indepedent from the final key generated by this scheme.


## 4. The Basic Multihop Key Agreement Scheme

In this section, we propose a basic multihop key agreement scheme. The basic scheme is built on one selected path between the two nodes that want to agree on a secret key. It is secure against any external eavesdroppers as long as those eavesdroppers are more than half a wavelength away from all the nodes in the selected path.


### 4.1. Scheme Outline

The basic idea of this multihop key agreement scheme is to use both the channel phase characteristics of the selected path and the randomly selected initial phases to extract common secrets (i.e., secrets known only toA and B). By using quantization, these common secrets are quantized into common secret bits. After that, information reconciliation and privacy amplification are used [36–38] on the common secret bits, so that a secret key can be generated. When the external eavesdroppers are more than half a wavelength away, they will experience channels that are independent of the channels in the selected path [3, 4].In order to havek common secret bits, the two parties (denoted by A and B) need to interact with each other for ⌈k/q⌉ rounds, assuming in each round that they can get q bits from quantization. In each round, A picks a random phase value, and sends an initial signal with this initial phase value to B using the selected path. Each intermediate node in this path estimates the phase of the signal received from its antecedent node and sends a new signal with this estimated phase to its subsequent node. Note that A is the first node in the path, and B is the last node in the path. Hence, A has a subsequent node only, and B has an antecedent node only. After B receives the signal from its antecedent node, it picks a random phase value and sends an initial signal with this initial phase value back to A, along the reverse path. Each intermediate node estimates the phase of the signal received from its subsequent node, and sends a new signal with the estimated phase to its antecedent node. Finally B (resp., A) estimates the phase of the signal received from its antecedent (resp., subsequent) node and adds the estimated phase with its randomly generated initial phase. The sums generated by A and B both reflect characteristics of all the channels in the path and the random initial phase values picked by A and B. In order to make sure that they are highly correlated, each round is completed within the channel coherence time. The random initial phase values picked by A and B are sources of randomness of the extracted common secrets.After extracting common secrets from the channels and the random initial phase values,A and B perform independent quantization on these secrets and get common secret bits. The discrepancies between common secret bits of A and B are corrected by information reconciliation. The lost entropy of performing the information reconciliation is reduced by privacy amplification. In the following, we give detailed descriptions of these steps. After that, we give analysis of the basic scheme.


### 4.2. Common Secret Extraction

The common secret extraction consists of⌈k/q⌉ rounds, and each round contains (2m+2) time slots. Figure 1 illustrates the signal transmission involved in one round.Figure 1
Illustration of signal transmission in one round.In the following, we describe steps involved in one round.(1)
In the time slotT1=[0,0+TS], A sends the initial signal sa(t) with phase ϕ1 to R1, where the value of ϕ1 is randomly picked by A from [0,2π) (and thus known toA). Without loss of generality, we assume that sa(t) has a unit power level. Denote the signal received at R1 by rA,R1. Then we get that rA,R1(t)=αA,R1(t)ej(ωct+ϕA,R1)+nR1(t), where αA,R1(t) and ϕA,R1 denote the amplitude and phase of the signal received from A, and nR1(t) denotes the receiver noise at R1.(2)
The phase ofrA,R1(t) is ϕA,R1=ϕ1+ψA,R1, in which ψA,R1 denotes the phase offset of the channel between A and R1. R1 computes the estimate of ϕA,R1, which we denote by ϕ^A,R1. After that in T2, R1 sends a unit signal to R2 whose phase is tuned to ϕ^A,R1.(3)
Fori=2,3,…,m-1, in the time slot Ti+1, Ri computes the phase estimate of the signal received from Ri-1 and sends a new unit signal with this phase estimate to Ri+1. In Tm+1, Rm sends the signal ej(wc(t-m·TS)+ϕ^A,Rm) to B.(4)
In the time slotTm+2, B sends the initial signal sb(t) with phase ϕ2 to Rm, where sb(t) also has a unit power level, and ϕ2 is picked randomly by B from [0,2π) (and thus known toB). Denote the signal received at Rm by rB,Rm. Then rB,Rm(t)=αB,Rm(t)ej(ωc(t-(m+1)·TS)+ϕB,Rm)+nRm(t). The phase of rB,Rm(t) is ϕB,Rm=ϕ2+ψB,Rm, in which ψB,Rm denotes the phase of the channel between B and Rm.(5)
Fori=m+3,m+4,…,2m+1, in Ti,  R2m+3-i sends the signal ej(wc(t-(i-1)·TS)+ϕ^B,R2m+3-i) to R2m+2-i. In T2m+2, R1 sends the signal ej(wc(t-(2m+1)·TS)+ϕ^B,R1) to A.(6)
From the previous stepsB receives rRm,B, and A receives rR1,A. It is easy to see that
(2)rRm,B(t)=αRm,B(t)ej(wc(t-m·TS)+ϕA,B,1)+nB(t),rR1,A(t)=αR1,A(t)ej(wc(t-(2m+1)·TS)+ϕB,A,1)+nA(t),whereϕA,B,1 and ϕB,A,1 denote the signal phases of rRm,B and rR1,A, respectively. B computes IB=(ϕ^A,B,1+ϕ2)mod2π, and A computes IA=(ϕ^B,A,1+ϕ1)mod2π. From IB and IA, B and A extract common secret bits.We denote such a round byRound(A,B,m). Apparently Round(A,B,m) needs to take (2m+2) time slots.From the previous protocol process, we can get thatIB=(ϕ^A,B,1+ϕ2)mod2π={est(ϕ1+ψA,R1+∑i=1m-1‍ψRi,Ri+1+ψRm,B)+ϕ2}mod2π and IA=(ϕ^B,A,1+ϕ1)mod2π={est(ϕ2+ψB,Rm+∑i=1m-1‍ψRi+1,Ri+ψR1,A)+ϕ1}mod2π. From the channel reciprocity, IB and IA are highly correlated if the measurements are within the channel coherence time. Hereafter, suppose that A and B carry out z rounds of Round(A,B,m), and denote the extracted secret vectors by [IA,1,IA,2,…,IA,z] and [IB,1,IB,2,…,IB,z], respectively.


### 4.3. Quantization

Afterz rounds of common secret extraction, A has got the secret vector [IA,1,IA,2,…,IA,z], and B has got the secret vector [IB,1,IB,2,…,IB,z]. For Z∈{A,B}  and  k=1,2,…,z,  IZ,k is in the range of [0,2π). Now A and B quantize each value in their vectors into common secret bits. Specifically, we divide the interval [0,2π) into q equal subintervals. Denote these subintervals by [0,2π/q),[2π/q,4π/q),…,[2(q-1)π/q,2π). We quantize each subinterval into log2(q) bits using the Gray code [39]. By using Gray code, adjacent subintervals have only one bit discrepancy after quantization, which reduces the number of bit errors caused by estimation errors.Denote the length of the targeted secret key byk. In order to generate the key, A and B need to interact with each other for at least ⌈k/q⌉ rounds.


### 4.4. Information Reconciliation and Privacy Amplification

Because there exist noises and interferences at the receivers,A and B can get discrepancies at some common secret bits. They can achieve secret bits reconciliation by transmitting error correcting information through a public channel, which is called information reconciliation [40, 41]. We use the classic Cascade protocol [40] to perform reconciliation between the extracted secret bits. For completeness we briefly review the Cascade protocol.Denote the two secret bit strings atA and B by BSA and BSB. In the Cascade protocol, each of the two bit strings are divided into disjoint blocks. One party sends the parity values of all the blocks to the other party. If an odd number of errors are found within any block, A and B perform an interactive binary error search on that block, until one bit error is corrected. The Cascade protocol consists of several rounds, depending on the rate of bit discrepancies between BSA and BSB. If in the kth (k≥2) round, one error is corrected at the ith bit, and then any other block that contains the ith bit also contain an odd number of errors, which need to be corrected subsequently. Only minimal information gets leaked out if the number of rounds and the block size are selected appropriately.After the information reconciliation, privacy amplification [36–38] is used to reduce the side information leaked during information reconciliation. We use the following 2-universal hash family [4]:
(3)ga,b(x)=(ax+b)modpM,ha,b(x)=ga,b(x)modm,x∈{1,2,…,M},a∈[1,pM-1],b∈[0,pM-1],
where pM is a prime number that satisfies pM>M. This 2-universal hash family consists of all the functions h that map from {1,2,…,M} to {0,1}m. One party randomly selects a and b and sends them to the other party. We divide the secret bits after reconciliation into blocks of log2(M) bits, and m is decided based on the required secret key length.After these two processes, the generated keys atA and B are cryptographic secure keys. A and B can use the generated key for secret communications.


### 4.5. Security Analysis of the Basic Scheme

In this section, we present a security analysis of the basic scheme. Firstly we argue that the basic scheme is secure against any external eavesdroppers that are more than half a wavelength away from all the nodes in the selected path. Secondly we show that threats from internal adversaries can affect the security of the scheme. Finally we show that MITM attack is possible in the basic scheme. (Recall that internal eavesdroppers, external eavesdroppers, and MITM adversary are defined at the end of Section3.)


#### 4.5.1. Security against Any External Eavesdropper

If all the external eavesdroppers are more than half a wavelength away from all the nodes in the selected path, then their experienced channels are independent of channels between nodes in the selected path.In the following we analyze the security of the basic scheme when there exists only one external eavesdropper. The analysis can be similarly extended to the case in which there are more than one eavesdroppers. In Figure2, denote the eavesdropper by E. From Round(A,B,m), E gets the following estimated phases from its received signals: (4)est(ϕ1+ψA,E)est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E),k∈[1,m]est(ϕ2+ψB,E)est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri+ψRk,E),k∈[1,m].Figure 2
Illustration of one external eavesdropper in the basic scheme.In (4), E gets est(ϕ1+ψA,E) at T1 from A and gets est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E) at Tk+1 from Rk,  k∈[1,m]. On the other hand, E gets est(ϕ2+ψB,E) at Tm+2 from B and gets est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri+ψRk,E) at Tm+2+k from Rm+1-k,  k∈[1,m].Becauseϕ1 and ϕ2 are randomly selected by A and B, respectively, these estimated phases are also random. Because ψA,E is independent of ψA,R1, E cannot get any knowledge of (ϕ1+ψA,R1) from est(ϕ1+ψA,E). Similarly, E cannot get any knowledge of (ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,B),  k∈[1,m] from est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E),  k∈[1,m]. Finally, during the channel coherence time, no probe signals are transmitted between the nodes in the selected path, so ψA,E, ψRk,E, k∈[1,m] and ψB,E are unknown to E. Therefore, from these estimated phase values, E gets no knowledge of the extracted secrets at A or B.We stress that it is realistic to assume that the external eavesdroppers are at least half a wavelength away. When the carrier frequency is 2.437 GHz (one of the frequency band of 802.11 b), the wavelength of the carrier is(3·108m/s)/(2.437·109Hz)≈0.12m. Half a wavelength is only about 6 centimeters. Within such a distance, it is hard for an eavesdropper to avoid being detected.


#### 4.5.2. Threats of Internal Adversaries

In the basic scheme, each of the internal nodes can get the complete knowledge of the extracted secrets atA and B. If one of them is corrupted, then the scheme is not secure. For example, if Rk is corrupted, based on its received signals from Rk-1 and Rk+1, it gets ϕ^A,Rk=est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1) and ϕ^B,Rk=est(ϕ2+∑i=km-1‍ψRi+1,Ri+ψB,Rm). By adding up these two values, Rk gets an estimate, which is highly correlated to both IB and IA. Therefore, if one of the intermediate nodes is corrupted, the basic scheme is not secure.


#### 4.5.3. MITM Attack

Because there arem intermediate nodes between A and B, any of them can carry out an MITM attack. Suppose that Rk intends to carry out an MITM attack and establish two different keys with A and B, respectively. Specifically, Rk agrees on one key with A, based on the subpath A→R1→⋯→Rk; Rk agrees on another key with B, based on the other subpath Rk→Rk+1→⋯→B. The MITM attack consists of the following steps:(1)
In each round,Rk performs the following steps:
(a)
WhenRk receives the signal rRk-1,Rk=αRk-1,Rk(t)ej(wc(t-(k-1)·TS)+ϕA,Rk) from Rk-1, it picks a random value ϕk,1∈[0,2π) and sends sk,1(t)=ej(wc(t-k·TS)+ϕk,1) to Rk+1.(b)
WhenRk receives the signal rRk+1,Rk=αRk+1,Rk(t)ej(wc(t-(2m+1-k)·TS)+ϕB,Rk) from Rk+1, it picks a random value ϕk,2∈[0,2π) and sends sk,2(t)=ej(wc(t-(2m+2-k)·TS)+ϕk,2) to Rk-1.(c)
Rk computes the estimates of ϕA,Rk and ϕB,Rk. Denote these two estimates by ϕ^A,Rk and ϕ^B,Rk, respectively.(d)
Rk computes Ik,B=ϕ^B,Rk+ϕk,1 and Ik,A=ϕ^A,Rk+ϕk,2. Rk then quantizes Ik,B and Ik,A to generate secret bit strings Qk,B and Qk,A. Denote the length of Qk,B and Qk,A by q bits.(2)
Afterz rounds, Rk gets STk,B=Qk,B,1∥Qk,B,2∥⋯∥Qk,B,z and STk,A=Qk,A,1∥Qk,A,2∥⋯∥Qk,A,z, in which ∥ denotes the string concatenation operation. Both STk,B and STk,A have a length of (z·q) bits. Rk uses STk,B to agree on a secret key KEYk,B with B, and uses STk,A to agree on a secret key KEYk,A with A.From the attack process we can see thatIk,B=ϕ^B,Rk+ϕk,1=est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri)+ϕk,1, and IB=est(ϕk,1+∑i=km-1‍ψRi,Ri+1+ψRm,B)+ϕ2. Both Ik,B and IB can be viewed as estimates of ϕk,1+∑i=km-1‍ψRi,Ri+1+ψRm,B+ϕ2. By using follow-up quantization, information reconciliation and privacy amplification techniques, Rk and B can agree on a secret key KEYk,B. Similarly, both Ik,A and IA can be viewed as estimates of ϕk,2+∑i=1k-1‍ψRi,Ri+1+ψA,R1+ϕ1. So Rk and A can also agree on a secret key KEYk,A. In this way, Rk carries out the MITM attack successfully.


### 4.6. Possible Reduction of Estimation Errors

Given the basic scheme we have designed, there are possible ways to reduce the estimation errors. For instance, the intermediate nodes betweenA and B may append fix phase delay on forward and backward paths; that is, let ΨRi,Ri+1=ΨRi+1,Ri. This would not reduce secrecy because ϕ1 and ϕ2 are random and unknown to the intermediate nodes.


## 4.1. Scheme Outline

The basic idea of this multihop key agreement scheme is to use both the channel phase characteristics of the selected path and the randomly selected initial phases to extract common secrets (i.e., secrets known only toA and B). By using quantization, these common secrets are quantized into common secret bits. After that, information reconciliation and privacy amplification are used [36–38] on the common secret bits, so that a secret key can be generated. When the external eavesdroppers are more than half a wavelength away, they will experience channels that are independent of the channels in the selected path [3, 4].In order to havek common secret bits, the two parties (denoted by A and B) need to interact with each other for ⌈k/q⌉ rounds, assuming in each round that they can get q bits from quantization. In each round, A picks a random phase value, and sends an initial signal with this initial phase value to B using the selected path. Each intermediate node in this path estimates the phase of the signal received from its antecedent node and sends a new signal with this estimated phase to its subsequent node. Note that A is the first node in the path, and B is the last node in the path. Hence, A has a subsequent node only, and B has an antecedent node only. After B receives the signal from its antecedent node, it picks a random phase value and sends an initial signal with this initial phase value back to A, along the reverse path. Each intermediate node estimates the phase of the signal received from its subsequent node, and sends a new signal with the estimated phase to its antecedent node. Finally B (resp., A) estimates the phase of the signal received from its antecedent (resp., subsequent) node and adds the estimated phase with its randomly generated initial phase. The sums generated by A and B both reflect characteristics of all the channels in the path and the random initial phase values picked by A and B. In order to make sure that they are highly correlated, each round is completed within the channel coherence time. The random initial phase values picked by A and B are sources of randomness of the extracted common secrets.After extracting common secrets from the channels and the random initial phase values,A and B perform independent quantization on these secrets and get common secret bits. The discrepancies between common secret bits of A and B are corrected by information reconciliation. The lost entropy of performing the information reconciliation is reduced by privacy amplification. In the following, we give detailed descriptions of these steps. After that, we give analysis of the basic scheme.


## 4.2. Common Secret Extraction

The common secret extraction consists of⌈k/q⌉ rounds, and each round contains (2m+2) time slots. Figure 1 illustrates the signal transmission involved in one round.Figure 1
Illustration of signal transmission in one round.In the following, we describe steps involved in one round.(1)
In the time slotT1=[0,0+TS], A sends the initial signal sa(t) with phase ϕ1 to R1, where the value of ϕ1 is randomly picked by A from [0,2π) (and thus known toA). Without loss of generality, we assume that sa(t) has a unit power level. Denote the signal received at R1 by rA,R1. Then we get that rA,R1(t)=αA,R1(t)ej(ωct+ϕA,R1)+nR1(t), where αA,R1(t) and ϕA,R1 denote the amplitude and phase of the signal received from A, and nR1(t) denotes the receiver noise at R1.(2)
The phase ofrA,R1(t) is ϕA,R1=ϕ1+ψA,R1, in which ψA,R1 denotes the phase offset of the channel between A and R1. R1 computes the estimate of ϕA,R1, which we denote by ϕ^A,R1. After that in T2, R1 sends a unit signal to R2 whose phase is tuned to ϕ^A,R1.(3)
Fori=2,3,…,m-1, in the time slot Ti+1, Ri computes the phase estimate of the signal received from Ri-1 and sends a new unit signal with this phase estimate to Ri+1. In Tm+1, Rm sends the signal ej(wc(t-m·TS)+ϕ^A,Rm) to B.(4)
In the time slotTm+2, B sends the initial signal sb(t) with phase ϕ2 to Rm, where sb(t) also has a unit power level, and ϕ2 is picked randomly by B from [0,2π) (and thus known toB). Denote the signal received at Rm by rB,Rm. Then rB,Rm(t)=αB,Rm(t)ej(ωc(t-(m+1)·TS)+ϕB,Rm)+nRm(t). The phase of rB,Rm(t) is ϕB,Rm=ϕ2+ψB,Rm, in which ψB,Rm denotes the phase of the channel between B and Rm.(5)
Fori=m+3,m+4,…,2m+1, in Ti,  R2m+3-i sends the signal ej(wc(t-(i-1)·TS)+ϕ^B,R2m+3-i) to R2m+2-i. In T2m+2, R1 sends the signal ej(wc(t-(2m+1)·TS)+ϕ^B,R1) to A.(6)
From the previous stepsB receives rRm,B, and A receives rR1,A. It is easy to see that
(2)rRm,B(t)=αRm,B(t)ej(wc(t-m·TS)+ϕA,B,1)+nB(t),rR1,A(t)=αR1,A(t)ej(wc(t-(2m+1)·TS)+ϕB,A,1)+nA(t),whereϕA,B,1 and ϕB,A,1 denote the signal phases of rRm,B and rR1,A, respectively. B computes IB=(ϕ^A,B,1+ϕ2)mod2π, and A computes IA=(ϕ^B,A,1+ϕ1)mod2π. From IB and IA, B and A extract common secret bits.We denote such a round byRound(A,B,m). Apparently Round(A,B,m) needs to take (2m+2) time slots.From the previous protocol process, we can get thatIB=(ϕ^A,B,1+ϕ2)mod2π={est(ϕ1+ψA,R1+∑i=1m-1‍ψRi,Ri+1+ψRm,B)+ϕ2}mod2π and IA=(ϕ^B,A,1+ϕ1)mod2π={est(ϕ2+ψB,Rm+∑i=1m-1‍ψRi+1,Ri+ψR1,A)+ϕ1}mod2π. From the channel reciprocity, IB and IA are highly correlated if the measurements are within the channel coherence time. Hereafter, suppose that A and B carry out z rounds of Round(A,B,m), and denote the extracted secret vectors by [IA,1,IA,2,…,IA,z] and [IB,1,IB,2,…,IB,z], respectively.


## 4.3. Quantization

Afterz rounds of common secret extraction, A has got the secret vector [IA,1,IA,2,…,IA,z], and B has got the secret vector [IB,1,IB,2,…,IB,z]. For Z∈{A,B}  and  k=1,2,…,z,  IZ,k is in the range of [0,2π). Now A and B quantize each value in their vectors into common secret bits. Specifically, we divide the interval [0,2π) into q equal subintervals. Denote these subintervals by [0,2π/q),[2π/q,4π/q),…,[2(q-1)π/q,2π). We quantize each subinterval into log2(q) bits using the Gray code [39]. By using Gray code, adjacent subintervals have only one bit discrepancy after quantization, which reduces the number of bit errors caused by estimation errors.Denote the length of the targeted secret key byk. In order to generate the key, A and B need to interact with each other for at least ⌈k/q⌉ rounds.


## 4.4. Information Reconciliation and Privacy Amplification

Because there exist noises and interferences at the receivers,A and B can get discrepancies at some common secret bits. They can achieve secret bits reconciliation by transmitting error correcting information through a public channel, which is called information reconciliation [40, 41]. We use the classic Cascade protocol [40] to perform reconciliation between the extracted secret bits. For completeness we briefly review the Cascade protocol.Denote the two secret bit strings atA and B by BSA and BSB. In the Cascade protocol, each of the two bit strings are divided into disjoint blocks. One party sends the parity values of all the blocks to the other party. If an odd number of errors are found within any block, A and B perform an interactive binary error search on that block, until one bit error is corrected. The Cascade protocol consists of several rounds, depending on the rate of bit discrepancies between BSA and BSB. If in the kth (k≥2) round, one error is corrected at the ith bit, and then any other block that contains the ith bit also contain an odd number of errors, which need to be corrected subsequently. Only minimal information gets leaked out if the number of rounds and the block size are selected appropriately.After the information reconciliation, privacy amplification [36–38] is used to reduce the side information leaked during information reconciliation. We use the following 2-universal hash family [4]:
(3)ga,b(x)=(ax+b)modpM,ha,b(x)=ga,b(x)modm,x∈{1,2,…,M},a∈[1,pM-1],b∈[0,pM-1],
where pM is a prime number that satisfies pM>M. This 2-universal hash family consists of all the functions h that map from {1,2,…,M} to {0,1}m. One party randomly selects a and b and sends them to the other party. We divide the secret bits after reconciliation into blocks of log2(M) bits, and m is decided based on the required secret key length.After these two processes, the generated keys atA and B are cryptographic secure keys. A and B can use the generated key for secret communications.


## 4.5. Security Analysis of the Basic Scheme

In this section, we present a security analysis of the basic scheme. Firstly we argue that the basic scheme is secure against any external eavesdroppers that are more than half a wavelength away from all the nodes in the selected path. Secondly we show that threats from internal adversaries can affect the security of the scheme. Finally we show that MITM attack is possible in the basic scheme. (Recall that internal eavesdroppers, external eavesdroppers, and MITM adversary are defined at the end of Section3.)


### 4.5.1. Security against Any External Eavesdropper

If all the external eavesdroppers are more than half a wavelength away from all the nodes in the selected path, then their experienced channels are independent of channels between nodes in the selected path.In the following we analyze the security of the basic scheme when there exists only one external eavesdropper. The analysis can be similarly extended to the case in which there are more than one eavesdroppers. In Figure2, denote the eavesdropper by E. From Round(A,B,m), E gets the following estimated phases from its received signals: (4)est(ϕ1+ψA,E)est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E),k∈[1,m]est(ϕ2+ψB,E)est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri+ψRk,E),k∈[1,m].Figure 2
Illustration of one external eavesdropper in the basic scheme.In (4), E gets est(ϕ1+ψA,E) at T1 from A and gets est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E) at Tk+1 from Rk,  k∈[1,m]. On the other hand, E gets est(ϕ2+ψB,E) at Tm+2 from B and gets est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri+ψRk,E) at Tm+2+k from Rm+1-k,  k∈[1,m].Becauseϕ1 and ϕ2 are randomly selected by A and B, respectively, these estimated phases are also random. Because ψA,E is independent of ψA,R1, E cannot get any knowledge of (ϕ1+ψA,R1) from est(ϕ1+ψA,E). Similarly, E cannot get any knowledge of (ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,B),  k∈[1,m] from est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E),  k∈[1,m]. Finally, during the channel coherence time, no probe signals are transmitted between the nodes in the selected path, so ψA,E, ψRk,E, k∈[1,m] and ψB,E are unknown to E. Therefore, from these estimated phase values, E gets no knowledge of the extracted secrets at A or B.We stress that it is realistic to assume that the external eavesdroppers are at least half a wavelength away. When the carrier frequency is 2.437 GHz (one of the frequency band of 802.11 b), the wavelength of the carrier is(3·108m/s)/(2.437·109Hz)≈0.12m. Half a wavelength is only about 6 centimeters. Within such a distance, it is hard for an eavesdropper to avoid being detected.


### 4.5.2. Threats of Internal Adversaries

In the basic scheme, each of the internal nodes can get the complete knowledge of the extracted secrets atA and B. If one of them is corrupted, then the scheme is not secure. For example, if Rk is corrupted, based on its received signals from Rk-1 and Rk+1, it gets ϕ^A,Rk=est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1) and ϕ^B,Rk=est(ϕ2+∑i=km-1‍ψRi+1,Ri+ψB,Rm). By adding up these two values, Rk gets an estimate, which is highly correlated to both IB and IA. Therefore, if one of the intermediate nodes is corrupted, the basic scheme is not secure.


### 4.5.3. MITM Attack

Because there arem intermediate nodes between A and B, any of them can carry out an MITM attack. Suppose that Rk intends to carry out an MITM attack and establish two different keys with A and B, respectively. Specifically, Rk agrees on one key with A, based on the subpath A→R1→⋯→Rk; Rk agrees on another key with B, based on the other subpath Rk→Rk+1→⋯→B. The MITM attack consists of the following steps:(1)
In each round,Rk performs the following steps:
(a)
WhenRk receives the signal rRk-1,Rk=αRk-1,Rk(t)ej(wc(t-(k-1)·TS)+ϕA,Rk) from Rk-1, it picks a random value ϕk,1∈[0,2π) and sends sk,1(t)=ej(wc(t-k·TS)+ϕk,1) to Rk+1.(b)
WhenRk receives the signal rRk+1,Rk=αRk+1,Rk(t)ej(wc(t-(2m+1-k)·TS)+ϕB,Rk) from Rk+1, it picks a random value ϕk,2∈[0,2π) and sends sk,2(t)=ej(wc(t-(2m+2-k)·TS)+ϕk,2) to Rk-1.(c)
Rk computes the estimates of ϕA,Rk and ϕB,Rk. Denote these two estimates by ϕ^A,Rk and ϕ^B,Rk, respectively.(d)
Rk computes Ik,B=ϕ^B,Rk+ϕk,1 and Ik,A=ϕ^A,Rk+ϕk,2. Rk then quantizes Ik,B and Ik,A to generate secret bit strings Qk,B and Qk,A. Denote the length of Qk,B and Qk,A by q bits.(2)
Afterz rounds, Rk gets STk,B=Qk,B,1∥Qk,B,2∥⋯∥Qk,B,z and STk,A=Qk,A,1∥Qk,A,2∥⋯∥Qk,A,z, in which ∥ denotes the string concatenation operation. Both STk,B and STk,A have a length of (z·q) bits. Rk uses STk,B to agree on a secret key KEYk,B with B, and uses STk,A to agree on a secret key KEYk,A with A.From the attack process we can see thatIk,B=ϕ^B,Rk+ϕk,1=est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri)+ϕk,1, and IB=est(ϕk,1+∑i=km-1‍ψRi,Ri+1+ψRm,B)+ϕ2. Both Ik,B and IB can be viewed as estimates of ϕk,1+∑i=km-1‍ψRi,Ri+1+ψRm,B+ϕ2. By using follow-up quantization, information reconciliation and privacy amplification techniques, Rk and B can agree on a secret key KEYk,B. Similarly, both Ik,A and IA can be viewed as estimates of ϕk,2+∑i=1k-1‍ψRi,Ri+1+ψA,R1+ϕ1. So Rk and A can also agree on a secret key KEYk,A. In this way, Rk carries out the MITM attack successfully.


## 4.5.1. Security against Any External Eavesdropper

If all the external eavesdroppers are more than half a wavelength away from all the nodes in the selected path, then their experienced channels are independent of channels between nodes in the selected path.In the following we analyze the security of the basic scheme when there exists only one external eavesdropper. The analysis can be similarly extended to the case in which there are more than one eavesdroppers. In Figure2, denote the eavesdropper by E. From Round(A,B,m), E gets the following estimated phases from its received signals: (4)est(ϕ1+ψA,E)est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E),k∈[1,m]est(ϕ2+ψB,E)est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri+ψRk,E),k∈[1,m].Figure 2
Illustration of one external eavesdropper in the basic scheme.In (4), E gets est(ϕ1+ψA,E) at T1 from A and gets est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E) at Tk+1 from Rk,  k∈[1,m]. On the other hand, E gets est(ϕ2+ψB,E) at Tm+2 from B and gets est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri+ψRk,E) at Tm+2+k from Rm+1-k,  k∈[1,m].Becauseϕ1 and ϕ2 are randomly selected by A and B, respectively, these estimated phases are also random. Because ψA,E is independent of ψA,R1, E cannot get any knowledge of (ϕ1+ψA,R1) from est(ϕ1+ψA,E). Similarly, E cannot get any knowledge of (ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,B),  k∈[1,m] from est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1+ψRk,E),  k∈[1,m]. Finally, during the channel coherence time, no probe signals are transmitted between the nodes in the selected path, so ψA,E, ψRk,E, k∈[1,m] and ψB,E are unknown to E. Therefore, from these estimated phase values, E gets no knowledge of the extracted secrets at A or B.We stress that it is realistic to assume that the external eavesdroppers are at least half a wavelength away. When the carrier frequency is 2.437 GHz (one of the frequency band of 802.11 b), the wavelength of the carrier is(3·108m/s)/(2.437·109Hz)≈0.12m. Half a wavelength is only about 6 centimeters. Within such a distance, it is hard for an eavesdropper to avoid being detected.


## 4.5.2. Threats of Internal Adversaries

In the basic scheme, each of the internal nodes can get the complete knowledge of the extracted secrets atA and B. If one of them is corrupted, then the scheme is not secure. For example, if Rk is corrupted, based on its received signals from Rk-1 and Rk+1, it gets ϕ^A,Rk=est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1) and ϕ^B,Rk=est(ϕ2+∑i=km-1‍ψRi+1,Ri+ψB,Rm). By adding up these two values, Rk gets an estimate, which is highly correlated to both IB and IA. Therefore, if one of the intermediate nodes is corrupted, the basic scheme is not secure.


## 4.5.3. MITM Attack

Because there arem intermediate nodes between A and B, any of them can carry out an MITM attack. Suppose that Rk intends to carry out an MITM attack and establish two different keys with A and B, respectively. Specifically, Rk agrees on one key with A, based on the subpath A→R1→⋯→Rk; Rk agrees on another key with B, based on the other subpath Rk→Rk+1→⋯→B. The MITM attack consists of the following steps:(1)
In each round,Rk performs the following steps:
(a)
WhenRk receives the signal rRk-1,Rk=αRk-1,Rk(t)ej(wc(t-(k-1)·TS)+ϕA,Rk) from Rk-1, it picks a random value ϕk,1∈[0,2π) and sends sk,1(t)=ej(wc(t-k·TS)+ϕk,1) to Rk+1.(b)
WhenRk receives the signal rRk+1,Rk=αRk+1,Rk(t)ej(wc(t-(2m+1-k)·TS)+ϕB,Rk) from Rk+1, it picks a random value ϕk,2∈[0,2π) and sends sk,2(t)=ej(wc(t-(2m+2-k)·TS)+ϕk,2) to Rk-1.(c)
Rk computes the estimates of ϕA,Rk and ϕB,Rk. Denote these two estimates by ϕ^A,Rk and ϕ^B,Rk, respectively.(d)
Rk computes Ik,B=ϕ^B,Rk+ϕk,1 and Ik,A=ϕ^A,Rk+ϕk,2. Rk then quantizes Ik,B and Ik,A to generate secret bit strings Qk,B and Qk,A. Denote the length of Qk,B and Qk,A by q bits.(2)
Afterz rounds, Rk gets STk,B=Qk,B,1∥Qk,B,2∥⋯∥Qk,B,z and STk,A=Qk,A,1∥Qk,A,2∥⋯∥Qk,A,z, in which ∥ denotes the string concatenation operation. Both STk,B and STk,A have a length of (z·q) bits. Rk uses STk,B to agree on a secret key KEYk,B with B, and uses STk,A to agree on a secret key KEYk,A with A.From the attack process we can see thatIk,B=ϕ^B,Rk+ϕk,1=est(ϕ2+ψB,Rm+∑i=km-1‍ψRi+1,Ri)+ϕk,1, and IB=est(ϕk,1+∑i=km-1‍ψRi,Ri+1+ψRm,B)+ϕ2. Both Ik,B and IB can be viewed as estimates of ϕk,1+∑i=km-1‍ψRi,Ri+1+ψRm,B+ϕ2. By using follow-up quantization, information reconciliation and privacy amplification techniques, Rk and B can agree on a secret key KEYk,B. Similarly, both Ik,A and IA can be viewed as estimates of ϕk,2+∑i=1k-1‍ψRi,Ri+1+ψA,R1+ϕ1. So Rk and A can also agree on a secret key KEYk,A. In this way, Rk carries out the MITM attack successfully.


## 4.6. Possible Reduction of Estimation Errors

Given the basic scheme we have designed, there are possible ways to reduce the estimation errors. For instance, the intermediate nodes betweenA and B may append fix phase delay on forward and backward paths; that is, let ΨRi,Ri+1=ΨRi+1,Ri. This would not reduce secrecy because ϕ1 and ϕ2 are random and unknown to the intermediate nodes.


## 5. The Improved Multihop Key Agreement

Because the basic scheme suffers from threats of internal adversaries and the MITM attack, in this section, we propose an improved multihop key agreement scheme.


### 5.1. Scheme Outline

In the improved multihop key agreement scheme, we assume that the network is biconnected. Therefore, between any pair of nodes, we can find at least two disjoint paths. The basic scheme suffers from threats from internal adversaries and the MITM attack because the signals are only transmitted in one path. Any node in that path can get knowledge of the extracted common secret bits and can perform the MITM attack. We design the improved multihop key agreement scheme to make it impossible for nodes in one path to get knowledge of the secret key or control it.We emphasize that the previous goal of security is nontrivial to achieve. In particular, we consider a simple protocol, which we call SMPP hereafter. Assume that there are two disjoint pathsPathA and PathB between A and B. SMPP starts by letting A and B generate key KA over PathA and key KB over PathB. Then, A generates two random sequences SA and SB, respectively, and sends KA⊕SA over PathB to B and KB⊕SB over PathA to B. Finally, B computes SA by XORing his received value of KA⊕SA with KA; similarly, he computes SB. The final key agreed by A and B is the SA∥SB.Note that SMPP cannot really work against MITM attacks. For example, suppose that there is a nodeNAdv controlled by the adversary in the middle of PathA. When A and B try to generate KA over PathA, NAdv launches an MITM attack and makes them disagree on the value of KA. (This is very easy in general, because NAdv can simply play B’s role when talking to its neighbor on A’s side and play A’s role when talking to its neighbor on B’s side. In this way, A and NAdv agree on one value of KA, while NAdv and B agree on another value of KA.) Hence, A believes that the value of KA is KAA, while B believes that the value of KA is KAB. Both values (KAA and KAB) are private against nodes in path B. Also suppose that all nodes in PathB are honest and so A and B agree on the value of KB, which is private against nodes in PathA. Next, A generates SA and SB and sends KAA⊕SA over path B and KB⊕SB over path A. Assume that NAdv does not tamper with these transmitted values. Therefore, B receives these values correctly. However, since B has a different belief about the value of KA, when B tries to recover the value of SA, he will get KAA⊕SA⊕KAB instead of SA. In other words, A and B will disagree on the value of SA, which is part of the final key.In order to achieve our goal of security, we use a better approach. We send the initial signals along two disjoint paths betweenA and B, perform estimation, and forwarding at intermediate nodes and add up the estimated phases of received signals from two paths at the two end nodes. In this way, the sum of phases contain not only the initial random values picked for phases, but also channel phase characteristics of both the two paths. Any adversaries within one single path can neither get the established secret key nor carry out a successful MITM attack.In the improved multihop key agreement scheme,A and B jointly discover two disjoint paths between them. Denote the lengths of the two paths by m and n, respectively. After that, A and B carry out Round(A,B,m) along the first path and Round(A,B,n) along the second path. They interact with each other for sufficient rounds in order to get the targeted common secret bits. In each round, they add up extracted secrets from both rounds together. Finally, A and B perform quantization, information reconciliation and privacy amplification to get the secret key.When performing the first step, existing node-disjoint routing discovery protocols [42, 43] can be used. In the improved scheme, we do not assume that there are any preloaded keys or public key infrastructures in the network. Secure routing protocols based on malicious node detection and trust based routing protocols [44–46] can meet this requirement. Using one of these protocols, A can find two disjoint paths to B. After that, A and B perform the rest of the multihop key agreement protocol by using the two paths.


### 5.2. The Improved Scheme—Detailed Description

Denote the two disjoint paths betweenA and B by A→R1→R2→⋯→Rm→B and A→S1→S2→⋯→Sn→B, as shown in Figure 3.Figure 3
Disjoint routes betweenA and B.The improved scheme consists of the following steps.(1)
Fori=1 to z, A and B perform Round(A,B,m) along the first path and perform Round(A,B,n) along the second path. Without loss of generality, let A (resp., B) use the same initial phase ϕ1,i (resp., ϕ2,i) for Round(A,B,m) and Round(A,B,n). We reset the starting time to 0 after each round. From Round(A,B,m), A and B get IA,i(1) and IB,i(1) as their extracted common secrets; from Round(A,B,n), A and B get IA,i(2) and IB,i(2) as their extracted common secrets. A and B get their final common secrets by computing IA,i=IA,i(1)+IA,i(2)mod2π and IB,i=IB,i(1)+IB,i(2)mod2π, respectively. Denote their extracted secret vectors by [IA,1,IA,2,…,IA,z] and [IB,1,IB,2,…,IB,z], respectively.(2)
A quantizes each value in the vector [IA,1,IA,2,…,IA,z], and B quantizes each value in the vector [IB,1,IB,2,…,IB,z]. Denote their generated bit strings by BSA and BSB, respectively.(3)
A and B perform information reconciliation and privacy amplification on BSA and BSB. After these two processes, they get the secret key.


### 5.3. Security Analysis

In this section, we give a security analysis of the improved scheme. This security analysis is based on the assumption that all participating nodes are more than half a wavelength away from each other. Just as mentioned in Section4.5.1, this is a reasonable assumption.The security of the improved scheme is guaranteed against adversaries in a single path. Collusion attack from adversaries of both paths is not considered. In the following we first prove that the improved scheme is secure against any internal eavesdroppers in a single path. After that we prove that the improved scheme is secure against any MITM adversaries in a single path. (Recall that internal eavesdroppers and MITM adversary are defined at the end of Section3.)Theorem 4.
Under the assumption that all nodes are more than half a wavelength away from each other, the improved multihop key agreement scheme is secure against any internal eavesdroppers in a single path.Proof.
In this proof we enumerate all the phase information that the routing nodes can extract and then point out that they cannot generate any useful information aboutA and B’s secrets.
In the following we consider the collected phase information at an intermediate node in one round. Because the extracted common secrets at each round are quantized separately, they cannot be used for getting knowledge of secrets of other rounds. ConsiderR1 in the first path A→R1→R2→⋯→Rm→B. R1 receives signals from both A and R2. From the signals received from A and R2, R1 gets ϕ^A,R1=ϕ1+ψ^A,R1 and ϕ^B,R1=est(ϕ2+∑k=1m-1‍ψRk+1,Rk+ψB,Rm), respectively. From these two phase estimates, R1 can only get the value of ϕ^A,R1+ϕ^B,R1. However, the secrets obtained by A and B also include the phase estimates through the other path A→S1→S2→⋯→Sn→B. So we can see that R1 can get no information about the secrets.
For each intermediate nodeRk in the first path, we enumerate its estimated phases as follows:
(5)ϕ^A,Rk=est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1),ϕ^B,Rk=est(ϕ2+∑i=km-1‍ψRi+1,Ri+ψB,Rm).
Because all the m intermediate nodes are more than half a wavelength away from other nodes, they cannot get the phase information from the other path; that is, ψA,S1+∑k=1n-1‍ψSk,Sk+1+ψSn,B. No matter how many nodes in the first path combine their phase information, they cannot gain any knowledge about this value.
Therefore, we can see that the proposed protocol is secure against any internal eavesdroppers in one single path.Remark 5.
If an eavesdropper is not an intermediate node in either path, and he is more than half a wavelength away from all participating nodes, then he cannot gain any knowledge on the secret key either. This is similar to our analysis in Section4.5.Theorem 6.
The improved multihop key agreement scheme is secure against any MITM adversaries in a single path.Proof.
Without loss of generality, suppose thatRi try to perform the MITM attack to A and B. The purpose of MITM attack is to establish two different keys with A and B, respectively, and after that to relay encrypted messages between them.
InRound(A,B,m), in Ti, Ri receives the signal rA,Ri=αRi-1,Ri(t)ej(wc(t-(i-1)·TS)+ϕ^A,Ri-1+ψRi-1,Ri)+nRi(t) from Ri-1. If Ri is an honest node, it will perform the phase estimation of the signal received from Ri-1 and send the signal ej(wc(t-i·TS)+ϕ^A,Ri) to Ri+1. However, Ri wants to perform the MITM attack, so it generates ϕ1e and sends a different signal ej(wc(t-i·TS)+ϕ1e) to Ri+1. If all other nodes in the first path are honest, then the signal received by B should be
(6)αRm,B(t)ej(wc(t-m·TS)+ϕ^Ri,Rme+ψRm,B)+nB(t).
In (6), ϕ^Ri,Rme=est(ϕ1e+∑k=im-1‍ψRk,Rk+1).
On the other hand, whenRi receives rRi+1,Ri(t)=αRi+1,Ri(t)ej(wc(t-(2m+2-i)·TS)+ϕ^B,Ri+1+ψRi+1,Ri)+nRi(t) from Ri+1 in T2m+2-i, Ri generates another phase ϕ2e and sends ej(wc(t-(2m+3-i)·TS)+ϕ2e) to Ri-1. If R1,R2,…,  and  Ri-1 behave honestly, and then the signal A receives should be
(7)αR1,A(t)ej(wc(t-(2m+2)·TS)+ϕ^Ri,R1e+ψR1,A)+nB(t).
In (9),  ϕ^Ri,R1e=est(ϕ2e+∑k=1i-1‍ψRk+1,Rk).
NowB can get his secret bits by quantizing est(ϕ1e+∑k=im-1‍ψRk,Rk+1+ψRm,B)+IB(2)+ϕ2. A can get its secret bits by quantizing est(ϕ2e+∑k=1i-1‍ψRk+1,Rk+ψR1,A)+IA(2)+ϕ1. Ri has est(ϕ2+ψB,Rm+∑k=im-1‍ψRk+1,Rk)+ϕ1e and est(ϕ1+ψA,R1+∑k=1i-1‍ψRk,Rk+1)+ϕ2e. However, Ri does not know IB(2) and IA(2) either, because Ri is more than half a wavelength from the other path.
From the previous analysis we know thatRi cannot agree on two different keys with A and B. Therefore, it cannot carry out MITM attack successfully. This analysis can be directly extended to the case that any number of intermediate nodes in the first path carry out MITM attacks collaboratively. Because their experienced channels are statistically independent of channels of the second path, they cannot gain any information of IB(2) or IA(2).
We conclude that the improved protocol is secure against any MITM adversaries in a single path.Remark 7.
If the adversary can place cheating nodes on two disjoint paths, there are straightforward ways to extend our protocol to achieve security. For example, we can consider using three disjoint paths betweenA and B. In general, in order to prevent cheating nodes on k disjoint paths, A and B can use k+1 disjoint paths between them for key extraction, as long as there exist k+1 disjoint paths between them. (If there are cheating nodes on all disjoint paths between A and B, then no solution is possible because these nodes can choose to simply block all communications between A and B.) This will lead to higher complexity of the protocol—so, there is a tradeoff between security and efficiency.


## 5.1. Scheme Outline

In the improved multihop key agreement scheme, we assume that the network is biconnected. Therefore, between any pair of nodes, we can find at least two disjoint paths. The basic scheme suffers from threats from internal adversaries and the MITM attack because the signals are only transmitted in one path. Any node in that path can get knowledge of the extracted common secret bits and can perform the MITM attack. We design the improved multihop key agreement scheme to make it impossible for nodes in one path to get knowledge of the secret key or control it.We emphasize that the previous goal of security is nontrivial to achieve. In particular, we consider a simple protocol, which we call SMPP hereafter. Assume that there are two disjoint pathsPathA and PathB between A and B. SMPP starts by letting A and B generate key KA over PathA and key KB over PathB. Then, A generates two random sequences SA and SB, respectively, and sends KA⊕SA over PathB to B and KB⊕SB over PathA to B. Finally, B computes SA by XORing his received value of KA⊕SA with KA; similarly, he computes SB. The final key agreed by A and B is the SA∥SB.Note that SMPP cannot really work against MITM attacks. For example, suppose that there is a nodeNAdv controlled by the adversary in the middle of PathA. When A and B try to generate KA over PathA, NAdv launches an MITM attack and makes them disagree on the value of KA. (This is very easy in general, because NAdv can simply play B’s role when talking to its neighbor on A’s side and play A’s role when talking to its neighbor on B’s side. In this way, A and NAdv agree on one value of KA, while NAdv and B agree on another value of KA.) Hence, A believes that the value of KA is KAA, while B believes that the value of KA is KAB. Both values (KAA and KAB) are private against nodes in path B. Also suppose that all nodes in PathB are honest and so A and B agree on the value of KB, which is private against nodes in PathA. Next, A generates SA and SB and sends KAA⊕SA over path B and KB⊕SB over path A. Assume that NAdv does not tamper with these transmitted values. Therefore, B receives these values correctly. However, since B has a different belief about the value of KA, when B tries to recover the value of SA, he will get KAA⊕SA⊕KAB instead of SA. In other words, A and B will disagree on the value of SA, which is part of the final key.In order to achieve our goal of security, we use a better approach. We send the initial signals along two disjoint paths betweenA and B, perform estimation, and forwarding at intermediate nodes and add up the estimated phases of received signals from two paths at the two end nodes. In this way, the sum of phases contain not only the initial random values picked for phases, but also channel phase characteristics of both the two paths. Any adversaries within one single path can neither get the established secret key nor carry out a successful MITM attack.In the improved multihop key agreement scheme,A and B jointly discover two disjoint paths between them. Denote the lengths of the two paths by m and n, respectively. After that, A and B carry out Round(A,B,m) along the first path and Round(A,B,n) along the second path. They interact with each other for sufficient rounds in order to get the targeted common secret bits. In each round, they add up extracted secrets from both rounds together. Finally, A and B perform quantization, information reconciliation and privacy amplification to get the secret key.When performing the first step, existing node-disjoint routing discovery protocols [42, 43] can be used. In the improved scheme, we do not assume that there are any preloaded keys or public key infrastructures in the network. Secure routing protocols based on malicious node detection and trust based routing protocols [44–46] can meet this requirement. Using one of these protocols, A can find two disjoint paths to B. After that, A and B perform the rest of the multihop key agreement protocol by using the two paths.


## 5.2. The Improved Scheme—Detailed Description

Denote the two disjoint paths betweenA and B by A→R1→R2→⋯→Rm→B and A→S1→S2→⋯→Sn→B, as shown in Figure 3.Figure 3
Disjoint routes betweenA and B.The improved scheme consists of the following steps.(1)
Fori=1 to z, A and B perform Round(A,B,m) along the first path and perform Round(A,B,n) along the second path. Without loss of generality, let A (resp., B) use the same initial phase ϕ1,i (resp., ϕ2,i) for Round(A,B,m) and Round(A,B,n). We reset the starting time to 0 after each round. From Round(A,B,m), A and B get IA,i(1) and IB,i(1) as their extracted common secrets; from Round(A,B,n), A and B get IA,i(2) and IB,i(2) as their extracted common secrets. A and B get their final common secrets by computing IA,i=IA,i(1)+IA,i(2)mod2π and IB,i=IB,i(1)+IB,i(2)mod2π, respectively. Denote their extracted secret vectors by [IA,1,IA,2,…,IA,z] and [IB,1,IB,2,…,IB,z], respectively.(2)
A quantizes each value in the vector [IA,1,IA,2,…,IA,z], and B quantizes each value in the vector [IB,1,IB,2,…,IB,z]. Denote their generated bit strings by BSA and BSB, respectively.(3)
A and B perform information reconciliation and privacy amplification on BSA and BSB. After these two processes, they get the secret key.


## 5.3. Security Analysis

In this section, we give a security analysis of the improved scheme. This security analysis is based on the assumption that all participating nodes are more than half a wavelength away from each other. Just as mentioned in Section4.5.1, this is a reasonable assumption.The security of the improved scheme is guaranteed against adversaries in a single path. Collusion attack from adversaries of both paths is not considered. In the following we first prove that the improved scheme is secure against any internal eavesdroppers in a single path. After that we prove that the improved scheme is secure against any MITM adversaries in a single path. (Recall that internal eavesdroppers and MITM adversary are defined at the end of Section3.)Theorem 4.
Under the assumption that all nodes are more than half a wavelength away from each other, the improved multihop key agreement scheme is secure against any internal eavesdroppers in a single path.Proof.
In this proof we enumerate all the phase information that the routing nodes can extract and then point out that they cannot generate any useful information aboutA and B’s secrets.
In the following we consider the collected phase information at an intermediate node in one round. Because the extracted common secrets at each round are quantized separately, they cannot be used for getting knowledge of secrets of other rounds. ConsiderR1 in the first path A→R1→R2→⋯→Rm→B. R1 receives signals from both A and R2. From the signals received from A and R2, R1 gets ϕ^A,R1=ϕ1+ψ^A,R1 and ϕ^B,R1=est(ϕ2+∑k=1m-1‍ψRk+1,Rk+ψB,Rm), respectively. From these two phase estimates, R1 can only get the value of ϕ^A,R1+ϕ^B,R1. However, the secrets obtained by A and B also include the phase estimates through the other path A→S1→S2→⋯→Sn→B. So we can see that R1 can get no information about the secrets.
For each intermediate nodeRk in the first path, we enumerate its estimated phases as follows:
(5)ϕ^A,Rk=est(ϕ1+ψA,R1+∑i=1k-1‍ψRi,Ri+1),ϕ^B,Rk=est(ϕ2+∑i=km-1‍ψRi+1,Ri+ψB,Rm).
Because all the m intermediate nodes are more than half a wavelength away from other nodes, they cannot get the phase information from the other path; that is, ψA,S1+∑k=1n-1‍ψSk,Sk+1+ψSn,B. No matter how many nodes in the first path combine their phase information, they cannot gain any knowledge about this value.
Therefore, we can see that the proposed protocol is secure against any internal eavesdroppers in one single path.Remark 5.
If an eavesdropper is not an intermediate node in either path, and he is more than half a wavelength away from all participating nodes, then he cannot gain any knowledge on the secret key either. This is similar to our analysis in Section4.5.Theorem 6.
The improved multihop key agreement scheme is secure against any MITM adversaries in a single path.Proof.
Without loss of generality, suppose thatRi try to perform the MITM attack to A and B. The purpose of MITM attack is to establish two different keys with A and B, respectively, and after that to relay encrypted messages between them.
InRound(A,B,m), in Ti, Ri receives the signal rA,Ri=αRi-1,Ri(t)ej(wc(t-(i-1)·TS)+ϕ^A,Ri-1+ψRi-1,Ri)+nRi(t) from Ri-1. If Ri is an honest node, it will perform the phase estimation of the signal received from Ri-1 and send the signal ej(wc(t-i·TS)+ϕ^A,Ri) to Ri+1. However, Ri wants to perform the MITM attack, so it generates ϕ1e and sends a different signal ej(wc(t-i·TS)+ϕ1e) to Ri+1. If all other nodes in the first path are honest, then the signal received by B should be
(6)αRm,B(t)ej(wc(t-m·TS)+ϕ^Ri,Rme+ψRm,B)+nB(t).
In (6), ϕ^Ri,Rme=est(ϕ1e+∑k=im-1‍ψRk,Rk+1).
On the other hand, whenRi receives rRi+1,Ri(t)=αRi+1,Ri(t)ej(wc(t-(2m+2-i)·TS)+ϕ^B,Ri+1+ψRi+1,Ri)+nRi(t) from Ri+1 in T2m+2-i, Ri generates another phase ϕ2e and sends ej(wc(t-(2m+3-i)·TS)+ϕ2e) to Ri-1. If R1,R2,…,  and  Ri-1 behave honestly, and then the signal A receives should be
(7)αR1,A(t)ej(wc(t-(2m+2)·TS)+ϕ^Ri,R1e+ψR1,A)+nB(t).
In (9),  ϕ^Ri,R1e=est(ϕ2e+∑k=1i-1‍ψRk+1,Rk).
NowB can get his secret bits by quantizing est(ϕ1e+∑k=im-1‍ψRk,Rk+1+ψRm,B)+IB(2)+ϕ2. A can get its secret bits by quantizing est(ϕ2e+∑k=1i-1‍ψRk+1,Rk+ψR1,A)+IA(2)+ϕ1. Ri has est(ϕ2+ψB,Rm+∑k=im-1‍ψRk+1,Rk)+ϕ1e and est(ϕ1+ψA,R1+∑k=1i-1‍ψRk,Rk+1)+ϕ2e. However, Ri does not know IB(2) and IA(2) either, because Ri is more than half a wavelength from the other path.
From the previous analysis we know thatRi cannot agree on two different keys with A and B. Therefore, it cannot carry out MITM attack successfully. This analysis can be directly extended to the case that any number of intermediate nodes in the first path carry out MITM attacks collaboratively. Because their experienced channels are statistically independent of channels of the second path, they cannot gain any information of IB(2) or IA(2).
We conclude that the improved protocol is secure against any MITM adversaries in a single path.Remark 7.
If the adversary can place cheating nodes on two disjoint paths, there are straightforward ways to extend our protocol to achieve security. For example, we can consider using three disjoint paths betweenA and B. In general, in order to prevent cheating nodes on k disjoint paths, A and B can use k+1 disjoint paths between them for key extraction, as long as there exist k+1 disjoint paths between them. (If there are cheating nodes on all disjoint paths between A and B, then no solution is possible because these nodes can choose to simply block all communications between A and B.) This will lead to higher complexity of the protocol—so, there is a tradeoff between security and efficiency.


## 6. Performance Analysis

As the improved protocol has more than just a pair of nodes, the estimation errors at each intermediate node will aggregate. In this section we present performance analysis of the improved protocol. We mainly focus on the agreement probability ofA and B’s common secrets.From the protocol description, we know that the ideal values ofIA and IB are as follows:
(8)IA-=2ϕ2+ψB,Rm+∑i=2m‍ψRi,Ri-1+ψR1,A+ψB,Sn+∑i=2n‍ψSi,Si-1+ψS1,A+2ϕ1,IB-=2ϕ1+ψA,R1+∑i=1m-1‍ψRi,Ri+1+ψRm,B+ψA,S1+∑i=1n-1‍ψSi,Si+1+ψSn,B+2ϕ2.From the channel reciprocity and the assumption that one protocol round is performed within the channel coherence time, we can see thatIA-=IB-. We denote this value by I-; that is, I-=IA-=IB-. However, due to the estimation errors of the phase information, there may be discrepancies between IA and IB. In the following we analyze the probability of IA=IB during one protocol round. We denote this probability by Pr.When one node transmits signals to another node, they use the same frequency, so that the receiver does not need to do frequency estimation. Without loss of generality, the noises at the receivers are independent Gaussian noises with zero mean and varianceσ2. The receiver samples the received signal and computes the phase estimate. When the sampling rate is high enough, the estimated phase is a Gaussian random variable whose variance is bounded by the Cramér-Rao bound [47].From [47], when the signal frequency is known, the variance of the phase is bounded by
(9)σθ^2≥σ2b02N.In (9), b0 is the amplitude of the received signal. From (9), we can see that the lower bound of the phase variance depends on the signal to noise ratio (SNR) and the sampling rate. When the SNR is higher, the phase variance can achieve a smaller lower bound. When the sampling rate is increased at the receiver, the lower bound can be further decreased. This is in accordance with the intuition that we should get more precise estimation given a higher SNR and sampling rate. In the following we use the Cramér-Rao bound for our analysis.The estimation error at each node is modeled as a Gaussian noise, with the zero mean and standard deviation relying on the SNR and the sampling rate. Without loss of generality, we assume that the SNR and the sampling rate are all the same at all the participating nodes. From the protocol execution process, we know that the accumulated estimation error at the source or the destination is the sum of all the intermediate estimation errors. We can writeIB as
(10)IB=IB-+ZB.Z
B represents the accumulated estimation error at B. According to the previous analysis, ZB~N(0,(m+n+2)σθ^2). Because IB-=I-,  IB~N(I-,(m+n+2)σθ^2). For ease of analysis, let σI2=(m+n+2)σθ^2. From the protocol execution process, we know that IA~N(I-,σI2). Because I-∈[0,2π), from the property of Gaussian distribution, the probability is much higher when IB and IA are close to I-.The probabilityPr is a function of I-. It can be computed using the following equation:
(11)Pr=∑i=0q-1‍P[IA∈[2πiq,2π(i+1)q),IB∈[2πiq,2π(i+1)q)].Because of the independent noise accumulations atA and B, we can get
(12)Pr=∑i=0q-1‍P[IA∈[2πiq,2π(i+1)q)]×P[IB∈[2πiq,2π(i+1)q)].Denote the interval[2πi/q,2π(i+1)/q) by Qi. Let Pi(A,B)=P[IA∈Qi]P[IB∈Qi]. Then from the distribution function of Gaussian distribution, Pi(A,B)=∫IA∈Qi‍(1/2πσI)e-(IA-I-)2/2σI2∫IB∈Qi‍(1/2πσI)e-(IB-I-)2/2σI2. Because IA and IB have the same distributions, Pr can be computed by the following expressions:
(13)Pr=∑i=0q-1‍Pi(A,B),Pi(A,B)=(∫IA∈Qi‍12πσIe-(IA-I-)2/2σI2)2.From (13) we can see that Pr is the sum of the probability that IA and IB fall into the same quantization subinterval; that is, Pi(A,B),  i=1,2,…,q. For each subinterval Qi, the magnitude of Pi(A,B) is affected by whether I-∈Qi. Suppose that I-∈Qi*, and then Pi*(A,B) will be larger than any other Pi(A,B) for I-∉Qi. This is because the Gaussian distribution function has a larger value when the variable value is closer to the mean (in this case, I-). Therefore, Pr is dominated by Pi*(A,B), for I-∈Qi*. On the other hand, Pi*(A,B) is affected by I-’s position in Qi*. If I- is close to the center of Qi*, then Pi*(A,B) will be large; if I- is close to the end points of Qi*, then Pi*(A,B) will be small. This is because when I- is close to the end points, the probability that IA and IB fall into two adjacent subintervals increases. In addition, the standard deviation σI also has impact on Pi*(A,B). A smaller σI will result in a larger Pi*(A,B), because when σI is smaller, the probability of IA or IB being close to I- is larger.


## 7. Simulation Results

In order to measure the performance of the proposed scheme, we simulate the proposed scheme using GlomoSim [7]. By using the PARSEC programming language [48], we write programs for the proposed scheme in the physical layer of GlomoSim protocol stack. We simulate the proposed scheme for different SNRs. Because the receiver SNR is affected mainly by distances between adjacent nodes, we select a set of communication distances, which is {10 m, 20 m, 30 m, 40 m, 50 m, 100 m, 150 m, 200 m, 250 m, 300 m}. For each communication distance (denote it by l), we randomly generate a geometric distribution of 6 nodes. The distance between any pair of adjacent nodes is randomly generated in [0.7l,1.3l]. We denote these distances by {l1,l2,l3,l4,l5,l6}. Because we select 10 communication distances, we also generate 10 random distributions of nodes. One common node distribution for the simulation is shown in Figure 4. We measure average SNRs under different communication distances. The results are shown in Figure 5.Figure 4
One common node distribution of the simulation.Figure 5
Average SNRs under different communication distances.To best simulate the wireless communication environment in reality, we set the center carrier frequency to be 2.437 GHz and the baseband bandwidth to be 11 MHz. This is one of the standard carrier band of 802.11 b. According to Nyquist-Shannon sampling theorem, the sampling rate should be no less than 22 MHz. We choose the sampling rate to be 25 MHz, so that the estimation at the receiver is more accurate.TS is chosen to be 10 μs. For the large scale signal propagation, we use the two-ray ground reflection model [49] which can be expressed by (14)
(14)Pr(d)=PtGtGrht2hr2d4.
In (14), Pt is the transmission power, and Pr(d) is the received power at a distance d away from the transmission antenna. Gt and Gr are the antenna gains at the transmitter and the receiver, respectively; ht and hr are the antenna heights at the transmitter and the receiver, respectively; d is the distance between the transmitter and the receiver.We use the Rayleigh distribution [49] for the small scale wireless fading model. Both the two-ray ground reflection model and the Rayleigh fading model are directly supported by the GlomoSim network simulator [7].We measure the quantization agreement probability ofA and B under different communication distances. We also measure the randomness of the secret key. In addition, we measure the key efficiency of the proposed scheme. The results are shown in Sections 7.1, 7.2, and 7.3.


### 7.1. Quantization Agreement Probability

Under different communication distances, we measure quantization agreement probabilities and bit error rates (BERs) of the quantized common secret bits. For the quantization step, we chooseq=32. Therefore, the interval of [0,2π) is divided into 32 subintervals of equal length. We use the Gray code to encode the quantization indices, so that only one bit discrepancy is introduced for adjacent intervals.The results are shown in Figures6 and 7, respectively. From Figures 6 and 7, we can see that when the communication distance is 50 m (approximately 38.23 dB SNR), the quantization agreement probability is 0.9535, and the BER is 0.0093. Even when the communication distance is increased to 300 m (approximately 10 dB SNR), the quantization agreement probability is still 0.906, and the BER is 0.019.Figure 6
Quantization agreement probabilities under different communication distances.Figure 7
Bit error rates under different communication distances.


### 7.2. Randomness of the Generated Key

We test the randomness of the generated key using the NIST randomness test suite [50]. We use the 8 tests in the NIST test suite to validate the randomness of one 1024-bit key. The results are shown in Table 1. From Table 1 we can see that the generated key passes all the 8 tests.Table 1
NIST statistical test results. To pass each test, theP value needs to be greater than 0.01.
Test
P value
Frequency
0.70766
Block frequency
0.936991
Runs
0.658522
Longest run of ones
0.871862
FFT
0.066457
Serial
0.815653, 0.586988
Approximate entropy
0.323517
Cumulative sums (forward)
0.745842
Cumulative sums (reverse)
0.745842


### 7.3. Key Efficiency

In this section, we focus on measuring how long it takes in order to generate a 256-bit key. In order to generate a 256-bit key,A and B need to get more common secret bits, because the Cascade protocol causes entropy loss. We compute the lost entropy rate of Cascade protocol according to the theoretical results in [40]. After that we measure the key efficiency under different Cascade parameters.We have completely implemented the Cascade protocol and the privacy amplification method described in Section4.4. We use the MIRACL library to implement the prime generation and large number arithmetics required for 2-universal hash family. We choose 4~5 rounds for the Cascade protocol, in order that the key agreement ratio is high. We compute the entropy loss rate when the Round-1 block size has different values. For each Round-(i+1), its block size is two times the block size of Round-i. The results are shown in Figure 8.Figure 8
Lost entropy rates under different SNRs and Round-1 cascade blocks.As can be seen from Figure8, when the Round-1 block of Cascade protocol increases, the lost entropy rate decreases. When the communication distance decreases, the lost entropy rate also decreases, because less bits need to be corrected. For example, when the communication distance is 50 m and the round-1 block size is 14, the lost entropy rate is 0.1925. Under such a lost entropy rate, in order to generate a 256-bit key, at least 317 common secret bits need to be collected. When the communication distance is 300 m and the round-1 block size is 10, the lost entropy rate is 0.3203. Under such a lost entropy rate, in order to generate a 256-bit key, at least 376 common secret bits need to be collected.Under the 10 distributions generated for different communication distances, we measure the efficiency of generating a256-bit key using the multihop key agreement protocol. Different combinations of Cascade rounds and Round-1 block sizes are used. The simulation is run at a laptop with Intel Core2 CPU of 2.33 GHz and 2.0 GB memory. For each different setting, we run the key agreement scheme for 100 times and measure the average time. In all these executions, A and B achieve successful key agreement. The efficiency results are shown in Figure 9.Figure 9
Efficiency of key generation under different communication distances. The measured time is for generating a 256-bit key.From Figure9, we can see that when the Cascade Round-1 block size is decreased, the key efficiency is also decreased. This is because the block number is increased, which increases transferred bits in each round. Furthermore, when the number of Cascade rounds is decreased, the key efficiency is increased. Specifically, for the Cascade parameter (Block=12,Round=4), when the communication distance is 50 m, the time of generating a 256-bit key is 0.0726 seconds. At this speed, the proposed key agreement scheme can achieve 3.5Kbps rate. Even when the communication distance is 300 m, the proposed scheme can still achieve 3.17 Kbps rate.


## 7.1. Quantization Agreement Probability

Under different communication distances, we measure quantization agreement probabilities and bit error rates (BERs) of the quantized common secret bits. For the quantization step, we chooseq=32. Therefore, the interval of [0,2π) is divided into 32 subintervals of equal length. We use the Gray code to encode the quantization indices, so that only one bit discrepancy is introduced for adjacent intervals.The results are shown in Figures6 and 7, respectively. From Figures 6 and 7, we can see that when the communication distance is 50 m (approximately 38.23 dB SNR), the quantization agreement probability is 0.9535, and the BER is 0.0093. Even when the communication distance is increased to 300 m (approximately 10 dB SNR), the quantization agreement probability is still 0.906, and the BER is 0.019.Figure 6
Quantization agreement probabilities under different communication distances.Figure 7
Bit error rates under different communication distances.


## 7.2. Randomness of the Generated Key

We test the randomness of the generated key using the NIST randomness test suite [50]. We use the 8 tests in the NIST test suite to validate the randomness of one 1024-bit key. The results are shown in Table 1. From Table 1 we can see that the generated key passes all the 8 tests.Table 1
NIST statistical test results. To pass each test, theP value needs to be greater than 0.01.
Test
P value
Frequency
0.70766
Block frequency
0.936991
Runs
0.658522
Longest run of ones
0.871862
FFT
0.066457
Serial
0.815653, 0.586988
Approximate entropy
0.323517
Cumulative sums (forward)
0.745842
Cumulative sums (reverse)
0.745842


## 7.3. Key Efficiency

In this section, we focus on measuring how long it takes in order to generate a 256-bit key. In order to generate a 256-bit key,A and B need to get more common secret bits, because the Cascade protocol causes entropy loss. We compute the lost entropy rate of Cascade protocol according to the theoretical results in [40]. After that we measure the key efficiency under different Cascade parameters.We have completely implemented the Cascade protocol and the privacy amplification method described in Section4.4. We use the MIRACL library to implement the prime generation and large number arithmetics required for 2-universal hash family. We choose 4~5 rounds for the Cascade protocol, in order that the key agreement ratio is high. We compute the entropy loss rate when the Round-1 block size has different values. For each Round-(i+1), its block size is two times the block size of Round-i. The results are shown in Figure 8.Figure 8
Lost entropy rates under different SNRs and Round-1 cascade blocks.As can be seen from Figure8, when the Round-1 block of Cascade protocol increases, the lost entropy rate decreases. When the communication distance decreases, the lost entropy rate also decreases, because less bits need to be corrected. For example, when the communication distance is 50 m and the round-1 block size is 14, the lost entropy rate is 0.1925. Under such a lost entropy rate, in order to generate a 256-bit key, at least 317 common secret bits need to be collected. When the communication distance is 300 m and the round-1 block size is 10, the lost entropy rate is 0.3203. Under such a lost entropy rate, in order to generate a 256-bit key, at least 376 common secret bits need to be collected.Under the 10 distributions generated for different communication distances, we measure the efficiency of generating a256-bit key using the multihop key agreement protocol. Different combinations of Cascade rounds and Round-1 block sizes are used. The simulation is run at a laptop with Intel Core2 CPU of 2.33 GHz and 2.0 GB memory. For each different setting, we run the key agreement scheme for 100 times and measure the average time. In all these executions, A and B achieve successful key agreement. The efficiency results are shown in Figure 9.Figure 9
Efficiency of key generation under different communication distances. The measured time is for generating a 256-bit key.From Figure9, we can see that when the Cascade Round-1 block size is decreased, the key efficiency is also decreased. This is because the block number is increased, which increases transferred bits in each round. Furthermore, when the number of Cascade rounds is decreased, the key efficiency is increased. Specifically, for the Cascade parameter (Block=12,Round=4), when the communication distance is 50 m, the time of generating a 256-bit key is 0.0726 seconds. At this speed, the proposed key agreement scheme can achieve 3.5Kbps rate. Even when the communication distance is 300 m, the proposed scheme can still achieve 3.17 Kbps rate.


## 8. Conclusions and Discussions

In this paper, we propose two key agreement schemes as a novel physical-layer technique in multihop wireless networks. The proposed key agreement schemes enable secret key generation between nodes in multihop wireless networks, even if they cannot communicate with each other directly. The proposed basic scheme is secure against external eavesdroppers. And the improved two-path-based scheme is secure against external eavesdroppers, as well as internal eavesdroppers and MITM adversaries in a single path. The proposed scheme can achieve high key efficiency under different communication distances among nodes. The secret key generated by the proposed scheme has very strong randomness. By properly selecting the protocol parameters, the proposed scheme can achieve high success ratio. The proposed scheme is suitable for establishing secret keys for multihop wireless networks.It is worth noting that our paper has covered only key agreement for unicast communications between two nodes. Broadcast and multicast communications may require different protocols for key agreement. In particular, key agreement for broadcast communications in a wireless network is relatively easy if there are only passive eavesdroppers. A straightforward solution is to establish key agreement between neighbor nodes and then transmit a global key in encrypted form throughout the network. If some nodes in the network are dishonest, then leaking the final global key is unavoidable.For multicast communications, this problem becomes the pretty challenging problem of group key agreement. Existing solutions such as Wang et al.’s [34] are suitable for this case, but further improvement in security and/or efficiency is also possible.



---

*Source: 935604-2013-05-20.xml*