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
-
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},
url = {https://eprint.iacr.org/2016/398}
}