RFC 4082

Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction 🎀

Okay so this is RFC 4082 🦋, from the Network Working Group. It's Informational, dated June 2005. The authors are A. Perrig, D. Song, R. Canetti, J. D. Tygar, and B. Briscoe. Perrig and Song are at Carnegie Mellon University, Canetti is at IBM, Tygar is at the University of California, Berkeley, and Briscoe is at BT. The title block doesn't list anything it obsoletes or updates, so it doesn't touch any other RFC 💅

Status of This Memo ✨

This memo gives information to the Internet community. It does not specify an Internet standard of any kind, and it can be distributed freely with no limits 🌸

Copyright Notice 🫶

Copyright (C) The Internet Society (2005).

Abstract 💖

Hi bestie, this doc introduces TESLA (Timed Efficient Stream Loss-tolerant Authentication) ✨ It lets every receiver check the integrity of each packet and confirm who sent it, whether it's a multicast or broadcast data stream 🔥 Receivers don't need to trust each other, the work done per packet is low-cost for both sender and receiver, and it can handle any amount of loss without retransmissions 🙈 The sender also doesn't need any per-receiver state, which is so clean 🧚 TESLA can protect receivers from denial of service attacks in certain situations 🛡️ Each receiver has to be loosely time-synchronized with the source so it can verify messages, but otherwise receivers don't have to send anything back 💜 One last thing, though: TESLA alone can't give you non-repudiation of the data source to third parties 💀

This informational doc is meant to help people write standardizable and secure specs for protocols built on TESLA in different contexts 🎀

Table of Contents 📋

   1. Introduction ....................................................2
      1.1. Notation ...................................................3
   2. Functionality ...................................................4
      2.1. Threat Model and Security Guarantee ........................5
      2.2. Assumptions ................................................5
   3. The Basic TESLA Protocol ........................................6
      3.1. Protocol Sketch ............................................6
      3.2. Sender Setup ...............................................7
      3.3. Bootstrapping Receivers ....................................8
           3.3.1. Time Synchronization ................................9
      3.4. Broadcasting Authenticated Messages .......................10
      3.5. Authentication at Receiver ................................11
      3.6. Determining the Key Disclosure Delay ......................12
      3.7. Denial of Service Protection ..............................13
           3.7.1. Additional Group Authentication ....................14
           3.7.2. Not Re-using Keys ..................................15
           3.7.3. Sender Buffering ...................................17
      3.8. Some Extensions ...........................................17
   4. Layer Placement ................................................17
   5. Security Considerations ........................................18
   6. Acknowledgements ...............................................19
   7. Informative References .........................................19

1. Introduction ✨

Picture multicast: one single packet can reach millions of receivers 🤯 That's amazing, but it's also scary, because an attacker could potentially reach millions of receivers with a malicious packet too 😭 This is where source authentication saves the day. With it, receivers can make sure a multicast packet actually came from the right source 👑 Basically, a multicast is the same as a broadcast to a superset of the multicast receivers, so the same worries apply 💅

In unicast, data authentication is pretty simple. The sender and receiver share a secret key and use it to compute a message authentication code (MAC) over everything they communicate. When a message shows up with a correct MAC, the receiver knows the sender made it 🎀 Normal mechanisms do unicast authentication this way. TLS and IPsec are two examples [1,2] 🌸

Symmetric MAC authentication isn't secure in a broadcast setting, though, and this part is the tea ☕ Say a sender broadcasts authentic data to receivers who don't trust each other. Every receiver knows the MAC key, so any of them could impersonate the sender and forge messages to the others 💀 What we actually need is an asymmetric mechanism for authenticated broadcast. That way every receiver can verify the messages it gets, but can't generate authentic messages itself 🦋 Doing this efficiently is a real challenge [3] 🥺

The standard way to get that asymmetry is asymmetric cryptography, like a digital signature 🔐 Signatures have the asymmetric property we need: the sender signs with its private key, and all receivers can verify with the sender's public key. A receiver holding only the public key still can't make a signature for a new message ✨ A digital signature also gives you non-repudiation, which is a stronger property than authentication 👑 The catch is cost. Signatures have high computation overhead for both sender and receiver, and most of them also have high bandwidth overhead 😩 In a broadcast setting the sender doesn't retransmit lost packets, and the receiver still wants to authenticate each packet immediately when it arrives. So we'd have to attach a digital signature to every message. Because asymmetric crypto is so expensive, that would limit us to low-rate streams and to senders and receivers with powerful workstations 💻 We could amortize one signature over several messages, but that's still costly compared with symmetric crypto, which is generally 3 to 5 orders of magnitude more efficient than asymmetric crypto 🤯 Also, spreading one signature across multiple packets needs reliability, because the receiver has to receive all of the packets to verify the signature 🙈 Several schemes follow this approach [4,5,6,7], and [8] has more details 📚

This document presents TESLA, the Timed Efficient Stream Loss-tolerant Authentication protocol 🎀 TESLA mostly uses symmetric cryptography, and it gets the asymmetry it needs from time-delayed key disclosure 🔑 The catch is that TESLA needs loosely synchronized clocks between sender and receivers. More on that in Section 3.3.1 ⏰ Schemes similar to TESLA include [9,10,11] 💜

1.1. Notation 🧮

To write a subscript or index for a variable, we put an underscore between the variable name and the index. For example, the key K with index i is K_i, and the key K with index i+d is K_{i+d} ✨ For a superscript, we use a caret. For example, function F with argument x run i times is F^i(x) 🌈

2. Functionality 🌸

Okay the key idea behind TESLA is that it gets both efficiency and security from delayed disclosure of keys 🔑 That delay leads to an authentication delay, which in practice is on the order of one RTT (round-trip time) ⏳

TESLA has these properties:

• Low computation overhead for generating and verifying authentication information 💅
• Low communication overhead 📦
• Limited buffering for both sender and receiver, so each individual packet can be authenticated in a timely way ⏱️
• Strong robustness to packet loss 🛡️
• Scales to a large number of receivers 🌍
• Protects receivers from denial of service attacks in certain circumstances, if configured appropriately ⚙️
• Each receiver can't verify message authenticity unless it's loosely time-synchronized with the source. That sync can happen at session setup. Once the session is running, receivers don't need to send any messages or acknowledgements 🫶
• Non-repudiation is not supported. Each receiver can know that a stream comes from an authentic source, but it can't prove that to a third party 🙅‍♀️

TESLA can be used in the network layer, the transport layer, or the application layer 🧚 Delayed authentication does require buffering packets until they're authenticated. Some apps that can't tolerate delay may be okay processing packets in parallel with buffering while they wait for authentication, as long as they can roll back if packets turn out to be unauthenticated 😳 For example, an interactive video might play packets that are still waiting for authentication. If they later turn out to be unauthenticated, it could stop playing and warn the viewer that the last x msec were unauthenticated and should be ignored 📺 For brevity, though, the rest of this document assumes packets aren't processed in parallel with buffering 🎀

2.1. Threat Model and Security Guarantee 🕵️‍♀️

TESLA is designed to be secure against a powerful adversary with these capabilities:

• Full control over the network. The adversary can eavesdrop, capture, drop, re-send, delay, and alter packets 😈
• Access to a fast network with negligible delay ⚡
• The adversary's computational resources may be very large, but not unbounded. Specifically, the adversary can do efficient computations, like computing a reasonable number of pseudo-random function applications and MACs with negligible delay. Still, the adversary can't find the key of a pseudo-random function (or tell it apart from a random function) with non-negligible probability 🧠

The security property of TESLA guarantees that the receiver never accepts M_i as authentic unless the sender really sent M_i 🔒 A scheme that provides this guarantee is called a secure broadcast authentication scheme 🏆

Because TESLA expects the receiver to buffer packets before authentication, the receiver has to protect itself from a possible denial of service (DoS) attack caused by a flood of bogus packets (see Section 3.8) 🚨

---

🧵 to be continued...

2.2. Assumptions

Okay so TESLA has three big assumptions it needs to work, and they're kinda the whole vibe 💅

1. The sender and the receiver have to be loosely time-synchronized 🕰️ Like, each receiver has to be able to figure out an upper bound on how far behind its clock is compared to the sender's clock. We call that D_t, and it's defined as D_t = sender time - receiver time. Fun fact: you can get an upper bound on D_t with a super simple two-message exchange 🎀 That exchange can ride along on any secure session initiation protocol. Or you can just use standard stuff like NTP [15] ✨
2. TESLA MUST be bootstrapped at session setup through a regular data authentication system 🔐 One option is a digital signature algorithm. In that case the receiver has to have an authentic copy of either the sender's public key certificate, or a root key certificate if there's a PKI (public-key infrastructure) involved 🫶 Or you can do this setup step with any secure session initiation protocol instead.
3. TESLA uses cryptographic MAC and PRF (pseudo-random functions) 🧚 These MUST be cryptographically secure. More details on how the MAC and PRF get instantiated are in Section 3.4 💜

We really want to hype this up: the security of TESLA does NOT rely on any assumptions about network propagation delay 🙌 That's a big deal, bestie 👑

3. The Basic TESLA Protocol ✨

TESLA is described in a bunch of academic publications: a book on broadcast security [12], a journal paper [13], and two conference papers [7,14] 📚 If you want the in-depth proofs of security, experimental results, and all that good stuff, go check those out 🤓

Let's start with the main ideas behind TESLA 🦋

3.1. Protocol Sketch 🌸

As we argued in the introduction, broadcast authentication needs a source of asymmetry. TESLA uses time for that asymmetry ⏰ First, we make sure the sender and receivers are loosely time-synchronized, like we talked about above. Next, the sender makes a one-way chain of keys, where each key in the chain is tied to a time interval (say, a second) 🔗 Here's the basic approach:

• The sender attaches a MAC to each packet 💌 The MAC is computed over the contents of the packet. For each packet, the sender uses the current key from the one-way chain as the cryptographic key to compute the MAC.
• The sender discloses a key from the one-way chain after some pre-defined time delay. Like, the key used in time interval i gets disclosed at time interval i+3 ⏳
• Each receiver gets the packet. Each receiver knows the schedule for disclosing keys, and since it has an upper bound on the local time at the sender, it can check that the key used to compute the MAC wasn't disclosed yet by the sender 👀 If it wasn't, the receiver buffers the packet. Otherwise, the packet gets dropped because the receiver can't authenticate it 😭 Note that we don't know for sure whether a "late packet" is bogus or just delayed, so we drop it since we can't authenticate it. (Of course, an implementation may choose not to drop packets and to use them unauthenticated 🤷‍♀️)
• Each receiver checks that the disclosed key belongs to the hash-chain (by checking against previously released keys in the chain), and then checks the correctness of the MAC. If the MAC is correct, the receiver accepts the packet 💖

Okay, here's a fun one: one-way chains have the property that if intermediate values get lost, they can be recomputed using subsequent values in the chain 🤯 So even if some key disclosures are lost, a receiver can recover the corresponding keys and check the correctness of earlier packets. Iconic 💅

Now we'll describe the stages of the basic TESLA protocol in this order: sender setup, receiver bootstrap, sender transmission of authenticated broadcast messages, and receiver authentication of broadcast messages 🎀

3.2. Sender Setup 🧁

The sender divides time into uniform intervals of duration T_int, and assigns one key from the one-way chain to each time interval, in sequence ⏱️

The sender determines the length N of the one-way chain K_0, K_1, ..., K_N, and this length limits the maximum transmission duration before a new one-way chain has to be created. The sender picks a random value for K_N. Using a pseudo-random function (PRF), f, the sender constructs the one-way function F: F(k) = f_k(0). The rest of the chain is computed recursively using K_i = F(K_{i+1}). Note that this gives us K_i = F^{N-i}(K_N), so the receiver can compute any value in the key chain from K_N, even if it doesn't have the intermediate values 🧠 The key K_i will be used to authenticate packets sent in time interval i.

Jakobsson [20] and Coppersmith and Jakobsson [21] present a storage- and computation-efficient mechanism for one-way chains. For a chain of length N, storage is about log(N) elements, and the computation overhead to reconstruct each element is also about log(N) 🤩

The sender determines the duration of a time interval, T_int, and the key disclosure delay, d. (T_int is measured in time units, say milliseconds, and d is measured in number of time intervals. That is, a key that is used for time interval i will be disclosed in time interval i+d.) It is stressed that the scheme remains secure for any values of T_int and d>0 🔒 Still, a correct choice of T_int and d is crucial for usability 🫠 The choice is influenced by the estimated network delay, the length of the transmission, and the tolerable delay at the receiver. A T_int that is too short will cause the keys to run out too soon ⚠️ A T_int that is too long will cause excessive delay in authentication for some of the packets (the ones sent at the beginning of a time period) 😩 A delay d that is too short will cause too many packets to be unverifiable by the receiver 💀 A delay d that is too long will cause excessive delay in authentication.

The sender estimates a reasonable upper bound on the network delay between the sender and any receiver as m milliseconds. This includes any delay expected in the stack (see Section 4, on layer placement) 📏 If the sender expects to send a packet every n milliseconds, then a reasonable value for T_int is max(n,m). Based on T_int, a rule of thumb for determining the key disclosure delay, d, is given in Section 3.6 🍓

The above value for T_int is neither an upper nor a lower bound 🙈 It's merely the value that reduces key change processing to a minimum without causing authentication delay to be higher than necessary. If the application can tolerate higher authentication delay, then T_int can be made appropriately larger. Also, if m (or n) increases during the session, perhaps due to congestion or a late joiner on a high delay path, T_int doesn't need to be revised 🌈

Finally, the sender needs to allow each receiver to synchronize its time with the sender. See more details on how this can be done in Section 3.3.1 🫶 (It is stressed that estimating network delay is a separate task from time synchronization between the sender and the receivers, so don't mix them up, bestie 💅)

3.3. Bootstrapping Receivers 🥾

Before a receiver can authenticate messages with TESLA, it needs to have the following:

• An upper bound, D_t, on the lag of its own clock with respect to the clock of the sender. (That is, if the local time reading is t, the current time reading at the sender is at most t+D_t.)
• One authenticated key of the one-way key chain. (Typically this will be the last key in the chain, i.e., K_0. This key will be signed by the sender, and all receivers will verify the signature with the public key of the signer 🔏)
• The disclosure schedule of the following keys:
  • T_int, the interval duration.
  • T_0, the start time of interval 0.
  • N, the length of the one-way key chain.
  • d, the key disclosure delay d (in number of intervals).

The receiver can do the time synchronization and get the authenticated TESLA parameters in a two-round message exchange, as described below. We stress again that time synchronization can be performed as part of the registration protocol between any receiver (including late joiners) and the sender, or between any receiver and a group controller 🤝

3.3.1. Time Synchronization ⏰

Various approaches exist for time synchronization [15,16,17,18]. TESLA only requires the receiver to know an upper bound on the delay of its local clock with respect to the sender's clock, so a simple algorithm is sufficient 😌 TESLA can be used with direct, indirect, and delayed synchronization as three default options. The specific synchronization method will be part of each instantiation of TESLA.

For completeness, here's a simple method for direct synchronization between the sender and a receiver 📨

• The receiver sends a (sync t_r) message to the sender and records its local time, t_r, at the moment of sending.
• Upon receipt of the (sync t_r) message, the sender records its local time, t_s, and sends (synch, t_r,t_s) to the receiver.
• Upon receiving (synch,t_r,t_s), the receiver sets D_t = t_s - t_r + S, where S is an estimated bound on the clock drift throughout the duration of the session.

Note:

• Assuming the messages are authentic (i.e., the message the receiver got was actually sent by the sender), and assuming the clock drift is at most S, then at any point throughout the session T_s < T_r + D_t, where T_s is the current time at the sender and T_r is the current time at the receiver 🧐
• The exchange of sync messages needs to be authenticated. This can be done in a number of ways; for instance, with a secure NTP protocol or in conjunction with a session set-up protocol 🔐

For indirect time synchronization (e.g., synchronization via a group controller), the sender and the controller engage in a protocol to find the value D^0_t between them. Next, each receiver, R, interacts with the group controller (say, when registering to the group) and finds the value D^R_t between the group controller and R. The overall value of D_t within R is set to the sum D_t = D^R_t + D^0_t 🧮✨

3.4. Broadcasting Authenticated Messages 📣✨

okay so every key in the one-way key chain is tied to a time interval 🕰️ and whenever the sender broadcasts a message, it slaps a MAC onto it using the key for the current interval. ngl that's the core move 💅. the key stays secret for the next d-1 intervals, so messages broadcast in interval j effectively disclose key K_j-d. we call d the key disclosure delay 🎀

now, big no-no alert 🚨: you should never use the same key for two different jobs. so using K_j to derive the previous chain key K_{j-1} AND as the MAC key in interval j could lead to a cryptographic weakness 💀. to avoid that drama, we use a pseudo-random function (PRF), f', to build a one-way function F'(k) = f'_k(1). the sender then derives the MAC key with K'_i = F'(K_i) 🧚

to broadcast message M_j in interval i, the sender builds this packet, where || just means concatenation:

P_j = {M_j || i || MAC(K'_i,M_j) || K_{i-d}}

check out the picture (Figure 1) 👀

                       F(K_i)     F(K_{i+1})      F(K_{i+2})
             K_{i-1} <------- K_i <------- K_{i+1} <------- K_{i+2}

                 |             |              |
                 | F'(K_{i-1}) | F'(K_i)      | F'(K_{i+1})
                 |             |              |
                 V             V              V

                K'_{i-1}      K'_i          K'_{i+1}

Figure 1: At the top of the figure, we see the one-way key chain (derived using the one-way function F), and the derived MAC keys (derived using the one-way function F').

---

3.5. Authentication at Receiver 👂💖

okay this part is giving suspense 😭. once a sender discloses a key, we have to assume EVERYONE might have it now. so an attacker could make a bogus message and forge a MAC with that disclosed key 🙅‍♀️. so whenever a packet shows up, the receiver has to check that the MAC is based on a safe key, which means a key that's still secret (only the sender knows it). we call a packet or message with a MAC computed with a safe key a safe packet or safe message 🔒

if a packet proves safe, it gets buffered 🗂️, and it only gets released when its own key shows up in a later packet and proves it's legit. a brand new packet can't be authenticated right away, but it might disclose a new key that lets earlier buffered packets get authenticated 🎉. any newly disclosed key has to be checked for being genuine first, and then the buffered packets waiting on it can finally get their authentication moment 👑

here's the full receiver routine, listed in the exact order the steps should happen 📋:

1. Safe packet test: When the receiver gets packet P_j, which carries an interval index i and a disclosed key K_{i-d}, it first records the local time T the packet arrived. then it computes an upper bound t_j on the sender's clock at arrival: t_j = T + D_t. to test safety, the receiver figures out the highest interval x the sender could possibly be in, namely x = floor((t_j - T_0) / T_int). the receiver checks that x < i + d (where i is the interval index), which means the sender isn't yet in the interval where it discloses K_i 🕵️‍♀️

even if the packet is safe, the receiver still can't verify it yet without K_i, which gets disclosed later. so it adds the triplet ( i, M_j, MAC( K'_i, M_j) ) to a buffer and verifies authenticity after it learns K'_i 🧠

if the packet is unsafe, the receiver treats it as unauthenticated. it should discard unsafe packets, but at its own risk it may choose to use them unverified ⚠️

2. New key index test: next, the receiver checks whether a key K_v has already been disclosed with the same index v as the current disclosed key K_{i-d}, or with a later one. that is, with v >= i-d 🔍
3. Key verification test: if the disclosed key index is new, the receiver checks the legitimacy of K_{i-d} by verifying, for some earlier disclosed key K_v (v<i-d), that K_v = F^{i-d-v}(K_{i-d}) 🔐

if key verification fails, the newly arrived packet P_j should be discarded 🗑️

4. Message verification tests: if the disclosed key is legit, the receiver then verifies the authenticity of any earlier safe, buffered packets of interval i-d. to authenticate one of the buffered packets P_h containing message M_h protected with a MAC that used key index i-d, the receiver computes K'_{i-d} = F'(K_{i-d}), which lets it compute MAC( K'_{i-d}, M_h) 🧮

if this MAC equals the MAC stored in the buffer, the packet is authenticated and can be released from the buffer ✅. if the MACs don't agree, the buffered packet P_h should be discarded ❌

the receiver keeps verifying and releasing (or not) any remaining buffered packets that depend on the newly disclosed key K_{i-d} 🔁

using one disclosed key, we can calculate all the previous disclosed keys 🪄. so even if packets get lost, we can still verify buffered, safe packets from earlier intervals. that means if i-d-v>1, the receiver can also verify the authenticity of the stored packets of intervals v+1 ... i-d-1 💜

---

3.6. Determining the Key Disclosure Delay ⏱️🌸

okay the key disclosure delay d is a big TESLA parameter 🎀. choosing it doesn't change the security of the system, BUT it totally affects performance 📈. a short delay makes packets lose their safety property, so receivers can't authenticate them 😬. a long delay means receivers wait forever for authentication 🐢

here's how we recommend picking it 💖. in direct time synchronization, let the RTT, 2m, be a reasonable upper bound on the round trip time between the sender and any receiver, including worst-case congestion delay and worst-case buffering delay in host stacks. then choose d = ceil( 2m / T_int) + 1. rounding the quotient up makes sure d >= 2 🧮

also, a disclosure delay of one time interval (d=1) does NOT work 🙅‍♀️. picture packets sent close to the boundary of an interval: after network propagation delay and receiver time sync error, a receiver won't be able to authenticate the packet, because the sender will already be in the next interval when it discloses the key 💀

measuring the delay to each receiver before picking m still won't adequately predict the upper bound for late joiners, or for when congestion delay rises later in the session 📉. it may be fine to use a hard-coded historic estimate of worst-case delay instead (e.g., round trip delays to any host on the intra-planetary Internet rarely exceed 500msec if routing remains stable) 🪐

and to be super clear 🫶: TESLA's security does NOT rely on any assumptions about network propagation delay. if the delay is longer than expected, authentic packets might get treated as unauthenticated, but still, no inauthentic packet will ever be accepted as authentic ✨

---

3.7. Denial of Service Protection 🛡️🔥

ngl this is where it gets spicy 🌶️. since TESLA authentication is delayed, receivers seem vulnerable to flooding attacks that make them buffer a ton of extra packets, even though those packets may eventually prove to be inauthentic 😤. when TESLA gets deployed somewhere with a flooding threat, the receiver can take some extra precautions 💅

first up, here are simple DoS mitigations that any receiver can do on its own, without anyone else's help. they don't need any protocol or sender changes 🙌. we spell out exactly where these extra steps slot in alongside the receiver authentication steps from Section 3.5 📍

• Session validity test: before the safe packet test (Step 1), check that arriving packets have a valid source IP address and port number for the session, that they don't replay a message already received in the session, and that they aren't significantly larger than the packet sizes expected in the session 🚫
• Reasonable misordering test: before the key verification test (Step 3), check whether the disclosed key index i-d of the arriving packet is within g of the previous highest disclosed key index v. so, for example, i-d-v <= g. g sets the threshold past which an out-of-order key index is assumed to be malicious rather than just misordered 🕵️. without this test, an attacker could abuse the iterated test in Step 3 to make receivers burn CPU time hashing along the chain for what look like super misordered packets 🔥

each receiver can adapt g on its own to the attack conditions 🎛️. for instance, using this algorithm: initially, g should be set to g_max (say, 16). but whenever an arriving packet fails the reasonable misordering test above or the key verification test (Step 3), g should be dropped to g_min (>0 and typically 1). at each successful key verification (Step 3), g should be incremented by 1 unless it's already g_max 📊. these precautions guarantee that sustained attack packets can't make the receiver run more than an average of g_min hashes each, unless they're paced against genuine packets. in that latter case, attacks are limited to g_max/(g_max-g_min) hashes per genuine packet 🧠

when choosing g_max and g_min, keep in mind that they limit the average gap in a packet sequence to g.max(n,m)/n packets (see Section 3.2 for definitions of n and m) 📏. so with g=1, m=100msec RTT, and n=4msec inter-packet period, reordering would be limited to gaps of 25 packets on average. bigger naturally occurring gaps would have to be written off as if they were losses 🫠

stronger DoS protection needs both senders and receivers to add extra constraints to the protocol 💪. below, we outline three alternative extensions to basic TESLA: the first adds group authentication, the second never re-uses keys during a time interval, and the third moves buffering to the sender 🧚‍♀️

it's important to understand where each scheme applies 🎯, because the first two schemes use slightly more (but bounded) resources in order to stop attackers from eating up unbounded resources. adding group authentication needs larger per-packet overhead 📦. never re-using a key means both ends process two hashes per packet (rather than per time interval), and the sender has to store or re-generate a longer hash chain 😵‍💫. the merits of each scheme, summarised after each one is described below, have to be weighed against these extra costs ⚖️

3.7.1. Additional Group Authentication 💖

okay so this scheme is basically just slapping a group MAC onto every single packet 🫶 The whole group shares one key, K_g, and it gets passed along as an extra step during receiver bootstrap (see Section 3.3). Then when the sender broadcasts message M_j (Section 3.4), it computes the group MAC of each packet, MAC(K_g, P_j), and appends it to the packet header. Note that the group MAC covers the whole packet P_j, which means the message M_j plus the extra TESLA authentication material, using the formula in Section 3.4 ✨

The best part is that each receiver can check right away that a packet came from a group member, just by recomputing the group MAC and comparing it 🔍

Real talk though: TESLA source authentication is only needed when the other group members can't be trusted to stop spoofing the source. If they can be trusted there, simpler group authentication would be enough 💅 So additional group authentication only really makes sense when the other members are trusted not to flood the group, but still aren't trusted not to spoof the source 🧚

3.7.2. Not Re-using Keys 🦋

okay so in TESLA as we've described it so far, each MAC key gets reused for all the packets sent in one time interval. But what if the sender promised to never use a MAC key more than once? 👀 Then every disclosed key could have a second job on top of authenticating a buffered packet. It would also show each receiver that the sender of each arriving packet knew the next key back along the hash chain. That key is now only disclosed once, kinda like S/KEY [22] 🔐 So a lowkey smart receiver strategy is to discard any arriving packet that discloses a key it has already seen. The receiver's buffer would then fill only as fast as the genuine sender reveals packets, which prevents memory flooding attacks 🛡️

An attacker with control of a network element, or of a faster bypass network, could intercept messages and overtake or replace them with different messages that still use the same keys. Still, as long as packets are only buffered when they also pass the delay safety test, those bogus packets will fail TESLA verification after the disclosure delay 💀 Admittedly, receivers could be fooled into discarding genuine messages that were overtaken by bogus ones. But it's hard to overtake messages without compromising a network element, and any attacker who can compromise a network element can discard genuine messages anyway 🙈 Okay, let's get into the details.

For the sender, the scheme is hardly different from TESLA. It just uses an interval duration short enough to make sure there's a new key back along the hash chain for each packet ✨ So the rule of thumb for an efficient re-keying interval T_int in Section 3.2 no longer applies. Instead, T_int is simply n, the inter-arrival time between packets in milliseconds. The rule of thumb for calculating d, the key disclosure delay, stays the same as the one in Section 3.6 🎀

If the packet rate is likely to vary, n should be taken as the minimum inter-departure time between any two packets, for safety 🫣 (Honestly, n doesn't need to be that strict. It can be the minimum average packet inter-departure time over any burst of d packets expected throughout the session.)

Note that if the packet rate slows down, then whenever no packets are sent in a key change interval, the key index has to increment along the hash chain once for each missed interval 🌸 (During a burst, if the less strict definition of n above has been used, packets may need to depart before their key change interval. The sender can safely keep changing the key for each packet, using keys from future key intervals, because if n has been chosen as defined above, such bursts will never last long enough to cause the associated key to be disclosed in a period less than the disclosure delay later.)

To be absolutely clear, the precise guarantees the sender keeps by following the guidance above are:

• not to re-use a MAC key,
• not to use a MAC key K_i after its time interval i, and
• not to disclose key K_i sooner than the disclosure delay d * T_int following the packet it protects.

Sender setup, receiver bootstrapping, and broadcasting authenticated messages are otherwise all identical to the descriptions in Sections 3.2, 3.3, and 3.4, respectively 🧁 However, the following step has to be added to the receiver authentication steps in Section 3.5:

• After Step 2, if a packet arrives carrying a key index i-d that has already been received, it should not be buffered.

This simple scheme would be enough against DoS, if it weren't for the fact that a network sometimes misorders packets without being compromised 😩 Even without control of a network element, an attacker can opportunistically exploit those openings to fool a receiver into buffering a bogus packet and discarding a later genuine one. A receiver can choose to set aside a fixed-size cache, and manage it to minimise the chances of discarding a genuine packet. However, since these vulnerabilities are rare and unpredictable, it's simpler to count these events as additions to the network loss rate. And as always, TESLA authentication will still uncover any bogus packets after the disclosure delay 💅

To sum up, avoiding re-using keys has the following properties, even under extreme flooding attacks 👑

• After delayed TESLA authentication, packets arriving within the disclosure delay will always be identified as authentic if they are, and as inauthentic if they are not authentic.
• The fill rate of the receiver's buffer is clocked by each packet revealed by the genuine sender, preventing memory flooding attacks.
• An attacker with control of a network element can cause any loss rate it chooses (but that's always true anyway) 🙃
• Where attackers do not have control of any network elements, the effective loss rate is bounded by the sum of the network's actual loss rate and its re-ordering rate.

3.7.3. Sender Buffering 🧚

Buffering of packets can be moved to the sender side, so receivers can authenticate packets immediately upon receipt. This method is described in [14] 🌈

3.8. Some Extensions ✨

Let's mention two salient extensions of the basic TESLA scheme 💜 The first allows a single stream to have multiple TESLA authentication chains, where each chain uses a different delay for disclosing its keys. This is typically used to deal with heterogeneous network delays within a single multicast transmission. The second allows most of the buffering of packets to happen at the sender side (rather than at the receiver side). Both extensions are described in [14] 🦋

TESLA's requirement that a key be received in a later packet for authentication means a receiver can't authenticate the last part of a message. So, to enable authentication of the last part of a message, or of the last message before a transmission suspension, the sender needs to send an empty message with the key 🫶

4. Layer Placement 🎀

TESLA authentication can be performed at any layer in the networking stack. Three natural places are the network, transport, or application layer. Here are some considerations regarding the choice of layer 🤔

• Performing TESLA in the network layer has the advantage that the transport or application layer only receives authenticated data, which could potentially aid a reliability protocol and mitigate denial of service attacks. (Indeed, reliable multicast tools based on forward error correction are highly susceptible to denial of service due to bogus packets 😭)
• Performing TESLA in either the transport or the application layer has the advantage that the network layer remains unchanged. But it has the potential drawback that packets are obtained by the application layer only after being processed by the transport layer. So if buffering is used in the transport, it may introduce additional and unpredictable delays on top of the unavoidable network delays.
• Note that because TESLA relies upon the timing of packets, deploying TESLA on top of a protocol or layer that aggressively buffers packets and hides the true packet arrival time will significantly reduce TESLA's performance 📉

5. Security Considerations 🔥

Okay, this section is serious, bestie, so listen up 🚨 See the academic publications on TESLA [7,13,19] for several security analyses. Regarding the security of implementations, by far the most delicate point is the verification of the timing conditions. Care should be taken to make sure that (a) the value bound D_t on the clock skew is calculated according to the spec at session setup, and that (b) the receiver records the arrival time of the packet as soon as possible after the packet's arrival, and computes the safety condition correctly 😱

It should be noted that a change to the key disclosure schedule for a message stream should never be declared within the message stream itself. This would introduce a vulnerability, because a receiver that did not receive the notification of the change would still believe in the old key disclosure schedule 💀

Finally, in common with all authentication schemes, if verification is located separately from the ultimate destination application (for example, an IPSec tunnel end point), a trusted channel must be present between verification and the application. For instance, the interface between the verifier and the application might simply assume that packets received by the application must have been verified by the verifier (because otherwise they would have been dropped). The application is then vulnerable to reception of packets that have managed to bypass the verifier 🙅‍♀️

6. Acknowledgements 🫶

We would like to thank the following for their feedback and support: Mike Luby, Mark Baugher, Mats Naslund, Dave McGrew, Ross Finlayson, Sylvie Laniepce, Lakshminath Dondeti, Russ Housley, and the IESG reviewers 💖🌸

7. Informative References ✨

okay bestie, here are the receipts 🧾💅 every source the spec leaned on, all listed out.

• [1] Dierks, T. and C. Allen, "The TLS Protocol Version 1.0", RFC 2246, January 1999.
• [2] IPsec, "IP Security Protocol, IETF working group" http://www.ietf.org/html.charters/OLD/ipsec-charter.html.
• [3] D. Boneh, G. Durfee, and M. Franklin, "Lower bounds for multicast message authentication," in Advances in Cryptology -- EUROCRYPT 2001 (B. Pfitzmann, ed.), Vol. 2045 of Lecture Notes in Computer Science, (Innsbruck, Austria), p. 434-450, Springer-Verlag, Berlin Germany, 2001. 🌈
• [4] R. Gennaro and P. Rohatgi, "How to Sign Digital Streams", tech. rep., IBM T.J.Watson Research Center, 1997.
• [5] P. Rohatgi, "A compact and fast hybrid signature scheme for multicast packet authentication", 6th ACM Conference on Computer and Communications Security , November 1999. 🔥
• [6] C. K. Wong and S. S. Lam, "Digital signatures for flows and multicasts," in Proc. IEEE ICNP `98, 1998.
• [7] A. Perrig, R. Canetti, J. Tygar, and D. X. Song, "Efficient authentication and signing of multicast streams over lossy channels", IEEE Symposium on Security and Privacy, May 2000. ✨
• [8] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, "Multicast security: A taxonomy and some efficient constructions", Infocom '99, 1999.
• [9] S. Cheung, "An efficient message authentication scheme for link state routing", 13th Annual Computer Security Applications Conference, 1997.
• [10] F. Bergadano, D. Cavagnino, and B. Crispo, "Chained stream authentication," in Selected Areas in Cryptography 2000, (Waterloo, Canada), August 2000. A talk describing this scheme was given at IBM Watson in August 1998. 🦋
• [11] F. Bergadano, D. Cavalino, and B. Crispo, "Individual single source authentication on the mbone", ICME 2000, August 2000. A talk containing this work was given at IBM Watson, August 1998.
• [12] A. Perrig and J. D. Tygar, Secure Broadcast Communication in Wired and Wireless Networks Kluwer Academic Publishers, October 2002. ISBN 0792376501. 📚
• [13] A. Perrig, R. Canetti, J. D. Tygar, and D. Song, "The tesla broadcast authentication protocol," RSA CryptoBytes, Volume 5, No. 2 Summer/Fall 2002.
• [14] A. Perrig, R. Canetti, D. Song, and J. D. Tygar, "Efficient and secure source authentication for multicast", Network and Distributed System Security Symposium, NDSS '01, p. 35-46, February 2001.
• [15] Mills, D., "Network Time Protocol (Version 3) Specification, Implementation and Analysis", RFC 1305, March 1992. ⏰
• [16] B. Simons, J. Lundelius-Welch, and N. Lynch, "An overview of clock synchronization", Fault-Tolerant Distributed Computing (B. Simons and A. Spector, eds.), No. 448 in LNCS, p. 84-96, Springer-Verlag, Berlin Germany, 1990.
• [17] D. Mills, "Improved algorithms for synchronizing computer network clocks", Proceedings of the conference on Communications architectures, protocols and applications, SIGCOMM 94, (London, England), p. 317-327, 1994.
• [18] L. Lamport and P. Melliar-Smith, "Synchronizing clocks in the presence of faults", J. ACM, Volume 32, No. 1, p. 52-78, 1985.
• [19] P. Broadfoot and G. Lowe, "Analysing a Stream Authentication Protocol using Model Checking", Proceedings of the 7th European Symposium on Research in Computer Security (ESORICS), 2002.
• [20] M. Jakobsson, "Fractal hash sequence representation and traversal", Cryptology ePrint Archive, http://eprint.iacr.org/2002/001/, January 2002. 🧚
• [21] D. Coppersmith and M. Jakobsson, "Almost optimal hash sequence traversal", Proceedings of the Sixth International Financial Cryptography Conference (FC '02), March 2002.
• [22] Haller, N., "The S/KEY One-Time Password System", RFC 1760, February 1995. 🔑

---

Authors' Addresses 🎀

meet the squad who made this happen 🫶

Adrian Perrig
ECE Department
Carnegie Mellon University
Pittsburgh, PA 15218
US

EMail: perrig@cmu.edu


Ran Canetti
IBM Research
30 Saw Mill River Rd
Hawthorne, NY 10532
US

EMail: canetti@watson.ibm.com


Dawn Song
ECE Department
Carnegie Mellon University
Pittsburgh, PA 15218
US

EMail: dawnsong@cmu.edu


J. D. Tygar
UC Berkeley - EECS & SIMS
102 South Hall 4600
Berkeley, CA  94720-4600
US

EMail: doug.tygar@gmail.com


Bob Briscoe
BT Research
B54/77, BT Labs
Martlesham Heath
Ipswich, IP5 3RE
UK

EMail: bob.briscoe@bt.com

---

Full Copyright Statement 🦋

Copyright (C) The Internet Society (2005).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property 💜

the IETF is not picking sides on who owns what 🙈 it takes no position on the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document, or on the extent to which any license under such rights might or might not be available. it also doesn't claim to have made any independent effort to identify any such rights. info on how rights work for RFC documents lives in BCP 78 and BCP 79.

copies of IPR disclosures made to the IETF Secretariat, any assurances of licenses to be made available, or the result of an attempt to get a general license or permission for implementers or users to use these proprietary rights can all be found in the IETF on-line IPR repository at http://www.ietf.org/ipr.

the IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology required to implement this standard. send that info to the IETF at ietf-ipr@ietf.org. 📬

Acknowledgement 🌸

funding for the RFC Editor function is currently provided by the Internet Society. thank you to them for keeping the whole operation running 🫶✨