next up previous
Next: Our Extensions Up: An Overview of TESLA Previous: Sending Authenticated Packets

Receiver Tasks

Since the security of TESLA depends on keys that remain secret until a pre-determined time period, the receiver must verify for each packet that the key, which is used to compute the MAC of that packet, is not yet disclosed by the sender. Otherwise, an attacker could have changed the message data and re-computed the MAC. This motivates the security condition, which the receiver must verify for each packet it receives.

Security condition: A packet arrived safely, if the receiver is assured that the sender cannot yet be in the time interval in which the corresponding key is disclosed.

The intuition is that if a packet satisfies the security condition, then no attacker could have altered it in transit, because the corresponding MAC key is not yet disclosed. In case the security condition is not valid, the receiver must drop that packet, because the authenticity is not assured any more. We would like to emphasize that the security of this scheme does not rely on any assumptions on network propagation delay. The original paper sketches a security proof [25].

We now explain how the authentication with TESLA works with a concrete example. When the receiver receives packet Pj sent in interval Ii at local time tc, it computes an upper bound on the sender's clock tj (we describe in section 3.3 how to compute this). To evaluate the security condition, the receiver computes the highest interval x the sender could possibly be in, which is x = (tj - T0) / Tint . The receiver now verifies that x < Ii + d (where Ii is the interval index), which means that the sender must not have been in the interval in which the key Ki is disclosed, hence no attacker can possibly know that key and spoof the message contents.

The receiver cannot, however, verify the authenticity of the message yet. Instead, it stores the triplet ( Ii, Mj, MAC( K'i, Mj) ) to verify the authenticity later when it knows K'i. Two possibilities exist on how to handle the unauthenticated message chunk Mj. The first possibility is to hand Mj to the application, and notify it through a callback mechanism as soon as Mj is verified. The second possibility is to buffer Mj until the authenticity can be checked and pass it to the application as soon as Mj is authenticated.

If the packet contains a disclosed key Ki-d, regardless of whether the security condition is verified or not, the receiver checks whether it can use Ki-d to authenticate previous packets. Clearly, if it has received Ki-d previously, it does not have any work to do. Otherwise, let us assume that the last key value in the reconstructed key chain is Kv. The receiver verifies if Ki-d is legitimate by verifying that Kv = Fi-d-v(Ki-d). If that condition is correct, the receiver updates the key chain. For each new key Kw, it computes K'w = F'(Kw) which might allow it to verify the authenticity of previously received packets.

It is clear that this system can tolerate arbitrary packet loss, because the receiver can verify the authenticity of all received packets that satisfy the security condition eventually.


next up previous
Next: Our Extensions Up: An Overview of TESLA Previous: Sending Authenticated Packets

Adrian Perrig
Sun Nov 5 19:29:44 PST 2000