The Vault

Extracting a Cryptographic Key from an Unauthenticated Wireless Channel
Research Paper / Jan 2008


Extracting a Cryptographic Key from an Unauthenticated
Wireless Channel

ABSTRACT
We describe a simple protocol that allows two parties, Alice
and Bob, communicating on a point-to-point wireless link,
to establish a common cryptographic key. The established
key can then be used to encrypt messages exchanged by Al-
ice and Bob using standard symmetric key algorithms such
as Rijndael, DES, etc. The protocol allows Alice and Bob
to regularly refresh their keys. It resists cryptanalysis of the
generated key by an eavesdropping adversary Eve and unlike
previous key-agreement schemes, does not require that Al-
ice and Bob share an authenticated channel. The presence
of a man-in-the-middle adversary can be detected much as
in quantum key distribution systems. The performance of
our algorithm is numerically evaluated and supported by a
measurement based study using reciprocity measurements
on wireless channels. A proof-of-concept model built using
existing 802.11 radios is demonstrated.

1. INTRODUCTION
As wireless devices become increasingly pervasive and es-

sential, they are becoming both a target for the attack and
the very weapon with which such an attack can be carried
out. Traditional high-level computer and network security
techniques can, and must, play and important role in com-
bating such attacks. Accordingly, there have been numerous
attempts to make wireless platforms secure by migrating tra-
ditional network security strategies to the wireless domain.
But the wireless environment presents both the means and
the opportunity for new forms of intrusion, and in spite of
concerted efforts, the development of secure wireless proto-
cols has proven to be a very elusive goal - a fact that is
supported by the numerous recent papers that reveal suc-
cessful security attacks on many wireless security protocols.
[REFS] . Perhaps the most fundamental reason why wire-
less systems have been difficult to secure stems from the
broadcast nature of the medium itself, which facilitates both
eavesdropping and easy network intrusion. As a result, tech-
niques which would provide a high level of security in a wired

Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.

network are demonstrably inadequate in a wireless network.
Although conventional cryptographic security mechanisms

are essential to the overall problem of securing wireless net-
works, these techniques do not directly leverage the unique
properties of the wireless domain to address security threats.
The properties of the wireless medium are a powerful source
of domain-specific information that can be used to comple-
ment and enhance traditional security mechanisms. In this
paper, we propose a cross-layer approach to the problem
of protecting confidentiality on wireless links. Specifically,
we propose to utilize the unique space, time and frequency
characteristics of the physical layer, in combination with
traditional higher-layer cryptographic techniques to enhance
confidentiality. In the following sections we explain how the
uniqueness of the radio path between two devices in the net-
work, and its rapid decorrelation with distance, provides a
basis for the selection of shared secrets, such as higher layer
encryption keys, even in the presence of an eavesdropper.
It is important to recognize that these new approaches are
intended to augment, rather than to replace existing, cryp-
tographic security mechanisms- they provide an additional
layer of protection uniquely suited for the very networks that
are most likely to be compromised.

The enabling factor in our approach is that in the rich
multi-path environment typical of wireless channels, the re-
sponse of the medium between any transmit-receive path
is frequency-selective (or in the time domain dispersive) in
a way that is location specific. The wireless channel be-
tween two radios, Alice and Bob, is a random, time-varying,
stochastic process, causing the signal received at one end
to be a randomly scaled version of the transmitted signal.
In addition, the received signal contains additive receiver
noise. This phenomenon, commonly termed fading, is due
to the effects of multipath propagation. It has been shown
to be often well modelled by Rayleigh or Ricean distributed
stochastic processes. [REF] Since the paths taken by a signal
to travel from Alice to Bob are the very same paths taken by
a signal from Bob to Alice at any given time, electromagnetic
waves follow the principle of reciprocity. Therefore, the scal-
ing factor for a signal due to the fading process from Alice to
Bob at any given time is also the scaling factor for a signal
from Bob to Alice at that time. The fading process between
two users is highly sensitive to the spatial position of the
users and quickly decorrelates away in space. Therefore, an
adversary, Eve, who is more than an order of a wavelength
away from both Alice and Bob experiences fading channels
to Alice and Bob that are statistically independent of the
fading channel between Alice and Bob. For example, at a



Alice RANDOMLY VARYING CHANNEL BETWEEN
ALICE AND BOB

Bob

Eve

Figure 1: Alice and Bob can use the specificity of the

time-varying channel between themselves to extract

a key without letting Eve learn the key.

frequency of 2.4 Ghz, we only require that Eve be of the
order of

λ =
c

f
=

3× 108
2.4× 109 = 12.5 cm (1)

away from Alice and Bob.
The reciprocity of a wireless channel along with the spe-

cific nature of the fading process between two points can be
exploited to generate a common, secret cryptographic key at
Alice and Bob such that Eve gets absolutely no information
about the generated key. The generated key could then be
used to encrypt messages exchanged by the users using stan-
dard symmetric cryptographic algorithms such as Rijndael
or DES.

In Section 2 we describe the prior work in this area, in
Section 3 we describe our system model, in Section 4 we
describe the algorithm we propose, in Section 5 we explain
the details of a quantizer that we use for our algorithm in
Section 4, along with a numerical evaluation of the perfor-
mance of our algorithm and an analytical model for opti-
mizing performance, and finally in Section 6 we provide a
detailed experimental study for studying reciprocity of wire-
less channels using a network analyzer for indoor channel,
a GNUradio setup and a proof-of-concept system using off-
the-shelf commercial 802.11 radios.

2. RELATED WORK
In common randomness , Maurer introduces the problem

of generating identical keys based on correlated information
available to two users such that a third eavesdropping user
does not learn anything about the generated key. This was
followed almost immediately and independently by [3]. Since
then, a large body of work has explored the information
theoretic limits and possibilities of using correlated random
variables to extract identical keys under various system as-
sumptions. When Alice and Bob share an authenticated
public channel in addition to correlated information, then
secret key agreement has been shown to be possible [15, 3]
and efficient protocols have been designed [5, 6] to allow
them to exchange messages to derive a key about which the
adversary has negligibly little information. The standard
method for generating identical secret keys at Alice and Bob
under such an assumption [8, 14, 5, 21] may be described,

for the sake of completeness, through the following steps 1:

1. Advantage distillation [15, 7]: Generation of cor-
related information at Alice and Bob, such that Alice
and Bob share greater information than Alice and Eve
or Bob and Eve. Mathematically speaking, if the in-
formation possessed by Alice, Bob and Eve is repre-
sented by Xa,Xb and Xe then the mutual information
between Alice and Bob must greater than that between
Alice and Eve or Bob and Eve.

I(Xa;Xb) > I(Xa,Xe) (2)

I(Xa;Xb) > I(Xb, Xe) (3)

Alice and Bob may convert their information into bits.

2. Information Reconciliation [5]: Alice and Bob then
exchange error-correcting messages over a public chan-
nel (available to Eve) that allow them to settle on an
identical string of bits. However, the messages reveal
a certain amount of information about the bits to Eve.
When the correlated information Xa and Xb possessed
by Alice and Bob is derived from continuous random
variables, quantization using a function Q(Xa) is re-
quired. Reconciliation may be one-way (Alice sends a
message M = f(K) to Bob, where K = Q(Xa) and

Bob determines bK = g(Xb,M)) or interactive, such as
an exchange of parities of subsets of the bits possessed
by Alice and Bob.

3. Privacy amplification [4]: Alice and Bob apply a se-
quence of hash functions to their bits (i.e. they discard
some of their bits) to remove Eve’s partial information
about their bits at the expense of reducing the num-
ber of bits that they share. Eve has negligibly little
information about the remaining identical bit strings
shared by Alice and Bob.

In order to have Alice and Bob generate a common key about
which Eve has no information we require that

H(K|Xe,M) = H(K), (4)
where K is the key, M denotes the messages exchanged
between Alice and Bob and H(.) denotes the entropy or
uncertainty of the adversary. Efficient protocols for infor-
mation reconciliation [5, 6], suitable error-correcting mech-
anisms [14] and hashing functions for privacy amplification
[REFs] have been developed. However, a central assump-
tion in this entire body of work is that Alice and Bob have
an authenticated channel available to them even before the
process of key agreement begins. This is an unrealistic as-
sumption in practice because the availability of an authen-
ticated channel implies that Alice and Bob already share a
secret key to begin with. Therefore, the purpose of gen-
erating a common secret key is defeated. The absence of
an authenticated channel implies that the process of infor-
mation reconciliation is open to a man-in-the middle type
attack. It is worth exploring therefore, whether it is possi-
ble to entirely do away with the reconciliation stage, thus
also doing away the requirement of a authenticating chan-
nel. In our work, we explain how the wireless medium and

1Much of this work was done in the context of quantum key
distribution. For a more complete bibliography on quantum
key distribution see [Give REF]



the phenomenon of fading allows us to do just this. We show
that it is possible to use the fundamental properties of the
wireless physical medium to generate with very high proba-
bility identical keys at Alice and Bob, without requiring that
an authenticated channel already exist between them, while
giving away absolutely no information about an adversary.

In [16, 17, 18], Maurer and Wolf explore under what con-
ditions it is possible for Alice and Bob to extract a common
secret key without having to assume the availability of an
authenticated channel between them in terms of the joint
probability distribution PXa,Xb,Xe(hˆa, hˆb, xe) of the infor-
mation possessed by Alice, Bob and Eve. They express this
condition as the non-simulatibility condition, which states
that it is possible for Alice and Bob to generate identical
secret keys without requiring an authenticated channel if
and only if the joint distribution PXa,Xb,Xe(hˆa, hˆb, xe) is
such that Eve cannot generate a message X ′a at Bob such
that Bob cannot distinguish between the joint distribution
PX′a,Xb(hˆ


a, hˆb) and PXa,Xb(hˆa, hˆb).

In [14, 21, 8], Alice, based on her information Xa and
its quantized version Q(Xa) sends an error-correcting code
α(Q(Xa)) to Bob which Bob then uses along with his own
information Xb to decode as β(Xb, α(Xa)). Here α(.) can be
thought of as a source code with side information such that
β(.) is the decoding function and Xb is the side information.
This unidirectional message from Alice to Bob is aimed at
reconciliation again assumes that an authenticated channel
is available and reveals a certain amount of information to
Eve, which must then be wiped out through privacy ampli-
fication.

In [12, 13], a method for secret key agreement has been
proposed based on phase reciprocity of frequency selective
fading channels. While this is an attractive theoretical model,
it is difficult to implement or evaluate in practice because
phase information is difficult to harvest from existing hard-
ware platforms. However, the work in [12, 13]provides an
important insight, namely that the generation of correlated
information (advantage distillation) at Alice and Bob in the
context of a wireless channel can be accomplished very sim-
ply by merely having them estimate the channel to one an-
other and relying on reciprocity. In the following section we
explain this principle in detail and also how this allows us
to do away with an explicit reconciliation stage for wireless
channels.

Our contribution in this paper may be summarized as fol-
lows:

1. We translate information-theoretic ideas developed in
the past into a practical protocol applied to wireless
channels,

2. We build a simple algorithm that, unlike prior schemes,
does not require an authenticated channel to begin
with,

3. Provide a proof-of concept model built on coarse mea-
surements using existing off the shelf 802.11 radios,
and a more detailed measurements study using chan-
nel impulse responses made using the 802.11 packet
preambles.

Using our measurements, we argue that existing radio plat-
forms already provide for valuable information from the phys-
ical layer which is discarded for data communications but

Figure 2: The multipath profile for a signal travelling from

Alice to Bob is different from the that for the signal reaching

Eve.

which can be profitably utilized in deriving the benefits of
enhanced confidentiality and authentication services.

3. SYSTEM MODEL & DESIGN ISSUES
The idea behind using the wireless channel for secret key

generation is that it allows two users Alice and Bob to ex-
change messages on a public channel and yet keep the mes-
sages hidden from adversaries. This is because the messages
exchanged are simply probe signals that allow Alice and Bob
to estimate the channel between each other. Due to rapid
spatial decorrelation of the channel, is it not possible for an
adversary who is located more than an order of a wavelength
away from both Alice and Bob to guess the value of these
estimates.

One way to exploit this unique property of the wireless
medium is to allow Alice and Bob to estimate a statistical
measure of the channel between them, for e.g. the mean
signal-strength or perhaps the variance of the Q-component
of the received signal. If the channel is stationary2, then
their estimates would each converge to the true value with
time. In this way, Alice and Bob will each have knowledge
about a number, namely the estimated statistical measure,
without having actually sent messages containing this num-
ber over the wireless link. They may then quantize their
estimate to generate a common bit string at their respective
ends. If the estimated quantity lies in the same quantizer bin
at Alice and Bob, then they would have generated identical
bits.

However, the problem with using a long-term statistical
measure of a wireless channel to derive a cryptographic key is
that knowledge of the locations of the users Alice and Bob
and their environment may be sufficeint for an adversary,
Eve, to infer the statistics of the channel between them. In-
deed publicly available tools such as the WISE ray-tracing
tool [10, 11] make it a simple matter to predict the signal
statistics at a receiver given the knowledge of the the loca-
tions of the transmitter and receiver ad the layout of the
environment.

We therefore employ an approach which incorporates the
reciprocity of wireless channels while avoiding statistical mea-
sures from directly influencing the outcome of the secret key
generation process. Let h(t) be a time-varying, stochastic

2By stationary, we mean a channel whose stochastic charac-
teristics do not vary significantly over the time duration of
the key extraction protocol.



parameter of the channel between Alice and Bob. For the
purpose of our discussion, we shall assume that h(t) is the
magnitude of the transfer function of the multipath fading
channel between Alice and Bob evaluated at a fixed test
frequency f0. Implicit in this formulation is the observa-
tion that the system transfer function of the channel is the
same in the Alice →Bob direction as in the Bob→Alice di-
rection at a given instant of time. This follows from reci-
procity, which is a fundamental property of electromagnetic
waves. In order to estimate h(t), Alice and Bob must trans-
mit known probe signals to one another. Each party can
then use the received signal along with the known probe
signal to compute an estimate of the parameter h. Unfortu-
nately, practical radios cannot transmit and receive signals
at the same frequency at he same time due to constraints
imposed by the hardware. In other words, practical radios
are half duplex. This implies that Alice must wait to re-
ceive a probe signal from Bob before she can transmit her
probe to him and vice-verse. In the time delay between the
two successive probes, the parameter h changes in a ran-
dom manner. The received signal at Alice and Bob due to
successive probe signals may be written as

ra(t1) = s(t1)h(t1) + na(t1) (5)

rb(t2) = s(t2)h(t2) + nb(t2), (6)

where s is the known probe signal (for e.g. s may be a
pure sinusoid at the test frequency f0), na and nb are the
independent noise processes added at Alice and Bob respec-
tively, and t2−t1 = τ is the time lag of the probe received at
Bob from Alice with respect to the probe received by Alice
from Bob. Using the received signal, Alice and Bob, each
compute estimates of the parameter h:

hˆa(t1) = h(t1) + za(t1) (7)

hˆb(t2) = h(t2) + zb(t2), (8)

where za and zb represent the noise terms na and nb respec-
tively after having been processed by the estimator for h.
We do not go into the details of designing a good estima-
tor function for h. Even though the estimates hˆa and hˆb
are in all likelihood unequal, due in part to the the inde-
pendent additive noise terms and in part to the time lag τ ,
they may be highly correlated. This means that if we man-
age to send probes between Alice and Bob at a fast enough
rate3, such that τ is small, then we may be able to push the

quantityE
h
hˆahˆ


b

i
significantly above zero. Then, by repeat-

edly sending probes to one another in an alternating man-
ner over the time-varying channel, Alice and Bob generate
a sequence of n estimates hˆa = {hˆa[1], hˆa[2], . . . , hˆa[n]} and
hˆb = {hˆb[1], hˆb[2], . . . , hˆb[n]} respectively, that are highly
correlated with one another. An adversary Eve can over-
hear the probe signals sent by each of them. The signals
received by Eve from Alice and Bob respectively are

rae (t1) = s(t1)hae(t1) + ne(t1) (9)

rbe(t2) = s(t2)hbe(t2) + ne(t2), (10)

where hae and hbe denote the channel between Alice and Eve
and between Bob and Eve respectively and ne is the noise
added at Eve. If Eve is more than an order-of-a-wavelength

3‘Fast enough’ is in relation to the rate at which the channel
is changing, as we shall see in detail in the following sections.

away from both Alice and Bob, then hae and hbe are com-
pletely uncorrelated with h. Therefore, even with knowledge
of the probe signal s used by Alice and Bob, she cannot use
her received signals to compute meaningful estimates of the
Alice-Bob channel, h.

How can Alice and Bob use their respective sequences of
channel estimates to extract identical bit-strings? Further,
the bit strings they generate must be suitable for use as
cryptographic keys. This means that they must be:

1. Suitably long - 128 bits keys are commonly used in
symmetric encryption algorithms. So they should be
able to generate at least these many bits.

2. Statistically non-trivial - The keys should be equally
likely with the probability of a ‘0’ being equal to the
probability of a ‘1’. Also, they must not have any sig-
nificant autocorrelation properties. This means that
they must appear as pseudo-noise sequences on aver-
age.

The second requirement above is important to guarantee
that the generated key cannot be easily cracked by an ad-
versary and that the key generation process does not reveal
any prior information about the keys to an adversary. That
is, an N-bit key must really provide N bits of uncertainty
to an adversary who only knows how the keys are made.

We now briefly describe how the above objectives can be
met, while postponing a formal description of our algorithm
to Section 4. The sequence of channel estimates hˆa and hˆb
are really sequences of random variables, drawn from an un-
derlying probability distribution that characterizes the ran-
dom channel parameter h, and are correlated across different
time samples. This means that the channel estimates com-
puted by each user follow a correlation law across different
time-samples and the channel estimates of Alice are corre-
lated with those of Bob. The second observation follows
from the first since the channel estimates of Alice and Bob
can be thought of as being a single sequence of estimates
of the same time-varying parameter h, with alternate esti-
mates belonging to Alice and Bob. We assume that h is
a Gaussian random variable and the underlying stochastic
process h(t) is a stationary Gaussian process with a corre-
lation function described by a Bessel function of the zeroth
order and first kind. A Gaussian distribution for h may be
obtained, for example, by considering h to be the magnitude
of the in-phase component of the received signal assuming a
Rayleigh fading process between Alice and Bob due to the
presence of a suitably rich scattering environment. [REF
to a book describing fundamentals of fading]. It must be
noted that assuming a Gaussian distribution on h is for ease
of discussion and our algorithm would work in the general
case.

Since the channel estimates computed by Alice and Bob
are continuous random variables and we need to extract bits,
it is natural to expect that Alice and Bob would need to
quantize their estimates using some quantizer function Q(.).
However, it is not sufficient to simply quantize the estimates
and use the resulting bits are a key because it is highly un-
likely that the bit strings generated by Alice and Bob in
this way would be identical. This means Alice and Bob
must exchange messages over the public channel to recon-
cile their correlated information. But how can Alice and
Bob exchange messages without revealing some information



0 0.5 1 1.5 2 2.5 3 3.5
−25

−20

−15

−10

−5

0

5

10

Time (Seconds)

R
ay

le
ig

h
W

SS
US

P
ro

ce
ss

(d
B)

Maximum doppler frequency = 10Hz

Figure 3: A sample realization of a Rayleigh fading

stochastic process. Amplitude on a dB scale.

to Eve? Further, any protocol that involves exchange of
messages of the public, unauthenticated channel must also
address the problem of a man-in-the middle attack by Eve.

Fortunately, there is a way to allow Alice and Bob to rec-
oncile their information without revealing any information
to Eve, while precluding a man-in-the-middle type attack.
Even though Alice and Bob do not share a key that can
be used for authentication, they do share a large amount of
common information in the form of the sequence of channel
estimates. This can be used to provide reconciliation and
authentication simultaneously.

Alice and Bob use the statistics of their respective chan-
nel estimates to determine a scalar, q that serves as a ref-
erence level for quantizing the channel estimates into bits.
Alice then parses through her sequence of channel estimates
hˆa to determine the locations of excursions of her chan-
nel estimates above the level q or below q− that are of
duration greater than or equal to m samples. She sends
Bob a message over the public channel containing the loca-
tions of such excursions in the form of an array of indexes
L = {l1, l2, . . . , lk}. Bob then checks his own sequence hˆb
at the locations specified by the indexes in L to see whether
it contains an excursion above the level q or below q− for
a duration greater than or equal to m samples, i.e whether
hˆa(li) is part of such an excursion that spans m or more
values, for each i = 1, . . . , m. Each index lj that does not
produce such an excursion at Bob’s end is placed into an ar-
ray L˜ and sent back to Alice in a public message from Bob.
Each side drops these indexes from consideration. The re-
maining indexes L′ = L\L˜ are used by each side to compute
a sequence of bits as Q(hˆa(L

′)) and Q(hˆa(L
′)), where

Q(x) =


1 if x > q+
0 if x < q−

(11)

If Q(hˆa(L
′)) = Q(hˆa(L

′)) then Alice and Bob have suc-
ceeded in generating identical keys. We show that provided
the level q and the parameter m are properly chosen, the
probability that the bit strings Q(hˆa(L

′)) and Q(hˆa(L
′))

are equal is extremely high.

An important quantity of interest in the bit-extraction
process described above is the rate of generation of secret
bits. We express rate in secret-bits per second or s-bits/sec.
Later, in Section ?? we express rate in s-bits per observation
in the context of optimizing the quantizer Q(.). Naturally, it
is desirable that Alice and Bob achieve a high rate of secret
bit extraction, however, we are especially wary of errors. If
the sequence Q(hˆa(L

′)) is different from Q(hˆb(L
′)) even by

a single bit, then the two strings cannot be used as cryp-
tographic keys and consequently the entire protocol must
be repeated. We would like the bit error probability to be
extremely low, so that the probability that the keys gen-
erated by the two users do not match is acceptably small.
For example, in order to have a key-mismatch probability
of pk = 10

−6, assuming 128 bit long keys, we must target a
bit-error probability pe where

pk = 1− (1− pe)128, (12)
which gives pe ∼ 10−8. The rate at which secret bits can
be extracted from the channel is fundamentally limited by
the rate of variation int he channel. We quantify this varia-
tion by the Doppler frequency, fd. In a fading channel, the
Doppler frequency determines the both the rate at which
the channel varies and the magnitude of the swings. A sim-
ple measure of the amount of Doppler in a given wireless
environment is given by

fd ∼ v
λ
, (13)

where v is a measure of the effects of user mobility and the
dynamic environment around the users expressed in meters
per second and λ is the wavelength of the carrier wave at
frequency of communications. In our case λ = c

f0
. In can

be seen intuitively that increasing the value of q or m would
result in a lower rate in s-bits/sec. but also a lower prob-
ability of error. Intuitively, this is because a larger value
of q makes is less likely that while the Alice’s channel esti-
mates lie above the level q+, Bob’s estimates like below q−
or vice-verse, but excursions of the parameter h above the
increased q+ (or below q−) become less frequent, thereby
decreasing the number of secret bits that can be generated
per second. Further, a larger value of m provides greater
protection from errors since the likelihood of the channel
estimates of Alice and Bob, interleaved in time, falling in
different intervals of the quantizer Q(.) above, decreases -
however, this must come at the cost of reduced rate since
excursions of h of longer duration are required. Thus, there
is a tradeoff between rate and probability of error and the
parameters q and m in the above description of out proto-
col provide convenient controls to select a suitable operating
point over this tradeoff.

4. ALGORITHM
Our basic algorithm can be described via the following

steps:

1. Alice parses through her vector hˆa to find instances
where m or more consecutive samples lie above the
level q+ or below q−. Such an occurrence is referred
to as an excursion above the level q+ or below q− re-
spectively. She notes down the location of all such
instances.



Table 1: A summary of the notation used

fd Doppler frequency (Hz)
fs Channel probe rate (Hz)
q The quantizer bin boundary
m # of consecutive samples reqd. in the same bin
N Length of key in bits
Rk Rate at which secret bits are collected (bits/sec)
pe Probability of a bit error

pk Probability of key mismatch = 1− (1− pe)N
h(t) Value of the stochastic process h at time t
s(t) Probe signal transmitted to estimate h(t)

2. Alice selects a random subset of these instances and
sends Bob the index of the channel estimate lying in
the center of the excursion for each of the selected in-
stances. For example, if hˆa is > q+ at indexes i = 35
to i = 43 and m = 5 then she sends Bob the index
i = 39.

3. Bob checks whether his own vector of channel esti-
mates hˆb contains at least m − 1 channel estimates
centered around the index sent by Alice that lie in an
excursion above q+ or below q−. In our example, Bob
would check whether hˆa is > q+ or < q− from i = 37
to i = 41 inclusive.

4. Bob replies to Alice with a subset of the indexes sent
by her at which his vector hˆb does not contains at least
m−1 successive estimates in one of the two excursions.
These indexes are discarded by each user. We shall
henceforth refer to these indexes as bad indexes.

5. Bob and Alice compute Q(ha) and Q(hb) respectively
at the remaining indexes, in increasing order of the
indexes, thus generating a bit string.

Since the stationary stochastic process h(t) between Al-
ice and Bob has an inherent statistical basis, the selection of
each excursion above q+ and below q− may result in the gen-
eration of a key that suffers from non-randomness that can
be attributed to the statistical structure inherited from the
stochastic process itself. Intuitively, the stochastic process
h(t) contains a certain predictability because of a known cor-
relation structure and an attacker who knows that key bits
are generated from each successive excursion, may be able
to infer additional information about the key. The random
selection of a subset of indexes by Alice before she sends
them to Bob is therefore necessary to destroy this correla-
tion structure.

4.1 Detecting a man-in-the middle attack
Since Alice and Bob do not have an authenticated channel

between themselves to begin with, the exchange of messages
in the protocol described above is susceptible to an active
adversarial attack. Accordingly, Eve may play the role of a
’man-in-the-middle’ wherein she spoofs herself to be Alice
and sends a fake POS′ message to Bob. This was effec-
tively disrupt the protocol and Alice and Bob would never
be able to generate identical keys. Eve would have therefore
succeeded in carrying out a kind of denial attack without re-
vealing her presence to the two users. Alternately, Eve could
spoof herself to be Bob by sending a fake POS REPLY

Data: hˆa and hˆb
for i = 1 to length(hˆa) do

if Q(hˆa[i]) = Q(hˆa[i+1]) = . . . = Q(hˆa[i+m−1]) then
KEY ← [KEY hˆa[i]]
POS ← [POS i]
i← i+m

else
i← i+ 1

end

end

POS′ = Random subset of POS
Alice sends POS′ to Bob on PUBLIC CHANNEL.

POS REPLY = POS′;
for j = 1 to length(POS’) do

if Q(hb[POS
′(j)]) = . . . = Q(hb[POS

′(j)+m−2]) then
POS REPLY ← [POS REPLY \ POS′(j)]

end

end

Bob send POS REPLY to Alice on PUBLIC CHANNEL.

Ka = hˆa(POS
′\POS REPLY )

Kb = hˆb(POS
′\POS REPLY )

Algorithm 1: The basic level crossing algorithm

message to Alice, again resulting in disruption of the proto-
col.

Fortunately, the common information at Alice and Bob
provides a way to build authentication into the key extrac-
tion protocol. It is important to recognize that the message
sent by Alice to Bob is, in a way, self-authenticating. Even
though Bob’s channel estimates vector hˆa may not contain
excursions at a number of indexes sent by Alice to Bob in the
POS′ message, it is expected that the fraction of positive
results in Bob’s vector from among the indexes sent by Alice
would be significantly greater than 1

2
. On the other hand, if

an adversary had injected a false POS′ message containing
randomly chosen indexes, then the fraction of indexes that
produced positive results at Bob would evaluate roughly to
0.5. Therefore, Bob can use this simple test to check for
the presence of an active adversary. If the fraction of useful
indexes evaluate significantly close to 0.5, he concludes that
a man-in-the middle attack is being carried out against him
and terminates the protocol.

A similar situation exists with respect to the message sent
from Bob to Alice containing a list of indexes that are to be
discarded. After the list of indexes to be discarded has been
computed by Bob, he can compute a string of bits which,
he knows, Alice will also be able to generate once she re-
ceives the list of indexes to be discarded. A certain fraction
of these bits can then be used for authentication. For ex-
ample, suppose this fraction is fixed to be 1

2
in the protocol,

then Bob takes the first half of the generated bits as the
secret cryptographic key that is the output of the protocol
and the second half of the bits are used as an authentication
key. He then computes a hash4 of the message containing

4Any standard hash function may be used, for e.g. MD5 or



the list of indexes to be discarded, and signs the hash with
the authentication key. Alice, upon receiving the list of dis-
carded indexes and its signed hash, can then discard the
relevant indexes, compute bits from the remaining indexes
and thereby compute the authentication key and the crypto-
graphic secret key. She can then decrypt the signed hash and
verify that it came from Bob. Therefore, even without an
authenticated channel, it is possible, with some loss in the
number of secret bits that are ultimately produced as the
output of the protocol, to detect active adversarial attacks.
A modified version of the secret key extraction algorithm is
presented as Algorithm 2.

Data: hˆa and hˆb
Alice:

for i = 1 to length(hˆa) do

if Q(hˆa[i]) = Q(hˆa[i+1]) = . . . = Q(hˆa[i+m−1]) then
KEY ← [KEY hˆa[i]]
POS ← [POS i]
i← i +m

else
i← i + 1

end

end

POS′ = Random subset of POS
Alice sends POS′ to Bob on PUBLIC CHANNEL.

Bob:

POS REPLY = POS′;
for j = 1 to length(POS’) do

if Q(hb[POS
′(j)]) = . . . = Q(hb[POS

′(j)+m−2]) then
POS REPLY ← [POS REPLY \ POS′(j)]

end

end

if
n

|POS REPLY |
|POS′|

< 0.5 + ǫ
o
then

TERMINATE PROTOCOL

end

good indexes = POS′\POS REPLY ;
L = length(good indexes);

Kb = hˆb(good indexes(1 : L/2))

Kau = hˆb(good indexes(L/2 : L)))
Package = {good indexes,EKau(hash(good indexes))}
Bob send Package to Alice on PUBLIC CHANNEL.

Alice:

Ka = hˆa(good indexes(1 : L/2))

Kau = hˆb(good indexes(L/2 : L)))

if
n
E
K
−1
au

(Hash(good indexes)) 6= Hash(good indexes)
o

then
TERMINATE PROTOCOL

end

Algorithm 2: Modified algorithm exploiting the self-
authenticating property

The modified algorithm may be described through the fol-
lowing steps:

1. Alice parses through her vector hˆa as before to find in-

SHA-1.

stances where m or more consecutive samples lie above
the level q+ or below q−. She notes down the location
of all such instances.

2. Alice selects a random subset of these instances as in
the basic algorithm and sends Bob the index of the
channel estimate lying in the center of the excursion
for each of the selected instances.

3. Bob checks whether his own vector of channel esti-
mates hˆb contains at least m − 1 channel estimates
centered around the index sent by Alice that lie in an
excursion above q+ or below q−.

4. To make sure that the message received is really from
Alice, Bob computes the fraction on indexes sent by
Alice that result in a positive result according to his
own channel estimate vector hˆb. If this fraction is sig-
nificantly close to 0.5, Bob concludes that the message
was not really sent by Alice implying that a man-in-
the-middle attack is in progress, and the protocol is
halted.

5. If the authentication check above passes, Bob replies
to Alice with a message containing those indexes sent
by her where his vector hˆb does not contain at least
m − 1 successive estimates in one of the two excur-
sions. These indexes are discarded by each user. Fur-
ther, Bob uses the remaining M indexes in the follow-
ing manner: He computes the binary function Q(hˆb)
at the M indexes to obtain M bits. The first M/2 bits
are kept as the cryptographic key that is the output
of the protocol. The remaining M/2 bits are used as
an authentication key to encrypt a hash of the list of
bad indexes sent by Bob to Alice. Therefore the over-
all message sent from Bob to Alice is of the following
structure

LISTbad, EKau [Hash(LISTbad)]

where Kau is the key derived from the second half of
the M/2 bits for the purpose of authenticating Bob
to Alice and Hash is a generic hash function such as
MD − 5 or SHA− 1.

6. Bob and Alice compute Q(ha) and Q(hb) respectively
at the remaining indexes, in increasing order of the
indexes, thus generating a bit string.

Another important type of active attack is worth mention-
ing. Eve may spoof Alice or Bob during the probing stage
itself, i.e. Eve may disrupt the alternating probing process
between Alice and Bob and may begin sending probes to
Bob (Alice) pretending to be Alice (Bob). Such an attack
is possible to detect using a hypothesis testing approach on
the received signals at Bob, and has been dealt with in past
literature []. Essentially, it requires that Bob test each re-
ceived probe using a hypothesis test; the null hypothesis is
that the probe came from Alice, i.e. the same user as all the
past probes, and the alternate hypothesis is that the probe
was transmitted by a different user. We do not expound on
this further.

5. NUMERICAL EVALUATION



+ q

-q

t ime

Ampl i tude
Bit "1"

Bit "0"

Figure 4: The level-crossing algorithm uses a simple quan-

tizer. When m successive channel estimates at a user lie

above the q+ level or below the q− level, the excursion is

considered a candidate for the extraction of a single bit.

The central quantities of interest in our protocol are the
rate of generation of secret bits per second and the proba-
bility of error. The controls available to us, namely, the pa-
rameters of the protocol are the variables q, m and the rate
at which Alice and Bob probe the channel between them-
selves, fs. The channel itself is not under our control, and
explained earlier, the rate at which the channel is varying
can be represented by the Doppler frequency, fd. A typical
Doppler frequency for indoor wireless environments at the
carrier frequency of 2.4 Ghz is

fd =
v

λ
=

v
c
f0

∼ 1
3×108

2.4×109

= 8 Hz, (14)

assuming a velocity v of 1 m/s. We can therefore expect
typical Doppler frequencies in indoor environments in the
2.4 Ghz range of 802.11 to be not more than of the order
of about 10 Hz. However, the same frequency range may
result in a Doppler about ten times greater if the user was
in a moving automobile.

We contend that of the two quantities, rate Rk and prob-
ability of error pe, the probability of error is very impor-
tant in that the feasibility of our protocol depends on it.
As explained through equation (12), in order to achieve
a meaningful key-mismatch error probability pk (we con-
sider 10−6 ∼ 10−5 to be a reasonable key-mismatch prob-
ability), the bit-error probability pe must be much lower,
and for a 128 bits key, this entails a bit-error probability of
pe = 10

−7 ∼ 10−8. We have explained in Section 3 that
there is a fundamental trade-off in the selection of parame-
ters m and q that affects the rate and probability of error in
opposite ways.

5.1 Probability of error
The probability of bit-error, pe is the probability that a

single bits generated by Alice and Bob are different. The
symmetry of the problem allows us to consider one such sce-
nario. Let us consider the probability that Alice generates a
1 while Bob generates a 0. This probability can be expanded

-8

-7.5

-7

-6.5

-6

-5.5

-5

-4.5

-4

-3.5

2 2.5 3 3.5 4 4.5 5

Pr
ob

ab
ilit

y
of

b
it

er
ro

r (
log

10
sc

ale
)

value of m

Probability of error

Prob. of bit error Vs. m

Figure 5: Probability of error numerically evaluated for

various values of m. Channel estimates of Alice and Bob

have been assumed to be noise-free.

Figure 6: Probability of error numerically evaluated for

various values of m with noise

as

P (B = 0|A = 1) =
P (B = 0, A = 1)

p(A = 1)
=

Z ∞
q

Z q−
−∞

. . .

Z ∞
q| {z }

(2m−1)terms

1

(2pi)
2m−1

2 |K2m−1|
1/2

exp
n
− 12 x

TK
−1
2m−1x

o
d(2m−1)x

Z


q

Z


q

. . .

Z


q| {z }
(m)terms

1

(2pi)
m
2 |Km|

1/2
exp

n
− 12x

T K
−1
m x

o
d(m)x

,

where Km is the covariance matrix of m successive Gaus-
sian channel estimates of Alice and K2m−1 is the covariance
matrix of the Gaussian vectors formed by m of Alice’s chan-
nel estimates along with the m−1 time-interleaved channel-
estimates belonging to Bob. Therefore, computing the prob-
ability of a bit-errorrequires us to compute the probability
of the event that of 2m− 1 successive channel estimates, m
belonging to Alice, and m− 1 interleaved estimates belong-
ing to Bob, all of Alice’s estimates lie in an excursion above
q+ while all of Bob’s estimates lie in an excursion below q−.

We compute these probabilities for various values of m,
using numerical integration. The results of the probability
of error computations are summarized in figures 5-7. The re-
sults confirm the intuitive understanding that a larger value
of m produces a lower probability of error. This is because



Figure 7: Probability of error numerically evaluated for

various values of m with noise

0

2

4

6

8

10

12

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

R
at

e
in

s
ec

re
t b

its
p

er
s

ec
on

d

Probing frequency (kHz)

Rate in secret bits per sec against probing frequency for various values of m

m=2
m=4
m=6
m=8

m=10
m=12
m=14
m=16
m=18
m=20

Figure 8: Rate in secret bits per second for various values

of m, against probing frequency for a channel with Doppler

frequency fd = 10 Hz

a larger m make it less likely that given Alice’s channel es-
timates lie in a certain excursion, Bob’s (time-interleaved)
estimated lie in the opposite excursion.

5.2 Secret bit rate
The correct way to address the tradeoff between probabil-

ity of error and rate of generation of secret bits is to upper
bound the acceptable probability of error and then attempt
to derive the greatest possible rate of secret bits per second.

How many s-bits per second can we expect to derive from a
time-varying channel? The level crossing rate for a Rayleigh

fading process is given by LCR =

2πfdρe

−ρ2 [19], where
fd is the maximum Doppler frequency is the threshold level,
normalized to the root mean square signal level. Setting
ρ = 1 in this expression gives

LCR ∼ fd (15)
Therefore, a rough calculation tells us that since the level
crossing rate for a Rayleigh fading process is of the order
of the Doppler frequency, and since the rate of s-bits that
our algorithm produces depends on the number of excur-
sions above and below certain levels per unit time, we can-
not expect to obtain more s-bits per sec. than roughly the
order of the Doppler frequency. In practice, the rate of s-
bits/sec depends also on the channel probing frequency, i.e.

0

20

40

60

80

100

120

0 10 20 30 40 50 60 70 80 90 100

R
at

e
in

s
ec

re
t b

its
p

er
s

ec
on

d

Probing frequency (kHz)

Rate in secret bits per sec against probing frequency for various values of m, f_d = 100 Hz

m=2
m=4
m=6
m=8

m=10
m=12
m=14
m=16
m=18
m=20

Figure 9: Rate in secret bits per second for various values

of m, against probing frequency for a channel with Doppler

frequency fd = 100 Hz

1 1.5 2 2.5 3 3.5 4 4.5 5
0

2

4

6

8

10

12

Value of ’m’

Se
cr

et
b

its
p

er
s

ec
on

d

Figure 10: Fall in the secret bit rate for various probing

frequencies fs, as a function of m.

how fast Alice and Bob are able to send each other probe
signals. In figure 8, we plot the rate in s-bits/sec as a func-
tion of the channel probing frequency for a wireless channel
with a maximum Doppler of fd = 10 Hz. As expected, we
find that the number of s-bits the channel yields increases
with the probing frequency, but only up to a certain point,
after which further increase in the probing frequency does
not produce gains in secret bit rate. Further, the maximum
number of s-bits/sec that the channel yields is of the order
of the Doppler frequency. In figure 9, the computation is
repeated for a maximum Doppler frequency of fd = 100 Hz.
How is the secret bit rate affected by the parameter m? Fig-
ures 8 and 9 confirm the intuitive idea that the secret bit
rate must fall with increasing m. This is because excursions
of the Gaussian processes above q+ and below q− for an in-
creased duration (i.e. a larger m) are less frequent. Figure
10 further captures the effect of increasing m for a fixed value
of of probing frequency fs. The curves near the top belong
to high probing frequencies - at these frequencies, the secret
bit rate does is not affected by an increase in m. The curves
near the bottom of the figure belong to lower probing fre-
quencies, for which an increment in m produces a significant
drop in the secret bit rate. In figure 11, we investigate how
the secret bit rate is affected by a change in the maximum



0 50 100 150 200 250
0

50

100

150

200

250

Doppler frequency fd (Hz)

Se
cr

et
b

its
p

er
s

ec
on

d
m=2
m=3
m=4
m=5
m=6

Sampling freuqncy f
s
= 4 Khz

Figure 11: Rate in secret bits per second for varying

Doppler frequency fd and a fixed sampling frequency fs = 4

Khz (for various values of m)

0 200 400 600 800 1000 1200 1400 1600 1800 2000
0.5

0.6

0.7

0.8

0.9

1

Sampling frequency f
s
(Hz)

Fr
ac

tio
n

of
A

lic
e’

s
ob

se
rv

at
io

ns
th

at
B

ob
fi

nd
s

co
rre

ct

m=2
m=3
m=4
m=5
m=6

Doppler frequency fd = 10 Hz

Figure 12: The fraction of messages from Alice that are in

agreement with Bob’s observations.

Doppler frequency, i.e. as the time-variation of the channel
is increased. We found that for a fixed maximum channel
probing rate (in this particular case, fs = 4000 probes/sec),
increasing the Doppler produces greater rate but only up to
a point, after which the the secret bit rate actually begins
to fall. Therefore, running faster does not help unless we
can increase the probing frequency fs proportionally. This
suggests that not only does each channel corresponds to an
optimal minimum probing rate for best rate, each channel
probing rate also corresponds to a best Doppler frequency.
Finally, in figure 12 we compute the fraction of indexes sent
by Alice to Bob that give positive results at Bob’s end, as a
function of the probing frequency. Recall that we had postu-
lated that Bob can use this measure to authenticate Alice.
Ideally, this fraction should be well above 0.5 and as ex-
pected, it converges to 1, with increasing probing frequency.

5.3 Insights gained
The rate in secret bits per second that Alice and Bob can

derive from a time-varying channel is fundamentally limited
by the rate of time-variation in the channel. Further, in or-

Figure 13: Floor plan of the office building where coarse

RSSI-abased measurements were taken. The letters “AP”

indicate the location of the fixed access point and the path

taken by the moving client is shown with a black arrow.

der to extract the greatest number of s-bits/sec possible, we
need to probe the channel at a fast enough rate. Given the
fastest possible rate at which we can probe a given channel,
the parameters m and q can be controlled to keep the proba-
bility of error within an acceptable bound. Increasing m or q
buys a drop in the error probability at the cost of a decrease
in the s-bits/sec. Further, increasing the time-rate of varia-
tion of a channel helps in increasing the secret bit rate but
only up to a limit, after which further increase in the rate
of time-variation in the channel results in a decrease in the
secret bit rate, unless it is accompanied by a proportional
increase in the channel probing frequency.

6. EXPERIMENTAL VALIDATION VIA 802.11
In this section we describe the experimental validation of

our algorithm. Our experimental study was divided into two
parts. In the first phase, we use coarse RSSI (received sig-
nal strength indicator) measurements reported in the Prism
header5 of 802.11 packets exchanged between two nodes. In
the second, more detailed study, we dig deeper into the re-
ceived preamble structure6. We describe out experiments
and results for each of these cases below.

6.1 Coarse measurements using RSSI

6.1.1 Experiment setup
The setup consisted of an 802.11 node configured as an ac-

cess point along with a virtual monitor interface to capture
received packets. The Client side consister of a laptop with
a 802.11 card configured in station mode, along with vir-
tual monitor mode for capturing received packets. Atheros
[1] Wifi cards based on the 5212 chipset were used at each
end in conjunction with the Madwifi driver for Linux. The

5The Prism header is available on Atheros 802.11 cards us-
ing the Madwifi[2] driver and contains RSSI and MAC-layer
timestamps among other parameters.
6For details of the preamble in 802.11 packets, see [20]



Figure 14: Timing diagram of the simple ICMP PING ex-

periment for collecting reciprocal RSSI information on a wire-

less channel (not to scale)

2.1 2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 2.55
x 109

15

20

25

30

35

40

45

50

MAC layer timestamp

R
SS

I v
al

ue
w

.r.
t.

5−
pa

ck
et

m
ov

in
g

av
er

ag
e

Alice
Bob
"1" bits & positions of Alice +q level
"0" bits and position of Alice −q level
Position of Bob +q level
Position of Bob −q level

Figure 15: An experiment with 3 users shows the RSSI

traces of Alice & Bob and the key bits generated from them

without errors. This plot includes the effect of shadow fading,

therefore there are long strings of zeros and ones in the key

generated.

experiments were done in the 5.26 Ghz channel. The AP-
station configuration ensures that MAC-layer clocks at the
two nodes are synchronized. Figure 13 shows the layout of
the office building along with the location of the fixed AP
and path followed by the mobile client. ICMP ping packets
were sent from the AP to the client at a rate of 20 packets
per second. Each PING request packet received at the client
generated a MAC-layer acknowledgment packet sent back to
the AP, followed by a PING response packet. Upon receiv-
ing the PING response packet, the AP similarly replies with
a MAC-layer ACK packet. Figure 14 shows the sequence
in which these packets are sent. Each of these four packets
contain useful information in their Prism headers. A tcp-
dump application running on both the AP and the client
side recorded all packets received on the monitor interface.
The experiment consisted of sending 10, 000 packets from
the AP to the client. The traces collected by tcpdump at
each end were filtered using the MAC address field to keep
only the four types of packets described above. Further,
RSSI and MAC-timestamps were pulled out of each packet

2.1 2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5 2.55
x 109

−8

−6

−4

−2

0

2

4

6

8

10

MAC timestamp

R
SS

I v
al

ue
w

.r.
t.

5−
pa

ck
et

m
ov

in
g

av
er

ag
e

RSSI at Alice
RSSI at Bob
"1" bits, position of Alice’s +q level
"0" bits, position of Alice’s −q level
Position of Bob’s +q level
Position of Bob’s −q level

Figure 16: The RSSI traces of Alice & Bob wrt avg. sig-

nal power, along with the key bits generated. 511 bits were

generated in 392 sec. using a value of m = 4, without errors,

→ 1.3 s-bits/sec.

2.26 2.28 2.3 2.32 2.34 2.36 2.38
x 109

20

25

30

35

40

45

50

55

60

MAC timestamp

R
SS

I

RSSI from packets Alice receives from Bob
RSSI from packets Bob receives from Alice
RSSI from packets Eve overhears from Alice
RSSI from packets Eve overhears from Bob

Figure 17: The RSSI traces of Alice & Bob along with the

RSSI information from packets captured by Eve from both

users.

to generate a trace consisting of (timestamp,RSSI) pairs.

6.1.2 Modification to handle timestamps
It is important to note that since the precise time instants

at which the PING request and PING response messages are
received Alice and Bob respectively cannot be controlled,
there was no way to guarantee that successive PING re-
sponses received by Bob were separated in time by exactly
one PING request in between received by Alice. Therefore
MAC-layer timestamps are essential to time-align RSSI in-
formation at Alice & Bob since we do not have the luxury
of index numbers with which to reference RSSI values. This
requires a slight variation in our algorithm to handle MAC-
timestamps instead of indexes in the messages exchanged
between Alice and Bob. The modifications in the algorithms
may be summarized as follows:

1. Alice, instead of sending index numbers to Bob, now
sends MAC-timestamps in the message POS (see al-
gorithm 1 in section 4).



2.274 2.275 2.276 2.277 2.278 2.279 2.28 2.281 2.282
x 109

−6

−4

−2

0

2

4

MAC layer timestamp

R
SS

I v
al

ue
w

.r.
t.

5−
pa

ck
et

m
ov

in
g

av
er

ag
e

RSSI from packets Alice receives from Bob
RSSI from packets Bob receives from Alice
RSSI from packets Eve overhears from Alice
RSSI from packets Eve overhears from Bob

Figure 18: The RSSI traces of Alice & Bob along with the

RSSI information from packets captured by Eve from both

users.

2. For each MAC-timestamp sent by Alice, Bob finds the
MAC-timestamp in his own received packets that is
closest in time to the value of the timestamp sent by
Alice.

3. Starting from the packet corresponding to this times-
tamp, Bob to checks to see whether m−1 RSSI values
in an excursion above q+ or below q− in the usual way.

It is important to note that the RSSI field reported in the
Prism header of received 802.11 packets provides only very
coarse information about the received signal strength. In
fact, RSSI is reported only in increments on integers. More-
over, the 802.11 cards at Alice and Bob may not be relatively
calibrated any therefore, may report different values of RSSI
for the same actual received signal power. We found in our
experiments, that even in such cases,the relative variations
in RSSI with time are matched at both ends. Therefore,
this problem was solved by considering the variation of RSSI
about its moving average. Figure 15 shows the actual RSSI
traces collected by Alice and Bob. If each user simply uses
this data to compute suitable quantizer boundaries q+ and
q−, and then runs the level-crossing algorithm on it, we find
that the key generated had long strings of 1s and 0s. In-
tuitively, this is because we are attempting to include the
effect of change in shadow fading into the key generation
algorithm. In other words, the channels in figure 15 are not
stationary. Here, we have computed q+ and q− as:

qu+ = median(RSSIu) + σ
2(RSSIu) (16)

qu− = median(RSSIu)− σ2(RSSIu), (17)
where u can be be user Alice or Bob and σ2(RSSIu) repre-
sents the variance of the RSSI of user u. We can do away
with the shadow fading underlying the overall RSSI data by
computing a moving average of each RSSI trace and sub-
tracting it from the original RSSI trace. This leaves only
the small scale fading that can then be used as an input
to our algorithm. The result is shown in figure 16. In this
way, not only do we do away with the problem of having a
long strings of 1s and 0s, we also discard the average sig-
nal power from affecting our key generation process - recall
that as explained in Section 3, it is dangerous to use long

Figure 19: Timing diagram for the experiments done us-

ing channel impulse response computed from the preamble of

probe request and probe response packets (not to scale)

term statistical information such as the average signal power
for key generation since it allows the adversary an opportu-
nity to use knowledge of the locations of Alice and Bob to
estimate the mean channel between them.

6.1.3 Contrasting Eve’s attempts
To contrast the attempts of Eve, based on the signals over-

heard from both Alice and Bob, with the channel estimates
that Alice and Bob build for the channel between them, we
plot the RSSI traces captured by Eve for both signal against
Alice’s and Bob’s channel estimates in figure 17. The traces
of each user after considering only variations about a moving
average, are shown in figure 18. We see from this plot that
even with coarse RSSI measurements that represent the av-
erage received signal power per-packet over the entire 802.11
channel bandwidth, Alice and Bob are able to show fairly
good reciprocity while each of Eve’s overheard signals looks
unrelated to the true Alice-Bob channel.

6.2 Measuring CIR using 802.11 preamble
6.2.1 Experiment setup
The setup consisted of three 802.11 radios implemented

on FPGAs, allowing us to pull out the received signal in-
formation at a level that is not normally accessible using
commonly available 802.11 drivers. Two of the radios are
used as Alice and Bob while the third is configured as Eve.
Alice is configured to be the AP as before, and Bob is config-
ured in station mode. The experiment involves Bob sending
PROBE request messages to Alice, who then replies with a
PROBE response message to Bob. In our setup, we were
able to have Eve listen in on either Alice or Bob. In the
results presented, Eve has been configured to listen in on
Alice. In our first experiment, , Alice and Eve were placed
in laboratory room, while Bob was placed in an office cubicle
outside the lab. Figure 20 explains the exact layout of the
experiment. In our second experiment, Alice and Eve re-
mained in the same positions as before while Bob was made
to circle around the cubicle area in a mobile cart on wheels.
Figure 21 shows a 64-point CIR obtained from a single

PROBE request packet at Alice, along with the correspond-
ing CIR computed from the PROBE response packet sent in
reply. Also shown is the CIR as computed by Eve, using the
PROBE response packet that she overhears from Alice. For
the purpose of our key-extraction algorithm, we use only the



Figure 20: A layout of the experimental setup for the two

experiments conducted using fine channel impulse response

measurements. The locations of Alice, Bob and Eve are in-

dicated in the figure.

0 10 20 30 40 50 60 70
0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

CIR samples

M
ag

ni
tu

de
s

(no
rm

ali
ze

d)





Alice
Bob
Eve

Figure 21: The 64-point CIR from a single 802.11 packet.

For our key-extraction algorithm, we use the magnitude of

the main peak as the channel parameter of interest.

0 100 200 300 400 500 600 700 800 900 1000
0.6

0.8

1

1.2

1.4

1.6

1.8

2

CIR index

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

(Li
ne

ar
sc

ale
)

Alice
Bob
Locations of ’1’s
Locations of ’0’s
Moving avg (LPF)

Figure 22: CIR main peak magnitude of Alice & Bob with

average power

100 200 300 400 500 600

1.1

1.2

1.3

1.4

1.5

1.6

1.7

CIR index

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

(Li
ne

ar
sc

ale
)

Alice
Bob
Locations of 1s
Locations of zeros

Figure 23: Running the key generation algorithm on raw

data results in long strings of 1s and 0s.

magnitude of the main peak in the CIR.
Figure 22 shows the traces of the CIR’s main peak’s mag-

nitude at Alice and Bob for our first experiment, wherein
each user was stationary. 1000 CIRs were collected over
a duration of ∼ 110 seconds. We see the the traces show
significant changes in average signal power, presumably due
to time-variations in the wireless environment between Alice
and Bob in the experimental setup (see figure 20). Figure 23
is a magnified version of figure 22. Once again, it is easy to
see that changes in average signal power cause long strings
of 1s and 0s to appear in the generated key. We correct for
this in figure 24 by subtracting out the average power as be-
fore. The result is N = 90 s-bits generated in 110 seconds,
implying a key rate of about 0.82 s-bits/sec.

6.2.2 Contrasting Eve’s attempts
Figures 25 - 26 show Eve’s information overheard from

Bob along with Alice’s and Bob’s information about the
channel between them. Figure 27 shows that bits that Eve
would generate if she carried through with the key-generation
procedure. The mutual information [9] between Eve’s data
and Bob’s data is a useful measure of the information learnt
by Eve about the Alice-Bob channel and can be compared to
the mutual information between the information possessed



0 100 200 300 400 500 600 700 800 900 1000
−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

CIR index

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

(Li
ne

ar
sc

ale
)

Alice
Bob
Locations of 1s
Locations of zeros

Figure 24: CIR main peak values wrt the average signal

power. Using m = 4, N = 90 bits were generated using 1000

probes in 110 seconds.

Mutual information Static case Mobile Case

Alice-Bob 1.218 bits 3.294 bits
Bob-Eve 0 bits 0.0468 bits

Table 2: Mutual information between the CIR information

collected by Alice and Bob and that between the CIRs gath-

ered by Eve from packet coming from Bob and Bob’s CIRs

from Alice.

by Alice and Bob about the channel between them. In each
case, we are referring only to the magnitude of the main
peak in the CIRs. Table 6.2.2 gives the empirically com-
puted mutual information between the magnitudes of the
main peak in Alice’s and Bob’s CIRs, along with the mu-
tual information between the corresponding quantities for
Eve and Bob. As a consequence of the data processing in-
equality, any further processing of the received signal by
Eve would only reduce her information about the Alice-Bob
channel, and therefore the numbers in Table 6.2.2 provide
an upper bound on the information leaked out to Eve about
the Alice-Bob channel as per our experimental results. The
results from our second experiment with a moving Bob looks
very similar to the ones shown for the first experiment, al-
though with fewer bits produced in each case. This could
be because we are not probing the channel fast enough to
utilize the increased time-variation in the channel (see fig-
ure 11). Finally, we give an example of a single bit error
that occurred during our second experiment when using a
value of m = 3. Figure ?? shows that around CIR index
781, Alice’s channel estimates lie in an excursion above q+
while Bob’s estimates like in an excursion below q−. There-
fore, Bob does not discard this index, believing that Alice’s
estimates must also be in an excursion below q−. The error
disappears when the value of m is increased to 4.

7. CONCLUSIONS
Wireless networks represent a dramatically different type

of communication system than traditional “wired” networks.
Typically, these differences have been seen as a challenge

50 100 150 200 250 300
0.9

1

1.1

1.2

1.3

1.4

1.5

1.6

1.7

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

Bob
Eve

Figure 25: Main peak magnitude for the Alice-Bob and

Bob-Eve channels.

0 50 100 150 200 250 300

−0.5

−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

Bob
Eve

Figure 26: Main peak magnitudes for CIRs of the Alice-

Bob and Bob-Eve channels, with respect to the average signal

power

0 100 200 300 400 500 600 700 800 900 1000
−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

CIR index

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

(Li
ne

ar
sc

ale
)

0 100 200 300 400 500 600 700 800 900 1000
−0.1

−0.05

0

0.05

0.1

CIR index

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

(Li
ne

ar
sc

ale
)

Eve
Ones
Zeros

Bob
Ones
Zeros

Figure 27: The resulting bits generated by Bob and Eve

from figure 26



770 775 780 785 790 795 800 805
−0.2

−0.15

−0.1

−0.05

0

0.05

0.1

0.15

0.2

0.25

0.3

CIR index

M
ag

ni
tu

de
o

f t
he

m
ai

n
pe

ak
in

th
e

CI
R

(Li
ne

ar
sc

ale
)

Alice
Bob
Locations of 1s
Locations of zerosERROR

Figure 28: An example of a single bit error when using

m = 3 in the case in which Bob is mobile. The error goes

away for m = 4

from a security perspective, making it harder to secure wire-
less systems. In this paper, however, we have proposed that
it is possible to exploit the underlying properties of the wire-
less medium in order to enhance security objectives. In par-
ticular, we have proposed a protocol that builds upon the
reciprocity of wireless channels to extract a common cryp-
tographic key at the two ends of a wireless link. Further,
our protocol exploits the fact that the channel decorrelates
away quickly in space to ensure strong protection against a
passive adversary, and additionally protects from an active
adversary by building-up authentication during the key ex-
traction process. We pointed out the various performance
measures for evaluating our key-extraction algorithm and
presented numerical evaluations of performance, along with
the important insights that they offered. Finally, we ex-
perimentally validated our proposed algorithm using first, a
set of coarse RSSI measurements reported in 802.11 head-
ers, and then using a more thorough system that utilizes the
802.11 preamble sequence to compute a channel impulse re-
sponse on a per-packet basis. We found our algorithm gave
satisfactory results for indoor wireless environments. Our
work demonstrates that multipath information that is in-
herent in any wireless system, and is normally discarded for
data communications, can be successfully utilized to provide
enhanced confidentiality services. What is more, existing
off-the-shelf radio platforms already contain this capability.

8. REFERENCES
[1] http://www.atheros.com/.

[2] http://www.madwifi.org/.

[3] R. Ahlswede and I. Csiszar. Common randomness in
information theory and cryptography – part I: Secret
sharing. IEEE Transactions on Information Theory,
39(4):1121–1132, 1993.

[4] C. H. Bennett, G. Brassard, and J.-M. Robert.
Privacy amplification by public discussion. SIAM J.
Comput., 17(2):210–229, 1988.

[5] G. Brassard and L. Salvail. Secret key reconciliation
by public discussion. Advances in Crytology Proc. -
Eurocrypt ’93, Lecture Notes in Computer Science,
765:410–??, 1994.

[6] W. T. Buttler, S. K. Lamoreaux, J. R. Torgerson,
G. H. Nickel, C. H. Donahue, and C. G. Peterson.
Fast, efficient error reconciliation for quantum
cryptography. Phys. Rev. A, 67:052303, 2003.

[7] C. Cachin and U. M. Maurer. Linking information
reconciliation and privacy amplification. Journal of
Cryptology: the journal of the International
Association for Cryptologic Research, 10(2):97–110,
Spring 1997.

[8] J. Cardinal and G. V. Assche. Construction of a
shared secret key using continuous variables. Info.
Theory Workshop, 2003.

[9] T. M. Cover and J. A. Thomas. Elements of
Information Theory. John Wiley, 1991.

[10] S. Fortune, D. Gay, B. Kernighan, O. Landron,
R. Valenzuela, and M. Wright. Wise design of indoor
wireless systems: practical computation
andoptimization. Computational Science and
Engineering, IEEE, 2(1):58–68, April 1995.

[11] G. German and R. V. Q. Spencer, L. Swindlehurst.
Wireless indoor channel modeling: Statistical
agreement of ray tracing simulations and channel
sounding measurements. In IEEE International
Conference on Acoustics, Speech, and Signal
Processing, 2001. Proceedings. (ICASSP ’01). 2001,
pages 2501–2504, Salt Lake City, UT, USA, May 2001.

[12] A. Hassan, W. Stark, J. Hershey, and S. Chennakeshu.
Cryptographic key agreement for mobile radio, 1996.

[13] H. Koorapaty, A. Hassan, and S. Chennakeshu. Secure
information transmission for mobile radio. IEEE
communication letters, 4(2), feb 2000.

[14] A. T. M. Bloch and S. W. McLaughlin. Efficient
reconciliation of correlated continuous random
variables using ldpc codes. 2005.

[15] U. Maurer. Secret key agreement by public discussion
from common information. IEEE Transactions on
Information Theory, 39(4):733–742, 1993.

[16] U. Maurer and S. Wolf. Secret key agreement over a
non-authenticated channel — part i: Definitions and
bounds. IEEE Transactions on Information Theory,
49(4):822–831, Apr. 2003.

[17] U. Maurer and S. Wolf. Secret key agreement over a
non-authenticated channel — part ii: The
simulatability condition. IEEE Transactions on
Information Theory, 49(4):832–838, Apr. 2003.

[18] U. Maurer and S. Wolf. Secret key agreement over a
non-authenticated channel — part iii: Privacy
amplification. IEEE Transactions on Information
Theory, 49(4):839–851, Apr. 2003.

[19] T. S. Rappaport. Wireless Communications:
Principles and Practice. Prentice Hall PTR. ISBN
0-13-042232-0, 2001.

[20] I. standard 802.11a:. Part 11- Wireless LAN Medium
Access Control (MAC) and Physical Layer (PHY)
specifications: High-speed Physical Layer in the 5 GHZ
Band. 1999.

[21] C. Ye, A. Reznik, and Y. Shah. Extracting secrecy
from jointly gaussian random variables. Int. Symp on
Info. Theory, jul 2006.