基于MILP寻找SM4算法的差分特征

The automatic search method based on MILP (mixed integer linear programming) has been widely used to search the differential characteristic of cryptographic algorithms, and has formed a complete framework. The basic principle of the framework is to use linear inequalities to describe the operations of cryptographic algorithms. The framework is easy to search the differential characteristics of the ciphers based on the S-box with the state of 4-bit. However, for the ciphers based on S-box with the state of 8-bit, the search model based on this framework has a large amount of computation, so that it can hardly find differential characteristics. SM4 algorithm was issued by the Chinese government in 2006. It was the national cryptographic industry standard in 2012 and was the national standard in 2016. SM4 is an iterative block cipher. The block size is 128-bit, and each round contains four 8-bit S-boxes. In order to efficiently search the differential characteristics of SM4, we propose an improved method to search difference characteristic based on MILP. For 19-round SM4, we not only obtain a differential characteristic with probability 2^-124, but also get a differential characteristic with probability 2^-123, which is the best differential characteristic using the automatic search method based on MILP.