Several Cryptanalysis Methods On Block Ciphers

In recent years,with the rapid development of the new generation of information technolo-gy,such as cloud computing and Internet of things,all kinds of mobile terminals and sensors have been widely used.Meanwhile,lightweight block ciphers have been developed rapidly,in order to provide effective protection measures.In this thesis,we focus on the security analysis of several lightweight block ciphers in the process of standardization.We have improved biclique cryptanalysis method and several differential characteristics distinguishers in the attacks.These detailed cryptanalysis methods include biclique cryptanalysis technique,MILP?Mixed Integer Linear Programming?method and matrix theory.The lightweight block ciphers involve Kuz-nyechik published by the national standard[GOST R 34.12-2015]of the Russian Federation in2015,and the Keccak sponge function which was standardized as SHA-3 by the National Insti-tute of Standards and Technology of the U.S.in 2012.We also have analyzed some lightweight block ciphers,such as Piccolo,Midori,Skinny,PRESENT,KLEIN,and MIBS.The main con-tributions are as follows:?1?Improved biclique cryptanalysis of the lightweight block cipher Piccolo based on the weakness of the key schedule.Based on the study of Piccolo algorithm structure and key schedule,we re-evaluate the abil-ity of Piccolo against biclique attack.Biclique structure is established on the weakness that the23rd round key can offset 16bits of the postwhitening key on Piccolo-80.We recover the master key for the full round Piccolo-80 by a 6-round biclique,with data complexity of 2⁴⁰ and compu-tational complexity of 2^79.22.The data complexity of the attack is greatly reduced,from 2⁴88 to 2⁴⁰.We construct a 5-round biclique structure and a 7-round biclique structure for the full round biclique cryptanalysis of Piccolo-128 with data complexity of 2⁸ and 2⁴⁰,and computational complexity of 2¹27.3027.30 and 2^127.14,respectively.The research results show Piccolo algorithm with simple key schedule has weak immunity to biclique cryptanalysis.?2?Evaluate the unbalanced biclique cryptanalysis on full round Midori.We proposed a scheme of automatic searching unbalanced biclique structure after the eval-uation process of Midori.A biclique cryptanalysis of full-round Midori is presented by investi-gating the simple key schedule and encryption structure.Then,we construct a 5-round 4×8 un-balanced biclique on Midori-64,with data complexities of 2³⁶ and computational complexities of2^126.25,respectively.Moreover,we use a 4-round 8×16 unbalanced biclique on Midori128 with data complexities of 2⁷²,correspondingly,and with computational complexities of 2^126.91.This is the best single key attack on Midori so far.The security of Midori algorithm is evaluated from a new perspective.The biclique attack is superior to other cryptanalysis methods in the number of rounds.The unbalanced biclique attack has advantages over the balanced biclique attack in data and time complexity.?3?Automatic search for the differential path with the highest probability and the longest number of rounds of block ciphers.Based on study and analysis of cryptographic structure and basic operation,the differential propagation probability of each point in DDT of nonlinear transformation is accurately described by linear inequalities.MILP model based on bit is constructed.Then,we can search automati-cally the differential path with the highest probability and the most rounds under the single key.The differential path with the minimum number of active S-boxes is not necessarily the differen-tial path with maximum probability.The objective function is the maximum probability of diffe-rential propagations.By accurately describing the internal structure of Midori,an automatic differential distin-guisher model based on MILP is constructed.We present a 10-round differential path of Mido-ri-64.Meanwhile,we can extend the 10-round path to 11-round path by utilizing the characteris-tics of its s-box property and linear layer.So,we derive an 11-round MILP model for Midori-64with the probability of no less than 2^-118.It is easy to get two differential paths of 6-round SKINNY-64-64 with the probabilities of 2^-48/2^-60,one differential path of 13-round SKINNY-64-128 with the probabilities of 2^-124,and two differential paths of 18-round SKINNY-64-192 with the probabilities of 2^-188/2^-190.We construct the MILP model based on the bit-level for keccak-f[400].The two active bits are in the same column,so only two bits keep active after one round.Then,we find 3/4/5-round differential characteristics of 2-bits difference.After the systematic study of the s-box properties of PRESENT and the defects of the linear layer,we find a 4-round cycle differential path with a probability of 2^-18.Based on this,two differential paths are constructed with probability of 2^-72and 2^-76 for 16 and 17 rounds.?4?An upper bound of the longest impossible differentials based on matrix theory.By using matrix theory,we can determine whether there exists an r-round impossible differential of the SPN structure or a Feistel structure with SP-type round functions.In this way,the diffusion ability of linear transformation of encryption algorithm is evaluated.After r rounds?the minimum number of rounds?,the martrix of linear transformation is positive.Then the upper bound of the length of the im-possible differential path is obtained.We apply the matrix to express the linear transformation layer and use the matrix method to quickly ascertain the upper bound of the longest impossible differentials for several block ciphers ignoring the nonlinear transformations.The matrix method can be extended to many other block cipher.The research results lay a theoretical foundation for further key recovery attacks and provide a reference for the design of block cipher as choosing the round function and the number of round.We analyse Kuznyechik which is the national standard of the Russian Federation in 2015,and some other block ciphers.As a result,we show that,unless considering the details of the S-boxes,there is not any 3-round,5-round,7-round and 9-round impossible differentials for Kuznyechik,KLEIN,Midori-64and MIBS.