Research On The Security Of SPN Structures Against The Differential-Class Cryptanalysis

As an important block cipher structure,the SPN structure has been adopted by many famous block ciphers and the most notable example is AES.As extensions of the classical differential attack,the truncated differential attack and the impossible differential attack have been another two effective attacks against many block ciphers,which even gain(almost)full-round attack.Thus,evaluation on the security of SPN block ciphers against these two attacks,is a problem worth investigating.This paper focuses on the truncated differential distinguisher and the impossible differential distinguisher,and makes the following four progresses:1.Starting from the formula of calculating the Expected Differential Probability of a truncated differential trail,we give a new method on precisely estimating this probability.This method overcomes the shortcomings of existing methods that they either can not consider the detail of the underlying S-box or only apply to special trails of some specific block ciphers,and takes in account the differential distribution of the S-box and the correlation caused by the linear layer,and applies to any truncated differential trails of any SPN block ciphers.As applications,we use this method to evaluate the probability of 8 truncated differential trails of 4 SPN block ciphers(KLEIN,Midori64,CRYPTON and ARIA),and give precise estimations,whose precision is not less than the existing methods.What's more,this method can give a precise estimation on the number of matching differential trails within a truncated differential trail,which proposes a new idea on investigating the differential trail clustering in the future.2.Focusing on the upper bound on the length of impossible differentials,we propose a new method on giving tight upper bounds on the length of impossible differentials for any SPN structure regardless of the detail of the S-box,which has polynomial complexity and overcomes the shortcomings of existing methods that either their complexity is too high to be practically implemented or they are only suitable for special linear layers.As applications,this method gives tight upper bounds on the length of impossible differentials for CRYPTON,m Crypton,Minalpher-P,Midori and Skinny64 for the first time,and for those block ciphers that previous methods have given tight bounds,our method gives the same tight bounds.What's more,we have implemented and encapsulated this method into a C function that can be conveniently used by designers to evaluate the security of an SPN block ciphers against the impossible differential attack,and to choose linear layers that improve the security of a cipher against the impossible differential attack independent of the choice of the S-box.3.By investigating the special algebraic properties of the AES S-box and its linear layer defined over the finite field GF(2~8)and assuming its round keys to be independent and uniformly random,we theoretically prove that there do not exist impossible differentials longer than 4rounds for AES,which goes a step further on proving the security of AES against the impossible differential attack.In our proof,we introduce an important concept“(w,d)-Dependent Tree”,which may be extended to be used to proved upper bounds on the length of impossible differentials for other SPN block ciphers when the detail of the S-box is considered.4.For the first round candidate block cipher TASS1 of the National Cryptographic Algorithm Design Competition,we reveal that its feature“only small number of bits enter the nonlinear transformation”makes the cipher have long differential trails with probability 1(Note that this is also found by Li et al.independently at the same time),which are further used to construct long even full-round impossible differentials and full-round differential counting distinguisher for TASS1.