idnits 2.17.1 draft-irtf-smug-tesla-00.txt: -(180): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(186): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(213): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(351): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(357): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(361): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(364): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(386): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1267): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1434): 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? == There are 53 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard 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. ** There are 4 instances of too long lines in the document, the longest one being 9 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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 (17 November 2000) is 8554 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 1071 looks like a reference -- Missing reference section? '2' on line 1074 looks like a reference -- Missing reference section? '3' on line 1077 looks like a reference -- Missing reference section? '4' on line 1081 looks like a reference -- Missing reference section? '5' on line 1084 looks like a reference -- Missing reference section? '6' on line 1088 looks like a reference -- Missing reference section? '7' on line 1092 looks like a reference -- Missing reference section? '8' on line 1095 looks like a reference -- Missing reference section? '9' on line 1099 looks like a reference -- Missing reference section? '10' on line 1103 looks like a reference -- Missing reference section? '11' on line 1107 looks like a reference -- Missing reference section? '12' on line 1112 looks like a reference -- Missing reference section? '13' on line 1116 looks like a reference -- Missing reference section? '14' on line 1120 looks like a reference -- Missing reference section? '15' on line 1124 looks like a reference -- Missing reference section? '16' on line 1127 looks like a reference -- Missing reference section? '17' on line 1131 looks like a reference -- Missing reference section? '18' on line 1136 looks like a reference -- Missing reference section? '19' on line 1139 looks like a reference -- Missing reference section? '20' on line 1409 looks like a reference -- Missing reference section? '21' on line 1148 looks like a reference -- Missing reference section? '22' on line 1151 looks like a reference -- Missing reference section? '23' on line 1317 looks like a reference -- Missing reference section? '24' on line 1317 looks like a reference -- Missing reference section? '25' on line 1162 looks like a reference -- Missing reference section? '26' on line 1388 looks like a reference -- Missing reference section? '27' on line 1169 looks like a reference -- Missing reference section? '28' on line 1188 looks like a reference -- Missing reference section? '29' on line 1229 looks like a reference -- Missing reference section? '30' on line 1324 looks like a reference Summary: 6 errors (**), 0 flaws (~~), 3 warnings (==), 32 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force IRTF SMUG 2 Internet Draft Perrig, Canetti, Briscoe, Tygar, Song 3 draft-irtf-smug-tesla-00.txt UC Berkeley / Digital Fountain / IBM / BT 4 17 November 2000 5 Expires: 17 June 2001 7 TESLA: Multicast Source Authentication Transform 9 STATUS OF THIS MEMO 11 This document is an Internet-Draft and is in full conformance with 12 all provisions of Section 10 of RFC2026. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as Internet- 17 Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet-Drafts as reference mate- 22 rial or to cite them other than as "work in progress". 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 Abstract 32 This document describes TESLA, a secure sender authentication mecha- 33 nism for multicast or broadcast data streams. Data authentication is 34 an important component for many applications, for example audio and 35 video Internet broadcasts, or data distribution by satellite. 37 The main deterrents so far for a data authentication mechanism for 38 multicast were the seemingly conflicting requirements: loss toler- 39 ance, high efficiency, no per-receiver state at the sender. The prob- 40 lem is particularly hard in settings with high packet loss rates and 41 where lost packets are not retransmitted, and where the receiver 42 wants to authenticate each packet it receives. 44 TESLA provides authentication of individual data packets, regardless 45 of the packet loss rate. In addition, TESLA features low overhead for 46 both sender and receiver, and does not require per-receiver state at 47 the sender. TESLA is secure as long as the sender and receiver are 48 loosely time synchronized. 50 Table of Contents 52 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . 3 54 1.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 55 2 Rationale . . . . . . . . . . . . . . . . . . . . . . . . 3 56 3 Functionality . . . . . . . . . . . . . . . . . . . . . . 4 57 3.1 Threat Model and Security Guarantee . . . . . . . . . . . 5 58 3.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 5 59 4 Notation . . . . . . . . . . . . . . . . . . . . . . . . 6 60 5 Detailed TESLA Description . . . . . . . . . . . . . . . 6 61 5.1 Sender Setup . . . . . . . . . . . . . . . . . . . . . . 6 62 5.2 Bootstrapping a new Receiver . . . . . . . . . . . . . . 7 63 5.3 Sending Authenticated Packets . . . . . . . . . . . . . . 9 64 5.4 Receiver Tasks . . . . . . . . . . . . . . . . . . . . . 9 65 5.5 Multiple Authentication Instances . . . . . . . . . . . . 11 66 5.6 Immediate Authentication . . . . . . . . . . . . . . . . 12 67 5.7 TESLA Authentication Field Format for MESP . . . . . . . 14 68 5.8 TESLA for Authentication in other Protocols . . . . . . . 18 69 5.9 Security Discussion . . . . . . . . . . . . . . . . . . . 18 70 6 Implementation Considerations for the Sender . . . . . . 19 71 6.1 Choosing the disclosure delay . . . . . . . . . . . . . . 19 72 6.2 Choosing the interval duration . . . . . . . . . . . . . 19 73 6.3 Selecting a PRF and a MAC . . . . . . . . . . . . . . . . 20 74 6.4 Altering key chains on the fly . . . . . . . . . . . . . 20 75 7 Implementation Considerations for the Receiver . . . . . 21 76 7.1 Time Synchronization and Security Condition Issues . . . 21 77 7.2 Reconstruction of the key chain . . . . . . . . . . . . . 23 78 7.3 Protecting against Denial-of-Service Attacks . . . . . . 23 79 8 Acknowledgments . . . . . . . . . . . . . . . . . . . . . 23 80 9 Bibliography . . . . . . . . . . . . . . . . . . . . . . 23 81 A TESLA Attributes . . . . . . . . . . . . . . . . . . . . 26 82 B Time Synchronization Packet Format . . . . . . . . . . . 27 83 B.1 Direct Synchronization . . . . . . . . . . . . . . . . . 27 84 B.2 Indirect Synchronization . . . . . . . . . . . . . . . . 31 85 C Author Contact Information . . . . . . . . . . . . . . . 32 86 D Full Copyright Statement . . . . . . . . . . . . . . . . 34 88 1 Introduction 90 As the online population continues to expand, the Internet is 91 increasingly used to distribute streamed media, such as streamed 92 radio and video. We expect this trend to continue. 94 To enable a widespread and trusted streamed media dissemination, one 95 must first provide sufficient security guarantees. A most prominent 96 security risk from a user point of view is data authenticity. The 97 user needs assurance that the data stream originated from the pur- 98 ported sender. Otherwise, an attacker could replace parts of the 99 stream with its own material. For example, an adversary might alter 100 stock quotes that are distributed through IP multicast. In that sce- 101 nario, the receiver needs strong sender and data authentication. 103 The problem of continuous stream authentication is solved for the 104 case of one sender and one receiver via standard mechanisms, e.g. 105 [1,2]. The sender and receiver agree on a secret key which is used in 106 conjunction with a message authenticating code (MAC) to ensure 107 authenticity of each packet. In case of multiple receivers, however, 108 the problem becomes much harder to solve, because a symmetric 109 approach would allow anyone holding a key (that is, any receiver) to 110 forge packets. Alternatively, the sender can use digital signatures 111 to sign every packet with its private key. This solution provides 112 adequate authentication, but digital signatures are prohibitively 113 inefficient. 115 Real-time data streams are lossy, which makes the security problem 116 even harder. With many receivers, we typically have a high variance 117 among the bandwidth of the receivers, with high packet loss for the 118 receivers with relatively low bandwidth. Nevertheless, we want to 119 assure data authenticity even in the presence of high packet loss. 120 One of the main challenges is to ensure data authenticity of every 121 received packet, even though lost packets are not retransmitted. 123 1.1 Previous Work 125 A number of schemes for solving data authentication have been sug- 126 gested in the past few years [3,4,5,6,7,8,9,10,11]. An Internet 127 Draft based on [7] was proposed by McCarthy in 1998 but was not 128 updated. 130 This document is based mainly on the TESLA [8,9] and FLAMeS [10] 131 schemes, which have low computation and communication overhead. Sim- 132 ilar schemes were suggested by Cheung [12], and by Bergadano et al. 133 [11,13]. 135 1.2 Terminology 137 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 138 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 139 document are to be interpreted as described in RFC 2119 [14]. 141 2 Rationale 142 The authentication of broadcast data is an important building block 143 for settings that require source authentication. 145 The secure multicast group (SMuG) views multicast source authentica- 146 tion as one of the fundamental security services [15]. In particular, 147 an early SMuG draft mentions the multicast source authentication and 148 data integrity building block as one of four fundamental functional 149 building blocks [16]. 151 The recent multicast data security transformation draft also needs 152 source authentication [17]. The draft distinguishes between two data 153 authentication methods, namely the internal data authentication tag, 154 and the external authentication data. The former is encrypted with 155 the payload and the latter is outside of the encrypted data. TESLA 156 can be used in both cases. In this document, we propose TESLA as a 157 building block. We define the format of the authentication informa- 158 tion only, without committing to any specific packet format. 160 Source authentication is also required within the reliable multicast 161 transport (RMT) IETF group [18]. In particular, authentication is 162 required in the Asynchronous Layered Coding (ALC) draft [19]. TESLA 163 is ideally suited also in this setting to provide source authentica- 164 tion, possibly by incorporating it within AMESP and then in turn 165 incorporating AMESP within the ALC header. See details in [17]. 167 3 Functionality 169 TESLA provides delayed per-packet data authentication. The key idea 170 to provide both efficiency and security is a delayed disclosure of 171 keys. The delayed key disclosure results in an authentication delay. 172 In practice, the delay is on the order of one RTT (Round-trip-time). 174 TESLA has the following properties: 176 � Low computation overhead. The authentication involves typically 177 only one MAC function and one hash function computation per 178 packet, for both sender and receiver. 180 � Low per-packet communication overhead. Overhead can be as low as 181 12 bytes per packet. 183 � Arbitrary packet loss tolerated. Every packet which is received 184 in time can be authenticated. 186 � Unidirectional data flow. Data only flows from the sender to the 187 receiver. No acknowledgments or other messages are necessary 188 except for time synchronisation or for eventual initial connec- 189 tion setup. This implies that the sender's stream authentication 190 overhead is independent of the number of receivers, hence TESLA 191 is very scalable. 193 � No sender-side buffering. Every packet is sent as soon as it is 194 ready. 196 � High guarantee of authenticity. The system provides strong 197 authenticity. By strong authenticity we mean that the receiver 198 has a high assurance of authenticity, as long as our timing and 199 cryptographic assumptions are enforced. However, the scheme does 200 not provide non-repudiation. That is, the recipient cannot con- 201 vince a third party that the stream arrived from the claimed 202 source. 204 TESLA can be used both in the network layer or in the application 205 layer. The delayed authentication, however, requires buffering of 206 packets until authentication is completed. 208 3.1 Threat Model and Security Guarantee 210 We design TESLA to be secure against a powerful adversary with the 211 following capabilities: 213 � Full control over the network. The adversary can eavesdrop, cap- 214 ture, drop, resend, delay, and alter packets. 216 � Access to a fast network with negligible delay. 218 � The adversary's computational resources may be very large, but 219 not unbounded. In particular, this means that the adversary can 220 perform efficient computations, such as computing a reasonable 221 number of pseudo-random function applications and MACs with neg- 222 ligible delay. Nonetheless, the adversary cannot invert a pseudo- 223 random function (or distinguish it from a random function) with 224 non-negligible probability. 226 The security property TESLA guarantees is that the receiver never 227 accepts M_i as an authentic message unless M_i was actually sent by 228 the sender. A scheme that provides this guarantee is called a secure 229 stream authentication scheme. 231 3.2 Assumptions 233 For TESLA to be secure, the sender and the receiver ARE REQUIRED to 234 be loosely time synchronized. Loosely time synchronized means that 235 the synchronization does not need to be precise, but the receiver 236 MUST know an upper bound on the dispersion (the maximum clock 237 offset). TESLA supports two synchronization methods, direct and indi- 238 rect synchronization. In direct synchronization, the receiver syn- 239 chronizes its time directly with the data sender, in indirect syn- 240 chronization both the sender and the receiver synchronize their time 241 with a common time synchronization service. If the latter method is 242 used, we assume that secure time synchronization servers exist in the 243 network, for example NTP servers [20]. Finally, the clock of the 244 receiver MUST have known drift while receiving information from the 245 server and MUST be secure against alteration by an attacker. We would 246 like to emphasize that the security of TESLA does not rely on any 247 assumptions on network propagation delay. 249 TESLA also MUST be bootstrapped through a regular data authentication 250 system. We recommend to use a digital signature algorithm for this 251 purpose, in which case the receiver is REQUIRED to have an authentic 252 copy of either the sender's public key certificate or a root key cer- 253 tificate in case of a PKI (public-key infrastructure). 255 Finally, the MAC and pseudo-random functions MUST be cryptographi- 256 cally secure. Further details on the instantiation of the MAC and 257 PRF are in section 6.3. 259 4 Notation 261 To denote the subscript or an index of a variable, we use the under- 262 score between the variable name and the index, e.g. the key K with 263 index i is K_i, the key K with index i+d is K_{i+d}. To write a 264 superscript we use the caret, e.g. the function F with the argument x 265 executed i times is F^i(x), executed j-1 times we write F^{j-1}(x). 267 5 Detailed TESLA Description 269 In this section, we describe TESLA in detail. We first discuss our 270 threat model and the security guarantees that TESLA provides. Next we 271 describe the sender setup, the receiver bootstrapping process, fol- 272 lowed by the detailed sender receiver operations. 274 5.1 Sender Setup 276 In our model, a sender distributes a long message M as a stream of 277 small message chunks M_i (the i'th chunk of the message). Generally, 278 the sender sends each message chunk M_i in one network packet P_i. 280 For the purpose of TESLA, the sender splits the time up into even 281 intervals I_i, where the duration of each interval is Tint and the 282 starting time of an interval is TI_i. Trivially, we have TI_i = TI_0 283 + i * Tint. In each interval, the sender may send zero or multiple 284 packets. 286 Before sending the first message, the sender determines the sending 287 duration (possibly infinite), the interval duration, and the number N 288 of keys of the key chain. In section 6.1 and 6.2, we will go into 289 more detail about the choice of Tint and on the length of the hash 290 chain. This key chain is analogous to the one-way chain introduced 291 by Lamport [21], and the S/KEY authentication scheme [22]. The sender 292 then picks the last key K_N of the key chain randomly and pre-com- 293 putes the entire key chain using a pseudo-random function F, which is 294 by definition a one-way function. Each element of the chain is 295 defined as K_i = F(K_{i+1}). Each key can be derived from K_N as K_i 296 = F^{N-i}(K_N), where F^j(k) = F^{j-1}(F(k)) and F^0(k) = k. Each key 297 of the key chain corresponds to one interval (K_j is active in inter- 298 val I_j). 300 Since we do not want to use the same key multiple times in different 301 cryptographic operations, we use a second pseudo-random function F' 302 to derive the key which is used to compute the MAC of messages in 303 each interval. Hence, K'_i = F'(K_i). Figure 1 depicts this key 304 derivation. The choice of F and F' are detailed in section 6.3. 306 F(Ki) F(Ki+1) F(Ki+2) 307 Ki-1 <------- Ki <--------- Ki+1 <------- 309 | | | 310 | F'(Ki-1) | F'(Ki) | F'(Ki+1) 311 | | | 312 V V V 314 K'i-1 K'i K'i+1 316 Figure 1: TESLA key chain and the derived MAC keys 318 5.2 Bootstrapping a new Receiver 320 TESLA requires loosely synchronized clocks between the sender and the 321 receivers. Furthermore, TESLA requires an initially authenticated 322 data packet. This authentication is achieved with a digital signature 323 scheme, such as RSA [23], or DSA [24]. 325 We present two options for synchronizing the time. Either the 326 receiver directly synchronizes its time with the sender (direct syn- 327 chronization), or both the sender and receiver synchronize their time 328 with a third entity, a time server (indirect synchronization), for 329 example using NTP [20]. Both schemes (including their packet format) 330 are described in appendix B. Whatever time synchronization mechanism 331 is used, the receiver MUST know the dispersion (maximum clock offset) 332 after the time synchronization. 334 For both schemes, we assume that the sender's and receiver's clocks 335 have negligible drift, otherwise the receiver uses periodic re-syn- 336 chronization, or accounts for the drift with an increased d_t. 338 The receiver MUST receive the following authenticated information 339 about the time intervals and key chain: 341 � The beginning time of a specific interval TI_j 343 � The id of that interval I_j 345 � The interval duration Tint 347 � The number n of authentication instances per packet. Note that 348 all TESLA instances share the same time interval and key chain, 349 only the key disclosure delay is different for each instance. 351 � Key disclosure delay d_v of each authentication instance (unit is 352 interval) (1 <= v <= n) 354 � A publically known key K_i (i < j - d where j is the current 355 interval index) 357 � The interval of the last key chain element (key chain expiration) 359 � Total key chain length 361 � Indicate if immediate authentication is used, and how many hashes 362 of future data segments are added to each TESLA header. 364 � For each hash in the immediate authentication, the sender defines 365 the maximum distance in intervals that the hash value spans. Usu- 366 ally, this distance is equal to the maximum key disclosure delay. 368 The sender needs to define the parameters of the cryptographic primi- 369 tives that TESLA uses. The following parameters MUST be defined: 371 � The number n_1 of bits used for the key chain keys. 373 � A function F that is used to compute the key chain. Recall that 374 K_i = F(K_{i+1}). Hence F MUST take an input of size n_1 and map 375 it to an output of equal length. 377 � The number n_2 of bits used for the MAC key. 379 � A function F' to derive the MAC key from key chain keys. Recall 380 that K'_i = F'(K_i). F' takes an input of n_1 bits and outputs 381 n_2 bits. 383 � A MAC function that takes a key of length n_2 bits and data of 384 any length; and outputs a MAC of length n_3. 386 � A hash function H that is used for the immediate authentication. 387 H takes an input of arbitrary length and outputs n_4 bits. 389 Appendix A presents a list of the TESLA attributes. 391 For each of these values, n_i needs to be smaller or equal length 392 than the function that generates the parameter. If the required out- 393 put is smaller, we truncate is as specified in RFC 2104 [25]. 395 If the sender and the receiver are already time synchronized, the 396 sender may periodically broadcast signed packets that contain the 397 above interval and key chain information. A new receiver would simply 398 wait for such a packet, authenticate it with traditional schemes, and 399 it can authenticate subsequent packets of the stream using TESLA. 400 This is particularly useful in the case of satellite broadcast, since 401 the receiver does not need to send any messages to the sender to 402 bootstrap the authentication. 404 5.3 Sending Authenticated Packets 406 Each key is used in one time interval. However many messages are sent 407 in each interval I_j, the key K_{j+d} is used to compute the MAC of 408 all those messages. This allows the sender to send packets at any 409 rate and to switch the sending rate dynamically. The key K_{j+d} 410 remains secret for d-1 future intervals and is disclosed in interval 411 I_{j+d}.. Packets sent in interval I_j can hence disclose key K_j. As 412 soon as the receivers receive that key, they can verify the authen- 413 ticity of the packets sent in interval I_{j-d}. Figure 2 shows the 414 time intervals and the arrows point from the interval to the interval 415 of which the key is disclosed. In the figure, d=2, hence packet P_2 416 sent in interval I_{j+3} discloses key K_{j+3}. From this key, the 417 receiver can also recover K_{j+2} and verify the MAC of P_1. 419 5.4 Receiver Tasks 421 Since the security of TESLA depends on keys that remain secret until 422 a pre-determined time period, the receiver MUST verify for each 423 packet that the key, which is used to compute the MAC of that packet, 424 _____ _____ 425 / \ / \ 426 / \ \ 427 / / \ \ 428 / / \ \ 429 V V \ \ 430 --+------+------+------+------+---> t 431 Ij Ij+1 Ij+2 Ij+3 433 Kj Kj+1 Kj+2 Kj+3 435 +----+ +----+ 436 | P1 | | P2 | 437 +----+ +----+ 439 Figure 2: TESLA intervals and key disclosure 441 is not yet published by the sender. Otherwise an attacker could have 442 changed the message data and re-computed the MAC. This motivates the 443 security condition, which the receiver MUST verify for each packet it 444 receives. 446 Security condition: A packet arrived safely, if the receiver is 447 assured (based on its synchronized time and d_t) that the sender is 448 not yet in the time interval in which the corresponding key is dis- 449 closed. 451 The formal definition of the security condition is in section 7.1. 452 The intuition is that no attacker could have altered the packet in 453 transit, because the corresponding MAC key is not yet disclosed by 454 the sender. In case the security condition is not valid, the receiver 455 MUST drop that packet, because the authenticity is not assured any 456 more. 458 This stream authentication scheme is secure as long as the security 459 condition holds. We would like to emphasize that the security of this 460 scheme does not rely on any assumptions on network propagation delay. 462 We can now explain how the authentication with TESLA works with a 463 concrete example. Figure 2 shows an example of two packets sent in 464 different intervals. When the receiver receives packet P_i sent in 465 interval I_j at time t_i (meaning the time the entire packet is 466 received), it first evaluates the security condition. For this, the 467 receiver computes the highest interval the sender could possibly be 468 in, in this case that interval is x = (t_i - TI_0 + d_t) / Tint. It 469 now needs to verify x < I_j + d (I_j is the interval index) which 470 means that the sender cannot be in the interval when the key K_j is 471 disclosed, hence no attacker can possibly know that key and spoof the 472 message contents. 474 Another property (could be called sanity condition) is that the 475 receiver can verify if the interval id I_j is possible and is not in 476 the future, i.e. if the sender can already be in that interval. The 477 verification condition is that the following MUST hold I_j < (t_i - 478 TI_0 + d_t) / Tint. This test prevents a denial-of-service attack 479 described in more detail in section 7.3. 481 The receiver cannot, however, verify the authenticity of the message 482 yet. Instead, it stores the triplet ( I_j, M_i, MAC( K'_j, M_i) ) to 483 verify the authenticity later when it knows K'_j. Two possibilities 484 exist on how to handle the unauthenticated message chunk M_i. The 485 first possibility is to hand M_i to the application, and notify it 486 through a callback mechanism as soon as M_i is verified. The second 487 possibility it to keep M_i until the authenticity can be checked and 488 pass it to the application as soon as M_i is authenticated. 490 If the packet contains a disclosed key, regardless of whether the 491 security condition is verified or not, the receiver checks whether it 492 can use K_{j-d} to authenticate previous packets. Clearly, if it has 493 received K_{j-d} previously, it does not have any work to do. Other- 494 wise, let us assume that the last key value in the reconstructed key 495 chain is K_{v}. The receiver verifies if K_{j-d} is legitimate by 496 applying the pseudo-random function F (j - d - v) -times and by veri- 497 fying that the result is indeed K_{v}. More formally, K_{v} == F^{j- 498 d-v}(K_{j-d}). If that condition is correct, the receiver updates the 499 key chain. For each new keys K_{w}, it computes K'_{w} = F'(K_w) 500 which might allow it to verify the authenticity of previously 501 received packets. 503 It is clear that this system can tolerate arbitrary packet loss, 504 because the receiver can verify the authenticity of all received 505 packets eventually. 507 5.5 Multiple Authentication Instances 509 The key disclosure period in TESLA presents a tradeoff. If the time 510 difference is short, the packet can be authenticated quickly, but if 511 the packet travel time is long the security condition will not hold 512 for remote receivers, which forces them to drop the packet. Con- 513 versely, a long time period will suit remote receivers, but the 514 authentication time delay may be unacceptable for receivers with fast 515 network access. Since the scheme needs to scale to a large number of 516 receivers and we expect the receivers to have a wide variety of net- 517 work access, we need to solve this tradeoff. Our approach is to use 518 multiple authentication instances with different disclosure periods 519 simultaneously. Each receiver can then use the instance with the min- 520 imal disclosure delay, sufficient to prevent spurious drops which are 521 caused if the security condition does not hold. 523 The receiver verifies one security condition for each authentication 524 instance C_i, and drops the packet if none of the conditions are sat- 525 isfied. Assume that the sender uses n authentication instances, where 526 the first instance has the smallest delay until the disclosure packet 527 is sent, and the nth instance has the longest delay. Furthermore, 528 assume that for the incoming packet P_j, the security conditions for 529 instances C_v (v < m) are not satisfied, and the condition for 530 instance C_m is satisfied. In this case, as long as the key disclo- 531 sure packets for the instances C_v (v < m ) arrive, the receiver's 532 confidence in the authenticity of packet P_j is increasing. As soon 533 as the key disclosure packet for a instance C_v (v >= m) arrives, the 534 receiver is assured of the authenticity of the packet P_j. 536 Instead of using one independent key chain per TESLA instance, we use 537 the same key chain and time interval for all instances, but each 538 instance has a different key disclosure delay. Each key K_i in the 539 key chain is associated with the corresponding time interval T_i, and 540 K_i will be disclosed in T_i. Assume that the sender uses n instances 541 of TESLA, which we denote with A_1 ... A_n. Each TESLA instance A_u 542 has a different key disclosure delay d_u, and it will have a MAC key 543 schedule derived from the key schedule shifted by d_u time intervals 544 from the key disclosure schedule. Let K^u_{i+d_u} denote the MAC key 545 used by instance u in time interval T_i. We derive K^u_{i+d_u} as 546 K^u_{i+d_u} = MAC(K_{i+d_u},u). The reason for generating all differ- 547 ent, independent keys for each instance is to prevent an attack where 548 an attacker moves the MAC value of an instance to another instance, 549 which might allow it to claim that data was sent in a different 550 interval. Our approach of generating independent keys prevents this 551 attack. Thus to compute the MAC value in packet P_j in time interval 552 T_i, the sender computes one MAC value of the message chunk M_j per 553 instance and append the MAC values to M_j. In particular, for the 554 instance A_u with disclosure delay d_u, the sender will now use the 555 key K^u_{i+d_u} as mentioned above for the MAC computation. 557 Figure 3 shows an example with two TESLA instances, one with a key 558 disclosure time of two intervals and the other of four intervals. The 559 lowest line of keys shows the key disclosure schedule, i.e. which key 560 is disclosed in which time interval. The middle and top line of keys 561 shows the key schedule of the first and second instance respectively, 562 i.e. which key is used to compute the MAC for the packets in the 564 K''_{j+4} K''_{j+5} K''_{j+6} K''_{j+7} K''_{j+8} MAC key inst 2 566 K'_{j+2} K'_{j+3} K'_{j+4} K'_{j+5} K'_{j+6} MAK key inst 1 568 K_j K_{j+1} K_{j+2} K_{j+3} K_{j+4} Disclosed key 570 +----------+-----------+-----------+-----------+-----------+---> t 572 I_j I_{j+1} I_{j+2} I_{j+3} I_{j+4} Interval # 574 Figure 3: TESLA intervals and key disclosure 576 given time interval for the given instance. Using this technique, the 577 sender will only need to disclose one key no matter how many 578 instances are used concurrently. 580 5.6 Immediate Authentication 582 A drawback of the basic TESLA protocol is that the receiver needs to 583 buffer packets during one disclosure delay before it can authenticate 584 them. This might not be practical for certain applications if the 585 receivers cannot afford much buffer space and bursty traffic might 586 cause the receivers to drop packets due to insufficient buffer space. 587 Moreover, as we show later in section 7.3, the requirement of 588 receiver buffering introduces a vulnerability to a denial-of-service 589 attack. To solve these problems caused by receiver-buffering, we pro- 590 pose a new method to support immediate authentication, which allows 591 the receiver to authenticate packets as soon as they arrive. 593 The basic observation of this method is that we can replace receiver 594 buffering with sender buffering. If the sender can buffer packets 595 during one disclosure delay, then it could store the hash value of 596 the data of a later packet in an earlier packet and hence as soon as 597 the earlier packet is authenticated, the data in the later packet is 598 authenticated through the hash value as well. 600 In the new scheme, the sender buffers packets for the duration of one 601 disclosure delay. For simplicity of illustration, we assume that the 602 sender sends out a constant number v of packets per time interval. To 603 construct the packet for the message chunk M_j in time interval T_i, 604 the sender appends the hash value of the message chunk M_{j+vd} to 605 M_j and then computes the MAC value also over H(M_{j+vd}) with the 606 key K_i. Figure 4 illustrates how the packet P_j is constructed by 607 - +-----------------------+ +-----------------------+- 608 / | M_j | /---> | M_{j+vd} | \ 609 D_j - +-----------------------+ / +-----------------------+ - D_{j+vd} 610 \ | H( M_{j+vd} ) | ---/ | H( M_{j+2vd} ) | / 611 - +-----------------------+ +-----------------------+- 612 | MAC( K'_i, D_j ) | <---\ | MAC(K'_{i+d},D_{j+vd})| 613 +-----------------------+ \ +-----------------------+ 614 | K_{i-d} | \--- | K_i | 615 +-----------------------+ +-----------------------+ 617 Figure 4: Immediate authentication packet example. D_j = H(M_{j+vd}) 618 | M_j and D_{j+vd} = H(M_{j+2vd}) | M_{j+vd}. 620 appending H(M_{j+vd}), MAC(K_i, M_j | H(M_{j+vd})), along with the 621 disclosed key K_{i-d}. (Note that the | stands for message concatena- 622 tion). When the packet P_{j+vd} arrives at the receiver which dis- 623 closes the key K_i it allows authentication of packet P_j sent in 624 interval I_i. P_j carries a hash of the data M_{j+vd} in P_{j+vd}. If 625 P_j is authentic, H(M_{j+vd}) is also authentic and therefore the 626 data M_{j+vd} is immediately authenticated. Also note that if P_j is 627 lost or dropped due to violation of the security condition, P_{j+vd} 628 will not be immediately authenticated and can still be authenticated 629 later using the MAC value. To achieve higher robustness to lost pack- 630 ets, the sender may add multiple hashes of future packets to the data 631 packet, as we show in the data format in the following section. 633 The above description assumes a constant sending rate, an assumption 634 which might not be the satisfied in practice. If the sending rate 635 varies, matching the hash to the data with simple counting does not 636 work any more. A simple solution would be to add the sequence number 637 of the packet that contains the data to the hash. Unfortunately, 638 this introduces overhead. A simple trick can save space in the TESLA 639 header. From the connection setup, the receiver knows for each hash 640 the interval in which the data will be sent in. Hence, to match the 641 hash to the data, the receiver stores for each future interval the 642 authenticated hashes that it received. For each incoming packet, the 643 receiver can compute the hash of the data and search if the corre- 644 sponding hash is present, which would immediately authenticate the 645 data. 647 5.7 TESLA Authentication Field Format for MESP 649 TESLA can be used to authenticate the content of a variety of proto- 650 cols. We discuss the format of the TESLA authentication field for the 651 case where it is used as the internal or external authentication 652 scheme in MESP [17]. The MESP (for Multicast ESP) header is proposed 653 as the header for authenticated and/or encrypted multicast traffic. 655 The approach of MESP for designing the packet format is to use a con- 656 nection setup phase in which the various parameters of the header 657 field are defined (such as authentication type and field lengths). 658 Hence, subsequent headers fields do not contain type or length infor- 659 mation. 661 Figure 5 shows the authentication data field format for authenticat- 662 ing message M_i. The fields have the following semantics. Note that 663 if the length of each field will be rounded up to the next byte 664 boundary. 666 � Disclosed key present flag (D): 1 bit 667 D=1 indicates that this packet discloses the key of a previous 668 interval. If D=0, the disclosed key is not present. 670 � Commitment to new key chain present flag (C): 1 bit 671 C=1 indicates that the commitment value of the next key chain is 672 present, only used shortly before switching to a new key chain. 673 The common case is that C=0 and the key is not present. Section 674 6.4 has more details on how to switch key chains. 676 � The last key from the previous key chain disclosed again flag 677 (L): 1 bit 678 L=1 indicates that the last key of the previous key chain is dis- 679 closed again. The common case is L=0 and the disclosed key is not 680 present. Section 6.4 has more details on how to switch key 681 chains. 682 *NOTE*: Since the size of the authentication field in MESP is 683 fixed, exactly one of these fields MUST be set to one (and there- 684 fore one of these fields MUST be present). 686 � Reserved (Res): 5 bits 687 All these bits MUST be set to 0. 689 � Disclosed key: n_1 bits if present 690 Disclosing the interval key is OPTIONAL, since any key can be 691 derived from a later interval key. The implementor needs to be 692 careful though since a sparse key disclosure can potentially lead 693 to an increased authentication delay. 695 0 1 2 3 696 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 697 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 698 |D|C|L| Res | | 699 +-+-+-+-+-+-+-+-+ [Disclosed Key K_i] or ~ 700 | [Commitment to new key] or | 701 ~ [Disclosed Key of previous chain] ~ 702 | | 703 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 704 | | 705 ~ [H( M_v1 )] ~ 706 | | 707 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 708 | | 709 ~ [H( M_v3 )] ~ 710 | | 711 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 712 | | 713 ~ [H( M_v2 )] ~ 714 | | 715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 716 | | 717 ~ Mac(K'_{i-d_1}, Di) ~ 718 | | 719 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 720 | | 721 ~ [Mac(K''_{i-d_2}, Di)] ~ 722 | | 723 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 724 | | 725 ~ [Mac(K'''_{i-d_3}, Di)] ~ 726 | | 727 ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 728 | | Padding (0-3 bytes) | 729 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 731 Figure 5: TESLA authentication field format in MESP 733 � Commitment to new key chain: n_1 bits if present 734 This field is OPTIONAL. When the key chain tapers off and the 735 sender wants to continue sending, the key chain needs to be 736 changed and a commitment to the new key chain is added to the 737 packet. It is implicit that the new chain will have the same 738 length as the old key chain. A more detailed discussion is in 739 section 6.4. 741 � Disclosed key from previous chain: n_2 bits if present 742 This field is OPTIONAL. Since the last key from the previous 743 chain cannot be recovered from the current keys, a receiver might 744 not have received the last key of a changed key chain, so it 745 might need to be retransmitted. See section 6.4 for details. 747 � H( M_vi ): n_4 bits 748 These fields are OPTIONAL. If immediate authentication is used, 749 the hashes of future data packets are present. From the connec- 750 tion setup, the receiver knows for each hash the interval in 751 which the data will be sent in. Hence, to match the hash to the 752 data, the receiver stores for each future interval the authenti- 753 cated hashes that it received. For each incoming packet, the 754 receiver can search if the corresponding hash is present, which 755 would immediately authenticate the data. 757 � MAC: n_3 bits 758 The MAC MUST be present in the packet. The MAC is computed over 759 all data that needs authentication, which we denote with D_i, so 760 MAC ( K'_j, D_i ). The MESP draft defines the data that is in D_i 761 for both the internal and external authentication the fields that 762 are included in the MAC. An exception, however, is that if the 763 TESLA header contains a commitment to a new key of a new key 764 chain, that key MUST be authenticated, hence it MUST be included 765 in the data part of the computation of the MAC. Another exception 766 are the hash value of the immediate authentication, which MUST 767 also be authenticated, and hence included in the MAC computation. 768 The format of the MAC computation is 769 MAC( K'_j, D_i [| K_{new chain}] [| h_1 | ... | h_m ]). 770 As mentioned, D_i corresponds to the data that needs to be 771 authenticated as described in [17]. If the commitment to the new 772 key chain is in the packet, it is included in the MAC computa- 773 tion, as well as the hashes of future data, if immediate authen- 774 tication is used. 776 � Padding: 0-3 bytes 777 Pads the authentication block to the next 4 byte boundary. The 778 padding field MUST be set to 0. 780 Note that no sequence number is present in the MESP version of the 781 TESLA header, because MESP already features sequence numbers. The 782 purpose of the sequence number is to filter out duplicates. Since 783 TESLA does not provide duplicate protection, the packet sequence num- 784 ber helps the TESLA implementation to filter out duplicate messages 785 for the receiver. Another method to remove duplicates is to use the 786 MAC of the message and remove messages that were sent in the same 787 interval and have identical MAC's. 789 Also, the header we present does not include an explicit interval 790 number. However, the receiver can infer the interval from the dis- 791 closed key. For reasonable implementations, changing key chains is 792 extremely rare, and hence almost all packets will contain the dis- 793 closed key that implicitly informs the receiver of the time interval. 794 Even if the disclosed key is not present, the receiver may infer the 795 time interval by a brute-force verification of which time interval 796 the packet was sent in. 798 5.8 TESLA for Authentication in other Protocols 800 Other authentication fields in other protocols may require different 801 formats for the TESLA authentication field. For example, the Asyn- 802 chronous Layer Coding (ALC) draft of the Reliable Multicast Group 803 (RMT) also has an authentication field in their header, which needs a 804 length and type field inside the authentication information [19]. It 805 is straightforward to adapt TESLA for this format. 807 It is also possible to use the AMESP format with TESLA authentication 808 (as described in Section 5.7) for the ALC authentication filed. See 809 more details in [17]. 811 5.9 Security Discussion 813 We briefly discuss potential security problems in this section and 814 show how we address them in TESLA. First, we note that a more rigor- 815 ous proof of security is detailed in [8]. 817 The main point is that an attacker can perform at most a denial-of- 818 service attack. Since we assume that the attacker has full control 819 over the network, a denial-of-service attack is always possible (the 820 attacker can simply drop or alter all packets). In the proof in [8] 821 we show that an attacker cannot forge a MAC or invert the key chain, 822 otherwise the attacker can break or invert the MAC function, which we 823 assume is not possible. Similarly, the attacker cannot alter the 824 packets undetectable, because she could not recompute the crypto- 825 graphically secure MAC. Consequently, creating new packets is not 826 possible either. 828 The security of TESLA is clearly compromised if an attacker could 829 alter the receiver's clock. Hence, we assume that this is not possi- 830 ble. However, how is the security of TESLA influenced by speeding up 831 or delaying individual packets? Delaying packets does not help, 832 since the worst that could happen is for the receiver to drop the 833 packet because it does not satisfy the security condition. Delaying 834 packets therefore results in a denial-of-service attack. On the other 835 hand, speeding up packets does not do anything at all. The receiver 836 even benefits from this since she might be able to use a chain with a 837 short disclosure delay that she could not use otherwise. 839 The packet replay attack is prevented by adding a sequence number to 840 each packet. Other measures against replay attacks are presented in 841 section 5.7. The TESLA layer in the network stack or in the applica- 842 tion will filter out duplicate packets. In any case, a duplication 843 would be possible only within a short time period, since the security 844 condition would cause packets to be dropped if they were duplicated 845 with a long delay. 847 6 Implementation Considerations for the Sender 849 This section discusses general implementation issues for the sender. 850 This discussion will assume that the sender uses one authentication 851 chain only. 853 6.1 Choosing the disclosure delay 855 The choice of the disclosure delay presents a tradeoff. If the dis- 856 closure delay is short, the packet can be authenticated quickly, but 857 if the packet travel time is long the security condition will not 858 hold for remote receivers, which forces them to drop the packet. Con- 859 versely, a long time period will suit remote receivers, but the 860 authentication time delay may be unacceptable for receivers with fast 861 network access. Since the scheme needs to scale to a large number of 862 receivers and we expect the receivers to have a wide variety of net- 863 work access, we need to address this tradeoff. 865 The first approach is to use multiple authentication chains, to 866 accommodate the heterogeneity of the receiver delays, described in 867 section 5.5. The problem remains how to choose the disclosure delay. 869 The main requirement for the disclosure delay is that the majority of 870 packets will validate the security condition. Suppose that an upper 871 bound on the dispersion of any client is d_t (maximum clock offset) 872 and the propagation delay of any (reasonable) client is at most d_p. 873 Usually the dispersion is also dependent on the propagation delay, in 874 practice d_t ~ RTT. For each packet, the receiver needs to verify 875 that the corresponding key was not disclosed yet at the moment the 876 packet arrives. Therefore, the disclosure delay D_d needs to be 877 longer than the sum of the dispersion and the propagation delay D_d > 878 d_t + d_p. 880 6.2 Choosing the interval duration 881 The interval duration affects other parameters of TESLA. One key is 882 necessary for each time interval, and due to the one-wayness of 883 pseudo-random functions, the sender needs to pre-compute the key 884 chain before sending packets. Consequently, a short interval dura- 885 tion and a long expected sending time will result in a longer pre- 886 computation time. 888 Another factor to consider for the interval duration is the accuracy 889 of the security condition. Because the time is sampled into inter- 890 vals, the security condition is evaluated using the interval as unit. 891 The finer-grained (or shorter) the interval duration is, the easier 892 it is to approximate the ideal disclosure duration. A simple example 893 illustrates this. The disclosure delay always needs to be longer than 894 one interval, because otherwise (assuming that the disclosure delay 895 is only one interval) packets that are sent close to an interval 896 boundary would always violate the security condition. To achieve at 897 least two intervals for the disclosure delay, the interval duration 898 should be shorter than half of the desired disclosure delay Tint < 899 D_d / 2. 901 The security is also influenced by the choice of the interval dura- 902 tion. The same key is used to compute the MAC of all packets sent in 903 that interval. If a large number of packets is sent in each interval, 904 an attacker can gather the packet-MAC pairs to attack the system. So 905 far, we are not aware of such an attack, but it is nevertheless pru- 906 dent to minimize the number of MAC computations that use an identical 907 key. 909 6.3 Selecting a PRF and a MAC 911 TESLA requires two pseudo-random functions, one to generate the key 912 chain and the other one to derive the MAC key from the key chain key. 913 Figure 1 shows both functions. A good choice is to use HMAC for this 914 purpose [25]. Any cryptographically secure hash function can be used 915 in conjunction with HMAC, for example MD5 [26], SHA-1 [27], or 916 RIPEMD-160. We propose the following constructs for our functions: 917 F(x) = HMAC(x, 0) and F'(x) = HMAC(x, 1). Note that the first parame- 918 ter to HMAC is the key and the second parameter is the data. For 919 TESLA, the key size is 80 bits and the parameters 0 and 1 are passed 920 as one-byte character (0x00 and 0x01 respectively). The output of 921 this function is truncated to 80 bits, we pick the 80 most signifi- 922 cant bits out of the 128 output bits. 924 Clearly, we also use HMAC for our MAC function. We simply have 925 MAC(k,d) = HMAC(k,d) and we use the 80 most significant bits. 927 6.4 Altering key chains on the fly 928 If a sender distributes the same information for a long time, the 929 pre-computed key chain can taper off. The question is how the sender 930 can seamlessly switch to a new key chain. A simplistic approach is 931 for the sender to stop using the old chain, send a new authenticated 932 packet that commits to the new chain and to subsequently use the new 933 chain only. The shortcoming of this scheme is that a receiver might 934 not receive the authenticated packet and could not authenticate sub- 935 sequent packets. Another approach is to use two key chains that over- 936 lap during a short transition period. The shortcoming of this 937 approach is that the authentication field size would need to grow 938 larger during the transition period, which conflicts with the fixed 939 authentication field size in some standards mentioned previously. 941 A better approach is to commit to the new key chain by using previous 942 TESLA packets. The challenge of packet loss though remains. A solu- 943 tion is to add the commitment to the new key chain to a number of 944 packets. The sender needs to start sending the new key chain commit- 945 ment value early enough, such that the majority of receivers will 946 receive and authenticate the new key chain before the previous chain 947 expires. This ensures that the switching to the new chain happens 948 seamlessly. 950 Figure 6 shows an example. One key chain stops at Key K_n and the 951 next chain starts with key K_{n+1}. The sender would then include a 952 commitment to the new key chain into multiple packets of the previous 953 chain, so F(K_{n+1}) would be added to packets throughout intervals 954 I_{n-3} through I_n. Since the keys of the new chain are first 955 revealed in interval I_{n+4}, it is sufficient if the commitment to 956 the new key chain is sent in interval I_n (because the key K_n is 957 disclosed in interval I_{n+3}). Again, to guard against packet loss 958 it is safer to add the commitment to multiple packets before interval 959 I_n. Similarly, the key for interval I_n is disclosed by packets sent 960 in interval I_{n+3}, but if interval I_{n+3} packets are either not 961 sent or lost, the receiver could not verify the packets from interval 962 I_n. To guard against this event, the sender would include K_n in a 963 packets sent after interval I_{n+3}. 965 7 Implementation Considerations for the Receiver 967 This section discusses implementation considerations for the 968 receiver. 970 7.1 Time Synchronization and Security Condition Issues 972 We assume that the time at the receiver has negligible drift. In case 973 the time drift can be substantial, periodic time synchronization is 974 necessary. In appendix B, we propose two time synchronization schemes 976 _____ _____ _____ _____ _____ _____ _____ ___ 977 \/ \/ \/ \/ \/ \/ \/ 978 /\ /\ /\ /\ /\ /\ /\ 979 / \ / \ / \ / \ / \ / \ / \ 980 / \ / \ / \ / \ / \ / \ / \ 981 / \ \ \ \ \ \ 982 / / \ / \ / \ / \ / \ / \ / 983 / / \ / \ / \ / \ / \ / \ / 984 V V \V \V \V \V \V \V 985 --+------+------+------+------+------+------+------+---> t 986 In-3 In-2 In-1 In In+1 In+2 In+3 988 Kn-3 Kn-2 Kn-1 Kn Kn+1 Kn+2 Kn+3 990 -----------------------------> <----------------------- 991 Old key chain New key chain 993 Figure 6: Key chain change 995 for TESLA. Either the receiver synchronizes its time with the sender 996 directly, or indirectly with a time synchronization server in the 997 network. In the latter case, the receiver would need to wait for an 998 authenticated interval and key chain announcement packet, before it 999 can start authenticating packets of the data stream. Even if the 1000 receiver is not time synchronized, it can already receive packets and 1001 record their arrival times. Later in time after the time synchroniza- 1002 tion, the receiver can then start to evaluate their security condi- 1003 tion and authenticate the packets. 1005 Before sending the packet, the receiver records the current time T_s. 1006 When it receives the sender's response, the receiver immediately 1007 records the current time T_r. After this, the receiver verifies the 1008 digital signature using the public key of the server, and checks that 1009 the returned nonce is equal to the nonce sent (if the return packet 1010 contains the nodes of a hash tree, the receiver computes the root 1011 node of the hash tree and checks if that matches the value in the 1012 packet). If the check is unsuccessful or if the round-trip-time (RTT 1013 = T_r - T_s) passes a certain threshold, the synchronization needs to 1014 be repeated. The packet will contain the current time at the sender 1015 T_c. 1017 During the protocol, the receiver needs to evaluate the earliest and 1018 the latest time that the sender can possibly be in. The latest possi- 1019 ble time t_l at the server is t_l = t - T_s + T_c, where t is the 1020 current receiver time. Similarly, the earliest possible time at the 1021 sender is t_e = t - T_r + T_c. 1023 To evaluate the security condition, the receiver computes the latest 1024 possible time that the sender can be at and it verifies that the 1025 sender is not yet in the time interval in which the corresponding key 1026 is disclosed. Assume that the packet arrival time is t_p and the 1027 interval is I_j. The corresponding key will be disclosed in interval 1028 I_{j+d}. The latest possible interval the server can be in is I' = 1029 integer( (t_l - T_i) / Tint ) + I_i, where T_i is the starting time 1030 of interval I_i. So the security condition is valid if I' < I_{j+d}. 1032 Similarly, the receiver can ensure that the sender can even be in 1033 that interval, based on the earliest time the server can be in. This 1034 test prevents the denial-of-service attack outlined in section 7.3. 1035 The check is integer( (t_e - T_i) / Tint ) + I_i >= I_j. 1037 7.2 Reconstruction of the key chain 1039 The receiver reconstructs the key chain as time progresses. For each 1040 new key chain value it receives, it verifies the correctness of the 1041 key by calling the pseudo-random function F until it matches the last 1042 authenticated key chain value. Fortunately, it makes no sense for the 1043 receiver to store the entire key chain. As soon as a key value is 1044 used to authenticate packets in the packet buffer, no new packet 1045 could arrive using that same key since it would clearly violate the 1046 security condition. Hence a key can be immediately discarded after 1047 the corresponding packets were authenticated. Only the most recently 1048 disclosed key is used subsequently, because it is a commitment for 1049 the later keys in the key chain and it is therefore used to verify a 1050 new key. 1052 7.3 Protecting against Denial-of-Service Attacks 1054 A possible denial-of-service attack on the receiver would be as fol- 1055 lows. A malicious attacker can send a packet with a sending interval 1056 that is far out in the future. When the receiver would try to verify 1057 the disclosed key, it would need to perform a large number of pseudo- 1058 random function computations, which would cause it to waste large 1059 amounts of its computation resources. Fortunately, this attack is 1060 easy to prevent. Analogous to the security condition, the receiver 1061 verifies for each packet whether it is even possible that the sender 1062 has sent that particular packet. If this check is not satisfied, the 1063 packet must be spoofed and the receiver immediately drops the packet. 1065 8 Acknowledgments 1067 We would like to thank Mike Luby for his feedback and support. 1069 9 Bibliography 1071 [1] T. Dierks and C. Allen, "The TLS protocol version 1.0." Internet 1072 Request for Comments RFC 2246, January 1999. Proposed standard. 1074 [2] Ipsec, "IP Security Protocol, IETF working group." 1075 http://www.ietf.org/html.charters/ipsec-charter.html. 1077 [3] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. 1078 Pinkas, "Multicast security: A taxonomy and some efficient construc- 1079 tions," in Infocom '99 , 1999. 1081 [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams," tech. 1082 rep., IBM T.J.Watson Research Center, 1997. 1084 [5] P. Rohatgi, "A compact and fast hybrid signature scheme for mul- 1085 ticast packet authentication," in 6th ACM Conference on Computer and 1086 Communications Security , November 1999. 1088 [6] P. Rohatgi, "A hybrid signature scheme for multicast source 1089 authentication," Internet Draft, Internet Engineering Task Force, 1090 June 1999. Work in progress. 1092 [7] C. K. Wong and S. S. Lam, "Digital signatures for flows and mul- 1093 ticasts," in Proc. IEEE ICNP `98 , 1998. 1095 [8] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient 1096 authentication and signing of multicast streams over lossy channels," 1097 in IEEE Symposium on Security and Privacy , May 2000. 1099 [9] A. Perrig, R. Canetti, D. X. Song, and J. Tygar, "Efficient and 1100 secure source authentication for multicast," in Network and Dis- 1101 tributed Systems Security NDSS 2001 , 2001. 1103 [10] B. Briscoe, "Flames: Fast, loss-tolerant authentication of mul- 1104 ticast streams," tech. rep., BT Research, 2000. 1105 http://www.labs.bt.com/people/briscorj/papers.html. 1107 [11] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream 1108 authentication," in Selected Areas in Cryptography 2000 , (Waterloo, 1109 Canada), August 2000. A talk describing this scheme was given at IBM 1110 Watson in August 1998. 1112 [12] S. Cheung, "An efficient message authentication scheme for link 1113 state routing," in 13th Annual Computer Security Applications Confer- 1114 ence , 1997. 1116 [13] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single 1117 source authentication on the mbone," in ICME 2000 , Aug 2000. A talk 1118 containing this work was given at IBM Watson, August 1998. 1120 [14] S. Bradner, "Key words for use in RFCs to indicate requirement 1121 levels," Request for Comments (Best Current Practice) 2119, Internet 1122 Engineering Task Force, Mar. 1997. 1124 [15] Secure Multicast Group (SMuG). http://www.ipmulticast.com/com- 1125 munity/smug/. 1127 [16] R. Canetti, P. Cheng, D. Pendarakis, J. Rao, P. Rohatgi, and D. 1128 Saha, "An architecture for secure internet multicast," Internet 1129 Draft, Internet Engineering Task Force, Feb. 1999. Work in progress. 1131 [17] R. Canetti, P. Rohatgi, and P.-C. Cheng, "Multicast data secu- 1132 rity transformations: Requirements, considerations, and prominent 1133 choices," internet draft, Internet Engineering Task Force, 2000. 1134 draft-data-transforms.txt. 1136 [18] Reliable Multicast Transport (RMT). 1137 http://www.ietf.org/html.charters/rmt-charter.html. 1139 [19] M. Luby, J. Gemmell, L. Vicisano, L. Rizzo, J. Crowcroft, and B. 1140 Lueckenhoff, "Asynchronous layered coding. a massively scalable reli- 1141 able multicast protocol," internet draft, Internet Engineering Task 1142 Force, July 2000. draft-ietf-rmt-pi-alc-01.txt. 1144 [20] D. L. Mills, "Network Time Protocol (Version 3) Specification, 1145 Implementation and Analysis." Internet Request for Comments, March 1146 1992. RFC 1305. 1148 [21] L. Lamport, "Password authentication with insecure communica- 1149 tion," Communications ACM , vol. 24, Nov. 1981. 1151 [22] N. Haller, "The S/KEY one-time password system," Request for 1152 Comments (Informational) 1760, Internet Engineering Task Force, Feb. 1153 1995. 1155 [23] R. L. Rivest, A. Shamir, and L. M. Adleman, "A method for 1156 obtaining digital signatures and public-key cryptosystems," Communi- 1157 cations ACM , vol. 21, no. 2, pp. 120--126, 1978. 1159 [24] "Digital Signature Standard (DSS), Federal Register 56." FIPS 1160 PUB 186, Aug. 1991. 1162 [25] M. Bellare, R. Canetti, and H. Krawczyk, "HMAC: Keyed-hashing 1163 for message authentication," Internet Request for Comment RFC 2104, 1164 Internet Engineering Task Force, Feb. 1997. 1166 [26] R. L. Rivest, "The MD5 message-digest algorithm." Internet 1167 Request for Comments, Apr. 1992. RFC 1321. 1169 [27] C. S. Laboratory), "Secure hash standard." Federal Information 1170 Processing Standards Publication FIPS PUB 180-1. 1171 http://csrc.nist.gov/fips/fip180-1.txt (ascii), 1172 http://csrc.nist.gov/fips/fip180-1.ps (postscript), Apr. 1995. 1174 [28] M. Baugher, T. Hardjono, and B. Weis, "Group domain of interpre- 1175 tation for isakmp," internet draft, Internet Engineering Task Force, 1176 July 2000. draft-irtf-smug-gdoi-00.txt. 1178 [29] M. Bishop, "A Security Analysis of the NTP Protocol Version 2," 1179 in Sixth Annual Computer Security Applications Conference , November 1180 1990. 1182 [30] R. Merkle, "Protocols for public key cryptosystems," in 1980 1183 IEEE Symposium on Security and Privacy , 1980. 1185 A TESLA Attributes 1187 The following attributes need to be defined in the connection startup 1188 phase for TESLA. This list is extended from [28] and will be com- 1189 pleted in the next version of this draft. 1191 ID Class Value 1192 -------- ----- 1193 RESERVED 0 1194 SOURCE_ID 64 1195 DIRECT_SYNCHRONIZATION 65 1196 SENDERS_CERT_TYPE 66 1197 SENDERS_CERT 67 1198 MAC_TYPE 68 1199 MAC_LENGTH 69 1200 KEY_CHAIN_PRF 70 1201 KEY_CHAIN_KEY_LENGTH 71 1202 INTERVAL_NUMBER 72 1203 INTERVAL_STARTING_TIME 73 1204 INTERVAL_DURATION 74 1205 KEY_DISCLOSURE_DELAY 75 1206 KEY_CHAIN_COMMITMENT_VALUE 76 1207 KEY_CHAIN_EXPIRATION_VALUE 77 1208 NUMBER_OF_TESLA_INSTANCES 78 1209 IMMEDIATE_AUTH_HASH_NUMBER 79 1210 IMMEDIATE_AUTH_HASH_TYPE 80 1211 IMMEDIATE_AUTH_HASH_LENGTH 81 1213 B Time Synchronization Packet Format 1215 We present two options for synchronizing the time. Either the 1216 receiver directly synchronizes its time with the sender (direct syn- 1217 chronization), or both the sender and receiver synchronize their time 1218 with a third entity, a time server (indirect synchronization). We 1219 discuss both cases separately. 1221 B.1 Direct Synchronization 1223 In direct synchronization, each receiver synchronizes its time with 1224 the sender, and registers the dispersion (maximum clock offset 1225 between the sender and receiver clock). We remark that the receiver 1226 only needs to know a rough upper bound d_t on the dispersion (where 1227 d_t can be on the order of multiple seconds). (Many clock synchro- 1228 nization algorithms exist, for example the work of Mills on NTP [20], 1229 and its security analysis [29].) In section 7.1 we describe a simple 1230 protocol and discuss scalability issues related to the initial syn- 1231 chronization. 1233 The receiver sends a time synchronization request to the sender. To 1234 ensure that the senders response is fresh and not replayed by an 1235 attacker, the receiver creates a nonce N_r and sends it to the 1236 sender. Figure 7 shows the request information. 1238 The sender will then return this nonce in the response, which allows 1239 the receiver to ensure that the response packet is fresh. The 1240 response packet contains the following components: 1242 � The current sender time 1244 � The beginning time of a specific interval TI_j 1246 � The id of that interval I_j 1248 � The interval duration Tint 1250 0 1 2 3 1251 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1252 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1253 | | 1254 ~ ~ 1255 | Nr (nonce) | 1256 ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1257 | | 1258 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1260 Figure 7: Time synchronization request packet format 1262 � Key disclosure delay d (unit is interval) 1264 � A publically known key K_i (i < j - d where j is the current 1265 interval index) 1267 � The interval of the last key chain element (key chain expiration) 1269 � Total key chain length 1271 � The nonce N_r 1273 Figure 8 shows the outline of the direct synchronization packet for- 1274 mat. If the T-bit is set, multiple users requested synchronization 1275 concurrently and a hash tree was formed over the nonces. Hence the 1276 signed nonce is the root of the hash tree and the other nodes used 1277 for reconstruction is added outside of the signature at the end of 1278 the packet. If the bit is clear, no hash tree is added and the value 1279 in the nonce field is the users nonce. 1281 The times are specified in milliseconds (ms). Absolute times are 1282 expressed in the number of milliseconds since January 1, 1970. Since 1283 we use 64-bit time fields, this value will roll over in the year 1284 584944387 AD. The interval id's and lengths are in 32-bit fields. 1285 Finally, the packet is signed. The digital signature includes the 1286 bitfield and ends at the nonce. 1288 The number of nodes specifies how many nodes of the hash tree follow. 1289 This number is followed by a list of 10-byte tree hash nodes, start- 1290 ing at the lowest node. The last hash node in the list a child node 1291 of the root node. 1293 The receiver uses a nonce in its first packet to prevent a replay 1294 attack by an attacker that replays a previously signed synchroniza- 1295 tion reply. Besides the current sender time t_S, the sender also 1296 sends all information necessary to define the intervals and a commit- 1297 ment to the active key chain. The disclosure lag defines the differ- 1298 ence in intervals on when the key values are disclosed. Finally, the 1299 packet is signed with a digital signature scheme. 1301 Since an adversary could artificially speed up either the sender's or 1302 the receiver's packet, the timestamp t_S that the sender returns 1303 could be either from the instant the request was sent or from the 1304 instant the request is received. The receiver sets its local time to 1305 t_S and sets d_t = RTT, where RTT stands for the round-trip time. The 1306 sender's time is assured to be within the interval [t-d_t,t+d_t], 1307 where t is the synchronized local time of the receiver. This syn- 1308 chronization is quite primitive, but it is secure against an active 1309 adversary and it's accuracy suffices for our application. To increase 1310 the accuracy, the receiver can run the protocol multiple times and 1311 use the run which has the lowest RTT. Any other time synchronization 1312 protocol can be used, as long as it is robust against an active 1313 adversary (most schemes do not satisfy this requirement). An example 1314 for a time synchronization protocol is Mills NTP [20]. 1316 This response packet needs to be authenticated with a digital signa- 1317 ture scheme, such as RSA [23], or DSA [24]. We assume that a public- 1318 key infrastructure is in place (PKI). Since most public-key signature 1319 algorithms are computationally expensive, the signing of the response 1320 packet can become a performance bottleneck for the sender. (A 500 MHz 1321 Pentium III workstation can compute on the order of 100 RSA 1024-bit 1322 signatures per second.) A simple trick can alleviate this situation. 1323 The sender can aggregate multiple requests, compute and sign a Merkle 1324 hash tree that is generated from all the requester's nonces [30]. 1325 Figure 9 shows how such a hash tree is constructed. If N_h is the 1326 root of the hash tree, N_h would be included in the signed part of 1327 the response packet instead of N_r. To verify the digital signature 1328 of the response packet, each receiver would reconstruct the hash 1329 tree. Since it does not know the other receiver's nonces that are 1330 part of the hash tree, the sender would include the nodes of the tree 1331 necessary to reconstruct the root node. For the example in figure 9, 1332 the packet returned to receiver A would include N_b and H_{cd}. 1333 Receiver A can reconstruct the root node H_{ad} from these values and 1334 its own nonce N_a as follows: H_{ad} = H(H(N_a,N_b),H_{cd}). Note 1335 that the number of nodes returned in the response packet is logarith- 1336 mic in the number of receivers whose request arrived in the same time 1337 interval. Assuming a 50 ms interval time (the sender would need to 1338 compute at most 20 signatures per second) and assuming that 1,000,000 1339 receivers wanted to synchronize their time in that interval, the 1340 return packet would only need to contain 20 hash nodes or 200 bytes, 1342 0 1 2 3 1343 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1344 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1345 | | 1346 ~ Sender time (unit: ms) ~ 1347 | | 1348 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1349 | Interval id (j) | 1350 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1351 | | 1352 ~ Beginning time of interval Ij (unit: ms) ~ 1353 | | 1354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1355 | Interval duration (unit: ms) | 1356 ~-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1357 | Key disclosure (unit:interval)| | 1358 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ 1359 | | 1360 ~ Disclosed Key Ki ~ 1361 | | 1362 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1363 | Last key chain element interval | 1364 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1365 | Total key chain length | 1366 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1367 | | 1368 ~ ~ 1369 | Nr (nonce) | 1370 ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1371 | |T| Signature length | 1372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1373 | | 1374 ~ Signature (variable length) ~ 1375 | | 1376 ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1377 | | Padding (variable length) | 1378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1379 | # of nodes | | 1380 +-+-+-+-+-+-+-+-+ ~ 1381 | Node list (size = 10 * # of nodes) | 1382 ~ ~ 1383 | | 1384 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1386 Figure 8: Direct synchronization packet format 1387 assuming an 80 bit hash function. Any cryptographically secure hash 1388 function can be used for H(x,y), for example MD5 [26]. 1390 Had 1391 / \ 1392 / \ 1393 / \ 1394 Hab Hcd 1395 / \ / \ 1396 / \ / \ 1397 Na Nb Nc Nd 1399 Figure 9: Hash tree over receiver nonces. Node H_{ab} = H(N_a, N_b). 1400 H_{ad} = H(H_{ab},H_{cd}). 1402 B.2 Indirect Synchronization 1404 If distributed time synchronization servers exist in the network, the 1405 sender and receivers can separately synchronize their clocks with the 1406 same time synchronization server. The resulting dispersion is the sum 1407 of their dispersions with the time synchronization server. NTP is a 1408 sophisticated time synchronization protocol that can be used in this 1409 case [20]. 1411 To bootstrap the authentication process, an initial authenticated 1412 packet is still required, which can be authenticated with a digital 1413 signature scheme. The sender periodically broadcasts an interval 1414 specification message, digitally signed with its private key. The 1415 initial authenticated packet contains the precise interval informa- 1416 tion (interval frequency and the starting time of a specific inter- 1417 val) along with the key of a past interval. The packet contains the 1418 following fields: 1420 � The Id / IP address of the time synchronization server 1422 � The dispersion to the time synchronization server 1424 � The beginning time of a specific interval TI_j 1426 � The id of that interval I_j 1428 � The interval duration Tint 1429 � Key disclosure delay d (unit is interval) 1431 � A publically known key K_i (i < j - d where j is the current 1432 interval index) 1434 � The interval of the last key chain element (key chain expiration) 1436 � Total key chain length 1438 The packet format is depicted in figure 10. The bitfield is currently 1439 unused in this version and reserved for future purposes. The remain- 1440 ing fields are analogous to the direct synchronization packet, except 1441 that the current time is replaced with the IP address of the time 1442 synchronization server and the dispersion of the sender's clock with 1443 respect to the time synchronization server. 1445 The main advantage for indirect synchronization is that the sender 1446 does not need to process any requests from the receiver, hence this 1447 scheme achieves maximum scalability. This also dramatically improves 1448 the security of the sender, since it can be configured not to receive 1449 any packets. 1451 C Author Contact Information 1453 Adrian Perrig 1454 SIMS - UC Berkeley / Digital Fountain 1455 102 South Hall, 4600 1456 Berkeley, CA 94720 1457 US 1458 perrig@cs.berkeley.edu 1460 Ran Canetti 1461 IBM Research 1462 30 Saw Mill River Rd 1463 Hawthorne, NY 10532 1464 US 1465 canetti@watson.ibm.com 1467 Bob Briscoe 1468 BT Research 1469 B54/74, BT Labs 1470 Martlesham Heath 1471 Ipswich, IP5 3RE 1472 UK 1473 bob.briscoe@bt.com 1474 0 1 2 3 1475 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1477 | Id of the synchronization server (IP address) | 1478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1479 | Sender's dispersion with the time syn server (unit: ms) | 1480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1481 | Interval id (j) | 1482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1483 | | 1484 ~ Beginning time of interval Ij (unit: ms) ~ 1485 | | 1486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1487 | Interval duration (unit: ms) | 1488 ~-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1489 | Key disclosure (unit:interval)| | 1490 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ 1491 | | 1492 ~ Disclosed Key Ki ~ 1493 | | 1494 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1495 | Last key chain element interval | 1496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1497 | Total key chain length | 1498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1499 | Signature length (unit: bytes)| | 1500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ 1501 | | 1502 ~ Signature (variable length) ~ 1503 | | 1504 ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1505 | | Padding (variable length) | 1506 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1508 Figure 10: Indirect synchronization packet format 1510 Doug Tygar 1511 SIMS - UC Berkeley 1512 102 South Hall, 4600 1513 Berkeley, CA 94720-4600 1514 US 1515 tygar@cs.berkeley.edu 1517 Dawn Song 1518 CS - UC Berkeley 1519 387 Soda Hall, 1776 1520 Berkeley, CA 94720-1776 1521 US 1522 dawnsong@cs.berkeley.edu 1524 D Full Copyright Statement 1526 Copyright (C) The Internet Society (2000). All Rights Reserved. 1528 This document and translations of it may be copied and furnished to 1529 others, and derivative works that comment on or otherwise explain it 1530 or assist in its implementation may be prepared, copied, published 1531 and distributed, in whole or in part, without restriction of any 1532 kind, provided that the above copyright notice and this paragraph are 1533 included on all such copies and derivative works. However, this doc- 1534 ument itself may not be modified in any way, such as by removing the 1535 copyright notice or references to the Internet Society or other 1536 Internet organizations, except as needed for the purpose of develop- 1537 ing Internet standards in which case the procedures for copyrights 1538 defined in the Internet languages other than English. 1540 The limited permissions granted above are perpetual and will not be 1541 revoked by the Internet Society or its successors or assigns. 1543 This document and the information contained herein is provided on an 1544 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1545 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1546 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1547 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MER- 1548 CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."