Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / High-Degree Indicator Matrix, Feistel Network, ANF, Linear Approximation Table, Walsh Spectrum, Division Property, Integral Attack

Original Publication (with major differences): IACR-FSE-2016

Date: received 21 Apr 2016

Contact author: leo perrin at uni lu

Available format(s): PDF | BibTeX Citation

Version: 20160421:205659 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]