Finding Differential Characteristics of SM4 Algorithm Based on MILP

被引：0
作者：
Pan Y. [1 ,2 ]
Wang G. [1 ,2 ]
Ni J. [1 ]
机构：
[1] Shanghai Key Laboratory of Highly Trustworthy Computing (East China Normal University), Shanghai
[2] State Key Laboratory of Cryptography, Beijing
来源：
Jisuanji Yanjiu yu Fazhan/Computer Research and Development | 2022年 / 59卷 / 10期
基金：
中国国家自然科学基金;
关键词：
8-bit S-box; Differential analysis; Differential characteristic; MILP; SM4; algorithm;
D O I：
10.7544/issn1000-1239.20220486
中图分类号：
学科分类号：
摘要：
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. © 2022, Science Press. All right reserved.
引用
收藏
页码：2299 / 2308
页数：9
相关论文
共 38 条
  • [1] Biham E, Shamir A., Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 4, 1, pp. 3-72, (1991)
  • [2] Matsui M., Linear cryptanalysis method for DES cipher, Proc of Workshop on the Theory and Application of Cryptographic Techniques, pp. 386-397, (1993)
  • [3] Knudsen L, Wagner D., Integral cryptanalysis, Proc of Int Workshop on Fast Software Encryption, pp. 112-127, (2002)
  • [4] Dinur I, Shamir A., Cube attacks on tweakable black box polynomials, Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques, pp. 278-299, (2009)
  • [5] Coppersmith D., The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development, 38, 3, pp. 243-250, (1994)
  • [6] The SMS4 block cipher
  • [7] Daemen J, Rijmen V., The block cipher Rijndael, Proc of Smart Card Research and Applications, pp. 277-284, (1998)
  • [8] Beierle C, Jean J, Kolbl S, Et al., The SKINNY family of block ciphers and its low-latency variant MANTIS, Proc of Annual Int Cryptology Conf, pp. 123-153, (2016)
  • [9] Lai Xuejia, Massey J L, Murphy S., Markov ciphers and differential cryptanalysis, Proc of Workshop on the Theory and Application of Cryptographic Techniques, pp. 17-38, (1991)
  • [10] Junod P, Vaudenay S., FOX: A new family of block ciphers, Proc of Int Workshop on Selected Areas in Cryptography, pp. 114-129, (2004)
1234