Page 402 - 《软件学报》2024年第4期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(4):1980−1992 [doi: 10.13328/j.cnki.jos.006839] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
分组密码复杂线性层可分性传播的 MILP 刻画方法

黄 明 1 , 张莎莎 1 , 洪春雷 2 , 曾 乐 3 , 向泽军 1

1
(湖北大学 数学与统计学学院, 湖北 武汉 433062)
2
(上海大学 通信与信息工程学院, 上海 200444)
3
(Faculty of Science, The University of Melbourne, Melbourne VIC3010, Australia)
通信作者: 张莎莎, E-mail: amushasha@163.com

摘 要: 混合整数线性规划 (MILP) 作为一种自动化搜索工具, 被广泛地应用于搜索分组密码的差分、线性、积分
等密码性质. 提出一种基于动态选取策略构建 MILP 模型的新技术, 该技术在不同的条件下采用不同的约束不等
式刻画密码性质的传播. 具体地, 从可分性出发根据输入可分性汉明重量的不同, 分别采用不同的方法构建线性层
可分性传播的 MILP 模型. 最后, 将该技术应用于搜索 uBlock 和 Saturnin 算法的积分区分器. 实验结果表明: 对于

uBlock128 算法, 该技术可以搜索到比之前最优区分器多 32 个平衡比特的 8 轮积分区分器. 除此之外, 搜索到
uBlock128 和 uBlock256 算法比之前最优区分器更长一轮的 9 和 10 轮积分区分器. 对于 Saturnin256 算法, 同样搜
索到比之前最优区分器更长一轮的 9 轮积分区分器.
关键词: 混合整数线性规划; 可分性; 线性层; 汉明重量; 积分区分器
中图法分类号: TP309

中文引用格式: 黄明, 张莎莎, 洪春雷, 曾乐, 向泽军. 分组密码复杂线性层可分性传播的MILP刻画方法. 软件学报, 2024, 35(4):
1980–1992. http://www.jos.org.cn/1000-9825/6839.htm
英文引用格式: Huang M, Zhang SS, Hong CL, Zeng L, Xiang ZJ. MILP Modeling of Division Property Propagation for Block Ciphers
with Complex Linear Layers. Ruan Jian Xue Bao/Journal of Software, 2024, 35(4): 1980–1992 (in Chinese). http://www.jos.org.cn/
1000-9825/6839.htm

MILP Modeling of Division Property Propagation for Block Ciphers with Complex Linear Layers
1
1
3
2
HUANG Ming , ZHANG Sha-Sha , HONG Chun-Lei , ZENG Le , XIANG Ze-Jun 1
1
(Faculty of Mathematics and Statistics, Hubei University, Wuhan 433062, China)
2
(School of Communication and Information Engineering, Shanghai University, Shanghai 200444, China)
3
(Faculty of Science, The University of Melbourne, Melbourne VIC3010, Australia)
Abstract: As an automatic search tool, mixed integer linear programming (MILP) is widely used to search for differential, linear, integral,
and other cryptographic properties of block ciphers. In this study, a new technique of constructing MILP models based on a dynamic
selection strategy is proposed, which uses different constraint inequalities to describe the propagation of cryptographic properties under
different conditions. Specifically, according to the different Hamming weights of the input division property, this study adopts different
methods to construct MILP models of the division property propagation with linear layers. Finally, this technique is applied to search for
integral distinguishers of uBlock and Saturnin algorithms. The experimental results show that the proposed technique can obtain an 8-round
integral distinguisher with 32 more balance bits than the previous optimal integral distinguisher for the uBlock128 algorithm. In addition,
this study gets 9- and 10-round integral distinguishers for uBlock128 and uBlock256 algorithms which are one round longer than the
previous optimal integral distinguishers. For the Saturnin256 algorithm, the study finds a 9-round integral distinguisher which is one round

* 基金项目: 湖北省教育厅科学研究计划 (D2020104); 国家自然科学基金 (61802119); 武汉市科技局应用基础前沿项目 (20200106
01012189)
收稿时间: 2022-08-26; 修改时间: 2022-10-15; 采用时间: 2022-11-22; jos 在线出版时间: 2023-07-28
CNKI 网络首发时间: 2023-07-31