Geodesic
Distinguishing attack on four rounds of the Luby~--- Rackoff cipher by~differentials of two-block texts
Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 32-36.

Voir la notice de l'article provenant de la source Math-Net.Ru

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)$.
Keywords: Markov cipher, Feistel network, Luby — Rackoff cipher, Kullback divergence, sequential distinguishing attack. 
@article{PDMA_2023_16_a8,
     author = {O. V. Denisov},
     title = {Distinguishing attack on four rounds of the {Luby~---} {Rackoff} cipher by~differentials of two-block texts},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {32--36},
     publisher = {mathdoc},
     number = {16},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2023_16_a8/}
}
TY  - JOUR
AU  - O. V. Denisov
TI  - Distinguishing attack on four rounds of the Luby~--- Rackoff cipher by~differentials of two-block texts
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2023
SP  - 32
EP  - 36
IS  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2023_16_a8/
LA  - ru
ID  - PDMA_2023_16_a8
ER  - 
%0 Journal Article
%A O. V. Denisov
%T Distinguishing attack on four rounds of the Luby~--- Rackoff cipher by~differentials of two-block texts
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2023
%P 32-36
%N 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2023_16_a8/
%G ru
%F PDMA_2023_16_a8
O. V. Denisov. Distinguishing attack on four rounds of the Luby~--- Rackoff cipher by~differentials of two-block texts. Prikladnaya Diskretnaya Matematika. Supplement, no. 16 (2023), pp. 32-36. http://geodesic.mathdoc.fr/item/PDMA_2023_16_a8/

[1] Luby M. and Rackoff C., “How to construct pseudorandom permutations from pseudorandom functions”, SIAM J. Comput., 17 (1988), 373–386 | DOI | MR | Zbl

[2] Nachef V., Patarin J., and Volte E., Feistel Ciphers: Security Proofs and Cryptanalysis, Springer, 2017 | MR | Zbl

[3] Lankaster P., Teoriya matrits, Nauka, M., 1978

[4] Denisov O. V., “Ataki razlicheniya na blochnye shifrsistemy po raznostyam dvublochnykh tekstov”, Prikladnaya diskretnaya matematika, 2020, no. 48, 43–62 | Zbl

[5] Ivchenko G. I., Medvedev Yu. I., Matematicheskaya statistika, Vysshaya shkola, M., 1984 | MR