diff options
Diffstat (limited to 'doc/rfc/rfc4082.txt')
| -rw-r--r-- | doc/rfc/rfc4082.txt | 1235 |
1 files changed, 1235 insertions, 0 deletions
diff --git a/doc/rfc/rfc4082.txt b/doc/rfc/rfc4082.txt new file mode 100644 index 0000000..555bef3 --- /dev/null +++ b/doc/rfc/rfc4082.txt @@ -0,0 +1,1235 @@ + + + + + + +Network Working Group A. Perrig +Request for Comments: 4082 D. Song +Category: Informational Carnegie Mellon University + R. Canetti + IBM + J. D. Tygar + University of California, Berkeley + B. Briscoe + BT + June 2005 + + + Timed Efficient Stream Loss-Tolerant Authentication (TESLA): + Multicast Source Authentication Transform Introduction + +Status of This Memo + + This memo provides information for the Internet community. It does + not specify an Internet standard of any kind. Distribution of this + memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (2005). + +Abstract + + This document introduces Timed Efficient Stream Loss-tolerant + Authentication (TESLA). TESLA allows all receivers to check the + integrity and authenticate the source of each packet in multicast or + broadcast data streams. TESLA requires no trust between receivers, + uses low-cost operations per packet at both sender and receiver, can + tolerate any level of loss without retransmissions, and requires no + per-receiver state at the sender. TESLA can protect receivers + against denial of service attacks in certain circumstances. Each + receiver must be loosely time-synchronized with the source in order + to verify messages, but otherwise receivers do not have to send any + messages. TESLA alone cannot support non-repudiation of the data + source to third parties. + + This informational document is intended to assist in writing + standardizable and secure specifications for protocols based on TESLA + in different contexts. + + + + + + + + +Perrig, et al. Informational [Page 1] + +RFC 4082 TESLA Introduction June 2005 + + +Table of Contents + + 1. Introduction ....................................................2 + 1.1. Notation ...................................................3 + 2. Functionality ...................................................4 + 2.1. Threat Model and Security Guarantee ........................5 + 2.2. Assumptions ................................................5 + 3. The Basic TESLA Protocol ........................................6 + 3.1. Protocol Sketch ............................................6 + 3.2. Sender Setup ...............................................7 + 3.3. Bootstrapping Receivers ....................................8 + 3.3.1. Time Synchronization ................................9 + 3.4. Broadcasting Authenticated Messages .......................10 + 3.5. Authentication at Receiver ................................11 + 3.6. Determining the Key Disclosure Delay ......................12 + 3.7. Denial of Service Protection ..............................13 + 3.7.1. Additional Group Authentication ....................14 + 3.7.2. Not Re-using Keys ..................................15 + 3.7.3. Sender Buffering ...................................17 + 3.8. Some Extensions ...........................................17 + 4. Layer Placement ................................................17 + 5. Security Considerations ........................................18 + 6. Acknowledgements ...............................................19 + 7. Informative References .........................................19 + +1. Introduction + + In multicast, a single packet can reach millions of receivers. + Unfortunately, this introduces the danger that an attacker can + potentially also reach millions of receivers with a malicious packet. + Through source authentication, receivers can ensure that a received + multicast packet originates from the correct source. In these + respects, a multicast is equivalent to a broadcast to a superset of + the multicast receivers. + + In unicast communication, we can achieve data authentication through + a simple mechanism: the sender and the receiver share a secret key to + compute a message authentication code (MAC) of all communicated data. + When a message with a correct MAC arrives, the receiver is assured + that the sender generated that message. Standard mechanisms achieve + unicast authentication this way; for example, TLS or IPsec [1,2]. + + Symmetric MAC authentication is not secure in a broadcast setting. + Consider a sender that broadcasts authentic data to mutually + mistrusting receivers. The symmetric MAC is not secure: every + receiver knows the MAC key and therefore could impersonate the sender + and forge messages to other receivers. Intuitively, we need an + asymmetric mechanism to achieve authenticated broadcast, such that + + + +Perrig, et al. Informational [Page 2] + +RFC 4082 TESLA Introduction June 2005 + + + every receiver can verify the authenticity of messages it receives, + without being able to generate authentic messages. Achieving this in + an efficient way is a challenging problem [3]. + + The standard approach to achieving such asymmetry for authentication + is to use asymmetric cryptography; e.g., a digital signature. + Digital signatures have the required asymmetric property: the sender + generates the signature with its private key, and all receivers can + verify the signature with the sender's public key, but a receiver + with the public key alone cannot generate a digital signature for a + new message. A digital signature provides non-repudiation, a + stronger property than authentication. However, digital signatures + have a high cost: they have a high computation overhead for both the + sender and the receiver, and most signatures also have a high- + bandwidth overhead. Since we assume broadcast settings for which the + sender does not retransmit lost packets, and the receiver still wants + to authenticate each packet it receives immediately, we would need to + attach a digital signature to each message. Because of the high + overhead of asymmetric cryptography, this approach would restrict us + to low-rate streams, and to senders and receivers with powerful + workstations. We can try to amortize one digital signature over + multiple messages. However, this approach is still expensive in + contrast to symmetric cryptography, since symmetric cryptography is + in general 3 to 5 orders of magnitude more efficient than asymmetric + cryptography. In addition, the straight-forward amortization of one + digital signature over multiple packets requires reliability, as the + receiver needs to receive all packets to verify the signature. A + number of schemes that follow this approach are [4,5,6,7]. See [8] + for more details. + + This document presents the Timed Efficient Stream Loss-tolerant + Authentication protocol (TESLA). TESLA uses mainly symmetric + cryptography, and uses time-delayed key disclosure to achieve the + required asymmetry property. However, TESLA requires loosely + synchronized clocks between the sender and the receivers. See more + details in Section 3.3.1. Schemes that follow a similar approach to + TESLA are [9,10,11]. + +1.1. Notation + + To denote the subscript or an index of a variable, we use the + underscore between the variable name and the index; e.g., the key K + with index i is K_i, and the key K with index i+d is K_{i+d}. To + write a superscript, we use the caret; e.g., function F with the + argument x executed i times is F^i(x). + + + + + + +Perrig, et al. Informational [Page 3] + +RFC 4082 TESLA Introduction June 2005 + + +2. Functionality + + TESLA provides delayed per-packet data authentication and integrity + checking. The key idea to providing both efficiency and security is + a delayed disclosure of keys. The delayed key disclosure results in + an authentication delay. In practice, the delay is on the order of + one RTT (round-trip-time). + + TESLA has the following properties: + + o Low computation overhead for generation and verification of + authentication information. + + o Low communication overhead. + + o Limited buffering required for the sender and the receiver, and + therefore timely authentication for each individual packet. + + o Strong robustness to packet loss. + + o Scales to a large number of receivers. + + o Protects receivers from denial of service attacks in certain + circumstances if configured appropriately. + + o Each receiver cannot verify message authenticity unless it is + loosely time-synchronized with the source, where synchronization + can take place at session setup. Once the session is in + progress, receivers need not send any messages or + acknowledgements. + + o Non-repudiation is not supported; each receiver can know that a + stream is from an authentic source, but cannot prove this to a + third party. + + TESLA can be used in the network layer, in the transport layer, or in + the application layer. Delayed authentication, however, requires + buffering of packets until authentication is completed. Certain + applications intolerant of delay may be willing to process packets in + parallel to being buffered while awaiting authentication, as long as + roll-back is possible if packets are later found to be + unauthenticated. For instance, an interactive video may play out + packets still awaiting authentication, but if they are later found to + be unauthenticated, it could stop further play-out and warn the + viewer that the last x msec were unauthenticated and should be + ignored. However, in the remainder of this document, for brevity, we + will assume that packets are not processed in parallel to buffering. + + + + +Perrig, et al. Informational [Page 4] + +RFC 4082 TESLA Introduction June 2005 + + +2.1. Threat Model and Security Guarantee + + We design TESLA to be secure against a powerful adversary with the + following capabilities: + + o Full control over the network. The adversary can eavesdrop, + capture, drop, re-send, delay, and alter packets. + + o Access to a fast network with negligible delay. + + o The adversary's computational resources may be very large, but + not unbounded. In particular, this means that the adversary can + perform efficient computations, such as computing a reasonable + number of pseudo-random function applications and MACs with + negligible delay. Nonetheless, the adversary cannot find the + key of a pseudo-random function (or distinguish it from a random + function) with non-negligible probability. + + The security property of TESLA guarantees that the receiver never + accepts M_i as an authentic message unless the sender really sent + M_i. A scheme that provides this guarantee is called a secure + broadcast authentication scheme. + + Because TESLA expects the receiver to buffer packets before + authentication, the receiver needs to protect itself from a potential + denial of service (DoS) attack due to a flood of bogus packets (see + Section 3.8). + +2.2. Assumptions + + TESLA makes the following assumptions in order to provide security: + + 1. The sender and the receiver must be loosely time-synchronized. + Specifically, each receiver must be able to compute an upper + bound on the lag of the receiver clock relative to the sender + clock. We denote this quantity with D_t. (That is, D_t = + sender time - receiver time). We note that an upper bound on + D_t can easily be obtained via a simple two-message exchange. + (Such an exchange can be piggybacked on any secure session + initiation protocol. Alternatively, standard protocols such + as NTP [15] can be used. + + 2. TESLA MUST be bootstrapped at session setup through a regular + data authentication system. One option is to use a digital + signature algorithm for this purpose, in which case the + receiver is required to have an authentic copy of either the + sender's public key certificate or a root key certificate in + + + + +Perrig, et al. Informational [Page 5] + +RFC 4082 TESLA Introduction June 2005 + + + case of a PKI (public-key infrastructure). Alternatively, + this initialization step can be done using any secure session + initiation protocol. + + 3. TESLA uses cryptographic MAC and PRF (pseudo-random + functions). These MUST be cryptographically secure. Further + details on the instantiation of the MAC and PRF are in Section + 3.4. + + We would like to emphasize that the security of TESLA does NOT rely + on any assumptions about network propagation delay. + +3. The Basic TESLA Protocol + + TESLA is described in several academic publications: A book on + broadcast security [12], a journal paper [13], and two conference + papers [7,14]. Please refer to these publications for in-depth + proofs of security, experimental results, etc. + + We first outline the main ideas behind TESLA. + +3.1. Protocol Sketch + + As we argue in the introduction, broadcast authentication requires a + source of asymmetry. TESLA uses time for asymmetry. We first make + sure that the sender and receivers are loosely time-synchronized as + described above. Next, the sender forms a one-way chain of keys, in + which each key in the chain is associated with a time interval (say, + a second). Here is the basic approach: + + o The sender attaches a MAC to each packet. The MAC is computed + over the contents of the packet. For each packet, the sender + uses the current key from the one-way chain as a cryptographic + key to compute the MAC. + + o The sender discloses a key from the one-way chain after some + pre-defined time delay (e.g., the key used in time interval i is + disclosed at time interval i+3). + + o Each receiver receives the packet. Each receiver knows the + schedule for disclosing keys and, since it has an upper bound on + the local time at the sender, it can check that the key used to + compute the MAC was not yet disclosed by the sender. If it was + not, then the receiver buffers the packet. Otherwise the packet + is dropped due to inability to authenticate. Note that we do + not know for sure whether a "late packet" is a bogus one or + + + + + +Perrig, et al. Informational [Page 6] + +RFC 4082 TESLA Introduction June 2005 + + + simply a delayed packet. We drop the packet because we are + unable to authenticate it. (Of course, an implementation may + choose not to drop packets and to use them unauthenticated.) + + o Each receiver checks that the disclosed key belongs to the + hash-chain (by checking against previously released keys in the + chain) and then checks the correctness of the MAC. If the MAC + is correct, the receiver accepts the packet. + + Note that one-way chains have the property that if intermediate + values of the one-way chain are lost, they can be recomputed using + subsequent values in the chain. Even if some key disclosures are + lost, a receiver can recover the corresponding keys and check the + correctness of earlier packets. + + We now describe the stages of the basic TESLA protocol in this order: + sender setup, receiver bootstrap, sender transmission of + authenticated broadcast messages, and receiver authentication of + broadcast messages. + +3.2. Sender Setup + + The sender divides the time into uniform intervals of duration T_int. + The sender assigns one key from the one-way chain to each time + interval in sequence. + + The sender determines the length N of the one-way chain K_0, + K_1, ..., K_N, and this length limits the maximum transmission + duration before a new one-way chain must be created. The sender + picks a random value for K_N. Using a pseudo-random function (PRF), + f, the sender constructs the one-way function F: F(k) = f_k(0). The + rest of the chain is computed recursively using K_i = F(K_{i+1}). + Note that this gives us K_i = F^{N-i}(K_N), so the receiver can + compute any value in the key chain from K_N, even if it does not have + intermediate values. The key K_i will be used to authenticate + packets sent in time interval i. + + Jakobsson [20] and Coppersmith and Jakobsson [21] present a storage- + and computation-efficient mechanism for one-way chains. For a chain + of length N, storage is about log(N) elements, and the computation + overhead to reconstruct each element is also about log(N). + + The sender determines the duration of a time interval, T_int, and the + key disclosure delay, d. (T_int is measured in time units, say + milliseconds, and d is measured in number of time intervals. That + is, a key that is used for time interval i will be disclosed in time + interval i+d.) It is stressed that the scheme remains secure for any + values of T_int and d>0. Still, correct choice of T_int and d is + + + +Perrig, et al. Informational [Page 7] + +RFC 4082 TESLA Introduction June 2005 + + + crucial for the usability of the scheme. The choice is influenced by + the estimated network delay, the length of the transmission, and the + tolerable delay at the receiver. A T_int that is too short will + cause the keys to run out too soon. A T_int that is too long will + cause excessive delay in authentication for some of the packets + (those that were sent at the beginning of a time period). A delay d + that is too short will cause too many packets to be unverifiable by + the receiver. A delay d that is too long will cause excessive delay + in authentication. + + The sender estimates a reasonable upper bound on the network delay + between the sender and any receiver as m milliseconds. This includes + any delay expected in the stack (see Section 4, on layer placement). + If the sender expects to send a packet every n milliseconds, then a + reasonable value for T_int is max(n,m). Based on T_int, a rule of + thumb for determining the key disclosure delay, d, is given in + Section 3.6. + + The above value for T_int is neither an upper or a lower bound; it is + merely the value that reduces key change processing to a minimum + without causing authentication delay to be higher than necessary. If + the application can tolerate higher authentication delay, then T_int + can be made appropriately larger. Also, if m (or n) increases during + the session, perhaps due to congestion or a late joiner on a high + delay path, T_int need not be revised. + + Finally, the sender needs to allow each receiver to synchronize its + time with the sender. See more details on how this can be done in + Section 3.3.1. (It is stressed that estimating the network delay is + a separate task from the time synchronization between the sender and + the receivers.) + +3.3. Bootstrapping Receivers + + Before a receiver can authenticate messages with TESLA, it needs to + have the following: + + o An upper bound, D_t, on the lag of its own clock with respect to + the clock of the sender. (That is, if the local time reading is + t, the current time reading at the sender is at most t+D_t.). + + o One authenticated key of the one-way key chain. (Typically, + this will be the last key in the chain; i.e., K_0. This key + will be signed by the sender, and all receivers will verify the + signature with the public key of the signer.) + + + + + + +Perrig, et al. Informational [Page 8] + +RFC 4082 TESLA Introduction June 2005 + + + o The disclosure schedule of the following keys: + + - T_int, the interval duration. + - T_0, the start time of interval 0. + - N, the length of the one-way key chain. + - d, the key disclosure delay d (in number of intervals). + + The receiver can perform the time synchronization and get the + authenticated TESLA parameters in a two-round message exchange, as + described below. We stress again that time synchronization can be + performed as part of the registration protocol between any receiver + (including late joiners) and the sender, or between any receiver and + a group controller. + +3.3.1. Time Synchronization + + Various approaches exist for time synchronization [15,16,17,18]. + TESLA only requires the receiver to know an upper bound on the delay + of its local clock with respect to the sender's clock, so a simple + algorithm is sufficient. TESLA can be used with direct, indirect, + and delayed synchronization as three default options. The specific + synchronization method will be part of each instantiation of TESLA. + + For completeness, we sketch a simple method for direct + synchronization between the sender and a receiver: + + o The receiver sends a (sync t_r) message to the sender and + records its local time, t_r, at the moment of sending. + + o Upon receipt of the (sync t_r) message, the sender records its + local time, t_s, and sends (synch, t_r,t_s) to the receiver. + + o Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s - + t_r + S, where S is an estimated bound on the clock drift + throughout the duration of the session. + + Note: + + o Assuming that the messages are authentic (i.e., the message + received by the receiver was actually sent by the sender), and + assuming that the clock drift is at most S, then at any point + throughout the session T_s < T_r + D_t, where T_s is the current + time at the sender and T_r is the current time at the receiver. + + o The exchange of sync messages needs to be authenticated. This + can be done in a number of ways; for instance, with a secure NTP + protocol or in conjunction with a session set-up protocol. + + + + +Perrig, et al. Informational [Page 9] + +RFC 4082 TESLA Introduction June 2005 + + + For indirect time synchronization (e.g., synchronization via a group + controller), the sender and the controller engage in a protocol for + finding the value D^0_t between them. Next, each receiver, R, + interacts with the group controller (say, when registering to the + group) and finds the value D^R_t between the group controller and R. + The overall value of D_t within R is set to the sum D_t = D^R_t + + D^0_t. + +3.4. Broadcasting Authenticated Messages + + Each key in the one-way key chain corresponds to a time interval. + Every time a sender broadcasts a message, it appends a MAC to the + message, using the key corresponding to the current time interval. + The key remains secret for the next d-1 intervals, so messages that a + sender broadcasts in interval j effectively disclose key K_j-d. We + call d the key disclosure delay. + + We do not want to use the same key multiple times in different + cryptographic operations; that is, using key K_j to derive the + previous key of the one-way key chain K_{j-1}, and using the same key + K_j as the key to compute the MACs in time interval j may potentially + lead to a cryptographic weakness. Using a pseudo-random function + (PRF), f', we construct the one-way function F': F'(k) = f'_k(1). We + use F' to derive the key to compute the MAC of messages in each + interval. The sender derives the MAC key as follows: K'_i = F'(K_i). + Figure 1 depicts the one-way key chain construction and MAC key + derivation. To broadcast message M_j in interval i the sender + constructs the packet + + P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}} + + where || denotes concatenation. + + + F(K_i) F(K_{i+1}) F(K_{i+2}) + K_{i-1} <------- K_i <------- K_{i+1} <------- K_{i+2} + + | | | + | F'(K_{i-1}) | F'(K_i) | F'(K_{i+1}) + | | | + V V V + + K'_{i-1} K'_i K'_{i+1} + + Figure 1: At the top of the figure, we see the one-way key chain + (derived using the one-way function F), and the derived MAC keys + (derived using the one-way function F'). + + + + +Perrig, et al. Informational [Page 10] + +RFC 4082 TESLA Introduction June 2005 + + +3.5. Authentication at Receiver + + Once a sender discloses a key, we must assume that all parties might + have access to that key. An adversary could create a bogus message + and forge a MAC using the disclosed key. So whenever a packet + arrives, the receiver must verify that the MAC is based on a safe + key; a safe key is one that is still secret (known only by the + sender). We define a safe packet or safe message as one with a MAC + that is computed with a safe key. + + If a packet proves safe, it will be buffered, only to be released + when its own key, disclosed in a later packet, proves its + authenticity. Although a newly arriving packet cannot immediately be + authenticated, it may disclose a new key so that earlier, buffered + packets can be authenticated. Any newly disclosed key must be + checked to determine whether it is genuine; then authentication of + buffered packets that have been waiting for it can proceed. + + We now describe TESLA authentication at the receiver with more + detail, listing all of these steps in the exact order they should be + carried out: + + 1. Safe packet test: When the receiver receives packet P_j, which + carries an interval index i, and a disclosed key K_{i-d}, it + first records local time T at which the packet arrived. The + receiver then computes an upper bound t_j on the sender's + clock at the time when the packet arrived: t_j = T + D_t. To + test whether the packet is safe, the receiver then computes + the highest interval x the sender could possibly be in; namely + x = floor((t_j - T_0) / T_int). The receiver verifies that x + < i + d (where i is the interval index), which implies that + the sender is not yet in the interval during which it + discloses the key K_i. + + Even if the packet is safe, the receiver cannot yet verify the + authenticity of this packet sent in interval i without key + K_i, which will be disclosed later. Instead, it adds the + triplet ( i, M_j, MAC( K'_i, M_j) ) to a buffer and verifies + the authenticity after it learns K'_i. + + If the packet is unsafe, then the receiver considers the + packet unauthenticated. It should discard unsafe packets, + but, at its own risk it may choose to use them unverified. + + 2. New key index test: Next the receiver checks whether a key K_v + has already been disclosed with the same index v as the + current disclosed key K_{i-d}, or with a later one; that is, + with v >= i-d. + + + +Perrig, et al. Informational [Page 11] + +RFC 4082 TESLA Introduction June 2005 + + + 3. Key verification test: If the disclosed key index is new, the + receiver checks the legitimacy of K_{i-d} by verifying, for + some earlier disclosed key K_v (v<i-d), that K_v = F^{i-d- + v}(K_{i-d}). + + If key verification fails, the newly arrived packet P_j should + be discarded. + + 4. Message verification tests: If the disclosed key is + legitimate, the receiver then verifies the authenticity of any + earlier safe, buffered packets of interval i-d. To + authenticate one of the buffered packets P_h containing + message M_h protected with a MAC that used key index i-d, the + receiver will compute K'_{i-d} = F'(K_{i-d}) from which it can + compute MAC( K'_{i-d}, M_h). + + If this MAC equals the MAC stored in the buffer, the packet is + authenticated and can be released from the buffer. If the + MACs do not agree, the buffered packet P_h should be + discarded. + + The receiver continues to verify and release (or not) any + remaining buffered packets that depend on the newly disclosed + key K_{i-d}. + + Using a disclosed key, we can calculate all previous disclosed keys, + so even if packets are lost, we will still be able to verify + buffered, safe packets from earlier time intervals. Thus, if i-d- + v>1, the receiver can also verify the authenticity of the stored + packets of intervals v+1 ... i-d-1. + +3.6. Determining the Key Disclosure Delay + + An important TESLA parameter is the key disclosure delay d. Although + the choice of the disclosure delay does not affect the security of + the system, it is an important performance factor. A short + disclosure delay will cause packets to lose their safety property, so + receivers will not be able to authenticate them; but a long + disclosure delay leads to a long authentication delay for receivers. + We recommend determining the disclosure delay as follows: In direct + time synchronization, let the RTT, 2m, be a reasonable upper bound on + the round trip time between the sender and any receiver including + worst-case congestion delay and worst-case buffering delay in host + stacks. Then choose d = ceil( 2m / T_int) + 1. Note that rounding + up the quotient ensures that d >= 2. Also note that a disclosure + delay of one time interval (d=1) does not work. Consider packets + sent close to the boundary of the time interval: After the network + propagation delay and the receiver time synchronization error, a + + + +Perrig, et al. Informational [Page 12] + +RFC 4082 TESLA Introduction June 2005 + + + receiver will not be able to authenticate the packet, because the + sender will already be in the next time interval when it discloses + the corresponding key. + + Measuring the delay to each receiver before determining m will still + not adequately predict the upper bound on delay to late joiners, or + where congestion delay rises later in the session. It may be + adequate to use a hard-coded historic estimate of worst-case delay + (e.g., round trip delays to any host on the intra-planetary Internet + rarely exceed 500msec if routing remains stable). + + We stress that the security of TESLA does not rely on any assumptions + about network propagation delay: If the delay is longer than + expected, then authentic packets may be considered unauthenticated. + Still, no inauthentic packet will be accepted as authentic. + +3.7. Denial of Service Protection + + Because TESLA authentication is delayed, receivers seem vulnerable to + flooding attacks that cause them to buffer excess packets, even + though they may eventually prove to be inauthentic. When TESLA is + deployed in an environment with a threat of flooding attacks, the + receiver can take a number of extra precautions. + + First, we list simple DoS mitigation precautions that can and should + be taken by any receiver independently of others, thus requiring no + changes to the protocol or sender behaviour. We precisely specify + where these extra steps interleave with the receiver authentication + steps already given in Section 3.5. + + o Session validity test: Before the safe packet test (Step 1), + check that arriving packets have a valid source IP address and + port number for the session, that they do not replay a message + already received in the session, and that they are not + significantly larger than the packet sizes expected in the + session. + + o Reasonable misordering test: Before the key verification test + (Step 3), check whether the disclosed key index i-d of the + arriving packet is within g of the previous highest disclosed + key index v; thus, for example, i-d-v <= g. g sets the + threshold beyond which an out-of-order key index is assumed to + be malicious rather than just misordered. Without this test, an + attacker could exploit the iterated test in Step 3 to make + receivers consume inordinate CPU time checking along the hash + chain for what appear to be extremely misordered packets. + + + + + +Perrig, et al. Informational [Page 13] + +RFC 4082 TESLA Introduction June 2005 + + + Each receiver can independently adapt g to prevailing attack + conditions; for instance, by using the following algorithm. + Initially, g should be set to g_max (say, 16). But whenever an + arriving packet fails the reasonable misordering test above or + the key verification test (Step 3), g should be dropped to g_min + (>0 and typically 1). At each successful key verification (Step + 3), g should be incremented by 1 unless it is already g_max. + These precautions will guarantee that sustained attack packets + cannot cause the receiver to execute more than an average of + g_min hashes each, unless they are paced against genuine + packets. In the latter case, attacks are limited to + g_max/(g_max-g_min) hashes per each genuine packet. + + When choosing g_max and g_min, note that they limit the average + gap in a packet sequence to g.max(n,m)/n packets (see Section + 3.2 for definitions of n and m). So with g=1, m=100msec RTT, + and n=4msec inter-packet period, reordering would be limited to + gaps of 25 packets on average. Bigger naturally occurring gaps + would have to be written off as if they were losses. + + Stronger DoS protection requires that both senders and receivers + arrange additional constraints on the protocol. Below, we outline + three alternative extensions to basic TESLA; the first adding group + authentication, the second not re-using keys during a time interval, + and the third moving buffering to the sender. + + It is important to understand the applicability of each scheme, as + the first two schemes use slightly more (but bounded) resources in + order to prevent attackers from consuming unbounded resources. + Adding group authentication requires larger per-packet overhead. + Never re-using a key requires both ends to process two hashes per + packet (rather than per time interval), and the sender must store or + re-generate a longer hash chain. The merits of each scheme, + summarised after each is described below, must be weighed against + these additional costs. + +3.7.1. Additional Group Authentication + + This scheme simply involves addition of a group MAC to every packet. + That is, a shared key K_g common to the whole group is communicated + as an additional step during receiver bootstrap (Section 3.3). Then, + during broadcast of message M_j (Section 3.4), the sender computes + the group MAC of each packet MAC(K_g, P_j), which it appends to the + packet header. Note that the group MAC covers the whole packet P_j; + that is, the concatenation of the message M_j and the additional + TESLA authentication material, using the formula in Section 3.4. + + + + + +Perrig, et al. Informational [Page 14] + +RFC 4082 TESLA Introduction June 2005 + + + Immediately upon packet arrival, each receiver can check that each + packet came from a group member, by recomputing and comparing the + group MAC. + + Note that TESLA source authentication is only necessary when other + group members cannot be trusted to refrain from spoofing the source; + otherwise, simpler group authentication would be sufficient. + Therefore, additional group authentication will only make sense in + scenarios where other group members are trusted to refrain from + flooding the group, but where they are still not trusted to refrain + from spoofing the source. + +3.7.2. Not Re-using Keys + + In TESLA as described so far, each MAC key was used repeatedly for + all the packets sent in a time interval. If instead the sender were + to guarantee never to use a MAC key more than once, each disclosed + key could assume an additional purpose on top of authenticating a + previously buffered packet. Each key would also immediately show + each receiver that the sender of each arriving packet knew the next + key back along the hash chain, which is now only disclosed once, + similar to S/KEY [22]. Therefore a reasonable receiver strategy + would be to discard any arriving packets that disclosed a key seen + already. The fill rate of the receiver's buffer would then be + clocked by each packet revealed by the genuine sender, preventing + memory flooding attacks. + + An attacker with control of a network element or of a faster bypass + network could intercept messages and overtake or replace them with + different messages but with the same keys. However, as long as + packets are only buffered if they also pass the delay safety test, + these bogus packets will fail TESLA verification after the disclosure + delay. Admittedly, receivers could be fooled into discarding genuine + messages that had been overtaken by bogus ones. But it is hard to + overtake messages without compromising a network element, and any + attacker that can compromise a network element can discard genuine + messages anyway. We will now describe this scheme in more detail. + + For the sender, the scheme is hardly different from TESLA. It merely + uses an interval duration short enough to ensure a new key back along + the hash chain for each packet. So the rule of thumb given in + Section 3.2 for an efficient re-keying interval T_int no longer + applies. Instead, T_int is simply n, the inter-arrival time between + packets in milliseconds. The rule of thumb for calculating d, the + key disclosure delay, remains unchanged from that given in Section + 3.6. + + + + + +Perrig, et al. Informational [Page 15] + +RFC 4082 TESLA Introduction June 2005 + + + If the packet rate is likely to vary, for safety n should be taken as + the minimum inter-departure time between any two packets. (In fact, + n need not be so strict; it can be the minimum average packet inter- + departure time over any burst of d packets expected throughout the + session.) + + Note that if the packet rate slows down, whenever no packets are sent + in a key change interval, the key index must increment along the hash + chain once for each missed interval. (During a burst, if the less + strict definition of n above has been used, packets may need to + depart before their key change interval. The sender can safely + continue changing the key for each packet, using keys from future key + intervals, because if n has been chosen as defined above, such bursts + will never sustain long enough to cause the associated key to be + disclosed in a period less than the disclosure delay later.) + + To be absolutely clear, the precise guarantees that the sender keeps + to by following the above guidance are: + + o not to re-use a MAC key, + + o not to use a MAC key K_i after its time interval i, and + + o not to disclose key K_i sooner than the disclosure delay d * + T_int following the packet it protects. + + Sender setup, receiver bootstrapping, and broadcasting authenticated + messages are otherwise all identical to the descriptions in Sections + 3.2, 3.3, and 3.4, respectively. However, the following step must be + added to the receiver authentication steps in Section 3.5: + + o After Step 2, if a packet arrives carrying a key index i-d that + has already been received, it should not be buffered. + + This simple scheme would suffice against DoS, were it not for the + fact that a network sometimes misorders packets without being + compromised. Even without control of a network element, an attacker + can opportunistically exploit such openings to fool a receiver into + buffering a bogus packet and discarding a later genuine one. A + receiver can choose to set aside a fixed size cache and can manage it + to minimise the chances of discarding a genuine packet. However, + given such vulnerabilities are rare and unpredictable, it is simpler + to count these events as additions to the network loss rate. As + always, TESLA authentication will still uncover any bogus packets + after the disclosure delay. + + To summarise, avoiding re-using keys has the following properties, + even under extreme flooding attacks: + + + +Perrig, et al. Informational [Page 16] + +RFC 4082 TESLA Introduction June 2005 + + + o After delayed TESLA authentication, packets arriving within the + disclosure delay will always be identified as authentic if they + are and as inauthentic if they are not authentic. + + o The fill rate of the receiver's buffer is clocked by each packet + revealed by the genuine sender, preventing memory flooding + attacks. + + o An attacker with control of a network element can cause any loss + rate it chooses (but that's always true anyway). + + o Where attackers do not have control of any network elements, the + effective loss rate is bounded by the sum of the network's + actual loss rate and its re-ordering rate. + +3.7.3. Sender Buffering + + Buffering of packets can be moved to the sender side; then receivers + can authenticate packets immediately upon receipt. This method is + described in [14]. + +3.8. Some Extensions + + Let us mention two salient extensions of the basic TESLA scheme. A + first extension allows having multiple TESLA authentication chains + for a single stream, where each chain uses a different delay for + disclosing the keys. This extension is typically used to deal with + heterogeneous network delays within a single multicast transmission. + A second extension allows having most of the buffering of packets at + the sender side (rather than at the receiver side). Both extensions + are described in [14]. + + TESLA's requirement that a key be received in a later packet for + authentication prevents a receiver from authenticating the last part + of a message. Thus, to enable authentication of the last part of a + message or of the last message before a transmission suspension, the + sender needs to send an empty message with the key. + +4. Layer Placement + + TESLA authentication can be performed at any layer in the networking + stack. Three natural places are the network, transport, or + application layer. We list some considerations regarding the choice + of layer: + + o Performing TESLA in the network layer has the advantage that the + transport or application layer only receives authenticated data, + potentially aiding a reliability protocol and mitigating denial + + + +Perrig, et al. Informational [Page 17] + +RFC 4082 TESLA Introduction June 2005 + + + of service attacks. (Indeed, reliable multicast tools based on + forward error correction are highly susceptible to denial of + service due to bogus packets.) + + o Performing TESLA in either the transport or the application + layer has the advantage that the network layer remains + unchanged, but it has the potential drawback that packets are + obtained by the application layer only after being processed by + the transport layer. Consequently, if buffering is used in the + transport, then this may introduce additional and unpredictable + delays on top of the unavoidable network delays. + + o Note that because TESLA relies upon timing of packets, deploying + TESLA on top of a protocol or layer that aggressively buffers + packets and hides the true packet arrival time will + significantly reduce TESLA's performance. + +5. Security Considerations + + See the academic publications on TESLA [7,13,19] for several security + analyses. Regarding the security of implementations, by far the most + delicate point is the verification of the timing conditions. Care + should be taken to make sure that (a) the value bound D_t on the + clock skew is calculated according to the spec at session setup and + that (b) the receiver records the arrival time of the packet as soon + as possible after the packet's arrival, and computes the safety + condition correctly. + + It should be noted that a change to the key disclosure schedule for a + message stream should never be declared within the message stream + itself. This would introduce a vulnerability, because a receiver + that did not receive the notification of the change would still + believe in the old key disclosure schedule. + + Finally, in common with all authentication schemes, if verification + is located separately from the ultimate destination application + (e.g., an IPSec tunnel end point), a trusted channel must be present + between verification and the application. For instance, the + interface between the verifier and the application might simply + assume that packets received by the application must have been + verified by the verifier (because otherwise they would have been + dropped). The application is then vulnerable to reception of packets + that have managed to bypass the verifier. + + + + + + + + +Perrig, et al. Informational [Page 18] + +RFC 4082 TESLA Introduction June 2005 + + +6. Acknowledgements + + We would like to thank the following for their feedback and support: + Mike Luby, Mark Baugher, Mats Naslund, Dave McGrew, Ross Finlayson, + Sylvie Laniepce, Lakshminath Dondeti, Russ Housley, and the IESG + reviewers. + +7. Informative References + + [1] Dierks, T. and C. Allen, "The TLS Protocol Version 1.0", RFC + 2246, January 1999. + + [2] IPsec, "IP Security Protocol, IETF working group" + http://www.ietf.org/html.charters/OLD/ipsec-charter.html. + + [3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for + multicast message authentication," in Advances in Cryptology -- + EUROCRYPT 2001 (B. Pfitzmann, ed.), Vol. 2045 of Lecture Notes + in Computer Science, (Innsbruck, Austria), p. 434-450, + Springer-Verlag, Berlin Germany, 2001. + + [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 + multicast packet authentication", 6th ACM Conference on Computer + and Communications Security , November 1999. + + [6] C. K. Wong and S. S. Lam, "Digital signatures for flows and + multicasts," in Proc. IEEE ICNP `98, 1998. + + [7] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient + authentication and signing of multicast streams over lossy + channels", IEEE Symposium on Security and Privacy, May 2000. + + [8] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. + Pinkas, "Multicast security: A taxonomy and some efficient + constructions", Infocom '99, 1999. + + [9] S. Cheung, "An efficient message authentication scheme for link + state routing", 13th Annual Computer Security Applications + Conference, 1997. + + [10] 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, et al. Informational [Page 19] + +RFC 4082 TESLA Introduction June 2005 + + + [11] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single + source authentication on the mbone", ICME 2000, August 2000. A + talk containing this work was given at IBM Watson, August 1998. + + [12] A. Perrig and J. D. Tygar, Secure Broadcast Communication in + Wired and Wireless Networks Kluwer Academic Publishers, October + 2002. ISBN 0792376501. + + [13] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla + broadcast authentication protocol," RSA CryptoBytes, Volume 5, + No. 2 Summer/Fall 2002. + + [14] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and + secure source authentication for multicast", Network and + Distributed System Security Symposium, NDSS '01, p. 35-46, + February 2001. + + [15] Mills, D., "Network Time Protocol (Version 3) Specification, + Implementation and Analysis", RFC 1305, March 1992. + + [16] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of + clock synchronization", Fault-Tolerant Distributed Computing (B. + Simons and A. Spector, eds.), No. 448 in LNCS, p. 84-96, + Springer-Verlag, Berlin Germany, 1990. + + [17] D. Mills, "Improved algorithms for synchronizing computer + network clocks", Proceedings of the conference on Communications + architectures, protocols and applications, SIGCOMM 94, (London, + England), p. 317-327, 1994. + + [18] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the + presence of faults", J. ACM, Volume 32, No. 1, p. 52-78, 1985. + + [19] P. Broadfoot and G. Lowe, "Analysing a Stream Authentication + Protocol using Model Checking", Proceedings of the 7th European + Symposium on Research in Computer Security (ESORICS), 2002. + + [20] M. Jakobsson, "Fractal hash sequence representation and + traversal", Cryptology ePrint Archive, + http://eprint.iacr.org/2002/001/, January 2002. + + [21] D. Coppersmith and M. Jakobsson, "Almost optimal hash sequence + traversal", Proceedings of the Sixth International Financial + Cryptography Conference (FC '02), March 2002. + + [22] Haller, N., "The S/KEY One-Time Password System", RFC 1760, + February 1995. + + + + +Perrig, et al. Informational [Page 20] + +RFC 4082 TESLA Introduction June 2005 + + +Authors' Addresses + + Adrian Perrig + ECE Department + Carnegie Mellon University + Pittsburgh, PA 15218 + US + + EMail: perrig@cmu.edu + + + Ran Canetti + IBM Research + 30 Saw Mill River Rd + Hawthorne, NY 10532 + US + + EMail: canetti@watson.ibm.com + + + Dawn Song + ECE Department + Carnegie Mellon University + Pittsburgh, PA 15218 + US + + EMail: dawnsong@cmu.edu + + + J. D. Tygar + UC Berkeley - EECS & SIMS + 102 South Hall 4600 + Berkeley, CA 94720-4600 + US + + EMail: doug.tygar@gmail.com + + + Bob Briscoe + BT Research + B54/77, BT Labs + Martlesham Heath + Ipswich, IP5 3RE + UK + + EMail: bob.briscoe@bt.com + + + + + +Perrig, et al. Informational [Page 21] + +RFC 4082 TESLA Introduction June 2005 + + +Full Copyright Statement + + Copyright (C) The Internet Society (2005). + + This document is subject to the rights, licenses and restrictions + contained in BCP 78, and except as set forth therein, the authors + retain all their rights. + + This document and the information contained herein are provided on an + "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS + OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET + ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, + INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE + INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED + WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Intellectual Property + + The IETF takes no position regarding the validity or scope of any + Intellectual Property Rights or other rights that might be claimed to + pertain to the implementation or use of the technology described in + this document or the extent to which any license under such rights + might or might not be available; nor does it represent that it has + made any independent effort to identify any such rights. Information + on the procedures with respect to rights in RFC documents can be + found in BCP 78 and BCP 79. + + Copies of IPR disclosures made to the IETF Secretariat and any + assurances of licenses to be made available, or the result of an + attempt made to obtain a general license or permission for the use of + such proprietary rights by implementers or users of this + specification can be obtained from the IETF on-line IPR repository at + http://www.ietf.org/ipr. + + The IETF invites any interested party to bring to its attention any + copyrights, patents or patent applications, or other proprietary + rights that may cover technology that may be required to implement + this standard. Please address the information to the IETF at ietf- + ipr@ietf.org. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + +Perrig, et al. Informational [Page 22] + |