Research On Differential Cryptanalysis Method Based On Mixed Integer Linear Programming

As a mainstream information encryption method,block cipher plays an important role in data security of software systems and other fields.Differential cryptanalysis is a fundamental cryptanalysis method for block cipher.It involves identifying a differential characteristic with high probability which distinguishing cryptographic algorithm from random permutation,thus launching a key recovery attack.Due to the advantages of high accuracy and easy operation,the automatic analysis method of block cipher based on mixed integer linear programming（MILP）has attracted wide attention in the industry.At present,it is a research hotspot that how to use MILP to describe the differential properties more efficiently and find better differential distinguishers.The research topic of this thesis focuses on the differential cryptanalysis of block cipher based on MILP.The main research results are given below:1.A new segmented searching method is proposed based on the forward searching strategy,and applied to the security analysis of FBC.Combined with the idea of divide and conquer,the search model of differential characteristics can be decomposed into several small models and then solved successively,which effectively improves the search efficiency.Applied to FBC-128,a 15-round differential distinguisher with probability 2^-121 is obtained with the search mode of 6+5+4.Then,we extend it by one round,and launch a key recovery attack on 16-round FBC-128,which the data complexity is 2¹²¹ chosen-plaintexts and the time complexity is 2^92.68 encryptions.Compared with the existing results,the number of rounds of both the newly proposed differential distinguisher and key recovery attack are improved by 4 rounds,while the data and time complexity are lower.2.A new multi-segment searching method is proposed based on the opposite searching strategy,and applied to the security analysis of FESH.By setting appropriate initial intermediate difference,multiple MILP models can be established and solved from the forward and backward directions,so as to obtain a better differential distinguisher.Applied to FESH-128,24 5-round differential characteristics are found under the condition of setting7 initial intermediate differences.Compared with the existing results of FESH-128,16differential characteristics with higher probability are obtained by using the multi-segment opposite searching method,with the maximum probability of 2^-105.3.A novel related differential searching method of linear component is proposed based on MILP model of differential cryptanalysis,then applied to the related differential analysis of linear component of Saturnin.By fixing the specified input difference of the linear transformation,the corresponding related differentials can be find by build a MILP model.For Saturnin,all the related differentials of its mixcolumn component were found by applying the new MILP method,including 120 groups.Then the validity of the MILP method was verified by traversal searching method.The result show that it takes only about 27minutes to search for all the related differentials of the mixcolumn component of Saturnin by the MILP-based searching method,while the traditional traversal method takes about 22hours,which means that the new method is nearly 48 times more efficient than the traditional searching method.