Implementation And Study Of The Automatic Search Algorithm Of The Meet In The Middle Attack

Since the 1990s, the rapid development of technology communication have been infiltrating into all areas of people’s life, also changing people’s production and life at the same time. Especially, the developing of communication technology in the Mobile Terminal Device is more quickly, such as the area of mobile phones, satellite navigation and Internet of things etc. As the development of Information science and technology have brought convenience to people’s life, a series of security issues have raised, such as information disclosure, the leak of social account, etc. So the lightweight ciphers which run in the limited resources become more and more important.In this thesis, we focus on the meet in the middle attack (MITM) of a lightweight block cipher:TWINE, which was first presented by Tomoyasu Suzaki at ECRYPT in 2011. It’s a 64-bit block cipher with two supported key lengths,80 and 128 bits, the encryption and decryption function are all 36 rounds, and it’s a generalized Feistel structure which has 16 branches. A round function of TWINE consists of a nonlinear layer using 4-bit S-boxes, XOR round keys and a diffusion layer, which permutes the 16 blocks. In particular, instead of traditional shift operation, the linear layer was replaced by the 4 bits direct pull.Diffie and Hellman proposed the meet in the middle attack (MITM) when they analyzed the DES algorithm in 1979. In recent years, a lot of researchers improved this attack on AES algorithm through transforming the MITM. In 2008, Demirci et al made improvements to the meet in the middle attack by using theδset, and analyzed 7 rounds AES-192. In 2010, Dunkelman et al. took advantage of the differential enumeration technology to improve the analysis of AES-192. In 2013, Parick et al. analyzed the 8 rounds of AES-192 by using the properties of the S-box. In 2014, Li et al improved the 5 rounds distinguisher by using its key schedule.In aspect of the meet in the middle attack used to the Feistel structure, Biryukov et al. proposed a new kind of meet in the middle attack based on multiset, and achieved the best cryptanalysis results on TWINE-128 till now. Inspired by their work, this thesis introduces an automatic search algorithm of MITM attack. The algorithm is divided into three parts.1) The distinguishers are detected automatically.2) The round subkeys involved in the online phase are listed.3) The guessed round subkeys are transferred to equivalent master keys. The results achieved from the algorithm can be checked manually. With the same δ-set, we find several equivalent distinguishers besides the one proposed by Biryukov et al, which also can be applied in the MITM attack on TWINE-128, and the attack process is the same, so as the complexity.