Welcome to the resource topic for 2008/036
Title:
Generic Attacks on Feistel Schemes
Authors: 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}
ePrint: https://eprint.iacr.org/2008/036
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .