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

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):181194密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于 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分别表示Su