Request for Comments: 4082 D. Song
Category: Informational Carnegie Mellon University
R. Canetti
IBM
J. D. Tygar
University of California, Berkeley
B. Briscoe
BT
June 2005
Timed Efficient Stream Loss-Tolerant Authentication (TESLA):
Multicast Source Authentication Transform Introduction
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2005).
Abstract
This document introduces Timed Efficient Stream Loss-tolerant
Authentication (TESLA). TESLA allows all receivers to check the
integrity and authenticate the source of each packet in multicast or
broadcast data streams. TESLA requires no trust between receivers,
uses low-cost operations per packet at both sender and receiver, can
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 do not have to send any
messages. TESLA alone cannot support non-repudiation of the data
source to third parties.
This informational document is intended to assist in writing
standardizable and secure specifications for protocols based on TESLA
in different contexts.
Table of Contents
1. Introduction ....................................................2
1.1. Notation ...................................................3
2. Functionality ...................................................4
2.1. Threat Model and Security Guarantee ........................5
2.2. Assumptions ................................................5
3. The Basic TESLA Protocol ........................................6
3.1. Protocol Sketch ............................................6
3.2. Sender Setup ...............................................7
3.3. Bootstrapping Receivers ....................................8
3.3.1. Time Synchronization ................................9
3.4. Broadcasting Authenticated Messages .......................10
3.5. Authentication at Receiver ................................11
3.6. Determining the Key Disclosure Delay ......................12
3.7. Denial of Service Protection ..............................13
3.7.1. Additional Group Authentication ....................14
3.7.2. Not Re-using Keys ..................................15
3.7.3. Sender Buffering ...................................17
3.8. Some Extensions ...........................................17
4. Layer Placement ................................................17
5. Security Considerations ........................................18
6. Acknowledgements ...............................................19
7. Informative References .........................................19
1. Introduction
In multicast, a single packet can reach millions of receivers.
Unfortunately, this introduces the danger that an attacker can
potentially also reach millions of receivers with a malicious packet.
Through source authentication, receivers can ensure that a received
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 through
a simple mechanism: the sender and the receiver share a secret key to
compute a message authentication code (MAC) of all communicated data.
When a message with a correct MAC arrives, the receiver is assured
that the sender generated that message. Standard mechanisms achieve
unicast authentication this way; for example, TLS or IPsec [1,2].
Symmetric MAC authentication is not secure in a broadcast setting.
Consider a sender that broadcasts authentic data to mutually
mistrusting receivers. The symmetric MAC is not secure: every
receiver knows the MAC key and therefore could impersonate the sender
and forge messages to other receivers. Intuitively, we need an
asymmetric mechanism to achieve authenticated broadcast, such that
every receiver can verify the authenticity of messages it receives,
without being able to generate authentic messages. Achieving this in
an efficient way is a challenging problem [3].
The standard approach to achieving such asymmetry for authentication
is to use asymmetric cryptography; e.g., a digital signature.
Digital signatures have the required asymmetric property: the sender
generates the signature with its private key, and all receivers can
verify the signature with the sender’s public key, but a receiver
with the public key alone cannot generate a digital signature for a
new message. A digital signature provides non-repudiation, a
stronger property than authentication. However, digital signatures
have a high cost: they have a high computation overhead for both the
sender and the receiver, and most signatures also have a high-
bandwidth overhead. Since we assume broadcast settings for which the
sender does not retransmit lost packets, and the receiver still wants
to authenticate each packet it receives immediately, we would need to
attach a digital signature to each message. Because of the high
overhead of asymmetric cryptography, this approach would restrict us
to low-rate streams, and to senders and receivers with powerful
workstations. We can try to amortize one digital signature over
multiple messages. However, this approach is still expensive in
contrast to symmetric cryptography, since symmetric cryptography is
in general 3 to 5 orders of magnitude more efficient than asymmetric
cryptography. In addition, the straight-forward amortization of one
digital signature over multiple packets requires reliability, as the
receiver needs to receive all packets to verify the signature. A
number of schemes that follow this approach are [4,5,6,7]. See [8]
for more details.
This document presents the Timed Efficient Stream Loss-tolerant
Authentication protocol (TESLA). TESLA uses mainly symmetric
cryptography, and uses time-delayed key disclosure to achieve the
required asymmetry property. However, TESLA requires loosely
synchronized clocks between the sender and the receivers. See more
details in Section 3.3.1. Schemes that follow a similar approach to
TESLA are [9,10,11].
1.1. Notation
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 index i is K_i, and the key K with index i+d is K_{i+d}. To
write a superscript, we use the caret; e.g., function F with the
argument x executed i times is F^i(x).
2. Functionality
TESLA provides delayed per-packet data authentication and integrity
checking. The key idea to providing both efficiency and security is
a delayed disclosure of keys. The delayed key disclosure results in
an authentication delay. In practice, the delay is on the order of
one RTT (round-trip-time).
TESLA has the following properties:
o Low computation overhead for generation and verification of
authentication information.
o Low communication overhead.
o Limited buffering required for the sender and the receiver, and
therefore timely authentication for each individual packet.
o Strong robustness to packet loss.
o Scales to a large number of receivers.
o Protects receivers from denial of service attacks in certain
circumstances if configured appropriately.
o Each receiver cannot verify message authenticity unless it is
loosely time-synchronized with the source, where synchronization
can take place at session setup. 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 cannot prove this to a
third party.
TESLA can be used in the network layer, in the transport layer, or in
the application layer. Delayed authentication, 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 while 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 that packets are not processed in parallel to buffering.
2.1. Threat Model and Security Guarantee
We design TESLA to be secure against a powerful adversary with the
following capabilities:
o Full control over the network. The adversary can eavesdrop,
capture, drop, re-send, delay, and alter packets.
o Access to a fast network with negligible delay.
o The adversary’s computational resources may be very large, but
not unbounded. In particular, this means that the adversary can
perform efficient computations, such as computing a reasonable
number of pseudo-random function applications and MACs with
negligible delay. Nonetheless, the adversary cannot find the
key of a pseudo-random function (or distinguish it from a random
function) with non-negligible probability.
The security property of TESLA guarantees that the receiver never
accepts M_i as an authentic message unless the sender really sent
M_i. A scheme that provides this guarantee is called a secure
broadcast authentication scheme.
Because TESLA expects the receiver to buffer packets before
authentication, the receiver needs to protect itself from a potential
denial of service (DoS) attack due to a flood of bogus packets (see
Section 3.8).
2.2. Assumptions
TESLA makes the following assumptions in order to provide security:
1. The sender and the receiver must be loosely time-synchronized.
Specifically, each receiver must be able to compute an upper
bound on the lag of the receiver clock relative to the sender
clock. We denote this quantity with D_t. (That is, D_t =
sender time - receiver time). We note that an upper bound on
D_t can easily be obtained via a simple two-message exchange.
(Such an exchange can be piggybacked on any secure session
initiation protocol. Alternatively, standard protocols such
as NTP [15] can be used.
2. TESLA MUST be bootstrapped at session setup through a regular
data authentication system. One option is to use a digital
signature algorithm for this purpose, in which case the
receiver is required to have an authentic copy of either the
sender’s public key certificate or a root key certificate 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
functions). These MUST be cryptographically secure. Further
details on the instantiation of the MAC and PRF are in Section
3.4.
We would like to emphasize that the security of TESLA does NOT rely
on any assumptions about network propagation delay.
3. The Basic TESLA Protocol
TESLA is described in several academic publications: A book on
broadcast security [12], a journal paper [13], and two conference
papers [7,14]. Please refer to these publications for in-depth
proofs of security, experimental results, etc.
We first outline the main ideas behind TESLA.
3.1. Protocol Sketch
As we argue in the introduction, broadcast authentication requires a
source of asymmetry. TESLA uses time for asymmetry. We first make
sure that the sender and receivers are loosely time-synchronized as
described above. Next, the sender forms a one-way chain of keys, in
which each key in the chain is associated with a time interval (say,
a second). Here is the basic approach:
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 the current key from the one-way chain as a cryptographic
key to compute the MAC.
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 is
disclosed at time interval i+3).
o Each receiver receives the packet. Each receiver knows the
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 to
compute the MAC was not yet disclosed by the sender. If it was
not, then the receiver buffers the packet. Otherwise the packet
is dropped due to inability to authenticate. Note that we do
not know for sure whether a "late packet" is a bogus one or
simply a delayed packet. We drop the packet because we are
unable to authenticate it. (Of course, an implementation may
choose not to drop packets and to use them unauthenticated.)
o Each receiver checks that the disclosed key belongs to the
hash-chain (by checking against previously released keys in the
chain) and then checks the correctness of the MAC. If the MAC
is correct, the receiver accepts the packet.
Note that one-way chains have the property that if intermediate
values of the one-way chain are lost, they can be recomputed using
subsequent values in the chain. Even if some key disclosures are
lost, a receiver can recover the corresponding keys and check the
correctness of earlier packets.
We now describe the stages of the basic TESLA protocol in this order:
sender setup, receiver bootstrap, sender transmission of
authenticated broadcast messages, and receiver authentication of
broadcast messages.
3.2. Sender Setup
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
interval in sequence.
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 before a new one-way chain must be created. The sender
picks a random value for K_N. Using a pseudo-random function (PRF),
f, the sender constructs the one-way function F: F(k) = f_k(0). The
rest of the chain is computed recursively using K_i = F(K_{i+1}).
Note that this gives us K_i = F^{N-i}(K_N), so the receiver can
compute any value in the key chain from K_N, even if it does not have
intermediate values. The key K_i will be used to authenticate
packets sent in time interval i.
Jakobsson [20] and Coppersmith and Jakobsson [21] 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 disclosure delay, d. (T_int is measured in time units, say
milliseconds, and d is measured in number of time intervals. That
is, 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
values of T_int and d>0. 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. A T_int that is too short will
cause the keys to run out too soon. A 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). A delay d
that is too short will cause too many packets to be unverifiable by
the receiver. A delay d that is too long will cause excessive delay
in authentication.
The sender estimates a reasonable upper bound on the network delay
between the sender and any receiver as m milliseconds. This includes
any delay expected in the stack (see Section 4, on layer placement).
If the sender expects to send a packet every n milliseconds, then a
reasonable value for T_int is max(n,m). Based on T_int, a rule of
thumb for determining the key disclosure delay, d, is given in
Section 3.6.
The above value for T_int is neither an upper or a lower bound; it is
merely the value that reduces key change processing to a minimum
without causing authentication delay to be higher than necessary. 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 from the time synchronization between the sender and
the receivers.)
3.3. Bootstrapping Receivers
Before a receiver can authenticate messages with TESLA, it needs to
have the following:
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
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,
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 with the public key of the signer.)
o The disclosure schedule of the following keys:
- T_int, the interval duration.
- T_0, the start time of interval 0.
- 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 get the
authenticated TESLA parameters in a two-round message exchange, as
described below. We stress again that time synchronization can be
performed as part of the registration protocol between any receiver
(including late joiners) and the sender, or between any receiver and
a group controller.
3.3.1. Time Synchronization
Various approaches exist for time synchronization [15,16,17,18].
TESLA only requires the receiver to know an upper bound on the delay
of its local clock with respect to the sender’s clock, so a simple
algorithm is sufficient. TESLA can be used with direct, indirect,
and delayed synchronization as three default options. The specific
synchronization method will be part of each instantiation of TESLA.
For completeness, we sketch a simple method for direct
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, at the moment of sending.
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.
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
throughout the duration of the session.
Note:
o Assuming that the messages are authentic (i.e., the message
received by 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 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.
o The exchange of sync messages needs to be authenticated. This
can be done in a number of ways; for instance, with a secure NTP
protocol or in conjunction with a session set-up protocol.
For indirect time synchronization (e.g., synchronization via a group
controller), the sender and the controller engage in a protocol for
finding the value D^0_t between them. 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
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
message, using the key corresponding to the current time interval.
The key remains secret for the next d-1 intervals, so messages that a
sender broadcasts in interval j effectively disclose key K_j-d. We
call d the key disclosure delay.
We do not want to use the same key multiple times in different
cryptographic operations; that is, using key K_j to derive the
previous key of the one-way key chain K_{j-1}, and using the same 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 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 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 MAC key
derivation. To broadcast message M_j in interval i the sender
constructs the packet
P_j = {M_j || i || MAC(K’_i,M_j) || K_{i-d}}