Improved Meet-in-the-Middle Attacks on Generic Feistel Constructions
Shibin Zhao, Xiaohan Duan, Yuanhao Deng, Zhiniang Peng, Junhu Zhu · IEEE Access · 2019
In this paper, we present improved meet-in-the-middle key-recovery attacks on six-round and seven-round Feistel constructions separately. The attacks are based on Guo et al.'s work which appends one round to the five-round distinguisher to attack the six-round Feistel construction through the meet-in-the-middle method. The proposed method stores only target sequences instead of all the possible sequences, which reduces the memory complexity from 2(3/4)nblocks to 2(n/2)blocks. A new key-recovery attack method on the seven-round Feistel construction is proposed by appending one another round after a five-round distinguisher. What is more, is that we propose a new method called the impossible-differential pairs sieve technique which reduces the data complexity from 2nchosen plaintexts to 3×2n-2chosen plaintexts so that the attack complexity is lower than the exhaustive attack. The time complexity is equivalent to about 3×2n-2encryptions, and the memory complexity is optimized to 2(3/4)nblocks of 2(n/2)bits. To the best of our knowledge, it is the first known generic key-recovery attack on the seven-round Feistel construction with a lower attack complexity when compared with the exhaustive attack.