Generic Attacks on Feistel Schemes

摘要

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: 1. It is possible to distinguish A from a random permutation from 2n bits to 2n bits after doing at most O(2(3n)/4) computations with O(2(3n)/4) random plaintext/ciphertext pairs. 2. It is possible to distinguish A from a random permutation from 2n bits to 2n bits after doing at most O(2(3n)/2) computations with O(2(3n)/2) chosen plaintexts. Since the complexities are smaller than the number 2{sup}(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. O(1)) permutations of the generator and by using a total number of O(2{sup}(2n)) queries and a total of O(2{sup}(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.