Paper 2016/398

Algebraic Insights into the Secret Feistel Network (Full version)

Léo Perrin and Aleksei Udovenko


We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a Feistel Network contains very specific patterns depending on the degree of the Feistel functions, the number of rounds and whether the Feistel functions are 1-to-1 or not. We exploit these patterns to distinguish Feistel Networks, even if the Feistel Network is whitened using unknown affine layers. We also present a new type of structural attack exploiting monomials that cannot be present at round $r-1$ to recover the ANF of the last Feistel function of a $r$-round Feistel Network. Finally, we discuss the relations between our findings, integral attacks, cube attacks, Todo's division property and the congruence modulo 4 of the Linear Approximation Table.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2016
High-Degree Indicator MatrixFeistel NetworkANFLinear Approximation TableWalsh SpectrumDivision PropertyIntegral Attack
Contact author(s)
leo perrin @ inria fr
2021-05-31: revised
2016-04-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Léo Perrin and Aleksei Udovenko},
      title = {Algebraic Insights into the Secret Feistel Network (Full version)},
      howpublished = {Cryptology ePrint Archive, Paper 2016/398},
      year = {2016},
      doi = {10.1007/978-3-662-52993-5_19},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.