The Security of Feistel Ciphers with Six Rounds or Less

This paper considers the security of Feistel networks where the round functions are chosen at random from a family of 2 ^k randomly chosen functions for any k . Also considered are the networks where the round functions are themselves permutations, since these have applications in practice. The constructions are attacked under the assumption that a key-recovery attack on one round function itself requires an exhaustive search over all 2 ^k possible functions. Attacks are given on all three-, four-, five-, and six-round Feistel constructions and interesting bounds on their security level are obtained. In a chosen text scenario the key recovery attacks on the four-round constructions, the analogue to the super pseudorandom permutations in the Luby and Rackoff model, take roughly only the time of an exhaustive search for the key of one round. A side result of the presented attacks is that some constructions, which have been proved super pseudorandom in the model of Luby and Rackoff, do not seem to offer more security in our model than constructions which are not super pseudorandom.