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 27 July 2000 Expires: 26 January 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". To view the list Internet-Draft Shadow Directories, see http://www.ietf.org/shadow.html. Abstract This document describes TESLA, a secure sender authentication mecha­ nism for multicast 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 27 July 2000 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 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]. 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] and FLAMeS [9] schemes, which have low computation and communication overhead. Simi­ lar schemes were suggested by Cheung [11], by Bergadano et al. [10]. 1.2 Terminology Perrig, Canetti, Briscoe, Tygar, Song [Page 2] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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 [12]. 2 Rationale 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 [13]. In particular, an early SMuG draft mentions the multicast source authentication and data integrity building block as one of four fundamental functional building blocks [14]. The recent multicast data security transformation draft also needs source authentication [15]. 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 and we define the format of the authentication infor­ mation only, without committing to any specific packet format. Source authentication is also required within the reliable multicast transport (RMT) IETF group [16]. In particular, authentication is required in the Asynchronous Layered Coding (ALC) draft [17]. TESLA is ideally suited also in this setting to provide source authentica­ tion. 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. Perrig, Canetti, Briscoe, Tygar, Song [Page 3] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 · Unidirectional data flow. Data only flows from the sender to the receiver. No acknowledgments or other messages are necessary after connection setup. This implies that the sender's stream authentication 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 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 client MUST know the dispersion (the maximum clock offset). TESLA supports two synchronization methods, direct and indirect synchronization. In direct synchronization, the receiver synchronizes its time directly with the data sender, in indirect synchronization both the sender and the receiver synchronize their time with a common time synchroniza­ tion server. If the latter method is used, we assume that secure time synchronization servers exist in the network, for example NTP servers [18]. Finally, the clock of the receiver MUST have negligible drift while receiving information from the server and MUST be secure against alteration by an attacker. 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. Perrig, Canetti, Briscoe, Tygar, Song [Page 4] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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 An Overview of TESLA 5.1 Threat Model and Security Guarantee We design our schemes 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. 5.2 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 in one network packet. 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 many or zero mes­ sages. Before sending the first message, the sender determines the sending duration (can be infinite), the interval duration, and the number N of keys of the key chain. This key chain is analogous to the one-way Perrig, Canetti, Briscoe, Tygar, Song [Page 5] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 chain introduced by Lamport [19], and the S/KEY authentication scheme [20]. The sender then picks the last key K_N of the key chain ran­ domly and precomputes 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 follows: 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 interval 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 to derive the key which is used to compute the MAC of messages in each interval (we will explain the algorithm in detail later). 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 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. TESLA is bootstrapped through an initially authenticated data packet. This authentication is achieved with a digital signature scheme, such as RSA [21], DSA [22], or PGP [23]. 5.3 Bootstrapping a new Receiver TESLA requires loosely synchronized clocks between the sender and the receivers. Furthermore, TESLA requires an initial packet that is authenticated with another message authentication scheme. We present two options for synchronizing the time. Either the receiver directly synchronizes its time with the sender (direct Perrig, Canetti, Briscoe, Tygar, Song [Page 6] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 synchronization), or both the sender and receiver synchronize their time with a third entity, a time server (indirect synchronization), for example using NTP [18]. Both schemes (including their packet for­ mat) are described in appendix A. 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. 5.4 TESLA Stream Authentication Protocol - Sender Tasks This section describes the TESLA protocol from a sender perspective. The next section explains the receiver's tasks. Figure 2 shows the packet format for a message M_i. To enable inter­ action with other protocols, we want to keep maximal flexibility. A first difficulty is how to handle the length of the authentication data. Some headers require a length and type field inside the authen­ tication information (e.g. ALC draft [17]), others set up the authen­ tication at connection setup and use the pre-determined authentica­ tion information for the entire session (e.g. ESP [24] or MESP [15]). The requirement for a pre-determined fixed authentication data size results in an inefficiency, because the common case in TESLA is that the authentication data includes the MAC only, and no disclosed key, and no commitments to new key chains (which is very infrequent).1 Hence, the authentication data is on the order of 10 bytes in the common case, and on the order of 20 bytes when disclosing the key. By fixing the authentication data length, 10 bytes will be wasted in most packets, because of the allocated space for the disclosed key. To remain compatible with both the MESP header [15] and the ALC draft [17], we include the length and type fields as optional fields for maximum flexibility and adaptability. The fields have the following semantics: · Authentication data length field: 8 bits This field is OPTIONAL. Some header formats require the length to be part of the authentication data. This field determines the length in bytes. ----------- 1 We assume that the keys are disclosed in a small number of packets and that one key chain is active over a long time period. Perrig, Canetti, Briscoe, Tygar, Song [Page 7] Internet Draft draft-irtf-smug-tesla-00 27 July 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | [Length] | [Type] |D|C|L| Res | [Interval Id] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | [Packet Sequence Number] | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ | | ~ MAC(Ki, [NK | ] Payload) ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ [Disclosed Key] ~ | | ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ | | ~ [NK: Commitment to new key] ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ [Disclosed Key from previous chain] ~ | | ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Padding (0-3 bytes) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: TESLA packet format · Authentication type field: 8 bits This field is OPTIONAL. Included for compatibility with the ALC draft [17]. · 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. Perrig, Canetti, Briscoe, Tygar, Song [Page 8] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 · 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. · Reserved (Res): 5 bits · Interval Id: 0 or 8 bits The interval id is simply the last 8 bits of the interval number. This number is not really necessary, since in practice, packets arrive mostly in the sending order. This allows a receiver to estimate the current interval number and once the key is dis­ closed, the receiver can try out which interval the packet belongs to. By storing the arrival time of each packet, the secu­ rity condition limits the number of distinct potential intervals. · Packet Sequence Number: 0 or 16 bits The packet sequence number is to filter out duplicates. Since TESLA does not provide duplicate protection, the packet sequence number helps the TESLA implementation to filter out duplicate messages for the receiver. Another method to remove duplicates is to use the MAC of the message and remove messages that were sent in the same interval and have identical MAC's. · MAC: 80 bits The MAC has to be present in the packet. · Disclosed key: 0 or 80 bits 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. · Commitment to new key: 0 or 80 bits 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 section 6.4. · Disclosed key from previous chain: 0 or 80 bits 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 retrans­ mitted. See section 6.4 for details. Perrig, Canetti, Briscoe, Tygar, Song [Page 9] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 · Padding: 0-3 bytes Pads the authentication block to the next 4 byte boundary. We would like to point out that the key used in a specific interval remains secret for d future intervals. The key is then disclosed in a later interval. Figure 3 shows this graphically, where key K_j is disclosed in interval K_{j+d}, with d=2. However many messages are sent in each interval, the key which corre­ sponds to that interval is used to compute the MAC of all those mes­ sages. This allows the sender to send packets at any rate and to switch the sending rate dynamically. _____ _____ / \ / \ / \ \ / / \ \ / / \ \ V V \ \ --+------+------+------+------+---> t Ij Ij+1 Ij+2 Ij+3 Kj Kj+1 Kj+2 Kj+3 +----+ +----+ | P1 | | P2 | +----+ +----+ Figure 3: TESLA intervals and key disclosure 5.5 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, 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 P 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 Perrig, Canetti, Briscoe, Tygar, Song [Page 10] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 disclosed. 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 3 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 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 Perrig, Canetti, Briscoe, Tygar, Song [Page 11] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 verifying 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.6 Extension The previous scheme has a tradeoff in the choice of the key disclo­ sure period. 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. Conversely, a long time period will suit remote receivers, but the authentication time delay may be unaccept­ able 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 network access, we need to solve this tradeoff. Our approach is to use multiple authentication chains with different disclosure periods simultaneously. Each receiver can then use the chain with the minimal disclosure delay, sufficient to pre­ vent spurious drops which are caused if the security condition does not hold. The receiver verifies one security condition for each authentication chain C_i, and drops the packet if none of the conditions are satis­ fied. Assume that the sender uses n authentication chains, where the first chain has the smallest delay until the disclosure packet is sent, and the nth chain has the longest delay. Furthermore, assume that for the incoming packet P_j, the security conditions for chains C_v (v < m) are not satisfied, and the condition for chain C_m is satisfied. In this case, as long as the key disclosure packets for the chains C_v (v < m ) arrive, the receiver's confidence in the authenticity of packet P_j is increasing. As soon as the key disclo­ sure packet for a chain C_v (v >= m) arrives, the receiver is assured of the authenticity of the packet P_j. 5.7 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 Perrig, Canetti, Briscoe, Tygar, Song [Page 12] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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, because she could not recompute the cryptographically 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 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.4. 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. The problem remains on how to choose the disclosure delay. Perrig, Canetti, Briscoe, Tygar, Song [Page 13] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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 is d_t (maximum clock offset) and the propa­ gation delay is 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 propa­ gation delay D_d > d_t + d_p. 6.2 Choosing the interval duration 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 pseudo-random one-way function and a MAC function 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: Perrig, Canetti, Briscoe, Tygar, Song [Page 14] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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 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. 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 4 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 Perrig, Canetti, Briscoe, Tygar, Song [Page 15] Internet Draft draft-irtf-smug-tesla-00 27 July 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 4: Key chain change This section discusses implementation considerations for the receiver. 7.1 Time Synchronization, Stable Time Source, Security Condition 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 A, we propose two time synchronization schemes 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 Perrig, Canetti, Briscoe, Tygar, Song [Page 16] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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. 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 client would try to verify the disclosed key, it would need to perform a large number of pseudo- Perrig, Canetti, Briscoe, Tygar, Song [Page 17] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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. 8 Security Considerations This entire document is about Security Considerations. 9 Acknowledgments We would like to thank Mike Luby for his feedback and support. 10 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] B. Briscoe, "Flames: Fast, loss-tolerant authentication of multi­ cast streams," tech. rep., BT Research, 2000. http://www.labs.bt.com/people/briscorj/papers.html. Perrig, Canetti, Briscoe, Tygar, Song [Page 18] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 [10] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream authentication," in Selected Areas in Cryptography 2000 , (Waterloo, Canada), August 2000. [11] S. Cheung, "An efficient message authentication scheme for link state routing," in 13th Annual Computer Security Applications Confer­ ence , 1997. [12] 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. [13] Secure Multicast Group (SMuG). http://www.ipmulticast.com/com­ munity/smug/. [14] 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. [15] 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. [16] Reliable Multicast Transport (RMT). http://www.ietf.org/html.charters/rmt-charter.html. [17] 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. [18] D. L. Mills, "Network Time Protocol (Version 3) Specification, Implementation and Analysis." Internet Request for Comments, March 1992. RFC 1305. [19] L. Lamport, "Password authentication with insecure communica­ tion," Communications ACM , vol. 24, Nov. 1981. [20] N. Haller, "The S/KEY one-time password system," Request for Comments (Informational) 1760, Internet Engineering Task Force, Feb. 1995. [21] 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 19] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 [22] "Digital Signature Standard (DSS), Federal Register 56." FIPS PUB 186, Aug. 1991. [23] D. Atkins, W. Stallings, and P. Zimmermann, "PGP message exchange formats," Request for Comments (Informational) 1991, Inter­ net Engineering Task Force, Aug. 1996. [24] S. Kent and R. Atkinson, "IP encapsulating security payload (ESP)," Request for Comments (Proposed Standard) 2406, Internet Engi­ neering Task Force, Nov. 1998. [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. Bishop, "A Security Analysis of the NTP Protocol Version 2," in Sixth Annual Computer Security Applications Conference , November 1990. [29] R. Merkle, "Protocols for public key cryptosystems," in 1980 IEEE Symposium on Security and Privacy , 1980. A 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. A.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).2 In section 7.1 we ----------- 2 Many clock synchronization algorithms exist, for example the work of Mills on NTP [18], and its Perrig, Canetti, Briscoe, Tygar, Song [Page 20] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 describe a simple protocol and discuss scalability issues related to the initial synchronization. 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 5 shows the request information. 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 5: Time synchronization request packet format 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 · 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 ----------- security analysis [28]. Perrig, Canetti, Briscoe, Tygar, Song [Page 21] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 · The nonce N_r Figure 6 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. 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 [18]. This response packet needs to be authenticated with a digital signa­ ture scheme, such as RSA [21], DSA [22], or PGP [23]. We assume that Perrig, Canetti, Briscoe, Tygar, Song [Page 22] Internet Draft draft-irtf-smug-tesla-00 27 July 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 6: Direct synchronization packet format Perrig, Canetti, Briscoe, Tygar, Song [Page 23] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 a public-key infrastructure is in place (PKI). Since most public-key signature algorithms are computationally expensive3 , the signing of the response packet can become a performance bottleneck for the sender. 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 [29]. Figure 7 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 recon­ struct the entire tree. For the example in figure 7, 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 logarithmic in the number of receivers whose request arrived in the same time interval. Assum­ ing 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, 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 7: Hash tree over receiver nonces. Node H_{ab} = H(N_a, N_b). H_{ad} = H(H_{ab},H_{cd}). A.2 Indirect Synchronization ----------- 3 A 500 MHz Pentium III workstation can compute on the order of 100 RSA 1024-bit signatures per second. Perrig, Canetti, Briscoe, Tygar, Song [Page 24] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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 [18]. 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 current time at the sender · 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 · 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 8. 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 Perrig, Canetti, Briscoe, Tygar, Song [Page 25] Internet Draft draft-irtf-smug-tesla-00 27 July 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 8: Indirect synchronization packet format the security of the sender, since it can be configured not to receive any packets. B Author Contact Information Adrian Perrig SIMS - UC Berkeley / Digital Fountain Perrig, Canetti, Briscoe, Tygar, Song [Page 26] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 102 South Hall, 4600 Berkeley, CA 94720 perrig@cs.berkeley.edu Ran Canetti IBM Research 30 Saw Mill River Rd Hawthorne, NY 10532 (914) 784-7076 canetti@watson.ibm.com Bob Briscoe BT Research B54/74, BT Labs Martlesham Heath Ipswich, IP5 3RE England bob.briscoe@bt.com Doug Tygar SIMS - UC Berkeley 102 South Hall, 4600 Berkeley, CA 94720-4600 tygar@cs.berkeley.edu Dawn Song CS - UC Berkeley 387 Soda Hall, 1776 Berkeley, CA 94720-1776 dawnsong@cs.berkeley.edu C 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. Perrig, Canetti, Briscoe, Tygar, Song [Page 27] Internet Draft draft-irtf-smug-tesla-00 27 July 2000 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." Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . 2 2 Rationale . . . . . . . . . . . . . . . . . . . . . . . . 3 3 Functionality . . . . . . . . . . . . . . . . . . . . . . 3 3.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 4 4 Notation . . . . . . . . . . . . . . . . . . . . . . . . 5 5 An Overview of TESLA . . . . . . . . . . . . . . . . . . 5 5.1 Threat Model and Security Guarantee . . . . . . . . . . . 5 5.2 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.3 Bootstrapping a new Receiver . . . . . . . . . . . . . . 6 5.4 TESLA Stream Authentication Protocol - Sender Tasks . . . 7 5.5 Receiver Tasks . . . . . . . . . . . . . . . . . . . . . 10 5.6 Extension . . . . . . . . . . . . . . . . . . . . . . . . 12 5.7 Security Discussion . . . . . . . . . . . . . . . . . . . 12 6 Implementation Considerations for the Sender . . . . . . 13 6.1 Choosing the disclosure delay . . . . . . . . . . . . . . 13 6.2 Choosing the interval duration . . . . . . . . . . . . . 14 6.3 Selecting a pseudo-random one-way function and a MAC function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.4 Altering key chains on the fly . . . . . . . . . . . . . 15 7 Implementation Considerations for the Receiver . . . . . 15 7.1 Time Synchronization, Stable Time Source, Security Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 7.2 Reconstruction of the key chain . . . . . . . . . . . . . 17 7.3 Protecting against Denial-of-Service Attacks . . . . . . 17 8 Security Considerations . . . . . . . . . . . . . . . . . 18 9 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 18 10 Bibliography . . . . . . . . . . . . . . . . . . . . . . 18 A Time Synchronization Packet Format . . . . . . . . . . . 20 A.1 Direct Synchronization . . . . . . . . . . . . . . . . . 20 A.2 Indirect Synchronization . . . . . . . . . . . . . . . . 24 B Author Contact Information . . . . . . . . . . . . . . . 26 C Full Copyright Statement . . . . . . . . . . . . . . . . 27 Perrig, Canetti, Briscoe, Tygar, Song [Page 28]