Paper 2015/723

Cryptanalysis of Feistel Networks with Secret Round Functions

Alex Biryukov, Gaëtan Leurent, and Léo Perrin

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.Selected Areas in Cryptography 2015
Keywords
Feistel NetworkYoyoGeneric AttackGuess-and-determine
Contact author(s)
leo perrin @ uni lu
History
2015-07-21: received
Short URL
https://ia.cr/2015/723
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/723,
      author = {Alex Biryukov and Gaëtan Leurent and Léo Perrin},
      title = {Cryptanalysis of Feistel Networks with Secret Round Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/723},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/723}},
      url = {https://eprint.iacr.org/2015/723}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.