基于MILP的GIFT积分区分器搜索及优化  

Search and Optimization of GIFT Integral Distinguisher Based on MILP

作　　者：祖锦源 刘杰[1,2] 石一鹏 张涛 张国群[3] ZU Jinyuan;LIU Jie;SHI Yipeng;ZHANG Tao;ZHANG Guoqun(College of Software,Northwestern Polytechnical University,Xi’an 710000,China;Yangtze River Delta Research Institute,Nerthwestern Polytechnical University,Taicang,Jiangsu 215400,China;Shanghai Institute of Mechanical and Electrical Engineering,Shanghai 200000,China)

机构地区：[1]西北工业大学软件学院,西安710000 [2]西北工业大学长三角研究院,江苏太仓215400 [3]上海机电工程研究所,上海200000

出　　处：《计算机科学》2023年第S02期886-893,共8页Computer Science

基　　金：上海航天科技创新基金(SAST2021-054);太仓市基础研究计划面上项目(TC2021JC32);中央高校基本科研业务费专项资金(D5000210638)。

摘　　要：Banik等提出的轻量级分组密码GIFT算法已经入选了NIST针对国际轻量级密码算法开展的标准化竞赛的最终轮。目前已有针对其的线性分析、差分分析等的相关研究,但针对GIFT的积分分析仍待进一步研究。针对GIFT在积分密码分析过程中可分路径表达冗余的问题,提出了基于混合整数线性规划模型的积分区分器搜索求解和优化算法。首先对GIFT算法创建MILP积分分析模型,利用可分性质分别对GIFT算法的线性层和非线性层进行刻画。对线性层利用传播规则进行表达;对非线性S盒在传播规则的基础上使用贪心算法对表达式进行精简优化,得到了15个不等式作为约束条件。经过MILP求解后,得到64个9轮积分区分器。在此基础上,针对基于贪心算法的MILP求解模型精确度不足问题,引入MILP模型对S盒的可分性质进行重新表达,设计基于MILP的约简算法对GIFT积分区分器搜索进行优化,并重新求解MILP模型,最高得到了3个13轮的积分区分器。因此,基于MILP的S盒新约简算法可以优化S盒可分性质的表达,有效增加对GIFT算法的积分区分器攻击轮数,提高积分攻击效果。The lightweight block cipher GIFT algorithm proposed by Banik et al.has been selected for the final round of the NIST standardization competition for international lightweight cryptographic algorithms.At present,there have been linear analysis,difference analysis and other related studies,but the integral analysis of GIFT still needs to be further studied.Aiming at the problem of division trails expression redundancy in the process of integral cryptanalysis of GIFT,an integral dividers solution and search optimization algorithm based on mixed integer linear programming model(MILP)is proposed.Firstly,the linear layer and the nonlinear layer of the GIFT algorithm are respectively described according to their bit division property.The linear layer is expressed by the propagation rule,the greedy algorithm is used to simplify the expression for the nonlinear S-box based on the propagation rule,and 15 inequalities are obtained as constraint conditions.649-round integral discriminators are found after the MILP solution.On this basis,in order to solve the problem of insufficient accuracy of the MILP solution model based on the greedy algorithm,the MILP model is introduced to reconstruct the bit division property of the S-box.Design a MILP-based reduction algorithm to optimize the GIFT integral dividers search,and re-solve the MILP model,then obtain two 13-round integral discriminators.Therefore,the MILP-based S-box new reduction algorithm can optimize the expression of the S-box division property,and can effectively increase the number of rounds of the integral dividers attack on the GIFT algorithm,and improve the integral attack effect.

关 键 词：积分密码分析 混合整数线性规划算法 GIFT 可分性质 SPN网络结构 

分 类 号：TN918.1[电子电信—通信与信息系统]