PRF-PRF Attack

Both attacks focus on consecutive pairs of outputs generated by . Clearly, LevPair generates the same -byte keystream as Lev, so a distinguisher for one is a distinguisher for the other. Such pairs are interesting because they are the most closely related outputs in the tree structure; [5] refers to attacks using such pairs as ``up-and-down attacks''. We can expand the formula for LevPair as follows:

$$\begin{eqnarray*} \textrm{LevPair}(t\vert z) & = & (\textrm{Lev}(t\vert z\vert),... ...D_{1\vert z}(V(t,1\vert z)))),C(G(D_{1\vert z}(V(t,1\vert z))))) \end{eqnarray*}$$

From this we define functions LevAbove which generates the last common ancestor of such an output pair as illustrated in Figure 2, and PairCom which generates the output pair from the ancestor:

$$\begin{eqnarray*} \textrm{LevAbove}(t\vert z) & = & D_{1\vert z}(V(t,1\vert z))\... ...z\vert=h-1)\\ \textrm{PairCom}(x,y) & = & (C(F(x,y)),C(G(x,y))) \end{eqnarray*}$$

from which we can see as stated. We model LevAbove as a random function throughout, and focus on the properties of PairCom.

Figure 2: Final stage of LevPair output; LevAbove finds the last common ancestor of the pair.

This structure gives us our first distinguisher. Though PairCom has the same domain as range, it is not in general bijective; it can be modelled more accurately as a random function. Thus a collision can occur in LevPair, given two distinct inputs, if there is a collision either in LevAbove or in PairCom, and if we model both as random functions the probability of an output collision for two random distinct inputs to LevPair is thus approximately , twice what it should be if the keystream were a random binary string.

For , this increased probability of collisions between output word pairs can be observed with a birthday attack after around output pairs ( bytes) have been generated; the techniques of [8] may be used to reduce the memory demands of this attack, though this slows the attack by a factor of approximately where is the height of the tree, since probes can no longer take advantage of the higher efficiency of sampling consecutive values of LevPair.