Meet in the Middle Attack on Type-1 Feistel Construction

摘要

We provide a key recovery attack on type-1 Feistel construction based on the meet-in-the-middle technique. This construction is described by Zheng, Matsumoto, and Imai in CRYPTO 1989. Type-1 Feistel structure is a well-known construction used to construct ciphers and hash functions, such as CAST-256 and Lesamnta. 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. We present an attack on 5d - 3 rounds with the data complexity 2~((3/d)n) chosen plain- texts, the memory complexity 2 (d-1)/d n blocks, each block is n bits, and the time complexity 2 (d-1)/d n encryptions, which is the best known generic key recovery attack on Type-1 Feistel construction. The attack is valid if the key length k ≥n.