where || denotes concatenation.
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
Once a sender discloses a key, we must assume that all parties might
have access to that key. An adversary could create a bogus message
and forge a MAC using the disclosed key. So whenever a packet
arrives, the receiver must verify that the MAC is based on a safe
key; a safe key is one that is still secret (known only by the
sender). We define a safe packet or safe message as one with a MAC
that is computed with a safe key.
If a packet proves safe, it will be buffered, only to be released
when its own key, disclosed in a later packet, proves its
authenticity. Although a newly arriving packet cannot immediately be
authenticated, it may disclose a new key so that earlier, buffered
packets can be authenticated. Any newly disclosed key must be
checked to determine whether it is genuine; then authentication of
buffered packets that have been waiting for it can proceed.
We now describe TESLA authentication at the receiver with more
detail, listing all of these steps in the exact order they should be
carried out:
1. Safe packet test: When the receiver receives packet P_j, which
carries an interval index i, and a disclosed key K_{i-d}, it
first records local time T at which the packet arrived. The
receiver then computes an upper bound t_j on the sender’s
clock at the time when the packet arrived: t_j = T + D_t. To
test whether the packet is safe, the receiver then computes
the highest interval x the sender could possibly be in; namely
x = floor((t_j - T_0) / T_int). The receiver verifies that x
< i + d (where i is the interval index), which implies that
the sender is not yet in the interval during which it
discloses the key K_i.
Even if the packet is safe, the receiver cannot yet verify the
authenticity of this packet sent in interval i without key
K_i, which will be disclosed later. Instead, it adds the
triplet ( i, M_j, MAC( K’_i, M_j) ) to a buffer and verifies
the authenticity after it learns K’_i.
If the packet is unsafe, then the receiver considers the
packet 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
legitimate, 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 will compute K’_{i-d} = F’(K_{i-d}) from which it can
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 do not agree, the buffered packet P_h should be
discarded.
The receiver continues to verify and release (or not) any
remaining buffered packets that depend on the newly disclosed
key K_{i-d}.
Using a disclosed key, we can calculate all previous disclosed keys,
so even if packets are lost, we will still be able to verify
buffered, safe packets from earlier time intervals. Thus, 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
An important TESLA parameter is the key disclosure delay d. Although
the choice of the disclosure delay does not affect the security of
the system, it is an important performance factor. A short
disclosure delay will cause packets to lose their safety property, so
receivers will not be able to authenticate them; but a long
disclosure delay leads to a long authentication delay for receivers.
We recommend determining the disclosure delay as follows: 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. Note that rounding
up the quotient ensures that d >= 2. Also note that a disclosure
delay of one time interval (d=1) does not work. Consider packets
sent close to the boundary of the time interval: After the network
propagation delay and the receiver time synchronization error, a
receiver will not be able to authenticate the packet, because the
sender will already be in the next time interval when it discloses
the corresponding key.
Measuring the delay to each receiver before determining m will still
not adequately predict the upper bound on delay to late joiners, or
where congestion delay rises later in the session. It may be
adequate to use a hard-coded historic estimate of worst-case delay
(e.g., round trip delays to any host on the intra-planetary Internet
rarely exceed 500msec if routing remains stable).
We stress that the security of TESLA does not rely on any assumptions
about network propagation delay: If the delay is longer than
expected, then authentic packets may be considered unauthenticated.
Still, no inauthentic packet will be accepted as authentic.
3.7. Denial of Service Protection
Because TESLA authentication is delayed, receivers seem vulnerable to
flooding attacks that cause them to buffer excess packets, even
though they may eventually prove to be inauthentic. When TESLA is
deployed in an environment with a threat of flooding attacks, the
receiver can take a number of extra precautions.
First, we list simple DoS mitigation precautions that can and should
be taken by any receiver independently of others, thus requiring no
changes to the protocol or sender behaviour. We precisely specify
where these extra steps interleave with the receiver authentication
steps already given in Section 3.5.
o 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 do not replay a message
already received in the session, and that they are not
significantly larger than the packet sizes expected in the
session.
o 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; thus, for example, i-d-v <= g. g sets the
threshold beyond which an out-of-order key index is assumed to
be malicious rather than just misordered. Without this test, an
attacker could exploit the iterated test in Step 3 to make
receivers consume inordinate CPU time checking along the hash
chain for what appear to be extremely misordered packets.
Each receiver can independently adapt g to prevailing attack
conditions; for instance, by using the following 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 is already g_max.
These precautions will guarantee that sustained attack packets
cannot cause the receiver to execute more than an average of
g_min hashes each, unless they are paced against genuine
packets. In the latter case, attacks are limited to
g_max/(g_max-g_min) hashes per each genuine packet.
When choosing g_max and g_min, note 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 requires that both senders and receivers
arrange additional constraints on the protocol. Below, we outline
three alternative extensions to basic TESLA; the first adding group
authentication, the second not re-using keys during a time interval,
and the third moving buffering to the sender.
It is important to understand the applicability of each scheme, as
the first two schemes use slightly more (but bounded) resources in
order to prevent attackers from consuming unbounded resources.
Adding group authentication requires larger per-packet overhead.
Never re-using a key requires both ends to process two hashes per
packet (rather than per time interval), and the sender must store or
re-generate a longer hash chain. The merits of each scheme,
summarised after each is described below, must be weighed against
these additional costs.
3.7.1. Additional Group Authentication
This scheme simply involves addition of a group MAC to every packet.
That is, a shared key K_g common to the whole group is communicated
as an additional step during receiver bootstrap (Section 3.3). Then,
during broadcast of message M_j (Section 3.4), the sender computes
the group MAC of each packet MAC(K_g, P_j), which it appends to the
packet header. Note that the group MAC covers the whole packet P_j;
that is, the concatenation of the message M_j and the additional
TESLA authentication material, using the formula in Section 3.4.
Immediately upon packet arrival, each receiver can check that each
packet came from a group member, by recomputing and comparing the
group MAC.
Note that TESLA source authentication is only necessary when other
group members cannot be trusted to refrain from spoofing the source;
otherwise, simpler group authentication would be sufficient.
Therefore, additional group authentication will only make sense in
scenarios where other group members are trusted to refrain from
flooding the group, but where they are still not trusted to refrain
from spoofing the source.
3.7.2. Not Re-using Keys
In TESLA as described so far, each MAC key was used repeatedly for
all the packets sent in a time interval. If instead the sender were
to guarantee never to use a MAC key more than once, each disclosed
key could assume an additional purpose on top of authenticating a
previously buffered packet. Each key would also immediately show
each receiver that the sender of each arriving packet knew the next
key back along the hash chain, which is now only disclosed once,
similar to S/KEY [22]. Therefore a reasonable receiver strategy
would be to discard any arriving packets that disclosed a key seen
already. The fill rate of the receiver’s buffer would then be
clocked by each packet revealed by the genuine sender, preventing
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 but with the same keys. However, as long as
packets are only buffered if they also pass the delay safety test,
these bogus packets will fail TESLA verification after the disclosure
delay. Admittedly, receivers could be fooled into discarding genuine
messages that had been overtaken by bogus ones. But it is hard to
overtake messages without compromising a network element, and any
attacker that can compromise a network element can discard genuine
messages anyway. We will now describe this scheme in more detail.
For the sender, the scheme is hardly different from TESLA. It merely
uses an interval duration short enough to ensure a new key back along
the hash chain for each packet. So the rule of thumb given in
Section 3.2 for an efficient re-keying interval T_int 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, remains unchanged from that given in Section
3.6.
If the packet rate is likely to vary, for safety n should be taken as
the minimum inter-departure time between any two packets. (In fact,
n need not be so 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, whenever no packets are sent
in a key change interval, the key index must 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
continue 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 sustain 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 that the sender keeps
to by following the above guidance are:
o not to re-use a MAC key,
o not to use a MAC key K_i after its time interval i, and
o 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 must be
added to the receiver authentication steps in Section 3.5:
o 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 suffice against DoS, were it not for the
fact that a network sometimes misorders packets without being
compromised. Even without control of a network element, an attacker
can opportunistically exploit such 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 can manage it
to minimise the chances of discarding a genuine packet. However,
given such vulnerabilities are rare and unpredictable, it is simpler
to count these events as additions to the network loss rate. As
always, TESLA authentication will still uncover any bogus packets
after the disclosure delay.
To summarise, avoiding re-using keys has the following properties,
even under extreme flooding attacks:
o 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.
o The fill rate of the receiver’s buffer is clocked by each packet
revealed by the genuine sender, preventing memory flooding
attacks.
o An attacker with control of a network element can cause any loss
rate it chooses (but that’s always true anyway).
o 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; then receivers
can authenticate packets immediately upon receipt. This method is
described in [14].
3.8. Some Extensions
Let us mention two salient extensions of the basic TESLA scheme. A
first extension allows having multiple TESLA authentication chains
for a single stream, where each chain uses a different delay for
disclosing the keys. This extension is typically used to deal with
heterogeneous network delays within a single multicast transmission.
A second extension allows having most of the buffering of packets 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 prevents a receiver from authenticating the last part
of a message. Thus, 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. We list some considerations regarding the choice
of layer:
o Performing TESLA in the network layer has the advantage that the
transport or application layer only receives authenticated data,
potentially aiding a reliability protocol and mitigating denial
of service attacks. (Indeed, reliable multicast tools based on
forward error correction are highly susceptible to denial of
service due to bogus packets.)
o 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. Consequently, if buffering is used in the
transport, then this may introduce additional and unpredictable
delays on top of the unavoidable network delays.
o Note that because TESLA relies upon 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
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
(e.g., 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
[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