< draft-ietf-msec-tesla-intro-02.txt   draft-ietf-msec-tesla-intro-03.txt >
Internet Engineering Task Force IETF MSEC Internet Engineering Task Force IETF MSEC
Internet Draft Perrig, Canetti, Song, Tygar, Briscoe Internet Draft Perrig, Canetti, Song, Tygar, Briscoe
draft-ietf-msec-tesla-intro-02.txt UC Berkeley / Digital Fountain / IBM / BT draft-ietf-msec-tesla-intro-03.txt CMU / IBM / CMU / UC Berkeley / BT
May 2004 August 2004
Expires: November 2004 Expires: 1 February 2005
TESLA: Multicast Source Authentication Transform Introduction TESLA: Multicast Source Authentication Transform Introduction
STATUS OF THIS MEMO STATUS OF THIS MEMO
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet other groups may also distribute working documents as Internet
Drafts. Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress". or to cite them other than as "work in progress".
To view the list Internet-Draft Shadow Directories, see To view the list Internet-Draft Shadow Directories, see
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
Data authentication is an important component for many applications, Data authentication is an important component for many broadcast
for example audio and video Internet broadcasts, or data distribution applications, for example audio and video Internet broadcasts, or
by satellite. This document introduces TESLA, a secure source data distribution by satellite. This document introduces TESLA,
authentication mechanism for multicast or broadcast data streams. This short for Timed Efficient Stream Loss-tolerant Authentication, a
document provides an algorithmic description of the scheme for secure source authentication mechanism for multicast or broadcast
informational purposes, and in particular, it is intended to assist data streams. This document provides an algorithmic description of
in writing standardizable and secure specifications for protocols TESLA for informational purposes, and in particular, is intended to
based on TESLA in different contexts. assist in writing standardizable and secure specifications for
protocols based on TESLA in different contexts.
The main deterrents so far for a data authentication mechanism for The main deterrents so far for a data authentication mechanism for
multicast were the seemingly conflicting requirements: loss tolerance, multicast were the seemingly conflicting requirements: loss
high efficiency, no per-receiver state at the sender. The problem tolerance, efficiency, and no per-receiver state at the sender. The
is particularly hard in settings with high packet loss rates and problem is particularly hard in settings with high packet loss
where lost packets are not retransmitted, and where the receiver rates and where lost packets are not retransmitted, and where the
wants to authenticate each packet it receives. receivers want to authenticate each packet they do receive.
TESLA provides authentication of individual data packets, regardless TESLA provides authentication of individual data packets,
of the packet loss rate. In addition, TESLA features low overhead for regardless of loss rate. In addition, TESLA features low overhead
both sender and receiver, and does not require per-receiver state at for both sender and receiver, and does not require per-receiver
the sender. TESLA is secure as long as the sender and receiver are state at the sender. TESLA is secure as long as the sender and
loosely time synchronized. receiver are loosely time synchronized.
Table of Contents Table of Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2
1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Functionality . . . . . . . . . . . . . . . . . . . . . . 4 2 Functionality . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Threat Model and Security Guarantee . . . . . . . . . . . 4 2.1 Threat Model and Security Guarantee . . . . . . . . . . . 4
2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5
3 The Basic TESLA Protocol . . . . . . . . . . . . . . . . 5 3 The Basic TESLA Protocol . . . . . . . . . . . . . . . . 5
3.1 Sketch of protocol . . . . . . . . . . . . . . . . . . . 6 3.1 Protocol sketch . . . . . . . . . . . . . . . . . . . . . 6
3.2 Sender Setup . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Sender Setup . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Bootstrapping Receivers . . . . . . . . . . . . . . . . . 7 3.3 Bootstrapping Receivers . . . . . . . . . . . . . . . . . 7
3.3.1 Time Synchronization. . . . . . . . . . . . . . . . . . . 8 3.3.1 Time Synchronization. . . . . . . . . . . . . . . . . . . 8
3.4 Broadcasting Authenticated Messages . . . . . . . . . . . 8 3.4 Broadcasting Authenticated Messages . . . . . . . . . . . 8
3.5 Authentication at Receiver . . . . . . . . . . . . . . . 8 3.5 Authentication at Receiver . . . . . . . . . . . . . . . 8
3.6 Determining the Key Disclosure Delay . . . . . . . . . . 9 3.6 Determining the Key Disclosure Delay . . . . . . . . . . 9
3.7 An alternative delay description method . . . . . . . . . 10 3.7 An alternative delay description method . . . . . . . . . 10
3.8 Some extensions . . . . . . . . . . . . . . . . . . . . . 11 3.8 Some extensions . . . . . . . . . . . . . . . . . . . . . 11
4 Layer placement . . . . . . . . . . . . . . . . . . . . . 11 4 Layer placement . . . . . . . . . . . . . . . . . . . . . 11
5 Security considerations . . . . . . . . . . . . . . . . . 11 5 Security considerations . . . . . . . . . . . . . . . . . 11
6 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 12 6 IP statement . . . . . . . . . . . . . . . . . . . . . . .12
7 Bibliography . . . . . . . . . . . . . . . . . . . . . . 12 7 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 12
8 References . . . . . . . . . . . . . . . . . . . . . . . 12
A Author Contact Information . . . . . . . . . . . . . . . 13 A Author Contact Information . . . . . . . . . . . . . . . 13
B Full Copyright Statement . . . . . . . . . . . . . . . . 14 B Full Copyright Statement . . . . . . . . . . . . . . . . 14
1 Introduction 1 Introduction
The power of multicast is that one packet can reach millions of In multicast, a single packet can reach millions of receivers. This
receivers. This great property is unfortunately also a great danger: unfortunately also introduces the danger that an attacker can
an attacker that sends one malicious packet can also potentially potentially also reach millions of receivers with a malicious
reach millions of receivers. Receivers need multicast source packet. Through source authentication, receivers can ensure that a
authentication to ensure that a given packet originates from the correct received multicast packet originates from the correct source.
source.
In unicast communication, we can achieve data authentication through In unicast communication, we can achieve data authentication
a purely symmetric mechanism: the sender and the receiver share a through a simple mechanism: the sender and the receiver share a
secret key to compute a message authentication code (MAC) of all secret key to compute a message authentication code (MAC) of all
communicated data. When a message with a correct MAC arrives, the communicated data. When a message with a correct MAC arrives, the
receiver is assured that the sender generated that message. Standard receiver is assured that the sender generated that message.
mechanisms achieve unicast authentication this way, for example TLS Standard mechanisms achieve unicast authentication this way, for
or IPsec [1,2]. example TLS or IPsec [1,2].
The symmetric MAC authentication is not secure in a broadcast The symmetric MAC authentication is not secure in a broadcast
setting. Consider a sender that broadcasts authentic data to mutually setting. Consider a sender that broadcasts authentic data to mutually
untrusting receivers. The symmetric MAC is not secure: every receiver untrusting receivers. The symmetric MAC is not secure: every receiver
knows the MAC key, and hence could impersonate the sender and forge knows the MAC key, and hence could impersonate the sender and forge
messages to other receivers. Intuitively, we need an asymmetric messages to other receivers. Intuitively, we need an asymmetric
mechanism to achieve authenticated broadcast, such that every receiver mechanism to achieve authenticated broadcast, such that every receiver
can verify the authenticity of messages it receives, without being can verify the authenticity of messages it receives, without being
able to generate authentic messages. Achieving this in an efficient able to generate authentic messages. Achieving this in an efficient
way is a challenging problem [3]. way is a challenging problem [3].
The standard approach to achieve such asymmetry for authentication is The standard approach to achieve such asymmetry for authentication
to use asymmetric cryptography, for instance a digital signature. is to use asymmetric cryptography, e.g., a digital signature.
Digital signatures have the required asymmetric property: the sender Digital signatures have the required asymmetric property: the
generates the signature with its private key, and all receivers can sender generates the signature with its private key, and all
verify the signature with the sender's public key, but a receiver receivers can verify the signature with the sender's public key,
with the public key alone cannot generate a digital signature for a but a receiver with the public key alone cannot generate a digital
new message. A digital signature provides non-repudiation, which is a signature for a new message. A digital signature provides
stronger property than authentication. Unfortunately, digital non-repudiation, a stronger property than authentication. However,
signatures have a high cost: they have a high computation overhead for digital signatures have a high cost: they have a high computation
both the sender and the receiver, as well as a high communication overhead for both the sender and the receiver, and most signatures
overhead. Since we assume broadcast settings where the sender does also have a high bandwidth overhead. Since we assume broadcast
not retransmit lost packets, and the receiver still wants to settings where the sender does not retransmit lost packets, and the
immediately authenticate each packet it receives, we would need to receiver still wants to immediately authenticate each packet it
attach a digital signature to each message. Because of the high receives, we would need to attach a digital signature to each
overhead of asymmetric cryptography, this approach would restrict message. Because of the high overhead of asymmetric cryptography,
us to low-rate streams, and to senders and receivers with powerful this approach would restrict us to low-rate streams, and to senders
workstations. To deal with the high overhead of asymmetric cryptography, and receivers with powerful workstations. We can try to amortize one
we can try to amortize one digital signature over multiple messages. digital signature over multiple messages. However, such an
However, such an approach is still expensive in contrast to symmetric approach is still expensive in contrast to symmetric cryptography,
cryptography, since symmetric cryptography is in general 3 to 5 orders since symmetric cryptography is in general 3 to 5 orders of
of magnitude more efficient than asymmetric cryptography. In addition, magnitude more efficient than asymmetric cryptography. In addition,
the straight-forward amortization of one digital signature over multiple the straight-forward amortization of one digital signature over
packets requires reliability, as the receiver needs to receive all multiple packets requires reliability, as the receiver needs to
packets to verify the signature. A number of schemes that follow this receive all packets to verify the signature. A number of schemes
approach are [4,5,6,7,8]. See [9] for more details. that follow this approach are [4,5,6,7,8]. See [9] for more
details.
This document presents the Timed Efficient Stream Loss-tolerant This document presents the Timed Efficient Stream Loss-tolerant
Authentication protocol (TESLA). TESLA uses mainly symmetric Authentication protocol (TESLA). TESLA uses mainly symmetric
cryptography, and uses time delayed key disclosure to achieve the cryptography, and uses time delayed key disclosure to achieve the
required asymmetry property. However, TESLA requires loosely required asymmetry property. However, TESLA requires loosely
synchronized clocks between the sender and the receivers. See more synchronized clocks between the sender and the receivers. See more
details in Section 4. Other schemes that follow a similar approach details in Section 4. Other schemes that follow a similar approach
to TESLA are [10,11,12]. to TESLA are [10,11,12].
1.1 Notation 1.1 Notation
To denote the subscript or an index of a variable, we use the To denote the subscript or an index of a variable, we use the
underscore between the variable name and the index, e.g. the key K with underscore between the variable name and the index, e.g., the key K
index i is K_i, the key K with index i+d is K_{i+d}. To write a with index i is K_i, the key K with index i+d is K_{i+d}. To write
superscript we use the caret, e.g. the function F with the argument x a superscript we use the caret, e.g., function F with the argument
executed i times is F^i(x), executed j-1 times we write F^{j-1}(x). x executed i times is F^i(x).
2 Functionality 2 Functionality
TESLA provides delayed per-packet data authentication. The key idea TESLA provides delayed per-packet data authentication. The key idea
to providing both efficiency and security is a delayed disclosure of to providing both efficiency and security is a delayed disclosure of
keys. The delayed key disclosure results in an authentication delay. keys. The delayed key disclosure results in an authentication delay.
In practice, the delay is on the order of one RTT (Round-trip-time). In practice, the delay is on the order of one RTT (round-trip-time).
TESLA has the following properties: TESLA has the following properties:
¸ Low computation overhead for generation and verification of o Low computation overhead for generation and verification of
authentication information authentication information
¸ Low communication overhead o Low communication overhead
¸ Limited buffering required for the sender and the receiver, hence o Limited buffering required for the sender and the receiver, hence
timely authentication for each individual packet timely authentication for each individual packet
¸ Strong robustness to packet loss o Strong robustness to packet loss
¸ Scales to a large number of receivers o Scales to a large number of receivers
¸ Security is guaranteed as long as the sender and recipients are o Security is guaranteed as long as the sender and recipients are
loosely time synchronized, where synchronization can take place loosely time synchronized, where synchronization can take place
at session set-up. at session set-up.
TESLA can be used either in the network layer, or in the transport TESLA can be used either in the network layer, or in the transport
layer, or in the application layer. The delayed authentication, layer, or in the application layer. The delayed authentication,
however, requires buffering of packets until authentication is completed. however, requires buffering of packets until authentication is
completed. Certain applications intolerant of delay may be willing to
process packets in parallel to being buffered awaiting authentication,
as long as roll-back is possible if packets are later found to be
unauthenticated. For instance, an interactive video may play-out
packets still awaiting authentication, but if they are later found to
be unauthenticated, it could stop further play-out and warn the viewer
that the last x msec were unauthenticated and should be ignored.
However, in the remainder of this document, for brevity, we will
assume packets are not processed in parallel to buffering.
2.1 Threat Model and Security Guarantee 2.1 Threat Model and Security Guarantee
We design TESLA to be secure against a powerful adversary with the We design TESLA to be secure against a powerful adversary with the
following capabilities: following capabilities:
¸ Full control over the network. The adversary can eavesdrop, o Full control over the network. The adversary can eavesdrop,
capture, drop, resend, delay, and alter packets. capture, drop, resend, delay, and alter packets.
¸ Access to a fast network with negligible delay. o Access to a fast network with negligible delay.
¸ The adversary's computational resources may be very large, but o The adversary's computational resources may be very large, but
not unbounded. In particular, this means that the adversary can not unbounded. In particular, this means that the adversary can
perform efficient computations, such as computing a reasonable perform efficient computations, such as computing a reasonable
number of pseudo-random function applications and MACs with number of pseudo-random function applications and MACs with
negligible delay. Nonetheless, the adversary cannot find the key negligible delay. Nonetheless, the adversary cannot find the key
of a pseudorandom function (or distinguish it from a random of a pseudorandom function (or distinguish it from a random
function) with non-negligible probability. function) with non-negligible probability.
The security property of TESLA guarantees that the receiver never The security property of TESLA guarantees that the receiver never
accepts M_i as an authentic message unless the sender really sent accepts M_i as an authentic message unless the sender really sent
M_i. A scheme that provides this guarantee is called a secure M_i. A scheme that provides this guarantee is called a secure
broadcast authentication scheme. broadcast authentication scheme.
Since TESLA requires the receiver to buffer packets before Since TESLA expects the receiver to buffer packets before
authentication, the receiver needs to protect itself from a authentication, the receiver needs to protect itself from a
potential denial-of-service (DOS) attack due to a flood of bogus packets. potential denial-of-service (DOS) attack due to a flood of bogus
packets.
2.2 Assumptions 2.2 Assumptions
TESLA makes the following assumptions in order to provide security: TESLA makes the following assumptions in order to provide security:
1. The sender and the receiver must be be able to loosely 1. The sender and the receiver must be be able to loosely
synchronize. Specifically, each receiver must be able to synchronize. Specifically, each receiver must be able to
compute an upper bound on the lag of the receiver clock compute an upper bound on the lag of the receiver clock
relative to the sender clock. We denote this quantity by D_t. relative to the sender clock. We denote this quantity by D_t.
(That is, D_t = sender time - receiver time). (That is, D_t = sender time - receiver time). We note that
We note that an upper bound on D_t can be easily obtained via an upper bound on D_t can be easily obtained via a simple
a simple two-message exchange. (Such an exchange can be two-message exchange. (Such an exchange can be piggybacked on
piggybacked on any session initiation protocol. Alternatively, any secure session initiation protocol. Alternatively, standard
standard protocols such as as NTP [16] can be used. protocols such as as NTP [16] can be used.
(The synchronization assumption of TESLA is considerably weaker
the synchronization requirements of authentication protocols based
on timestamps. In those protocols, the participants are
assumed to have the same global time a-priori.)
2. TESLA MUST be bootstrapped at session set-up through a regular 2. TESLA MUST be bootstrapped at session set-up through a
data authentication system. We recommend to use a digital regular data authentication system. We recommend to use a
signature algorithm for this purpose, in which case the receiver digital signature algorithm for this purpose, in which case
is REQUIRED to have an authentic copy of either the sender's the receiver is required to have an authentic copy of either
public key certificate or a root key certificate in case of a the sender's public key certificate or a root key certificate
PKI (public-key infrastructure). in case of a PKI (public-key infrastructure). Alternatively,
this initialization step can be done using any secure session
initiation protocol.
3. TESLA uses cryptographic MAC and PRF (pseudo-random 3. TESLA uses cryptographic MAC and PRF (pseudo-random functions).
functions). These MUST be cryptographically secure. Further These MUST be cryptographically secure. Further details on
details on the instantiation of the MAC and PRF are in Section the instantiation of the MAC and PRF are in Section 4.2.
4.2.
4. We would like to emphasize that the security of TESLA does NOT 4. We would like to emphasize that the security of TESLA does NOT
rely on any assumptions on network propagation delay. rely on any assumptions on network propagation delay.
3 The Basic TESLA Protocol 3 The Basic TESLA Protocol
TESLA is described in several academic publications: A book on TESLA is described in several academic publications: A book on
broadcast security [13], a journal paper [14], and two conference papers broadcast security [13], a journal paper [14], and two conference
papers [8,15]. Please refer to these publications for an in-depth
[8,15]. Please refer to these publications for an in-depth treatment. treatment.
3.1 Sketch of protocol 3.1 Protocol sketch
We first outline the main ideas behind TESLA. We first outline the main ideas behind TESLA.
As we argue in the introduction, broadcast authentication requires a As we argue in the introduction, broadcast authentication requires
source of asymmetry. TESLA uses time for asymmetry. We first make sure a source of asymmetry. TESLA uses time for asymmetry. We first make
that the sender and receivers are loosely time synchronized as described sure that the sender and receivers are loosely time synchronized as
above. Next, the sender forms a one-way chain of keys, where each key in described above. Next, the sender forms a one-way chain of keys,
chain is associated with a time interval (say, a second). Here is the where each key in chain is associated with a time interval (say, a
basic approach: second). Here is the basic approach:
¸ The sender attaches a MAC to each packet. The MAC is computed o The sender attaches a MAC to each packet. The MAC is computed
over the contents of the packet. For each packet, the sender uses over the contents of the packet. For each packet, the sender
the current key from the one-way chain as a cryptographic key uses the current key from the one-way chain as a cryptographic
to compute the MAC. key to compute the MAC.
¸ The sender discloses a key from the one-way chain after some o The sender discloses a key from the one-way chain after some
pre-defined time delay. (e.g., the key used in time interval i pre-defined time delay. (e.g., the key used in time interval i
is disclosed at time interval i+3.) is disclosed at time interval i+3.)
¸ Each receiver receives the packet. Each receiver knows the o Each receiver receives the packet. Each receiver knows the
schedule for disclosing keys and, since it has an upper bound on schedule for disclosing keys and, since it has an upper bound
the local time at the sender, it can check that the key used to on the local time at the sender, it can check that the key used
compute the MAC was not yet disclosed by the sender. If so, then to compute the MAC was not yet disclosed by the sender. If so,
the receiver buffers the packet. Otherwise the packet is dropped. then the receiver buffers the packet. Otherwise the packet is
(Note that we do not know for sure whether a "late packet" is a dropped due to inability to authenticate. Note that we do not
bogus one or simply a delayed packet. We drop the packet since we know for sure whether a "late packet" is a bogus one or simply
are unable to authenticate it.) a delayed packet. We drop the packet since we are unable to
authenticate it. (Ofcourse, an implementation may choose to
not drop packets and use them unauthenticated.)
¸ Each receiver checks that the disclosed key belongs to the hash-chain o Each receiver checks that the disclosed key belongs to the
(by checking against previously released keys in the chain) and then hash-chain (by checking against previously released keys in the
checks the correctness of the MAC. If the MAC is correct, the chain) and then checks the correctness of the MAC. If the MAC
receiver accepts the packet. is correct, the receiver accepts the packet.
Note that one-way chains have the property that if intermediate Note that one-way chains have the property that if intermediate
values of the one-way chain are lost, they can be recomputed using values of the one-way chain are lost, they can be recomputed using
subsequent values in the chain . So, even if some key disclosures subsequent values in the chain . So, even if some key disclosures
are lost, a receiver can recover the corresponding keys and check are lost, a receiver can recover the corresponding keys and check
the correctness of earlier packets. the correctness of earlier packets.
We now describe the stages of the basic TESLA protocol in this order: We now describe the stages of the basic TESLA protocol in this
sender setup, receiver bootstrap, sender transmission of order: sender setup, receiver bootstrap, sender transmission of
authenticated broadcast messages, and receiver authentication of authenticated broadcast messages, and receiver authentication of
broadcast messages. broadcast messages.
3.2 Sender Setup 3.2 Sender Setup
The sender divides the time into uniform intervals of duration T_int. The sender divides the time into uniform intervals of duration T_int.
The sender assigns one key from the one-way chain to each time The sender assigns one key from the one-way chain to each time
interval in sequence. interval in sequence.
The sender determines the length N of the one-way chain K_0, K_1, The sender determines the length N of the one-way chain K_0, K_1,
..., K_N, and this length limits the maximum transmission duration ..., K_N, and this length limits the maximum transmission duration
before a new one-way chain must be created. The sender picks a random before a new one-way chain must be created. The sender picks a
value for K_N. Using a pseudo-random function (PRF) f, the sender random value for K_N. Using a pseudo-random function (PRF) f, the
constructs the one-way function F: F(k) = f_k(0). The rest of the sender constructs the one-way function F: F(k) = f_k(0). The rest
chain is computed recursively using K_i = F(K_{i+1}). Note that this of the chain is computed recursively using K_i = F(K_{i+1}). Note
gives us K_i = F^{N-i}(K_N), so the receiver can compute any value in that this gives us K_i = F^{N-i}(K_N), so the receiver can compute
the key chain from K_N even if is does not have intermediate values. any value in the key chain from K_N even if is does not have
The key K_i will be used to authenticate packets sent in time intermediate values. The key K_i will be used to authenticate
interval i. packets sent in time interval i.
Jakobsson [21], and Coppersmith and Jakobsson [22] present a storage
and computation efficient mechanism for one-way chains. For a chain
of length N, storage is about log(N) elements, and the computation
overhead to reconstruct each element is also about log(N).
The sender determines the duration of a time interval, T_int, and the
key disclodure delay, d. (T_int is measured in time units, say
millieconds, and d is measured in number of time intervals. That is,
a key that is used for time interval i will be desclosed in time
interval i+d.) It is stressed that the scheme remains secure for any
values of T_int and d. Still, correct choice of T_int and d is
crucial for the usability of the scheme. The choice is influenced by
the estimated network delay, the length of the transmission, and the
tolerable delay at the receiver. T_int that is too short will cause
the keys to run out too soon. T_int that is too long will cause
excessive delay in authentication for some of the packets (those that
were sent at the beginning of a time period). Delay d that is too
short will cause to many packets to be unverifiable by the receiver.
Delay d that is too long will cause excessive delay in authentication.
If the sender estimates that the average network delay is m
milliseconds, and the sender expects to send a packet every n
milliseconds, then a reasonable value for T_int is max(n,m) and
a reasonable value for d is ceil(2m/T_int). If the application can
tolerate higher authentication delay then T_int can be made
appropriately larger.
Finally, the sender needs to allow each receiver to synchronize
its time with the sender. See more details on how this can be done in
section 3.3. (It is stressed that estimating the network delay is a
separate task than the time synchronization between the sender and
the receivers.)
3.3 Bootstrapping Receivers 3.3 Bootstrapping Receivers
Before a receiver can authenticate messages with TESLA, it needs to Before a receiver can authenticate messages with TESLA, it needs to
have: have:
* An upper bound D_t on the lag of its own clock with respect to
the clock of the sender. (That is, if the local time reading is t,
the current time reading at the sender is at most t+D_t.).
* The disclosure schedule of keys. (Note that this information is not
essential. See details below.)
* One authenticated key of the one-way key chain. (Typically, this
will be the last key in the chain, i.e. K_0, this key will be
signed by the sender, and all receivers will verify the signature against
the public key of the signer.
The sender sends the key disclosure schedule by transmitting the o An upper bound D_t on the lag of its own clock with respect to
following information to the receivers over an authenticated channel the clock of the sender. (That is, if the local time reading is
(either via a digitally signed broadcast message, or over an t, the current time reading at the sender is at most t+D_t.).
authenticated unicast channel with each receiver):
¸ Time interval schedule: interval duration T_int, start time of o One authenticated key of the one-way key chain. (Typically,
interval i and index of interval i, length of one-way key chain. this will be the last key in the chain, i.e. K_0, this key will
be signed by the sender, and all receivers will verify the
signature against the public key of the signer.
¸ Key disclosure delay d (number of intervals). o The disclosure schedule of keys:
¸ A commitment to the key chain K_i (i < j - d + 1, where j is - T_int, the interval duration.
the current interval index). - T_0, the start time of interval 1.
- N, the length of the one-way key chain.
- d, the key disclosure delay d (in number of intervals).
The receiver can perform the time synchronization and getting the The receiver can perform the time synchronization and getting the
authenticated TESLA parameters in a two-round message exchange, which authenticated TESLA parameters in a two-round message exchange,
we will describe in the technical TESLA document. Time synchronization as described below. We stress again that time synchronization can
can be performed as part of the registration protocol between member be performed as part of the registration protocol between the receiver
and sender. and sender, or between the receiver and a group controller.
3.3.1 Time Synchronization 3.3.1 Time Synchronization
Various approaches exist for time synchronization [16,17,18,19]. Various approaches exist for time synchronization [16,17,18,19].
TESLA, however, only requires the receiver to know an upper bound on TESLA only requires the receiver to know an upper bound on the
the delay of its local clock with respect to the receiver's clock, delay of its local clock with respect to the sender's clock, so a
so a simple algorithm is sufficient. TESLA can be used with direct, simple algorithm is sufficient. TESLA can be used with direct,
indirect, and delayed synchronization as three default options. indirect, and delayed synchronization as three default options.
The specific synchronization method will be part of each instantiation The specific synchronization method will be part of each
of TESLA, and needs to be described in the appropriate standards-track instantiation of TESLA.
RFC.
For completeness we sketch a simple method for direct synchronization For completeness, we sketch a simple method for direct
between the sender and a receiver: synchronization between the sender and a receiver:
o The receiver sends a (sync t_r) message to the sender and
records its local time t_r.
* The receiver sends a (sync t_r) message to the sender and records o Upon receipt of the (sync t_r) message, the sender records its
its local time t_r. local time t_s and sends (synch, t_r,t_s) to the receiver.
* Upon receipt of the (sync t_r) message, the sender records its
local time t_s and sends (synch, t_r,t_s) to the receiver. o Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s -
* Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s - t_r + S, t_r + S, where S is an estimated bound on the clock drift
where S is an estimated bound on the clock drift throughout the throughout the duration of the session.
duration of the session.
Note: Note:
o Assuming that the messages are authentic (i.e., the message
received the receiver was actually sent by the sender), and
assuming that the clock drift is at most S, then at any point
throughout the session we have that T_s < T_r + D_t, where T_s
is the current time at the sender and T_r is the current time
at the receiver.
* Assuming that the messages are authentic (i.e., the message received o The exchange of sync messages needs to be authenticated. This
the receiver was actually sent by the sender), and assuming that the can be done in a number of ways, for instance a secure NTP
clock drift is at most S, then at any point throughout the session protocol, or in conjunction with a session set-up protocol.
we have that T_s < T_r + D_t, where T_s is the current time at the
sender and T_r is the current time at the receiver.
* The exchange of sync messages needs to be authenticated. This can be For indirect time synchronization (eg, synchronization via a group
done in a number of ways, for instance a secure NTP protocol, or in controller), the sender and the controller engage in a protocol for
conjunction with a session set-up protocol. finding the value D^0_t between the sender and the controller. Next,
each receiver R interacts with the group controller (say, when
registering to the group) and finds the value D^R_t between the group
controller and R. The overall value of D_t within R is set to the sum
D_t = D^R_t + D^0_t.
3.4 Broadcasting Authenticated Messages 3.4 Broadcasting Authenticated Messages
Each key in the one-way key chain corresponds to a time interval. Each key in the one-way key chain corresponds to a time interval.
Every time a sender broadcasts a message, it appends a MAC to the Every time a sender broadcasts a message, it appends a MAC to the
message, using the key corresponding to the current time interval. message, using the key corresponding to the current time interval.
The key remains secret for the next d-1 intervals, so messages a The key remains secret for the next d-1 intervals, so messages a
sender broadcasts in interval j effectively disclose key K_j-d. We sender broadcasts in interval j effectively disclose key K_j-d. We
call d the key disclosure delay. call d the key disclosure delay.
We do not want to use the same key multiple times in different We do not want to use the same key multiple times in different
cryptographic operations, that is, to use key K_j to derive the previous cryptographic operations, that is, to use key K_j to derive the
key of the one-way key chain K_{j-1}, and to use the same key K_j as previous key of the one-way key chain K_{j-1}, and to use the same
the key to compute the MACs in time interval j may potentially lead key K_j as the key to compute the MACs in time interval j may
to a cryptographic weakness. Using a pseudo-random function (PRF) potentially lead to a cryptographic weakness. Using a pseudo-random
f', we construct the one-way function F': F'(k) = f'_k(1). We use F' function (PRF) f', we construct the one-way function F': F'(k) =
to derive the key to compute the MAC of messages in each interval. f'_k(1). We use F' to derive the key to compute the MAC of messages
The sender derives the MAC key as follows: K'_i = F'(K_i). Figure 1 in each interval. The sender derives the MAC key as follows: K'_i
depicts the one-way key chain construction and MAC key derivation. To = F'(K_i). Figure 1 depicts the one-way key chain construction and
broadcast message M_j in interval i the sender constructs packet MAC key derivation. To broadcast message M_j in interval i the
P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}}, where || denotes sender constructs the packet
concatenation.
P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}}
where || denotes concatenation.
F(K_i) F(K_{i+1}) F(K_{i+2}) F(K_i) F(K_{i+1}) F(K_{i+2})
K_{i-1} <------- K_i <--------- Ki+1 <------- Ki+2 K_{i-1} <------- K_i <--------- Ki+1 <------- Ki+2
| | | | | |
| F'(K_{i-1}) | F'(K_i) | F'(K_{i+1}) | F'(K_{i-1}) | F'(K_i) | F'(K_{i+1})
| | | | | |
V V V V V V
K'_{i-1} K'_i K'_{i+1} K'_{i-1} K'_i K'_{i+1}
skipping to change at page 9, line 33 skipping to change at page 9, line 33
and forge a MAC using the disclosed key. So whenever a packet and forge a MAC using the disclosed key. So whenever a packet
arrives, the receiver must verify that the MAC is based on a safe arrives, the receiver must verify that the MAC is based on a safe
key; a safe key is one that is still secret (only known by the key; a safe key is one that is still secret (only known by the
sender). We define a safe packet or safe message to be one with a MAC sender). We define a safe packet or safe message to be one with a MAC
that is computed with a safe key. that is computed with a safe key.
If the packet is not safe, the receiver must discard that packet, If the packet is not safe, the receiver must discard that packet,
because the authenticity is not assured any more. because the authenticity is not assured any more.
We now explain the TESLA authentication in more detail. When the We now explain the TESLA authentication in more detail. When the
receiver receives packet P_j sent in interval i, the receiver receiver receives packet P_j which carries an interval index i, the
computes an upper bound on the sender's clock: t_j. To test whether the receiver first records local time T in which the packet arrived. It
packet is safe, the receiver computes the highest interval x the then computes an upper bound t_j on the sender's clock at the time
where the packet arrived: t_j = T + D_t. To test whether the packet
is safe, the receiver then computes the highest interval x the
sender could possibly be in, namely x = floor((t_j - T_0) / T_int). sender could possibly be in, namely x = floor((t_j - T_0) / T_int).
The receiver verifies that x < i + d (where i is the interval index), The receiver verifies that x < i + d (where i is the interval index),
which implies that the sender is not yet in the interval during which which implies that the sender is not yet in the interval during which
it discloses the key K_i. If the condition fails then the receiver it discloses the key K_i. If the condition fails then the receiver
drops the packet. considers the packet unauthenticated.
The receiver cannot yet verify the authenticity of packets sent in The receiver cannot yet verify the authenticity of packets sent in
interval i without key K_i. Instead, it adds the triplet ( i, M_j, interval i without key K_i. Instead, it adds the triplet ( i, M_j,
MAC( K'_i, M_j) ) to a buffer, and verifies the authenticity after it MAC( K'_i, M_j) ) to a buffer, and verifies the authenticity after it
learns K'_i. learns K'_i.
What does a receiver do when it receives the disclosed key K_i? What does a receiver do when it receives the disclosed key K_i?
First, it checks whether it already knows K_i or a later key K_j First, it checks whether it already knows K_i or a later key K_j
(j>i). If K_i is the latest key received to date, the receiver checks with j>i. Then the receiver checks the legitimacy of K_i by verifying,
the legitimacy of K_i by verifying, for some earlier key K_v (v<i) for some earlier key K_v (v<i) that K_v = F^{i-v}(K_i). The receiver
that K_v = F^{i-v}(K_i). The receiver then computes K'_i = F'(K_i) then computes K'_i = F'(K_i) and verifies the authenticity of packets
and verifies the authenticity of packets of interval i. of interval i.
Using a disclosed key, we can calculate all previous disclosed keys, Using a disclosed key, we can calculate all previous disclosed keys,
so even if packets are lost, we will still be able to verify so even if packets are lost, we will still be able to verify
buffered, safe packets from earlier time intervals. Thus, if i-v>1, buffered, safe packets from earlier time intervals. Thus, if i-v>1,
the receiver can also verify the authenticity of the stored packets the receiver can also verify the authenticity of the stored packets
of intervals v+1 ... i-1. of intervals v+1 ... i-1.
Note that the security of TESLA does not rely on any assumptions on
network propagation delay.
3.6 Determining the Key Disclosure Delay 3.6 Determining the Key Disclosure Delay
An important TESLA parameter is the key disclosure delay d. Although An important TESLA parameter is the key disclosure delay d. Although
the choice of the disclosure delay does not affect the security of the choice of the disclosure delay does not affect the security of
the system, it is an important performance factor. A short disclosure the system, it is an important performance factor. A short disclosure
delay will cause packets to lose their safety property, so receivers delay will cause packets to lose their safety property, so receivers
will discard them; but a long disclosure delay leads to a long will discard them; but a long disclosure delay leads to a long
authentication delay for receivers. We recommend choosing the authentication delay for receivers. We recommend determining the
disclo¡ sure delay as follows: in direct time synchronization let disclosure delay as follows: in direct time synchronization let
the RTT be a reasonable upper bound on the round trip time between the the RTT be a reasonable upper bound on the round trip time between the
sender and the receiver; then choose d = ceil( RTT / T_int) + 1. Note sender and the receiver; then choose d = ceil( RTT / T_int) + 1. Note
that rounding up the quotient ensures that d >= 2. Also note that a that rounding up the quotient ensures that d >= 2. Also note that a
disclosure delay of one time interval (d=1) does not work. Consider disclosure delay of one time interval (d=1) does not work. Consider
packets sent close to the boundary of the time interval: after the packets sent close to the boundary of the time interval: after the
network propagation delay and the receiver time synchronization network propagation delay and the receiver time synchronization
error, a receiver will need to discard the packet, because the sender error, a receiver will need to discard the packet, because the sender
will already be in the next time interval, when it discloses the will already be in the next time interval, when it discloses the
corresponding key. corresponding key.
We stress that the security of TESLA does not rely on any assumptions on
network propagation delay: If the delay is longer than expected then
authentic packets may be considered unauthenticated. Still,
no unauthentic packet will be accepted as authentic.
3.7 An alternative delay description method 3.7 An alternative delay description method
The above description instructs the sender to include the time interval The above description instructs the sender to include the time interval
i in each packet. The receiver then uses i to determine the time at which i in each packet. The receiver then uses i to determine the time at which
the key authenticating the packet is disclosed. This method limits the the key authenticating the packet is disclosed. This method limits the
the sender to a pre-determined schedule of disclosing keys. the sender to a pre-determined schedule of disclosing keys.
Alternatively, the sender may directly include in each packet the time t_p Alternatively, the sender may directly include in each packet the time t_p
at which it is going to disclose the key for this packet. This way, the at which it is going to disclose the key for this packet. This way, the
receiver does not need to know the duration of intervals or the delay receiver does not need to know the duration of intervals or the delay
factor d. All the receiver needs to know is the bound D_t on the clock factor d. All the receiver needs to know is the bound D_t on the clock
skew and T_0, the sender's local time at the initiation of the session. skew and T_0, the sender's local time at the initiation of the session.
Then the receiver records the local time T when the packet has arrived, Then the receiver records the local time T when the packet has arrived,
and verifies that and verifies that
T <= T_0 + D_t + t_p. T <= T_0 + D_t + t_p.
Else the packet is dropped. Else the packet is considered aunauthenticated.
Another advantage of this method is that the sender is able to change Another advantage of this method is that the sender is able to
the duration of intervals and the key disclosure delay dynamically change the duration of intervals and the key disclosure delay
throughout the session. dynamically throughout the session. It is stressed, however, that the
interval index i must still be included in the packet, to allow the
receiver to know which key K_i should be used to verify the packet.
3.8 Some extensions 3.8 Some extensions
Let us mention two salient extensions of the basic TESLA scheme. Let us mention two salient extensions of the basic TESLA scheme. A
A first extension allows having multiple TESLA authentication chains first extension allows having multiple TESLA authentication chains
for a single stream, where each chain uses a different delay for for a single stream, where each chain uses a different delay for
disclosing the keys. This extension is typically used to deal with disclosing the keys. This extension is typically used to deal with
heterogeneous network delays within a single multicast transmission. heterogeneous network delays within a single multicast
A second extension allows having most of the buffering of packets transmission. A second extension allows having most of the
at the sender side (rather than at the receiver side). Both buffering of packets at the sender side (rather than at the
extensions are described in [15]. receiver side). Both extensions are described in [15].
The requirement in TESLA to receive a key in a later packet for
authentication prevents a receiver from authenticating the last
part of a message. Thus, to enable authentication of the last part
of a message or of the last message before a transmission
suspension, the sender needs to send an empty message with the key
to enable authentication.
4 Layer placement 4 Layer placement
The TESLA authentication can be performed at any layer in the The TESLA authentication can be performed at any layer in the
networking stack. Three natural places are in the network, transport, networking stack. Three natural places are in the network, transport,
or the application layer. We list some considerations regarding the or the application layer. We list some considerations regarding the
choice of layer: choice of layer:
¸ Performing TESLA in the network layer has the advantage that the o Performing TESLA in the network layer has the advantage that the
transport or application layer only receives authenticated data, transport or application layer only receives authenticated data,
potentially aiding a reliability protocol and preventing denial potentially aiding a reliability protocol and preventing denial
of service attacks. (Indeed, reliable multicast tools based on of service attacks. (Indeed, reliable multicast tools based on
forward error correction are highly susceptible to denial of forward error correction are highly susceptible to denial of
service due to bogus packets.) service due to bogus packets.)
¸ Performing TESLA in either the transport or the application layer o Performing TESLA in either the transport or the application layer
has the advantage that the network layer remains unchanged; but it has the advantage that the network layer remains unchanged; but it
has the drawback that packets are obtained by the application layer has the drawback that packets are obtained by the application layer
only after being processed by the transport layer. Consequently, only after being processed by the transport layer. Consequently,
if TCP is used then this may introduce additional and unpredictable if TCP is used then this may introduce additional and unpredictable
delays on top of the unavoidable network delays. (However, if UDP delays on top of the unavoidable network delays. (However, if UDP
is used then this is not a problem.) is used then this is not a problem.)
o It should be kept in mind that, since TESLA relies upon timing
of packets, deploying TESLA on top of a protocol or layer which
aggressively buffers packets and hides the true packet arrival
time (e.g., TCP) will significantly reduce the perormance of TESLA.
5. Security Considerations 5. Security Considerations
See the academic publications on TESLA [8,14,20] for several security See the academic publications on TESLA [8,14,20] for several
analyses. Regarding the security of implementations, by far the most security analyses. Regarding the security of implementations, by
delicate point is the verification of the timing conditions. Care far the most delicate point is the verification of the timing
should be taken to to make sure that: conditions. Care should be taken to to make sure that: (a) the
(a) The value bound D_t on the clock skew is calculated according to the value bound D_t on the clock skew is calculated according to the
spec at session set-up. spec at session set-up; (b) the receiver records the arrival time
(b) The receiver records the arrival time of the packet as soon as possible of the packet as soon as possible after the packet's arrival, and
after the packet's arrival, and computes the safety condition correctly. computes the safety condition correctly.
6 Acknowledgments It is important to note that, unless appropriate measures are taken,
TESLA increases the susceptibility of receivers to denial of service
(DoS) attacks. Specifically, an attacker can flood a victim receiver
with bogus packets that need to be buffered for delayed authentication.
There are several measures against such attacks. Here we mention
some of the known mechanisms to reduce this susceptibility:
o Limit the size of buffers at the receiver side.
o Add an external MAC that is computed using either (a) a key that
is constant for the session and known to all receivers, or (b)
the key that is disclosed in the current packet. Both mechanisms
prevent simple flooding attacks but are still susceptible to
more sophisticated attacks that have some "inside" information
on the session.
o Move the buffering of packets to the sender side, and allow
receivers to authenticate packets immediately upon receipt.
This method is described in [14].
Finally, in common with all authentication schemes, if verification
is located separately from the ultimate destination application (e.g.
an IPSec tunnel end point), a trusted channel must be present between
verification and the application. For instance, the interface between
the verifier and the application might simply assume that packets
received by the application must have been verified by the verifier
(because otherwise they would have been dropped). The application is
then vulnerable to reception of packets that have managed to bypass
the verifier.
6 IP Statement
The authors are not aware of any patents that encumber the free
use of TESLA.
7 Acknowledgments
We would like to thank Mike Luby for his feedback and support. We would like to thank Mike Luby for his feedback and support.
7 Bibliography 8 References
All references are informative.
[1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet [1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet
Request for Comments RFC 2246, January 1999. Proposed standard. Request for Comments RFC 2246, January 1999. Proposed standard.
[2] Ipsec, "IP Security Protocol, IETF working group." [2] IPsec, "IP Security Protocol, IETF working group."
http://www.ietf.org/html.charters/ipsec-charter.html. http://www.ietf.org/html.charters/ipsec-charter.html.
[3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast [3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast
message authentication," in Advances in Cryptology -- EUROCRYPT '2001 message authentication," in Advances in Cryptology -- EUROCRYPT '2001
(B. Pfitzmann, ed.), vol. 2045 of Lecture Notes in Computer Science , (B. Pfitzmann, ed.), vol. 2045 of Lecture Notes in Computer Science ,
(Innsbruck, Austria), pp. 434--450, Springer-Verlag, Berlin Germany, (Innsbruck, Austria), pp. 434--450, Springer-Verlag, Berlin Germany,
2001. 2001.
[4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech. [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech.
rep., IBM T.J.Watson Research Center, 1997. rep., IBM T.J.Watson Research Center, 1997.
[5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul¡ [5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul-
ticast packet authentication," in 6th ACM Conference on Computer and ticast packet authentication," in 6th ACM Conference on Computer and
Communications Security , November 1999. Communications Security , November 1999.
[6] P. Rohatgi, "A hybrid signature scheme for multicast source [6] P. Rohatgi, "A hybrid signature scheme for multicast source
authentication," Internet Draft, Internet Engineering Task Force, authentication," Internet Draft, Internet Engineering Task Force,
June 1999. Work in progress. June 1999. Work in progress.
[7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul¡ [7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul-
ticasts," in Proc. IEEE ICNP `98 , 1998. ticasts," in Proc. IEEE ICNP `98 , 1998.
[8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient [8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient
authentication and signing of multicast streams over lossy channels," authentication and signing of multicast streams over lossy channels,"
in IEEE Symposium on Security and Privacy , May 2000. in IEEE Symposium on Security and Privacy , May 2000.
[9] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. [9] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B.
Pinkas, "Multicast security: A taxonomy and some efficient construc¡ Pinkas, "Multicast security: A taxonomy and some efficient construc-
tions," in Infocom '99 , 1999. tions," in Infocom '99 , 1999.
[10] S. Cheung, "An efficient message authentication scheme for link [10] S. Cheung, "An efficient message authentication scheme for link
state routing," in 13th Annual Computer Security Applications Confer¡ state routing," in 13th Annual Computer Security Applications Confer-
ence , 1997. ence , 1997.
[11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream [11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream
authentication," in Selected Areas in Cryptography 2000 , (Waterloo, authentication," in Selected Areas in Cryptography 2000 , (Waterloo,
Canada), August 2000. A talk describing this scheme was given at IBM Canada), August 2000. A talk describing this scheme was given at IBM
Watson in August 1998. Watson in August 1998.
[12] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single [12] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single
source authentication on the mbone," in ICME 2000 , Aug 2000. A talk source authentication on the mbone," in ICME 2000 , Aug 2000. A talk
containing this work was given at IBM Watson, August 1998. containing this work was given at IBM Watson, August 1998.
[13] A. Perrig and J. D. Tygar, Secure Broadcast Communication in [13] A. Perrig and J. D. Tygar, Secure Broadcast Communication in
Wired and Wireless Networks Kluwer Academic Publishers, Oct. 2002. Wired and Wireless Networks Kluwer Academic Publishers, Oct. 2002.
ISBN 0792376501. ISBN 0792376501.
[14] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla [14] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla
broadcast authentication protocol," RSA CryptoBytes , vol. 5, no. broadcast authentication protocol," RSA CryptoBytes , vol. 5, no.
Summer, 2002. Summer, 2002.
[15] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and [15] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and
secure source authentication for multicast," in Network and Dis¡ secure source authentication for multicast," in Network and Dis-
tributed System Security Symposium, NDSS '01 , pp. 35--46, February tributed System Security Symposium, NDSS '01 , pp. 35--46, February
2001. 2001.
[16] D. L. Mills, "Network Time Protocol (Version 3) Specification, [16] D. L. Mills, "Network Time Protocol (Version 3) Specification,
Implementation and Analysis." Internet Request for Comments, March Implementation and Analysis." Internet Request for Comments, March
1992. RFC 1305. 1992. RFC 1305.
[17] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of [17] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of
clock synchronization," in Fault-Tolerant Distributed Computing (B. clock synchronization," in Fault-Tolerant Distributed Computing (B.
Simons and A. Spector, eds.), no. 448 in LNCS, pp. 84--96, Springer- Simons and A. Spector, eds.), no. 448 in LNCS, pp. 84--96, Springer-
Verlag, Berlin Germany, 1990. Verlag, Berlin Germany, 1990.
[18] D. Mills, "Improved algorithms for synchronizing computer net¡ [18] D. Mills, "Improved algorithms for synchronizing computer net-
work clocks," in Proceedings of the conference on Communications work clocks," in Proceedings of the conference on Communications
architectures, protocols and applications, SIGCOMM 94 , (London, architectures, protocols and applications, SIGCOMM 94 , (London,
England), pp. 317--327, 1994. England), pp. 317--327, 1994.
[19] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the [19] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the
presence of faults," J. ACM , vol. 32, no. 1, pp. 52--78, 1985. presence of faults," J. ACM , vol. 32, no. 1, pp. 52--78, 1985.
[20] Philippa Broadfoot and Gavin Lowe, "Analysing a Stream [20] Philippa Broadfoot and Gavin Lowe, "Analysing a Stream
Authentication Protocol using Model Checking. In Proceedings of the Authentication Protocol using Model Checking. In Proceedings of the
7th European Symposium on Research in Computer Security (ESORICS), 7th European Symposium on Research in Computer Security (ESORICS),
2002. 2002.
[21] M. Jakobsson, "Fractal hash sequence representation and traver¡
sal." Cryptology ePrint Archive, http://eprint.iacr.org/2002/001/,
Jan. 2002.
[22] D. Coppersmith and M. Jakobsson, "Almost optimal hash sequence
traversal," in Proceedings of the Sixth International Financial Cryp¡
tography Conference (FC '02) , March 2002.
A Author Contact Information A Author Contact Information
Adrian Perrig Adrian Perrig
ECE Department ECE Department
Carnegie Mellon University Carnegie Mellon University
Pittsburgh, PA Pittsburgh, PA 15218
US US
perrig@ece.cmu.edu perrig@cmu.edu
Ran Canetti Ran Canetti
IBM Research IBM Research
30 Saw Mill River Rd 30 Saw Mill River Rd
Hawthorne, NY 10532 Hawthorne, NY 10532
US US
canetti@watson.ibm.com canetti@watson.ibm.com
Dawn Song Dawn Song
CS Department ECE Department
Carnegie Mellon University Carnegie Mellon University
Pittsburgh, PA Pittsburgh, PA 15218
US US
dawnsong@cmu.edu dawnsong@cmu.edu
Doug Tygar Doug Tygar
UC Berkeley UC Berkeley
102 South Hall, 4600 102 South Hall, 4600
Berkeley, CA 94720-4600 Berkeley, CA 94720-4600
US US
tygar@cs.berkeley.edu tygar@cs.berkeley.edu
Bob Briscoe Bob Briscoe
BT Research BT Research
B54/74, BT Labs B54/77, BT Labs
Martlesham Heath Martlesham Heath
Ipswich, IP5 3RE Ipswich, IP5 3RE
UK UK
bob.briscoe@bt.com bob.briscoe@bt.com
B Full Copyright Statement B Full Copyright Statement
Copyright (C) The Internet Society (2000). All Rights Reserved. Copyright (C) The Internet Society (2000). All Rights Reserved.
This document and translations of it may be copied and furnished to This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this doc¡ included on all such copies and derivative works. However, this doc-
ument itself may not be modified in any way, such as by removing the ument itself may not be modified in any way, such as by removing the
copyright notice or references to the Internet Society or other copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of develop¡ Internet organizations, except as needed for the purpose of develop-
ing Internet standards in which case the procedures for copyrights ing Internet standards in which case the procedures for copyrights
defined in the Internet languages other than English. defined in the Internet languages other than English.
The limited permissions granted above are perpetual and will not be The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns. revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER¡ HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER-
CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
 End of changes. 92 change blocks. 
255 lines changed or deleted 366 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/