Information Technology Reference
In-Depth Information
Distance-Avoiding Sequences for Extremely
Low-Bandwidth Authentication
Michael J. Collins and Scott Mitchell
Sandia National Laboratories
Albuquerque, NM 87185, USA
mjcolli@sandia.gov
Abstract.
We develop a scheme for providing strong cryptographic au-
thentication on a stream of messages which consumes very little band-
width (as little as one bit per message) and is robust in the presence of
dropped messages. Such a scheme should be useful for extremely low-
power, low-bandwidth wireless sensor networks and “smart dust” appli-
cations. The tradeoffs among security, memory, bandwidth, and tolerance
for missing messages give rise to several new optimization problems. We
report on experimental results and derive bounds on the performance of
the scheme.
1
Introduction and Previous Work
We consider the following scenario: we wish to send a stream of many short mes-
sages
m
1
,m
2
,m
3
,
···
on a channel with very limited bandwidth, and we need to
provide strong cryptographic authentication for this data. Because bandwidth is
so limited, we assume that we must use almost all transmitted bits for delivering
payload data: say we can append no more than
r
bits of authentication to each
message, where
r
is too small to provide adequate security. Such a situation might
arise for power-scavenging or energy harvesting systems, since communication is
generally energy-intensive relative to computation.
Suppose we have decided that
qr
authentication bits are needed for security; a
simple solution would be to send
q
consecutive messages
m
1
,m
2
,
m
q
, followed
by a message authentication tag
t
of length
qr
for the concatenated message
(
m
1
|
···
m
q
) (repeating this process for the next block of
q
messages and
so on). This achieves the desired data rate, but it is unsatisfactory for several
reasons. In an extremely low-power environment (such as a wireless network of
very small sensors), we expect that many messages will be dropped or corrupted,
making it impossible for the receiver to verify the correctness of
t
. Also, we are
transmitting no data at all during the relatively long time needed to transmit the
tag. We seek a more robust solution which will tolerate some missing messages
m
2
|···
Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed
Martin Company, for the United States Department of Energy's National Nuclear
Security Administration under contract DE-AC04-94AL85000.
