A New Approach of Evaluating the Security Against Differential and Linear Cryptanalysis and Its Applications to Serpent, NOEKEON and ASCON

Abstract In recent years, Mixed-Integer Linear Programming (MILP)-based automatic tools have played a significant role in providing security evaluations of symmetric-key primitives. Differential and linear cryptanalysis are the two most important cryptographic techniques. Although some methods have conducted a great effort in exploiting MILP-aided tools in searching for differential (linear) characteristics, traditional methods still suffer from primitives with strong diffusion layers and large sizes, such as NOEKEON. Typically, searching for differential (linear) characteristics of such primitives is difficult, and the corresponding MILP models are too heavy to be solved efficiently. To this end, we propose a simple yet efficient approach to employ MILP to evaluate the security against differential and linear cryptanalysis of such primitives. The core of our approach is to reduce the complex problem to a set of simpler subproblems and obtain the optimal solution of the complex problem by combining all the subproblems. A subproblem is equivalent to searching for all differential (linear) characteristics with a fixed number of active S-boxes in each round. Furthermore, we design an elaborate algorithm consisting of three MILP-aided methods to solve various subproblems and adopt some techniques to improve efficiency further. Applying our new algorithm to three SPN primitives Serpent, NOEKEON and ASCON, we obtain the tightest security bounds against differential and linear cryptanalysis for all three primitives so far and find improved differential and linear characteristics for Serpent and NOEKEON. For Serpent, we improve the upper bound of the maximum probability of 7-round differential characteristics from $2^{-71}$ to $2^{-76}$ and find for the first time 7-round differential characteristics. For NOEKEON, our results show that there is no 9-round (10-round) differential (linear) characteristic with a probability (correlation) higher than $2^{-128}$ ($2^{-64}$), whereas it needs 10 rounds (11 rounds) according to the previous results. In addition, we find an 8-round (9-round) differential (linear) characteristic with a probability (correlation) of $2^{-127}$ ($2^{-60}$). For ASCON permutation, we provide for the first time an upper bound of the maximum probability (correlation) of 5-round differential (linear) characteristics as $2^{-70}$ ($2^{-33}$).