Differential Analysis Of Large S-boxes And ARX Ciphers Based On MILP

At present,Cryptography is indispensible for the prosperity and development of society.The cipher based on S-boxes is one of the most classical block cipher algorithms.The ARX structure is widely used in the industry due to its software-friendly implementation.At the same time,differential analysis is the most classical analysis method of modern cipher.Accordingly,it is of great importance to study the security of S-boxes cipher and ARX cipher against differential analysis.This article focuses on the modeling of ciphers based on S-boxes and ARX,and makes a differential analysis of Craft,SM4 and Ballet based on MILP technology.For the S-boxes cipher,we add the idea of Branch and Bound to the model,and propose a new MILP model for analyzing large S-boxes cipher.For the ARX cipher,we focus on the modeling of modular addition operation,and add programming skills to speed up the solution of the model.The main research results of this article are as follows:For the Craft algorithm,we solve the model and obtain the lower bound of the number of active S-boxes from 1 to 17 rounds.Our results are consistent with the known results,which proves the security against differential analysis in the single-key mode.It is worth noting that it takes 1881s to get the result without optimization method,and only 732s with optimization method for 9-round of the Craft.In addition,we verify a 13round differential characteristic with the probability of 2-124.It shows that our model construction and programming implementation are correct,which establishes the base for analysis of Large S-boxes and ARX ciphers.For the SM4 algorithm,we model its S-boxes based on abdelkhalek model and Wu model respectively.After analyzing the experimental results of these two models,we propose a new MILP model for large S-boxes cipher.We adopt the new model to model SM4 and obtain the minimum number of active S-boxes from 1 to 24 rounds.Compared with other articles,we get a tighter lower bound in some rounds.For 19-round of SM4,we not only get the differential characteristic with probability of 2-124,but also get the differential characteristic with probability of 2-123,which is the differential characteristic with the highest probability based on MILP.For 20-round of SM4,when the number of active S-boxes is 18,the differential characteristic cannot be found,so we believe that the minimum number of active S-boxes of the 20-round is greater than 18.In addition,we get that the number of active S-boxes of 24-round is at least 22,and the maximum difference probability of SM4 S-boxes is 2-6,which can prove that SM4 is against differential analysis.For the Ballet algorithm based on ARX structure,We study how to model modular addition operations efficiently,that is,based on MILP method to describe modular addition operations with 1+13 ×(n-1)linear inequalities.We propose a programming technique to reduce model variables and then improve the speed of model solving.Compared with the difference probability of 9-round given by the designer based on SAT technology is 2-43,we give the accurate probability from 1 to 7 rounds,and only give a bound for 8 or 9 rounds,which still prove that the Ballet can resist the differential analysis.But it shows that the model based on MILP has a lot of room for optimization,which is worthy of further research.