The Model And Application Of Automatic Search For Differential-linear Trails Of ARX Ciphers

The structure of ARX is a kind of cryptographic structure which contains only Addition,Rotation and Exclusive-OR operations.It has been widely used in block ciphers,stream ciphers,cryptographic hash functions and Message Authentication Codes(MACs).ARX-based ciphers have the advantages of simple cipher structures and high computational efficiency,which are very suitable for software realization.Differential-linear cryptanalysis was proposed at CRYPTO'94.By com-bining the truncated differential characteristic of high probability and the lin-ear approximation of high bias with certain conditions,the differential-linear characteristic of high bias can be obtained,which can effectively attack some ci-phers.At EUROCRYPT'16,Leurent attacked the ARX-based MAC Chaskey using differential-linear cryptanalysis combined with improved bit-partition technique,which has seriously threatened the security of Chaskey,and reflect-ed the validity of the differential-linear cryptanalysis for ARX-based ciphers.The technology of automatic search has a wide range of applications in cryptography.Especially in recent years,with the further study of ARX,there have been a set of automatic search methods to search differential character-istics and linear trails in ARX-based ciphers.However,there is no tool of automatic search for differential-linear trails.In practice,it is not feasible to combine the automation technology of searching for differential characteristics with the linear trails in order to obtain the differential-linear characteristics of many rounds.Based on these,a model of automatic search for differential-linear trail-s in ARX-based ciphers is presented.Besides,we give a feasible method to realize the model.In order to verify the model,we apply the model to the differential-linear cryptanalysis of ARX-based SipHash and SPECK,and present the differential-linear cryptanalysis results.For the SipHash-2-4 which is the most widely used in the SipHash family,a number of differential-linear trails of 4 rounds in the finalization are found,where the absolute value of bias of the optimal trail is only 2-2.84,and only 27.68 known plaintexts are needed to distinguish.The best result previously published was differential cryptanalysis.The probability is 2-35,and 235 pairs of chosen plaintexts are needed.In the case where the length of the plaintext message is no more than.7 bytes and the exclusive-OR operations of four branches of the MAC are not taken into account,we also give a number of differential-linear trails.In addition,in the case where the length of plaintext message is no more than 7 bytes,we give the results of the differential-linear cryptanalysis of SipHash-2-4,which is the first differential-linear cryptanalysis result of the SipHash.For the SPECK,the differential-linear trails of the shortest instances SPECK32/64 and the longest instances SPECK128/192,SPECK128/256 are given respectively.Moreover,using the trails obtained by our originally-proposed method,we give the specific differential-linear attack process,data complexity,storage complexity and time complexity.As far as we know,the differential-linear cryptanalysis of SPECK family in the paper is the first one.