Research On Application Of Mixed Integer Linear Programming And Related Methods In Cryptanalysis Of Symmetric Ciphers

Information resource management is an important research field in management science and engineering.The key theories and technologies in information security and network security are a hot research topic in recent years.Cryptography is a core technology and the basis on which the security management of information resources in the network environment is realized,which in-cludes symmetric and asymmetric ciphers.One of the development trends of symmetric crypta-nalysis is the automation of cryptanalysis.In 2011,Mouha introduced the Mixed Integer Linear Programming（MILP）method from the field of operations research to the field of cryptanalysis to determine the minimum number of active S-boxes and impossible differential characteritics for block ciphers at the byte-level.Subsequently,cryptanalysts have achieved many breakthroughs with the help of MILP.However,in the face of enormous demand for new cryptographic algo-rithms,the security analysis of these emerging algorithms is not sophisticated enough and some open problems and theoretical issues have not yet been answered or resolved as it hasn’t been long since applying MILP to cryptanalysis.This thesis integrates the MILP method into conditional dif-ference analysis,carries out the analysis of the Non-linear Feedback Shift Registers（NLFSR）based block cipher KATAN32 algorithm in the single-key scenario,and conducts the collision attack on GIMLI-HASH.MILP does best in integral attacks when combined with division property,which can be used to characterize the integral properties at the bit-level.However,it also means that the process of the MILP model will exceed the computing power if the size of block cipher is large.As a supple-ment to integral attacks based on MILP,by making full use of the algebraic structure characteristics of the block cipher and considering the（non）linear combination of ciphertext bytes and using the zero-sum nature of the S-box and the fact that the entries in the Difference Distribution Table（DDT）are all even,we have obtained integral distinguishers which can cover more rounds with lower complexity.We also applied the method on WARP,Cl EFIA and LBLOCK,respectively,and obtained the best integral attack result for WARP so far.Taking advantage of the properties of the algebraic structure of block ciphers with Substitution-Permutation Network with Partial non-linear layers（PSPN）structure,and applying the impossible differential analysis on them,we explored the security analysis method on this new kind cryptographic algorithm.The main research achieve-ments are concluded as follows:1.Improved conditional differential cryptanalysis and collision attacks using MILP.To offset two limitations of conditional differential cryptanalysis that lead to a limited number of analyzable rounds,we proposed a MILP method for conditional differential cryptanalysis and probability calculation formula.We applied this model and method to the lightweight block cipher KATAN32 based on NLFSR and then obtained an 81-round conditional differential distinguisher,which is 3 rounds more than the previous conditional differential cryptanalysis results in the single-key scenario.Based on the 81-round conditional differential distinguisher,we used the algebraic expressions and standard differential analysis method to extend it,leading to a key recovery attack on 99-round KATAN32.Combining MILP and conditional difference analysis,we applied them to the semi-free-start collision attack of GIMLI-HASH,and found six rounds,seven rounds,and eight rounds of conditional differential characteristic.The results show that MILP applied to con-ditional differential cryptanalysis improves the efficiency of cryptanalysis,and the number of rounds that can be attacked is closer to the actual number of rounds of the cipher than the known results,and more accurate security bound are obtained.2.A proposed integral cryptanalysis method from algebraic structure perspective to obtain the optimal attack on WARP in the singe-key scenario.We extended the integral cryptanalysis from the algebraic structure perspective to Feistel-SP block ciphers.Also,we found a property of the algebraic structure that is favorable for integral cryptanalysis when the output word is represented by a multivariate polynomial of input words,and we proved the integral property.By using the property,we improved the integral analysis on SPN and Feistel-SP structure block ciphers from the algebraic structure perspective.We applied this method to the lightweight block cipher WARP and constructed a 22-round integral distin-guisher with a data complexity of 2¹¹⁶ which is two rounds more and with less complexity than the previous integral distinguisher.Based on this 22-round integral distinguisher,combined with par-tial sum technologies,we gave an integral attack on 26-round WARP with a complexity of 2^119.5,which is 5 rounds more than the attack given by designers,and is by far the best integral attack in single-key scenario.3.Integral attacks on the generalized Feistel structured block ciphers CLEFIA and LBLOCK.From the perspective of algebraic structure,we carried out integral analysis on two general-ized Feistel-SP structured block ciphers,CLEFIA with a 128-bit block size and LBLOCK with a64-bit block size.We constructed eight 9-round integral distinguishers of CLEFIA,which is equal to the longest integral distinguisher of CLEFIA so far.For LBLOCK,15-round integral distin-guishers are obtained,which is no weaker than the results given by designers.The results show that the advantage of cryptanalysis from the algebraic structure perspective is reflected in the anal-ysis of block ciphers with larger block size.4.Proposed impossible differential analysis on PSPN ciphers.PSPN ciphers use partial S-boxes in the non-linear layer.With the help of multivariate poly-nomials of the internal state word in both encryption and decryption directions,we constructed the conflict on a certain internal state word or linear combinations of some internal state words to obtain impossible differential distinguishers of PSPN ciphers.Using AES as an example,we in-vestigated the relationship between the ratio of non-linear modules in the round function and the number of distinguisher rounds.We have effectively explored methods for security evaluation of PSPN block ciphers.