**Generic Attacks on Feistel Schemes**

*Jacques Patarin*

**Abstract: **
\begin{abstract}
Let $A$ be a Feistel scheme with $5$ rounds from $2n$ bits to $2n$
bits. In the present paper we show that for most such schemes $A$:
\begin{enumerate}
\item It is possible to distinguish $A$ from a random
permutation from $2n$ bits to $2n$ bits
after doing at most ${\cal O}(2^{n})$ computations with ${\cal
O}(2^{n})$ non-adaptive {\bf chosen} plaintexts.
\item It is possible to distinguish $A$ from a random
permutation from $2n$ bits to $2n$ bits
after doing at most ${\cal O}(2^{\frac{3n}{2}})$ computations with
${\cal O}(2^{\frac{3n}{2}})$ {\bf random} plaintext/ciphertext
pairs.

\end{enumerate} Since the complexities are smaller than the number $2^{2n}$ of possible inputs, they show that some generic attacks always exist on Feistel schemes with $5$ rounds. Therefore we recommend in Cryptography to use Feistel schemes with at least $6$ rounds in the design of pseudo-random permutations.

We will also show in this paper that it is possible to distinguish most of $6$ round Feistel permutations generator from a truly random permutation generator by using a few (i.e. ${\cal O}(1)$) permutations of the generator and by using a total number of ${\cal O}(2^{2n})$ queries and a total of ${\cal O}(2^{2n})$ computations. This result is not really useful to attack a single $6$ round Feistel permutation, but it shows that when we have to generate several pseudo-random permutations on a small number of bits we recommend to use more than $6$ rounds.

We also show that it is also possible to extend these results to any number of rounds, however with an even larger complexity. \end{abstract}

**Category / Keywords: **secret-key cryptography / Feistel permutations, pseudorandom permutations,generic attacks on encryption schemes, Luby-Rackoff theory

**Publication Info: **This paper is an extended version of a paper with the same title published at Asiacrypt'2001 and we have also included here the cryptanalysis of the paper ''Security of Random Feistel Schemes with 5 or more Rounds'' published at Crypto'2004.

**Date: **received 24 Jan 2008, last revised 24 Jan 2008

**Contact author: **valerie nachef at u-cergy fr

**Available format(s): **PDF | BibTeX Citation

**Note: **pdf file instead of ps file

**Version: **20080128:153151 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]