idnits 2.17.1 draft-ietf-msec-tesla-intro-01.txt: -(22): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(32): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(33): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(34): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(35): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(41): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(78): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(84): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(94): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(107): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(111): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(126): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(128): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(147): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(167): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(175): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(182): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(185): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(201): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(208): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(224): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(232): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(253): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(267): 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 -(274): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(288): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(299): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(317): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(319): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(327): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(345): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(420): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(429): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(450): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(454): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(457): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(486): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(494): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(502): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(506): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(542): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(595): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(598): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(609): 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 6 months document validity -- 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 69 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 1 longer page, the longest (page 10) being 66 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** 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 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 193: '...and the receiver MUST be loosely time ...' RFC 2119 keyword, line 195: '...e, but the receiver MUST know an upper...' RFC 2119 keyword, line 207: '... 2. TESLA MUST be bootstrapped a...' RFC 2119 keyword, line 210: '... is REQUIRED to have an authe...' RFC 2119 keyword, line 215: '... tions). 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 367 has weird spacing: '...ure, we see ...' == Line 368 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 (27 October 2002) is 7852 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 471 looks like a reference -- Missing reference section? '2' on line 474 looks like a reference -- Missing reference section? '3' on line 477 looks like a reference -- Missing reference section? '4' on line 483 looks like a reference -- Missing reference section? '5' on line 486 looks like a reference -- Missing reference section? '6' on line 490 looks like a reference -- Missing reference section? '7' on line 494 looks like a reference -- Missing reference section? '8' on line 497 looks like a reference -- Missing reference section? '9' on line 501 looks like a reference -- Missing reference section? '10' on line 505 looks like a reference -- Missing reference section? '11' on line 509 looks like a reference -- Missing reference section? '12' on line 514 looks like a reference -- Missing reference section? '13' on line 518 looks like a reference -- Missing reference section? '14' on line 522 looks like a reference -- Missing reference section? '15' on line 526 looks like a reference -- Missing reference section? '16' on line 531 looks like a reference -- Missing reference section? '17' on line 535 looks like a reference -- Missing reference section? '18' on line 540 looks like a reference -- Missing reference section? '19' on line 545 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 6 warnings (==), 21 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-01.txt UC Berkeley/Digital Fountain/IBM/BT 5 27 October 2002 6 Expires: 27 April 2002 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 mate� 23 rial 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 authen� 33 tication mechanism for multicast or broadcast data streams. This doc� 34 ument provides an algorithmic description of the scheme for informa� 35 tional purposes, and in particular, it is intended to assist in writ� 36 ing standardizable and secure specifications for protocols based on 37 TESLA in different contexts. 39 The main deterrents so far for a data authentication mechanism for 40 multicast were the seemingly conflicting requirements: loss toler� 41 ance, high efficiency, no per-receiver state at the sender. The prob� 42 lem 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 2 Functionality . . . . . . . . . . . . . . . . . . . . . . 3 56 2.1 Threat Model and Security Guarantee . . . . . . . . . . . 4 57 2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5 58 3 Notation . . . . . . . . . . . . . . . . . . . . . . . . 5 59 4 The Basic TESLA Protocol . . . . . . . . . . . . . . . . 5 60 4.1 Sketch of protocol . . . . . . . . . . . . . . . . . . . 6 61 4.2 Sender Setup . . . . . . . . . . . . . . . . . . . . . . 7 62 4.3 Bootstrapping Receivers . . . . . . . . . . . . . . . . . 7 63 4.4 Broadcasting Authenticated Messages . . . . . . . . . . . 8 64 4.5 Authentication at Receiver . . . . . . . . . . . . . . . 8 65 4.6 Determining the Key Disclosure Delay . . . . . . . . . . 9 66 4.7 Some extenstions. . . . . . . . . . . . . . . . . . . . . 10 67 5 Layer placement . . . . . . . . . . . . . . . . . . . . . 10 68 6 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 10 69 7 Bibliography . . . . . . . . . . . . . . . . . . . . . . 10 70 A Author Contact Information . . . . . . . . . . . . . . . 12 71 B Full Copyright Statement . . . . . . . . . . . . . . . . 13 73 1 Introduction 75 The power of multicast is that one packet can reach millions of 76 receivers. This great property is unfortunately also a great danger: 77 an attacker that sends one malicious packet can also potentially 78 reach millions of receivers. Receivers need multicast source authen� 79 tication to ensure that a given packet originates from the correct 80 source. 82 In unicast communication, we can achieve data authentication through 83 a purely symmetric mechanism: the sender and the receiver share a 84 secret key to compute a message authentication code (MAC) of all com� 85 municated data. When a message with a correct MAC arrives, the 86 receiver is assured that the sender generated that message. Standard 87 mechanisms achieve unicast authentication this way, for example TLS 88 or IPsec [1,2]. 90 The symmetric MAC authentication is not secure in a broadcast set� 91 ting. Consider a sender that broadcasts authentic data to mutually 92 untrusted receivers. The symmetric MAC is not secure: every receiver 93 knows the MAC key, and hence could impersonate the sender and forge 94 messages to other receivers. Intuitively, we need an asymmetric mech� 95 anism to achieve authenticated broadcast, such that every receiver 96 can verify the authenticity of messages it receives, without being 97 able to generate authentic messages. Achieving this in an efficient 98 way is a challenging problem [3]. 100 The standard approach to achieve such asymmetry for authentication is 101 to use asymmetric cryptography, for instance a digital signature. 102 Digital signatures have the required asymmetric property: the sender 103 generates the signature with its private key, and all receivers can 104 verify the signature with the sender's public key, but a receiver 105 with the public key alone cannot generate a digital signature for a 106 new message. A digital signature provides non-repudiation, which is a 107 stronger property than authentication. Unfortunately, digital signa� 108 tures have a high cost: they have a high computation overhead for 109 both the sender and the receiver, as well as a high communication 110 overhead. Since we assume broadcast settings where the sender does 111 not retransmit lost packets, and the receiver still wants to immedi� 112 ately authenticate each packet it receives, we would need to attach a 113 digital signature to each message. Because of the high overhead of 114 asymmetric cryptography, this approach would restrict us to low-rate 115 streams, and to senders and receivers with powerful workstations. To 116 deal with the high overhead of asymmetric cryptography, we can try to 117 amortize one digital signature over multiple messages. However, such 118 an approach is still expensive in contrast to symmetric cryptography, 119 since symmetric cryptography is in general 3 to 5 orders of magnitude 120 more efficient than asymmetric cryptography. In addition, the 121 straight-forward amortization of one digital signature over multiple 122 packets requires reliability, as the receiver needs to receive all 123 packets to verify the signature. A number of schemes that follow this 124 approach are [4,5,6,7,8]. See [9] for more details. 126 This draft presents the Timed Efficient Stream Loss-tolerant Authen� 127 tication protocol (TESLA). TESLA uses mainly symmetric cryptography, 128 and uses time delayed key disclosure to achieve the required asymme� 129 try property. However, TESLA requires loosely synchronized clocks 130 between the sender and the receivers. See more details in Section 4. 131 Other schemes that follow a similar approach to TESLA are [10,11,12]. 133 2 Functionality 135 TESLA provides delayed per-packet data authentication. The key idea 136 to providing both efficiency and security is a delayed disclosure of 137 keys. The delayed key disclosure results in an authentication delay. 138 In practice, the delay is on the order of one RTT (Round-trip-time). 140 TESLA has the following properties: 142 � Low computation overhead for generation and verification of 143 authentication information 145 � Low communication overhead 147 � Limited buffering required for the sender and the receiver, hence 148 timely authentication for each individual packet 150 � Strong robustness to packet loss 152 � Scales to a large number of receivers 154 � Security is guaranteed as long as the sender and recipients are 155 loosely time synchronized, where synchronization can take place 156 at session set-up. 158 TESLA can be used both in the network layer or in the application 159 layer. The delayed authentication, however, requires buffering of 160 packets until authentication is completed. 162 2.1 Threat Model and Security Guarantee 164 We design TESLA to be secure against a powerful adversary with the 165 following capabilities: 167 � Full control over the network. The adversary can eavesdrop, cap� 168 ture, drop, resend, delay, and alter packets. 170 � Access to a fast network with negligible delay. 172 � The adversary's computational resources may be very large, but 173 not unbounded. In particular, this means that the adversary can 174 perform efficient computations, such as computing a reasonable 175 number of pseudo-random function applications and MACs with neg� 176 ligible delay. Nonetheless, the adversary cannot find the key of 177 a pseudorandom function (or distinguish it from a random func� 178 tion) with non-negligible probability. 180 The security property of TESLA guarantees that the receiver never 181 accepts M_i as an authentic message unless the sender really sent 182 M_i. A scheme that provides this guarantee is called a secure broad� 183 cast authentication scheme. 185 Since TESLA requires the receiver to buffer packets before authenti� 186 cation, the receiver needs to protect itself from a potential denial- 187 of-service (DOS) attack due to a flood of bogus packets. 189 2.2 Assumptions 191 TESLA makes the following assumptions in order to provide security: 193 1. The sender and the receiver MUST be loosely time synchronized. 194 Loosely time synchronized means that the synchronization does 195 not need to be precise, but the receiver MUST know an upper 196 bound on the dispersion (the maximum clock offset). For the 197 purposes of this draft, we assume that the receiver knows the 198 maximum clock offset between its clock and the sender's clock, 199 which we denote with D_t. We stress that the sender and 200 receiver's clock do not need to be synchronized a-priori. 201 Instead, the receiver can easily achieve the required synchro� 202 nization through a two-round message exchange with the sender. 203 (This stands in contrast with authentication protocols based 204 on timestamps. In those protocols, the participants are 205 assumed to have the same global time a-priori.) 207 2. TESLA MUST be bootstrapped at session set-up through a regular 208 data authentication system. We recommend to use a digital sig� 209 nature algorithm for this purpose, in which case the receiver 210 is REQUIRED to have an authentic copy of either the sender's 211 public key certificate or a root key certificate in case of a 212 PKI (public-key infrastructure). 214 3. TESLA uses cryptographic MAC and PRF (pseudo-random func� 215 tions). These MUST be cryptographically secure. Further 216 details on the instantiation of the MAC and PRF are in Section 217 4.2. 219 4. We would like to emphasize that the security of TESLA does NOT 220 rely on any assumptions on network propagation delay. 222 3 Notation 224 To denote the subscript or an index of a variable, we use the under� 225 score between the variable name and the index, e.g. the key K with 226 index i is K_i, the key K with index i+d is K_{i+d}. To write a 227 superscript we use the caret, e.g. the function F with the argument x 228 executed i times is F^i(x), executed j-1 times we write F^{j-1}(x). 230 4 The Basic TESLA Protocol 232 TESLA is described in several academic publications: A book on broad� 233 cast security [13], a journal paper [14], and two conference papers 235 [8,15]. Please refer to these publications for an in-depth treatment. 237 4.1 Sketch of protocol 239 We first outline the main ideas behind TESLA. 241 As we argue in the introduction, broadcast authentication requires a 242 source of asymmetry. TESLA uses time for asymmetry. We assume that 243 the sender and receivers are all loosely time synchronized -- up to 244 some D_t value, all parties agree on the current time. The sender 245 forms a one-way chain, where each such value is associated with a 246 time interval (say, a second). Here is the basic approach: 248 � The sender attaches a MAC to each packet. The MAC is computed 249 over the contents of the packet. For each packet, the sender uses 250 the current value from the one-way chain as a cryptographic key 251 to compute the MAC. 253 � Each receiver receives the packet. Each receiver knows the sched� 254 ule for disclosing keys and, since the clocks are loosely syn� 255 chronized, can check that the key used to compute the MAC is 256 still secret by determining that the sender could not have yet 257 reached the time for disclosing it. If the MAC key is still 258 secret, then the receiver buffers the packet. 260 � According to a schedule, the sender discloses the key from the 261 one-way chain. 263 � Each receiver checks that the disclosed key is correct (using 264 previously released keys) and then checks the correctness of the 265 MAC. If the MAC is correct, the receiver accepts the packet. 267 Note that one way chains have the property that if intermediate val� 268 ues of the one-way chain are lost, they can be recomputed using the 269 following values. So, even if some key disclosures are lost, a 270 receiver can recover the key chain and check the correctness of ear� 271 lier packets. 273 The sender distributes a stream of messages {M_i}, and the sender 274 sends each message M_i in a network packet P_i along with authentica� 275 tion information. The broadcast channel may be lossy, but in many 276 broadcast applications the sender does not retransmit lost packets. 277 Despite packet loss, each receiver needs to authenticate every mes� 278 sage it receives. 280 We now describe the stages of the basic TESLA protocol in this order: 281 sender setup, receiver bootstrap, sender transmission of authenti� 282 cated broadcast messages, and receiver authentication of broadcast 283 messages. 285 4.2 Sender Setup 287 The sender divides the time into uniform intervals of duration T_int. 288 The sender assigns one key from the one-way chain to each time inter� 289 val in sequence. 291 The sender determines the length N of the one-way chain K_0, K_1, 292 ..., K_N, and this length limits the maximum transmission duration 293 before a new one-way chain must be created. The sender picks a random 294 value for K_N. Using a pseudo-random function (PRF) f, the sender 295 constructs the one-way function F: F(k) = f_k(0). The rest of the 296 chain is computed recursively using K_i = F(K_{i+1}). Note that this 297 gives us K_i = F^{N-i}(K_N), so the receiver can compute any value in 298 the key chain from K_N even if is does not have intermediate values. 299 The key K_i will be used to authenticate packets sent in time inter� 300 val i. 302 4.3 Bootstrapping Receivers 304 Before a receiver can authenticate messages with TESLA, it needs to 305 be loosely time synchronized with the sender, know the disclosure 306 schedule of keys, and receive an authenticated key of the one-way key 307 chain. 309 Various approaches exist for time synchronization [16,17,18,19]. 310 TESLA, however, only requires loose time synchronization between the 311 sender and the receivers, so a simple algorithm is sufficient. The 312 time synchronization property that TESLA requires is that each 313 receiver can place an upper bound of the senders local time. TESLA 314 offers direct, indirect, and delayed synchronization as three default 315 options, which we will describe in the TESLA technical draft. 317 The sender sends the key disclosure schedule by transmitting the fol� 318 lowing information to the receivers over an authenticated channel 319 (either via a digitally signed broadcast message, or over an authen� 320 ticated unicast channel with each receiver): 322 � Time interval schedule: interval duration T_int, start time and 323 index of interval i, length of one-way key chain. 325 � Key disclosure delay d (number of intervals). 327 � A key 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 draft. Time synchronization 333 can be performed as part of the registration protocol between member 334 and sender. 336 4.4 Broadcasting Authenticated Messages 338 Each key in the one-way key chain corresponds to a time interval. 339 Every time a sender broadcasts a message, it appends a MAC to the 340 message, using the key corresponding to the current time interval. 341 The key remains secret for the next d-1 intervals, so messages a 342 sender broadcasts in interval j effectively disclose key K_j-d. We 343 call d the key disclosure delay. 345 We do not want to use the same key multiple times in different cryp� 346 tographic operations, that is, to use key K_j to derive the previous 347 key of the one-way key chain K_{j-1}, and to use the same key K_j as 348 the key to compute the MACs in time interval j may potentially lead 349 to a cryptographic weakness. Using a pseudo-random function (PRF) 350 f', we construct the one-way function F': F'(k) = f'_k(1). We use F' 351 to derive the key to compute the MAC of messages in each interval. 352 The sender derives the MAC key as follows: K'_i = F'(K_i). Figure 1 353 depicts the one-way key chain construction and MAC key derivation. To 354 broadcast message M_j in interval i the sender constructs packet P_j 355 = {M_j || MAC(K'_i,M_j) || K_{i-d}}, where || denotes concatenation. 357 F(K_i) F(K_{i+1}) F(K_{i+2}) 358 K_{i-1} <------- K_i <--------- Ki+1 <------- 360 | | | 361 | F'(K_{i-1}) | F'(K_i) | F'(K_{i+1}) 362 | | | 363 V V V 365 K'_{i-1} K'_i K'_{i+1} 367 Figure 1: At the top of the figure, we see the one-way key chain 368 (derived using the one-way function F), and the derived MAC keys 369 (derived using the one-way function F'). 371 4.5 Authentication at Receiver 372 Once a sender discloses a key, we must assume that all parties might 373 have access to that key. An adversary could create a bogus message 374 and forge a MAC using the disclosed key. So whenever a packet 375 arrives, the receiver must verify that the MAC is based on a safe 376 key; a safe key is one that is still secret (only known by the 377 sender). We define a safe packet or safe message to be one with a MAC 378 that is computed with a safe key. 380 If the packet is not safe, the receiver must discard that packet, 381 because the authenticity is not assured any more. 383 We now explain the TESLA authentication in more detail. When the 384 receiver receives packet P_j sent in interval i, the receiver com� 385 putes an upper bound on the sender's clock: t_j. To test whether the 386 packet is safe, the receiver computes the highest interval x the 387 sender could possibly be in, namely x = floor((t_j - T_0) / T_int). 388 The receiver verifies that x < i + d (where i is the interval index), 389 which implies that the sender is not yet in the interval during which 390 it discloses the key K_i. 392 The receiver cannot yet verify the authenticity of packets sent in 393 interval i without key K_i. Instead, it adds the triplet ( i, M_j, 394 MAC( K'_i, M_j) ) to a buffer, and verifies the authenticity after it 395 learns K'_i. 397 What does a receiver do when it receives the disclosed key K_i? 398 First, it checks whether it already knows K_i or a later key K_j 399 (j>i). If K_i is the latest key received to date, the receiver checks 400 the legitimacy of K_i by verifying, for some earlier key K_v (v1, 407 the receiver can also verify the authenticity of the stored packets 408 of intervals v+1 ... i-1. 410 Note that the security of TESLA does not rely on any assumptions on 411 network propagation delay. 413 4.6 Determining the Key Disclosure Delay 415 An important TESLA parameter is the key disclosure delay d. Although 416 the choice of the disclosure delay does not affect the security of 417 the system, it is an important performance factor. A short disclosure 418 delay will cause packets to loose their safety property, so receivers 419 will discard them; but a long disclosure delay leads to a long 420 authentication delay for receivers. We recommend choosing the disclo� 421 sure delay as follows: in direct time synchronization let the RTT be 422 a reasonable upper bound on the round trip time between the sender 423 and the receiver; then choose d = ceil( RTT / T_int) + 1. Note that 424 rounding up the quotient ensures that d >= 2. Also note that a dis� 425 closure delay of one time interval (d=1) does not work. Consider 426 packets sent close to the boundary of the time interval: after the 427 network propagation delay and the receiver time synchronization 428 error, a receiver will need to discard the packet, because the sender 429 will already be in the next time interval, when it discloses the cor� 430 responding key. 432 4.7 Some extenstions 434 Let us mention two salient extenstions of the basic TESLA scheme. 435 A first extension allows having multiple TESLA authentication chains 436 for a single stream, where each chain uses a different delay for 437 disclosing the keys. This extension is typically used to deal with 438 heterogenous network delays withing a single multicast transmission. 439 A second extension allows having most of the buffering of packets 440 at the sender side (rather than at the receiver side). Both 441 extensions are described in [15]. 443 5 Layer placement 445 The TESLA authentication can be performed at any layer in the net� 446 working stack. The two logical places are in the network or the 447 application layer. We list some considerations regarding the choice 448 of layer: 450 � Performing TESLA in the network layer has the advantage that the 451 transport or application layer only receives authenticated data, 452 potentially aiding a reliability protocol and preventing denial- 453 of-service attacks. (Indeed, reliable multicast tools based on 454 forward error correction are highly susceptible to denial of ser� 455 vice due to bogus packets.) 457 � Performing TESLA in the application layer has the advantage that 458 the network layer remains unchanged; but it has the drawback that 459 packets are obtained by the application layer only after being 460 processed by the transport layer. Consequently, if TCP is used 461 then this may introduce additional and unpredictable delays on 462 top of the unavoidable network delays. (However, if UDP is used 463 then this is not a problem.) 465 6 Acknowledgments 467 We would like to thank Mike Luby for his feedback and support. 469 7 Bibliography 471 [1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet 472 Request for Comments RFC 2246, January 1999. Proposed standard. 474 [2] Ipsec, "IP Security Protocol, IETF working group." 475 http://www.ietf.org/html.charters/ipsec-charter.html. 477 [3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast 478 message authentication," in Advances in Cryptology -- EUROCRYPT '2001 479 (B. Pfitzmann, ed.), vol. 2045 of Lecture Notes in Computer Science , 480 (Innsbruck, Austria), pp. 434--450, Springer-Verlag, Berlin Germany, 481 2001. 483 [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech. 484 rep., IBM T.J.Watson Research Center, 1997. 486 [5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul� 487 ticast packet authentication," in 6th ACM Conference on Computer and 488 Communications Security , November 1999. 490 [6] P. Rohatgi, "A hybrid signature scheme for multicast source 491 authentication," Internet Draft, Internet Engineering Task Force, 492 June 1999. Work in progress. 494 [7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul� 495 ticasts," in Proc. IEEE ICNP `98 , 1998. 497 [8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient 498 authentication and signing of multicast streams over lossy channels," 499 in IEEE Symposium on Security and Privacy , May 2000. 501 [9] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. 502 Pinkas, "Multicast security: A taxonomy and some efficient construc� 503 tions," in Infocom '99 , 1999. 505 [10] S. Cheung, "An efficient message authentication scheme for link 506 state routing," in 13th Annual Computer Security Applications Confer� 507 ence , 1997. 509 [11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream 510 authentication," in Selected Areas in Cryptography 2000 , (Waterloo, 511 Canada), August 2000. A talk describing this scheme was given at IBM 512 Watson in August 1998. 514 [12] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single 515 source authentication on the mbone," in ICME 2000 , Aug 2000. A talk 516 containing this work was given at IBM Watson, August 1998. 518 [13] A. Perrig and J. D. Tygar, Secure Broadcast Communication in 519 Wired and Wireless Networks Kluwer Academic Publishers, Oct. 2002. 520 ISBN 0792376501. 522 [14] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla 523 broadcast authentication protocol," RSA CryptoBytes , vol. 5, no. 524 Summer, 2002. 526 [15] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and 527 secure source authentication for multicast," in Network and Dis� 528 tributed System Security Symposium, NDSS '01 , pp. 35--46, February 529 2001. 531 [16] D. L. Mills, "Network Time Protocol (Version 3) Specification, 532 Implementation and Analysis." Internet Request for Comments, March 533 1992. RFC 1305. 535 [17] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of 536 clock synchronization," in Fault-Tolerant Distributed Computing (B. 537 Simons and A. Spector, eds.), no. 448 in LNCS, pp. 84--96, Springer- 538 Verlag, Berlin Germany, 1990. 540 [18] D. Mills, "Improved algorithms for synchronizing computer net� 541 work clocks," in Proceedings of the conference on Communications 542 architectures, protocols and applications, SIGCOMM 94 , (London, Eng� 543 land), pp. 317--327, 1994. 545 [19] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the 546 presence of faults," J. ACM , vol. 32, no. 1, pp. 52--78, 1985. 548 A Author Contact Information 550 Adrian Perrig 551 UC Berkeley / Digital Fountain 552 102 South Hall 553 Berkeley, CA 94720 554 US 555 perrig@cs.berkeley.edu 557 Ran Canetti 558 IBM Research 559 30 Saw Mill River Rd 560 Hawthorne, NY 10532 561 US 562 canetti@watson.ibm.com 564 Dawn Song 565 UC Berkeley 566 387 Soda Hall, 1776 567 Berkeley, CA 94720-1776 568 US 569 dawnsong@cs.berkeley.edu 571 Doug Tygar 572 UC Berkeley 573 102 South Hall, 4600 574 Berkeley, CA 94720-4600 575 US 576 tygar@cs.berkeley.edu 578 Bob Briscoe 579 BT Research 580 B54/74, BT Labs 581 Martlesham Heath 582 Ipswich, IP5 3RE 583 UK 584 bob.briscoe@bt.com 586 B Full Copyright Statement 588 Copyright (C) The Internet Society (2000). All Rights Reserved. 590 This document and translations of it may be copied and furnished to 591 others, and derivative works that comment on or otherwise explain it 592 or assist in its implementation may be prepared, copied, published 593 and distributed, in whole or in part, without restriction of any 594 kind, provided that the above copyright notice and this paragraph are 595 included on all such copies and derivative works. However, this doc� 596 ument itself may not be modified in any way, such as by removing the 597 copyright notice or references to the Internet Society or other 598 Internet organizations, except as needed for the purpose of develop� 599 ing Internet standards in which case the procedures for copyrights 600 defined in the Internet languages other than English. 602 The limited permissions granted above are perpetual and will not be 603 revoked by the Internet Society or its successors or assigns. 605 This document and the information contained herein is provided on an 606 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 607 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 608 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 609 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER� 610 CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."