潘印雪, 王高丽, 倪建强. 基于MILP寻找SM4算法的差分特征[J]. 计算机研究与发展, 2022, 59(10): 2299-2308.
 引用本文: 潘印雪, 王高丽, 倪建强. 基于MILP寻找SM4算法的差分特征[J]. 计算机研究与发展, 2022, 59(10): 2299-2308.
Pan Yinxue, Wang Gaoli, Ni Jianqiang. Finding Differential Characteristics of SM4 Algorithm Based on MILP[J]. Journal of Computer Research and Development, 2022, 59(10): 2299-2308.
 Citation: Pan Yinxue, Wang Gaoli, Ni Jianqiang. Finding Differential Characteristics of SM4 Algorithm Based on MILP[J]. Journal of Computer Research and Development, 2022, 59(10): 2299-2308.

## Finding Differential Characteristics of SM4 Algorithm Based on MILP

• 摘要: 基于混合整数线性规划(mixed integer linear programming, MILP)的自动化搜索方法被广泛用于搜索密码算法的差分特征，已形成一套完整的框架.该框架采用的基本原理是用线性不等式来刻画密码算法的各个操作，该框架适用于搜索采用4-bit S盒的密码算法的差分特征.对于采用8-bit S盒的密码算法，基于该框架的搜索模型计算量很大，以致无法高效地找到差分特征.SM4算法于2006年由中国政府发布，于2012年成为国家密码行业标准，于2016年成为国家标准的迭代分组密码算法，其分组状态为128 b，每轮包含4个8-bit的S盒.为了高效地搜索SM4算法的差分特征，研究了对8-bit S盒进行MILP建模的问题，对于采用8-bit S盒的密码算法，改进了搜索高概率差分特征的方法.对于19轮SM4算法，不仅找到了概率为2\+\-124\的差分特征，而且找到了概率为2\+\-124\的差分特征，这是目前基于MILP建模找到的SM4算法轮数最多、概率最高的差分特征.

Abstract: 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\+\-124\, which is the best differential characteristic using the automatic search method based on MILP.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈