< draft-ietf-msec-tesla-intro-03.txt   draft-ietf-msec-tesla-intro-04.txt >
Internet Engineering Task Force IETF MSEC Internet Engineering Task Force Perrig, Canetti, Song, Tygar, Briscoe
Internet Draft Perrig, Canetti, Song, Tygar, Briscoe MSEC Working Group CMU / IBM / CMU / UC Berkeley / BT
draft-ietf-msec-tesla-intro-03.txt CMU / IBM / CMU / UC Berkeley / BT INTERNET-DRAFT
August 2004 Expires: June 2005 December 2004
Expires: 1 February 2005
TESLA: Multicast Source Authentication Transform Introduction TESLA: Multicast Source Authentication Transform Introduction
<draft-ietf-msec-tesla-intro-04.txt>
STATUS OF THIS MEMO STATUS OF THIS MEMO
This document is an Internet-Draft and is in full conformance with By submitting this Internet-Draft, I certify that any applicable
all provisions of Section 10 of RFC2026. patent or other IPR claims of which I am aware have been disclosed,
or will be disclosed, and any of which I become aware will be
disclosed, in accordance with RFC 3668.
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
other groups may also distribute working documents as Internet 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
or to cite them other than as "work in progress". material or to cite them other than as "work in progress."
To view the list Internet-Draft Shadow Directories, see The list of current Internet-Drafts can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/1id-abstracts.html
Abstract The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Data authentication is an important component for many broadcast Abstract
applications, for example audio and video Internet broadcasts, or
data distribution by satellite. This document introduces TESLA,
short for Timed Efficient Stream Loss-tolerant Authentication, a
secure source authentication mechanism for multicast or broadcast
data streams. This document provides an algorithmic description of
TESLA for informational purposes, and in particular, is intended to
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 This document introduces TESLA, short for Timed Efficient Stream
multicast were the seemingly conflicting requirements: loss Loss-tolerant Authentication. TESLA allows all receivers to check the
tolerance, efficiency, and no per-receiver state at the sender. The integrity and authenticate the source of each packet in multicast or
problem is particularly hard in settings with high packet loss broadcast data streams. TESLA requires no trust between receivers;
rates and where lost packets are not retransmitted, and where the uses low cost operations per packet at both sender and receiver; can
receivers want to authenticate each packet they do receive. tolerate any level of loss without retransmissions; and requires no
per-receiver state at the sender. TESLA can protect receivers against
denial of service attacks in certain circumstances. Each receiver
must be loosely time synchronized with the source in order to verify
messages, but otherwise receivers need send no messages. TESLA alone
cannot support non-repudiation of the data source to third parties.
TESLA provides authentication of individual data packets, This informational document is intended to assist in writing
regardless of loss rate. In addition, TESLA features low overhead standardizable and secure specifications for protocols based on TESLA
for both sender and receiver, and does not require per-receiver in different contexts.
state at the sender. TESLA is secure as long as the sender and
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 . . . . . . . . . . . 5
2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5
3 The Basic TESLA Protocol . . . . . . . . . . . . . . . . 5 3. The Basic TESLA Protocol . . . . . . . . . . . . . . . . 6
3.1 Protocol sketch . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . 8
3.3.1 Time Synchronization. . . . . . . . . . . . . . . . . . . 8 3.3.1. Time Synchronization. . . . . . . . . . . . . . . . . . . 9
3.4 Broadcasting Authenticated Messages . . . . . . . . . . . 8 3.4. Broadcasting Authenticated Messages . . . . . . . . . . . 9
3.5 Authentication at Receiver . . . . . . . . . . . . . . . 8 3.5. Authentication at Receiver . . . . . . . . . . . . . . . 10
3.6 Determining the Key Disclosure Delay . . . . . . . . . . 9 3.6. Determining the Key Disclosure Delay . . . . . . . . . . 12
3.7 An alternative delay description method . . . . . . . . . 10 3.7. An alternative delay description method . . . . . . . . . 12
3.8 Some extensions . . . . . . . . . . . . . . . . . . . . . 11 3.8. Denial of service protection. . . . . . . . . . . . . . . 13
4 Layer placement . . . . . . . . . . . . . . . . . . . . . 11 3.8.1. Additional group authentication . . . . . . . . . . . . . 14
5 Security considerations . . . . . . . . . . . . . . . . . 11 3.8.2. Not re-using keys . . . . . . . . . . . . . . . . . . . . 15
6 IP statement . . . . . . . . . . . . . . . . . . . . . . .12 3.8.3. Sender buffering. . . . . . . . . . . . . . . . . . . . . 17
7 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 12 3.9. Some extensions . . . . . . . . . . . . . . . . . . . . . 17
8 References . . . . . . . . . . . . . . . . . . . . . . . 12 4. Layer placement . . . . . . . . . . . . . . . . . . . . . 17
A Author Contact Information . . . . . . . . . . . . . . . 13 5. IANA considerations . . . . . . . . . . . . . . . . . . . 18
B Full Copyright Statement . . . . . . . . . . . . . . . . 14 6. Security considerations . . . . . . . . . . . . . . . . . 18
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . 18
8. References . . . . . . . . . . . . . . . . . . . . . . . 18
A. Author Contact Information . . . . . . . . . . . . . . . 21
B. Full Copyright Statement, IPR Notice and Disclaimer . . . 22
1 Introduction 1. Introduction
In multicast, a single packet can reach millions of receivers. This In multicast, a single packet can reach millions of receivers. This
unfortunately also introduces the danger that an attacker can unfortunately also introduces the danger that an attacker can
potentially also reach millions of receivers with a malicious potentially also reach millions of receivers with a malicious packet.
packet. Through source authentication, receivers can ensure that a Through source authentication, receivers can ensure that a received
received multicast packet originates from the correct source. multicast packet originates from the correct source. In these
respects, a multicast is equivalent to a broadcast to a superset of
the multicast receivers.
In unicast communication, we can achieve data authentication In unicast communication, we can achieve data authentication through
through a simple mechanism: the sender and the receiver share a a simple mechanism: the sender and the receiver share a secret key to
secret key to compute a message authentication code (MAC) of all compute a message authentication code (MAC) of all communicated data.
communicated data. When a message with a correct MAC arrives, the When a message with a correct MAC arrives, the receiver is assured
receiver is assured that the sender generated that message. that the sender generated that message. Standard mechanisms achieve
Standard mechanisms achieve unicast authentication this way, for unicast authentication this way, for example TLS or IPsec [1,2].
example TLS or IPsec [1,2].
The symmetric MAC authentication is not secure in a broadcast Symmetric MAC authentication is not secure in a broadcast setting.
setting. Consider a sender that broadcasts authentic data to mutually Consider a sender that broadcasts authentic data to mutually
untrusting receivers. The symmetric MAC is not secure: every receiver mistrusting receivers. The symmetric MAC is not secure: every
knows the MAC key, and hence could impersonate the sender and forge receiver knows the MAC key, and hence could impersonate the sender
messages to other receivers. Intuitively, we need an asymmetric and forge messages to other receivers. Intuitively, we need an
mechanism to achieve authenticated broadcast, such that every receiver asymmetric mechanism to achieve authenticated broadcast, such that
can verify the authenticity of messages it receives, without being every receiver can verify the authenticity of messages it receives,
able to generate authentic messages. Achieving this in an efficient without being able to generate authentic messages. Achieving this in
way is a challenging problem [3]. an efficient way is a challenging problem [3].
The standard approach to achieve such asymmetry for authentication The standard approach to achieve such asymmetry for authentication is
is to use asymmetric cryptography, e.g., a digital signature. to use asymmetric cryptography, e.g., a digital signature. Digital
Digital signatures have the required asymmetric property: the signatures have the required asymmetric property: the sender
sender generates the signature with its private key, and all generates the signature with its private key, and all receivers can
receivers can verify the signature with the sender's public key, verify the signature with the sender's public key, but a receiver
but a receiver with the public key alone cannot generate a digital with the public key alone cannot generate a digital signature for a
signature for a new message. A digital signature provides new message. A digital signature provides non-repudiation, a stronger
non-repudiation, a stronger property than authentication. However, property than authentication. However, digital signatures have a high
digital signatures have a high cost: they have a high computation cost: they have a high computation overhead for both the sender and
overhead for both the sender and the receiver, and most signatures the receiver, and most signatures also have a high bandwidth
also have a high bandwidth overhead. Since we assume broadcast overhead. Since we assume broadcast settings where the sender does
settings where the sender does not retransmit lost packets, and the not retransmit lost packets, and the receiver still wants to
receiver still wants to immediately authenticate each packet it immediately authenticate each packet it receives, we would need to
receives, we would need to attach a digital signature to each attach a digital signature to each message. Because of the high
message. Because of the high overhead of asymmetric cryptography, overhead of asymmetric cryptography, this approach would restrict us
this approach would restrict us to low-rate streams, and to senders to low-rate streams, and to senders and receivers with powerful
and receivers with powerful workstations. We can try to amortize one workstations. We can try to amortize one digital signature over
digital signature over multiple messages. However, such an multiple messages. However, such an approach is still expensive in
approach is still expensive in contrast to symmetric cryptography, contrast to symmetric cryptography, since symmetric cryptography is
since symmetric cryptography is in general 3 to 5 orders of in general 3 to 5 orders of magnitude more efficient than asymmetric
magnitude more efficient than asymmetric cryptography. In addition, cryptography. In addition, the straight-forward amortization of one
the straight-forward amortization of one digital signature over digital signature over multiple packets requires reliability, as the
multiple packets requires reliability, as the receiver needs to receiver needs to receive all packets to verify the signature. A
receive all packets to verify the signature. A number of schemes number of schemes that follow this approach are [4,5,6,7,8]. See [9]
that follow this approach are [4,5,6,7,8]. See [9] for more for more details.
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 3.3.1. Other schemes that follow a similar
to TESLA are [10,11,12]. approach 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 underscore between the variable name and the index, e.g., the key K
with index i is K_i, the key K with index i+d is K_{i+d}. To write with index i is K_i, the key K with index i+d is K_{i+d}. To write a
a superscript we use the caret, e.g., function F with the argument superscript we use the caret, e.g., function F with the argument x
x executed i times is F^i(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 and integrity
to providing both efficiency and security is a delayed disclosure of checking. The key idea to providing both efficiency and security is a
keys. The delayed key disclosure results in an authentication delay. delayed disclosure of keys. The delayed key disclosure results in an
In practice, the delay is on the order of one RTT (round-trip-time). authentication delay. In practice, the delay is on the order of one
RTT (round-trip-time).
TESLA has the following properties: TESLA has the following properties:
o Low computation overhead for generation and verification of o Low computation overhead for generation and verification of
authentication information authentication information
o Low communication overhead o Low communication overhead
o 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
o Strong robustness to packet loss o Strong robustness to packet loss
o Scales to a large number of receivers o Scales to a large number of receivers
o Security is guaranteed as long as the sender and recipients are o Protects receivers against denial of service attacks in certain
loosely time synchronized, where synchronization can take place circumstances if configured appropriately
at session set-up.
o Each receiver cannot verify message authenticity unless it is
loosely time synchronized with the source, where synchronization
can take place at session set-up. Once the session is in
progress, receivers need not send any messages or
acknowledgements.
o Non-repudiation is not supported - each receiver can know that a
stream is from an authentic source, but not prove this to others
later.
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. Delayed authentication, however,
however, requires buffering of packets until authentication is requires buffering of packets until authentication is completed.
completed. Certain applications intolerant of delay may be willing to Certain applications intolerant of delay may be willing to process
process packets in parallel to being buffered awaiting authentication, packets in parallel to being buffered awaiting authentication, as
as long as roll-back is possible if packets are later found to be long as roll-back is possible if packets are later found to be
unauthenticated. For instance, an interactive video may play-out unauthenticated. For instance, an interactive video may play-out
packets still awaiting authentication, but if they are later found to packets still awaiting authentication, but if they are later found to
be unauthenticated, it could stop further play-out and warn the viewer be unauthenticated, it could stop further play-out and warn the
that the last x msec were unauthenticated and should be ignored. viewer that the last x msec were unauthenticated and should be
However, in the remainder of this document, for brevity, we will ignored. However, in the remainder of this document, for brevity, we
assume packets are not processed in parallel to buffering. 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:
o 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, re-send, delay, and alter packets.
o Access to a fast network with negligible delay. o Access to a fast network with negligible delay.
o 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 pseudo-random 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 expects 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
potential denial-of-service (DOS) attack due to a flood of bogus denial-of-service (DOS) attack due to a flood of bogus packets (see
packets. section 3.8).
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 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). We note that (That is, D_t = sender time - receiver time). We note that an
an upper bound on D_t can be easily obtained via a simple upper bound on D_t can be easily obtained via a simple
two-message exchange. (Such an exchange can be piggybacked on two-message exchange. (Such an exchange can be piggybacked on
any secure session initiation protocol. Alternatively, standard any secure session initiation protocol. Alternatively, standard
protocols such as as NTP [16] can be used. protocols such as NTP [16] can be used.
2. TESLA MUST be bootstrapped at session set-up through a 2. TESLA MUST be bootstrapped at session set-up through a
regular data authentication system. We recommend to use a regular data authentication system. One option is to use a
digital signature algorithm for this purpose, in which case digital signature algorithm for this purpose, in which case
the receiver is required to have an authentic copy of either the receiver is required to have an authentic copy of either
the sender's public key certificate or a root key certificate the sender's public key certificate or a root key certificate
in case of a PKI (public-key infrastructure). Alternatively, in case of a PKI (public-key infrastructure). Alternatively,
this initialization step can be done using any secure session this initialization step can be done using any secure session
initiation protocol. initiation protocol.
3. TESLA uses cryptographic MAC and PRF (pseudo-random functions). 3. TESLA uses cryptographic MAC and PRF (pseudo-random functions).
These MUST be cryptographically secure. Further details on These MUST be cryptographically secure. Further details on the
the instantiation of the MAC and PRF are in Section 4.2. instantiation of the MAC and PRF are in Section 3.4.
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 broadcast security [13], a journal paper [14], and two conference
papers [8,15]. Please refer to these publications for an in-depth papers [8,15]. Please refer to these publications for in-depth proofs
treatment. of security, experimental results, etc.
3.1 Protocol sketch
We first outline the main ideas behind TESLA. We first outline the main ideas behind TESLA.
3.1. Protocol sketch
As we argue in the introduction, broadcast authentication requires As we argue in the introduction, broadcast authentication requires
a source of asymmetry. TESLA uses time for asymmetry. We first make a source of asymmetry. TESLA uses time for asymmetry. We first make
sure that the sender and receivers are loosely time synchronized as sure that the sender and receivers are loosely time synchronized as
described above. Next, the sender forms a one-way chain of keys, described above. Next, the sender forms a one-way chain of keys,
where each key in chain is associated with a time interval (say, a where each key in chain is associated with a time interval (say, a
second). Here is the basic approach: second). Here is the basic approach:
o 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 over the contents of the packet. For each packet, the sender
uses the current key from the one-way chain as a cryptographic uses the current key from the one-way chain as a cryptographic
skipping to change at page 6, line 33 skipping to change at page 6, line 47
is disclosed at time interval i+3.) is disclosed at time interval i+3.)
o 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 schedule for disclosing keys and, since it has an upper bound
on the local time at the sender, it can check that the key used on the local time at the sender, it can check that the key used
to compute the MAC was not yet disclosed by the sender. If so, to compute the MAC was not yet disclosed by the sender. If so,
then the receiver buffers the packet. Otherwise the packet is then the receiver buffers the packet. Otherwise the packet is
dropped due to inability to authenticate. Note that we do not dropped due to inability to authenticate. Note that we do not
know for sure whether a "late packet" is a bogus one or simply know for sure whether a "late packet" is a bogus one or simply
a delayed packet. We drop the packet since we are unable to a delayed packet. We drop the packet since we are unable to
authenticate it. (Ofcourse, an implementation may choose to authenticate it. (Of course, an implementation may choose to
not drop packets and use them unauthenticated.) not drop packets and use them unauthenticated.)
o Each receiver checks that the disclosed key belongs to the o Each receiver checks that the disclosed key belongs to the
hash-chain (by checking against previously released keys in the hash-chain (by checking against previously released keys in the
chain) and then checks the correctness of the MAC. If the MAC chain) and then checks the correctness of the MAC. If the MAC
is correct, the 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
are lost, a receiver can recover the corresponding keys and check lost, a receiver can recover the corresponding keys and check the
the correctness of earlier packets. correctness of earlier packets.
We now describe the stages of the basic TESLA protocol in this We now describe the stages of the basic TESLA protocol in this
order: 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 before a new one-way chain must be created. The sender picks a random
random value for K_N. Using a pseudo-random function (PRF) f, the value for K_N. Using a pseudo-random function (PRF) f, the sender
sender constructs the one-way function F: F(k) = f_k(0). The rest constructs the one-way function F: F(k) = f_k(0). The rest of the
of the chain is computed recursively using K_i = F(K_{i+1}). Note chain is computed recursively using K_i = F(K_{i+1}). Note that this
that this gives us K_i = F^{N-i}(K_N), so the receiver can compute gives us K_i = F^{N-i}(K_N), so the receiver can compute any value in
any value in the key chain from K_N even if is does not have the key chain from K_N even if is does not have intermediate values.
intermediate values. The key K_i will be used to authenticate The key K_i will be used to authenticate packets sent in time
packets sent in time interval i. interval i.
Jakobsson [21], and Coppersmith and Jakobsson [22] present a storage Jakobsson [21], and Coppersmith and Jakobsson [22] present a storage
and computation efficient mechanism for one-way chains. For a chain and computation efficient mechanism for one-way chains. For a chain
of length N, storage is about log(N) elements, and the computation of length N, storage is about log(N) elements, and the computation
overhead to reconstruct each element is also about log(N). overhead to reconstruct each element is also about log(N).
The sender determines the duration of a time interval, T_int, and the 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 key disclosure delay, d. (T_int is measured in time units, say
millieconds, and d is measured in number of time intervals. That is, milliseconds, 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 a key that is used for time interval i will be disclosed in time
interval i+d.) It is stressed that the scheme remains secure for any 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 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 crucial for the usability of the scheme. The choice is influenced by
the estimated network delay, the length of the transmission, and the the estimated network delay, the length of the transmission, and the
tolerable delay at the receiver. T_int that is too short will cause 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 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 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 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. short will cause too many packets to be unverifiable by the receiver.
Delay d that is too long will cause excessive delay in authentication. Delay d that is too long will cause excessive delay in
authentication.
If the sender estimates that the average network delay is m The sender estimates a reasonable upper bound on the network delay
milliseconds, and the sender expects to send a packet every n between the sender and any receiver as m milliseconds. This includes
milliseconds, then a reasonable value for T_int is max(n,m) and any delay expected in the stack (see section 4 on layer placement).
a reasonable value for d is ceil(2m/T_int). If the application can If the sender expects to send a packet every n milliseconds, then a
tolerate higher authentication delay then T_int can be made reasonable value for T_int is max(n,m). Based on T_int, a rule of
appropriately larger. thumb for determining the key disclosure delay, d, is given in
section 3.6.
Finally, the sender needs to allow each receiver to synchronize The above value for T_int is neither an upper or lower bound, merely
its time with the sender. See more details on how this can be done in the value that reduces key change processing to a minimum without
section 3.3. (It is stressed that estimating the network delay is a causing authentication delay to be higher than necessary. So if the
application can tolerate higher authentication delay then T_int can
be made appropriately larger. Also, if m (or n) increases during the
session, perhaps due to congestion or a late joiner on a high delay
path, T_int need not be revised.
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.1. (It is stressed that estimating the network delay is a
separate task than the time synchronization between the sender and separate task than the time synchronization between the sender and
the receivers.) 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:
o An upper bound D_t on the lag of its own clock with respect to o 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 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.). t, the current time reading at the sender is at most t+D_t.).
o One authenticated key of the one-way key chain. (Typically, o One authenticated key of the one-way key chain. (Typically, this
this will be the last key in the chain, i.e. K_0, this key will will be the last key in the chain, i.e. K_0, this key will be
be signed by the sender, and all receivers will verify the signed by the sender, and all receivers will verify the signature
signature against the public key of the signer. against the public key of the signer.
o The disclosure schedule of keys: o The disclosure schedule of keys:
- T_int, the interval duration. - T_int, the interval duration.
- T_0, the start time of interval 1. - T_0, the start time of interval 1.
- N, the length of the one-way key chain. - N, the length of the one-way key chain.
- d, the key disclosure delay d (in number of intervals). - 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, authenticated TESLA parameters in a two-round message exchange, as
as described below. We stress again that time synchronization can described below. We stress again that time synchronization can be
be performed as part of the registration protocol between the receiver performed as part of the registration protocol between any receiver
and sender, or between the receiver and a group controller. (including late joiners) and the sender, or between any 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 only requires the receiver to know an upper bound on the TESLA only requires the receiver to know an upper bound on the delay
delay of its local clock with respect to the sender's clock, so a of its local clock with respect to the sender's clock, so a simple
simple algorithm is sufficient. TESLA can be used with direct, algorithm is sufficient. TESLA can be used with direct, indirect, and
indirect, and delayed synchronization as three default options. delayed synchronization as three default options. The specific
The specific synchronization method will be part of each synchronization method will be part of each instantiation of TESLA.
instantiation of TESLA.
For completeness, we sketch a simple method for direct For completeness, we sketch a simple method for direct
synchronization 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. o The receiver sends a (sync t_r) message to the sender and records
its local time t_r at the moment of sending.
o Upon receipt of the (sync t_r) message, the sender records its o 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. 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 - o Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s -
t_r + S, where S is an estimated bound on the clock drift t_r + S, where S is an estimated bound on the clock drift
throughout the duration of the session. throughout the duration of the session.
Note: Note:
o Assuming that the messages are authentic (i.e., the message o Assuming that the messages are authentic (i.e., the message
received the receiver was actually sent by the sender), and received by the receiver was actually sent by the sender), and
assuming that the clock drift is at most S, then at any point 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 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 is the current time at the sender and T_r is the current time at
at the receiver. the receiver.
o The exchange of sync messages needs to be authenticated. This o The exchange of sync messages needs to be authenticated. This can
can be done in a number of ways, for instance a secure NTP be done in a number of ways, for instance a secure NTP protocol,
protocol, or in conjunction with a session set-up protocol. or in conjunction with a session set-up protocol.
For indirect time synchronization (eg, synchronization via a group For indirect time synchronization (eg, synchronization via a group
controller), the sender and the controller engage in a protocol for controller), the sender and the controller engage in a protocol for
finding the value D^0_t between the sender and the controller. Next, finding the value D^0_t between the sender and the controller. Next,
each receiver R interacts with the group controller (say, when each receiver R interacts with the group controller (say, when
registering to the group) and finds the value D^R_t between the group 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 controller and R. The overall value of D_t within R is set to the sum
D_t = D^R_t + D^0_t. 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 cryptographic operations, that is, to use key K_j to derive the
previous key of the one-way key chain K_{j-1}, and to use the same previous key of the one-way key chain K_{j-1}, and to use the same
key K_j as the key to compute the MACs in time interval j may key K_j as the key to compute the MACs in time interval j may
potentially lead to a cryptographic weakness. Using a pseudo-random potentially lead to a cryptographic weakness. Using a pseudo-random
function (PRF) f', we construct the one-way function F': F'(k) = function (PRF) f', we construct the one-way function F': F'(k) =
f'_k(1). We use F' to derive the key to compute the MAC of messages f'_k(1). We use F' to derive the key to compute the MAC of messages
in each interval. The sender derives the MAC key as follows: K'_i in each interval. The sender derives the MAC key as follows: K'_i =
= F'(K_i). Figure 1 depicts the one-way key chain construction and F'(K_i). Figure 1 depicts the one-way key chain construction and MAC
MAC key derivation. To broadcast message M_j in interval i the key derivation. To broadcast message M_j in interval i the sender
sender constructs the packet constructs the packet
P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}} P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}}
where || denotes concatenation. 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 <------- K_{i+1} <------- K_{i+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}
Figure 1: At the top of the figure, we see the one-way key chain Figure 1: At the top of the figure, we see the one-way key chain
(derived using the one-way function F), and the derived MAC keys (derived using the one-way function F), and the derived MAC keys
(derived using the one-way function F'). (derived using the one-way function F').
3.5 Authentication at Receiver 3.5. Authentication at Receiver
Once a sender discloses a key, we must assume that all parties might Once a sender discloses a key, we must assume that all parties might
have access to that key. An adversary could create a bogus message have access to that key. An adversary could create a bogus message
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 a packet proves safe it will be buffered, only to be released when
because the authenticity is not assured any more. its own key, disclosed in a later packet, proves its authenticity.
Although a newly arriving packet cannot immediately be authenticated,
it may disclose a new key so that earlier, buffered packets can be
authenticated. Any newly disclosed key must be checked to determine
whether it is genuine, then authentication of buffered packets that
have been waiting for it can proceed.
We now explain the TESLA authentication in more detail. When the We now describe TESLA authentication at the receiver with more
receiver receives packet P_j which carries an interval index i, the precision, listing all of these steps in the exact order they should
receiver first records local time T in which the packet arrived. It be carried out:
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).
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
it discloses the key K_i. If the condition fails then the receiver
considers the packet unauthenticated.
The receiver cannot yet verify the authenticity of packets sent in 1. Safe packet test: When the receiver receives packet P_j which
interval i without key K_i. Instead, it adds the triplet ( i, M_j, carries an interval index i, and a disclosed key K_{i-d}, it
MAC( K'_i, M_j) ) to a buffer, and verifies the authenticity after it first records local time T at which the packet arrived. The
learns K'_i. receiver then computes an upper bound t_j on the sender's clock
at the time when 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). 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 it discloses the
key K_i.
What does a receiver do when it receives the disclosed key K_i? Even if the packet is safe, the receiver cannot yet verify the
First, it checks whether it already knows K_i or a later key K_j authenticity of this packet sent in interval i without key K_i
with j>i. Then the receiver checks the legitimacy of K_i by verifying, that will be disclosed later. Instead, it adds the triplet ( i,
for some earlier key K_v (v<i) that K_v = F^{i-v}(K_i). The receiver M_j, MAC( K'_i, M_j) ) to a buffer, and verifies the
then computes K'_i = F'(K_i) and verifies the authenticity of packets authenticity after it learns K'_i.
of interval i.
If the packet is unsafe, then the receiver considers the packet
unauthenticated. It should discard unsafe packets but, at its
own risk it may choose to use them unverified.
2. New key index test: Next the receiver checks whether a key K_v
has already been disclosed with the same or later index v than
the current disclosed key K_{i-d}, that is with v >= i-d.
3. Key verification test: If the disclosed key index is new, the
receiver checks the legitimacy of K_{i-d} by verifying, for
some earlier disclosed key K_v (v<i-d), that K_v =
F^{i-d-v}(K_{i-d}).
If key verification fails, the newly arrived packet P_j should
be discarded.
4. Message verification tests: If the disclosed key is legitimate,
the receiver then verifies the authenticity of any earlier
safe, buffered packets of interval i-d. To authenticate one of
the buffered packets P_h containing message M_h protected with
a MAC that used key index i-d, the receiver will compute
K'_{i-d} = F'(K_{i-d}) from which it can compute MAC( K'_{i-d},
M_h).
If this MAC equals the MAC stored in the buffer, the packet is
authenticated and can be released from the buffer. If the MACs
do not agree, the buffered packet P_h should be discarded.
The receiver continues to verify and release (or not) any
remaining buffered packets that depend on the newly disclosed
key K_{i-d}.
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-d-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-d-1.
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 not be able to authenticate them; but a long disclosure delay
leads to a long authentication delay for receivers. We recommend
authentication delay for receivers. We recommend determining the determining the disclosure delay as follows: in direct time
disclosure delay as follows: in direct time synchronization let synchronization let the RTT, 2m, be a reasonable upper bound on the
the RTT be a reasonable upper bound on the round trip time between the round trip time between the sender and any receiver including worst
sender and the receiver; then choose d = ceil( RTT / T_int) + 1. Note case congestion delay and worst case buffering delay in host stacks.
that rounding up the quotient ensures that d >= 2. Also note that a Then choose d = ceil( 2m / T_int) + 1. Note that rounding up the
disclosure delay of one time interval (d=1) does not work. Consider quotient ensures that d >= 2. Also note that a disclosure delay of
packets sent close to the boundary of the time interval: after the one time interval (d=1) does not work. Consider packets sent close to
network propagation delay and the receiver time synchronization the boundary of the time interval: after the network propagation
error, a receiver will need to discard the packet, because the sender delay and the receiver time synchronization error, a receiver will
will already be in the next time interval, when it discloses the not be able to authenticate the packet, because the sender 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 Measuring the delay to each receiver before determining m will still
network propagation delay: If the delay is longer than expected then not adequately predict the upper bound on delay to late joiners, or
authentic packets may be considered unauthenticated. Still, where congestion delay rises later in the session. It may be adequate
no unauthentic packet will be accepted as authentic. to use a hard-coded historic estimate of worst-case delay (e.g. round
trip delays to any host on the intra-planetary Internet rarely exceed
500msec if routing remains stable). If such authentication delay is
too pessimistic, the adaptive approach of section 3.7 may be an
alternative, at the expense of extra packet overhead.
3.7 An alternative delay description method 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
inauthentic packet will be accepted as authentic.
The above description instructs the sender to include the time interval 3.7. An alternative delay description method
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 above description instructs the sender to include the time
the sender to a pre-determined schedule of disclosing keys. interval 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 sender to a pre-determined schedule of
disclosing keys.
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 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 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, and verifies that
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
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
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,
and verifies that
T <= T_0 + D_t + t_p. T <= T_0 + D_t + t_p.
Else the packet is considered aunauthenticated. Else the packet is considered unauthenticated.
Another advantage of this method is that the sender is able to Another advantage of this method is that the sender is able to change
change the duration of intervals and the key disclosure delay the duration of intervals and the key disclosure delay dynamically
dynamically throughout the session. It is stressed, however, that the throughout the session. It is stressed, however, that the interval
interval index i must still be included in the packet, to allow the index i must still be included in the packet, to allow the receiver
receiver to know which key K_i should be used to verify the packet. to know which key K_i should be used to verify the packet.
3.8 Some extensions 3.8. Denial of service protection
Because TESLA authentication is delayed, receivers seem vulnerable to
flooding attacks that cause them to buffer excess packets, even
though they may eventually prove to be inauthentic. When TESLA is
deployed in an environment with a threat of flooding attacks, the
receiver can take a number of extra precautions.
First we list simple DoS mitigation precautions that can and should
be taken by any receiver independently of others, thus requiring no
changes to the protocol or sender behaviour. We precisely specify
where these extra steps interleave with the receiver authentication
steps already given in section 3.5.
áá o Session validity test: Before the safe packet test (step 1), check
that arriving packets have a valid source IP address and port
number for the session, that they do not replay a message already
received in the session and that they are not significantly larger
than the packet sizes expected in the session.
áá o Reasonable misordering test: Before the key verification test (step
3), check the disclosed key index i-d of the arriving packet is
within g of the previous highest disclosed key index v, thus for
example i-d-v <= g. g sets the threshold beyond which an out of
order key index is assumed to be malicious rather than just
misordered. Without this test an attacker could exploit the
iterated test in step 3 to make receivers consume inordinate CPU
time checking along the hash chain for what appear to be extremely
misordered packets.
Each receiver can independently adapt g to prevailing attack
conditions, for instance using the following algorithm. Initially,
g should be set to g_max (say 16). But whenever an arriving packet
fails the reasonable misordering test above or the key verification
test (step 3), g should be dropped to g_min (>0 and typically 1).
At each successful key verification (step 3), g should be
incremented by 1 unless it is already g_max. These precautions will
guarantee that sustained attack packets cannot cause the receiver
to execute more than an average of g_min hashes each, unless they
are paced against genuine packets. In the latter case attacks are
limited to g_max/(g_max-g_min) hashes per each genuine packet.
g_max and g_min should be chosen knowing that they limit the
average gap in a packet sequence to g.max(n,m)/n packets (see
section 3.2 for definitions of n & m). So with g=1, m=100msec RTT
and n=4msec inter-packet period, reordering would be limited to
gaps of 25 packet on average. Bigger naturally occurring gaps would
have to be written off as if they were losses.
Stronger DoS protection requires both senders and receivers to
arrange additional constraints on the protocol. Below we outline
three alternative extensions to basic TESLA; the first adding group
authentication, the second not re-using keys during a time interval
and the third moving buffering to the sender.
It is important to understand the applicability of each scheme, as
the first two schemes use slightly more (but bounded) resources in
order to prevent attackers from consuming unbounded resources. Adding
group authentication requires larger per packet overhead. Never
re-using a key requires both ends to process two hashes per packet
(rather than per time interval) and the sender must store or
re-generate a longer hash chain. The merits of each scheme,
summarised after describing each below, must be weighed against these
additional costs.
3.8.1. Additional group authentication
This scheme simply involves addition of a group MAC to every packet.
That is, a shared key K_g common to the whole group is communicated
as an additional step during receiver bootstrap (section 3.3). Then,
during broadcast of message M_j (section 3.4) the sender computes the
group MAC of each packet MAC(K_g, P_j), which it appends to the
packet header. Note that the group MAC covers the whole packet P_j,
that is the concatenation of the message M_j and the additional TESLA
authentication material, using the formula in section 3.4.
Immediately on packet arrival, each receiver can check that each
packet came from a group member, by recomputing and comparing the
group MAC.
It should be noted that TESLA source authentication is only necessary
when other group members cannot be trusted to refrain from spoofing
the source, otherwise simpler group authentication would be
sufficient. Therefore, additional group authentication will only make
sense in scenarios where other group members are trusted to refrain
from flooding the group, but they are still not trusted to refrain
from spoofing the source.
3.8.2. Not re-using keys
In TESLA as described so far, each MAC key was used repeatedly for
all the packets sent in a time interval. If instead the sender were
to guarantee never to use a MAC key more than once, each disclosed
key could assume an additional purpose on top of authenticating a
previously buffered packet. Each key would also immediately show each
receiver that the sender of each arriving packet knew the next key
back along the hash chain, which is now only ever disclosed once,
similar to S/KEY [23]. Therefore a reasonable receiver strategy would
be to discard any arriving packets that disclosed a key seen already.
The fill rate of the receiver's buffer would then be clocked by each
packet revealed by the genuine sender, preventing memory flooding
attacks.
An attacker with control of a network element or of a faster bypass
network could intercept messages and overtake or replace them with
different messages but the same keys. However, as long as packets are
only buffered if they also pass the delay safety test, such bogus
packets will fail TESLA verification after the disclosure delay.
Admittedly, receivers could be fooled into discarding genuine
messages that had been overtaken by bogus ones. But it is hard to
overtake messages without compromising a network element. And any
attacker that can compromise a network element can discard genuine
messages anyway. We will now describe this scheme in more detail.
For the sender the scheme is hardly different from TESLA. It merely
uses an interval duration short enough to ensure a new key back along
the hash chain for each packet. So the rule of thumb given in section
3.2 for an efficient re-keying interval T_int no longer applies.
Instead, T_int is simply n, the inter-arrival time between packets in
milliseconds. The rule of thumb for calculating d, the key disclosure
delay, remains unchanged from that given in section 3.6, or the
explicit disclosure delay method in section 3.7 can be used.
If the packet rate is likely to vary, for safety n should be taken as
the minimum inter-departure time between any two packets. (In fact, n
need not be so strict; it can be the minimum average packet
inter-departure time over any burst of d packets expected throughout
the session.)
Note that if the packet rate slows down, whenever no packets are sent
in a key change interval the key index must increment along the hash
chain once for each missed interval. (During a burst, if the less
strict definition of n above has been used, packets may need to
depart before their key change interval. The sender can safely
continue changing the key each packet, using keys from future key
intervals, because if n has been chosen as defined above, such bursts
will never sustain long enough to cause the associated key to be
disclosed less than the disclosure delay later.)
To be absolutely clear, the precise guarantees that the sender keeps
to by following the above guidance are:
o not to re-use a MAC key
o not to use a MAC key K_i after its time interval i
o not to disclose key K_i sooner than the disclosure delay d * T_int
following the packet it protects
Sender setup, receiver bootstrapping and broadcasting authenticated
messages are otherwise all identical to the descriptions in sections
3.2, 3.3 and 3.4 respectively. However, the following step must be
added to the receiver authentication steps in section 3.5:
o After step 2, if a packet arrives carrying a key index i-d that has
already been received, it should not be buffered.
This simple scheme would suffice against DoS, were it not for the
fact that a network sometimes misorders packets without being
compromised. Even without control of a network element, an attacker
can opportunistically exploit such openings to fool a receiver into
buffering a bogus packet and discarding a later genuine one. A
receiver can choose to set aside a fixed size cache and manage it to
minimise the chances of discarding a genuine packet. However, given
such vulnerabilities are rare and unpredictable, it is simpler to
count these events as additions to the network loss rate. As always,
TESLA authentication will still uncover any bogus packets after the
disclosure delay.
To summarise, avoiding re-using keys has the following properties,
even under extreme flooding attacks:
o After delayed TESLA authentication, packets arriving within the
disclosure delay will always be identified as authentic if they are
and inauthentic if they are not.
o The fill rate of the receiver's buffer is clocked by each packet
revealed by the genuine sender, preventing memory flooding attacks.
o An attacker with control of a network element can cause any loss
rate it chooses (but that's always true anyway).
o Where attackers do not have control of any network elements, the
effective loss rate is bounded by the sum of the network's actual
loss rate and its re-ordering rate.
3.8.3. Sender buffering
Buffering of packets can be moved to the sender side, then receivers
can authenticate packets immediately upon receipt. This method is
described in [15].
3.9. Some extensions
Let us mention two salient extensions of the basic TESLA scheme. A Let us mention two salient extensions of the basic TESLA scheme. 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 heterogeneous network delays within a single multicast transmission.
transmission. A second extension allows having most of the A second extension allows having most of the buffering of packets at
buffering of packets at the sender side (rather than at the the sender side (rather than at the receiver side). Both extensions
receiver side). Both extensions are described in [15]. are described in [15].
The requirement in TESLA to receive a key in a later packet for The requirement in TESLA to receive a key in a later packet for
authentication prevents a receiver from authenticating the last authentication prevents a receiver from authenticating the last part
part of a message. Thus, to enable authentication of the last part of a message. Thus, to enable authentication of the last part of a
of a message or of the last message before a transmission message or of the last message before a transmission suspension, the
suspension, the sender needs to send an empty message with the key sender needs to send an empty message with the key to enable
to enable authentication. authentication.
4 Layer placement 4. Layer placement
The TESLA authentication can be performed at any layer in the TESLA authentication can be performed at any layer in the networking
networking stack. Three natural places are in the network, transport, stack. Three natural places are in the network, transport, or the
or the application layer. We list some considerations regarding the application layer. We list some considerations regarding the choice
choice of layer: of layer:
o 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 mitigating 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.)
o 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
has the drawback that packets are obtained by the application layer it has the potential drawback that packets are obtained by the
only after being processed by the transport layer. Consequently, application layer only after being processed by the transport
if TCP is used then this may introduce additional and unpredictable layer. Consequently, if buffering is used in the transport then
delays on top of the unavoidable network delays. (However, if UDP this may introduce additional and unpredictable delays on top of
is used then this is not a problem.) the unavoidable network delays.
o It should be kept in mind that, since TESLA relies upon timing o It should be kept in mind that, since TESLA relies upon timing of
of packets, deploying TESLA on top of a protocol or layer which packets, deploying TESLA on top of a protocol or layer which
aggressively buffers packets and hides the true packet arrival aggressively buffers packets and hides the true packet arrival
time (e.g., TCP) will significantly reduce the perormance of TESLA. time will significantly reduce TESLA's performance.
5. Security Considerations 5. IANA Considerations
This document has no actions for IANA.
6. Security Considerations
See the academic publications on TESLA [8,14,20] for several See the academic publications on TESLA [8,14,20] for several
security analyses. Regarding the security of implementations, by security analyses. Regarding the security of implementations, by
far the most delicate point is the verification of the timing far the most delicate point is the verification of the timing
conditions. Care should be taken to to make sure that: (a) the conditions. Care should be taken to make sure that: (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; (b) the receiver records the arrival time spec at session set-up; (b) the receiver records the arrival time
of the packet as soon as possible after the packet's arrival, and of the packet as soon as possible after the packet's arrival, and
computes the safety condition correctly. computes the safety condition correctly.
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 Finally, in common with all authentication schemes, if verification
is located separately from the ultimate destination application (e.g. is located separately from the ultimate destination application (e.g.
an IPSec tunnel end point), a trusted channel must be present between an IPSec tunnel end point), a trusted channel must be present between
verification and the application. For instance, the interface between verification and the application. For instance, the interface between
the verifier and the application might simply assume that packets the verifier and the application might simply assume that packets
received by the application must have been verified by the verifier received by the application must have been verified by the verifier
(because otherwise they would have been dropped). The application is (because otherwise they would have been dropped). The application is
then vulnerable to reception of packets that have managed to bypass then vulnerable to reception of packets that have managed to bypass
the verifier. the verifier.
6 IP Statement 7. Acknowledgments
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 the following for their feedback and support:
Mike Luby, Mark Baugher, Mats Naslund, Dave McGrew, Ross Finlayson,
Sylvie Laniepce, Lakshminath Dondeti, Russ Housley and the IESG
reviewers
8 References 8. References
All references are informative. 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
skipping to change at page 12, line 108 skipping to change at page 20, line 31
2002. 2002.
[21] M. Jakobsson, "Fractal hash sequence representation and traver¡ [21] M. Jakobsson, "Fractal hash sequence representation and traver¡
sal." Cryptology ePrint Archive, http://eprint.iacr.org/2002/001/, sal." Cryptology ePrint Archive, http://eprint.iacr.org/2002/001/,
Jan. 2002. Jan. 2002.
[22] D. Coppersmith and M. Jakobsson, "Almost optimal hash sequence [22] D. Coppersmith and M. Jakobsson, "Almost optimal hash sequence
traversal," in Proceedings of the Sixth International Financial Cryp¡ traversal," in Proceedings of the Sixth International Financial Cryp¡
tography Conference (FC '02) , March 2002. tography Conference (FC '02) , March 2002.
A Author Contact Information [23] N. Haller, "The S/KEY one-time password system," IETF RFC 1760,
February 1995.
A. Author Contact Information
Adrian Perrig Adrian Perrig
ECE Department ECE Department
Carnegie Mellon University Carnegie Mellon University
Pittsburgh, PA 15218 Pittsburgh, PA 15218
US US
perrig@cmu.edu perrig@cmu.edu
Ran Canetti Ran Canetti
IBM Research IBM Research
skipping to change at page 13, line 4 skipping to change at page 22, line 4
US US
tygar@cs.berkeley.edu tygar@cs.berkeley.edu
Bob Briscoe Bob Briscoe
BT Research BT Research
B54/77, 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, IPR Notice and Disclaimer
Copyright (C) The Internet Society (2000). All Rights Reserved. Copyright (C) The Internet Society (2004). This document is
subject to the rights, licenses and restrictions contained in BCP
78, and except as set forth therein, the authors retain all their
rights.
This document and translations of it may be copied and furnished to The IETF takes no position regarding the validity or scope of any
others, and derivative works that comment on or otherwise explain it Intellectual Property Rights or other rights that might be claimed
or assist in its implementation may be prepared, copied, published to pertain to the implementation or use of the technology
and distributed, in whole or in part, without restriction of any described in this document or the extent to which any license
kind, provided that the above copyright notice and this paragraph are under such rights might or might not be available; nor does it
included on all such copies and derivative works. However, this doc- represent that it has made any independent effort to identify any
ument itself may not be modified in any way, such as by removing the such rights. Information on the procedures with respect to rights
copyright notice or references to the Internet Society or other in RFC documents can be found in BCP 78 and BCP 79.
Internet organizations, except as needed for the purpose of develop-
ing Internet standards in which case the procedures for copyrights
defined in the Internet languages other than English.
The limited permissions granted above are perpetual and will not be Copies of IPR disclosures made to the IETF Secretariat and any
revoked by the Internet Society or its successors or assigns. assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use
of such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository
at http://www.ietf.org/ipr.
This document and the information contained herein is provided on an The IETF invites any interested party to bring to its attention
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING any copyrights, patents or patent applications, or other
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING proprietary rights that may cover technology that may be required
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION to implement this standard. Please address the information to the
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER- IETF at ietf-ipr@ietf.org.
CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."
This document and the information contained herein are provided on
an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT
THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR
ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
PARTICULAR PURPOSE.
Change log (to be removed before publication)
Main changes from draft-03 are:
* Abstract
Completely re-written to fit length guidelines
* Section 2. Functionality:
Added some clarification of the properties of TESLA
* Section 3. The Basic TESLA Protocol
Clarified why other TESLA publications are not normative
references.
* Section 3.2 Sender Setup
Removed the duplicate rule of thumb for determining d, and replaced
with reference forward to section 3.6. Replaced the imprecise
definition of m with half the precise definition of RTT from
section 3.6:
o Section 3.2 said d = ceil(2m/T_int);
o Section 3.6 said d = ceil(RTT/T_int) + 1
o Section 3.2 defined m as "the average network delay"
o Section 3.6 defined RTT as "a reasonable upper bound on the round
trip time between the sender and any receiver"
Added extra discussion of choice of key interval wrt congestion
and late joiners.
* Section 3.3 Bootstrapping Receivers
Clarified that any receiver including late joiners can do time
synchronization independently of others.
* Section 3.5 Receiver authentication
I had to completely re-arrange this to better allow the DoS
section to refer back to it. This was tough. Firstly, I enumerated
each step and gave them names (which should also help when other
standards refer to this one), so I could interleave steps
later in the DoS section. Secondly, the original text focused on
one packet, staying with it during buffering then eventual
verification. Instead, I traced the procedures that would be
triggered as a packet arrived. This involved leaving it in the
buffer for later and tracing through to the earlier packets it
released from the buffer.
* Section 3.6 Determining the Key Disclosure Delay
Added extra discussion of choice of disclosure delay wrt congestion
and late joiners.
* Section 3.8 Denial of service protection
Added whole new section
* Section 6 Security Considerations
Removed high level discussion of DoS
* Throughout
Spell-checked, fixed cross-referencing & nits, formatted.
* Fixed all the other IESG comments in
<https://datatracker.ietf.org/public/pidtracker.cgi?command=print_
ballot&ballot_id=690&filename=draft-ietf-msec-tesla-intro>
IANA considerations, boilerplate stuff, Acknowledgements, other
content issues covered in the relevant sections.
 End of changes. 93 change blocks. 
335 lines changed or deleted 583 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/