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

潘印雪; 王高丽; 倪建强

doi:10.7544/issn1000-1239.20220486

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

¹(上海市高可信计算重点实验室(华东师范大学) 上海 200062)
²(密码科学技术国家重点实验室北京 100878) (jqiangni@163.com)

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

详细信息

中图分类号: TP309.7
计量
- 文章访问数: 169
- HTML全文浏览量: 11
- PDF下载量: 102
出版历程
- 发布日期: 2022-09-30

Finding Differential Characteristics of SM4 Algorithm Based on MILP

¹(Shanghai Key Laboratory of Highly Trustworthy Computing (East China Normal University), Shanghai 200062)
²(State Key Laboratory of Cryptography, Beijing 100878)

Funds: This work was supported by the National Key Research and Development Program of China (2020YFA0712300), the National Natural Science Foundation of China (62072181), the Project of Shanghai Trusted Industry Internet Software Collaborative Innovation Center.

摘要

摘要: 基于混合整数线性规划(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算法轮数最多、概率最高的差分特征.
- 混合整数线性规划 /
- SM4算法 /
- 差分分析 /
- 差分特征 /
- 8-bit的S盒
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.
- MILP /
- SM4 algorithm /
- differential analysis /
- differential characteristic /
- 8-bit S-box

HTML全文

参考文献(0)

施引文献(19)

期刊类型引用(11)

1.	安晓明，王忠勇，翟慧鹏，巩克现，王玮，孙鹏. 基于深度学习的二进制变种协议字段划分方法. 计算机工程与设计. 2024(04): 982-988 . 百度学术
2.	黄涛，王郅伟，刘家池，龙千禧，况博裕，付安民，张玉清. 工控协议安全研究综述. 通信学报. 2024(06): 60-74 . 百度学术
3.	许伟杰，邹洪，张佳发，曾子峰，江家伟. 基于模糊测试技术的工控协议安全性分析系统. 微型电脑应用. 2024(09): 250-253 . 百度学术
4.	赵起超，杨晓龙，赵文宇，刘经纬，贾磊，于潼. 基于语义级协议解析的工控网络安全监测方法. 信息安全与通信保密. 2024(09): 19-30 . 百度学术
5.	谭高升，李伟，裴彦纯，孙军，王诗蕊. 工控协议深度包解析与检测技术研究. 网络安全技术与应用. 2023(05): 1-4 . 百度学术
6.	付安民，毛安，黄涛，胡超，刘莹，张晓明，王占丰. 基于主动交互式学习的工控协议逆向分析. 西安电子科技大学学报. 2023(04): 22-33 . 百度学术
7.	况博裕，李雨泽，顾芳铭，苏铓，付安民. 车联网安全研究综述：威胁、对策与未来展望. 计算机研究与发展. 2023(10): 2304-2321 . 本站查看
8.	徐魁，海洋，李晓辉，朱承才，陶军. 未知二进制协议的报文分割方法. 计算机技术与发展. 2023(11): 119-125 . 百度学术
9.	屠雅春，许驰，杜昕宜，王倚天，夏长清，金曦. 基于字符距离聚类的未知工控协议分类方法. 计算机应用研究. 2023(12): 3696-3700+3705 . 百度学术
10.	孙彦斌，汪弘毅，田志宏，方滨兴. 工业控制系统安全防护技术发展研究. 中国工程科学. 2023(06): 126-136 . 百度学术
11.	李长连，余思阳，程驰. 基于设备流量行为的工业物联网指纹识别技术. 工业信息安全. 2022(10): 47-56 . 百度学术