next up previous
Next: Scheme III: Achieving Fast Up: TESLA: Timed Efficient Stream Previous: Scheme I: The Basic

Scheme II: Tolerating Packet Loss

 

To authenticate lossy multimedia streams, tolerating packet loss is paramount. Our solution is to generate a sequence of keys {Ki} through a sequence generated through pseudo-random function applications. We denote v consecutive applications of the pseudo-random function F as Fv(x) = Fv-1(F(x)). By convention, F0(x) = x. The sender picks a random Kn and pre-computes a sequence of n key values, where K0 = Fn(Kn), and Ki = Fn-i(Kn). We call this sequence of values the key chain. Each Ki looks pseudorandom to an attacker; in particular, given Ki, the attacker cannot invert F and compute any Kj for j > i. On the other hand, the receiver can compute all Kj from a Ki it received, where j < i, since Kj = Fi-j(Ki). Hence, if a receiver received packet Pi, any subsequently received packet will allow it to compute Ki and Ki' = F'(Ki) and verify the authenticity of Pi. This scheme tolerates an arbitrary number of packet losses.

Similarly, dropping unsafe packets (i.e. those packets where the security condition does not hold) does not cause any problems in the authentication of later packets.

In the basic scheme I, an adversary might try to capture two consecutive packets before the recipient received the first of them, and then forge the packet stream. Although the security condition prevents this, the key chain also prevents this attack, because the initial commitment commits to the entire key chain and it is computationally infeasible for the attacker to invert or find collisions in the pseudo-random function.gif

An additional benefit is that the key commitment does not need to be embedded in each packet any more. Due to the intractability of inverting the pseudo-random function, any value of the chain is a commitment for the entire chain. Hence the commitment in the initial authenticated packet is sufficient. Figure 2 shows an example of scheme II.

Kim2K'i-2 Kim1K'i-1 KiK'i Kip1K'i+1 FF' fF

 figure273
Figure 2: Scheme II. The packet format is the same as in scheme I, except that the commitment F(Ki-1) is omitted and the keys form a one-way key chain. 


next up previous
Next: Scheme III: Achieving Fast Up: TESLA: Timed Efficient Stream Previous: Scheme I: The Basic

Adrian Perrig
Sat Sep 2 17:01:14 PDT 2000