Paper 2016/398

Algebraic Insights into the Secret Feistel Network (Full version)

Léo Perrin and Aleksei Udovenko

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2016
DOI
10.1007/978-3-662-52993-5_19
Keywords
High-Degree Indicator MatrixFeistel NetworkANFLinear Approximation TableWalsh SpectrumDivision PropertyIntegral Attack
Contact author(s)
leo perrin @ inria fr
History
2021-05-31: revised
2016-04-21: received
See all versions
Short URL
https://ia.cr/2016/398
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/398,
      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{https://eprint.iacr.org/2016/398}},
      url = {https://eprint.iacr.org/2016/398}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.