TESLA Broadcast Authentication Protocol PDF

In CryptoBytes, 5:2, Summer/Fall 2002, pp. 2-13 The TESLA Broadcast Authentication Protocol∗ Adrian Perrig Ran Canetti J. D. Tygar Dawn Song Abstract 1 Introduction One of the main cha...

In CryptoBytes, 5:2, Summer/Fall 2002, pp. 2-13 The TESLA Broadcast Authentication Protocol∗ Adrian Perrig Ran Canetti J. D. Tygar Dawn Song Abstract 1 Introduction One of the main challenges of securing broad- Broadcast communication is gaining popularity cast communication is source authentication, or for efficient and large-scale data dissemination. enabling receivers of broadcast data to verify Examples of broadcast distribution networks are that the received data really originates from the satellite broadcasts, wireless radio broadcast, or claimed source and was not modified en route. IP multicast. While many broadcast networks can This problem is complicated by mutually un- efficiently distribute data to multiple receivers, trusted receivers and unreliable communication they often also allow a malicious user to imper- environments where the sender does not retrans- sonate the sender and inject broadcast packets — mit lost packets. we call this a packet injection attack. (Source- Specific Multicast (SSM, EXPRESS) is a no- This article presents the TESLA (Timed table exception, and attempts to prevent this at- Efficient Stream Loss-tolerant Authentication) tack [17, 40].) broadcast authentication protocol, an efficient protocol with low communication and computa- Because malicious packet injection is easy in tion overhead, which scales to large numbers of many broadcast networks, the receivers want to receivers, and tolerates packet loss. TESLA is ensure that the broadcast packets they receive re- based on loose time synchronization between the ally originate from the claimed source. A broad- sender and the receivers. cast authentication protocol enables the receivers to verify that a received packet was really sent by Despite using purely symmetric cryptographic the claimed sender. functions (MAC functions), TESLA achieves asymmetric properties. We discuss a PKI appli- Simply deploying the standard point-to-point cation based purely on TESLA, assuming that all authentication mechanism (i.e., appending a mes- network nodes are loosely time synchronized. sage authentication code (MAC) to each packet, computed using a shared secret key) does not pro- vide secure broadcast authentication. The prob- lem is that any receiver with the secret key can forge data and impersonate the sender. Conse- quently, it is natural to look for solutions based ∗ on asymmetric cryptography to prevent this at- Most of this work was done at UC Berkeley and IBM Research. The authors can be reached at tack; a digital signature scheme is an example of [email protected], [email protected], an asymmetric cryptographic protocol. Indeed, [email protected], [email protected]. signing each data packet provides secure broad- 2 cast authentication; however, it has high over- Another approach to providing broadcast au- head, both in terms of the time required to sign thentication uses only symmetric cryptography, and verify, and in terms of the bandwidth. Several more specifically on message authentication codes schemes were proposed that mitigate this over- (MACs), and is based on delayed disclosure of head by amortizing a single signature over sev- keys by the sender. This technique was indepen- eral packets, e.g., [14, 25, 28, 33, 38, 39]. How- dently discovered by Cheung in the context of ever, none of these schemes is fully satisfactory authenticating link state routing updates. A re- in terms of bandwidth overhead, processing time, lated approach was used in the Guy Fawkes proto- scalability, robustness to denial-of-service attacks, col for interactive unicast communication. In and robustness to packet loss. Even though some the context of multicast streamed data it was pro- schemes amortize a digital signature over multiple posed by several authors [2, 3, 5, 27, 28]. data packets, a serious denial-of-service attack is usually possible where an attacker floods the re- The main idea of TESLA is that the sender at- ceiver with bogus packets supposedly containing taches to each packet a MAC computed with a key a signature. Since signature verification is often k known only to itself. The receiver buffers the computationally expensive, the receiver is over- received packet without being able to authenti- whelmed verifying bogus signatures. cate it. A short while later, the sender discloses k and the receiver is able to authenticate the packet. Researchers proposed information-theoretically Consequently, a single MAC per packet suffices to secure broadcast authentication mechanisms [10, provide broadcast authentication, provided that 11, 12, 13, 20, 34, 35, 36]. These protocols have a the receiver has synchronized its clock with the high overhead in large groups with many receivers. sender ahead of time. Canetti et al. construct a broadcast authentica- This article is an overview of the TESLA broad- tion protocol based on k different keys to authen- cast authentication protocol. A more detailed de- ticate every message with k different MAC’s. scription is in a forthcoming book and in our Every receiver knows m keys and can hence ver- earlier publications [27, 28]. A standardization ef- ify m MAC’s. The keys are distributed in such fort for TESLA is under way in the Multicast Se- a way that no coalition of w receivers can forge a curity (MSEC) working group of the IETF. packet for a specific receiver. The security of their TESLA is used in a wide variety of applications, scheme depends on the assumption that at most ranging from broadcast authentication in sensor a bounded number (which is on the order of k) of networks , to authentication of messages in receivers collude. ad hoc network routing protocols. Boneh, Durfee, and Franklin show that one can- not build a compact collusion resistant broad- 2 Background and Assumptions cast authentication protocol without relying on digital signatures or on time synchronization. TESLA requires that the receivers are loosely time They show that any secure broadcast authenti- synchronized with the sender. In this section, cation protocol with per-packet overhead slightly we review a simple protocol to achieve this time less than the number of receivers can be converted synchronization. TESLA also needs an efficient into a signature scheme. mechanism to authenticate keys at the receiver — we first review one-way chains for this purpose. 3 2.1 One-Way Chains Generate Many protocols need to commit to a sequence of F (s1 ) F (s2 ) F (s
−1 ) F (s
) s0 s1... s
−2 s
−1 s
random values. For this purpose, we repeatedly use a one-way hash function to generate a one-way chain. One-way chains are a widely-used crypto- Use / Reveal graphic primitive. One of the first uses of one- Figure 1: One-way chain example. The sender way chains was for one-time passwords by Lam- generates this chain by randomly selecting s
and port. Haller later used the same approach for repeatedly applying the one-way function F. The the S/KEY one-time password system. One- sender then reveals the values in the opposite or- way chains are also used in many other applica- der. tions. Figure 1 shows the one-way chain construction. To generate a chain of length
we randomly pick the last element of the chain s
. We generate the 2.2 Time Synchronization chain by repeatedly applying a one-way function F. Finally, s0 is a commitment to the entire one- TESLA does not need the strong time synchro- way chain, and we can verify any element of the nization properties that sophisticated time syn- chain through s0 , e.g. to verify that element si chronization protocols provide [22, 24, 37], but is indeed the element with index i of the hash only requires loose time synchronization, and that chain, we check that F i (si ) = s0. More gener- the receiver knows an upper bound on the sender’s ally, si commits to sj if i < j (to verify that sj is local time. We now outline a simple and secure part of the chain if we know that si is the ith el- time synchronization protocol that achieves this ement of the chain, we check that F j−i (sj ) = si ). requirement. For simplicity, we assume the clock We reveal the elements of the chain in this or- drift of both sender and receiver is negligible (oth- der s0 , s1 ,... , s
−1 , s
. How can we store this erwise the receiver can periodically resynchronize chain? We can either create it all at once and store the time with the sender). We denote the real each element of the chain, or we can just store s
difference between the sender and the receiver’s and compute any other element on demand. In time with δ. In loose time synchronization, the practice, a hybrid approach helps to reduce stor- receiver does not need to know the exact δ but age with a small recomputation penalty. Jakobs- only an upper bound on it, ∆, which we also refer son , and Coppersmith and Jakobsson pro- to as the maximum time synchronization error. pose a storage efficient mechanism for one-way chains: a one-way chain with N elements only We now describe a simple protocol for time requires log(N ) storage and log(N ) computation synchronization, where each receiver performs ex- to access an element. plicit time synchronization with the sender. This approach does not require any extra infrastruc- In TESLA, the elements of the one-way chain ture to perform time synchronization. We present are keys, so we call the chain a one-way key chain. a simple two-round time synchronization protocol Furthermore, any key of the one-way key chain that satisfies the requirement for TESLA, which commits to all following keys, so we call such a is that the receiver knows an upper bound on the key a one-way key chain commitment, or simply sender’s clock. Reiter previously describes this key chain commitment. protocol [31, 32]. 4  Receiver time Sender time 1. Setup. The sender S has a digital signature tR t1 key pair, with the private key KS−1 and the public key KS. We assume a mechanism that δ allows a receiver R to learn the authenticated public key KS. The receiver chooses a ran- t3 tS dom and unpredictable nonce. ∆ 2. Protocol steps. Before sending the first mes- sage, the receiver records its local time tR. t2 R → S : Nonce S → R : {Sender time tS , Nonce}K −1 Figure 2: Direct time synchronization between S the sender and the receiver. The receiver is- sues a time synchronization request at time tR , To verify the return message, the receiver ver- at which time the sender’s clock is at time t1. ifies the digital signature and checks that the The sender responds to the request at its local nonce in the packet equals the nonce it ran- time tS. In TESLA, the receiver is only interested domly generated. If the message is authentic, in an upper bound on the sender’s time. When the receiver stores tR and tS. To compute the the receiver has its current time tr , it computes upper bound on the sender’s clock at local the upper bound on the current sender’s time as time t, the receiver computes t − tR + tS. ts ≤ tr − tR + tS. The real synchronization er- ror after this protocol is δ. The receiver, however, does not know the propagation delay of the time Upon receiving the signed response, the receiver synchronization request packet, so it must assume checks the validity of the signature and verifies that the time synchronization error is ∆ (or the that the nonce in the response packet equals the full round-trip time (RTT)). nonce in the request packet. If all verifications are successful, the receiver uses tR and tS to com- pute the upper bound of the sender’s time: when Figure 2 shows a sample time synchronization the receiver has the current time tr , it computes between the receiver and the sender. In the pro- the upper bound on the current sender’s time as tocol, the receiver first records its local time tR ts ≤ tr − tR + tS. The real synchronization error and sends a time synchronization request contain- after this protocol is δ, as Figure 2 shows. The ing a nonce to the sender.1 Upon receiving the receiver, however, does not know the propagation time synchronization request, the sender records delay of the time synchronization request packet, its local time tS and replies with a signed response so it must assume that the time synchronization packet containing tS and the nonce.2 error is ∆ (or the full round-trip time (RTT)). 1 The security of this time synchronization protocol re- the sender immediately records and replies with the arrival lies on the unpredictability of the nonce — if an attacker time of the request packet), since the receiver is only in- could predict the receiver’s nonce, it could send a time terested in an upper bound on the sender’s clock. If the synchronization request to the sender with that nonce, and receiver were interested in the lower bound on the sender’s replay the response later to the receiver. clock, the processing delay and delay of the response mes- 2 Interestingly, the processing and propagation delay of sage would matter. For more details on this refer to the the response message does not change δ (assuming that more detailed time synchronization description. 5  A digital signature operation is computation- Despite the buffering, TESLA has a low authen- ally expensive, and we need to be careful about tication delay. In typical configurations, the au- denial-of-service attacks in which an attacker thentication delay is on the order of one round- floods the sender with time synchronization re- trip delay between the sender and receiver. quests. Another problem is request implosion: the sender is overwhelmed with time synchronization requests from receivers. We address these issues in our earlier paper. 3.1 Sketch of TESLA protocol We first outline the main ideas behind TESLA. Broadcast authentication requires a source of 3 The TESLA Broadcast Authentica- asymmetry, such that the receivers can only ver- ify the authentication information, but not gener- tion Protocol ate valid authentication information. TESLA uses time for asymmetry. We assume that receivers are A viable broadcast authentication protocol has all loosely time synchronized with the sender — the following requirements: up to some time synchronization error ∆, all par- ties agree on the current time. Here is a sketch of the basic approach: Low computation overhead for generation and verification of authentication informa- tion. The sender splits up the time into time in- tervals of uniform duration. Next, the sender Low communication overhead. forms a one-way chain of self-authenticating values, and assigns the values sequentially to Limited buffering required for the sender and the time intervals (one key per time inter- the receiver, hence timely authentication for val). The one-way chain is used in the re- each individual packet. verse order of generation, so any value of a time interval can be used to derive values of Robustness to packet loss. previous time intervals. The sender defines a disclosure time for one-way chain values, usu- Scales to a large number of receivers. ally on the order of a few time intervals. The sender publishes the value after the disclosure The TESLA protocol meets all these require- time. ments with low cost — and it has the following The sender attaches a MAC to each packet. special requirements: The MAC is computed over the contents of the packet. For each packet, the sender de- The sender and the receivers must be at least termines the time interval and uses the cor- loosely time-synchronized as outlined in Sec- responding value from the one-way chain as tion. a cryptographic key to compute the MAC. Along with the packet, the sender also sends Either the receiver or the sender must buffer the most recent one-way chain value that it some messages. can disclose. 6  Each receiver that receives the packet per- 3.2 Sender Setup forms the following operation. It knows the schedule for disclosing keys and, since the TESLA uses self-authenticating one-way chains. clocks are loosely synchronized, can check The sender divides the time into uniform intervals that the key used to compute the MAC is still of duration Tint. Time interval 0 will start at time secret by determining that the sender could T0 , time interval 1 at time T1 = T0 +Tint , etc. The not have yet reached the time interval for dis- sender assigns one key from the one-way chain closing it. If the MAC key is still secret, then to each time interval in sequence. The one-way the receiver buffers the packet. chain is used in the reverse order of generation, so any value of a time interval can be used to derive Each receiver also checks that the disclosed values of previous time intervals. key is correct (using self-authentication and The sender determines the length N of the previously released keys) and then checks the one-way chain K0 , K1 ,... , KN , and this length correctness of the MAC of buffered packets limits the maximum transmission duration be- that were sent in the time interval of the dis- fore a new one-way chain must be created.3 The closed key. If the MAC is correct, the receiver sender picks a random value for KN. Using a accepts the packet. pseudo-random function f , the sender constructs the one-way function F : F (k) = fk (0). The remainder of the chain is computed recursively using Ki = F (Ki+1 ). Note that this gives us Ki = F N −i (KN ), so we can compute any value in the key chain from KN even if we do not have One-way chains have the property that if inter- intermediate values. Each key Ki will be active mediate values of the one-way chain are lost, they in time interval i. can be recomputed using later values. So, even if some disclosed keys are lost, a receiver can re- cover the key chain and check the correctness of packets. 3.3 Bootstrapping Receivers The sender distributes a stream of messages Before a receiver can authenticate messages with {Mi }, and the sender sends each message Mi in TESLA, it needs to be loosely time synchronized a network packet Pi along with authentication in- with the sender, know the disclosure schedule of formation. The broadcast channel may be lossy, keys, and receive an authenticated key of the one- but the sender does not retransmit lost packets. way key chain. Despite packet loss, each receiver needs to authen- ticate all the messages it receives. Various approaches exist for time synchroniza- tion [24, 37, 22]. TESLA, however, only requires We now describe the stages of the basic TESLA loose time synchronization between the sender protocol in this order: sender setup, receiver 3 For details on how to handle broadcast streams of bootstrap, sender transmission of authenticated unbounded duration by switching one-way key chains, broadcast messages, and receiver authentication see. For this article we assume that chains are suf- of broadcast messages. ficiently long for the duration of communication. 7 and the receivers, so a simple algorithm is suf- depicts the one-way key chain construction and ficient. The time synchronization property that MAC key derivation. To broadcast message Mj TESLA requires is that each receiver can place in interval i the sender constructs packet Pj = an upper bound of the sender’s local time, as we {Mj || MAC(Ki
, Mj ) || Ki−d }. discuss in Section. Figure 3 depicts the one-way key chain deriva- The sender sends the key disclosure schedule by tion, the MAC key derivation, the time intervals, transmitting the following information to the re- and some sample packets that the sender broad- ceivers over an authenticated channel (either via casts. a digitally signed broadcast message, or over uni- cast with each receiver): 3.5 Authentication at Receiver Time interval schedule: interval duration Tint , start time Ti and index of interval i, When a sender discloses a key, all parties poten- length of one-way key chain. tially have access to that key. An adversary can create a bogus message and forge a MAC using Key disclosure delay d (number of intervals). the disclosed key. So as packets arrive, the re- ceiver must verify that their MACs are based on A key commitment to the key chain Ki (i < safe keys: a safe key is one that is only known by j − d where j is the current interval index). the sender, and safe packets or safe messages have MACs computed with safe keys. Receivers must discard any packet that is not 3.4 Broadcasting Authenticated Messages safe, because it may have been forged. We now explain TESLA authentication in de- Each key in the one-way key chain corresponds to tail: A sender sends packet Pj in interval i. When a time interval. Every time a sender broadcasts a the receiver receives packet Pj , the receiver can message, it appends a MAC to the message, using use the self-authenticating key Ki−d disclosed in the key corresponding to the current time interval. Pj to determine i. It then checks the latest possi- The key remains secret for the next d−1 intervals, ble time interval x the sender could currently be so messages sent in interval j effectively disclose in (based on the loosely synchronized clock). If key Kj−d. We call d the key disclosure delay. x < i + d (recall that d is the key disclosure delay, or number of intervals that the key disclosure is As a general rule, using the same key multi- delayed), then the packet is safe. The sender has ple times in different cryptographic operations is thus not yet reached the interval where it discloses ill-advised — it may lead to cryptographic weak- key Ki , the key that will verify packet Pj. nesses. So we do not want to use key Kj both The receiver cannot yet verify the authenticity to derive key Kj−1 and to compute MACs. Us- of packet Pj sent in interval i. Instead, it adds ing a pseudo-random function family f
, we con- the triplet (i, Mj , MAC(Ki
, Mj )) to a buffer, and struct the one-way function F
: F
(k) = fk
(1). verifies the authenticity after it learns Ki
. We use F
to derive the key to compute the MAC of messages: Ki
= F
(Ki ). Figure 3 8  F (Ki ) F (Ki+1 ) F (Ki+2 ) F (Ki+3 ) Ki−1 Ki Ki+1 Ki+2 F
(Ki−1 ) F
(Ki ) F
(Ki+1 ) F
(Ki+2 )
Ki−1 Ki

Ki+1
Ki+2 Interval i − 1 Interval i Interval i + 1 Interval i + 2 time Pj Pj+1 Pj+2 Pj+3 Pj+4 Pj+5 Pj+6 Figure 3: At the top of the figure is the one-way key chain (using the one-way function F ), and the derived MAC keys (using the one-way function F
). Time advances left-to-right, and the time is split into time intervals of uniform duration. At the bottom of the figure, we can see the packets that the sender sends in each time interval. For each packet, the sender uses the key that corresponds to the time interval to compute the MAC of the packet. For example for packet Pj+3 , the sender computes a MAC of the data using key Ki+1
. Assuming a key disclosure delay of two time intervals (d = 2), packet Pj+3 would also carry key Ki−1. What does a receiver do when it receives the 4 Discussion disclosed key Ki ? First, it checks whether it al- ready knows Ki or a later key Kj (j > i). If 4.1 TESLA Security Considerations Ki is the latest key received to date, the receiver checks the legitimacy of Ki by verifying, for some The security of TESLA relies on the following as- earlier key Kv (v < i) that Kv = F i−v (Ki ). The sumptions: receiver then computes Ki
= F
(Ki ) and verifies the authenticity of packets of interval i, and of The receiver’s clock is time synchronized up previous intervals if the receiver did not yet re- to a maximum error of ∆. (We suggest ceive the keys for these intervals (the receiver can that because of clock drift, the receiver pe- derive them from Ki ). riodically re-synchronizes its clock with the Note that the security of TESLA does not rely sender.) on any assumptions on network propagation de- The functions F, F
are secure PRFs, and the lay, since each receiver locally determines the function F furthermore provides weak colli- packet safety, i.e. whether the sender disclosed sion resistance.4 the corresponding key. However, if the key dis- closure delay is not much longer than the network propagation delay, the receivers will find that the As long as these assumptions are satisfied, it packets are not safe. is computationally intractable for an attacker to forge a TESLA packet that the receivers will au- thenticate successfully. 4 See our earlier paper for a formal security proof. 9 4.2 Achieving Asymmetric Security Proper- are loosely time synchronized (as above with an ties with TESLA upper bound on the synchronization error); and all nodes in the network trust the time stamp- ing server [6, 15, 23]. The time stamping server Broadcast authentication requires an asymmetric timestamps all TESLA packets it receives. The primitive, which TESLA provides through loosely time stamping server can broadcast the hooks to synchronized clocks and delayed key disclosure. the trust chain authenticated with its TESLA in- TESLA shares many common properties with stance. A judge who wants to verify that a sender asymmetric cryptographic mechanisms. In fact, sent packet P performs the following operations: assuming that all nodes in a network are time syn- chronized, any key of the key chain serves as a key chain commitment and is similar to a public key of 1. Receive the current value of the time stamp- a digital signature: any loosely time synchronized ing server’s trust chain, ensure that it is safe, receiver with an authentic key chain commitment and wait for the TESLA key to authenticate can authenticate messages, but not forge a mes- it. sage with a MAC that receivers would accept. We can construct an efficient PKI based solely 2. Based on the trust chain value, verify that on TESLA. Consider an environment with n com- packet P is part of the trust chain. municating nodes. We assume that all nodes are loosely time synchronized, such that the maxi- 3. Verify that packet P was safe when the time mum clock offset between any two nodes is ∆; and stamping server received it (not necessary if that all nodes know the authentic key chain com- the time stamping server only timestamps mitment and key disclosure schedule of the certi- safe packets). fication authority (CA). We further assume that the CA knows the authentic key chain commit- ment and key disclosure schedule of every node. 4. Retrieve key from the sender and verify it If a node A wants to start authenticating packets using the key chain commitment and disclo- originating from another node B, A can contact sure schedule recorded by the time stamping the CA for B’s key chain commitment and key server. disclosure schedule, which the CA sends authen- ticated with its TESLA instance. After the CA discloses the corresponding key, A can authenti- 5. Verify that the authenticity of the packet, cate B’s TESLA parameters and subsequently au- which implies that the correct sender must thenticate B’s packets. have generated the packet. Note that TESLA is not a signature mecha- nism and does not provide non-repudiation, as TESLA and a time stamping server can thus anybody could forge “authentic” TESLA packets achieve non-repudiation. This example also shows after the key is disclosed. However, in conjunction that the TESLA authentication can also be per- with a trusted time stamping mechanism, TESLA formed after the key is already disclosed, as long could achieve properties similar to a digital signa- as the verifier can check that the packet arrived ture. Consider this setup: all nodes in the network safely. 10 5 Acknowledgments ’2001, volume 2045 of Lecture Notes in Com- puter Science, pages 434–450, 2001. We gratefully acknowledge funding support for B. Briscoe. FLAMeS: Fast, Loss-Tolerant this research. This research was sponsored in part Authentication of Multicast Streams. the United States Postal Service (contract USPS Technical report, BT Research, 2000. 102592-01-Z-0236), by the United States Defense http://www.labs.bt.com/people/briscorj/ Advanced Research Projects Agency (contract papers.html. N66001-99-2-8913), and by the United States Na- tional Science Foundation (grants 99-79852 and A. Buldas, P. Laud, H. Lipmaa, and 01-22599). DARPA Contract N66001-99-2-8913 J. Villemson. Time-stamping with binary is under the supervision of the Space and Naval linking schemes. In Advances in Cryptol- Warfare Systems Center, San Diego. ogy — CRYPTO ’98, volume 1462 of Lecture Notes in Computer Science, pages 486–501, The views and conclusions contained in this 1998. document are those of the author and should not be interpreted as representing official policies, ei- R. Canetti, J. Garay, G. Itkis, D. Miccian- ther expressed or implied, of the United States cio, M. Naor, and B. Pinkas. Multicast se- government, of DARPA, NSF, USPS, any of its curity: A taxonomy and some efficient con- agencies. structions. In INFOCOMM’99, pages 708– 716, March 1999. References S. Cheung. An efficient message authen- tication scheme for link state routing. In 13th Annual Computer Security Applications R. Anderson, F. Bergadano, B. Crispo, Conference, pages 90–98, 1997. J. Lee, C. Manifavas, and R. Needham. A new family of authentication protocols. ACM D. Coppersmith and M. Jakobsson. Almost Operating Systems Review, 32(4):9–20, Oc- optimal hash sequence traversal. In Pro- tober 1998. ceedings of the Fourth Conference on Finan- F. Bergadano, D. Cavagnino, and B. Crispo. cial Cryptography (FC ’02), Lecture Notes in Chained stream authentication. In Selected Computer Science, 2002. Areas in Cryptography, 7th Annual Interna- Y. Desmedt and Y. Frankel. Shared genera- tional Workshop, SAC 2000, volume 2012 of tion of authenticators and signatures. In Ad- Lecture Notes in Computer Science, pages vances in Cryptology — CRYPTO ’91, vol- 144–157, August 2000. ume 576 of Lecture Notes in Computer Sci- F. Bergadano, D. Cavalino, and B. Crispo. ence, pages 457–469, 1992. Individual single source authentication on the mbone. In ICME 2000, Aug 2000. Y. Desmedt, Y. Frankel, and M. Yung. Multi- receiver / multi-sender network security: Ef- D. Boneh, G. Durfee, and M. Franklin. Lower ficient authenticated multicast / feedback. In bounds for multicast message authentication. Proceedings IEEE Infocom ’92, pages 2045– In Advances in Cryptology — EUROCRYPT 2054, 1992. 11  Y. Desmedt and M. Yung. Arbitrated un- K. Kurosawa and S. Obana. Characteriza- conditionally secure authentication can be tion of (k,n) multi-receiver authentication. unconditionally protected against arbiter’s In Proceedings of the 2nd Australasian Con- attacks. In Advances in Cryptology — ference on Information Security and Privacy CRYPTO ’90, volume 537 of Lecture Notes (ACISP ’97), volume 1270 of Lecture Notes in Computer Science, pages 177–188, 1991. in Computer Science, pages 205–215, 1997. F. Fujii, W. Kachen, and K. Kurosawa. Com- L. Lamport. Password authentication with binatorial bounds and design of broadcast insecure communication. Communications of authentication. IEICE Transactions, E79- the ACM, 24(11):770–772, November 1981. A(4):502–506, 1996. L. Lamport and P. Melliar-Smith. Synchro- R. Gennaro and P. Rohatgi. How to sign dig- nizing clocks in the presence of faults. Jour- ital streams. In Advances in Cryptology — nal of the ACM, 32(1):52–78, 1985. CRYPTO ’97, volume 1294 of Lecture Notes in Computer Science, pages 180–197, 1997. H. Lipmaa. Secure and Efficient Time- Stamping Systems. PhD thesis, Department S. Haber and W. Stornetta. How to time- of Mathematics, University of Tartu, Esto- stamp a digital document. In Advances in nia, April 1999. Cryptology — CRYPTO ’90, volume 537 of Lecture Notes in Computer Science, pages D. Mills. Network Time Protocol (version 3) 437–455, 1991. specification, implementation and analysis. N. Haller. The S/Key one-time password Internet Request for Comment RFC 1305, In- system. In Proceedings of the Symposium ternet Engineering Task Force, March 1992. on Network and Distributed Systems Secu- S. Miner and J. Staddon. Graph-based au- rity, pages 151–157. Internet Society, Febru- thentication of digital streams. In Proceed- ary 1994. ings of the IEEE Symposium on Research H. Holbrook and D. Cheriton. IP multicast in Security and Privacy, pages 232–246, May channels: EXPRESS support for large-scale 2001. single-source applications. In Proceedings of ACM SIGCOMM ’99, September 1999. Multicast security ietf working group (msec). http://www.ietf.org/html.charters/ Y.-C. Hu, A. Perrig, and D. B. Johnson. msec-charter.html, 2002. Ariadne: A secure on-demand routing pro- tocol for ad hoc networks. In Proceedings A. Perrig, R. Canetti, D. Song, and J. D. of the Eighth ACM International Conference Tygar. Efficient and secure source authen- on Mobile Computing and Networking (Mo- tication for multicast. In Proceedings of the bicom 2002), September 2002. To appear. Symposium on Network and Distributed Sys- tems Security (NDSS 2001), pages 35–46. In- M. Jakobsson. Fractal hash sequence repre- ternet Society, February 2001. sentation and traversal. In Proceedings of the 2002 IEEE International Symposium on In- A. Perrig, R. Canetti, J. D. Tygar, and formation Theory (ISIT ’02), pages 437–444, D. Song. Efficient authentication and signa- July 2002. ture of multicast streams over lossy channels. 12  In Proceedings of the IEEE Symposium on B. Simons, J. Lundelius-Welch, and Research in Security and Privacy, pages 56– N. Lynch. An overview of clock syn- 73, May 2000. chronization. In B. Simons and A. Spector, editors, Fault-Tolerant Distributed Com- A. Perrig, R. Szewczyk, V. Wen, D. Culler, puting, number 448 in LNCS, pages 84–96, and J. D. Tygar. SPINS: Security proto- 1990. cols for sensor networks. In Proceedings of Seventh Annual International Conference on D. Song, D. Zuckerman, and J. D. Tygar. Mobile Computing and Networks (Mobicom Expander graphs for digital stream authen- 2001), pages 189–199, 2001. tication and robust overlay networks. In Proceedings of the IEEE Symposium on Re- A. Perrig and J. D. Tygar. Security Protocols search in Security and Privacy, pages 258– for Broadcast Networks. Kluwer Academic 270, May 2002. Publishers, 2002. To appear. C. Wong and S. Lam. Digital signatures for M. Reiter. A security architecture for fault- flows and multicasts. In IEEE ICNP ‘98, tolerant systems. PhD thesis, Department 1998. of Computer Science, Cornell University, Au- gust 1993. Source-Specific Multicast IETF work- ing group (SSM). http://www.ietf.org/html. M. Reiter, K. Birman, and R. van Renesse. charters/ssm-charter.html, 2002. A security architecture for fault-tolerant sys- tems. ACM Transactions on Computer Sys- tems, 12(4):340–371, November 1994. P. Rohatgi. A compact and fast hybrid sig- nature scheme for multicast packet. In Pro- ceedings of the 6th ACM Conference on Com- puter and Communications Security, pages 93–100, November 1999. R. Safavi-Naini and H. Wang. New results on multireceiver authentication codes. In Ad- vances in Cryptology — EUROCRYPT ’98, volume 1403 of Lecture Notes in Computer Science, pages 527–541, 1998. R. Safavi-Naini and H. Wang. Multireceiver authentication codes: Models, bounds, con- structions and extensions. Information and Computation, 151(1/2):148–172, 1999. G. Simmons. A cartesian product construc- tion for unconditionally secure authentica- tion codes that permit arbitration. Journal of Cryptology, 2(2):77–104, 1990. 13