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

Finding Differential Characteristics of SM4 Algorithm Based on MILP

作　　者：潘印雪 王高丽[1,2] 倪建强 Pan Yinxue;Wang Gaoli;Ni Jianqiang(Shanghai Key Laboratory of Highly Trustworthy Computing(East China Normal University),Shanghai 200062;State Key Laboratory of Cryptography,Beijing 100878)

机构地区：[1]上海市高可信计算重点实验室(华东师范大学),上海200062 [2]密码科学技术国家重点实验室,北京100878

出　　处：《计算机研究与发展》2022年第10期2299-2308,共10页Journal of Computer Research and Development

基　　金：国家重点研发计划项目(2020YFA0712300);国家自然科学基金项目(62072181);上海市可信工业互联网软件协同创新中心项目。

摘　　要：基于混合整数线性规划(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的差分特征,而且找到了概率为2的差分特征,这是目前基于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, but also get a differential characteristic with probability 2, which is the best differential characteristic using the automatic search method based on MILP.

关 键 词：混合整数线性规划 SM4算法 差分分析 差分特征 8-bit的S盒 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]