Scheme II: Tolerating Packet Loss

 

To authenticate lossy multimedia streams, tolerating packet loss is paramount. Our solution is to generate a sequence of keys $\{K$_i} 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 $K$_n and pre-computes a sequence of $n$ key values, where $K$₀ = Fⁿ(K_n), and $K$_i = F^n-i(K_n). We call this sequence of values the key chain. Each $K$_i looks pseudorandom to an attacker; in particular, given $K$_i, the attacker cannot invert $F$ and compute any $K$_j for $j\; >\; i$. On the other hand, the receiver can compute all $K$_j from a $K$_i it received, where , since $K$_j = F^i-j(K_i). Hence, if a receiver received packet $P$_i, any subsequently received packet will allow it to compute $K$_i and $K$_i' = F'(K_i) and verify the authenticity of $P$_i. 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.

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.

Kim2$K\text{'}$_i-2 Kim1$K\text{'}$_i-1 Ki$K\text{'}$_i Kip1$K\text{'}$_i+1 F$F\text{'}$ f$F$

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