[Resource Topic] 2015/723: Cryptanalysis of Feistel Networks with Secret Round Functions

Welcome to the resource topic for 2015/723

Cryptanalysis of Feistel Networks with Secret Round Functions

Authors: Alex Biryukov, Gaëtan Leurent, Léo Perrin


Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions. When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called \textit{yoyo game} which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to O(2^{2n}) encryptions where n is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively O(2^{n2^{n-1}+2n}) and O(2^{n2^{n}+2n}). However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity O(2^{n2^{3n/4}}). Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.

ePrint: https://eprint.iacr.org/2015/723

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 .