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 $2n$ bits to $2n$ bits after doing at most ${\cal O}(2^{n})$ computations with ${\cal O}(2^{n})$ nonadaptive {\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 pseudorandom 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 pseudorandom 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}
Note: pdf file instead of ps file
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. 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.
 Keywords
 Feistel permutationspseudorandom permutationsgeneric attacks on encryption schemesLubyRackoff theory
 Contact author(s)
 valerie nachef @ ucergy fr
 History
 20080128: received
 Short URL
 https://ia.cr/2008/036
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/036, author = {Jacques Patarin}, title = {Generic Attacks on Feistel Schemes}, howpublished = {Cryptology ePrint Archive, Paper 2008/036}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/036}}, url = {https://eprint.iacr.org/2008/036} }