idnits 2.17.1 draft-ietf-msec-tesla-intro-02.txt: -(159): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(270): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(510): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(517): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(557): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(565): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(573): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(577): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(671): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(674): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(685): 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 28 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 2 longer pages, the longest (page 8) being 60 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. ** There are 49 instances of too long lines in the document, the longest one being 6 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 219: '... 2. TESLA MUST be bootstrapped a...' RFC 2119 keyword, line 222: '... is REQUIRED to have an authe...' RFC 2119 keyword, line 227: '...unctions). These MUST be cryptographic...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 213 has weird spacing: '...such as as NT...' == Line 402 has weird spacing: '...ure, we see ...' == Line 403 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 (May 2004) is 7286 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) -- Missing reference section? '1' on line 542 looks like a reference -- Missing reference section? '2' on line 545 looks like a reference -- Missing reference section? '3' on line 548 looks like a reference -- Missing reference section? '4' on line 554 looks like a reference -- Missing reference section? '5' on line 557 looks like a reference -- Missing reference section? '6' on line 561 looks like a reference -- Missing reference section? '7' on line 565 looks like a reference -- Missing reference section? '8' on line 568 looks like a reference -- Missing reference section? '9' on line 572 looks like a reference -- Missing reference section? '10' on line 576 looks like a reference -- Missing reference section? '11' on line 580 looks like a reference -- Missing reference section? '12' on line 585 looks like a reference -- Missing reference section? '16' on line 602 looks like a reference -- Missing reference section? '13' on line 589 looks like a reference -- Missing reference section? '14' on line 593 looks like a reference -- Missing reference section? '15' on line 597 looks like a reference -- Missing reference section? '17' on line 606 looks like a reference -- Missing reference section? '18' on line 611 looks like a reference -- Missing reference section? '19' on line 616 looks like a reference -- Missing reference section? '20' on line 619 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 7 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-02.txt UC Berkeley / Digital Fountain / IBM / BT 5 May 2004 6 Expires: November 2004 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 applications, 31 for example audio and video Internet broadcasts, or data distribution 32 by satellite. This document introduces TESLA, a secure source 33 authentication mechanism for multicast or broadcast data streams. This 34 document provides an algorithmic description of the scheme for 35 informational purposes, and in particular, it is intended to assist 36 in writing standardizable and secure specifications for protocols 37 based on TESLA in different contexts. 39 The main deterrents so far for a data authentication mechanism for 40 multicast were the seemingly conflicting requirements: loss tolerance, 41 high efficiency, no per-receiver state at the sender. The problem 42 is particularly hard in settings with high packet loss rates and 43 where lost packets are not retransmitted, and where the receiver 44 wants to authenticate each packet it receives. 46 TESLA provides authentication of individual data packets, regardless 47 of the packet loss rate. In addition, TESLA features low overhead for 48 both sender and receiver, and does not require per-receiver state at 49 the sender. TESLA is secure as long as the sender and receiver are 50 loosely time synchronized. 52 Table of Contents 54 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2 55 1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . 3 56 2 Functionality . . . . . . . . . . . . . . . . . . . . . . 4 57 2.1 Threat Model and Security Guarantee . . . . . . . . . . . 4 58 2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5 59 3 The Basic TESLA Protocol . . . . . . . . . . . . . . . . 5 60 3.1 Sketch of protocol . . . . . . . . . . . . . . . . . . . 6 61 3.2 Sender Setup . . . . . . . . . . . . . . . . . . . . . . 7 62 3.3 Bootstrapping Receivers . . . . . . . . . . . . . . . . . 7 63 3.3.1 Time Synchronization. . . . . . . . . . . . . . . . . . . 8 64 3.4 Broadcasting Authenticated Messages . . . . . . . . . . . 8 65 3.5 Authentication at Receiver . . . . . . . . . . . . . . . 8 66 3.6 Determining the Key Disclosure Delay . . . . . . . . . . 9 67 3.7 An alternative delay description method . . . . . . . . . 10 68 3.8 Some extensions . . . . . . . . . . . . . . . . . . . . . 11 69 4 Layer placement . . . . . . . . . . . . . . . . . . . . . 11 70 5 Security considerations . . . . . . . . . . . . . . . . . 11 71 6 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 12 72 7 Bibliography . . . . . . . . . . . . . . . . . . . . . . 12 73 A Author Contact Information . . . . . . . . . . . . . . . 13 74 B Full Copyright Statement . . . . . . . . . . . . . . . . 14 76 1 Introduction 78 The power of multicast is that one packet can reach millions of 79 receivers. This great property is unfortunately also a great danger: 80 an attacker that sends one malicious packet can also potentially 81 reach millions of receivers. Receivers need multicast source 82 authentication to ensure that a given packet originates from the correct 83 source. 85 In unicast communication, we can achieve data authentication through 86 a purely symmetric mechanism: the sender and the receiver share a 87 secret key to compute a message authentication code (MAC) of all 88 communicated data. When a message with a correct MAC arrives, the 89 receiver is assured that the sender generated that message. Standard 90 mechanisms achieve unicast authentication this way, for example TLS 91 or IPsec [1,2]. 93 The symmetric MAC authentication is not secure in a broadcast 94 setting. Consider a sender that broadcasts authentic data to mutually 95 untrusting receivers. The symmetric MAC is not secure: every receiver 96 knows the MAC key, and hence could impersonate the sender and forge 97 messages to other receivers. Intuitively, we need an asymmetric 98 mechanism to achieve authenticated broadcast, such that every receiver 99 can verify the authenticity of messages it receives, without being 100 able to generate authentic messages. Achieving this in an efficient 101 way is a challenging problem [3]. 103 The standard approach to achieve such asymmetry for authentication is 104 to use asymmetric cryptography, for instance a digital signature. 105 Digital signatures have the required asymmetric property: the sender 106 generates the signature with its private key, and all receivers can 107 verify the signature with the sender's public key, but a receiver 108 with the public key alone cannot generate a digital signature for a 109 new message. A digital signature provides non-repudiation, which is a 110 stronger property than authentication. Unfortunately, digital 111 signatures have a high cost: they have a high computation overhead for 112 both the sender and the receiver, as well as a high communication 113 overhead. Since we assume broadcast settings where the sender does 114 not retransmit lost packets, and the receiver still wants to 115 immediately authenticate each packet it receives, we would need to 116 attach a digital signature to each message. Because of the high 117 overhead of asymmetric cryptography, this approach would restrict 118 us to low-rate streams, and to senders and receivers with powerful 119 workstations. To deal with the high overhead of asymmetric cryptography, 120 we can try to amortize one digital signature over multiple messages. 121 However, such an approach is still expensive in contrast to symmetric 122 cryptography, since symmetric cryptography is in general 3 to 5 orders 123 of magnitude more efficient than asymmetric cryptography. In addition, 124 the straight-forward amortization of one digital signature over multiple 125 packets requires reliability, as the receiver needs to receive all 126 packets to verify the signature. A number of schemes that follow this 127 approach are [4,5,6,7,8]. See [9] for more details. 129 This document presents the Timed Efficient Stream Loss-tolerant 130 Authentication protocol (TESLA). TESLA uses mainly symmetric 131 cryptography, and uses time delayed key disclosure to achieve the 132 required asymmetry property. However, TESLA requires loosely 133 synchronized clocks between the sender and the receivers. See more 134 details in Section 4. Other schemes that follow a similar approach 135 to TESLA are [10,11,12]. 137 1.1 Notation 139 To denote the subscript or an index of a variable, we use the 140 underscore between the variable name and the index, e.g. the key K with 141 index i is K_i, the key K with index i+d is K_{i+d}. To write a 142 superscript we use the caret, e.g. the function F with the argument x 143 executed i times is F^i(x), executed j-1 times we write F^{j-1}(x). 145 2 Functionality 147 TESLA provides delayed per-packet data authentication. The key idea 148 to providing both efficiency and security is a delayed disclosure of 149 keys. The delayed key disclosure results in an authentication delay. 150 In practice, the delay is on the order of one RTT (Round-trip-time). 152 TESLA has the following properties: 154 � Low computation overhead for generation and verification of 155 authentication information 157 � Low communication overhead 159 � Limited buffering required for the sender and the receiver, hence 160 timely authentication for each individual packet 162 � Strong robustness to packet loss 164 � Scales to a large number of receivers 166 � Security is guaranteed as long as the sender and recipients are 167 loosely time synchronized, where synchronization can take place 168 at session set-up. 170 TESLA can be used either in the network layer, or in the transport 171 layer, or in the application layer. The delayed authentication, 172 however, requires buffering of packets until authentication is completed. 174 2.1 Threat Model and Security Guarantee 176 We design TESLA to be secure against a powerful adversary with the 177 following capabilities: 179 � Full control over the network. The adversary can eavesdrop, 180 capture, drop, resend, delay, and alter packets. 182 � Access to a fast network with negligible delay. 184 � The adversary's computational resources may be very large, but 185 not unbounded. In particular, this means that the adversary can 186 perform efficient computations, such as computing a reasonable 187 number of pseudo-random function applications and MACs with 188 negligible delay. Nonetheless, the adversary cannot find the key 189 of a pseudorandom function (or distinguish it from a random 190 function) with non-negligible probability. 192 The security property of TESLA guarantees that the receiver never 193 accepts M_i as an authentic message unless the sender really sent 194 M_i. A scheme that provides this guarantee is called a secure 195 broadcast authentication scheme. 197 Since TESLA requires the receiver to buffer packets before 198 authentication, the receiver needs to protect itself from a 199 potential denial-of-service (DOS) attack due to a flood of bogus packets. 201 2.2 Assumptions 203 TESLA makes the following assumptions in order to provide security: 205 1. The sender and the receiver must be be able to loosely 206 synchronize. Specifically, each receiver must be able to 207 compute an upper bound on the lag of the receiver clock 208 relative to the sender clock. We denote this quantity by D_t. 209 (That is, D_t = sender time - receiver time). 210 We note that an upper bound on D_t can be easily obtained via 211 a simple two-message exchange. (Such an exchange can be 212 piggybacked on any session initiation protocol. Alternatively, 213 standard protocols such as as NTP [16] can be used. 214 (The synchronization assumption of TESLA is considerably weaker 215 the synchronization requirements of authentication protocols based 216 on timestamps. In those protocols, the participants are 217 assumed to have the same global time a-priori.) 219 2. TESLA MUST be bootstrapped at session set-up through a regular 220 data authentication system. We recommend to use a digital 221 signature algorithm for this purpose, in which case the receiver 222 is REQUIRED to have an authentic copy of either the sender's 223 public key certificate or a root key certificate in case of a 224 PKI (public-key infrastructure). 226 3. TESLA uses cryptographic MAC and PRF (pseudo-random 227 functions). These MUST be cryptographically secure. Further 228 details on the instantiation of the MAC and PRF are in Section 229 4.2. 231 4. We would like to emphasize that the security of TESLA does NOT 232 rely on any assumptions on network propagation delay. 234 3 The Basic TESLA Protocol 236 TESLA is described in several academic publications: A book on 237 broadcast security [13], a journal paper [14], and two conference papers 239 [8,15]. Please refer to these publications for an in-depth treatment. 241 3.1 Sketch of protocol 243 We first outline the main ideas behind TESLA. 245 As we argue in the introduction, broadcast authentication requires a 246 source of asymmetry. TESLA uses time for asymmetry. We first make sure 247 that the sender and receivers are loosely time synchronized as described 248 above. Next, the sender forms a one-way chain of keys, where each key in 249 chain is associated with a time interval (say, a second). Here is the 250 basic approach: 252 � The sender attaches a MAC to each packet. The MAC is computed 253 over the contents of the packet. For each packet, the sender uses 254 the current key from the one-way chain as a cryptographic key 255 to compute the MAC. 257 � The sender discloses a key from the one-way chain after some 258 pre-defined time delay. (e.g., the key used in time interval i 259 is disclosed at time interval i+3.) 261 � Each receiver receives the packet. Each receiver knows the 262 schedule for disclosing keys and, since it has an upper bound on 263 the local time at the sender, it can check that the key used to 264 compute the MAC was not yet disclosed by the sender. If so, then 265 the receiver buffers the packet. Otherwise the packet is dropped. 266 (Note that we do not know for sure whether a "late packet" is a 267 bogus one or simply a delayed packet. We drop the packet since we 268 are unable to authenticate it.) 270 � Each receiver checks that the disclosed key belongs to the hash-chain 271 (by checking against previously released keys in the chain) and then 272 checks the correctness of the MAC. If the MAC is correct, the 273 receiver accepts the packet. 275 Note that one-way chains have the property that if intermediate 276 values of the one-way chain are lost, they can be recomputed using 277 subsequent values in the chain . So, even if some key disclosures 278 are lost, a receiver can recover the corresponding keys and check 279 the correctness of earlier packets. 281 We now describe the stages of the basic TESLA protocol in this order: 282 sender setup, receiver bootstrap, sender transmission of 283 authenticated broadcast messages, and receiver authentication of 284 broadcast messages. 286 3.2 Sender Setup 288 The sender divides the time into uniform intervals of duration T_int. 289 The sender assigns one key from the one-way chain to each time 290 interval in sequence. 292 The sender determines the length N of the one-way chain K_0, K_1, 293 ..., K_N, and this length limits the maximum transmission duration 294 before a new one-way chain must be created. The sender picks a random 295 value for K_N. Using a pseudo-random function (PRF) f, the sender 296 constructs the one-way function F: F(k) = f_k(0). The rest of the 297 chain is computed recursively using K_i = F(K_{i+1}). Note that this 298 gives us K_i = F^{N-i}(K_N), so the receiver can compute any value in 299 the key chain from K_N even if is does not have intermediate values. 300 The key K_i will be used to authenticate packets sent in time 301 interval i. 303 3.3 Bootstrapping Receivers 305 Before a receiver can authenticate messages with TESLA, it needs to 306 have: 307 * An upper bound D_t on the lag of its own clock with respect to 308 the clock of the sender. (That is, if the local time reading is t, 309 the current time reading at the sender is at most t+D_t.). 310 * The disclosure schedule of keys. (Note that this information is not 311 essential. See details below.) 312 * One authenticated key of the one-way key chain. (Typically, this 313 will be the last key in the chain, i.e. K_0, this key will be 314 signed by the sender, and all receivers will verify the signature against 315 the public key of the signer. 317 The sender sends the key disclosure schedule by transmitting the 318 following information to the receivers over an authenticated channel 319 (either via a digitally signed broadcast message, or over an 320 authenticated unicast channel with each receiver): 322 � Time interval schedule: interval duration T_int, start time of 323 interval i and index of interval i, length of one-way key chain. 325 � Key disclosure delay d (number of intervals). 327 � A commitment to the key chain K_i (i < j - d + 1, where j is 328 the current interval index). 330 The receiver can perform the time synchronization and getting the 331 authenticated TESLA parameters in a two-round message exchange, which 332 we will describe in the technical TESLA document. Time synchronization 333 can be performed as part of the registration protocol between member 334 and sender. 336 3.3.1 Time Synchronization 338 Various approaches exist for time synchronization [16,17,18,19]. 339 TESLA, however, only requires the receiver to know an upper bound on 340 the delay of its local clock with respect to the receiver's clock, 341 so a simple algorithm is sufficient. TESLA can be used with direct, 342 indirect, and delayed synchronization as three default options. 343 The specific synchronization method will be part of each instantiation 344 of TESLA, and needs to be described in the appropriate standards-track 345 RFC. 347 For completeness we sketch a simple method for direct synchronization 348 between the sender and a receiver: 350 * The receiver sends a (sync t_r) message to the sender and records 351 its local time t_r. 352 * Upon receipt of the (sync t_r) message, the sender records its 353 local time t_s and sends (synch, t_r,t_s) to the receiver. 354 * Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s - t_r + S, 355 where S is an estimated bound on the clock drift throughout the 356 duration of the session. 358 Note: 360 * Assuming that the messages are authentic (i.e., the message received 361 the receiver was actually sent by the sender), and assuming that the 362 clock drift is at most S, then at any point throughout the session 363 we have that T_s < T_r + D_t, where T_s is the current time at the 364 sender and T_r is the current time at the receiver. 366 * The exchange of sync messages needs to be authenticated. This can be 367 done in a number of ways, for instance a secure NTP protocol, or in 368 conjunction with a session set-up protocol. 370 3.4 Broadcasting Authenticated Messages 372 Each key in the one-way key chain corresponds to a time interval. 373 Every time a sender broadcasts a message, it appends a MAC to the 374 message, using the key corresponding to the current time interval. 375 The key remains secret for the next d-1 intervals, so messages a 376 sender broadcasts in interval j effectively disclose key K_j-d. We 377 call d the key disclosure delay. 379 We do not want to use the same key multiple times in different 380 cryptographic operations, that is, to use key K_j to derive the previous 381 key of the one-way key chain K_{j-1}, and to use the same key K_j as 382 the key to compute the MACs in time interval j may potentially lead 383 to a cryptographic weakness. Using a pseudo-random function (PRF) 384 f', we construct the one-way function F': F'(k) = f'_k(1). We use F' 385 to derive the key to compute the MAC of messages in each interval. 386 The sender derives the MAC key as follows: K'_i = F'(K_i). Figure 1 387 depicts the one-way key chain construction and MAC key derivation. To 388 broadcast message M_j in interval i the sender constructs packet 389 P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}}, where || denotes 390 concatenation. 392 F(K_i) F(K_{i+1}) F(K_{i+2}) 393 K_{i-1} <------- K_i <--------- Ki+1 <------- Ki+2 395 | | | 396 | F'(K_{i-1}) | F'(K_i) | F'(K_{i+1}) 397 | | | 398 V V V 400 K'_{i-1} K'_i K'_{i+1} 402 Figure 1: At the top of the figure, we see the one-way key chain 403 (derived using the one-way function F), and the derived MAC keys 404 (derived using the one-way function F'). 406 3.5 Authentication at Receiver 408 Once a sender discloses a key, we must assume that all parties might 409 have access to that key. An adversary could create a bogus message 410 and forge a MAC using the disclosed key. So whenever a packet 411 arrives, the receiver must verify that the MAC is based on a safe 412 key; a safe key is one that is still secret (only known by the 413 sender). We define a safe packet or safe message to be one with a MAC 414 that is computed with a safe key. 416 If the packet is not safe, the receiver must discard that packet, 417 because the authenticity is not assured any more. 419 We now explain the TESLA authentication in more detail. When the 420 receiver receives packet P_j sent in interval i, the receiver 421 computes an upper bound on the sender's clock: t_j. To test whether the 422 packet is safe, the receiver computes the highest interval x the 423 sender could possibly be in, namely x = floor((t_j - T_0) / T_int). 424 The receiver verifies that x < i + d (where i is the interval index), 425 which implies that the sender is not yet in the interval during which 426 it discloses the key K_i. If the condition fails then the receiver 427 drops the packet. 429 The receiver cannot yet verify the authenticity of packets sent in 430 interval i without key K_i. Instead, it adds the triplet ( i, M_j, 431 MAC( K'_i, M_j) ) to a buffer, and verifies the authenticity after it 432 learns K'_i. 434 What does a receiver do when it receives the disclosed key K_i? 435 First, it checks whether it already knows K_i or a later key K_j 436 (j>i). If K_i is the latest key received to date, the receiver checks 437 the legitimacy of K_i by verifying, for some earlier key K_v (v1, 444 the receiver can also verify the authenticity of the stored packets 445 of intervals v+1 ... i-1. 447 Note that the security of TESLA does not rely on any assumptions on 448 network propagation delay. 450 3.6 Determining the Key Disclosure Delay 452 An important TESLA parameter is the key disclosure delay d. Although 453 the choice of the disclosure delay does not affect the security of 454 the system, it is an important performance factor. A short disclosure 455 delay will cause packets to lose their safety property, so receivers 456 will discard them; but a long disclosure delay leads to a long 458 authentication delay for receivers. We recommend choosing the 459 disclo� sure delay as follows: in direct time synchronization let 460 the RTT be a reasonable upper bound on the round trip time between the 461 sender and the receiver; then choose d = ceil( RTT / T_int) + 1. Note 462 that rounding up the quotient ensures that d >= 2. Also note that a 463 disclosure delay of one time interval (d=1) does not work. Consider 464 packets sent close to the boundary of the time interval: after the 465 network propagation delay and the receiver time synchronization 466 error, a receiver will need to discard the packet, because the sender 467 will already be in the next time interval, when it discloses the 468 corresponding key. 470 3.7 An alternative delay description method 472 The above description instructs the sender to include the time interval 473 i in each packet. The receiver then uses i to determine the time at which 474 the key authenticating the packet is disclosed. This method limits the 475 the sender to a pre-determined schedule of disclosing keys. 477 Alternatively, the sender may directly include in each packet the time t_p 478 at which it is going to disclose the key for this packet. This way, the 479 receiver does not need to know the duration of intervals or the delay 480 factor d. All the receiver needs to know is the bound D_t on the clock 481 skew and T_0, the sender's local time at the initiation of the session. 482 Then the receiver records the local time T when the packet has arrived, 483 and verifies that 484 T <= T_0 + D_t + t_p. 486 Else the packet is dropped. 488 Another advantage of this method is that the sender is able to change 489 the duration of intervals and the key disclosure delay dynamically 490 throughout the session. 492 3.8 Some extensions 494 Let us mention two salient extensions of the basic TESLA scheme. 495 A first extension allows having multiple TESLA authentication chains 496 for a single stream, where each chain uses a different delay for 497 disclosing the keys. This extension is typically used to deal with 498 heterogeneous network delays within a single multicast transmission. 499 A second extension allows having most of the buffering of packets 500 at the sender side (rather than at the receiver side). Both 501 extensions are described in [15]. 503 4 Layer placement 505 The TESLA authentication can be performed at any layer in the 506 networking stack. Three natural places are in the network, transport, 507 or the application layer. We list some considerations regarding the 508 choice of layer: 510 � Performing TESLA in the network layer has the advantage that the 511 transport or application layer only receives authenticated data, 512 potentially aiding a reliability protocol and preventing denial 513 of service attacks. (Indeed, reliable multicast tools based on 514 forward error correction are highly susceptible to denial of 515 service due to bogus packets.) 517 � Performing TESLA in either the transport or the application layer 518 has the advantage that the network layer remains unchanged; but it 519 has the drawback that packets are obtained by the application layer 520 only after being processed by the transport layer. Consequently, 521 if TCP is used then this may introduce additional and unpredictable 522 delays on top of the unavoidable network delays. (However, if UDP 523 is used then this is not a problem.) 525 5. Security Considerations 527 See the academic publications on TESLA [8,14,20] for several security 528 analyses. Regarding the security of implementations, by far the most 529 delicate point is the verification of the timing conditions. Care 530 should be taken to to make sure that: 531 (a) The value bound D_t on the clock skew is calculated according to the 532 spec at session set-up. 533 (b) The receiver records the arrival time of the packet as soon as possible 534 after the packet's arrival, and computes the safety condition correctly. 536 6 Acknowledgments 538 We would like to thank Mike Luby for his feedback and support. 540 7 Bibliography 542 [1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet 543 Request for Comments RFC 2246, January 1999. Proposed standard. 545 [2] Ipsec, "IP Security Protocol, IETF working group." 546 http://www.ietf.org/html.charters/ipsec-charter.html. 548 [3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast 549 message authentication," in Advances in Cryptology -- EUROCRYPT '2001 550 (B. Pfitzmann, ed.), vol. 2045 of Lecture Notes in Computer Science , 551 (Innsbruck, Austria), pp. 434--450, Springer-Verlag, Berlin Germany, 552 2001. 554 [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech. 555 rep., IBM T.J.Watson Research Center, 1997. 557 [5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul� 558 ticast packet authentication," in 6th ACM Conference on Computer and 559 Communications Security , November 1999. 561 [6] P. Rohatgi, "A hybrid signature scheme for multicast source 562 authentication," Internet Draft, Internet Engineering Task Force, 563 June 1999. Work in progress. 565 [7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul� 566 ticasts," in Proc. IEEE ICNP `98 , 1998. 568 [8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient 569 authentication and signing of multicast streams over lossy channels," 570 in IEEE Symposium on Security and Privacy , May 2000. 572 [9] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. 573 Pinkas, "Multicast security: A taxonomy and some efficient construc� 574 tions," in Infocom '99 , 1999. 576 [10] S. Cheung, "An efficient message authentication scheme for link 577 state routing," in 13th Annual Computer Security Applications Confer� 578 ence , 1997. 580 [11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream 581 authentication," in Selected Areas in Cryptography 2000 , (Waterloo, 582 Canada), August 2000. A talk describing this scheme was given at IBM 583 Watson in August 1998. 585 [12] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single 586 source authentication on the mbone," in ICME 2000 , Aug 2000. A talk 587 containing this work was given at IBM Watson, August 1998. 589 [13] A. Perrig and J. D. Tygar, Secure Broadcast Communication in 590 Wired and Wireless Networks Kluwer Academic Publishers, Oct. 2002. 591 ISBN 0792376501. 593 [14] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla 594 broadcast authentication protocol," RSA CryptoBytes , vol. 5, no. 595 Summer, 2002. 597 [15] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and 598 secure source authentication for multicast," in Network and Dis� 599 tributed System Security Symposium, NDSS '01 , pp. 35--46, February 600 2001. 602 [16] D. L. Mills, "Network Time Protocol (Version 3) Specification, 603 Implementation and Analysis." Internet Request for Comments, March 604 1992. RFC 1305. 606 [17] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of 607 clock synchronization," in Fault-Tolerant Distributed Computing (B. 608 Simons and A. Spector, eds.), no. 448 in LNCS, pp. 84--96, Springer- 609 Verlag, Berlin Germany, 1990. 611 [18] D. Mills, "Improved algorithms for synchronizing computer net� 612 work clocks," in Proceedings of the conference on Communications 613 architectures, protocols and applications, SIGCOMM 94 , (London, 614 England), pp. 317--327, 1994. 616 [19] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the 617 presence of faults," J. ACM , vol. 32, no. 1, pp. 52--78, 1985. 619 [20] Philippa Broadfoot and Gavin Lowe, "Analysing a Stream 620 Authentication Protocol using Model Checking. In Proceedings of the 621 7th European Symposium on Research in Computer Security (ESORICS), 622 2002. 624 A Author Contact Information 626 Adrian Perrig 627 ECE Department 628 Carnegie Mellon University 629 Pittsburgh, PA 630 US 631 perrig@ece.cmu.edu 633 Ran Canetti 634 IBM Research 635 30 Saw Mill River Rd 636 Hawthorne, NY 10532 637 US 638 canetti@watson.ibm.com 640 Dawn Song 641 CS Department 642 Carnegie Mellon University 643 Pittsburgh, PA 644 US 645 dawnsong@cmu.edu 647 Doug Tygar 648 UC Berkeley 650 102 South Hall, 4600 651 Berkeley, CA 94720-4600 652 US 653 tygar@cs.berkeley.edu 655 Bob Briscoe 656 BT Research 657 B54/74, BT Labs 658 Martlesham Heath 659 Ipswich, IP5 3RE 660 UK 661 bob.briscoe@bt.com 662 B Full Copyright Statement 664 Copyright (C) The Internet Society (2000). All Rights Reserved. 666 This document and translations of it may be copied and furnished to 667 others, and derivative works that comment on or otherwise explain it 668 or assist in its implementation may be prepared, copied, published 669 and distributed, in whole or in part, without restriction of any 670 kind, provided that the above copyright notice and this paragraph are 671 included on all such copies and derivative works. However, this doc� 672 ument itself may not be modified in any way, such as by removing the 673 copyright notice or references to the Internet Society or other 674 Internet organizations, except as needed for the purpose of develop� 675 ing Internet standards in which case the procedures for copyrights 676 defined in the Internet languages other than English. 678 The limited permissions granted above are perpetual and will not be 679 revoked by the Internet Society or its successors or assigns. 681 This document and the information contained herein is provided on an 682 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 683 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 684 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 685 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER� 686 CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."