Information Technology Reference
In-Depth Information
(without the additional cost of applying an erasure code to already-redundant
data), and which does not interrupt the flow of payload data.
Perrig et al. [1,2,3] have considered the problem of ecient authentication for
lossy data streams, but our work considers a somewhat different set of issues.
Protocols such as
μ
TESLA [2] have low overhead compared to earlier authen-
tication methods for such streams, but “low overhead” in their context means
tens of bytes; our work considers a scenario in which we may add only a few
bits to each message. In order to attain such extreme bandwidth eciency, it
is necessary to constrain the problem somewhat. The
μ
TESLA protocol specifi-
cally addresses the problem of
broadcast
in sensor networks, but our work is only
applicable to point-to-point communication, because we assume that the sender
and receiver share a symmetric key.
2 Subset Authentication
Our basic approach is to append a short authentication tag
a
i
to each message
m
i
;each
a
i
is an
r
-bit authentication tag for some appropriately-chosen subset
S
i
of the previous messages. Let
A
K
be a message authentication code (MAC)
with key
K
that produces an
r
-bit output. Thus if
S
i
=
j
1
<j
2
<
j
k
}
{
···
we
have
1
a
i
=
A
K
(
i
|
m
j
1
|···|
m
j
k
)
(1)
and we transmit
m
1
,a
1
,m
2
,a
2
,
. If each message is contained in
q
sets, then
each message is used in the computation of
q
different tags, and we will eventually
accumulate the required
qr
bits of authentication for each message. If
···
A
K
is a
pseudorandom function, an adversary cannot cause an invalid
m
i
to be accepted
without guessing
qr
random bits. In practice,
A
K
could be implemented by
truncating the output of a full-length authentication code such as HMAC with
SHA-1 [4]. The design of an equally secure but less computationally intensive
MAC which inherently produces a short output would pose an interesting and
challenging problem.
It is essential to include the sequence number
i
in the computation of
a
i
,
so that an attacker cannot replay the same data with different authentication
bits and attack each
r
bit tag separately. We are here making a non-standard
security assumption; an attacker only has access to a
stateful
verification oracle.
Once this oracle has answered one query for a message with sequence number
i
, it will not answer queries (or will always answer “no”) for any message with
sequence number
i
. This is a plausible assumption in many cases, especially
for data with a short lifetime, which is likely to be the case in our intended
applications. Some non-standard assumption of this type is necessary to achieve
our very strong eciency requirements.
Given that bandwidth is very constrained, we would seek to avoid explicitly
transmitting the entire sequence number with each message. In particular, if
≤
1
It is convenient to ignore the distinction between a message and its index, writing
j
∈
S
i
instead of
m
j
∈
S
i
.
