idnits 2.17.1 draft-ietf-msec-tesla-intro-03.txt: -(728): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(733): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == There are 2 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 6 longer pages, the longest (page 11) being 91 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 25 instances of too long lines in the document, the longest one being 5 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 227: '... 2. TESLA MUST be bootstrapped at...' RFC 2119 keyword, line 237: '... These MUST be cryptographical...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 451 has weird spacing: '...ure, we see ...' == Line 452 has weird spacing: '...derived using...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (August 2004) is 7194 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2246 (ref. '1') (Obsoleted by RFC 4346) -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' -- Possible downref: Non-RFC (?) normative reference: ref. '7' -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' -- Possible downref: Non-RFC (?) normative reference: ref. '12' -- Possible downref: Non-RFC (?) normative reference: ref. '13' -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' ** Obsolete normative reference: RFC 1305 (ref. '16') (Obsoleted by RFC 5905) -- Possible downref: Non-RFC (?) normative reference: ref. '17' -- Possible downref: Non-RFC (?) normative reference: ref. '18' -- Possible downref: Non-RFC (?) normative reference: ref. '19' -- Possible downref: Non-RFC (?) normative reference: ref. '20' -- Possible downref: Non-RFC (?) normative reference: ref. '21' -- Possible downref: Non-RFC (?) normative reference: ref. '22' Summary: 11 errors (**), 0 flaws (~~), 6 warnings (==), 22 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force IETF MSEC 3 Internet Draft Perrig, Canetti, Song, Tygar, Briscoe 4 draft-ietf-msec-tesla-intro-03.txt CMU / IBM / CMU / UC Berkeley / BT 5 August 2004 6 Expires: 1 February 2005 8 TESLA: Multicast Source Authentication Transform Introduction 10 STATUS OF THIS MEMO 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference material 23 or to cite them other than as "work in progress". 25 To view the list Internet-Draft Shadow Directories, see 26 http://www.ietf.org/shadow.html. 28 Abstract 30 Data authentication is an important component for many broadcast 31 applications, for example audio and video Internet broadcasts, or 32 data distribution by satellite. This document introduces TESLA, 33 short for Timed Efficient Stream Loss-tolerant Authentication, a 34 secure source authentication mechanism for multicast or broadcast 35 data streams. This document provides an algorithmic description of 36 TESLA for informational purposes, and in particular, is intended to 37 assist in writing standardizable and secure specifications for 38 protocols based on TESLA in different contexts. 40 The main deterrents so far for a data authentication mechanism for 41 multicast were the seemingly conflicting requirements: loss 42 tolerance, efficiency, and no per-receiver state at the sender. The 43 problem is particularly hard in settings with high packet loss 44 rates and where lost packets are not retransmitted, and where the 45 receivers want to authenticate each packet they do receive. 47 TESLA provides authentication of individual data packets, 48 regardless of loss rate. In addition, TESLA features low overhead 49 for both sender and receiver, and does not require per-receiver 50 state at the sender. TESLA is secure as long as the sender and 51 receiver are loosely time synchronized. 53 Table of Contents 55 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2 56 1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . 3 57 2 Functionality . . . . . . . . . . . . . . . . . . . . . . 4 58 2.1 Threat Model and Security Guarantee . . . . . . . . . . . 4 59 2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5 60 3 The Basic TESLA Protocol . . . . . . . . . . . . . . . . 5 61 3.1 Protocol sketch . . . . . . . . . . . . . . . . . . . . . 6 62 3.2 Sender Setup . . . . . . . . . . . . . . . . . . . . . . 7 63 3.3 Bootstrapping Receivers . . . . . . . . . . . . . . . . . 7 64 3.3.1 Time Synchronization. . . . . . . . . . . . . . . . . . . 8 65 3.4 Broadcasting Authenticated Messages . . . . . . . . . . . 8 66 3.5 Authentication at Receiver . . . . . . . . . . . . . . . 8 67 3.6 Determining the Key Disclosure Delay . . . . . . . . . . 9 68 3.7 An alternative delay description method . . . . . . . . . 10 69 3.8 Some extensions . . . . . . . . . . . . . . . . . . . . . 11 70 4 Layer placement . . . . . . . . . . . . . . . . . . . . . 11 71 5 Security considerations . . . . . . . . . . . . . . . . . 11 72 6 IP statement . . . . . . . . . . . . . . . . . . . . . . .12 73 7 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 12 74 8 References . . . . . . . . . . . . . . . . . . . . . . . 12 75 A Author Contact Information . . . . . . . . . . . . . . . 13 76 B Full Copyright Statement . . . . . . . . . . . . . . . . 14 78 1 Introduction 80 In multicast, a single packet can reach millions of receivers. This 81 unfortunately also introduces the danger that an attacker can 82 potentially also reach millions of receivers with a malicious 83 packet. Through source authentication, receivers can ensure that a 84 received multicast packet originates from the correct source. 86 In unicast communication, we can achieve data authentication 87 through a simple mechanism: the sender and the receiver share a 88 secret key to compute a message authentication code (MAC) of all 89 communicated data. When a message with a correct MAC arrives, the 90 receiver is assured that the sender generated that message. 91 Standard mechanisms achieve unicast authentication this way, for 92 example TLS or IPsec [1,2]. 94 The symmetric MAC authentication is not secure in a broadcast 95 setting. Consider a sender that broadcasts authentic data to mutually 96 untrusting receivers. The symmetric MAC is not secure: every receiver 97 knows the MAC key, and hence could impersonate the sender and forge 98 messages to other receivers. Intuitively, we need an asymmetric 99 mechanism to achieve authenticated broadcast, such that every receiver 100 can verify the authenticity of messages it receives, without being 101 able to generate authentic messages. Achieving this in an efficient 102 way is a challenging problem [3]. 104 The standard approach to achieve such asymmetry for authentication 105 is to use asymmetric cryptography, e.g., a digital signature. 106 Digital signatures have the required asymmetric property: the 107 sender generates the signature with its private key, and all 108 receivers can verify the signature with the sender's public key, 109 but a receiver with the public key alone cannot generate a digital 110 signature for a new message. A digital signature provides 111 non-repudiation, a stronger property than authentication. However, 112 digital signatures have a high cost: they have a high computation 113 overhead for both the sender and the receiver, and most signatures 114 also have a high bandwidth overhead. Since we assume broadcast 115 settings where the sender does not retransmit lost packets, and the 116 receiver still wants to immediately authenticate each packet it 117 receives, we would need to attach a digital signature to each 118 message. Because of the high overhead of asymmetric cryptography, 119 this approach would restrict us to low-rate streams, and to senders 120 and receivers with powerful workstations. We can try to amortize one 121 digital signature over multiple messages. However, such an 122 approach is still expensive in contrast to symmetric cryptography, 123 since symmetric cryptography is in general 3 to 5 orders of 124 magnitude more efficient than asymmetric cryptography. In addition, 125 the straight-forward amortization of one digital signature over 126 multiple packets requires reliability, as the receiver needs to 127 receive all packets to verify the signature. A number of schemes 128 that follow this approach are [4,5,6,7,8]. See [9] for more 129 details. 131 This document presents the Timed Efficient Stream Loss-tolerant 132 Authentication protocol (TESLA). TESLA uses mainly symmetric 133 cryptography, and uses time delayed key disclosure to achieve the 134 required asymmetry property. However, TESLA requires loosely 135 synchronized clocks between the sender and the receivers. See more 136 details in Section 4. Other schemes that follow a similar approach 137 to TESLA are [10,11,12]. 139 1.1 Notation 141 To denote the subscript or an index of a variable, we use the 142 underscore between the variable name and the index, e.g., the key K 143 with index i is K_i, the key K with index i+d is K_{i+d}. To write 144 a superscript we use the caret, e.g., function F with the argument 145 x executed i times is F^i(x). 147 2 Functionality 149 TESLA provides delayed per-packet data authentication. The key idea 150 to providing both efficiency and security is a delayed disclosure of 151 keys. The delayed key disclosure results in an authentication delay. 152 In practice, the delay is on the order of one RTT (round-trip-time). 154 TESLA has the following properties: 156 o Low computation overhead for generation and verification of 157 authentication information 159 o Low communication overhead 161 o Limited buffering required for the sender and the receiver, hence 162 timely authentication for each individual packet 164 o Strong robustness to packet loss 166 o Scales to a large number of receivers 168 o Security is guaranteed as long as the sender and recipients are 169 loosely time synchronized, where synchronization can take place 170 at session set-up. 172 TESLA can be used either in the network layer, or in the transport 173 layer, or in the application layer. The delayed authentication, 174 however, requires buffering of packets until authentication is 175 completed. Certain applications intolerant of delay may be willing to 176 process packets in parallel to being buffered awaiting authentication, 177 as long as roll-back is possible if packets are later found to be 178 unauthenticated. For instance, an interactive video may play-out 179 packets still awaiting authentication, but if they are later found to 180 be unauthenticated, it could stop further play-out and warn the viewer 181 that the last x msec were unauthenticated and should be ignored. 182 However, in the remainder of this document, for brevity, we will 183 assume packets are not processed in parallel to buffering. 185 2.1 Threat Model and Security Guarantee 187 We design TESLA to be secure against a powerful adversary with the 188 following capabilities: 190 o Full control over the network. The adversary can eavesdrop, 191 capture, drop, resend, delay, and alter packets. 193 o Access to a fast network with negligible delay. 195 o The adversary's computational resources may be very large, but 196 not unbounded. In particular, this means that the adversary can 197 perform efficient computations, such as computing a reasonable 198 number of pseudo-random function applications and MACs with 199 negligible delay. Nonetheless, the adversary cannot find the key 200 of a pseudorandom function (or distinguish it from a random 201 function) with non-negligible probability. 203 The security property of TESLA guarantees that the receiver never 204 accepts M_i as an authentic message unless the sender really sent 205 M_i. A scheme that provides this guarantee is called a secure 206 broadcast authentication scheme. 208 Since TESLA expects the receiver to buffer packets before 209 authentication, the receiver needs to protect itself from a 210 potential denial-of-service (DOS) attack due to a flood of bogus 211 packets. 213 2.2 Assumptions 215 TESLA makes the following assumptions in order to provide security: 217 1. The sender and the receiver must be be able to loosely 218 synchronize. Specifically, each receiver must be able to 219 compute an upper bound on the lag of the receiver clock 220 relative to the sender clock. We denote this quantity by D_t. 221 (That is, D_t = sender time - receiver time). We note that 222 an upper bound on D_t can be easily obtained via a simple 223 two-message exchange. (Such an exchange can be piggybacked on 224 any secure session initiation protocol. Alternatively, standard 225 protocols such as as NTP [16] can be used. 227 2. TESLA MUST be bootstrapped at session set-up through a 228 regular data authentication system. We recommend to use a 229 digital signature algorithm for this purpose, in which case 230 the receiver is required to have an authentic copy of either 231 the sender's public key certificate or a root key certificate 232 in case of a PKI (public-key infrastructure). Alternatively, 233 this initialization step can be done using any secure session 234 initiation protocol. 236 3. TESLA uses cryptographic MAC and PRF (pseudo-random functions). 237 These MUST be cryptographically secure. Further details on 238 the instantiation of the MAC and PRF are in Section 4.2. 240 4. We would like to emphasize that the security of TESLA does NOT 241 rely on any assumptions on network propagation delay. 243 3 The Basic TESLA Protocol 245 TESLA is described in several academic publications: A book on 246 broadcast security [13], a journal paper [14], and two conference 247 papers [8,15]. Please refer to these publications for an in-depth 248 treatment. 250 3.1 Protocol sketch 252 We first outline the main ideas behind TESLA. 254 As we argue in the introduction, broadcast authentication requires 255 a source of asymmetry. TESLA uses time for asymmetry. We first make 256 sure that the sender and receivers are loosely time synchronized as 257 described above. Next, the sender forms a one-way chain of keys, 258 where each key in chain is associated with a time interval (say, a 259 second). Here is the basic approach: 261 o The sender attaches a MAC to each packet. The MAC is computed 262 over the contents of the packet. For each packet, the sender 263 uses the current key from the one-way chain as a cryptographic 264 key to compute the MAC. 266 o The sender discloses a key from the one-way chain after some 267 pre-defined time delay. (e.g., the key used in time interval i 268 is disclosed at time interval i+3.) 270 o Each receiver receives the packet. Each receiver knows the 271 schedule for disclosing keys and, since it has an upper bound 272 on the local time at the sender, it can check that the key used 273 to compute the MAC was not yet disclosed by the sender. If so, 274 then the receiver buffers the packet. Otherwise the packet is 275 dropped due to inability to authenticate. Note that we do not 276 know for sure whether a "late packet" is a bogus one or simply 277 a delayed packet. We drop the packet since we are unable to 278 authenticate it. (Ofcourse, an implementation may choose to 279 not drop packets and use them unauthenticated.) 281 o Each receiver checks that the disclosed key belongs to the 282 hash-chain (by checking against previously released keys in the 283 chain) and then checks the correctness of the MAC. If the MAC 284 is correct, the receiver accepts the packet. 286 Note that one-way chains have the property that if intermediate 287 values of the one-way chain are lost, they can be recomputed using 288 subsequent values in the chain . So, even if some key disclosures 289 are lost, a receiver can recover the corresponding keys and check 290 the correctness of earlier packets. 292 We now describe the stages of the basic TESLA protocol in this 293 order: sender setup, receiver bootstrap, sender transmission of 294 authenticated broadcast messages, and receiver authentication of 295 broadcast messages. 297 3.2 Sender Setup 299 The sender divides the time into uniform intervals of duration T_int. 300 The sender assigns one key from the one-way chain to each time 301 interval in sequence. 303 The sender determines the length N of the one-way chain K_0, K_1, 304 ..., K_N, and this length limits the maximum transmission duration 305 before a new one-way chain must be created. The sender picks a 306 random value for K_N. Using a pseudo-random function (PRF) f, the 307 sender constructs the one-way function F: F(k) = f_k(0). The rest 308 of the chain is computed recursively using K_i = F(K_{i+1}). Note 309 that this gives us K_i = F^{N-i}(K_N), so the receiver can compute 310 any value in the key chain from K_N even if is does not have 311 intermediate values. The key K_i will be used to authenticate 312 packets sent in time interval i. 314 Jakobsson [21], and Coppersmith and Jakobsson [22] present a storage 315 and computation efficient mechanism for one-way chains. For a chain 316 of length N, storage is about log(N) elements, and the computation 317 overhead to reconstruct each element is also about log(N). 319 The sender determines the duration of a time interval, T_int, and the 320 key disclodure delay, d. (T_int is measured in time units, say 321 millieconds, and d is measured in number of time intervals. That is, 322 a key that is used for time interval i will be desclosed in time 323 interval i+d.) It is stressed that the scheme remains secure for any 324 values of T_int and d. Still, correct choice of T_int and d is 325 crucial for the usability of the scheme. The choice is influenced by 326 the estimated network delay, the length of the transmission, and the 327 tolerable delay at the receiver. T_int that is too short will cause 328 the keys to run out too soon. T_int that is too long will cause 329 excessive delay in authentication for some of the packets (those that 330 were sent at the beginning of a time period). Delay d that is too 331 short will cause to many packets to be unverifiable by the receiver. 332 Delay d that is too long will cause excessive delay in authentication. 334 If the sender estimates that the average network delay is m 335 milliseconds, and the sender expects to send a packet every n 336 milliseconds, then a reasonable value for T_int is max(n,m) and 337 a reasonable value for d is ceil(2m/T_int). If the application can 338 tolerate higher authentication delay then T_int can be made 339 appropriately larger. 341 Finally, the sender needs to allow each receiver to synchronize 342 its time with the sender. See more details on how this can be done in 343 section 3.3. (It is stressed that estimating the network delay is a 344 separate task than the time synchronization between the sender and 345 the receivers.) 347 3.3 Bootstrapping Receivers 349 Before a receiver can authenticate messages with TESLA, it needs to 350 have: 352 o An upper bound D_t on the lag of its own clock with respect to 353 the clock of the sender. (That is, if the local time reading is 354 t, the current time reading at the sender is at most t+D_t.). 356 o One authenticated key of the one-way key chain. (Typically, 357 this will be the last key in the chain, i.e. K_0, this key will 358 be signed by the sender, and all receivers will verify the 359 signature against the public key of the signer. 361 o The disclosure schedule of keys: 363 - T_int, the interval duration. 364 - T_0, the start time of interval 1. 365 - N, the length of the one-way key chain. 366 - d, the key disclosure delay d (in number of intervals). 368 The receiver can perform the time synchronization and getting the 369 authenticated TESLA parameters in a two-round message exchange, 370 as described below. We stress again that time synchronization can 371 be performed as part of the registration protocol between the receiver 372 and sender, or between the receiver and a group controller. 374 3.3.1 Time Synchronization 376 Various approaches exist for time synchronization [16,17,18,19]. 377 TESLA only requires the receiver to know an upper bound on the 378 delay of its local clock with respect to the sender's clock, so a 379 simple algorithm is sufficient. TESLA can be used with direct, 380 indirect, and delayed synchronization as three default options. 381 The specific synchronization method will be part of each 382 instantiation of TESLA. 384 For completeness, we sketch a simple method for direct 385 synchronization between the sender and a receiver: 386 o The receiver sends a (sync t_r) message to the sender and 387 records its local time t_r. 389 o Upon receipt of the (sync t_r) message, the sender records its 390 local time t_s and sends (synch, t_r,t_s) to the receiver. 392 o Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s - 393 t_r + S, where S is an estimated bound on the clock drift 394 throughout the duration of the session. 396 Note: 397 o Assuming that the messages are authentic (i.e., the message 398 received the receiver was actually sent by the sender), and 399 assuming that the clock drift is at most S, then at any point 400 throughout the session we have that T_s < T_r + D_t, where T_s 401 is the current time at the sender and T_r is the current time 402 at the receiver. 404 o The exchange of sync messages needs to be authenticated. This 405 can be done in a number of ways, for instance a secure NTP 406 protocol, or in conjunction with a session set-up protocol. 408 For indirect time synchronization (eg, synchronization via a group 409 controller), the sender and the controller engage in a protocol for 410 finding the value D^0_t between the sender and the controller. Next, 411 each receiver R interacts with the group controller (say, when 412 registering to the group) and finds the value D^R_t between the group 413 controller and R. The overall value of D_t within R is set to the sum 414 D_t = D^R_t + D^0_t. 416 3.4 Broadcasting Authenticated Messages 418 Each key in the one-way key chain corresponds to a time interval. 419 Every time a sender broadcasts a message, it appends a MAC to the 420 message, using the key corresponding to the current time interval. 421 The key remains secret for the next d-1 intervals, so messages a 422 sender broadcasts in interval j effectively disclose key K_j-d. We 423 call d the key disclosure delay. 425 We do not want to use the same key multiple times in different 426 cryptographic operations, that is, to use key K_j to derive the 427 previous key of the one-way key chain K_{j-1}, and to use the same 428 key K_j as the key to compute the MACs in time interval j may 429 potentially lead to a cryptographic weakness. Using a pseudo-random 430 function (PRF) f', we construct the one-way function F': F'(k) = 431 f'_k(1). We use F' to derive the key to compute the MAC of messages 432 in each interval. The sender derives the MAC key as follows: K'_i 433 = F'(K_i). Figure 1 depicts the one-way key chain construction and 434 MAC key derivation. To broadcast message M_j in interval i the 435 sender constructs the packet 437 P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}} 439 where || denotes concatenation. 441 F(K_i) F(K_{i+1}) F(K_{i+2}) 442 K_{i-1} <------- K_i <--------- Ki+1 <------- Ki+2 444 | | | 445 | F'(K_{i-1}) | F'(K_i) | F'(K_{i+1}) 446 | | | 447 V V V 449 K'_{i-1} K'_i K'_{i+1} 451 Figure 1: At the top of the figure, we see the one-way key chain 452 (derived using the one-way function F), and the derived MAC keys 453 (derived using the one-way function F'). 455 3.5 Authentication at Receiver 457 Once a sender discloses a key, we must assume that all parties might 458 have access to that key. An adversary could create a bogus message 459 and forge a MAC using the disclosed key. So whenever a packet 460 arrives, the receiver must verify that the MAC is based on a safe 461 key; a safe key is one that is still secret (only known by the 462 sender). We define a safe packet or safe message to be one with a MAC 463 that is computed with a safe key. 465 If the packet is not safe, the receiver must discard that packet, 466 because the authenticity is not assured any more. 468 We now explain the TESLA authentication in more detail. When the 469 receiver receives packet P_j which carries an interval index i, the 470 receiver first records local time T in which the packet arrived. It 471 then computes an upper bound t_j on the sender's clock at the time 472 where the packet arrived: t_j = T + D_t. To test whether the packet 473 is safe, the receiver then computes the highest interval x the 474 sender could possibly be in, namely x = floor((t_j - T_0) / T_int). 475 The receiver verifies that x < i + d (where i is the interval index), 476 which implies that the sender is not yet in the interval during which 477 it discloses the key K_i. If the condition fails then the receiver 478 considers the packet unauthenticated. 480 The receiver cannot yet verify the authenticity of packets sent in 481 interval i without key K_i. Instead, it adds the triplet ( i, M_j, 482 MAC( K'_i, M_j) ) to a buffer, and verifies the authenticity after it 483 learns K'_i. 485 What does a receiver do when it receives the disclosed key K_i? 486 First, it checks whether it already knows K_i or a later key K_j 487 with j>i. Then the receiver checks the legitimacy of K_i by verifying, 488 for some earlier key K_v (v1, 495 the receiver can also verify the authenticity of the stored packets 496 of intervals v+1 ... i-1. 498 3.6 Determining the Key Disclosure Delay 500 An important TESLA parameter is the key disclosure delay d. Although 501 the choice of the disclosure delay does not affect the security of 502 the system, it is an important performance factor. A short disclosure 503 delay will cause packets to lose their safety property, so receivers 504 will discard them; but a long disclosure delay leads to a long 506 authentication delay for receivers. We recommend determining the 507 disclosure delay as follows: in direct time synchronization let 508 the RTT be a reasonable upper bound on the round trip time between the 509 sender and the receiver; then choose d = ceil( RTT / T_int) + 1. Note 510 that rounding up the quotient ensures that d >= 2. Also note that a 511 disclosure delay of one time interval (d=1) does not work. Consider 512 packets sent close to the boundary of the time interval: after the 513 network propagation delay and the receiver time synchronization 514 error, a receiver will need to discard the packet, because the sender 515 will already be in the next time interval, when it discloses the 516 corresponding key. 518 We stress that the security of TESLA does not rely on any assumptions on 519 network propagation delay: If the delay is longer than expected then 520 authentic packets may be considered unauthenticated. Still, 521 no unauthentic packet will be accepted as authentic. 523 3.7 An alternative delay description method 525 The above description instructs the sender to include the time interval 526 i in each packet. The receiver then uses i to determine the time at which 527 the key authenticating the packet is disclosed. This method limits the 528 the sender to a pre-determined schedule of disclosing keys. 530 Alternatively, the sender may directly include in each packet the time t_p 531 at which it is going to disclose the key for this packet. This way, the 532 receiver does not need to know the duration of intervals or the delay 533 factor d. All the receiver needs to know is the bound D_t on the clock 534 skew and T_0, the sender's local time at the initiation of the session. 535 Then the receiver records the local time T when the packet has arrived, 536 and verifies that 537 T <= T_0 + D_t + t_p. 539 Else the packet is considered aunauthenticated. 541 Another advantage of this method is that the sender is able to 542 change the duration of intervals and the key disclosure delay 543 dynamically throughout the session. It is stressed, however, that the 544 interval index i must still be included in the packet, to allow the 545 receiver to know which key K_i should be used to verify the packet. 547 3.8 Some extensions 549 Let us mention two salient extensions of the basic TESLA scheme. A 550 first extension allows having multiple TESLA authentication chains 551 for a single stream, where each chain uses a different delay for 552 disclosing the keys. This extension is typically used to deal with 553 heterogeneous network delays within a single multicast 554 transmission. A second extension allows having most of the 555 buffering of packets at the sender side (rather than at the 556 receiver side). Both extensions are described in [15]. 558 The requirement in TESLA to receive a key in a later packet for 559 authentication prevents a receiver from authenticating the last 560 part of a message. Thus, to enable authentication of the last part 561 of a message or of the last message before a transmission 562 suspension, the sender needs to send an empty message with the key 563 to enable authentication. 565 4 Layer placement 567 The TESLA authentication can be performed at any layer in the 568 networking stack. Three natural places are in the network, transport, 569 or the application layer. We list some considerations regarding the 570 choice of layer: 572 o Performing TESLA in the network layer has the advantage that the 573 transport or application layer only receives authenticated data, 574 potentially aiding a reliability protocol and preventing denial 575 of service attacks. (Indeed, reliable multicast tools based on 576 forward error correction are highly susceptible to denial of 577 service due to bogus packets.) 579 o Performing TESLA in either the transport or the application layer 580 has the advantage that the network layer remains unchanged; but it 581 has the drawback that packets are obtained by the application layer 582 only after being processed by the transport layer. Consequently, 583 if TCP is used then this may introduce additional and unpredictable 584 delays on top of the unavoidable network delays. (However, if UDP 585 is used then this is not a problem.) 587 o It should be kept in mind that, since TESLA relies upon timing 588 of packets, deploying TESLA on top of a protocol or layer which 589 aggressively buffers packets and hides the true packet arrival 590 time (e.g., TCP) will significantly reduce the perormance of TESLA. 592 5. Security Considerations 594 See the academic publications on TESLA [8,14,20] for several 595 security analyses. Regarding the security of implementations, by 596 far the most delicate point is the verification of the timing 597 conditions. Care should be taken to to make sure that: (a) the 598 value bound D_t on the clock skew is calculated according to the 599 spec at session set-up; (b) the receiver records the arrival time 600 of the packet as soon as possible after the packet's arrival, and 601 computes the safety condition correctly. 603 It is important to note that, unless appropriate measures are taken, 604 TESLA increases the susceptibility of receivers to denial of service 605 (DoS) attacks. Specifically, an attacker can flood a victim receiver 606 with bogus packets that need to be buffered for delayed authentication. 607 There are several measures against such attacks. Here we mention 608 some of the known mechanisms to reduce this susceptibility: 610 o Limit the size of buffers at the receiver side. 612 o Add an external MAC that is computed using either (a) a key that 613 is constant for the session and known to all receivers, or (b) 614 the key that is disclosed in the current packet. Both mechanisms 615 prevent simple flooding attacks but are still susceptible to 616 more sophisticated attacks that have some "inside" information 617 on the session. 619 o Move the buffering of packets to the sender side, and allow 620 receivers to authenticate packets immediately upon receipt. 621 This method is described in [14]. 623 Finally, in common with all authentication schemes, if verification 624 is located separately from the ultimate destination application (e.g. 625 an IPSec tunnel end point), a trusted channel must be present between 626 verification and the application. For instance, the interface between 627 the verifier and the application might simply assume that packets 628 received by the application must have been verified by the verifier 629 (because otherwise they would have been dropped). The application is 630 then vulnerable to reception of packets that have managed to bypass 631 the verifier. 633 6 IP Statement 635 The authors are not aware of any patents that encumber the free 636 use of TESLA. 638 7 Acknowledgments 640 We would like to thank Mike Luby for his feedback and support. 642 8 References 644 All references are informative. 646 [1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet 647 Request for Comments RFC 2246, January 1999. Proposed standard. 649 [2] IPsec, "IP Security Protocol, IETF working group." 650 http://www.ietf.org/html.charters/ipsec-charter.html. 652 [3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast 653 message authentication," in Advances in Cryptology -- EUROCRYPT '2001 654 (B. Pfitzmann, ed.), vol. 2045 of Lecture Notes in Computer Science , 655 (Innsbruck, Austria), pp. 434--450, Springer-Verlag, Berlin Germany, 656 2001. 658 [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech. 659 rep., IBM T.J.Watson Research Center, 1997. 661 [5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul- 662 ticast packet authentication," in 6th ACM Conference on Computer and 663 Communications Security , November 1999. 665 [6] P. Rohatgi, "A hybrid signature scheme for multicast source 666 authentication," Internet Draft, Internet Engineering Task Force, 667 June 1999. Work in progress. 669 [7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul- 670 ticasts," in Proc. IEEE ICNP `98 , 1998. 672 [8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient 673 authentication and signing of multicast streams over lossy channels," 674 in IEEE Symposium on Security and Privacy , May 2000. 676 [9] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. 677 Pinkas, "Multicast security: A taxonomy and some efficient construc- 678 tions," in Infocom '99 , 1999. 680 [10] S. Cheung, "An efficient message authentication scheme for link 681 state routing," in 13th Annual Computer Security Applications Confer- 682 ence , 1997. 684 [11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream 685 authentication," in Selected Areas in Cryptography 2000 , (Waterloo, 686 Canada), August 2000. A talk describing this scheme was given at IBM 687 Watson in August 1998. 689 [12] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single 690 source authentication on the mbone," in ICME 2000 , Aug 2000. A talk 691 containing this work was given at IBM Watson, August 1998. 693 [13] A. Perrig and J. D. Tygar, Secure Broadcast Communication in 694 Wired and Wireless Networks Kluwer Academic Publishers, Oct. 2002. 695 ISBN 0792376501. 697 [14] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla 698 broadcast authentication protocol," RSA CryptoBytes , vol. 5, no. 699 Summer, 2002. 701 [15] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and 702 secure source authentication for multicast," in Network and Dis- 703 tributed System Security Symposium, NDSS '01 , pp. 35--46, February 704 2001. 706 [16] D. L. Mills, "Network Time Protocol (Version 3) Specification, 707 Implementation and Analysis." Internet Request for Comments, March 708 1992. RFC 1305. 710 [17] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of 711 clock synchronization," in Fault-Tolerant Distributed Computing (B. 712 Simons and A. Spector, eds.), no. 448 in LNCS, pp. 84--96, Springer- 713 Verlag, Berlin Germany, 1990. 715 [18] D. Mills, "Improved algorithms for synchronizing computer net- 716 work clocks," in Proceedings of the conference on Communications 717 architectures, protocols and applications, SIGCOMM 94 , (London, 718 England), pp. 317--327, 1994. 720 [19] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the 721 presence of faults," J. ACM , vol. 32, no. 1, pp. 52--78, 1985. 723 [20] Philippa Broadfoot and Gavin Lowe, "Analysing a Stream 724 Authentication Protocol using Model Checking. In Proceedings of the 725 7th European Symposium on Research in Computer Security (ESORICS), 726 2002. 728 [21] M. Jakobsson, "Fractal hash sequence representation and traver� 729 sal." Cryptology ePrint Archive, http://eprint.iacr.org/2002/001/, 730 Jan. 2002. 732 [22] D. Coppersmith and M. Jakobsson, "Almost optimal hash sequence 733 traversal," in Proceedings of the Sixth International Financial Cryp� 734 tography Conference (FC '02) , March 2002. 736 A Author Contact Information 738 Adrian Perrig 739 ECE Department 740 Carnegie Mellon University 741 Pittsburgh, PA 15218 742 US 743 perrig@cmu.edu 745 Ran Canetti 746 IBM Research 747 30 Saw Mill River Rd 748 Hawthorne, NY 10532 749 US 750 canetti@watson.ibm.com 752 Dawn Song 753 ECE Department 754 Carnegie Mellon University 755 Pittsburgh, PA 15218 756 US 757 dawnsong@cmu.edu 759 Doug Tygar 760 UC Berkeley 761 102 South Hall, 4600 762 Berkeley, CA 94720-4600 763 US 764 tygar@cs.berkeley.edu 766 Bob Briscoe 767 BT Research 768 B54/77, BT Labs 769 Martlesham Heath 770 Ipswich, IP5 3RE 771 UK 772 bob.briscoe@bt.com 773 B Full Copyright Statement 775 Copyright (C) The Internet Society (2000). All Rights Reserved. 777 This document and translations of it may be copied and furnished to 778 others, and derivative works that comment on or otherwise explain it 779 or assist in its implementation may be prepared, copied, published 780 and distributed, in whole or in part, without restriction of any 781 kind, provided that the above copyright notice and this paragraph are 782 included on all such copies and derivative works. However, this doc- 783 ument itself may not be modified in any way, such as by removing the 784 copyright notice or references to the Internet Society or other 785 Internet organizations, except as needed for the purpose of develop- 786 ing Internet standards in which case the procedures for copyrights 787 defined in the Internet languages other than English. 789 The limited permissions granted above are perpetual and will not be 790 revoked by the Internet Society or its successors or assigns. 792 This document and the information contained herein is provided on an 793 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 794 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 795 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 796 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER- 797 CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."