Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels

Research Paper / Jan 2009

- Home /

Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels

Research Paper / Jan 2009

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.

Chapter 1

Secret Key Extraction from Level Crossings over

Unauthenticated Wireless Channels

Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

Abstract We present an algorithm that allows two users to establish a common

cryptographic key by exploiting special properties of the wireless channel: the

underlying channel response between any two parties is unique and decorrelates

rapidly in space. The established key can then be used to encrypt further communi-

cations between two users. This is especially useful in mobile and ah-hoc scenarios

where a key establishment infrastructure may not be readily available. Furthermore,

it provides unconditionally secret bits, as against secrecy based on computational

hardness and computational boundedness of the adversary. Our algorithm uses infor-

mation from level crossings to extract bits from correlated stochastic processes that

are generated by probing the channel. The resulting protocol resists cryptanalysis

by an eavesdropping adversary and a spoofing attack by an active adversary without

requiring an authenticated channel, as is typically assumed in prior information-

theoretic key establishment schemes. We evaluate our algorithm through theoreti-

cal and numerical studies, and provide validation through two complementary ex-

perimental studies. First, we use an 802.11 development platform with added cus-

tomized logic that extracts raw channel impulse response data from the preamble of

a format-compliant 802.11a packet. We show that it is possible to practically achieve

key establishment rates of ∼ 1 bit/sec in a real, indoor wireless environment. To

illustrate the generality of our method, we show that our approach is equally appli-

cable to per-packet coarse signal strength measurements using off-the-shelf 802.11

hardware.

Suhas Mathur, Wade Trappe, Narayan Mandayam

WINLAB, Rutgers University, e-mail: {suhas, trappe, narayan}@winlab.rutgers.edu

Chunxuan Ye, Alex Reznik

InterDigital, King of Prussia, PA. e-mail: {Chunxuan.Ye, Alex.Reznik}@interdigital.com

1

2 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

1.1 Introduction

Many of the risks associated with securing wireless systems stem from challenges

associated with operating in a mobile environment, such as the lack of a guaranteed

infrastructure or the ease with which entities can eavesdrop on communications.

Traditional network security mechanisms rely upon cryptographic keys to support

confidentiality and authentication services. However, in a dynamic mobile wireless

environment, with peer-to-peer associations being formed on-the-fly between mo-

bile entities, it is difficult to ensure availability of a certificate authority or a key

management center. Since such scenarios are likely to become more prevalent, it is

necessary to have alternatives for establishing keys between wireless peers without

resorting to a fixed infrastructure.

We explore an alternative for building cryptographic services by exploiting an

untapped resource – the wireless channel itself. The specificity of the radio channel

between two wireless devices, and its rapid decorrelation with distance, provide

a basis for the creation of shared secret information, such as cryptographic keys,

even in the presence of an eavesdropper. In typical multipath environments (see

Figure 1.1), the wireless channel between two users, Alice and Bob, produces a

time-varying, stochastic mapping between the transmitted and received signals. This

mapping varies with time in a manner that is location-specific and reciprocal, i.e.,

the mapping is the same whether Alice is the transmitter with Bob as the receiver or

vice-versa. The time-varying mapping, commonly termed fading, decorrelates over

distances of the order of half a wavelength, λ . Thus, an adversary, Eve, who is more

than λ/2 away from both Alice and Bob, experiences fading channels to Alice and

to Bob that are statistically independent of the fading between Alice and Bob. These

properties allow us to generate a common, secret cryptographic key at Alice and

Bob such that Eve gets no information about the generated key. For example, at 2.4

GHz, we only require that Eve be roughly λ/2 = 6.25 cm away from Alice and

Bob to ensure that she gets no useful information. Thus, while fading is typically

considered harmful, we profitably exploit it to extract perfectly secret bits without

leaking information to an adversary.

The extraction of secret bits from the wireless channel can be viewed as a ‘black-

box’ that can be advantageous in various ways, putting to good use information that

is already available from the channel. For example, in the current 802.11i standard,

session keys for communication between a station and an AP are derived by hash-

ing together authentication credentials and nonces exchanged in the clear. This ties

the confidentiality of future messages to the authentication credentials, and if these

credentials are ever compromised then an adversary will be able to derive the ses-

sion keys and decrypt past encrypted messages. If the nonces can be derived in an

information-theoretically secret manner from the channel between two users, then

a passive adversary has no means to derive the session keys even if it learns the au-

thentication credentials[1]. Further, session keys can be updated using these secret

bits derived from the channel, instead of relying on previously existing keys [1],

thus ensuring that the confidentiality of each new session is protected independently

of earlier sessions.

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 3

Fig. 1.1 The multipath fading for a signal from Alice to Bob is different from that for the signal

reaching Eve.

Yet another vulnerability in 802.11i stems from the fact that during the estab-

lishment of a secure link between a station and an AP, all messages exchanged over

the air, including management frames, are sent unencrypted until both parties have

obtained the session key (c.f. the temporal key (TK) in 802.11) and are therefore

susceptible to eavesdropping and to spoofing by other users. While the 802.11w

amendment seeks to protect some management frames from such attacks, it too fails

to protect messages exchanged before the the establishment of TKs. Unfortunately,

securing the initial exchanges between the parties requires them to share a key that

is not established until later. Our key extraction mechanism provides a natural so-

lution by allowing the parties to generate a temporary key that protects the interim

exchanges before the formal keys are in place.

Ad hoc or peer-to-peer networks present another avenue where our technique

can be useful. Alice may not care to establish Bob’s identity if she merely wishes

to employ his forwarding services. In such a scenario, she may nevertheless wish to

establish a confidential link with Bob by using the channel to form a key prior to

encrypting subsequent data, thereby preventing eavesdropping.

Prior work in information theory has noted the potential of using the wireless

channel for generating shared secret bits (see Section 1.7), but most of this work

has been aimed at computing theoretical limits and has not provided practical al-

gorithms, nor a demonstrable and quantifiable impact on security. Our contribution

may be summarized as follows:

1. We translate prior information-theoretic ideas into a practical protocol applied to

wireless channels;

2. We build a new algorithm for key extraction that, unlike prior schemes, does not

require an authenticated channel, and study performance for typical fading;

3. We validate our algorithm using channel impulse responses measured using the

802.11a packet preamble on a customized FPGA-based 802.11 development

4 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

platform and a second study that uses only coarse per-packet RSSI information

readily available to off-the-shelf 802.11 platforms.

Existing mobile radio platforms already provide the information we need, but such

data are normally discarded after physical layer processing and can be profitably

exploited to benefit security. The approach we present augments, rather than re-

places existing cryptographic security mechanisms– it provides a new approach to

establishing keys that is useful when there is no key management infrastructure.

In Section 2 we describe our system model and the design issues relevant to

our problem, in Section 3 we describe our key-extraction algorithm in detail, in

Section 4 we evaluate its performance and in Section 5 we present two experimental

studies that validate our algorithm using 802.11a hardware. In Section 6, we present

a discussion on the tradeoffs and security of our key-extraction method, in Section

7 we review the related literature, and we conclude in Section 8.

1.2 System model & Design issues

The crucial insight that allows the wireless channel to be amenable for generating

a secret key is that the received signal at the receiver is modified by the channel

in a manner that is unique to the transmitter-receiver pair. This distortion depends

critically upon the location of the transmitter, the receiver, and scatterers. Typically,

such distortion is estimated at the physical layer of the receiver and the associated

distortion information dealt with for reliable physical layer decoding. Since this

information is always present and uniquely corresponds to the transmitter-receiver

pair, it also provides our transmitter (Alice) and receiver (Bob) a means to privately

establish secret bits associated with this distortion. We now focus on the challenges

of using the stochastic nature of the wireless channel to secretly establish bits. We

break down our discussion to include a description of: (1) the underlying channel

model associated with multipath fading; (2) the tools needed to obtain bits from the

channel response; and (3) the design goals that need to be addressed in order to

reliably establish these bits. To assist the reader, we provide notation in Table 1.1.

Before we begin, we comment on our adversary. We assume an attacker that can

either act as an eavesdropper or who may inject messages to impersonate Alice or

Bob. We present further considerations of adversarial actions in Section 1.6.

1.2.1 Channel model

Let h(t) be a stochastic process corresponding to a time-varying parameter that

describes the wireless channel between Alice and Bob. Although there are many

choices for h(t), for our discussion, we shall assume that h(t) is the magnitude of

the transfer function of the multipath fading channel between Alice and Bob evalu-

ated at a fixed test frequency, f0. Implicit in this formulation is the observation that

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 5

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

0

0.5

1

1.5

2

2.5

Time (sec)

M

ag

ni

tu

de

(a)

10 20 30 40 50 60 70

0

0.5

1

1.5

2

(b)

Probe index number

M

ag

ni

tu

de

o

f c

ha

nn

el

p

ar

am

et

er q

+

level

q

−

level

h(t) process

Alice’s estimates

Bob’s etimates

Alice

Bob

q

+

q

−

3 pts above q

+

4 pts above q

+

Fig. 1.2 (a) A sample realization of a Rayleigh fading stochastic process. (b) Successive channel

estimates of the process by Alice and Bob showing excursions above the q+ and below the q−

levels on a magnified portion of (a).

Symbol Meaning

h Stochastic channel parameter of interest

h(t) Value of the stochastic process h at time t

s(t) Probe signal transmitted to estimate h(t)

fd Maximum Doppler frequency (Hz)

fs Rate at which each user sends probes (Hz)

q+,q− Quantizer bin boundaries (Upper and lower resp. )

m Reqd. min. # of estimates in a excursion

N Length of key in bits

Rk Rate of generation of secret bits (s-bits/sec)

pe Probability of a bit error

pk Probability of key mismatch = 1− (1− pe)N

Table 1.1 A summary of the notation used

the system transfer function of the channel is the same in the Alice →Bob direc-

tion as in the Bob→Alice direction at a given instant of time. This follows from

reciprocity, which is a fundamental property of electromagnetic wave propagation

[2, 3] in a medium and must not be confused with additive noise or interference,

which may be different for different receivers. To distinguish between the channel

parameter of interest, and its value at a given time, we denote the parameter by h

and refer to its value as h(t). To estimate the parameter h, Alice and Bob must trans-

6 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

mit known probe signals to one another. Each party can then use the received signal

along with the probe signal to compute an estimate ˆh of h. Since practical radios are

half duplex due to hardware constraints, Alice must wait to receive a probe signal

from Bob before she can transmit a probe to him and vice-versa. In the time be-

tween the two successive probes, h(t) changes slightly in a manner that is modeled

by an appropriate probability distribution. The received signal at Alice and Bob due

to successive probes may be written as

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

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

where s(t) is the known probe signal, na & nb are the independent noise processes

at Alice and Bob and t1 & t2 are the time instants at which successive probes are

received by Alice and by Bob, respectively. Using the received signal, Alice and

Bob, each compute (noisy) estimates of h:

ˆha(t1) = h(t1)+ za(t1) (1.3)

ˆhb(t2) = h(t2)+ zb(t2), (1.4)

where za and zb represent the noise terms due to na and nb after processing by the

function that estimates h. We refer the reader to [4] for designing good estimators

for h. The estimates ˆha and ˆhb are in all likelihood unequal, due in part to the in-

dependent noise terms and in part to the time lag τ . However they can be highly

correlated if Alice and Bob send probes to one another at a fast enough1 rate, i.e.

if τ = t2 − t1 is small. By repeatedly sending probes in an alternating manner over

the time-varying channel, Alice and Bob can generate a sequence of n estimates

ˆha = {ˆha[1], ˆha[2], . . . , ˆha[n]} and ˆhb = {ˆhb[1], ˆhb[2], . . . , ˆhb[n]}, respectively, that are

highly correlated, as in Figure 1.2. Although Eve can overhear the probe signals sent

by each user, the signals received by Eve are completely different:

rbe (t1) = s(t1)hbe(t1)+ ne(t1) (1.5)

rae (t2) = s(t2)hae(t2)+ ne(t2), (1.6)

where hbe and hae denote the channel between Bob & Eve and between Alice &

Eve, respectively, and ne is the noise added at Eve. If Eve is more than ∼ λ/2 away

from Alice and Bob, then hae and hbe are uncorrelated with h [5]. Therefore, despite

possessing knowledge of the probe signal s(t), Eve cannot use her received signals

to compute meaningful estimates of the Alice-Bob channel, h.

1

‘Fast enough’ here is in relation to the coherence time of the channel, which is inversely propor-

tional to the maximum Doppler frequency fd .

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 7

1.2.2 Converting the channel to bits

Alice and Bob must translate their respective sequences of channel estimates into

identical bit-strings suitable for use as cryptographic keys, thus requiring:

1. Suitably long: Keys of length 128 to 512 bits are commonly used in symmetric

encryption algorithms. So they should be able to generate at least these many bits

in a reasonable amount of time.

2. Statistically random: The bits should be random with equal probability of a ‘0’

and a ‘1’. Also, the bit-sequences must not suffer from statistical defects that

could be exploited by an attacker.

The second requirement guarantees that the generated key has desirable security

properties. That is, an N-bit key must provide N bits of uncertainty to an adversary

who only knows the key generation algorithm and nothing else.

We now briefly describe how to obtain bits from the channel estimates ˆha and ˆhb,

to provide the intuition behind our algorithm, while postponing a formal description

to Section 4. The sequence of channel estimates ˆha and ˆhb are random variables

drawn from an underlying probability distribution that characterizes the channel

parameter h. We assume, for the sake of discussion, that h(t) is a Gaussian random

variable and the underlying stochastic process h is a stationary Gaussian process.

A Gaussian distribution for h may be obtained, for example, by taking h to be the

magnitude of the in-phase component of a Rayleigh fading process between Alice

and Bob [2]. We note that the assumption of a Gaussian distribution on h is for ease

of discussion and our algorithm is equally valid in the general case.

Since the channel estimates computed by Alice and Bob are continuous random

variables, it is necessary to quantize their estimates using a quantizer Q(·) to ob-

tain bits. However, a straightforward quantization of the vectors ˆha and ˆhb is not

sufficient because it does not guarantee that an identical sequence of bits will be

generated at the two users. In our scheme, Alice and Bob use the channel statistics

to determine scalars, q+ and q− that serve as reference levels for the quantizer Q(·)

as follows:

Q(x) =

{

1 if x > q+

0 if x < q−

(1.7)

This forms the basis for positive and negative excursions, respectively, as explained

below. Values between q− and q+ are not assigned a bit. Alice parses through her

channel estimates ˆha to determine the locations of excursions of her channel esti-

mates above q+ or below q− that are of a duration ≥ m estimates, i.e., m successive

channel estimates in ˆha are > q+ or < q−, where m is a protocol parameter. She

sends Bob a message over the public channel containing the locations of k such

excursions in the form of an array of indexes L = {l1, l2, . . . , lk}. Bob then checks

his own sequence ˆhb at the locations specified in L to determine whether it contains

an excursion above q+ or below q− for a duration greater than or equal to ‘m− 1’

samples, i.e. whether ˆha(li) is > q+ or < q− for a duration that spans m−1 or more

estimates, for i = 1, . . . ,k. Bob identifies ‘good’ indexes by finding all index values l

in L that produce such an excursion in ˆhb. He places these indexes into an array ˜L to

8 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

be sent to Alice publicly. Indexes in L but not in ˜L are dropped from consideration

by each party. The indexes in ˜L are used by each user to compute a sequence of bits

by quantizing: Q(ˆha( ˜L)) and Q(ˆhb( ˜L)). If the bit-vectors Q(ˆha( ˜L)) and Q(ˆhb( ˜L))

are equal, then Alice and Bob succeed in generating | ˜L| identical bits. We show

later that provided the levels q+,q− and the parameter m are properly chosen, the

bits generated by the two users are identical with very high probability. A variation

of the protocol that copes with spoofing is detailed in Section 1.3.1.

1.2.3 Design goals

An important quantity of interest will be the rate of generation of secret bits, ex-

pressed in secret-bits per second or ‘s-bits/sec’. Naturally, it is desirable that Alice

and Bob achieve a high secret-bit rate. According to 802.1x recommendations, it

is generally desirable for master keys to be refreshed at one hour intervals[6]. Us-

ing these examples and AES key sizes of 128 bits as a guideline, a conservative

key rate of roughly 0.1 bits per second is needed, though it is desirable to achieve

higher secrecy rates. However, we are especially wary of bit errors. If the sequence

Q(ˆha( ˜L)) is different from Q(ˆhb( ˜L)) even by a single bit, then the two bit-strings

cannot be used as cryptographic keys and consequently the entire batch of bits must

be discarded. Therefore, we would like the bit error probability pe to be extremely

low, so that the probability pk that the keys generated 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 keys of length 128 bits, we must target a bit-error probability

of pe where

pk = 1− (1− pe)128, (1.8)

which gives pe ∼ 10−8. A bit-error is defined as the event that Alice and Bob agree

to use a certain index li contained in the list ˜L for generating a bit, but they end up

generating different bits, i.e. ˆha and ˆhb both lie in excursions at the index li but the

excursions are of opposite types.

The rate at which secret bits can be extracted from the channel is fundamentally

limited by the rate of time-variation in the channel. We quantify this variation by the

maximum Doppler frequency, fd . In a fading channel, fd determines both the rate

at which the channel varies and the magnitude of the swings produced. A simple

measure of the maximum Doppler frequency in a given wireless environment is

given by fd = vλ , where v is a measure of the effects of user mobility and the dynamic

environment around the users, expressed in meters/sec and λ is the wavelength of

the carrier wave. In our case λ = cf0 , where c is the speed of light. It can be seen

that increasing the value m or the magnitudes of the quantizer boundaries q+ & q−

would not only result in a lower rate, but also a lower probability of error. Intuitively,

this is because larger magnitudes of q+ & q−, or a larger value of m makes it less

likely that Alice’s and Bob’s channel estimates lie in opposite type of excursions,

thereby reducing the error rate. However, both types of excursions also become

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 9

less frequent, thereby decreasing the number of secret bits that can be generated

per second. Thus, there is a tradeoff between rate and probability of error, and the

parameters q+,q− and m provide convenient controls to select suitable operating

points over this tradeoff. Beyond rate and robustness, we also require the bits to be

random and free from statistical defects, as discussed in Section 1.4.3.

Finally, the correlated information obtained by Alice and Bob can be utilized to

build a secret key in a number of different ways and it is important to make sure the

method employed does not allow Eve to infer any useful information. An alterna-

tive bit extraction scheme is to have each user estimate a statistical measure of the

channel (e.g. the mean signal-strength, or variance in the estimates) using ˆha and ˆhb

respectively. If the channel is stochastically stationary, then their respective statisti-

cal measures would each converge to the true value with time. In this way, Alice and

Bob will each possess knowledge about a numerical quantity, without having sent

messages over the air containing this quantity. They could then quantize their esti-

mates of the statistical measure to generate bits. However, the trouble with using a

statistical measure is that knowledge of the locations of Alice and Bob and their en-

vironment may allow Eve to infer the statistics of the channel between them. Indeed,

publicly available tools, such as the WISE ray-tracer [7], make it easy to predict the

signal statistics at a receiver given the knowledge of the locations of the transmitter

and receiver and the building’s layout. Thus, it is important to recognize that us-

ing a statistical measure for key generation can be perilous. Our algorithm avoids

statistical measures by relying on specific instantiations of the fading process.

1.3 Level-crossing Algorithm

We now detail our level-crossing based key-extraction algorithm. It is assumed that

when the algorithm is run, Alice and Bob have collected a sufficiently large number

of channel estimates ˆha and ˆhb, by alternately probing the channel between them-

selves. Further, it is assumed that the vectors ˆha and ˆhb are of equal length and their

jth elements ˆha( j) and ˆhb( j) correspond to successive probes sent by Bob and Alice

respectively, for each j = 1, . . . , length(ˆha). Algorithm 1 describes the procedure

and consists of the following steps:

1. Alice parses the vector ˆha containing her channel estimates to find instances

where m or more successive estimates lie in an excursion above q+ or below

q−.

2. Alice selects a random subset of the excursions found in step 1 and for each

selected excursion, she sends Bob the index of the channel estimate lying in the

center of the excursion, as a list L. Therefore, if ˆha(i) > q+ or < q− for some

i = istart , . . . , iend , then she sends Bob the index icenter = ⌊ istart+iend2 ⌋.

3. For each index from Alice, Bob checks whether his vector of estimates ˆhb con-

tains at least m − 1 channel estimates centered around that index in an ex-

10 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

cursion above q+ or below q−, i.e. whether ˆha > q+ or < q− for each index{

l −⌊m−22 ⌋, . . . , l + ⌈m−22 ⌉

}

, for each l ∈ L.

4. For some of the indexes in L, Bob’s channel estimates do not lie in either ex-

cursion. Bob makes a list ˜L of all indexes that lie in excursions and sends it to

Alice.

5. Bob and Alice compute Q(ˆha) and Q(ˆhb) respectively at each index in ˜L, thus

generating a sequence of bits.

Since Eve’s observations from the channel probing do not provide her with any

useful information about ˆha and ˆhb, the messages L and ˜L do not provide her any

useful information either. This is because they contain time indexes only whereas

the generated bits depend upon the values of the channel estimates at those indexes.

Further, the selection of a random subset in Step 2 from the set of eligible excursions

found in Step 1, guarantees that Eve cannot use L and ˜L to infer the values of the

channel estimates of Alice or Bob at those time indexes.

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 11

1.3.1 Preventing a Spoofing Attack

Since Alice and Bob do not share an authenticated channel, Eve can impersonate

Alice in Step 2, or Bob in Step 4 above. Such an attack would allow Eve to insert

her own ‘fake’ L or ˜L messages, thus spoofing a legitimate user and disrupting the

protocol without revealing her presence. Therefore we require a form of data-origin

authentication, that assures each user that the L or ˜L message has originated at the

legitimate transmitter.

12 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

Our protocol can be made to detect the adversary in each of the two cases above.

We first focus on Eve inserting a fake L-message. Since Eve has no information

about the locations of channel excursions apart from L, she can only make random

guesses about which indexes to place into a fake L-message to Bob (apart from

the ones Eve learns from L). If Eve inserts a significant number of random guesses

into a fake L-message, Bob can detect her presence by computing the proportion of

indexes in L that lead to excursions in ˆhb. Since Eve can only make random guesses,

this quantity would be much lower than one resulting from a legitimate L-message

from Alice. For each guess, she has a very low probability of choosing an index that

lies in an excursion spanning (m−1) or more estimates at Bob. Of these, the indexes

that do not lie in an excursion in ˆhb are discarded by Bob while those that do happen

to lie in an excursion are considered eligible for quantization and placed into the

˜L-message sent to Alice. Thus, an unsuccessful guess provides no benefit to Eve,

while a successful guess, albeit improbable, causes ˜L to contain an index that was

not present in L, thereby alerting Alice. Thus, Eve must also modify the message

˜L by deleting this index before it reaches Alice. Our protocol can be made to resist

modification of the ˜L-message using a message authentication code (MAC), by the

following additional steps:

1. To make sure the L-message received is from Alice, Bob computes the fraction of

indexes in L where ˆhb lies in an excursion spanning (m−1) or more estimates. If

this fraction is less than 12 +ε , for some fixed parameter 0 < ε <

1

2 , Bob concludes

that the message was not sent by Alice, implying an adversary has injected a fake

L-message.

2. If the check above passes, Bob replies to Alice with a message ˜L containing those

indexes in L at which ˆhb lies in an excursion. Bob computes Kb = Q(ˆhb( ˜L)) to

obtain N bits. The first Nau bits are used as an authentication key to compute a

message authentication code (MAC) of ˜L. The remaining N−Nau bits are kept as

the extracted secret key. The overall message sent by Bob is

{

˜L,MAC

(

Kau, ˜L

)}

.

Upon receiving this message from Bob, Alice uses ˜L to form the sequence of bits

Ka = Q(ˆha( ˜L)). She uses the first Nau bits of Ka as the authentication key Kau =

Ka(1, . . . ,Nau), and using Kau she verifies the MAC to confirm that the package was

indeed sent by Bob. Since Eve does not know the bits in Kau generated by Bob, she

cannot modify the ˜L-message without failing the MAC verification at Alice.

Even without an authenticated channel, Alice and Bob can successfully establish

a common secret key despite an active adversary, provided there are no bit errors.

This explains why we insist on a very low probability of error in Section 1.2.3. Fur-

ther, the reduction in the secret-bit rate is negligible over a long run of the protocol

because the Nau bits are a one-time expense that allow Alice and Bob to bootstrap

data-origin authentication. A modified algorithm that incorporates the above ideas

is presented as Algorithm 2 (see Figure 1.3).

Another active attack involves Eve impersonating Alice or Bob during the

channel-probing stage, i.e. Eve may begin sending probes to Bob pretending to be

Alice or vice-versa. Such an attack can be detected using a hypothesis testing ap-

proach on the recent history probes received at each legitimate user, and this has

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 13

Fig. 1.3 Timing diagram for the key-extraction protocol.

been extensively studied in [8, 9]. The technique relies on the insight that given a

sufficiently fast probing rate, successive probes received by a user are most likely

to differ by a small amount. We provide further discussion related to the security of

our scheme in Section 1.6.

1.4 Performance evaluation

The central quantities of interest in our protocol are the rate of generation of secret

bits, the probability of error and the randomness of the generated bits. The controls

available to us are the parameters: q+,q−,m and the rate at which Alice and Bob

probe the channel between themselves, fs. We assume the channel is not under our

control, and as explained in Section 1.2.3, the rate at which the channel varies can be

represented by the maximum Doppler frequency, fd . The typical Doppler frequency

for indoor wireless environments at the carrier frequency of 2.4 GHz is fd = vλ ∼

2.4×109

3×108 = 8 Hz, assuming a velocity v of 1 m/s. We thus expect typical Doppler

frequencies in indoor environments in the 2.4 GHz range to be roughly 10 Hz and

20 Hz in the 5 GHz range. For automobile scenarios, we can expect a Doppler of

∼ 200 Hz in the 2.4 GHz range.

1.4.1 Probability of error

The probability of error, pe is critical to our protocol. In order to achieve a robust

key-mismatch probability pk, the bit-error probability pe must be much lower than

pk. A bit-error probability of pe = 10−7 ∼ 10−8 is desirable for keys of length N =

128 bits. We have explained in Section 1.2.3 that there is a fundamental trade-off

in the selection of parameters m,q+ and q− that affects the rate and probability of

error in opposing ways.

14 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

The probability of bit-error, pe is the probability that a single bit generated by

Alice and Bob is different at the two users. The symmetry of the distribution of

h allows us to consider just one type of bit error in computing pe. Consider the

probability that Bob generates the bit “0” at an index given that Alice has chosen

this index but she has generated the bit “1”. As per our Gaussian assumption on the

parameter h and estimates ˆha and ˆhb, this probability can be expanded as

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

p(A = 1)

= (1.9)

∫

∞

q+

∫ q−

−∞

. . .

∫

∞

q+︸ ︷︷ ︸

(2m−1) terms

(2pi)(1−2m)/2

|K2m−1|1/2 exp

{− 12 xT K−12m−1x}d(2m−1)x

∫

∞

q+

. . .

∫

∞

q+︸ ︷︷ ︸

(m) terms

(2pi)−m/2

|Km|1/2 exp

{− 12 xT K−1m x}d(m)x

,

where Km is the covariance matrix of m successive Gaussian channel estimates of

Alice and K2m−1 is the covariance matrix of the Gaussian vector (ˆha[1], ˆhb[1], ˆha[2], . . . , ˆhb[m−

1], ˆha[m]) formed by the combining m channel estimates of Alice and the m−1 es-

timates of Bob in chronological order. The numerator in (1.9) is the probability that

of 2m−1 successive channel estimates (m belonging to Alice, and m−1 for Bob),

all m of Alice’s estimates lie in an excursion above q+ while all m− 1 of Bob’s

estimates lie in an excursion below q−. The denominator is simply the probability

that all of Alice’s m estimates lie in an excursion above q+. We compute these prob-

2 3 4 5 6 7 8 9 10 11

−8

−7

−6

−5

−4

−3

−2

−1

0

Value of m

Pr

ob

ab

ilit

y

of

b

it

er

ro

r,

p e

(lo

g 1

0

sc

a

le

)

SNR = 0 dB

SNR = 10 dB

SNR = 20 dB

SNR = 30 dB

SNR = 40 dB

Fig. 1.4 Probability of bit error pe for various values of m at different SNR levels (q± = mean±

0.8σ )

abilities for various values of m and present the results of the probability of error

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 15

computations in Figure 1.4. The results confirm that a larger value of m will result

in a lower probability of error, as a larger m makes it less likely that Alice’s and

Bob’s estimates lie in opposite types of excursions. Note that if either user’s esti-

mates do not lie in an excursion at a given index, a bit error is avoided because that

index is discarded by both users.

1.4.2 Secret-bit rate

The correct way to address the tradeoff between probability of error and rate of gen-

eration of secret bits is to upper bound the acceptable probability of error and then

attempt to derive the greatest possible rate. How many s-bits/second can we expect

to derive from a time-varying channel? An approximate analysis can be done using

the level-crossing rate for a Rayleigh fading process, given by LCR =

√

2pi fdρe−ρ2

[2], where fd is the maximum Doppler frequency and ρ is the threshold level, nor-

malized to the root mean square signal level. Setting ρ = 1, gives LCR ∼ fd .

The above calculation tells us that we cannot expect to obtain more s-bits per

second than the order of fd . In practice, the rate of s-bits/sec depends also on the

channel probing rate fs, i.e. how fast Alice and Bob are able to send each other

probe signals. In Figure 1.5 (a) and (b), we plot the rate in s-bits/sec as a function of

the channel probing rate for a wireless channel with maximum Doppler frequencies

of fd = 10 Hz and fd = 100 Hz respectively. As expected, the number of s-bits the

channel yields increases with the probing rate, but saturates at a value on the order of

fd . More precisely, the number of s-bits/sec is the number of s-bits per observation

times the probing rate. Therefore

Rk = H(bins)× p(A = B)×

fs

m

(1.10)

= 2 fs

m

× p(A = 1,B = 1) (1.11)

= 2 fs

m

.

∫

∞

q+

. . .

∫

∞

q+︸ ︷︷ ︸

(2m−1) terms

(2pi) 1−2m2

|K2m−1|1/2

e{− 12 xT K−12m−1x}d2m−1x, (1.12)

where H(bins) is the entropy of the random variable that determines which bin

(> q+ or < q−) of the quantizer the observation lies in, which in our case equals

1 assuming that the two bins are equally likely2. The probing rate fs is normalized

by a factor of m because a single ‘observation’ in our algorithm is a sequence of m

channel estimates. The expression in (1.12) is reminiscent of the probability of error

expression in (1.9) and has been evaluated in Figure 1.5.

Figure 1.5 confirms the intuition that the secret bit rate must fall with increasing

m, since the longer duration excursions required by a larger value of m are less

2 The levels q+ and q− are chosen so as to maintain equal probabilities for the two bins.

16 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

0

2

4

6

8

10

12

Probing rate (KHz)

R

at

e

in

s

ec

re

t b

its

/s

ec

(a)

m=2

m=4

m=8

m=14

m=20

0 5 10 15 20 25 30 35 40 45 50

0

20

40

60

80

100

120

(b)

Probing rate (KHz)

R

at

e

in

s

ec

re

t b

its

/s

ec

m=2

m=4

m=8

m=14

m=20

fd = 10 Hz

fd = 100 Hz

Fig. 1.5 Rate in secret bits per second for various values of m, against probing rate for a channel

with Doppler frequency (a) fd = 10 Hz and (b) fd = 100 Hz (q± = mean±0.8σ )

frequent. In Figure 1.6 (a), we investigate how the secret-bit rate Rk varies with the

maximum Doppler frequency fd , i.e. versus the channel time-variation. We found

that for a fixed channel probing rate (in this case, fs = 4000 probes/sec), increasing

fd results in a greater rate but only up to a point, after which the secret-bit rate

begins to fall. Thus, ‘running faster’ does not always help unless we can increase the

probing rate fs proportionally. This suggests that not only does each channel have

an optimal minimum probing rate for deriving the best possible secret-bit rate, but

each probing rate also corresponds to a most ‘useful’ maximum Doppler frequency.

Figure 1.6(b) shows the expected decrease in rate as the quantizer levels q+ and

q− are increased in magnitude. In this figure, α denotes the number of standard

deviations from the mean at which the quantizer levels are placed.

1.4.3 Randomness of generated bits

Guaranteeing that the generated bits are random is crucial because they are intended

for use as a cryptographic key. Since we have assumed the adversary possesses com-

plete knowledge of our algorithm, any non-random behavior in the bit sequences can

be exploited by the adversary to reduce the time-complexity of cracking the key. For

example, if the algorithm is known to produce a greater proportion of ‘1’s than ‘0’s,

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 17

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

Probing rate f

s

= 4 Khz

(a)

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

0

5

10

15

Value of α

Se

cr

et

b

its

p

er

s

ec

on

d

f

s

= 3.5 KHz, any m

m=4, f

s

= 500 Hz

m=8, f

s

= 500 Hz

m=12, f

s

= 500 Hz

q

+

= mean+α⋅σ

q

−

= mean−α⋅σ

fd = 10 Hz

(b)

Fig. 1.6 (a) Secret-bit rate for varying Doppler fd and fixed fs for various values of m (b) Rate as

a function of function of quantizer levels q+ & q− parametrized by α .

then the effective search space for the adversary would be reduced. Consequently, a

variety of statistical tests have been devised to test for various defects [10].

In evaluating the randomness of bit sequences generated by our algorithm, we

focus on Maurer’s universal statistical test [11], a widely accepted benchmark for

testing randomness. The test statistic relates closely to the per-bit entropy of the

sequence, and thus measures the actual cryptographic significance of a defect as

related to the running time of an adversary’s optimal key-search strategy [11].

Additionally, we ran a few other tests using the NIST public-domain test suite[12].

We refer the interested reader to [13] for a description of these tests and the defini-

tions of p− value for each test. The results for these are summarized in Table 1.2.

Subsequent runs produced comparable results and thus support the conclusion that

our algorithm provides random bits. In particular, Maurer’s test showed the average

Test P-value

Maurer’s Test 0.8913

Monobit frequency 0.9910

Runs Test 0.1012

Approx. entropy 0.8721

Random excursions 0.5829

Lempel Ziv 1.0000

Table 1.2 Results from randomness tests on bit sequences (108 bits) produced by our algorithm

for fd = 10 Hz, fs = 30 Hz, m = 5 and q+,q− = mean ± 0.2σ . In each test, a p-value > 0.01

indicates the sequence is random.

entropy of our bit-sequences is very close to the value expected for a truly ran-

18 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

dom sequence. This can be possible only if successive bits are almost independent,

which in turn requires that they must be separated in time by at least a ‘coherence

time’ interval. Since the coherence time of a channel is inversely proportional to the

Doppler frequency, extracting bits from a channel at a rate significantly greater than

fd cannot possibly produce random bits using level crossings. We observed in Sec-

tion 1.4.2 that the rate at which our algorithm generates secret bits is bounded from

above by approximately the maximum Doppler fd . Finally, we note that the selec-

tion of a random subset of excursions by Alice effectively allows her some control

on selecting the final key generated. Thus, even if a particular run happens to pro-

duce excursions at Alice containing a statistical defect in the resulting bit sequence,

she can fix the defect to some extent by suitably choosing L from among eligible

excursions.

1.5 Validation using 802.11a

We now describe our experimental validation efforts for typical indoor environ-

ments. Our experiments were divided in two parts. In the first study, we delved

into the structure of an 802.11 packet to access the preamble sequence [14] in the

received signal to compute a 64-point channel impulse response (CIR) that showed

one or more resolvable dominant paths as separate peaks. We used the magnitude

of the tallest peak in the CIR (the dominant multipath) as the channel our parameter

of interest. To access signal information at the sample level, we used an 802.11 de-

velopment platform with FPGA-based customized logic added for processing CIR.

Our results showed that our algorithm works very well for both static and mobile

scenarios, producing error-free secret bits at rates ∼ 1 s-bits/sec in the tested indoor

environments.

Encouraged by the CIR results, we sought to determine whether unmodified off-

the-shelf 802.11 hardware could achieve comparable results. Therefore, for the sec-

ond study, we used coarse RSSI measurements reported in the Prism headers of

802.11 packets exchanged between commercially available 802.11a radios, with Al-

ice configured as an access point (AP mode) and Bob as a client (station mode),

and a third user configured to listen (station mode) on transmissions from both

legitimate users.

1.5.1 CIR method using 802.11a

Experiment setup: Our experimental platform (Figure 1.7(a)) consisted of an

802.11 development board with commercial 802.11a/b/g modem IP, to which we

added custom logic to extract the channel impulse response from received packets.

This allowed us to pull out received signal information at a level not normally acces-

sible using commodity 802.11 hardware and drivers. Two such boards were set up as

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 19

(a) (b)

Fig. 1.7 (a) Our experimental platform - a development board for a commercial 802.11a/b/g mo-

dem IP, to which we added custom logic to process CIR information. (b) Timing diagram for

collecting CIR information using PROBE packets

Alice and Bob, while a third board was configured to be Eve. Alice was configured

to be an access point (AP mode), and Bob was configured to be a client (station

mode). The experiment involved Bob sending PROBE request messages to Al-

ice, who then replied with a PROBE response message (Figure 1.7(b)). Limita-

tions of our development boards allowed us to have Eve listen on either Alice or

Bob, but not both. In the results presented here, Eve has been configured to listen in

on Alice. In the first experiment, Alice and Eve were placed in a laboratory, while

Bob was placed in an office cubicle outside the lab, see Figure 1.8. In the second

experiment, Alice and Eve remained in the same positions while Bob circled the

cubicle area along the trajectory in Figure 1.8 in a cart on wheels.

Fig. 1.8 A layout of the experimental setup for the CIR method (distances in cm)

Figure 1.9 shows a 64-point CIR obtained from a single 802.11aPROBE request

packet received at Alice, along with the corresponding CIR computed from the

PROBE response packet received by Bob in reply. Also shown is the CIR as

20 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

0 10 20 30 40 50 60

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

Sample number

M

ag

ni

tu

de

Alice’s CIR

Bob’s CIR

Eve’s CIR

Fig. 1.9 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.

computed by Eve, using the overheard PROBE response packet from Alice. For

the purpose of our algorithm, we use only the magnitude of the main peak in the

CIR.

Figure 1.10 shows the traces of the CIR’s main peak’s magnitude at Alice and

Bob for our first experiment. While our experiment ran for ∼ 22 minutes, in the in-

terest of space and clarity we show 700 CIRs collected over a duration of ∼ 77 sec-

onds. The traces show significant changes in average signal power, ostensibly due

to time-variations in the wireless environment between Alice and Bob (see Figure

1.8). If each user simply uses this data as input to the level-crossing bit-extraction

algorithm, the generated key has long strings of 1s and 0s (see Figure 1.10). This

is because we are attempting to include the effect of shadow fading [2] (also called

large-scale fading) that produces large but slow swings in the average signal power

into the key generation algorithm. In other words, the channel in Figure 1.10 is not

stationary. Each user locally computes q+ and q− as:

qu+ = mean(ˆhu)+ α ·σ(ˆhu) (1.13)

qu− = mean(ˆhu)−α ·σ(ˆhu), (1.14)

where u can be Alice or Bob, ˆhu is the set of magnitudes of the CIR’s main peak

collected by user u, and σ(ˆhu) represents the standard deviation of ˆhu. The factor α

can be selected to vary the quantizer levels. We chose α = 18 for the CIR-method.

The effect of the underlying shadow fading contained in the collected data can be

removed by subtracting a moving average of each trace from the original trace. This

leaves only the small scale fading that we wish to use in our algorithm. The result is

shown in Figure 1.11. In this way, not only do we do away with the problem of long

strings of 1s and 0s, we also prevent the average signal power from affecting our

key generation process. Using the small scale fading traces, our algorithm generates

N = 125 s-bits in 110 seconds (m = 4), yielding a key rate of about 1.13 s-bits/sec.

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 21

0 100 200 300 400 500 600 700

1

1.2

1.4

1.6

1.8

CIR index

(a)

M

ag

ni

tu

de

(m

ain

pe

ak

) Eve’s CIR

Bob’s CIR

Alice’ CIR

"1" bits

"0" bits

150 160 170 180 190 200 210 220 230 240 250

1.1

1.2

1.3

1.4

1.5

1.6

1.7

CIR index

(b)

M

ag

ni

tu

de

(m

ain

pe

ak

)

Key generated by Alice: 111000111110111111111111000011001000000010001

Key generated by Bob: 111000111110111111111111000011001000000010001

Key inferred by Eve: 010001010000000010001000100000000000000100000

q

+

q

−

Fig. 1.10 (a) Traces of Alice, Bob and Eve. Variation in avg. signal power produces longs strings

of 1s and 0s. (b) A magnified portion of the traces.

Contrasting Eve’s attempts: Figure 1.10 shows a trace of Eve’s CIR peak as

overheard from Alice along with Alice’s and Bob’s traces. Figure 1.11 shows the bits

that Eve would generate if she carried through with the key-generation procedure.

The mutual information [15] (M.I.) between Eve’s data and Bob’s data is a useful

measure of the information learned by Eve about Bob’s measurements ˆhb and can

be compared to the mutual information between Alice’s and Bob’s estimates ˆha and

ˆhb. Table 1.3 gives these mutual information values computed using the method

in [16]. As a consequence of the data processing inequality [15], any processing

of the received signal by Eve would only reduce her information about the Alice-

Bob channel, and therefore, the M.I. values in Table 1.3 provide upper bounds on

the information about the Alice-Bob channel leaked out to Eve. The results from

our second experiment with a moving Bob are very similar to the ones shown for

the first experiment, although with fewer bits produced. Due to space limits, we

do not present plots for the mobile experiment but instead summarize our results

in Table 1.3. It is notable that in the static case the M.I. between Eve and Bob is

orders of magnitude smaller than that between Alice and Bob and very close to

zero, indicating that Eve is unable to derive any significant information about the

Alice-Bob channel. Further, the M.I. between Eve and Bob is lower in the mobile

case compared to the static case, indicating that mobility actually helps strengthen

the secrecy of generated keys.

22 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

0 100 200 300 400 500 600 700

−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

CIR index

(a)

M

ag

ni

tu

de

(m

ain

pe

ak

)

Alice’s CIR

Bob’s CIR

Eve’s CIR

"1" bits

"0" bits

150 160 170 180 190 200 210 220 230 240 250

−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

CIR index

(b)

M

ag

ni

tu

de

(m

ain

pe

ak

)

Key generated by Alice: 10101011010011001011010010100100010010001010101101010101010

Key generated by Bob: 10101011010011001011010010100100010010001010101101010101010

Key inferred by Eve: 00100100101000101110010 101000110011010100001101101111011010

q

+

q

−

Fig. 1.11 (a) Traces of Alice and Bob after subtracting average signal power. Using m = 5, N = 59

bits were generated in 110 seconds (Rk = 0.54 s-bits/sec) while m = 4 gives N = 125 bits (Rk = 1.13

s-bits/sec.) with no errors in each case. (b) A magnified portion of (a)

1.5.2 Coarse measurements using RSSI

Experiment setup: The setup consisted of three off-the-shelf 802.11 radios. Al-

ice was configured in AP mode along with a virtual monitor interface to capture

received packets. Bob was a client, consisting of a laptop with a 802.11a card in

station mode, along with virtual monitor for capturing received packets. Eve

was a third 802.11a node, identical in configuration to Bob, but capable of receiving

packets from both Alice and Bob. In our experiment, Alice was stationary, while

Bob and Eve moved along fixed trajectories. Atheros [17] WiFi cards based on the

5212 chipset were used at each end along with the Madwifi driver [18] for Linux.

The experiments were done in the 5.26 GHz channel. The AP-station configuration

ensured that MAC-layer clocks at the two nodes were synchronized. Figure 1.12 (b)

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 generates a MAC-layer acknowledgment packet sent back to the AP,

followed by a PING response packet. Upon receiving the PING response

packet, the AP similarly replies with a MAC-layer ACK packet.

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 23

(a)

(b)

Fig. 1.12 (a) Timing diagram for collecting RSSI information using PING packets in the RSSI-

method. (b) Experimental Layout for RSSI-based method showing trajectories of Bob and Eve,

while Alice (the AP) was kept stationary.

Figure 1.12 (a) shows the sequence in which these packets are sent. A tcpdump

[19] application running on both the AP and the client recorded and time-stamped

all packets received on the monitor interface of each user. The experiment consisted

of sending 8,000 packets from Alice to Bob. The tcpdump traces at each end were

filtered using the MAC address to keep only the four types of packets described

above. Further, RSSI and MAC-timestamps were pulled out of each packet to gen-

erate a (timestamp,RSSI) trace.

Modification to handle timestamps: We note that since the precise time in-

stants at which the PING response and PING requestmessages are received

by Alice and Bob respectively cannot be controlled, there was no way to guaran-

tee that successive PING request messages received by Bob were separated in

time by exactly one PING response received in between by Alice. Therefore,

MAC-layer timestamps were essential to time-align RSSI information at Alice &

Bob since we did not have index numbers with which to reference RSSI values.

This required a slight variation in our algorithm to handle MAC-timestamps instead

of indexes in the messages exchanged between Alice and Bob. Instead of sending

index numbers to Bob, Alice now sends MAC-timestamps in the message L (see

Algorithm 1 in Section 1.3). For each MAC-timestamp sent by Alice, Bob finds the

MAC-timestamp in his own trace that is closest in time to the value of the times-

tamp sent by Alice. Bob uses the packet determined in Step 2 above as if it were the

index sent by Alice. He checks for the presence of excursions above q+ or below

q− centered at this packer as in Algorithm 1.

The RSSI field in the Prism header of received 802.11 packets reports RSSI as

integers, thereby providing only coarse channel information. Moreover, the 802.11

cards at Alice and Bob may not be relatively calibrated and thus may report different

values of RSSI. We found in our experiments that although lacking calibration, the

24 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

2.15 2.2 2.25 2.3 2.35 2.4

x 109

20

25

30

35

40

45

50

55

60

65

70

MAC layer timestamp (µs)

R

SS

I r

ec

ei

ve

d

Alice’s recd. RSSI

Bob’s recd. RSSI

"1" bits

"0" bits

Eve’s RSSI from Alice

Eve’s RSSI from Bob

0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0

1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1

0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1

Key generated

by Alice & Bob:

Bob → Eve

Alice → Eve Bob → Alice

Alice → BobLong strings of 1s & 0s

Fig. 1.13 RSSI traces of Alice and Bob and bits generated. This plot includes the effect of shadow

fading.

temporal variations in RSSI are matched in Alice’s and Bob’s traces. This problem

was solved by subtracting out a moving average of the trace to remove the effects

of slowly varying average signal power, as in the CIR method. Figure 1.13 shows

the raw RSSI traces collected by Alice and Bob plotted against their received MAC-

timestamps. As in the CIR-method, the traces exhibit strong variations in average

signal power. We average out the large-scale variations and keep only the small scale

fading effect. The result is shown in Figure 1.14. Our algorithm produces secret bits

at a rate of almost 1.3 s-bits/sec using m = 4, where q+ and q− were computed

independently by each user as in (1.13)-(1.14) with α = 12 .

Contrasting Eve’s attempts: We plot the RSSI traces captured by Eve for both

Alice’s and Bob’s signal in Figure 1.13. The traces from Alice and Bob after con-

sidering only variations about a moving average, are shown in Figure 1.14. Even

with coarse RSSI measurements that represent the average received signal power

per-packet over the entire 802.11 channel bandwidth, Alice and Bob can exploit

reciprocity of their channel to successfully generate secret bits at a fairly good rate.

We compute the pair-wise M.I. between the traces of Eve, Alice and Bob in Table

1.3. As in the CIR-method, we find that Eve gets almost no information about the

Alice-Bob channel.

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 25

2.15 2.2 2.25 2.3 2.35 2.4 2.45 2.5

x 109

−5

0

5

10

15

MAC−timestamp (µs)

(a)

R

SS

I (5

−p

kt

av

era

ge

)

2.335 2.336 2.337 2.338 2.339 2.34 2.341 2.342

x 109

−6

−4

−2

0

2

4

6

8

MAC−timestamp (µs)

(b)

R

SS

I (5

−p

kt

av

era

ge

) AliceBob

"1" bits

"0" bits

Alice recd. RSSI

Bob’s recd RSSI

"0" bits

"1" bits

0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1

0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 1 0

1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1

0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1

1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0

1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0

1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1

0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1

1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 0 1

1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 0

1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 0 0

0 1 1 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0

0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0

0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0

0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0

0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1

1 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 1

0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0

0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 0 1 1

1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 1 1

0 0 1 1

1 0 0 0

1 0 1 1

1 1 0 1

0 0 1 1

1 1 0 0

0 1 0 0

1 0 0 1

0 0 0 1

1 0 0 1

q

−

q

+

Key @ Alice

and Bob:

Fig. 1.14 RSSI traces of Alice & Bob after subtracting windowed mean. We get 511 bits in 392

sec using m = 4 (Rk = 1.3 s-bits/sec) without any errors.

CIR-based method

Value of m used 4

Choice of q+,q− mean ±0.125σ

Duration of experiments 1326 sec (∼ 22 min.)

Inter-probe duration 110 msec.

Static case:

Average secret-bit rate 1.28 s-bits/sec.

I(Alice; Bob) 3.294 bits

I(Bob; Eve) 0.0468 bits

Mobile case:

Average secret-bit rate 1.17 s-bits/sec.

I(Alice; Bob) 1.218 bits

I(Bob; Eve) 0.000 bits

RSSI-based method

Value of m used 4

Choice of q+,q− mean ±0.5σ

Average secret-bit rate 1.3 s-bits/sec

Inter-probe duration 50 msec.

Duration of experiment 400 sec.

I(Alice; Bob) 0.78 bits

I(Alice; Eve) 0.00 bits

I(Bob; Eve) 0.07 bits

Table 1.3 Summary of experimental results. I(u1;u2) denotes the mutual information (M.I.) between the measure-

ments of users u1 and u2.

26 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

1.6 Discussion

We now discuss insights related to our scheme, summarizing fundamental trade-

offs, and further discuss potential security threats. We showed in Section 1.4 that

the rate at which Alice and Bob derive secret bits from a time-varying channel is

limited by the rate of variation in the channel. To maximize rate, we must probe the

channel rapidly. For the fastest probing rate, the parameters m,q+ and q− can be

tuned to keep the probability of error within an acceptable bound. Increasing m or

the magnitudes of q+,q− decreases the error probability at the cost of a decrease in

the secret-bit rate. Increasing temporal variation in a channel increases the secret-

bit rate up to a point, after which further increase produces a rate decrease, unless

accompanied by a proportional increase in the channel probing rate.

The natural decorrelative properties of fading provides our scheme security

against eavesdroppers. We confirmed this through our system implementation. Stan-

dard randomness tests indicate that our algorithm is resilient to an eavesdropper ex-

ploiting randomness defects. However, it is worth noting that key rates significantly

greater than the maximum Doppler frequency cannot result in truly random bits.

Thus we recommend conservatively setting the probing rates relative to the dynam-

ics of the fading environment. Beyond a passive adversary, we have addressed the

threat of an active adversary impersonating Alice or Bob. Coping with spoofing of

probes can be dealt with using techniques similar to [9]. We have addressed spoofing

of messages following probing by providing a modified algorithm that uses some of

the shared secret bits for data-origin authentication. Thus, Eve cannot thwart the

key-generation process by impersonating either legitimate user without getting de-

tected.

A further concern common to all key establishment schemes is the man-in-the-

middle attack. A man-in-the-middle attack against our algorithm is only possible if

Alice and Bob cannot hear each other’s probes (e.g. they are not within radio range,

or Eve talks to Alice and Bob separately), otherwise Eve’s attack causes discrepan-

cies that are easily detectable by Alice and Bob. If Alice and Bob do fall victim to

a man-in-the-middle attack, this can be detected by the following identity-based au-

thentication mechanism: Alice asks Bob to send her the keyed hash of the answer to

a specific question using their (supposed) shared key as an input to a cryptographic

hash function. If Eve relays this question to Bob, then Bob’s answer will be useless

to Eve (assuming only Alice and Bob know the answer to the question). We note

this method requires that Alice and Bob share some secret information known only

to them. This is necessary as each user must authenticate the identity of the other in

order to prevent a man-in-the-middle attack, and is necessary even for classical key

establishment schemes like Diffie-Hellman.

Finally, the astute reader might inquire whether varying levels of interference at

different locations in the environment would affect our key generation process. We

have provided fundamental tradeoffs relating signal-to-interference levels to quan-

tizer parameter selection for an isotropic noise background. However, by conserva-

tively selecting protocol parameters (e.g. selecting a larger value of m (see Figure

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 27

1.4)), we achieve improved robustness in the key generation process at the cost of

lowering the rate.

1.7 Related work

Information-theoretic literature has explored the use of information from the physi-

cal layer in deriving security benefits. In [20, 21], the authors introduced the prob-

lem of generating identical bits based on correlated information available to two

users such that a third eavesdropping user does not learn anything about the gen-

erated key. They showed, provided Alice and Bob already share an authenticated

public channel, that it is possible to generate identical keys at the two users. The

standard method for generating secret keys at Alice and Bob under this assumption

consists of three basic steps and has been utilized by a number of proposed systems

[22, 23, 24]. In advantage distillation [20, 25], the legitimate users, Alice and Bob,

obtain correlated information while Eve is allowed to eavesdrop, so that Alice &

Bob share greater information3 than that shared between Alice & Eve or Bob &

Eve. Alice and Bob then convert their information into bits. In the information rec-

onciliation stage [23], Alice and Bob exchange error-correcting messages over an

authenticated public channel that allow them to agree on an identical string of bits.

However, the publicly exchanged messages reveal a certain amount of information

about the bit strings to Eve. In privacy amplification [26], Alice and Bob diminish

the partial information revealed to Eve by systematically discarding some of their

common bits. Efficient protocols have since been designed [23, 27]4 to allow key

generation without leaking information to an eavesdropping adversary.

A central assumption in this entire body of work is that Alice and Bob have an

authenticated channel available to them even before key generation begins. This

is an unrealistic assumption in practice because the availability of an authenticated

channel implies that Alice and Bob already share a secret key to begin with! There-

fore, the purpose of generating a common secret key is defeated.

In [29], Maurer and Wolf showed that secret key extraction without an authenti-

cated channel is possible only if Eve cannot possibly transmit a signal to Bob that is

statistically indistinguishable from signals coming from Alice (and vice-versa). This

provides an important insight that has not been translated into a practical algorithm.

Our work is the first to build upon this result: we use the wireless channel to guar-

antee that Eve does not possess the required information to prevent key generation.

More recently, [30] examined PHY-layer based authentication and confidential-

ity in wireless systems. The work in [8, 9] looked at authentication using channel

signatures between the transmitter and receiver(s). Our work is perhaps most closely

related to[31], which proposes a scheme for generating secret bits from correlated

observations of deep fades by two users communicating via a TDD link. This work

3 The amount of information between two observations X and Y is measured by the mutual infor-

mation I(X;Y )[15].

4 Much of this work was done in the context of quantum key distribution[28].

28 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

focuses on the theoretical construction for extracting randomness through universal

hash families. However, they do not demonstrate or evaluate the amenability of the

wireless channel to detection of deep fades by both users, nor the precision needed

in the TDD process for their scheme. A quantification of the secret key rate versus

parameters associated with the underlying fading process or parameters involved

in their algorithm was not provided. Additionally, we note that their method fo-

cuses primarily on a passive adversary. The reliance on deep fades may be exploited

by an active adversary that produces greater interference power at one legitimate

user than the other so that a deep fade for one user may not be a deep fade for the

other. In [32], a method exploiting channel reciprocity using ultra-wideband (UWB)

channels to generate secret bits was presented. In [33], specialized electronically

steerable antennas were proposed for use in generating key bits by exploiting chan-

nel reciprocity. The methods in [32, 31, 33] all rely on conventional reconciliation

for correcting bit-errors, and thus require an authenticated channel. In [34, 35], a

method for secret key generation based on phase reciprocity of frequency selective

fading channels was proposed. While this is attractive, it is difficult to implement as

accurate phase information is hard to harvest from existing platforms.

In contrast to prior work, the algorithm we propose transcends the requirement

of an authenticated channel, does not require specialized hardware and is not lim-

ited to UWB channels. We provide a fundamental analysis between the performance

of our scheme and underlying parameters governing fading and quantization. Fur-

ther, we provide two real-world experimental implementations of our scheme and

show that existing mobile platforms already provide sufficient information for pro-

ducing secret bits. We evaluate the randomness of the bit-sequences produced by

our algorithm, a generally overlooked aspect in prior work on secret key generation,

and show that they are suitable for use as cryptographic keys. Lastly, we note that

our technique may be compared with classical key establishment techniques such

as Diffie-Hellman, which also use message exchanges to establish keys. However

these rely upon unproven arguments of computational hardness of problems such

as inverting discrete logarithms or factoring a product of large prime numbers. Our

algorithm, on the other hand, provides information-theoretic secrecy, does not as-

sume bounded computation power at the adversary and further, represents practical

methods to achieve this type of security. The cost of enabling unconditional security

must be borne out in some form – in our case this may take the form of collecting

correlated information by probing – but in fact, depending upon how our method is

used, much of the required information is already available in present day systems.

In this way we provide a means to realize in wireless networks the same benefits

that quantum cryptography has enabled using optical fiber links.

1.8 Conclusions

We proposed a protocol that exploits the reciprocity of the transfer function of the

wireless multipath channel to establish a common cryptographic key between two

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 29

communicating entities. Our protocol obtains a security advantage from the fact that

the channel response decorrelates rapidly with distance from each communicator,

implying that there is strong protection against a passive eavesdropper as well as an

active adversary attempting a spoofing attack. The performance of our scheme was

evaluated and important insights relating the probing rate, quantizer parameters and

the resulting secret key rate were provided.

We also presented the results of a thorough effort to experimentally validate

the utility of the wireless channel for secret key generation. First, we constructed

a system to extract channel impulse responses on a customized 802.11 develop-

ment platform, where we used the 802.11a preamble to compute channel impulse

responses on a per-packet basis. Second, we used off-the-shelf 802.11a cards for

collecting coarse RSSI measurements. In both cases, our algorithm generated se-

cret bits at a useful rate without any errors. We showed that an eavesdropper shares

minuscule mutual information with legitimate communicators, thereby supporting

security against eavesdroppers. Our work demonstrates that the multipath informa-

tion that is inherent in any wireless system (and is normally discarded after physical

layer processing), can successfully support key establishment. More importantly, we

showed that although this capability is possible with custom architectures, it can be

achieved using off-the-shelf radio platforms, and thus could have immediate impact

on the security of commodity wireless systems. Looking beyond our fundamental

observations and feasibility studies, we note that our algorithm naturally applies to

emerging wireless systems that use MIMO or OFDM to enhance data rates since

the associated multiple uncorrelated channels between two users would lead to a

proportional increase in the secret-bit extraction rate.

Acknowledgements: The authors would like to express their gratitude to Yo-

gendra Shah for valuable discussions, and to NSF and DARPA (CNS-0626439 and

W31P4Q-07-1-0002) for supporting this research.

References

1. M. Rudolf and R. P. Mukherjee, Method and system for deriving an excryption key using joint

randomness not shared by others. US Patent Application Publication US2007/0058808A1,

2007.

2. T. S. Rappaport, Wireless Communications: Principles and Practice. Prentice Hall PTR.,

2001.

3. A. Goldsmith, Wireless Communications. New York, NY, USA: Cambridge University Press,

2005.

4. J. K. Tugnait, L. Tong, and Z. Ding, “Single-user channel estimation and equalization,” IEEE

Signal Processing Magazine, vol. 17, pp. 16–28, 2000.

5. W. C. Jakes, Microwave Mobile Communiations. Wiley, 1974.

6. T. Moore, “IEEE 802.11-01/610r02: 802.1x and 802.11 key interactions,” Microsoft Research,

2001.

7. S. Fortune, D. M. Gay, B. Kernighan, O. Landron, R. A. Valenzuela, and M. Wright, “Wise

design of indoor wireless systems: practical computation andoptimization,” Computational

Science and Engineering, IEEE, vol. 2, no. 1, pp. 58–68, April 1995.

30 Suhas Mathur, Wade Trappe, Narayan Mandayam, Chunxuan Ye, Alex Reznik

8. N. Patwari and S. K. Kasera, “Robust location distinction using temporal link signatures,”

in MobiCom ’07: Proceedings of the 13th annual ACM international conference on Mobile

computing and networking, 2007, pp. 111–122.

9. L. Xiao, L. Greenstein, N. Mandayam, and W. Trappe, “Fingerprints in the ether: Using the

physical layer for wireless authentication,” in Proceedings of the IEEE Int.. Conf. on Comm.,

2007, pp. 4646 – 4651.

10. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography.

CRC Press, 1996.

11. U. M. Maurer, “A universal statistical test for random bit generators,” Journal of Cryptology,

vol. 5, pp. 89–105, 1992.

12. “http://csrc.nist.gov/groups/st/toolkit/rng/.”

13. NIST, “A statistical test suite for the validation of random number generators and pseudo

random number generators for cryptographic applications,” 2001.

14. “IEEE 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.”

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

16. Q. Wang, S. R. Kulkarni, and S. Verdu, “A nearest-neighbor approach to estimating divergence

between continuous random vectors,” in Int. Symp. on Inform. Theory, 2006, pp. 242–246.

17. “http://www.atheros.com/.”

18. “http://www.madwifi.org/.”

19. “http://www.tcpdump.org.”

20. U. Maurer, “Secret key agreement by public discussion from common information,” IEEE

Transactions on Information Theory, vol. 39, no. 4, pp. 733–742, 1993.

21. R. Ahlswede and I. Csiszar, “Common randomness in information theory and cryptography –

Part I: Secret sharing,” IEEE Transactions on Information Theory, vol. 39, no. 4, pp. 1121–

1132, 1993.

22. J. Cardinal and G. V. Assche, “Construction of a shared secret key using continuous variables,”

Info. Theory Workshop, 2003.

23. G. Brassard and L. Salvail, “Secret key reconciliation by public discussion,” Advances in

Crytology Proc. - Eurocrypt ’93, Lecture Notes in Computer Science, vol. 765, pp. 410–423,

1994.

24. C. Ye, A. Reznik, and Y. Shah, “Extracting secrecy from jointly Gaussian random variables,”

in Proceedings of IEEE Int. Symp on Info. Theory, Jul 2006, pp. 2593 – 2597.

25. C. Cachin and U. M. Maurer, “Linking information reconciliation and privacy amplification,”

Journal of Cryptology: the journal of the International Association for Cryptologic Research,

vol. 10, no. 2, pp. 97–110, Spring 1997.

26. C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by public discussion,”

SIAM J. Comput., vol. 17, no. 2, pp. 210–229, 1988.

27. 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, vol. 67,

pp. 052 303.1–052 303.8, 2003.

28. G. V. Assche, Quantum Cryptography and Secret Key Distillation. Cambridge University

Press, 2006.

29. U. Maurer and S. Wolf, “Secret key agreement over a non-authenticated channel -Part II: The

simulatability condition,” IEEE Transactions on Information Theory, vol. 49, no. 4, pp. 832–

838, Apr. 2003.

30. Z. Li, W. Xu, R. Miller, and W. Trappe, “Securing wireless systems via lower layer enforce-

ments,” in WiSe ’06: Proceedings of the 5th ACM workshop on Wireless security, 2006, pp.

33–42.

31. B. Azimi-Sadjadi, A. Kiayias, A. Mercado, and B. Yener, “Robust key generation from signal

envelopes in wireless networks,” in CCS ’07: Proceedings of the 14th ACM conference on

Computer and communications security, 2007, pp. 401–410.

32. R. Wilson, D. Tse, and R. Scholtz, “Channel identification: Secret sharing using reciprocity in

UWB channels,” IEEE Transactions on Information Forensics and Security, vol. 2, no. 3, pp.

364–375, 2007.

1 Secret Key Extraction from Level Crossings over Unauthenticated Wireless Channels 31

33. T. Aono, K. Higuchi, T. Ohira, B. Komiyama, and H. Sasaoka, “Wireless secret key genera-

tion exploiting reactance-domain scalar response of multipath fading channels,” IEEE Trans-

actions on Antennas and Propagation, vol. 53, no. 11, pp. 3776–3784, Nov 2005.

34. A. Hassan, W. Stark, J. Hershey, and S. Chennakeshu, “Cryptographic key agreement for

mobile radio,” Digital Signal Processing, vol. 6, pp. 207–212, 1996.

35. H. Koorapaty, A. Hassan, and S. Chennakeshu, “Secure information transmission for mobile

radio,” IEEE Communication Letters, vol. 4, no. 2, Feb 2000.

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