06-05-2014, 02:46 PM
Efficient Spread Spectrum Communication without Preshared Secrets
Abstract
Spread spectrum (SS) communication relies on the assumption that some secret is shared beforehand among
communicating nodes to establish the spreading sequence for long-term wireless communication. Strasser et al. identified this as the
circular dependency problem (CDP). This problem is exacerbated in large networks, where nodes join and leave the network frequently,
and preconfiguration of secrets through physical contact is infeasible. In this work, we introduce an efficient and adversary-resilient
secret sharing mechanism based on two novel paradigms (intractable forward decoding, efficient backward decoding) called Time
Reversed Message Extraction and Key Scheduling (TREKS) that enables SS communication without preshared secrets. TREKS is
four orders of magnitude faster than previous solutions to the CDP. Furthermore, our approach can be used to operate long-term SS
communication without establishing any keys. The energy cost under TREKS is provably optimal with minimal storage overhead, and
computation cost at most twice that of traditional SS. We evaluate TREKS through simulation and empirically using an experimental
testbed consisting of USRP, GNU Radio, and GPU-equipped nodes. Using TREKS under a modest hardware setup, we can sustain a
1-Mbps long-term SS communication spread by a factor of 100 (i.e., 100 Megachips per second) over a 200-MHz bandwidth in real time.
INTRODUCTION
R ADIO-FREQUENCY
(RF) wireless communication is ex-
posed to adversaries that could eavesdrop trying
to get hold of important information, or jam trying to
prevent communication from happening. Resiliency to
malicious behavior is highly desirable on wireless environ-
ments, as reliance on wireless communication becomes
increasingly common for monitoring physical infrastruc-
ture or equipment.
Privacy issues in communication have been at the
forefront of networks research for decades, focusing mostly
on the protection of voice communication [2] and physical
layer, and use of Spread Spectrum (SS) techniques. Net-
works were small, allowing for easy node preconfiguration.
Today, however, communicating nodes from various
manufacturers enter and leave the networks dynamically,
making preconfiguration impractical. The alternative of
establishing SS keys over the air is subject to jamming,
creating a Circular Dependency Problem (CDP as coined
by Strasser et al. [3]), an obstacle for wider SS deployments.
Related Work
Antijamming techniques have been studied for decades, but
reliable communication in the presence of adversaries has
gained significant interest in the last few years. Several
specifically crafted attacks and counterattacks were pro-
posed for packetized wireless data networks [5], [6],
multiple access resolution in the presence of adversaries
[7], [4], [8], multihop networks [9], [10], [6], broadcast
communication [11], [12], [13], cross-layer attacks [5], and
navigation information broadcast [14]. While many recently
proposed countermeasure techniques can (and are assumed
to) be layered on a SS physical layer, it is usually taken for
granted that the communicating nodes preshare a secret
key. Recently, several countermeasures that do not consider
the possibility of using SS were proposed, considering
narrow RF bands or no preshared key [15], [8]. While some
of these techniques are theoretically optimal for the
considered physical layer, they are less energy efficient
than SS. Strasser et al. [3] recognized this presharing
requirement as a significant impediment to the use of SS,
even when the communicating nodes possess public keys
and certificates that potentially allow them to setup a
shared secret key.
Communication and Adversary
We consider a wireless network where nodes communicate
in pairs in the presence of adversaries through the use of SS.
Participants lack any preshared secret, which is a prerequi-
site for traditional SS communication systems. The goal of
the sender is to establish an adversary resilient and energy
efficient communication. The only goal of the adversary is
to prevent the receiver from decoding its messages.
Under our model, an adversary is within range of the
sender and the receiver, and can possibly jam, replay
previously collected messages or insert/modify bits of
messages. The goal of the adversary is to prevent a
successful reception of the message. The adversary’s utility
function is a tradeoff between the energy cost spent on
adversarial attacks versus the packet loss rate (PLR) on
the receiver side. We also evaluate the adversary in terms
of the delay incurred by its attacks on the receiver’s
decoding process.
Zero Preshared Key DSSS
Sender S, receiver R, and jammer J share the same physical
channel. Let M denote the message from S to R, and l the
length of M in bits. Prior to the start of transmission, S
randomly chooses a secret key K of length k bits. S then
uses K to generate a cryptographically strong PN-sequence
to spread M. Although PN-sequences generated from
cryptographic means (such as AES or DES) are not
orthogonally optimal, they have been used successfully in
military SS communication systems [2].
Implementation
To implement TREKS we use the Universal Software Radio
Peripheral (USRP) [21], and three different NVIDIA graphic
cards [22] to implement a sender and three receivers with
different computational powers. On the software side, we
employ GNU Radio as SDR [23] and the NVIDIA Compute
Unified Device Architecture (CUDA) for GPU program-
ming [24]. Our PN-generation is implemented using AES
with 128-bit keys [19]. See Figs. 1 and 10a for an overview of
the setup and main system components
CONCLUSION
In this paper, we propose new mechanisms, design, and a
full implementation of a real-time direct sequence spread
spectrum system that does not require preshared secrets
between the parties. We use readily available components
to build our demonstrator, displaying four orders of
magnitude improvement of computation cost in compar-
ison to existing schemes. We are able to sustain (in terms of
computation) a 1-Mbps bit-rate spread by a factor of a
100 (i.e., 100 Mega chips per second) spread over 200-MHz
bandwidth. Finally, we evaluate both the computation cost
and the achieved resiliency.
Abstract
Spread spectrum (SS) communication relies on the assumption that some secret is shared beforehand among
communicating nodes to establish the spreading sequence for long-term wireless communication. Strasser et al. identified this as the
circular dependency problem (CDP). This problem is exacerbated in large networks, where nodes join and leave the network frequently,
and preconfiguration of secrets through physical contact is infeasible. In this work, we introduce an efficient and adversary-resilient
secret sharing mechanism based on two novel paradigms (intractable forward decoding, efficient backward decoding) called Time
Reversed Message Extraction and Key Scheduling (TREKS) that enables SS communication without preshared secrets. TREKS is
four orders of magnitude faster than previous solutions to the CDP. Furthermore, our approach can be used to operate long-term SS
communication without establishing any keys. The energy cost under TREKS is provably optimal with minimal storage overhead, and
computation cost at most twice that of traditional SS. We evaluate TREKS through simulation and empirically using an experimental
testbed consisting of USRP, GNU Radio, and GPU-equipped nodes. Using TREKS under a modest hardware setup, we can sustain a
1-Mbps long-term SS communication spread by a factor of 100 (i.e., 100 Megachips per second) over a 200-MHz bandwidth in real time.
INTRODUCTION
R ADIO-FREQUENCY
(RF) wireless communication is ex-
posed to adversaries that could eavesdrop trying
to get hold of important information, or jam trying to
prevent communication from happening. Resiliency to
malicious behavior is highly desirable on wireless environ-
ments, as reliance on wireless communication becomes
increasingly common for monitoring physical infrastruc-
ture or equipment.
Privacy issues in communication have been at the
forefront of networks research for decades, focusing mostly
on the protection of voice communication [2] and physical
layer, and use of Spread Spectrum (SS) techniques. Net-
works were small, allowing for easy node preconfiguration.
Today, however, communicating nodes from various
manufacturers enter and leave the networks dynamically,
making preconfiguration impractical. The alternative of
establishing SS keys over the air is subject to jamming,
creating a Circular Dependency Problem (CDP as coined
by Strasser et al. [3]), an obstacle for wider SS deployments.
Related Work
Antijamming techniques have been studied for decades, but
reliable communication in the presence of adversaries has
gained significant interest in the last few years. Several
specifically crafted attacks and counterattacks were pro-
posed for packetized wireless data networks [5], [6],
multiple access resolution in the presence of adversaries
[7], [4], [8], multihop networks [9], [10], [6], broadcast
communication [11], [12], [13], cross-layer attacks [5], and
navigation information broadcast [14]. While many recently
proposed countermeasure techniques can (and are assumed
to) be layered on a SS physical layer, it is usually taken for
granted that the communicating nodes preshare a secret
key. Recently, several countermeasures that do not consider
the possibility of using SS were proposed, considering
narrow RF bands or no preshared key [15], [8]. While some
of these techniques are theoretically optimal for the
considered physical layer, they are less energy efficient
than SS. Strasser et al. [3] recognized this presharing
requirement as a significant impediment to the use of SS,
even when the communicating nodes possess public keys
and certificates that potentially allow them to setup a
shared secret key.
Communication and Adversary
We consider a wireless network where nodes communicate
in pairs in the presence of adversaries through the use of SS.
Participants lack any preshared secret, which is a prerequi-
site for traditional SS communication systems. The goal of
the sender is to establish an adversary resilient and energy
efficient communication. The only goal of the adversary is
to prevent the receiver from decoding its messages.
Under our model, an adversary is within range of the
sender and the receiver, and can possibly jam, replay
previously collected messages or insert/modify bits of
messages. The goal of the adversary is to prevent a
successful reception of the message. The adversary’s utility
function is a tradeoff between the energy cost spent on
adversarial attacks versus the packet loss rate (PLR) on
the receiver side. We also evaluate the adversary in terms
of the delay incurred by its attacks on the receiver’s
decoding process.
Zero Preshared Key DSSS
Sender S, receiver R, and jammer J share the same physical
channel. Let M denote the message from S to R, and l the
length of M in bits. Prior to the start of transmission, S
randomly chooses a secret key K of length k bits. S then
uses K to generate a cryptographically strong PN-sequence
to spread M. Although PN-sequences generated from
cryptographic means (such as AES or DES) are not
orthogonally optimal, they have been used successfully in
military SS communication systems [2].
Implementation
To implement TREKS we use the Universal Software Radio
Peripheral (USRP) [21], and three different NVIDIA graphic
cards [22] to implement a sender and three receivers with
different computational powers. On the software side, we
employ GNU Radio as SDR [23] and the NVIDIA Compute
Unified Device Architecture (CUDA) for GPU program-
ming [24]. Our PN-generation is implemented using AES
with 128-bit keys [19]. See Figs. 1 and 10a for an overview of
the setup and main system components
CONCLUSION
In this paper, we propose new mechanisms, design, and a
full implementation of a real-time direct sequence spread
spectrum system that does not require preshared secrets
between the parties. We use readily available components
to build our demonstrator, displaying four orders of
magnitude improvement of computation cost in compar-
ison to existing schemes. We are able to sustain (in terms of
computation) a 1-Mbps bit-rate spread by a factor of a
100 (i.e., 100 Mega chips per second) spread over 200-MHz
bandwidth. Finally, we evaluate both the computation cost
and the achieved resiliency.