The security of Feistel ciphers with six rounds or less (Q1849601)

\textit{M. Luby} and \textit{C. Rackoff} [SIAM J. Comput. 17, 373-386 (1988; Zbl 0644.94018)] showed a method for constructing pseudorandom permutations from pseudorandom functions by using three or four rounds of Feistel networks. The security of their construction as well as others suggested later is measured in terms of the complexity of distinguishing the outputs from the outputs of a truly random function. In this paper, a different approach is proposed. Namely, it is assumed that the round functions in the Feistel network are chosen at random from just a subset of \(2^k\) randomly chosen functions instead of the set of all functions. As each round function can be specified by a \(k\)-bit key, the security of the resulting permutations is then investigated as the complexity of finding all the keys of the cipher with \(r\) rounds. Using this approach attacks on all three-, four-, five-, and six-round Feistel constructions, where round functions are either functions or permutations, are given and their complexity analyzed. Also it is shown that a construction which is super pseudorandom in the Luby-Rackoff model is not necessarily stronger than a construction which is pseudorandom when translated into the model proposed. Finally, using the DES as the round function in a Feistel construction is briefly discussed.