[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

Internet Engineering Task Force                                IRTF SMUG
Internet Draft                     Perrig, Canetti, Briscoe, Tygar, Song
draft-irtf-smug-tesla-00.txt   UC Berkeley / Digital Fountain / IBM / BT
17 November 2000
Expires: 17 June 2001


            TESLA: Multicast Source Authentication Transform

STATUS OF THIS MEMO

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference mate-
   rial or to cite them other than as "work in progress".

     The list of current Internet-Drafts can be accessed at
     http://www.ietf.org/ietf/1id-abstracts.txt

     The list of Internet-Draft Shadow Directories can be accessed at
     http://www.ietf.org/shadow.html.


Abstract

   This document describes TESLA, a secure sender authentication mecha-
   nism for multicast or broadcast data streams. Data authentication is
   an important component for many applications, for example audio and
   video Internet broadcasts, or data distribution by satellite.

   The main deterrents so far for a data authentication mechanism for
   multicast were the seemingly conflicting requirements: loss toler-
   ance, high efficiency, no per-receiver state at the sender. The prob-
   lem is particularly hard in settings with high packet loss rates and
   where lost packets are not retransmitted, and where the receiver
   wants to authenticate each packet it receives.

   TESLA provides authentication of individual data packets, regardless
   of the packet loss rate. In addition, TESLA features low overhead for
   both sender and receiver, and does not require per-receiver state at
   the sender. TESLA is secure as long as the sender and receiver are
   loosely time synchronized.




Perrig, Canetti, Briscoe, Tygar, Song                         [Page 1]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


                           Table of Contents

1          Introduction  . . . . . . . . . . . . . . . . . . . . . .   2
1.1        Previous Work . . . . . . . . . . . . . . . . . . . . . .   3
1.2        Terminology . . . . . . . . . . . . . . . . . . . . . . .   3
2          Rationale . . . . . . . . . . . . . . . . . . . . . . . .   3
3          Functionality . . . . . . . . . . . . . . . . . . . . . .   4
3.1        Threat Model and Security Guarantee . . . . . . . . . . .   5
3.2        Assumptions . . . . . . . . . . . . . . . . . . . . . . .   5
4          Notation  . . . . . . . . . . . . . . . . . . . . . . . .   6
5          Detailed TESLA Description  . . . . . . . . . . . . . . .   6
5.1        Sender Setup  . . . . . . . . . . . . . . . . . . . . . .   6
5.2        Bootstrapping a new Receiver  . . . . . . . . . . . . . .   7
5.3        Sending Authenticated Packets . . . . . . . . . . . . . .   9
5.4        Receiver Tasks  . . . . . . . . . . . . . . . . . . . . .   9
5.5        Multiple Authentication Instances . . . . . . . . . . . .  11
5.6        Immediate Authentication  . . . . . . . . . . . . . . . .  12
5.7        TESLA Authentication Field Format for MESP  . . . . . . .  14
5.8        TESLA for Authentication in other Protocols . . . . . . .  18
5.9        Security Discussion . . . . . . . . . . . . . . . . . . .  18
6          Implementation Considerations for the Sender  . . . . . .  19
6.1        Choosing the disclosure delay . . . . . . . . . . . . . .  19
6.2        Choosing the interval duration  . . . . . . . . . . . . .  19
6.3        Selecting a PRF and a MAC . . . . . . . . . . . . . . . .  20
6.4        Altering key chains on the fly  . . . . . . . . . . . . .  20
7          Implementation Considerations for the Receiver  . . . . .  21
7.1        Time Synchronization and Security Condition Issues  . . .  21
7.2        Reconstruction of the key chain . . . . . . . . . . . . .  23
7.3        Protecting against Denial-of-Service Attacks  . . . . . .  23
8          Acknowledgments . . . . . . . . . . . . . . . . . . . . .  23
9          Bibliography  . . . . . . . . . . . . . . . . . . . . . .  23
A          TESLA Attributes  . . . . . . . . . . . . . . . . . . . .  26
B          Time Synchronization Packet Format  . . . . . . . . . . .  27
B.1        Direct Synchronization  . . . . . . . . . . . . . . . . .  27
B.2        Indirect Synchronization  . . . . . . . . . . . . . . . .  31
C          Author Contact Information  . . . . . . . . . . . . . . .  32
D          Full Copyright Statement  . . . . . . . . . . . . . . . .  34



1 Introduction

   As the online population continues to expand, the Internet is
   increasingly used to distribute streamed media, such as streamed
   radio and video. We expect this trend to continue.

   To enable a widespread and trusted streamed media dissemination, one
   must first provide sufficient security guarantees. A most prominent



Perrig, Canetti, Briscoe, Tygar, Song                         [Page 2]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   security risk from a user point of view is data authenticity. The
   user needs assurance that the data stream originated from the pur-
   ported sender. Otherwise, an attacker could replace parts of the
   stream with its own material. For example, an adversary might alter
   stock quotes that are distributed through IP multicast. In that sce-
   nario, the receiver needs strong sender and data authentication.

   The problem of continuous stream authentication is solved for the
   case of one sender and one receiver via standard mechanisms, e.g.
   [1,2]. The sender and receiver agree on a secret key which is used in
   conjunction with a message authenticating code (MAC) to ensure
   authenticity of each packet. In case of multiple receivers, however,
   the problem becomes much harder to solve, because a symmetric
   approach would allow anyone holding a key (that is, any receiver) to
   forge packets. Alternatively, the sender can use digital signatures
   to sign every packet with its private key. This solution provides
   adequate authentication, but digital signatures are prohibitively
   inefficient.

   Real-time data streams are lossy, which makes the security problem
   even harder.  With many receivers, we typically have a high variance
   among the bandwidth of the receivers, with high packet loss for the
   receivers with relatively low bandwidth. Nevertheless, we want to
   assure data authenticity even in the presence of high packet loss.
   One of the main challenges is to ensure data authenticity of every
   received packet, even though lost packets are not retransmitted.

1.1 Previous Work

   A number of schemes for solving data authentication have been sug-
   gested in the past few years [3,4,5,6,7,8,9,10,11].  An Internet
   Draft based on [7] was proposed by McCarthy in 1998 but was not
   updated.

   This document is based mainly on the TESLA [8,9] and FLAMeS [10]
   schemes, which have low computation and communication overhead.  Sim-
   ilar schemes were suggested by Cheung [12], and by Bergadano et al.
   [11,13].

1.2 Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [14].

2 Rationale





Perrig, Canetti, Briscoe, Tygar, Song                         [Page 3]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   The authentication of broadcast data is an important building block
   for settings that require source authentication.

   The secure multicast group (SMuG) views multicast source authentica-
   tion as one of the fundamental security services [15]. In particular,
   an early SMuG draft mentions the multicast source authentication and
   data integrity building block as one of four fundamental functional
   building blocks [16].

   The recent multicast data security transformation draft also needs
   source authentication [17]. The draft distinguishes between two data
   authentication methods, namely the internal data authentication tag,
   and the external authentication data. The former is encrypted with
   the payload and the latter is outside of the encrypted data. TESLA
   can be used in both cases. In this document, we propose TESLA as a
   building block. We define the format of the authentication informa-
   tion only, without committing to any specific packet format.

   Source authentication is also required within the reliable multicast
   transport (RMT) IETF group [18]. In particular, authentication is
   required in the Asynchronous Layered Coding (ALC) draft [19]. TESLA
   is ideally suited also in this setting to provide source authentica-
   tion, possibly by incorporating it within AMESP and then in turn
   incorporating AMESP within the ALC header. See details in [17].

3 Functionality

   TESLA provides delayed per-packet data authentication. The key idea
   to provide 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:

     ¸ Low computation overhead. The authentication involves typically
       only one MAC function and one hash function computation per
       packet, for both sender and receiver.

     ¸ Low per-packet communication overhead. Overhead can be as low as
       12 bytes per packet.

     ¸ Arbitrary packet loss tolerated. Every packet which is received
       in time can be authenticated.

     ¸ Unidirectional data flow. Data only flows from the sender to the
       receiver.  No acknowledgments or other messages are necessary
       except for time synchronisation or for eventual initial connec-
       tion setup. This implies that the sender's stream authentication



Perrig, Canetti, Briscoe, Tygar, Song                         [Page 4]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


       overhead is independent of the number of receivers, hence TESLA
       is very scalable.

     ¸ No sender-side buffering. Every packet is sent as soon as it is
       ready.

     ¸ High guarantee of authenticity. The system provides strong
       authenticity. By strong authenticity we mean that the receiver
       has a high assurance of authenticity, as long as our timing and
       cryptographic assumptions are enforced. However, the scheme does
       not provide non-repudiation. That is, the recipient cannot con-
       vince a third party that the stream arrived from the claimed
       source.


   TESLA can be used both in the network layer or in the application
   layer. The delayed authentication, however, requires buffering of
   packets until authentication is completed.

3.1 Threat Model and Security Guarantee

   We design TESLA to be secure against a powerful adversary with the
   following capabilities:

     ¸ Full control over the network. The adversary can eavesdrop, cap-
       ture, drop, resend, delay, and alter packets.

     ¸ Access to a fast network with negligible delay.

     ¸ 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 neg-
       ligible delay. Nonetheless, the adversary cannot invert a pseudo-
       random function (or distinguish it from a random function) with
       non-negligible probability.

   The security property TESLA guarantees is that the receiver never
   accepts M_i as an authentic message unless M_i was actually sent by
   the sender. A scheme that provides this guarantee is called a secure
   stream authentication scheme.

3.2 Assumptions

   For TESLA to be secure, the sender and the receiver ARE REQUIRED to
   be loosely time synchronized. Loosely time synchronized means that
   the synchronization does not need to be precise, but the receiver
   MUST know an upper bound on the dispersion (the maximum clock



Perrig, Canetti, Briscoe, Tygar, Song                         [Page 5]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   offset). TESLA supports two synchronization methods, direct and indi-
   rect synchronization. In direct synchronization, the receiver syn-
   chronizes its time directly with the data sender, in indirect syn-
   chronization both the sender and the receiver synchronize their time
   with a common time synchronization service. If the latter method is
   used, we assume that secure time synchronization servers exist in the
   network, for example NTP servers [20]. Finally, the clock of the
   receiver MUST have known drift while receiving information from the
   server and MUST be secure against alteration by an attacker. We would
   like to emphasize that the security of TESLA does not rely on any
   assumptions on network propagation delay.

   TESLA also MUST be bootstrapped through a regular data authentication
   system. We recommend 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 cer-
   tificate in case of a PKI (public-key infrastructure).

   Finally, the MAC and pseudo-random functions MUST be cryptographi-
   cally secure.  Further details on the instantiation of the MAC and
   PRF are in section 6.3.

4 Notation

   To denote the subscript or an index of a variable, we use the under-
   score 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 a
   superscript we use the caret, e.g. the function F with the argument x
   executed i times is F^i(x), executed j-1 times we write F^{j-1}(x).

5 Detailed TESLA Description

   In this section, we describe TESLA in detail. We first discuss our
   threat model and the security guarantees that TESLA provides. Next we
   describe the sender setup, the receiver bootstrapping process, fol-
   lowed by the detailed sender receiver operations.

5.1 Sender Setup

   In our model, a sender distributes a long message M as a stream of
   small message chunks M_i (the i'th chunk of the message). Generally,
   the sender sends each message chunk M_i in one network packet P_i.

   For the purpose of TESLA, the sender splits the time up into even
   intervals I_i, where the duration of each interval is Tint and the
   starting time of an interval is TI_i. Trivially, we have TI_i = TI_0
   + i * Tint. In each interval, the sender may send zero or multiple
   packets.



Perrig, Canetti, Briscoe, Tygar, Song                         [Page 6]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   Before sending the first message, the sender determines the sending
   duration (possibly infinite), the interval duration, and the number N
   of keys of the key chain. In section 6.1 and 6.2, we will go into
   more detail about the choice of Tint and on the length of the hash
   chain.  This key chain is analogous to the one-way chain introduced
   by Lamport [21], and the S/KEY authentication scheme [22]. The sender
   then picks the last key K_N of the key chain randomly and pre-com-
   putes the entire key chain using a pseudo-random function F, which is
   by definition a one-way function. Each element of the chain is
   defined as K_i = F(K_{i+1}).  Each key can be derived from K_N as K_i
   = F^{N-i}(K_N), where F^j(k) = F^{j-1}(F(k)) and F^0(k) = k. Each key
   of the key chain corresponds to one interval (K_j is active in inter-
   val I_j).

   Since we do not want to use the same key multiple times in different
   cryptographic operations, we use a second pseudo-random function F'
   to derive the key which is used to compute the MAC of messages in
   each interval. Hence, K'_i = F'(K_i). Figure 1 depicts this key
   derivation. The choice of F and F' are detailed in section 6.3.


           F(Ki)       F(Ki+1)         F(Ki+2)
    Ki-1 <------- Ki <--------- Ki+1 <-------

     |             |             |
     | F'(Ki-1)    | F'(Ki)      | F'(Ki+1)
     |             |             |
     V             V             V

    K'i-1         K'i           K'i+1



   Figure 1: TESLA key chain and the derived MAC keys



5.2 Bootstrapping a new Receiver

   TESLA requires loosely synchronized clocks between the sender and the
   receivers.  Furthermore, TESLA requires an initially authenticated
   data packet. This authentication is achieved with a digital signature
   scheme, such as RSA [23], or DSA [24].

   We present two options for synchronizing the time. Either the
   receiver directly synchronizes its time with the sender (direct syn-
   chronization), or both the sender and receiver synchronize their time
   with a third entity, a time server (indirect synchronization), for



Perrig, Canetti, Briscoe, Tygar, Song                         [Page 7]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   example using NTP [20]. Both schemes (including their packet format)
   are described in appendix B.  Whatever time synchronization mechanism
   is used, the receiver MUST know the dispersion (maximum clock offset)
   after the time synchronization.

   For both schemes, we assume that the sender's and receiver's clocks
   have negligible drift, otherwise the receiver uses periodic re-syn-
   chronization, or accounts for the drift with an increased d_t.

   The receiver MUST receive the following authenticated information
   about the time intervals and key chain:

     ¸ The beginning time of a specific interval TI_j

     ¸ The id of that interval I_j

     ¸ The interval duration Tint

     ¸ The number n of authentication instances per packet. Note that
       all TESLA instances share the same time interval and key chain,
       only the key disclosure delay is different for each instance.

     ¸ Key disclosure delay d_v of each authentication instance (unit is
       interval) (1 <= v <= n)

     ¸ A publically known key K_i (i < j - d where j is the current
       interval index)

     ¸ The interval of the last key chain element (key chain expiration)

     ¸ Total key chain length

     ¸ Indicate if immediate authentication is used, and how many hashes
       of future data segments are added to each TESLA header.

     ¸ For each hash in the immediate authentication, the sender defines
       the maximum distance in intervals that the hash value spans. Usu-
       ally, this distance is equal to the maximum key disclosure delay.

   The sender needs to define the parameters of the cryptographic primi-
   tives that TESLA uses. The following parameters MUST be defined:

     ¸ The number n_1 of bits used for the key chain keys.

     ¸ A function F that is used to compute the key chain. Recall that
       K_i = F(K_{i+1}). Hence F MUST take an input of size n_1 and map
       it to an output of equal length.




Perrig, Canetti, Briscoe, Tygar, Song                         [Page 8]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


     ¸ The number n_2 of bits used for the MAC key.

     ¸ A function F' to derive the MAC key from key chain keys. Recall
       that K'_i = F'(K_i). F' takes an input of n_1 bits and outputs
       n_2 bits.

     ¸ A MAC function that takes a key of length n_2 bits and data of
       any length; and outputs a MAC of length n_3.

     ¸ A hash function H that is used for the immediate authentication.
       H takes an input of arbitrary length and outputs n_4 bits.

   Appendix A presents a list of the TESLA attributes.

   For each of these values, n_i needs to be smaller or equal length
   than the function that generates the parameter. If the required out-
   put is smaller, we truncate is as specified in RFC 2104 [25].

   If the sender and the receiver are already time synchronized, the
   sender may periodically broadcast signed packets that contain the
   above interval and key chain information. A new receiver would simply
   wait for such a packet, authenticate it with traditional schemes, and
   it can authenticate subsequent packets of the stream using TESLA.
   This is particularly useful in the case of satellite broadcast, since
   the receiver does not need to send any messages to the sender to
   bootstrap the authentication.

5.3 Sending Authenticated Packets

   Each key is used in one time interval. However many messages are sent
   in each interval I_j, the key K_{j+d} is used to compute the MAC of
   all those messages. This allows the sender to send packets at any
   rate and to switch the sending rate dynamically. The key K_{j+d}
   remains secret for d-1 future intervals and is disclosed in interval
   I_{j+d}.. Packets sent in interval I_j can hence disclose key K_j. As
   soon as the receivers receive that key, they can verify the authen-
   ticity of the packets sent in interval I_{j-d}.  Figure 2 shows the
   time intervals and the arrows point from the interval to the interval
   of which the key is disclosed. In the figure, d=2, hence packet P_2
   sent in interval I_{j+3} discloses key K_{j+3}. From this key, the
   receiver can also recover K_{j+2} and verify the MAC of P_1.


5.4 Receiver Tasks

   Since the security of TESLA depends on keys that remain secret until
   a pre-determined time period, the receiver MUST verify for each
   packet that the key, which is used to compute the MAC of that packet,



Perrig, Canetti, Briscoe, Tygar, Song                         [Page 9]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



            _____   _____
           /     \ /     \
          /       \       \
         /       / \       \
        /       /   \       \
        V      V     \       \
  --+------+------+------+------+---> t
       Ij    Ij+1   Ij+2   Ij+3

       Kj    Kj+1   Kj+2   Kj+3

     +----+                +----+
     | P1 |                | P2 |
     +----+                +----+



   Figure 2: TESLA intervals and key disclosure


   is not yet published by the sender. Otherwise an attacker could have
   changed the message data and re-computed the MAC. This motivates the
   security condition, which the receiver MUST verify for each packet it
   receives.

   Security condition: A packet arrived safely, if the receiver is
   assured (based on its synchronized time and d_t) that the sender is
   not yet in the time interval in which the corresponding key is dis-
   closed.

   The formal definition of the security condition is in section 7.1.
   The intuition is that no attacker could have altered the packet in
   transit, because the corresponding MAC key is not yet disclosed by
   the sender. In case the security condition is not valid, the receiver
   MUST drop that packet, because the authenticity is not assured any
   more.

   This stream authentication scheme is secure as long as the security
   condition holds. We would like to emphasize that the security of this
   scheme does not rely on any assumptions on network propagation delay.

   We can now explain how the authentication with TESLA works with a
   concrete example. Figure 2 shows an example of two packets sent in
   different intervals. When the receiver receives packet P_i sent in
   interval I_j at time t_i (meaning the time the entire packet is
   received), it first evaluates the security condition. For this, the
   receiver computes the highest interval the sender could possibly be



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 10]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   in, in this case that interval is x = (t_i - TI_0 + d_t) / Tint. It
   now needs to verify x < I_j + d (I_j is the interval index) which
   means that the sender cannot be in the interval when the key K_j is
   disclosed, hence no attacker can possibly know that key and spoof the
   message contents.

   Another property (could be called sanity condition) is that the
   receiver can verify if the interval id I_j is possible and is not in
   the future, i.e. if the sender can already be in that interval. The
   verification condition is that the following MUST hold I_j < (t_i -
   TI_0 + d_t) / Tint. This test prevents a denial-of-service attack
   described in more detail in section 7.3.

   The receiver cannot, however, verify the authenticity of the message
   yet.  Instead, it stores the triplet ( I_j, M_i, MAC( K'_j, M_i) ) to
   verify the authenticity later when it knows K'_j. Two possibilities
   exist on how to handle the unauthenticated message chunk M_i. The
   first possibility is to hand M_i to the application, and notify it
   through a callback mechanism as soon as M_i is verified. The second
   possibility it to keep M_i until the authenticity can be checked and
   pass it to the application as soon as M_i is authenticated.

   If the packet contains a disclosed key, regardless of whether the
   security condition is verified or not, the receiver checks whether it
   can use K_{j-d} to authenticate previous packets. Clearly, if it has
   received K_{j-d} previously, it does not have any work to do. Other-
   wise, let us assume that the last key value in the reconstructed key
   chain is K_{v}. The receiver verifies if K_{j-d} is legitimate by
   applying the pseudo-random function F (j - d - v) -times and by veri-
   fying that the result is indeed K_{v}. More formally, K_{v} == F^{j-
   d-v}(K_{j-d}). If that condition is correct, the receiver updates the
   key chain. For each new keys K_{w}, it computes K'_{w} = F'(K_w)
   which might allow it to verify the authenticity of previously
   received packets.

   It is clear that this system can tolerate arbitrary packet loss,
   because the receiver can verify the authenticity of all received
   packets eventually.

5.5 Multiple Authentication Instances

   The key disclosure period in TESLA presents a tradeoff. If the time
   difference is short, the packet can be authenticated quickly, but if
   the packet travel time is long the security condition will not hold
   for remote receivers, which forces them to drop the packet. Con-
   versely, a long time period will suit remote receivers, but the
   authentication time delay may be unacceptable for receivers with fast
   network access. Since the scheme needs to scale to a large number of



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 11]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   receivers and we expect the receivers to have a wide variety of net-
   work access, we need to solve this tradeoff. Our approach is to use
   multiple authentication instances with different disclosure periods
   simultaneously. Each receiver can then use the instance with the min-
   imal disclosure delay, sufficient to prevent spurious drops which are
   caused if the security condition does not hold.

   The receiver verifies one security condition for each authentication
   instance C_i, and drops the packet if none of the conditions are sat-
   isfied. Assume that the sender uses n authentication instances, where
   the first instance has the smallest delay until the disclosure packet
   is sent, and the nth instance has the longest delay. Furthermore,
   assume that for the incoming packet P_j, the security conditions for
   instances C_v (v < m) are not satisfied, and the condition for
   instance C_m is satisfied. In this case, as long as the key disclo-
   sure packets for the instances C_v (v < m ) arrive, the receiver's
   confidence in the authenticity of packet P_j is increasing. As soon
   as the key disclosure packet for a instance C_v (v >= m) arrives, the
   receiver is assured of the authenticity of the packet P_j.

   Instead of using one independent key chain per TESLA instance, we use
   the same key chain and time interval for all instances, but each
   instance has a different key disclosure delay. Each key K_i in the
   key chain is associated with the corresponding time interval T_i, and
   K_i will be disclosed in T_i. Assume that the sender uses n instances
   of TESLA, which we denote with A_1 ... A_n. Each TESLA instance A_u
   has a different key disclosure delay d_u, and it will have a MAC key
   schedule derived from the key schedule shifted by d_u time intervals
   from the key disclosure schedule. Let K^u_{i+d_u} denote the MAC key
   used by instance u in time interval T_i. We derive K^u_{i+d_u} as
   K^u_{i+d_u} = MAC(K_{i+d_u},u). The reason for generating all differ-
   ent, independent keys for each instance is to prevent an attack where
   an attacker moves the MAC value of an instance to another instance,
   which might allow it to claim that data was sent in a different
   interval. Our approach of generating independent keys prevents this
   attack. Thus to compute the MAC value in packet P_j in time interval
   T_i, the sender computes one MAC value of the message chunk M_j per
   instance and append the MAC values to M_j. In particular, for the
   instance A_u with disclosure delay d_u, the sender will now use the
   key K^u_{i+d_u} as mentioned above for the MAC computation.


   Figure 3 shows an example with two TESLA instances, one with a key
   disclosure time of two intervals and the other of four intervals. The
   lowest line of keys shows the key disclosure schedule, i.e. which key
   is disclosed in which time interval. The middle and top line of keys
   shows the key schedule of the first and second instance respectively,
   i.e. which key is used to compute the MAC for the packets in the



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 12]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



  K''_{j+4}   K''_{j+5}   K''_{j+6}   K''_{j+7}   K''_{j+8}  MAC key inst 2

  K'_{j+2}    K'_{j+3}    K'_{j+4}    K'_{j+5}    K'_{j+6}   MAK key inst 1

  K_j         K_{j+1}     K_{j+2}     K_{j+3}     K_{j+4}    Disclosed key

+----------+-----------+-----------+-----------+-----------+---> t

  I_j         I_{j+1}     I_{j+2}     I_{j+3}     I_{j+4}    Interval #



   Figure 3: TESLA intervals and key disclosure


   given time interval for the given instance. Using this technique, the
   sender will only need to disclose one key no matter how many
   instances are used concurrently.

5.6 Immediate Authentication

   A drawback of the basic TESLA protocol is that the receiver needs to
   buffer packets during one disclosure delay before it can authenticate
   them. This might not be practical for certain applications if the
   receivers cannot afford much buffer space and bursty traffic might
   cause the receivers to drop packets due to insufficient buffer space.
   Moreover, as we show later in section 7.3, the requirement of
   receiver buffering introduces a vulnerability to a denial-of-service
   attack. To solve these problems caused by receiver-buffering, we pro-
   pose a new method to support immediate authentication, which allows
   the receiver to authenticate packets as soon as they arrive.

   The basic observation of this method is that we can replace receiver
   buffering with sender buffering. If the sender can buffer packets
   during one disclosure delay, then it could store the hash value of
   the data of a later packet in an earlier packet and hence as soon as
   the earlier packet is authenticated, the data in the later packet is
   authenticated through the hash value as well.


   In the new scheme, the sender buffers packets for the duration of one
   disclosure delay. For simplicity of illustration, we assume that the
   sender sends out a constant number v of packets per time interval. To
   construct the packet for the message chunk M_j in time interval T_i,
   the sender appends the hash value of the message chunk M_{j+vd} to
   M_j and then computes the MAC value also over H(M_{j+vd}) with the
   key K_i. Figure 4 illustrates how the packet P_j is constructed by



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 13]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



      - +-----------------------+            +-----------------------+-
     /  | M_j                   |      /---> | M_{j+vd}              | \
D_j -   +-----------------------+     /      +-----------------------+ - D_{j+vd}
     \  | H( M_{j+vd} )         | ---/       | H( M_{j+2vd} )        | /
      - +-----------------------+            +-----------------------+-
        | MAC( K'_i, D_j )      | <---\      | MAC(K'_{i+d},D_{j+vd})|
        +-----------------------+      \     +-----------------------+
        | K_{i-d}               |       \--- | K_i                   |
        +-----------------------+            +-----------------------+



   Figure 4: Immediate authentication packet example. D_j =  H(M_{j+vd})
   | M_j and D_{j+vd} = H(M_{j+2vd}) | M_{j+vd}.


   appending H(M_{j+vd}), MAC(K_i, M_j | H(M_{j+vd})), along with the
   disclosed key K_{i-d}. (Note that the | stands for message concatena-
   tion). When the packet P_{j+vd} arrives at the receiver which dis-
   closes the key K_i it allows authentication of packet P_j sent in
   interval I_i. P_j carries a hash of the data M_{j+vd} in P_{j+vd}. If
   P_j is authentic, H(M_{j+vd}) is also authentic and therefore the
   data M_{j+vd} is immediately authenticated. Also note that if P_j is
   lost or dropped due to violation of the security condition, P_{j+vd}
   will not be immediately authenticated and can still be authenticated
   later using the MAC value. To achieve higher robustness to lost pack-
   ets, the sender may add multiple hashes of future packets to the data
   packet, as we show in the data format in the following section.

   The above description assumes a constant sending rate, an assumption
   which might not be the satisfied in practice. If the sending rate
   varies, matching the hash to the data with simple counting does not
   work any more. A simple solution would be to add the sequence number
   of the packet that contains the data to the hash.  Unfortunately,
   this introduces overhead. A simple trick can save space in the TESLA
   header. From the connection setup, the receiver knows for each hash
   the interval in which the data will be sent in. Hence, to match the
   hash to the data, the receiver stores for each future interval the
   authenticated hashes that it received. For each incoming packet, the
   receiver can compute the hash of the data and search if the corre-
   sponding hash is present, which would immediately authenticate the
   data.

5.7 TESLA Authentication Field Format for MESP

   TESLA can be used to authenticate the content of a variety of proto-
   cols. We discuss the format of the TESLA authentication field for the



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 14]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   case where it is used as the internal or external authentication
   scheme in MESP [17]. The MESP (for Multicast ESP) header is proposed
   as the header for authenticated and/or encrypted multicast traffic.

   The approach of MESP for designing the packet format is to use a con-
   nection setup phase in which the various parameters of the header
   field are defined (such as authentication type and field lengths).
   Hence, subsequent headers fields do not contain type or length infor-
   mation.


   Figure 5 shows the authentication data field format for authenticat-
   ing message M_i. The fields have the following semantics. Note that
   if the length of each field will be rounded up to the next byte
   boundary.


     ¸ Disclosed key present flag (D): 1 bit
       D=1 indicates that this packet discloses the key of a previous
       interval. If D=0, the disclosed key is not present.

     ¸ Commitment to new key chain present flag (C): 1 bit
       C=1 indicates that the commitment value of the next key chain is
       present, only used shortly before switching to a new key chain.
       The common case is that C=0 and the key is not present. Section
       6.4 has more details on how to switch key chains.

     ¸ The last key from the previous key chain disclosed again flag
       (L): 1 bit
       L=1 indicates that the last key of the previous key chain is dis-
       closed again. The common case is L=0 and the disclosed key is not
       present.  Section 6.4 has more details on how to switch key
       chains.
       *NOTE*: Since the size of the authentication field in MESP is
       fixed, exactly one of these fields MUST be set to one (and there-
       fore one of these fields MUST be present).

     ¸ Reserved (Res): 5 bits
       All these bits MUST be set to 0.


     ¸ Disclosed key: n_1 bits if present
       Disclosing the interval key is OPTIONAL, since any key can be
       derived from a later interval key. The implementor needs to be
       careful though since a sparse key disclosure can potentially lead
       to an increased authentication delay.





Perrig, Canetti, Briscoe, Tygar, Song                        [Page 15]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|D|C|L|   Res   |                                               |
+-+-+-+-+-+-+-+-+ [Disclosed Key K_i] or                        ~
|                 [Commitment to new key] or                    |
~                 [Disclosed Key of previous chain]             ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                 [H( M_v1 )]                                   ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                 [H( M_v3 )]                                   ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                 [H( M_v2 )]                                   ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                 Mac(K'_{i-d_1}, Di)                           ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                 [Mac(K''_{i-d_2}, Di)]                        ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                 [Mac(K'''_{i-d_3}, Di)]                       ~
|                                                               |
~               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               |               Padding (0-3 bytes)             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



   Figure 5: TESLA authentication field format in MESP


     ¸ Commitment to new key chain: n_1 bits if present
       This field is OPTIONAL.  When the key chain tapers off and the
       sender wants to continue sending, the key chain needs to be
       changed and a commitment to the new key chain is added to the
       packet. It is implicit that the new chain will have the same
       length as the old key chain. A more detailed discussion is in



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 16]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


       section 6.4.

     ¸ Disclosed key from previous chain: n_2 bits if present
       This field is OPTIONAL. Since the last key from the previous
       chain cannot be recovered from the current keys, a receiver might
       not have received the last key of a changed key chain, so it
       might need to be retransmitted. See section 6.4 for details.

     ¸ H( M_vi ): n_4 bits
       These fields are OPTIONAL. If immediate authentication is used,
       the hashes of future data packets are present. From the connec-
       tion setup, the receiver knows for each hash the interval in
       which the data will be sent in. Hence, to match the hash to the
       data, the receiver stores for each future interval the authenti-
       cated hashes that it received. For each incoming packet, the
       receiver can search if the corresponding hash is present, which
       would immediately authenticate the data.

     ¸ MAC: n_3 bits
       The MAC MUST be present in the packet. The MAC is computed over
       all data that needs authentication, which we denote with D_i, so
       MAC ( K'_j, D_i ). The MESP draft defines the data that is in D_i
       for both the internal and external authentication the fields that
       are included in the MAC.  An exception, however, is that if the
       TESLA header contains a commitment to a new key of a new key
       chain, that key MUST be authenticated, hence it MUST be included
       in the data part of the computation of the MAC. Another exception
       are the hash value of the immediate authentication, which MUST
       also be authenticated, and hence included in the MAC computation.
       The format of the MAC computation is
       MAC( K'_j, D_i [| K_{new chain}] [| h_1 | ... | h_m ]).
       As mentioned, D_i corresponds to the data that needs to be
       authenticated as described in [17]. If the commitment to the new
       key chain is in the packet, it is included in the MAC computa-
       tion, as well as the hashes of future data, if immediate authen-
       tication is used.


     ¸ Padding: 0-3 bytes
       Pads the authentication block to the next 4 byte boundary. The
       padding field MUST be set to 0.

   Note that no sequence number is present in the MESP version of the
   TESLA header, because MESP already features sequence numbers. The
   purpose of the sequence number is to filter out duplicates. Since
   TESLA does not provide duplicate protection, the packet sequence num-
   ber helps the TESLA implementation to filter out duplicate messages
   for the receiver. Another method to remove duplicates is to use the



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 17]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   MAC of the message and remove messages that were sent in the same
   interval and have identical MAC's.

   Also, the header we present does not include an explicit interval
   number.  However, the receiver can infer the interval from the dis-
   closed key. For reasonable implementations, changing key chains is
   extremely rare, and hence almost all packets will contain the dis-
   closed key that implicitly informs the receiver of the time interval.
   Even if the disclosed key is not present, the receiver may infer the
   time interval by a brute-force verification of which time interval
   the packet was sent in.

5.8 TESLA for Authentication in other Protocols

   Other authentication fields in other protocols may require different
   formats for the TESLA authentication field. For example, the Asyn-
   chronous Layer Coding (ALC) draft of the Reliable Multicast Group
   (RMT) also has an authentication field in their header, which needs a
   length and type field inside the authentication information [19]. It
   is straightforward to adapt TESLA for this format.

   It is also possible to use the AMESP format with TESLA authentication
   (as described in Section 5.7) for the ALC authentication filed.  See
   more details in [17].

5.9 Security Discussion

   We briefly discuss potential security problems in this section and
   show how we address them in TESLA. First, we note that a more rigor-
   ous proof of security is detailed in [8].

   The main point is that an attacker can perform at most a denial-of-
   service attack. Since we assume that the attacker has full control
   over the network, a denial-of-service attack is always possible (the
   attacker can simply drop or alter all packets). In the proof in [8]
   we show that an attacker cannot forge a MAC or invert the key chain,
   otherwise the attacker can break or invert the MAC function, which we
   assume is not possible. Similarly, the attacker cannot alter the
   packets undetectable, because she could not recompute the crypto-
   graphically secure MAC. Consequently, creating new packets is not
   possible either.

   The security of TESLA is clearly compromised if an attacker could
   alter the receiver's clock. Hence, we assume that this is not possi-
   ble. However, how is the security of TESLA influenced by speeding up
   or delaying individual packets?  Delaying packets does not help,
   since the worst that could happen is for the receiver to drop the
   packet because it does not satisfy the security condition.  Delaying



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 18]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   packets therefore results in a denial-of-service attack. On the other
   hand, speeding up packets does not do anything at all. The receiver
   even benefits from this since she might be able to use a chain with a
   short disclosure delay that she could not use otherwise.

   The packet replay attack is prevented by adding a sequence number to
   each packet. Other measures against replay attacks are presented in
   section 5.7. The TESLA layer in the network stack or in the applica-
   tion will filter out duplicate packets. In any case, a duplication
   would be possible only within a short time period, since the security
   condition would cause packets to be dropped if they were duplicated
   with a long delay.

6 Implementation Considerations for the Sender

   This section discusses general implementation issues for the sender.
   This discussion will assume that the sender uses one authentication
   chain only.

6.1 Choosing the disclosure delay

   The choice of the disclosure delay presents a tradeoff. If the dis-
   closure delay is short, the packet can be authenticated quickly, but
   if the packet travel time is long the security condition will not
   hold for remote receivers, which forces them to drop the packet. Con-
   versely, a long time period will suit remote receivers, but the
   authentication time delay may be unacceptable for receivers with fast
   network access. Since the scheme needs to scale to a large number of
   receivers and we expect the receivers to have a wide variety of net-
   work access, we need to address this tradeoff.

   The first approach is to use multiple authentication chains, to
   accommodate the heterogeneity of the receiver delays, described in
   section 5.5.  The problem remains how to choose the disclosure delay.

   The main requirement for the disclosure delay is that the majority of
   packets will validate the security condition. Suppose that an upper
   bound on the dispersion of any client is d_t (maximum clock offset)
   and the propagation delay of any (reasonable) client is at most d_p.
   Usually the dispersion is also dependent on the propagation delay, in
   practice d_t ~ RTT. For each packet, the receiver needs to verify
   that the corresponding key was not disclosed yet at the moment the
   packet arrives. Therefore, the disclosure delay D_d needs to be
   longer than the sum of the dispersion and the propagation delay D_d >
   d_t + d_p.

6.2 Choosing the interval duration




Perrig, Canetti, Briscoe, Tygar, Song                        [Page 19]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   The interval duration affects other parameters of TESLA. One key is
   necessary for each time interval, and due to the one-wayness of
   pseudo-random functions, the sender needs to pre-compute the key
   chain before sending packets.  Consequently, a short interval dura-
   tion and a long expected sending time will result in a longer pre-
   computation time.

   Another factor to consider for the interval duration is the accuracy
   of the security condition. Because the time is sampled into inter-
   vals, the security condition is evaluated using the interval as unit.
   The finer-grained (or shorter) the interval duration is, the easier
   it is to approximate the ideal disclosure duration. A simple example
   illustrates this. The disclosure delay always needs to be longer than
   one interval, because otherwise (assuming that the disclosure delay
   is only one interval) packets that are sent close to an interval
   boundary would always violate the security condition. To achieve at
   least two intervals for the disclosure delay, the interval duration
   should be shorter than half of the desired disclosure delay Tint <
   D_d / 2.

   The security is also influenced by the choice of the interval dura-
   tion. The same key is used to compute the MAC of all packets sent in
   that interval. If a large number of packets is sent in each interval,
   an attacker can gather the packet-MAC pairs to attack the system. So
   far, we are not aware of such an attack, but it is nevertheless pru-
   dent to minimize the number of MAC computations that use an identical
   key.

6.3 Selecting a PRF and a MAC

   TESLA requires two pseudo-random functions, one to generate the key
   chain and the other one to derive the MAC key from the key chain key.
   Figure 1 shows both functions. A good choice is to use HMAC for this
   purpose [25]. Any cryptographically secure hash function can be used
   in conjunction with HMAC, for example MD5 [26], SHA-1 [27], or
   RIPEMD-160. We propose the following constructs for our functions:
   F(x) = HMAC(x, 0) and F'(x) = HMAC(x, 1). Note that the first parame-
   ter to HMAC is the key and the second parameter is the data. For
   TESLA, the key size is 80 bits and the parameters 0 and 1 are passed
   as one-byte character (0x00 and 0x01 respectively). The output of
   this function is truncated to 80 bits, we pick the 80 most signifi-
   cant bits out of the 128 output bits.

   Clearly, we also use HMAC for our MAC function. We simply have
   MAC(k,d) = HMAC(k,d) and we use the 80 most significant bits.

6.4 Altering key chains on the fly




Perrig, Canetti, Briscoe, Tygar, Song                        [Page 20]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   If a sender distributes the same information for a long time, the
   pre-computed key chain can taper off. The question is how the sender
   can seamlessly switch to a new key chain. A simplistic approach is
   for the sender to stop using the old chain, send a new authenticated
   packet that commits to the new chain and to subsequently use the new
   chain only. The shortcoming of this scheme is that a receiver might
   not receive the authenticated packet and could not authenticate sub-
   sequent packets. Another approach is to use two key chains that over-
   lap during a short transition period. The shortcoming of this
   approach is that the authentication field size would need to grow
   larger during the transition period, which conflicts with the fixed
   authentication field size in some standards mentioned previously.

   A better approach is to commit to the new key chain by using previous
   TESLA packets. The challenge of packet loss though remains. A solu-
   tion is to add the commitment to the new key chain to a number of
   packets. The sender needs to start sending the new key chain commit-
   ment value early enough, such that the majority of receivers will
   receive and authenticate the new key chain before the previous chain
   expires. This ensures that the switching to the new chain happens
   seamlessly.

   Figure 6 shows an example. One key chain stops at Key K_n and the
   next chain starts with key K_{n+1}. The sender would then include a
   commitment to the new key chain into multiple packets of the previous
   chain, so F(K_{n+1}) would be added to packets throughout intervals
   I_{n-3} through I_n. Since the keys of the new chain are first
   revealed in interval I_{n+4}, it is sufficient if the commitment to
   the new key chain is sent in interval I_n (because the key K_n is
   disclosed in interval I_{n+3}).  Again, to guard against packet loss
   it is safer to add the commitment to multiple packets before interval
   I_n. Similarly, the key for interval I_n is disclosed by packets sent
   in interval I_{n+3}, but if interval I_{n+3} packets are either not
   sent or lost, the receiver could not verify the packets from interval
   I_n. To guard against this event, the sender would include K_n in a
   packets sent after interval I_{n+3}.


7 Implementation Considerations for the Receiver

   This section discusses implementation considerations for the
   receiver.

7.1 Time Synchronization and Security Condition Issues

   We assume that the time at the receiver has negligible drift. In case
   the time drift can be substantial, periodic time synchronization is
   necessary. In appendix B, we propose two time synchronization schemes



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 21]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000




  _____  _____  _____  _____  _____  _____  _____  ___
       \/     \/     \/     \/     \/     \/     \/
       /\     /\     /\     /\     /\     /\     /\
      /  \   /  \   /  \   /  \   /  \   /  \   /  \
     /    \ /    \ /    \ /    \ /    \ /    \ /    \
    /      \      \      \      \      \      \
   /      / \    / \    / \    / \    / \    / \    /
  /      /   \  /   \  /   \  /   \  /   \  /   \  /
 V      V     \V     \V     \V     \V     \V     \V
  --+------+------+------+------+------+------+------+---> t
      In-3  In-2   In-1     In    In+1   In+2   In+3

      Kn-3  Kn-2   Kn-1     Kn    Kn+1   Kn+2   Kn+3

  -----------------------------> <-----------------------
         Old key chain                  New key chain




   Figure 6: Key chain change


   for TESLA. Either the receiver synchronizes its time with the sender
   directly, or indirectly with a time synchronization server in the
   network. In the latter case, the receiver would need to wait for an
   authenticated interval and key chain announcement packet, before it
   can start authenticating packets of the data stream. Even if the
   receiver is not time synchronized, it can already receive packets and
   record their arrival times. Later in time after the time synchroniza-
   tion, the receiver can then start to evaluate their security condi-
   tion and authenticate the packets.

   Before sending the packet, the receiver records the current time T_s.
   When it receives the sender's response, the receiver immediately
   records the current time T_r. After this, the receiver verifies the
   digital signature using the public key of the server, and checks that
   the returned nonce is equal to the nonce sent (if the return packet
   contains the nodes of a hash tree, the receiver computes the root
   node of the hash tree and checks if that matches the value in the
   packet). If the check is unsuccessful or if the round-trip-time (RTT
   = T_r - T_s) passes a certain threshold, the synchronization needs to
   be repeated. The packet will contain the current time at the sender
   T_c.





Perrig, Canetti, Briscoe, Tygar, Song                        [Page 22]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   During the protocol, the receiver needs to evaluate the earliest and
   the latest time that the sender can possibly be in. The latest possi-
   ble time t_l at the server is t_l = t - T_s + T_c, where t is the
   current receiver time.  Similarly, the earliest possible time at the
   sender is t_e = t - T_r + T_c.

   To evaluate the security condition, the receiver computes the latest
   possible time that the sender can be at and it verifies that the
   sender is not yet in the time interval in which the corresponding key
   is disclosed. Assume that the packet arrival time is t_p and the
   interval is I_j. The corresponding key will be disclosed in interval
   I_{j+d}. The latest possible interval the server can be in is I' =
   integer( (t_l - T_i) / Tint ) + I_i, where T_i is the starting time
   of interval I_i. So the security condition is valid if I' < I_{j+d}.

   Similarly, the receiver can ensure that the sender can even be in
   that interval, based on the earliest time the server can be in. This
   test prevents the denial-of-service attack outlined in section 7.3.
   The check is integer( (t_e - T_i) / Tint ) + I_i >= I_j.

7.2 Reconstruction of the key chain

   The receiver reconstructs the key chain as time progresses. For each
   new key chain value it receives, it verifies the correctness of the
   key by calling the pseudo-random function F until it matches the last
   authenticated key chain value. Fortunately, it makes no sense for the
   receiver to store the entire key chain. As soon as a key value is
   used to authenticate packets in the packet buffer, no new packet
   could arrive using that same key since it would clearly violate the
   security condition. Hence a key can be immediately discarded after
   the corresponding packets were authenticated. Only the most recently
   disclosed key is used subsequently, because it is a commitment for
   the later keys in the key chain and it is therefore used to verify a
   new key.

7.3 Protecting against Denial-of-Service Attacks

   A possible denial-of-service attack on the receiver would be as fol-
   lows. A malicious attacker can send a packet with a sending interval
   that is far out in the future. When the receiver would try to verify
   the disclosed key, it would need to perform a large number of pseudo-
   random function computations, which would cause it to waste large
   amounts of its computation resources. Fortunately, this attack is
   easy to prevent. Analogous to the security condition, the receiver
   verifies for each packet whether it is even possible that the sender
   has sent that particular packet. If this check is not satisfied, the
   packet must be spoofed and the receiver immediately drops the packet.




Perrig, Canetti, Briscoe, Tygar, Song                        [Page 23]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


8 Acknowledgments

   We would like to thank Mike Luby for his feedback and support.

9 Bibliography

   [1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet
   Request for Comments RFC 2246, January 1999.  Proposed standard.

   [2] Ipsec, "IP Security Protocol, IETF working group."
   http://www.ietf.org/html.charters/ipsec-charter.html.

   [3] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B.
   Pinkas, "Multicast security: A taxonomy and some efficient construc-
   tions," in Infocom '99 , 1999.

   [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech.
   rep., IBM T.J.Watson Research Center, 1997.

   [5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul-
   ticast packet authentication," in 6th ACM Conference on Computer and
   Communications Security , November 1999.

   [6] P. Rohatgi, "A hybrid signature scheme for multicast source
   authentication," Internet Draft, Internet Engineering Task Force,
   June 1999.  Work in progress.

   [7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul-
   ticasts," in Proc. IEEE ICNP `98 , 1998.

   [8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient
   authentication and signing of multicast streams over lossy channels,"
   in IEEE Symposium on Security and Privacy , May 2000.

   [9] A. Perrig, R. Canetti, D. X. Song, and J. Tygar, "Efficient and
   secure source authentication for multicast," in Network and Dis-
   tributed Systems Security NDSS 2001 , 2001.

   [10] B. Briscoe, "Flames: Fast, loss-tolerant authentication of mul-
   ticast streams," tech. rep., BT Research, 2000.
   http://www.labs.bt.com/people/briscorj/papers.html.

   [11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream
   authentication," in Selected Areas in Cryptography 2000 , (Waterloo,
   Canada), August 2000.  A talk describing this scheme was given at IBM
   Watson in August 1998.





Perrig, Canetti, Briscoe, Tygar, Song                        [Page 24]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   [12] S. Cheung, "An efficient message authentication scheme for link
   state routing," in 13th Annual Computer Security Applications Confer-
   ence , 1997.

   [13] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single
   source authentication on the mbone," in ICME 2000 , Aug 2000.  A talk
   containing this work was given at IBM Watson, August 1998.

   [14] S. Bradner, "Key words for use in RFCs to indicate requirement
   levels," Request for Comments (Best Current Practice) 2119, Internet
   Engineering Task Force, Mar. 1997.

   [15] Secure Multicast Group (SMuG).  http://www.ipmulticast.com/com-
   munity/smug/.

   [16] R. Canetti, P. Cheng, D. Pendarakis, J. Rao, P. Rohatgi, and D.
   Saha, "An architecture for secure internet multicast," Internet
   Draft, Internet Engineering Task Force, Feb. 1999.  Work in progress.

   [17] R. Canetti, P. Rohatgi, and P.-C. Cheng, "Multicast data secu-
   rity transformations: Requirements, considerations, and prominent
   choices," internet draft, Internet Engineering Task Force, 2000.
   draft-data-transforms.txt.

   [18] Reliable Multicast Transport (RMT).
   http://www.ietf.org/html.charters/rmt-charter.html.

   [19] M. Luby, J. Gemmell, L. Vicisano, L. Rizzo, J. Crowcroft, and B.
   Lueckenhoff, "Asynchronous layered coding. a massively scalable reli-
   able multicast protocol," internet draft, Internet Engineering Task
   Force, July 2000.  draft-ietf-rmt-pi-alc-01.txt.

   [20] D. L. Mills, "Network Time Protocol (Version 3) Specification,
   Implementation and Analysis." Internet Request for Comments, March
   1992.  RFC 1305.

   [21] L. Lamport, "Password authentication with insecure communica-
   tion," Communications ACM , vol. 24, Nov. 1981.

   [22] N. Haller, "The S/KEY one-time password system," Request for
   Comments (Informational) 1760, Internet Engineering Task Force, Feb.
   1995.

   [23] R. L. Rivest, A. Shamir, and L. M. Adleman, "A method for
   obtaining digital signatures and public-key cryptosystems," Communi-
   cations ACM , vol. 21, no. 2, pp. 120--126, 1978.





Perrig, Canetti, Briscoe, Tygar, Song                        [Page 25]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   [24] "Digital Signature Standard (DSS), Federal Register 56." FIPS
   PUB 186, Aug.  1991.

   [25] M. Bellare, R. Canetti, and H. Krawczyk, "HMAC: Keyed-hashing
   for message authentication," Internet Request for Comment RFC 2104,
   Internet Engineering Task Force, Feb. 1997.

   [26] R. L. Rivest, "The MD5 message-digest algorithm." Internet
   Request for Comments, Apr. 1992.  RFC 1321.

   [27] C. S. Laboratory), "Secure hash standard." Federal Information
   Processing Standards Publication FIPS PUB 180-1.
   http://csrc.nist.gov/fips/fip180-1.txt (ascii),
   http://csrc.nist.gov/fips/fip180-1.ps (postscript), Apr. 1995.

   [28] M. Baugher, T. Hardjono, and B. Weis, "Group domain of interpre-
   tation for isakmp," internet draft, Internet Engineering Task Force,
   July 2000.  draft-irtf-smug-gdoi-00.txt.

   [29] M. Bishop, "A Security Analysis of the NTP Protocol Version 2,"
   in Sixth Annual Computer Security Applications Conference , November
   1990.

   [30] R. Merkle, "Protocols for public key cryptosystems," in 1980
   IEEE Symposium on Security and Privacy , 1980.

A TESLA Attributes

   The following attributes need to be defined in the connection startup
   phase for TESLA. This list is extended from [28] and will be com-
   pleted in the next version of this draft.


           ID Class                   Value
           --------                   -----
           RESERVED                     0
           SOURCE_ID                   64
           DIRECT_SYNCHRONIZATION      65
           SENDERS_CERT_TYPE           66
           SENDERS_CERT                67
           MAC_TYPE                    68
           MAC_LENGTH                  69
           KEY_CHAIN_PRF               70
           KEY_CHAIN_KEY_LENGTH        71
           INTERVAL_NUMBER             72
           INTERVAL_STARTING_TIME      73
           INTERVAL_DURATION           74
           KEY_DISCLOSURE_DELAY        75



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 26]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


           KEY_CHAIN_COMMITMENT_VALUE  76
           KEY_CHAIN_EXPIRATION_VALUE  77
           NUMBER_OF_TESLA_INSTANCES   78
           IMMEDIATE_AUTH_HASH_NUMBER  79
           IMMEDIATE_AUTH_HASH_TYPE    80
           IMMEDIATE_AUTH_HASH_LENGTH  81



B Time Synchronization Packet Format

   We present two options for synchronizing the time. Either the
   receiver directly synchronizes its time with the sender (direct syn-
   chronization), or both the sender and receiver synchronize their time
   with a third entity, a time server (indirect synchronization). We
   discuss both cases separately.

B.1 Direct Synchronization

   In direct synchronization, each receiver synchronizes its time with
   the sender, and registers the dispersion (maximum clock offset
   between the sender and receiver clock). We remark that the receiver
   only needs to know a rough upper bound d_t on the dispersion (where
   d_t can be on the order of multiple seconds).  (Many clock synchro-
   nization algorithms exist, for example the work of Mills on NTP [20],
   and its security analysis [29].) In section 7.1 we describe a simple
   protocol and discuss scalability issues related to the initial syn-
   chronization.

   The receiver sends a time synchronization request to the sender. To
   ensure that the senders response is fresh and not replayed by an
   attacker, the receiver creates a nonce N_r and sends it to the
   sender. Figure 7 shows the request information.


   The sender will then return this nonce in the response, which allows
   the receiver to ensure that the response packet is fresh. The
   response packet contains the following components:

     ¸ The current sender time

     ¸ The beginning time of a specific interval TI_j

     ¸ The id of that interval I_j

     ¸ The interval duration Tint





Perrig, Canetti, Briscoe, Tygar, Song                        [Page 27]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                                                               ~
|                          Nr (nonce)                           |
~                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



   Figure 7: Time synchronization request packet format


     ¸ Key disclosure delay d (unit is interval)

     ¸ A publically known key K_i (i < j - d where j is the current
       interval index)

     ¸ The interval of the last key chain element (key chain expiration)

     ¸ Total key chain length

     ¸ The nonce N_r

   Figure 8 shows the outline of the direct synchronization packet for-
   mat. If the T-bit is set, multiple users requested synchronization
   concurrently and a hash tree was formed over the nonces. Hence the
   signed nonce is the root of the hash tree and the other nodes used
   for reconstruction is added outside of the signature at the end of
   the packet. If the bit is clear, no hash tree is added and the value
   in the nonce field is the users nonce.

   The times are specified in milliseconds (ms). Absolute times are
   expressed in the number of milliseconds since January 1, 1970. Since
   we use 64-bit time fields, this value will roll over in the year
   584944387 AD. The interval id's and lengths are in 32-bit fields.
   Finally, the packet is signed. The digital signature includes the
   bitfield and ends at the nonce.

   The number of nodes specifies how many nodes of the hash tree follow.
   This number is followed by a list of 10-byte tree hash nodes, start-
   ing at the lowest node. The last hash node in the list a child node
   of the root node.





Perrig, Canetti, Briscoe, Tygar, Song                        [Page 28]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   The receiver uses a nonce in its first packet to prevent a replay
   attack by an attacker that replays a previously signed synchroniza-
   tion reply. Besides the current sender time t_S, the sender also
   sends all information necessary to define the intervals and a commit-
   ment to the active key chain. The disclosure lag defines the differ-
   ence in intervals on when the key values are disclosed.  Finally, the
   packet is signed with a digital signature scheme.

   Since an adversary could artificially speed up either the sender's or
   the receiver's packet, the timestamp t_S that the sender returns
   could be either from the instant the request was sent or from the
   instant the request is received. The receiver sets its local time to
   t_S and sets d_t = RTT, where RTT stands for the round-trip time. The
   sender's time is assured to be within the interval [t-d_t,t+d_t],
   where t is the synchronized local time of the receiver.  This syn-
   chronization is quite primitive, but it is secure against an active
   adversary and it's accuracy suffices for our application. To increase
   the accuracy, the receiver can run the protocol multiple times and
   use the run which has the lowest RTT. Any other time synchronization
   protocol can be used, as long as it is robust against an active
   adversary (most schemes do not satisfy this requirement). An example
   for a time synchronization protocol is Mills NTP [20].

   This response packet needs to be authenticated with a digital signa-
   ture scheme, such as RSA [23], or DSA [24].  We assume that a public-
   key infrastructure is in place (PKI). Since most public-key signature
   algorithms are computationally expensive, the signing of the response
   packet can become a performance bottleneck for the sender. (A 500 MHz
   Pentium III workstation can compute on the order of 100 RSA 1024-bit
   signatures per second.) A simple trick can alleviate this situation.
   The sender can aggregate multiple requests, compute and sign a Merkle
   hash tree that is generated from all the requester's nonces [30].
   Figure 9 shows how such a hash tree is constructed. If N_h is the
   root of the hash tree, N_h would be included in the signed part of
   the response packet instead of N_r. To verify the digital signature
   of the response packet, each receiver would reconstruct the hash
   tree. Since it does not know the other receiver's nonces that are
   part of the hash tree, the sender would include the nodes of the tree
   necessary to reconstruct the root node. For the example in figure 9,
   the packet returned to receiver A would include N_b and H_{cd}.
   Receiver A can reconstruct the root node H_{ad} from these values and
   its own nonce N_a as follows: H_{ad} = H(H(N_a,N_b),H_{cd}). Note
   that the number of nodes returned in the response packet is logarith-
   mic in the number of receivers whose request arrived in the same time
   interval. Assuming a 50 ms interval time (the sender would need to
   compute at most 20 signatures per second) and assuming that 1,000,000
   receivers wanted to synchronize their time in that interval, the
   return packet would only need to contain 20 hash nodes or 200 bytes,



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 29]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                  Sender time (unit: ms)                       ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Interval id (j)                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                  Beginning time of interval Ij (unit: ms)     ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Interval duration (unit: ms)                 |
~-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Key disclosure (unit:interval)|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               ~
|                                                               |
~                  Disclosed Key Ki                             ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Last key chain element interval              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Total key chain length                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                                                               ~
|                  Nr (nonce)                                   |
~                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |T|       Signature length      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                  Signature (variable length)                  ~
|                                                               |
~                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |   Padding (variable length)   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # of nodes    |                                               |
+-+-+-+-+-+-+-+-+                                               ~
|                  Node list (size = 10 * # of nodes)           |
~                                                               ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



   Figure 8: Direct synchronization packet format



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 30]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


   assuming an 80 bit hash function. Any cryptographically secure hash
   function can be used for H(x,y), for example MD5 [26].


                   Had
                  /    \
                 /      \
                /        \
               Hab       Hcd
              /  \      /  \
             /    \    /    \
            Na    Nb  Nc    Nd



   Figure  9: Hash tree over receiver nonces. Node H_{ab} = H(N_a, N_b).
   H_{ad} = H(H_{ab},H_{cd}).



B.2 Indirect Synchronization

   If distributed time synchronization servers exist in the network, the
   sender and receivers can separately synchronize their clocks with the
   same time synchronization server. The resulting dispersion is the sum
   of their dispersions with the time synchronization server. NTP is a
   sophisticated time synchronization protocol that can be used in this
   case [20].

   To bootstrap the authentication process, an initial authenticated
   packet is still required, which can be authenticated with a digital
   signature scheme. The sender periodically broadcasts an interval
   specification message, digitally signed with its private key. The
   initial authenticated packet contains the precise interval informa-
   tion (interval frequency and the starting time of a specific inter-
   val) along with the key of a past interval. The packet contains the
   following fields:

     ¸ The Id / IP address of the time synchronization server

     ¸ The dispersion to the time synchronization server

     ¸ The beginning time of a specific interval TI_j

     ¸ The id of that interval I_j

     ¸ The interval duration Tint




Perrig, Canetti, Briscoe, Tygar, Song                        [Page 31]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


     ¸ Key disclosure delay d (unit is interval)

     ¸ A publically known key K_i (i < j - d where j is the current
       interval index)

     ¸ The interval of the last key chain element (key chain expiration)

     ¸ Total key chain length

   The packet format is depicted in figure 10. The bitfield is currently
   unused in this version and reserved for future purposes. The remain-
   ing fields are analogous to the direct synchronization packet, except
   that the current time is replaced with the IP address of the time
   synchronization server and the dispersion of the sender's clock with
   respect to the time synchronization server.


   The main advantage for indirect synchronization is that the sender
   does not need to process any requests from the receiver, hence this
   scheme achieves maximum scalability. This also dramatically improves
   the security of the sender, since it can be configured not to receive
   any packets.

C Author Contact Information


Adrian Perrig
SIMS - UC Berkeley / Digital Fountain
102 South Hall, 4600
Berkeley, CA 94720
US
perrig@cs.berkeley.edu

Ran Canetti
IBM Research
30 Saw Mill River Rd
Hawthorne, NY 10532
US
canetti@watson.ibm.com

Bob Briscoe
BT Research
B54/74, BT Labs
Martlesham Heath
Ipswich, IP5 3RE
UK
bob.briscoe@bt.com




Perrig, Canetti, Briscoe, Tygar, Song                        [Page 32]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000



 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|        Id of the synchronization server (IP address)          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Sender's dispersion with the time syn server (unit: ms)    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Interval id (j)                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
~                  Beginning time of interval Ij (unit: ms)     ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Interval duration (unit: ms)                 |
~-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Key disclosure (unit:interval)|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               ~
|                                                               |
~                  Disclosed Key Ki                             ~
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Last key chain element interval              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Total key chain length                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Signature length (unit: bytes)|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               ~
|                                                               |
~                  Signature (variable length)                  ~
|                                                               |
~                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                               |   Padding (variable length)   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+



   Figure 10: Indirect synchronization packet format


Doug Tygar
SIMS - UC Berkeley
102 South Hall, 4600
Berkeley, CA 94720-4600
US
tygar@cs.berkeley.edu

Dawn Song



Perrig, Canetti, Briscoe, Tygar, Song                        [Page 33]


Internet Draft          draft-irtf-smug-tesla-00        17 November 2000


CS - UC Berkeley
387 Soda Hall, 1776
Berkeley, CA 94720-1776
US
dawnsong@cs.berkeley.edu



D Full Copyright Statement

   Copyright (C) The Internet Society (2000). All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this doc-
   ument itself may not be modified in any way, such as by removing the
   copyright notice or references to the Internet Society or other
   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
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS 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 MER-
   CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."


















Perrig, Canetti, Briscoe, Tygar, Song                        [Page 34]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/