Research Of The Techniques Of Impossible Differential Cryptanalysis Of Lightweight Block Cipher

With the popularity of Cloud Computing and Internet of Things,more and more attention has been paid to the communication security between lightweight devices.How to design safer and more efficient lightweight block ciphers has become a research hotspot in the field of data encryption.The research of lightweight block cipher mainly focuses on two aspects of cipher design and cryptanalysis.The cryptanalytic method of lightweight block cipher is the same as that of classical block ciphers,which mainly includes exhaustive-attack,differential cryptanalysis and its improved method,linear cryptanalysis and integral cryptanalysis.Impossible differential cryptanalysis is one of improved method of differential cryptanalytic method.It has a good analysis result for the block cipher similar to the AES.At present,the research of impossible differential cryptanalysis is mainly about two aspects:one is to design efficiently automated searching path and construction algorithm,the second is to design efficient key recovery algorithm.This paper mainly focus on the techniques of impossible differential path searching and the skills of reducing key recovering complexity,using the attacked object of lightweight block cipher Midori for instance.Firstly,we studied the technique of searching impossible differential paths.According to the similarity of the structure of Midori and AES,impossible differential path search algorithm-u-method is simplified,mainly including simplifying encryption/decryption characteristic matrix,addition table,and the multiplication table.The set-1-method is found to get the encryption/decryption characteristic matrix.Some 5-round impossible differential paths are obtained by using the simplified u-method.This technique is also applicable to search the impossible differential paths of other SPN structured block ciphers.Secondly,we studied the extension technique of impossible differential path.Based on the analysis of the MixColumn operation characteristics of Midori,4 kinds of MixColumn differential propagation modes are summarized,and the correspondence of input and output of each mode is found.Based on the differential propagation mode of MixColumn,this paper proposes a method,which use the backtracking-method to find the preposition path and the postposition path,and splice it with the 5-round impossible differential path to obtain 7-round impossible differential path,and the automatic construction algorithm is designed.Then,we proposed the step-key-guessing technique.Using this method,the 10-round impossible differential cryptanalysis of the Midori-64 is improved.The complexity of the key-recovering process is reduced by the filtering plaintext process,and the time complexity is reduced by this method.In the 10 rounds impossible differential analysis,the time complexity is reduced from 2^80.98to 2^74.588,data complexity is reduced from 2^62.4to2^62.34,the temporary storage is reduced from 2^70.22to 2^70.16.By using 7-round impossible differential path,combined with the step-key-guessing method,the first 11-round impossible differential cryptanalysis of Midori-64 is proposed.The time complexity is2^121.369,data complexity is 2^61.95,the temporary storage is 2^73.68.Finally,structure number scaling technique is proposed.The method does not require to get the correct key after the key recovering process.Instead,the structure number is selected by theoretical calculation,so that the complexity of key recovering process and the time complexity of the exhaustive searching process reach the theoretical minimum.By using this technique,the time complexity of the impossible differential analysis of the 10-round Midori-64 is further reduced to 2^74.166,and the data complexity is reduced to 2^61.816,and the temporary storage space size is reduced to 2^69.636.For the 11-round impossible differential cryptanalysis of Midori-64,the time complexity is reduced to2^118.67,and the data complexity is reduced to 2^59.08,the temporary storage is reduced to 2^70.81.This technique is also applicable to the impossible differential analysis of other algorithms.