Distinguishing attack on four rounds of the Luby — Rackoff cipher by differentials of two-block texts

We show that the Luby — Rackoff cipher (Feistel network with block length $n=2m$, random independent round functions $f^1,\ldots,f^R:\mathbb{Z}_2^m\to\mathbb{Z}_2^m$) is a Markov cipher. Matrices $\mathbb{P}^R$ of $R$-round transition probabilities of differentials have been found for $R=1,2,4$ and arbitrary $m$. Let $(p_2(\Delta y),y\in\mathbb{X}')$ be the conditional probability distribution of the 4-round output differential under the fixed input differential $\Delta x=(\Delta x_0,\Delta x_1)$, $p_1(\Delta y)=(M^2-1)^{-1}$ — the uniform distribution on the $\mathbb{X}'=\mathbb{Z}_2^{2m}\setminus\{\vec0\}$, $M=2^m$. We have obtained expressions for Kullback divergences between the distributions and prove that: 1) if $(\Delta x_0=0 \wedge \Delta x_1\ne 0) \vee (\Delta x_0\ne 0 \wedge \Delta x_1\ne 0)$, then $K(2:1)\sim (2\ln2-1)M^{-2}$, $K(1:2)\sim (1-\ln2) M^{-2}$ as $M\to\infty$; 2) if $\Delta x_0\ne 0, \Delta x_1=0$, then $K(2:1)\sim (2\ln2-1)M^{-1}$, $K(1:2)\sim (1-\ln2) M^{-1}$. Therefore, in the second case distinguishing attack (based on the statistics of the logarithm of the likelihood ratio in the model of independent two-block texts) will be more powerful. In particular, for error probabilities $\alpha=\beta=0{,}1$ and large $M$, the average values of text amounts are approximately equal $T_1(M)=\dfrac{0{,}8\ln9}{1-\ln2}M=5{,}72 M$, $T_2(M)=\dfrac{0{,}8\ln9}{2\ln2-1}M=4{,}55 M$. In statistical experiments for $12\le n\le 44$ empirical probabilities of errors are close to the specified $\alpha,\beta$ and amounts of texts are close to the calculated values $T_1(M),T_2(M)$.