- ...Channels
- This work began in Summer 1999 when Adrian Perrig and Dawn
Song were visiting the IBM T. J. Watson research lab. Initial research on
stream authentication was done during Summer 1999 by Ran Canetti, Adrian
Perrig, and Dawn Song at IBM. Additional improvements were suggested by J.
D. Tygar in Fall 1999 at UC Berkeley. Implementation was done in Fall 1999
by Adrian Perrig at UC Berkeley. The work on stream signatures was done by
J. D. Tygar, Adrian Perrig, and Dawn Song at UC Berkeley. Additional work
was performed by Ran Canetti in Spring 2000. Ran Canetti is at IBM T. J.
Watson Research Center, and Adrian Perrig, Dawn Song, and J. D. Tygar are
at the Computer Science Division, UC Berkeley.
This research was suported in part by the Defense Advanced Research
Projects Agency under DARPA contract N6601-99-28913 (under supervision of
the Space and Naval Warfare Systems Center San Diego), by the National
Science foundation under grant FD99-79852, and by the United States Postal
Service under grant USPS 1025 90-98-C-3513. Views and conclusions
contained in this document are those of the authors and do not necessarily
represent the official opinion or policies, either expressed or implied of
the US government or any of its agencies, DARPA, NSF, USPS, or IBM.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...enforced.
- However, the scheme does not provide non-repudiation.
That is, the recipient cannot convince a third party that the stream arrived
from the claimed source.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...seconds.
- Many
clock synchronization algorithms exist, for example the work of Mills on NTP
[22], and its security analysis [5].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...function.
- I.e., it is infeasible, given
to find such that . Even if
the attacker could find such a collision then it would be
able to forge only a single message . Forging additional messages
would require inverting , i.e., finding such that
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...receiver
- The terms sender and receiver appear reversed in the
description of this time synchronization protocol, because we keep their role
with respect to the stream authentication scheme. So it is the receiver that
synchronizes its time with the sender's.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...guaranteed.
- The argumentation against this method claims that it
would put too much burden on the network layer to buffer data packet. For the
case of IP fragmentation, however, the network layer already buffers data and
forwards it to the application only when the entire packet is complete.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...probability.
- Our first
attempt was to devise an analytical formula to model the probability for each
node that it is connected to a signature node. Unfortunately, finding an
exact formula is harder than it first appears, so deriving the analytical
formula automatically for a given edge distribution remains an open problem.
We illustrate this complexity with an example for the recurrence relation
which describes the simple 1-2-4 scheme: , where is
the probability that node is connected to node which is signed, and
is the probability that the node is dropped.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...CLASS=INLINE>60%.
- We chose to
use six edges per node, because we wanted to achieve a high average robustness
for the case of packet loss and with only five edges did not give us a
high verification probability.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...packets,
- The loss
probability might be different for signature packets if they are sent
redundantly or in a higher service class in the context of QoS.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...packets.
- The packet id's of the
packet do not need to be stored in the packet for two reasons. Since the
probability of a hash collision is negligible, the receiver can store the hash
of the last data packets it received. If any packet contains the same
hash value, we consider that packet as verified, if the current packet can be
verified. Alternatively, we could build a deterministically computable random
graph over the packets, and the receiver would reconstruct it. This
alternative would require a packet id in each packet.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...MAC.
- In fact, we do not need the full security guarantee of a PRF. It
suffices to have a (length-doubling) pseudorandom generator with a similar TCR
property to the one described above. Nonetheless, for simplicity we describe
our schemes as ones using a full-fledged PRF.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.