基于MILP的相关密钥差分分析安全评估算法改进_周春宁.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):181194密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]基于 MILP 的相关密钥差分分析安全评估算法改进*周春宁1,2,张文涛1,2,曹文芹31.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 1000932.中国科学院大学 网络空间安全学院,北京 1000493.山东理工大学 数学与统计学院,淄博 255000通信作者:张文涛,E-mail:摘要:近年来,基于混合整数线性规划(MILP)的密码分析方法在对称密码的安全性分析中发挥了重要作用.Zhou 等人在 FSE 2020 上提出了结合分治法,大幅度提高基于 MILP 的差分和线性特征搜索方法效率.本文将 Zhou 等人的方法扩展到相关密钥差分特征搜索,提出了一种更高效的基于 MILP 的相关密钥差分分析安全评估新算法.应用新算法评估了 PRESENT-80/128 抵抗相关密钥差分分析的安全性,得到了高达 15 轮的最小活跃 S 盒数量和高达 12 轮的最优相关密钥差分特征,并由此得到了迄今最紧的 PRESENT-80/128 抵抗相关密钥差分分析安全界.找到了一条概率为 262的 15 轮 PRESENT-80 相关密钥差分特征,和一条概率为 260的 16 轮 PRESENT-128 相关密钥差分特征,是目前对于PRESENT-80/128 轮数最长的相关密钥差分特征.关键词:分组密码;相关密钥差分分析;MILP;PRESENT-80/128中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000588中文引用格式:周春宁,张文涛,曹文芹.基于 MILP 的相关密钥差分分析安全评估算法改进J.密码学报,2023,10(1):181194.DOI:10.13868/ki.jcr.000588英文引用格式:ZHOU C N,ZHANG W T,CAO W Q.Improvement of MILP-aided security evaluationalgorithm of related-key differential cryptanalysisJ.Journal of Cryptologic Research,2023,10(1):181194.DOI:10.13868/ki.jcr.000588Improvement of MILP-aided Security Evaluation Algorithm ofRelated-key Differential CryptanalysisZHOU Chun-Ning1,2,ZHANG Wen-Tao1,2,CAO Wen-Qin31.State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy ofSciences,Beijing 100093,China2.School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China3.School of Mathematics and Statistics,Shandong University of Technology,Zibo 255000,ChinaCorresponding author:ZHANG Wen-Tao,E-mail:Abstract:In recent years,mixed-integer linear programming(MILP)-aided methods have playedan important role in providing security evaluation of symmetric-key primitives.At FSE 2020,Zhou et*基金项目:国家自然科学基金(61379138)Foundation:National Natural Science Foundation of China(61379138)收稿日期:2022-02-07定稿日期:2022-05-09182Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023al.proposed an MILP-aided algorithm that employed a divide-and-conquer approach,significantlyimproving the search efficiency for differential and linear characteristics.This paper extends Zhou etal.s method to search for related-key differential characteristics and proposes a more efficient MILP-aided algorithm for evaluating the security against related-key differential cryptanalysis.Applying thisnew algorithm to PRESENT-80/128,the minimum number of active S-boxes of related-key differentialcharacteristics can be obtained for up to 15 rounds and the best related-key differential characteris-tic can be obtained for up to 12 rounds,from which the tightest security bounds against related-keydifferential cryptanalysis for PRESENT-80/128 is obtained.Furthermore,related-key differential char-acteristics of 15-round PRESENT-80 and 16-round PRESENT-128 can be found with probabilities of262and 260,respectively.Key words:block cipher;related-key differential cryptanalysis;MILP;PRESENT-80/1281引言差分分析1是针对分组密码最早提出、最有效的密码分析方法之一.对于一个新的分组密码算法的设计,差分分析的抵抗能力是一项必须考虑的重要准则.相关密钥差分分析2是差分分析的一种变形,该类分析方法赋予攻击者更多的权限.在相关密钥差分分析下,攻击者不知道确切的密钥,但是可以知道或选择密钥之间的关系.因此,在相关密钥机制下可能会对分组密码产生更高轮数的攻击.例如,AES3被证明足以抵抗单密钥差分分析,但是存在高概率的相关密钥差分特征,并且在 AES 的相关密钥类型攻击方面取得了突破性的成果4,5.近年来,基于混合整数线性规划(mixed-integer linear programming,MILP)的自动化分析方法已经成为了密码设计者和分析者最青睐的方法之一,被广泛应用于分组密码的安全性分析研究中.该类方法由Mouha 等人6于 2011 年首次提出,用于计算面向字分组密码的最小活跃 S 盒数量的下界,从而提供面向字分组密码抵抗差分和线性分析的安全界.随后,Sun 等人7,8将该方法进一步扩展到面向比特分组密码的安全评估中.他们对比特级操作进行建模,基于 MILP 方法来解决两个问题:最小活跃 S 盒数量的计算和最优(相关密钥)差分/线性特征的搜索.他们构建的 MILP 模型可用于评估分组密码抵抗(相关密钥)差分/线性分析的安全性,并搜索实际的(相关密钥)差分/线性特征.对于 PRESENT-80/1289的相关密钥差分分析,他们得到了 24 轮 PRESENT-80 相关密钥差分特征的最大概率上界为 264,并找到了一条概率为 211的 7 轮 PRESENT-128 相关密钥差分特征(非最优的).自此之后,基于 MILP 的方法被进一步地拓展到各种不同类型区分器的搜索,例如积分区分器10、不可能差分区分器11等.基于 MILP 的方法具有操作简单、易于实现等优点,仅需简单的代码将密码学问题编码为 MILP 问题,然后借助通用求解器(如 Gurobi12等求解器)自动求解 MILP 模型即可.然而,由于 MILP 模型的规模随着密码算法轮数的增加而显著增长,基于 MILP 的自动化分析方法的效率往往不足以满足人们的需求.如何提高该类方法效率的问题引起了广泛关注,众多的密码学者在该领域开展了大量的研究工作,并取得了一系列的成果.然而,大多数的研究工作主要关注差分分析,而很少关注相关密钥差分分析.在单密钥差分分析下,仅明文注入了差分.而在相关密钥差分分析下,明文和种子密钥都可以注入差分,它们分别经过加密算法和密钥编排算法进行传播.相比于单密钥差分分析,相关密钥差分分析下构建的 MILP 模型规模更大,模型求解的效率更低.据我们所知,对于分组密码的相关密钥差分分析,目前尚没有高效的基于 MILP 的安全评估方法.在 FSE 2020 上,基于活跃 S 盒数量(或权重)最小的差分/线性特征通常在某一轮包含少量的(0,1或 2 个)活跃 S 盒这一观察,Zhou 等人13将分治法的思想应用到基于 MILP 的方法中.他们提出了一种改进的基于 MILP 的差分/线性特征搜索算法,并显著提升了对 PRESENT 等五个轻量级分组密码的差分和线性特征搜索的效率.我们观察到活跃 S 盒数量(或权重)最小的相关密钥差分特征通常在某些轮包含少量活跃 S 盒,这与单密钥差分特征非常相似.然而,将他们的算法直接应用到相关密钥差分特征搜索,其效率不高,不能得到令人满意的结果.受此启发,我们进一步将 Zhou 等人的方法应用到分组密码抵抗相关密钥差分分析安全评估中,提高了基于 MILP 的安全评估方法的效率.其中,差分特征的权重定义周春宁 等:基于 MILP 的相关密钥差分分析安全评估算法改进183为概率的负对数.本文主要贡献如下:(1)结合分治法,我们设计了一种改进的基于 MILP 的算法,搜索活跃 S 盒数量(或权重)最小的相关密钥差分特征.该算法由三个部分组成:(a)首先,提出一种动态的方法,将所有相关密钥差分特征集合恰当地划分成若干较小的子集.(b)其次,在每一个子集内搜索活跃 S 盒数量(或权重)最小的相关密钥差分特征,这等价于求解相应的 MILP 模型.利用 Gurobi 求解器来求解模型,并借助 Gurobi 提供的参数 Cutoff 来提前终止某些模型的求解.采用这项技术,进一步提高了搜索效率.(c)最后,结合所有子集内搜索到的结果,得到分组密码相关密钥差分特征的最小活跃 S 盒数量(或权重).(2)将我们的新算法应用到 PRESENT-80 和 PRESENT-128,我们得到了这两个版本的高达 15 轮相关密钥差分特征的最小活跃 S 盒数量;高达 12 轮的最优相关密钥差分特征.根据这些结果,我们得到了迄今为止最紧的 PRESENT-80/128 抵抗相关密钥差分分析安全界.我们在同一平台上实现了 Sun 等人7,8的方法和我们的算法,对比的实验结果总结在表1中,t1和 t2分别表示Sun 等人7,8的方法和我们的算法的运行时间.从表格可以看出,我们的算法比 Sun 等人的方法更高效,在更短的时间内覆盖更高的轮数.例如,对于前 13 轮 PRESENT-80 相关密钥差分特征最小活跃 S 盒数量计算,我们的算法比 Sun 等人的方法在速度上提升了近 3.5 倍.我们的算法在 1.1 天左右(26.8 h)得到了前 12 轮 PRESENT-128 的最优相关密钥差分特征,而 Sun 等人的方法无法在 3 天内(89 h)得到 11 轮 PRESENT-128 的最优相关密钥差分特征.(3)对于 PRESENT-80,我们得到了概率分别为 248,255和 262的 13 轮、14 轮和 15 轮相关密钥差分特征.对于 PRESENT-128,我们得到了概率分别为 238、246、252和 260的 13 轮、14 轮、15 轮和 16 轮相关密钥差分特征.对于 PRESENT-80/128,我们得到了目前为止轮数最长的相关密钥差分特征.表 1 两种方法对于 PRESENT-80/128 的对比实验结果Table 1Experimental results of comparison with two methods on PRESENT-80/128密码算法相关密钥差分特征最小活跃 S 盒数量计算最优相关密钥差分特征搜索最高轮数t1(h)t2(h)最高轮数t1(h)t2(h)PRESENT-80139.12.6108952.714826.811-6015-1812-60.1PRESENT-1281315.69.11017.19.3148936.5118920.115-6912-26.8本文的结构安排如下:第2节介绍基于 MILP 的方法的相关工作.第3节研究分组密码抵抗相关密钥差分分析的安全评估,并提出一种改进的基于 MILP 的算法.第4节将提出的新算法应用于 PRESENT-80/128 的相关密钥差分分析.第5节对全文进行总结并展望未来的一些工作.2预备知识2.1Sun 等人的 MILP 模型框架对于相关密钥差分特征最小活跃 S 盒数量计算和最优相关密钥差分特征搜索这两个问题,Sun 等人7,8将其转化为 MILP 模型,通过求解 MILP 模型来解决上述两个问题.184Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023对于一个分组密码,用 0-1 变量表示比特级差分,使得该变量等于 1 当且仅当对应的比特级差分不为零.假设分组密码的加密算法和密钥编排算法都是由异或操作、S 盒和线性置换构成,采用下面的约束条件来描述比特级差分经过加密算法以及密码编排算法的传播.描述异或操作的约束条件.令变量 a,b 和 c 分别表示异或操作的输入和输出差分,采用方程(1)描述比特级差分经过异或操作的传播:a+b+c 2d,d a,d b,d c,a+b+c 2,(1)其中 d表示一个取值为 0 或 1 的虚拟变量.描述 S 盒的约束条件.采用凸闭包计算方法,描述比特级差分经过 S 盒的传播.对于一个 w v比特的 S 盒,将一条有效的差分传播(x0,x1,xw1)(y0,y1,yv1)看作是 Fw+v2中的一个点:(x0,x1,xw1,y0,y1,yv1)Fw+v2.那么 S 盒的所有有效差分传播构成一个有限的离散点集.通过借助 SageMath 软件14计算这个离散点集的凸闭包 H-Representation,得到一些线性不等式,这些线性不等式的所有可行解恰好等于这个集合包含的所有点.SageMath 返回的不等式数量通常非常多,因此采用一种贪心算法来减少不等式的数量.最终,选取少量的线性不等式,其所有可行解恰好为 S 盒的所有有效差分传播.此外,对于分支数 BS大于等于 3 的 S 盒,例如 PRESENT 的 S 盒,文献 15 研究表明,将方程(2)添加到 MILP 模型中可以加快模型求解的速度.w1k=0 xk+v1k=0yk BSdS,dS xk,k 0,1,w 1,dS yk,k 0,1,v 1,(2)其中 dS表示一个取值为 0 或 1 的虚拟变量.为了计算最小活跃 S 盒数量,引入 0-1 变量 A 来表示 S 盒的字级差分,变量 A 与 S 盒的比特级输入差分之间的关系描述为:A xk 0,k 0,1,w 1;x0+x1+xw1 A 0,也就是说,变量 A 等于 1 当且仅当 S 盒的输入差分不全为零.为了搜索最优差分特征,还需要将差分概率编码到 MILP 模型中.以差分概率 Pr 取值为 1、22、23这三种情况的 44 比特 S 盒(如 PRESENT的 S 盒)为例,一条有效差分传播被看作一个 10-维的点:(x0,x1,x2,x3,y0,y1,y2,y3,p0,p1)F102,其中(p0,p1)=(0,0),Pr=1;(0,1),Pr=22;(1,1),Pr=23,也就是说,概率 Pr 可以通过两个 0-1 变量 p0和 p1编码到模型中:Pr=2(p0+2p1).采用凸闭包计算方法,生成一组描述上述 10-维点集的线性不等式,该线性不等式组的所有可行解恰好等于 S 盒的所有附带概率信息的差分传播.额外的约束条件.在相关密钥差分分析下,限制种子密钥差分至少有 1 比特活跃.此外,所有的变量都限制为 0-1 变量.对于最小活跃 S 盒数量计算,将模型的目标函数设为最小化描述每一轮 S 盒字级差分的变量 A 之和.对于最优相关密钥差分特征搜索,将目标函数设为最小化描述每一轮 S 盒概率信息的变量(p0+2p1)之和.同时考虑分组密码的加密算法和密钥编排算法,采用上述约束条件和目标函数,得到一个 MILP 模型.通过求解该模型,即可得到分组密码相关密钥差分特征的最小活跃 S 盒数量或最优相关密钥差分特征,从周春宁 等:基于 MILP 的相关密钥差分分析安全评估算法改进185而评估分组密码抵抗相关密钥差分分析的安全性.2.2Zhou 等人的改进算法基于活跃 S 盒数量(或权重)最小的差分/线性特征通常在某一轮包含少量的(0、1 或 2 个)活跃 S盒这项观察,Zhou 等人13结合分治法的思想来改进基于 MILP 的搜索方法.对于一个 r 轮分组密码的最小活跃 S 盒数量或最优差分/线性特征的搜索,该算法由以下三个步骤组成:步骤 1 将所有 r 轮差分/线性特征集合划分成若干个较小的子集.对于 SPN 结构的分组密码,例如PRESENT,整个集合被划分成两大类子集.在第一类子集中,差分/线性特征在每一轮都包含大于等于 1(或 2)个活跃 S 盒;并且某一轮恰好有 1(或 2)个活跃 S 盒,而且这一轮的输入差分是固定的.在第二类子集中,差分/线性特征在每一轮都包含大于等于 3 个活跃 S 盒;步骤 2 在每一个子集内搜索活跃 S 盒数量(或权重)最小的 r 轮差分/线性特征,这等价于求解一个可行域为该子集的 MILP 模型.采用已有的方法,构建一个用于计算最小活跃 S 盒数量(或搜索最优差分/线性特征)的 MILP 模型,该模型的可行域是所有有效 r 轮差分/线性特征集合.通过向模型中添加简单的约束条件,例如,描述活跃 S 盒数量下界的线性不等式,描述某一轮输入差分/线性掩码的线性不等式,使得模型的可行域等于该子集.因此,求解该模型就可以得到对应子集内活跃 S 盒数量(或权重)最小的 r 轮差分/线性特征.步骤 3 结合所有的子集内搜索到的结果,即可得到整个集合内活跃 S 盒数量(或权重)最小的 r 轮差分/线性特征.为了进一步提高效率,在步骤 2 中采用以下 3 个技术,剪枝掉尽可能多的不必要搜索的子集,从而大大减少了算法的运行时间.技术 1 在搜索的最开始,根据先验知识找到一条有效的 r 轮差分/线性特征,并将其作为当前的最优r 轮差分/线性特征.例如,将已经搜索到的最优(r 1)轮差分/线性特征的 S 盒的差分/线性模式固定到 r 轮密码算法中,并基于 MILP 方法搜索此时的最优 r 轮差分/线性特征.将这条 r 轮差分/线性特征的活跃 S 盒数量(或权重)作为最小活跃 S 盒数量(或权重)的上界,记作 W.在搜索的过程中,如果找到了一条活跃 S 盒数量(或权重)更小的 r 轮差分/线性特征,动态更新当前的最优 r 轮差分/线性特征和上界 W.技术 2 技术 1 中介绍的上界 W 是一个阈值,用于剪枝那些不存在更优的 r 轮差分/线性特征的子集.在访问某一个子集时,估计其包含的 r 轮差分/线性特征的最小活跃 S 盒数量(或权重)的下界,记作 W.如果这个下界大于等于 W,则说明这个子集合内不存在比当前的最优 r 轮差分/线性特征更好的特征,因此可以提前终止对这个子集合的搜索,访问下一个子集.技术 3 为了能够尽可能早地搜索到更好的 r 轮差分/线性特征,根据以下两点来选取子集的搜索顺序:(1)优先搜索更可能存在最优 r 轮差分/线性特征的子集;(2)优先搜索对应的 MILP 模型求解时间更短的子集.3基于 MILP 的相关密钥差分分析安全评估新算法对于轻量级分组密码,例如 PRESENT 等,我们观察到活跃 S 盒数量(或权重)最小的相关密钥差分特征通常在某些轮包含少数的活跃 S 盒,这与单密钥差分特征非常相似.基于这一观察,我们探索如何将Zhou 等人的算法扩展到相关密钥差分特征搜索中.为此,我们提出以下两个主要的创新点:(1)根据实验观察,如果直接采用 Zhou 等人的方法来划分相关密钥差分特征集合,基于 MILP 方法在子集内搜索的效率非常低.为此,在步骤 1 中,我们提出一种更适合的动态机制,将所有相关密钥差分特征集合划分成若干个较小的子集.(2)根据技术 1 和技术 2,我们只关注活跃 S 盒数量(或权重)小于 W(最小活跃 S 盒数量或权重上界)的相关密钥差分特征.因此,在步骤 2 中,我们采用 Gurobi 求解 MILP 模型时将参数 Cutoff设置为 W.如果模型最优解的目标值大于 W,那么将提前终止对该模型的求解.通过这样做,大186Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023多数模型的求解都会提前终止,从而较快地剪枝大量不必要搜索的子集.将上述两点创新加入到 Zhou 等人的算法中,我们提出了一种新的相关密钥差分特征搜索算法,更高效地基于 MILP 方法评估分组密码抵抗相关密钥差分分析的安全性.为了方便起见,我们仅以最优相关密钥差分特征搜索为例,介绍算法的具体过程.对于相关密钥差分特征最小活跃 S 盒数量的搜索,只需要将该算法稍微修改即可.3.1相关密钥差分特征集合的划分在 Zhou 等人的算法中,如何划分集合对于算法效率的影响至关重要,主要有两个方面:(1)划分的子集数量越多,算法复杂度越高;(2)对应于子集内搜索的 MILP 模型求解时间越长,算法的时间成本越大.为此,我们提出了一种恰当的方法来划分所有相关密钥差分特征构成的集合.根据 PRESENT-80 相关密钥差分特征搜索的实验结果,我们有以下观察:(1)当固定分组密码的某一轮输入差分时,搜索单密钥差分特征的 MILP 模型通常可以在短时间内求解完毕,而搜索相关密钥差分特征的 MILP 模型通常求解较慢.因此,Zhou 等人提出的划分单密钥差分特征集合的方法不适用于相关密钥差分特征集合的划分.(2)当固定分组密码的某连续两轮 S 盒的差分模式时,搜索相关密钥差分特征的 MILP 模型通常求解较快.其中,NS个 S 盒的差分模式定义为一个向量 DP=(p1,p2,pNS),当且仅当第 i 个S 盒活跃(输入差分非零)时,pi取值为 1,否则 pi取值为 0,1 i NS.根据上述观察,我们设计一个动态的集合划分方法,使得基于 MILP 方法在子集内搜索最优相关密钥差分特征的效率较高.接下来详细阐述该集合划分方法.对于轮数 r,我们将其分成 n=r2 个部分,每部分由连续的两轮组成.对应地,通过以下规则生成一个二元组 r_set:r_set=(i,i+1)|i 1,3,2n 1,通过从 r_set 的中间元素开始分别向两边遍历,生成列表 r_split.具体地,我们最开始遍历 r_setn2+1.如果 n 是奇数,接下来遍历 r_setn2+2+i 和 r_setn2 i;如果 n 是偶数,接下来遍历r_setn2i 和 r_setn2+2+i,i=0,1,n2,直到遍历完 r_set 中的所有元素.例如,当 r=6或 r=7 时,r_split=(3,4),(5,6),(1,2).当 r=8 或 r=9 时,r_split=(5,6),(3,4),(7,8),(1,2).接下来,我们依据列表 r_split 来划分集合.为了方便说明,我们用 Sr,NA,i,DP来表示满足以下两个约束条件的所有 r 轮相关密钥差分特征集合:约束条件 1 r_split 中的每连续两轮都包含至少 NA个活跃 S 盒.约束条件 2 r_split 中第 i 个连续两轮包含 NA个活跃 S 盒,并且这两轮 S 盒的差分模式等于 DP.特别地,当 i=0,DP=0 时,对 r_split 中第 i 个连续两轮的 S 盒差分模式没有约束,也就是忽略第二个约束条件.因此,一个 r 轮分组密码的所有 r 轮相关密钥差分特征集合可以记作 Sr,0,0,0.接下来,我们采用一种动态的方法将该集合划分成若干较小的子集.首先,将集合 Sr,0,0,0划分为:Sr,0,0,0=(i,DPSr,0,i,DP)Sr,1,0,0,其中 i 1,2,n,DP 属于 r_split 中第 i 个连续两轮 S 盒的所有差分模式的集合,并且这两轮包含0 个活跃 S 盒.然后,我们在前面的子集 Sr,0,i,DP中搜索最优 r 轮相关密钥差分特征,并将其更新为当前的最优 r 轮相关密钥差分特征.此外,我们根据方程(3)估计子集 Sr,NA,0,0中包含的 r 轮相关密钥差分特征的最小权重下界:max(r2 NA wS,max1ir(Wi+r i2 NA wS),(3)周春宁 等:基于 MILP 的相关密钥差分分析安全评估算法改进187其中 wS表示单个 S 盒的最小权重,Wi表示 i 轮密码算法的最小权重.对于子集 Sr,1,0,0,如果根据方程(3)得到的下界大于或等于当前最优 r 轮相关密钥差分特征的权重,那么终止搜索.否则,我们进一步地将子集划分为:Sr,1,0,0=(i,DPSr,1,i,DP)Sr,2,0,0,其中 i 1,2,n,DP 属于 r_split 中第 i 个连续两轮 S 盒的所有差分模式的集合,并且这两轮包含1 个活跃 S 盒.接下来,继续以同样的方式划分子集 Sr,NA,0,0,NA=2,3,直到满足终止搜索条件.综上所述,集合 Sr,0,0,0被划分为:Sr,0,0,0=(i,DPSr,0,i,DP)(i,DPSr,NA1,i,DP)Sr,NA,0,0,(4)其中 NA的取值从 1 开始每次递增加 1,直到子集 Sr,NA,0,0可以被证明不存在权重更小的 r 轮相关密钥差分特征权重,i 1,2,n,DP 属于 r_split 中第 i 个连续两轮 S 盒的所有差分模式的集合,并且这两轮包含(0,1,NA 1)个活跃 S 盒.3.2基于 MILP 方法在子集内的搜索采用第2节介绍的方法,我们构建一个用于搜索最优 r 轮相关密钥差分特征的 MILP 模型 M,这个模型的可行域是所有有效 r 轮相关密钥差分特征集合.对于方程(4)中的子集,我们介绍额外的约束条件,并将其添加到模型 M 中,使得该模型的可行域恰好是这个子集.通过求解这个 MILP 模型,即可得到该子集内的最优 r 轮相关密钥差分特征.对于方程(4)中的一个子集 Sr,NA,i,DP,其包含的 r 轮相关密钥差分特征满足约束条件 1 和 2.令Aj,k表示第 j 轮第 k 个 S 盒的字级输入差分,那么约束条件 1 可以由方程(5)描述:(Nj,0Sk=1Ar_splitj0,k+Nj,1Sk=1Ar_splitj1,k)NA,j 1,2,n,(5)其中,Nj,mS表示第 r_splitjm轮包含的 S 盒总数,m 0,1.此外,约束条件 2 可以由方程(6)描述:Ar_spliti0,k=DPk,k 1,2,Ni,0S;Ar_spliti1,k=DPNi,0S+k,k 1,2,Ni,1S,(6)其中 DPj是向量 DP 的第 j 比特.通过将方程(5,6)添加到模型 M 中,并求解该模型,即可得到子集Sr,NA,i,DP内的最优 r 轮相关密钥差分特征.3.3搜索最优 r 轮相关密钥差分特征的改进算法根据前面的准备工作,我们设计一个算法来搜索 r 轮分组密码的最优相关密钥差分特征.我们将搜索过程以伪代码的形式总结在算法1,下面介绍详细的过程.首先,根据技术 1,生成一条有效的 r 轮相关密钥差分特征,并将它的权重初始化为 r 轮相关密钥差分特征的最小权重上界 W.接下来,我们根据方程(4)将所有 r 轮相关密钥差分特征集合划分成若干个较小的子集,并在每一个子集内搜索最优 r 轮相关密钥差分特征.对于每一个 NA 0,1,调用函数 estiLB(),具体见算法2,它根据方程(3)来计算子集 Sr,NA,0,0内 r 轮相关密钥差分特征的最小权重下界.如果该下界大于或等于上界 W,说明该子集内不存在权重更小的 r 轮相关密钥差分特征,此时满足集合划分的终止条件.否则,我们根据方程(4)继续划分子集,并调用函数 SearchWithMILP(),基于 MILP 方法在子集内搜索最优 r轮相关密钥差分特征,具体见算法3.函数 SearchWithMILP()有 6 个输入:GOAL,r_pattern,pattern,r_lb,lb,W,并用 Gurobi 的语188Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023算法 1 最优相关密钥差分特征的搜索算法Input:一个 r 轮分组密码Output:最优 r 轮相关密钥差分特征的权重1根据轮数 r 生成列表 r_split;2根据一些先验信息生成 W;3NA 0;4W estiLB(r,NA);5while W W do6将 r2 维列表 lb 的所有元素初始化为 NA;7for i=1 to r2 do8W max(W,(i 1)(NA+1)wS+(r2 i+1)NA wS);9if W W then10遍历下一个 i 的取值;11end12foreach 第 r_spliti0轮到 r_spliti1轮 S 盒的差分模式 DP1,其中包含 NA个活跃 S 盒 do13if r 小于一个经验值 MaxR1then14obj SearchWithMILP(“DC”,r_spliti,DP1,r_split,lb,W);15W min(W,obj);16end17else18if r 大于经验值MaxR1并且小于一个经验值 MaxR2then19obj SearchWithMILP(“AS”,r_spliti,DP1,r_split,lb,WwS);20if obj wS W then21遍历下一个 DP1的取值;22end23end24if r_spliti0r2then25r=r_spliti1+1;26end27else28r=r_spliti0 1;29end30foreach 第 r轮 S 盒的差分模式 DP2,其中包含少于 2 个活跃 S 盒 do31obj SearchWithMILP(“DC”,r_spliti,(r,r),DP1,DP2,r_split,lb,W);32W min(W,obj);33if W W then34break;35end36end37if W W then38break;39end40obj SearchWithMILP(“DC”,r_spliti,DP1,r_split+(r,r),lb+2,W);41W min(W,obj);42end43if W W then44break;45end46end47lbi=NA+1;48end49NA=NA+1;50W estiLB(r,NA);51end52return W;周春宁 等:基于 MILP 的相关密钥差分分析安全评估算法改进189算法 2 函数 estiLB()1Function estiLB(r,NA)2begin3return max(r2 NA wS,max1i3 d15.2 h1115151295 s93 s2407.3 h1216166.5 h207 s242441 s1318193869 s5030 s1420223 d4.2 h152511.3 h总时间3.4 d18 h3.7 d60.1 h表 3 PRESENT-128 的相关密钥差分分析结果Table 3Experimental results of PRESENT-128 against related-key differential cryptanalysis轮数本文结果#AS得到#AS 的 t1、t2Pr得到 Pr 的 t1、t2t1t2t1t2200.02 s0.06 s200.02 s0.07 s300.02 s0.08 s200.02 s0.08 s410.3 s0.4 s221 s0.23 s527 s5 s2416 s0.31 s6420 s15 s2874 s5 s7540 s29 s211313 s184 s87134 s1011 s2151455 s1468 s98175 s875 s2214.2 h6150 s109844 s1618 s22512.3 h7.1 h11101520 s827 s2283 d10.8 h12113681 s2024 s2306.7 h131513.8 h7.3 h1418 3 d27.4 h152032.5 h总时间 3.7 d69 h3.7 d26.8 h192Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023表 4 概率为 262的 15 轮 PRESENT-80 相关密钥差分特征Table 415-round related-key differential characteristics for PRESENT-80 with a probability of 262轮数输入差分轮密钥差分10 x007702000d0000000 x000002000000000020 x00000000004030000 x000000000040000030 x00000000000000080 x000000000000000840 x00000000000000000 x000000000000000050 x00000000000000000 x000020000000000060 x08000000080000000 x000000000400000070 x40400000000040400 x000000000000008080 x0000a00a0000a00a0 x000000000000000090 x09090000000000000 x0002000000000000100 x00005000400000000 x0000000040000000110 x00000000000008000 x0000000000000800120 x00000000000000000 x0000000000000000130 x00000000000000000 x0020000000000000140 x20002000000000000 x0000000400000000150 x00008900000089000 x000000000