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

MILP Modeling of Division Property Propagation for Block Ciphers with Complex Linear Layers

作　　者：黄明 张莎莎 洪春雷 曾乐 向泽军 HUANG Ming;ZHANG Sha-Sha;HONG Chun-Lei;ZENG Le;XIANG Ze-Jun(Faculty of Mathematics and Statistics,Hubei University,Wuhan 433062,China;School of Communication and Information Engineering,Shanghai University,Shanghai 200444,China;Faculty of Science,The University of Melbourne,Melbourne VIC3010,Australia)

机构地区：[1]湖北大学数学与统计学学院,湖北武汉433062 [2]上海大学通信与信息工程学院,上海200444 [3]Faculty of Science,The University of Melbourne,Melbourne VIC3010,Australia

出　　处：《软件学报》2024年第4期1980-1992,共13页Journal of Software

基　　金：湖北省教育厅科学研究计划(D2020104);国家自然科学基金(61802119);武汉市科技局应用基础前沿项目(2020010601012189)。

摘　　要：混合整数线性规划(MILP)作为一种自动化搜索工具,被广泛地应用于搜索分组密码的差分、线性、积分等密码性质.提出一种基于动态选取策略构建MILP模型的新技术,该技术在不同的条件下采用不同的约束不等式刻画密码性质的传播.具体地,从可分性出发根据输入可分性汉明重量的不同,分别采用不同的方法构建线性层可分性传播的MILP模型.最后,将该技术应用于搜索uBlock和Saturnin算法的积分区分器.实验结果表明:对于uBlock128算法,该技术可以搜索到比之前最优区分器多32个平衡比特的8轮积分区分器.除此之外,搜索到uBlock128和uBlock256算法比之前最优区分器更长一轮的9和10轮积分区分器.对于Saturnin256算法,同样搜索到比之前最优区分器更长一轮的9轮积分区分器.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 longer than the previous optimal integral distinguisher.

关 键 词：混合整数线性规划 可分性 线性层 汉明重量 积分区分器 

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