Square reflection cryptanalysis of 5-round Feistel networks with permutations

•New distinguishers are derived for 4-round Feistel Networks with permutational round functions under a weak key condition.•A new generic attack is mounted on 5-round Feistel Networks by combining the square attack and the reflection attack.•Hellman tables are utilized to construct a tradeoff between the time complexity and the memory complexity of the new attack.•The generic attack is applied to 5-round DEAL as a concrete example.•The complexity of the attack on DEAL is 265 DES encryptions, working on a key set of cardinality 272.

In this work, we introduce a new generic attack on 5-round Feistel networks whose round functions are random permutations, under the condition that the second and the fourth round keys are equal. The attack is a combination of the square attack technique with the reflection attack technique and exploits the unbalanced distribution of the fixed points of the inner rounds among all the keys. The data complexity of the attack is ⌈4mn⌉2n/2 chosen plaintexts where ⌈4mn⌉ is the smallest integer bigger than or equal to 4mn, m is the length of a round key and n   is the block length of the Feistel network. We utilize Hellman tables to construct a tradeoff between the time complexity and the memory complexity of the attack which are 23m−2M−123m−2M−1 and 2M2M respectively where M   is the tradeoff parameter. The number of weak keys is 2k−m2k−m where k is the key length. As a concrete example, we mount the attack on 5-round DEAL. Our attack has overall complexity of 265 and works on a key set of cardinality 272 for 128-bit key length.