S-Box Matching Attack

The definitions of the and functions are very similar; is the same as except that it treats its inputs in the opposite order, and inverts one of them. If did not apply bitwise inversion to its first input (call this function ), then the two functions would be related by (with Swap having the obvious definition ); this would mean in turn that for any , and thus that , with the result, as we shall see, that repeating pairs were visible in the output roughly twice as often as they should be. The inversion on the first input of breaks this symmetry; however, it turns out that it does not prevent a related attack.

Computation of PairCom requires 32 S-box lookups, but for each computation of the function the same 8-bit index, drawn from the least significant byte, is fed to each of the four S-boxes. Changes to the other bytes carry directly into the output of , without nonlinearity or mixing; in other words, where , we find . We call this least significant byte the index to the S-box. If is the input to PairCom, only bytes of are indices to S-boxes in , and only bytes are indices in ; by inverting only these two bytes in our pair , we can avoid the symmetry-breaking effect of the inversion as far as the nonlinear components are concerned, which results in the same four S-box indices being used in both the and branches of PairCom.

Figure 3: S-box matching input to . The function is on the left, on the right, and underneath; dotted lines indicate bitwise inversion (the first step of the function) and the `` '' symbol represents the function .

Figure 3 illustrates this attack. For an arbitrary -bit string , we define symbols for intermediate values in :

$$\begin{eqnarray*} b_{3}\vert b_{2}\vert b_{1}\vert b_{0} & = & S(a_{3}\vert a_{2... ...}\vert c_{0})\oplus (c'_{3}\vert c'_{2}\vert c'_{1}\vert c'_{0}) \end{eqnarray*}$$

With these definitions, we find that :

$$\begin{eqnarray*} C(F(x,y)) & = & C(L(S(L(S(x)))),\; S(R(S(R(y)))))\\ & = & C(... ...& = & d_{1}\vert\overline{d_{0}}\vert\overline{d_{3}}\vert d_{2} \end{eqnarray*}$$

From this it is clear that for any input of the appropriate form, one output word is the inverse of the other; or in other words, if we now XOR the two word outputs from PairCom together (which, conveniently, is the same as applying the LEVIATHAN compression function a second time), we find

$$\begin{eqnarray*} C(\textrm{PairCom}(a_{3}\vert\overline{a_{2}}\vert\overline{a_... ...d_{1}\vert\overline{d_{0}}\vert\overline{d_{3}}\vert d_{2}=1^{n} \end{eqnarray*}$$

for all values of .

Since we model LevAbove as a random function we conclude that inputs to PairCom have probability of matching this form in the normal calculation of LevPair. Where inputs do not match this form, we assume that PairCom behaves as a random function and therefore that for random not matching this form, ; this assumption is borne out by experiment. From this we conclude that LevPair is twice as likely as a random function to produce an output such that

$$\textrm{Pr}\left( C(\textrm{LevPair}(t\vert z))=1^{n}\right) =2^{-n}+(1-2^{-n})2^{-n}\approx 2^{1-n}$$

which in turn implies that 64-bit aligned segments of keystream of this form are twice as frequent as they should be, yielding another distinguisher.

For , a test for the presence of this bias should therefore take on the order of samples of LevPair, ie bytes, as for the previous attack.