- Home /

Extracting a Cryptographic Key from an Unauthenticated Wireless Channel

Research Paper / Jan 2008

In order for network slicing to deliver on its promise as an effective tool to generate new revenues and profitability, new business models must match the dynamic technical and operational changes that it brings. Significant progress is being made in demonstrations and trials, as highlighted in this report and the...

Joe Giersch, a biologist from USGS, sat down with InterDigital to discuss technology’s role in the study of stream ecology, and explain why we should all know about the insect, Lednia tumana, that he has spent his life studying.

Recently, the Qualcomm Tricorder XPRIZE® announced its winners. We caught up with Ed Hepler, ex-InterDigital engineer and hardware development lead of the winning bootstrap operation, Final Frontier Medical Devices, after the winning announcement in this CREATORS sit-down.

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.

InterDigital develops mobile technologies that are at the core of devices, networks, and services worldwide. We solve many of the industry's most critical and complex technical challenges, inventing solutions for more efficient broadband networks and a richer multimedia experience years ahead of market deployment.

© Copyright 2017 InterDigital, Inc. All Rights Reserved