Analysis of Diffusion Properties in Generalized Feistel Ciphers Under Multidimensional Linear Cryptanalysis

This paper presents a unified framework for generic attacks on Generalized Feistel Ciphers, with a primary focus on Type 1, Type 2, and unbalanced contracting (U-Type 1) Feistel constructions with non-invertible round functions. In [OBR23], authors reveal a class of vulnerabilities exploitable via key independent multidimensional linear trails for Feistel Ciphers, yielding efficient generic distinguishing and key-recovery attacks. We extend the work of [OBR23] by formalizing the application of generic multidimensional linear cryptanalysis to Generalized Feistel Ciphers. In this way, we improve upon existing results by extending the maximum number of rounds for the generic distinguishing attack to t2 + 2t − 1 for Type 1 and U-Type 1, and to 2t + 3 for Type 2. Moreover, we have the maximum number of rounds for generic key recovery attacks on (U)-Type 1 as t2 + 3t − 2 and Type 2 as 4t. To the best of our knowledge, these findings yield the best results for the maximum number of rounds in key recovery attacks on the corresponding GFC. We further demonstrate the branch-permutation-independence of these attacks, showing that changing internal permutations does not affect the applicability, complexity, or maximum number of rounds of generic attacks. The effectiveness of our attacks is validated through experiments on the first-round AES candidate CAST-256 and the MPC-friendly block cipher GMiMC. Both theoretical and experimental results confirm that our proposed branch-permutation-independent generic attacks enhance the maximum number of rounds for generic attacks for GFC and reduce complexity across various interesting cases.