Improvement And Application Of Nonlinear Invariant Attack

In Asiacrypt 2016,Todo et al.proposed nonlinear invariant attack,a new type of distinguisher that covers any number of rounds for a substitution-permutation networks(SPN)cipher under the weak keys.Nonlinear invariant attack was applied to lightweight ciphers Scream,i Scream and Midori-64,where the authors showed that nonlinear invari-ant functions can be constructed for the three ciphers under 2⁹⁶,2⁹⁶and 2⁶⁴weak keys,respectively.In this paper,based on Todo et al.the nonlinear invariant attack is fur-ther improved,and the improved attack is applied to the specific block cipher.The main results are as follows:Firstly,a new equivalence relation of S-box is defined,which is called Q-equivalence,and prove that Q-equivalence preserves the algebraic degree of the nonlinear invariants of S-boxes.Leander et al.classified all optimal 4-bit S-boxes into 16 affine equivalence classes according to the affine invariance of differential uniformity,linearity and alge-braic degree.Based on Leander's work,we classify partial 4-bit optimal S-boxes into 4different categories according to Q-equivalence,and give the number of Q-equivalence classes and representative for each category.Secondly,an improved nonlinear invariant attack based on S-box substitution is pro-posed.Let Q denotes an invertible matrix and c denote a constant.As for an AES-like block cipher E_kfor orthogonal matrix in linear layer,we can prove that the new cipher is equivalent to Q^-1M(?)E_k?(?)QM after replacing the S-box S(x)of E_kwith S^?(x)=Q^-1SQ(x)?c,where E_k?denote that E_kafter changing the round key and QM is a certain linear transformation.We present the application for improved nonlinear invariant attack:The main idea is to transform an S-box with no quadratic invariants by another S-box that possesses quadratic invariants,while maintaining the internal structure of the original cipher.After that,we can use the above properties to mount a distinguish-ing attack against E_k?By introducing the concept of round weak key multiple set,we can also get round weak key multiple set of E_kby going through all Q and c,so as to expand the amount of weak key to distinguishing attack.Finally,the improved nonlinear invariant attack is applied to the round function of FIDES-80 and Midori64-m,which is an variant of Midori64.As a result,we obtain non-linear invariants with 2³²weak keys which can be used to apply a distinguishing attack on any rounds of the round function of FIDES-80.We introduce the concept of the mas-ter weak key multiple set and calculate the master weak key multiple sets of different Midori64-m,where the maximum amount of the master weak key is 7×2⁶⁴?...