Paper 2008/036

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 $$ bits to $$ bits after doing at most $$ computations with $$ non-adaptive {\bf chosen} plaintexts. \item It is possible to distinguish $$ from a random permutation from $$ bits to $$ bits after doing at most $$ computations with $$ {\bf random} plaintext/ciphertext pairs. \end{enumerate} Since the complexities are smaller than the number $$ of possible inputs, they show that some generic attacks always exist on Feistel schemes with $$ rounds. Therefore we recommend in Cryptography to use Feistel schemes with at least $$ rounds in the design of pseudo-random permutations. We will also show in this paper that it is possible to distinguish most of $$ round Feistel permutations generator from a truly random permutation generator by using a few (i.e. $$) permutations of the generator and by using a total number of $$ queries and a total of $$ computations. This result is not really useful to attack a single $$ 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 $$ 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}

Note: pdf file instead of ps file