Automatic Search For Trails Of Block Cipher And Linear Cryptanalysis On SM4,SPECK

With the development of science and technology,and in particular,the pop-ularity of smartphones,the network has became a necessity in all walks of life and changed the living style to some extent.Under the circumstance,increased demands for secure network environment prompt the research community to de-note themselves to design and identify good cryptographic protocols for various application scenes and security requirements,including security in software and hardware,information communication,information network system,interactive data accessing and so on.It is a very significant goal to guarantee the data con-fidentiality in which encryption is a very important tool by changing messages into garbage for non-authenticated receivers.The block cipher is one way to achieve data encryption and it is easy to syn-chronization which makes it widespread suitable for many application scenarios.There are lots of ciphers with far-reaching influence,such as SPECK,a family of lightweight block ciphers which was publicly released by NSA(National Secu-rity Agency)to optimize the performance in software implementation.Due to the extensive application prospects of SPECK,it is necessary to analyzing the security against sorts of attacking methods.There are lots of cryptanalysis re-sults on SPECK.SM4(formerly SMS4)is issued by Chinese government in 2006 to provide confidentiality in the Chinese National Standard for Wireless LAN WAPI(Wired Authentication and Privacy Infrastructure).In addition,SM4 is also regarded as Chinese commercial ciphers standard.The research community has focused on SM4 from its release.Thus,many cryptanalysis results on SM4 exists.There are lots of cryptanalysis methods for block ciphers,of which the earliest one is the famous differential analysis.This cryptanalysis method was soon be known and widely used in cryptography and becomes one of the main analysis methods and the immune to various cryptanalysis methods must be considered when a new algorithm is designed.Another famous cryptanalysis method is lin-ear cryptanalysis.Linear cryptanalysis and differential cryptanalysis are vital and basic to analyze ciphers.A lot of other cryptanalysis methods are gradu-ally derived from the two cryptanalysis methods gradually such as:truncated differential cryptanalysis,rebound attack,multi-linear cryptanalysis,boomerang attack,multidimensional linear cryptanalysis,linear hull cryptanalysis and so on. In addition there are some other cryptanalysis methods such as algebraic attack,integral cryptanalysis,zero-correlation linear cryptanalysis,impossible differen-tial cryptanalysis and so on.The security of a specific block cipher is analyzed against various cryptanalysis methods.In the first part of this thesis,we introduced several models based on STP constraint solver to search for(impossible)differential and linear trails of S-Box based ciphers.Build STP-based model to search for(impossible)differential and linear trails of S-Box based ciphers:In recent years,automatic tools have played an important role in designing new cryptographic primitives and eval-uating the security of ciphers.There are three categories of automatic search tools used for cryptography,such as tools based on MILP,SAT/SMT,and CP.This thesis focuses on the automatic search tools based on SAT/SMT,and uses STP,as a SAT/SMT solver,to search for trails.STP has been used to search for differential/linear trails of ARX cipher,but is not used to search for trails of S-Box based ciphers.MILP-based tools have been developed to automatically search for real differential and linear trails and constructed to search for im-possible differential and zero-correlation linear trails for S-Box based and ARX ciphers.These tools could express all properties of the DDT/LAT for the 4-bitS-Box.However,it is difficult to effectively represent the DDT/LAT of the 8-bit S-Box.The CP technique has been utilized to design a new general tool to search for(impossible/related-key)differential,(zero-correlation)linear trails and integral distinguishers.From open literatures,it was shown that the advantage of CP-based tools is that they could deal with some ciphers with 8-bit S-Boxes.However,current CP-based automatic tools have not considered how to describe S-Boxes whose DDTs/LATs contain entities not equal to the power of 2.We aim to extend the application of STP in automatic search for differential and linear cryptanalysis of S-Box based cipher,and fill in the gaps of automatic tools for search for differential and linear trails with optimal probability and correlations of 8-bit S-Box based ciphers,whose DDTs or LATs have entities not all the power of 2.First,the STP-based model is built for differential and linear trails with the minimal number of active S-boxes.In this case,we only concern about the valid differential/linear propagations and do not calculate the probability of differential characteristic/linear approximation.Based on this,we present equations to de-scribe the valid differential/linear propagations through S-Boxes.The STP-based model is built using these equations for differential/linear trails with minimum active S-boxes.Particularly,this model works well for cipher with 8-bit S-Boxes.Second,the model for differential and linear trails with the optimal propagation and correlation is constructed based on STP.Trails with optimal probability or correlation may not have minimum active S-Boxes,and with the same number of active S-Boxes may not have the same probability or correlation.Hence,we need to describe the probability and correlation through S-Boxes.In order not to lose better trails,approximation functions are designed to compute the probability and correlation.This is the first STP-based model proposed to search for differ-ential and linear trails with optimal probability and correlation,even for S-Box based ciphers whose DDTs/LATs contain entities not equal to the power of two.The method to build the approximation functions suits for any automatic tools besides STP,especially for ones which perform poor for decimal operations or multiplication.Next,the STP-based model is shown to search for the impossible differentials with key schedule.The general models for impossible differentials are based on the model search for trails with minimum active S-Boxes.We can implements by adding equations to specify the input and output differences and deleting the constraints for the number of active S-Boxes.However,this method assumes that round keys are independent and uniformly random and ignores the existence of the key schedule.We consider not only the differential property of S-Boxes but also the key schedule in the encryption algorithm.Therefore,we trace propagations of values from plaintext to ciphertext instead of propagations of differences.As far as we know,this is the first time to give a search method for impossible differentials under the key schedule.Finally,our proposed models are utilized to search for linear trails for ARIA and ICEBERG,differential trails for SM4.We presented the optimal 4-,5-and 6-round ARIA linear trails,the op-timal 6-round ICEBERG linear trail and the 19-round SM4 differential tail with probability to be 2-123.As a result,improvements of results are in terms of the previous best trails.Specifically speaking,the trail of aria enlarges the number of round,and ones of ICEBERG and SM4 enhance its correlation and probability,respectively.Using the model for impossible differentials by considering the key schedule,we search for truncated impossible differentials of AES-128.And we found that there is no 5-round AES-128 truncated impossible differential,where input and output differences have only one active byte respectively.In the latter part of this thesis,we improved the linear analysis results of two algorithms,one is SM4,an S-boxes based ciphers,and the other is a lightweight add-rotate-xor(ARX)cipher,SPECK.Improve the linear cryptanalysis on SM4 using partial linear approx-imation table to search for short rounds iteration linear approximation-s:Among all the above attacks on SM4,the methods that could attack longest rounds are differential and linear attack.All the best previous attacks are based on 19-round distinguishers.We focus on whether we could find a longer distin-guisher for improving the best previous results first.However,the best previous identified linear approximation covers 19 rounds.If we search for linear approx-'imation for large round of SM4 directly,the search will implement at very high computation cost and may throw up no solution better than the best previous ones.Therefore,we want to design an algorithm to search for short rounds linear approximations using partial linear approximation table of S-box borrowing from the method which was used to search for linear approximations of ARX ciphers by Biryukov and Velichkov.Firstly,the existences of one round or two rounds nontrivial iterative linear approximation were proved.Secondly,some properties of three rounds of iterative linear approximations of SM4 are illustrated.Based on these properties,search for three rounds of iterative linear approximations for SM4 was implemented.If we use the linear approximation table of S-box to search for the iterative linear approximations,the algorithm is inefficient.So we use the partial linear approximation table of S-box to search for three rounds of iterative linear approximations of SM4.20-round linear approximation of SM4 is constructed by the three rounds iterative linear approximation.So far,this linear approximation is the best linear approximation.Furthermore,we show the key recovery attack on 24-round SM4 based on the 20-round linear approximation.This attack is the best one in terms of the number of rounds.At the same time,a 19-round linear approximation for SM4 is obtained by the 3-round iterative linear approximation.The correlation of this linear approximation is larger than the one of the known 19-round linear approximation.We improve the best pre-vious 23-round linear attack using this 19-round linear approximation.The time complexity is reduced from 2116 bytes to 285 bytes,and the data complexity is reduced from 2126 5 23-round encryption to 2120 3 23-round encryption.Improve the linear cryptanalysis on SPECK utilizing partial linear mask tables and Segment Searching strategy:Among these cryptanalysis results,the best one was differential cryptanalysis result proposed by Dinur and Abed.At that time there only was a linear cryptanalysis result proposed by Yao et al..This result was gotten by applying Wallen's enumeration algorithm and Matsui's branch-and-bound method.However,an obvious gap existed between the differential results and the linear one of SPECK especially for SPECK-96 and SPECK-128.For search for the linear approximation of SPECK,the first step is to design an appropriate search algorithm.Put all valid input/output masks of modular addition modulo 2n and their corresponding correlations into a table and denoted this table as the linear mask table of modular addition modulo 2n.However,if this linear mask table is used to search the linear approximation of SPECK,the search efficiency would be very low.So the partial linear masktable is used to speed up the search progress rather than the linear mask table.Using the red-black tree to store the partial linear mask table,which can deduce the search time,borrowing from the method which was used to search for linear approximations of ARX ciphers by Biryukov and Velichkov.The search time is further reduced by combining the Segment Searching with branch-and-bound method in the search algorithm.Finally,the security features of SPECK against linear cryptanalysis are given.The thesis gives and introduces 9-round linear approximation on SPECK-32,10-round linear approximation on SPECK-48,12-round linear approximation on SPECK-64,15-round linear approximation on SPECK-96 and 16-rounds linear approximations on SPECK-128.The length of the linear approximation of SPECK-48,SPECK-96 and SPECK-128 were 1,9 and 10 rounds longer than the best previous ones at the time,respectively.The correlation of the linear approximation for SPECK-64 was twice as much as the previous linear cryptanalytic then.As a result,we improved the previous linear cryptanalysis and got linear cryptanalysis results with the same rounds of differential cryptanalysis results for SPECK-96 and SPECK-128 then.The rounds that we can attack for SPECK-96/144,SPECK-128/192 and SPECK-128/256 were the same as the best previous ones at that time.