The Construction Of Attack Model For Block Ciphers And Automatic Cryptanalysis

With the transformation from Internet of Things(IoT)to Internet of Everything(IoE),the internet provides a convenient experience for our life.At the same time,network security is facing updated challenges under the new circumstance.As the cornerstone to ensure network security,the cipher plays a critical role in the security authentication,encipherment protection and information trans-fer.Owing to the advantages of high efficiency,simple structure and feasibility for bulk encryption,the symmetric-key encryption scheme has a broader and more flexible application comparing to the public-key encryption scheme.Based on this phenomenon,the research on the design and cryptanalysis of the block cipher is especially important under the new surrounding.This work focuses on the construction of the attack model for block ciphers and automatic crypt-analysis.On the aspect of constructing distinguishing models,we propose x2-multiple/multidimensional zero-correlation linear attack model and utilise it to analyse the security of many primitives.Regarding the automatic cryptanalysis,we investigate the automatic search of distinguishers on the one hand and manage to settle some theoretical problems in cryptography with the help of automatic methods on the other hand.In terms of the automatic search of distinguish-ers,we provide Mixed Integer Linear Programming(MILP)models to search for the bit-based division property of primitives with complicated linear layers as well as ARX ciphers.With these new models,we evaluate the security of many encryption algorithms against integral cryptanalysis.We also generate an auto-matic tool based on Boolean Satisfiability Problem(SAT)method for the search of bit-based division property and an automatic approach based on Satisfiability Modulo Theories(SMT)to search for word-based division property,which en-riches the frame of the automatic search of division property.With respect to the automatic analyses of theoretical problems,we discuss the differential effect in differential cryptanalysis.We give more accurate differential cryptanalysis for two ciphers.Finally,we evaluate the security of all versions of SIMON family against zero-correlation attack.The details are listed in the following.Proposing an automatic tool based on SAT problem to search and analyse differentials for ciphers with S-boxes:Considering the lack of an automatic tool based on SAT method for the search of differentials,we put for-ward an automatic method based on SAT to realise the automatic search of differentials for ciphers with S-boxes.Firstly,we construct SAT models for the diffusion layer and S-box.Then,the SAT model for the objective function is con-sidered.After that,we explain how to search for multiple characteristics within a differential.Owing to the invention of this method,we can search for differentials with numerous characteristics for LED64 and Midori64.For LED64 we construct an automatic approach to detect the right pairs following a given differential.To begin with,we derive the constraints on the right pairs following a given characteristic.Then,these constraints are converted into SAT clauses,and the solutions of these clauses are the right pairs matching that characteristic.Finally,the right pairs of a differential can be obtained by gathering the right pairs of all trails within the differential.With this technique,we improve the previous results provided by Mendel et al..Benefiting from the increased differential probability,the previous attacks exploiting the differential property of the STEP function can be improved.As to Midori64,we create an automatic method to evaluate the weak-key space of a differential.First of all,we deduce the necessary condition for a key being a,weak-key and an upper-bound of the weak-key ratio for a given differential.Then,this condition is transformed into a SAT problem,and we invoke SAT solver to estimate the weak-key ratio.We present two 4-round differentials with weak-key ratios much lower than the expected 50%.More than 78%of the keys will make these two differentials being impossible differentials.If such a differential is used to launch a key-recovery attack,the attack is very likely to fail since the attacker cannot find right pairs under the right key.On the contrary,we consider those extremely weak weak-keys determined by a given differential.For those keys we may detect the enhancement on the differential probability.The real success probability of differential cryptanalysis under these keys is significantly larger than the theoretical value.This problem is relevant to considering the compatible trails hold simultaneously under a particular set of keys.We find that this problem can be converted into a special kind of Max-PoSSo problem.We put forward a technique based on SAT to solve the dedicate Max-PoSSo problem derived from the question we care.As a result,for a 4-round differential of Midori64 with EDP= 2-23.79.we observe that for 2-12 of the keys,the differential property is increased to 2-16 These examples remind us that for some lightweight,block ciphers with a simple key schedule,or at least for Midori64.we need to pay attention to the effectiveness of the differential distinguisher.Constructing X2-multiple and multidimensional zero-correlation lin-ear cryptanalysis models and providing the best attack for TEA algo-rithm under single-key attack scenario with the new model:As more sophisticated methods,classical multiple and multidimensional zero-correlation linear models overcome the drawback of basic zero-correlation in terms of the data complexity,which enables zero-correlation cryptanalysis method to be widely ap-plied to the attacks for various symmetric-key primitives.In the meantime,the best attack methods for many ciphers are realised with the zero-correlation at-tack.Although multiple and multidimensional zero-correlation models have been widely used to analyse block ciphers,there still exists an unsolved issue on the number of involved approximations.To eliminate this constraint,we construct?2-multiple/multidimensional zero-correlation linear cryptanalysis model.Since we skip the normal approximation of the ?2-distribution,the new model achieves a more accurate evaluation of the complexity,and its validity does not rely on the assumption on the number of trails.The appearance of the ?2-model is of great,importance.On the one hand,the new models enlarge the range of appli-cation of zero-correlation models and is a generally applicable method.On the other hand,it enables us to launch an attack without using the full codebook even though there is only one trail,which overcomes the shortcoming of the basic zero-correlation model.The ?2-multidimensional attack model is applied to evaluate the security of CLEFIA-192.Under the same setting with the previous work,we provide a more precise estimation for the attack complexity.We also utilise less zero-correlation approxmations to improve the previous result Besides the new ?2-multiple zero-correlation model is employed to analyse the security of TEA and XTEA against multiple zero-correlation cryptanalysis.The improved multiple zero-correlation attack on 23-round TEA is the best attack in the single-key setting with data complexity less than the full codebook.Enriching the automatic tool based on MILP method for the search of bit-based division property:As a generalisation of traditional integral property,division property can depict the subtle property between the traditional ALL and BALANCE properties,which makes it a powerful tool to discover in-tegral distinguishers.Since bit-based division property achieves a more accurate control for the algebraic property of the objective primitive,the distinguisher de-duced with the bit-based division property is better than the one obtained with the general division property,sometimes.However,the direct application of this method requires a huge complexity,which restricts its further application.At ASIACRYPT 2016 Xiang et al.put forward a method based on MILP to re-alise the automatic search of bit-based division property.This tool relieves the constraint of bit-based division property on the block size of the objective prim-itive.and the authors improved the integral distinguishers of many algorithms,which all use bit permutations as their diffusion layers.For those primitives with non-bit-permutation linear layers,the validity of this method is not known at that time.Motivated by this observation,we first extend the original Copy and XOR models so that they can be adapted to the Copy operation with more output branches and the XOR operation with more input branches,respectively.Based on the observation of the primitive representation for the linear layer,we propose a general method to construct MILP models for complex linear layers with the generalised models.With this method,we settle the feasibility of MILP-aided bit-based division property for the ciphers with non-bit-permutation linear layers.The range of application of MILP-aided bit-based division property is enlarged so that bit-based division prop-erty plays a more critical role in the distinguisher searching phase of integral cryptanalysis.Considering the significant status of the ARX cipher in the field of symmetric-key encryption scheme.we construct MILP model for the modular addition operation,which guarantees the feasibility of MILP-aided bit-based division property for the ARX ciphers.With the generalised MILP models,we manage to search for integral distinguishers for a series of primitives.The integral distinguishers for various objectives are improved,such as Midori64.LED64,Joltik-BC,Serpent.Noekeon,HIGHT and LEA.Constructing the automatic tool based on SAT method for the search of bit-based division property:Since we observe that the SAT/SMT based methods outperform the MILP based methods in search of differential/linear characteristics for ARX ciphers,we aim to explore whether automatic tools for bit-based division property based on the SAT/SMT method can be constructed and provide better performance for ARX primitives.For ARX ciphers,we pro-pose an automatic tool to search integral distinguishers using bit-based division property.First,we model the division property propagations of the three basic operations,i.e.,Copy,AND,and XOR,and present formulas in Conjunction Normal Form(CNF)for them.Then,the concrete equations for the modular addition operation to depict bit-based division property propagation can be achieved.The initial division property and the stopping rule are transformed into logical equa-tions,too.Finally,the propagation of division property for the ARX cipher is described by a system of logical equations in CNF,and we can invoke SAT solver to solve it.To locate the optimal integral distinguisher rapidly,we pro-pose an efficient search algorithm.With this algorithm,we narrow the search scope of initial division properties and identify the initial divi-sion property resulting in the op.timal distinguisher,efficiently.Based on this method,we obtain a 17-round integral distinguisher for SHACAL-2,which gains four more rounds than the previous work.Also,we search for the bit-based division property for LEA,HIGHT,and all versions of SPECK,the integral distinguishers obtained with MILP method are improved.Developing the automatic tool based on SMT method for the search of word-based division property:For one thing,there is a lack of automatic method to search for word-based division property.For another thing,it is infea-sible to trace the division property propagation at the bit level for some ciphers with large state and complpicated operations.As a result,we consider building an automatic tool to search integral distinguishers on account of word-based division property.We study how to model division property propagations for basic oper-ations by logical formulas.With some available solvers,we can efficiently search integral distinguishers by setting the initial division property and stopping rule,rationally.Finally,the problem of searching word-based division property can be transformed into a SMT problem.New word-based division properties are pre-sented for some specific ciphers.For CLEFIA,we discover 10-round distinguish-ers,which attain one more round than the previous one.The data requirements of 4/5-round integral distinguishers for the internal block cipher of Whirlpool are reduced.As to Rijndael-192 and Rijindael-256,6-round distinguishers are proposed,which cover two more rounds than the previous work.With the newly obtained distinguishers for CLEFIA,we can improve the previous integral attacks by one round.