Meet-in-the-Middle Attacks On Three Types Of Generalized Feistel Constructions

Feistel Construction is proposed by Horst Feistel and Don Coppersmith from IBM when designing Lucifer in 1973.On the one hand,the procedure of encryption and decryption are similar for this construction,on the other hand,it has few limitations to round function.So this construction is widely used in cipher designs.Based on Feistel construction,some extend constructions called generic Feistel scheme?GFS?are proposed,such as three kinds of generalized Feistel constructions?Type-1,Type-2 and Type-3 Feistel constructions?,contracting and expanding Feistel constructions.These constructions provide many new methods for designers and the security of these constructions raised many researchers'interests.The best key recovery attacking result of Feistel and Feistel-SP constructions,contracting and expanding Feistel constructions are proposed by Guo et al.However,as for three kinds of generalized Feistel constructions,there are only distinguish attack on them,which means there are no key recovery attack on three kinds of generalized Feistel constructions.In this paper,we use meet-in-the-middle technique to attack three kinds of generalized Feistel constructions and provide the first known key-recovery attack on the condition of chosen plaintext attack.The main research contents and innovation points are as follows:Firstly,for Type-1 Feistel construction with n-bit blocks and d sub-blocks,we launch a 3d-1 rounds distinguisher by using a special truncated differential.Then we prepend d rounds at the top of the 3d-1 rounds distinguisher and append d-2rounds at the bottom of the distinguisher.We present an attack on 5d-3 rounds with the data complexity ³2^{n d} chosen plaintexts,the memory complexity 2^{?7?d-1?8?n d} blocks,each block is n bits,and the time complexity 2^{?7?d-1?8?n d} encryptions,which is the best known generic key recovery attack on Type-1 Feistel construction.Secondly,for Type-2 Feistel construction with n-bit blocks and d sub-blocks,we launch a d?10?2 rounds distinguisher by using a special truncated differential.Then we prepend 1 rounds at the top of the d?10?2 rounds distinguisher such that we can present an attack on d?10?3 rounds with the data complexity 2^{n d} chosen plaintexts,the memory complexity2^{?7?d-1?8?n d} blocks,each block is n bits,and the time complexity 2^{?7?d-1?8?n d} encryptions,which is the best known generic key recovery attack on Type-2 Feistel construction.Thirdly,for Type-3 Feistel construction with n-bit blocks and d sub-blocks,we launch a d?10?1 rounds distinguisher by using a special truncated differential.Then we prepend 1 rounds at the top of the d?10?1 rounds distinguisher.We present an attack on d?10?2 rounds with the data complexity2ⁿ² chosen plaintexts,the memory complexity2^{?7?d-1?8?n d} blocks,each block is n bits,and the time complexity 2^{?7?d-1?8?n d} encryptions,which is the best known generic key recovery attack on Type-3 Feistel construction.