Research On Cryptanalysis Based On Meet-in-the-Middle

The initial meet-in-the-middle attack was proposed in 1977 by Diffie and Hellman when they attacked two-DES.Meet-in-the-middle attack could combine the information leakages from both encrypton direction and decryption direction which could reach a better result.In the following years,the idea of meet-in-the-middle has been widely used by many scholars to design several cryptanalysis methods such as:impossible differential attack,meet-in-the-middle attack and biclique attack which acquired good results:impossible differential attack could attack the ciphers with more rounds,the first full-round attacks on AES were proposed by biclique attack and the best results on reduced-round AES in the single key setting were given by meet-in-the-middle attack.Furthermore,with the continuous research on cryptanalysis of block cipher,there is a lot of optimization techniques such as plaintext quick sort algothrim,early abort technique,automation technique and so on.How to design the new attacks with these optimization tehcniques to obtain better results is becoming an important but difficult problem.Therefore it is meaningful to deeply research the cryptanalysis based on the idea of meet-in-the-middle and to use a combination of various optimization techniques to design new attacks on block ciphers that would greatly enrich the design and cryptanalysis of block cipher.In this dissertation,with the usage of these optimization techinques,the security of several typical ciphers under impossible differential attack,biclique attack and meet-in-the-middle attack based on the integral property is analyzed.The works are shown as follows:1.Analysis on the security of Crypton under impossible differential attack.By analyzing the differential property of Crypton,a new 4-round impossible differential distinguisher is constructed.Combined with the divide-and-conquer strategy and early abort technique,a new impossible differential attack on 7-round Crypton with a lower compliexity is proposed.Based on the impossible differential attack on 7-round Crypton,one more round is extended to maintain the attack on 8-round Crypton to recover the 256-bit main key.By using 4 impossible differentials in parallel,combined with the property of the key schedule,the multiple impossible differential attack on 7-round Crypton is given and the master key of 7-round Crypton is recovered.2.Analysis on the security of Midori under impossible differential attack.With the usage of divide-and-conquer strategy,the key guess space of Midori is divided to reduce time complexity.The early abort technique is also introduced to reduce the time complexity in the matching phase.Based on the known 6-round impossible differential distinguisher,the improved impossible differential attack on 10-round Midori-64 is introduced to recover the 128-bit master key.Then by extending one more round in the backward direction,the master key of 11-round Midori-64 is recovered.3.A generalized biclique attack framework is proposed and improved biclique attacks on several ciphers are given automatically.A new method used to construct high dimension biclique is proposed to reduce the complexity in constructing bicliques.Based on this method,a generalized independent biclique attack framework is designed with the usage of automation technique.The bit-oriented bicliques including balanced biclique,unbalanced biclique and star could be constructed by this framework.And the attacks based on these bicliques could be given at the same time.By using the framework proposed in this dissertation,the security of LBlock under biclique attacks is analyzed.The best attack on full-round LBlock is proposed with a time complexity of2^78.14 full-round LBlock encryptions and a data complexity of 2⁶⁰ chosen plaintexts.The first star attack and unbalanced biclique attack on the full-round LBlock are given at the same time.As for CLEFIA-256,based on a 2-round 8-dimension balanced biclique,the attack on full-round CLEFIA-256 is proposed with a time complexity of 2^255.279 full-round CLEFIA-256encryption.With a 4-round 16-dimension balanced biclique,the first biclique attack on full-round Midori-64 is proposed with a data complexity of 2²⁸,a memory complexity of 2^17.2 and a time complexity of 2^126.5.Then the star attack with the optimal data complexity of 2 known ciphertexts and a time complexity of 2^127.06 is given.4.Analysis on the security of ARIA under meet-in-the-middle attack.Based on the diffusion property of ARIA block cipher,we use the ordered ciphertext differential sequence of 4.5-round ARIA-256 to construct a new meet-in-the-middle distinguisher with the usage of differential enumerate technique.With this distinguisher,time/memory tradeoff technique is considered and we propose a key recovery algorithm and improve the security analysis of 8-round ARIA-256under the meet-in-the-middle attack with the table-lookup.5.Analysis on the security of Crypton and mCrypton under meet-in-the-middle attack.By analyzing the differential properties of cell permutation,several differential characteristics are introduced to define the generalized?-sets.With the usage of the generalized?-set and the differential enumeration technique,a 6-round meet-in-the-middle distinguisher is proposed to give the first meet-in-the-middle attack on 9-round Crypton-192 and some improvements are done on the attack on 10-round Crypton-256.Combined with the properties of nibble permutation and substitution,an improved meet-in-the-middle attack on 8-round mCrypton is given and the attack on 9-round mCrypton-128 is proposed.