基于可分性改进分组密码SM4和FOX的积分区分器  

Improved Integral Distinguishers Based on Division Property for SM4 and FOX Block Ciphers

作　　者：毛永霞 吴文玲[1,2] MAO Yong-Xia;WU Wen-Ling(Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China;College of Mathmatics and Information Science,Henan Normal University,Xinxiang 453000,China)

机构地区：[1]中国科学院软件研究所可信计算与信息保障实验室,北京100190 [2]中国科学院大学,北京100049 [3]河南师范大学数学与信息科学学院,新乡453000

出　　处：《密码学报》2023年第6期1197-1208,共12页Journal of Cryptologic Research

基　　金：国家自然科学基金(62072445)。

摘　　要：可分性是由Todo在EUROCRYPT 2015上首次提出来的,可以看作积分分析的推广,已经被应用于许多对称密码的分析.目前,结合可分性与数学工具,例如混合整数线性规划和布尔可满足性问题等的自动化方法是搜索积分区分器最流行的方法之一.此方法根据可分性在密码基本部件上的传播规则建立约束模型,再选择合适的初始可分性搜索积分区分器.对一个分组密码来说,不同的建模方式和模型的精度会影响自动化搜索积分区分器的结果.本文针对分组密码的两种基本部件:分支异或压缩结构和非比特置换的线性变换,分别提出了两种基于比特可分性的建模策略.策略一根据分支异或压缩结构的特点,增加相关分支输入可分性之间的约束条件,使得初始可分性经过首轮分支异或压缩之后的输出可分性为0,进而提高其他分支可分性的传播优势.策略二对非比特置换的线性变换对应的矩阵进行处理,当矩阵中包含非独立可分性传播时,增加相应的约束条件限制非独立传播比特的可分性,从而提高模型的精度,减少冗余可分迹.为了验证两种建模策略的有效性,将新方法应用于分组密码SM4和FOX:(1)构造了SM4的13轮积分区分器,比之前最好的结果多一轮;(2)构造了FOX64和FOX128的3轮积分区分器,都优于目前已知的最好积分区分器.Division property,as a generalization of integral cryptanalysis,was first proposed by Todo at EUROCRYPT 2015,and has been applied to many symmetric ciphers.Currently,the combination of division property and mathematical tools,such as mixed integer linear programming(MILP)and Boolean satisfiability problem(SAT),has become a popular approach for finding integral distinguishers by automated methods.This approach involves establishing a constraint model based on the propagation rules of division property on the fundamental components of block ciphers and selecting an appropriate initial value for division property to search for integral distinguishers.For a block cipher,the integral distinguisher obtained by automated searching is influenced by different modeling methods employed for block ciphers and the precision of the models themselves.This paper proposes two modeling strategies that leverage bit-based division property for two fundamental components of a block cipher,i.e.,the branch-based XOR compression construction and the non-bit-permutation linear transformation.Strategy 1 adds constraints between the input division property of related branches into the propagation model of branch-based XOR compression,so that the output division property after the first round of the branch-based XOR compression construct is 0,thereby improving the propagation advantage of the division property of other branches.Strategy 2 introduces constraints by handling the matrix associated with a non-bit-permutation linear transformation.When the matrix contains non-independent division property propagation,the corresponding constraints are added to limit the division property of the non-independent propagation bits.This improves the model accuracy and reduces redundant division trails.In order to verify the effectiveness of the proposed method,the proposed modeling strategies are applied to two block ciphers,namely SM4 and FOX,and the following results are obtained:(1)A 13-round integral distinguisher for SM4 is constructed,which surp

关 键 词：积分分析 可分性 混合整数线性规划 SM4 FOX 

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