对轻量级分组密码PICO算法的差分攻击.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(4):685701密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]对轻量级分组密码 PICO 算法的差分攻击*王彩冰1,2,张志宇1,2,胡 磊1,21.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 1000932.中国科学院大学 网络空间安全学院,北京 100049通信作者:胡磊,E-mail:摘要:PICO 算法是一个 SP 结构的迭代型轻量级密码算法,目前对该算法的差分分析和相关密钥分析研究尚未完善.本文借助自动化搜索技术,设计了一套基于 SAT 方法搜索 SP 结构算法差分路径和差分闭包的自动化工具,构建了搜索约减轮 PICO 算法差分路径以及差分闭包的 SAT 模型,评估了 PICO 算法抵抗差分攻击的能力,提供了比之前分析结果更准确的安全评估.给出了 122 轮 PICO 算法的最优差分路径及其概率;搜索到概率为 260.75的 21 轮差分闭包和概率为 262.39的 22 轮差分闭包;实现了 26轮 PICO 算法的密钥恢复攻击,攻击的时间复杂度为 2101.106,数据复杂度为 263,存储复杂度为 263.研究了 PICO 算法抵抗相关密钥攻击的能力,发现 PICO 算法的密钥编排算法存在缺陷,构建了任意轮概率为 1 的相关密钥区分器,给出了全轮 PICO 算法的密钥恢复攻击.所提模型适用于其他轻量级密码算法,尤其是拥有更长的分组或者轮数更多的分组密码算法.关键词:PICO 算法;SP 结构;差分攻击;布尔可满足性问题;密钥恢复攻击;相关密钥攻击中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000619中文引用格式:王彩冰,张志宇,胡磊.对轻量级分组密码 PICO 算法的差分攻击J.密码学报,2023,10(4):685701.DOI:10.13868/ki.jcr.000619英文引用格式:WANG C B,ZHANG Z Z,HU L.Differential cryptanalysis on ultra lightweight block cipherPICOJ.Journal of Cryptologic Research,2023,10(4):685701.DOI:10.13868/ki.jcr.000619Differential Cryptanalysis on Ultra Lightweight Block Cipher PICOWANG Cai-Bing1,2,ZHANG Zhi-Yu1,2,HU Lei1,21.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,ChinaCorresponding author:HU Lei,E-mail:Abstract:PICO is an iterative lightweight block cipher with SP structure,whose differential andrelated-key cryptanalyses are insufficient.This paper designs an SAT-based tool to search for optimaldifferential trails and differentials of lightweight block ciphers with SP structure using the automaticsearching method.This paper designs an SAT model to search for optimal differential trails and*基金项目:国家重点研发计划(2018YFA0704704,2022YFB2701900);国家自然科学基金(62172410,62202460);中央高校基本科研业务费专项资金Foundation:National Key Research and Development Program of China(2018YFA0704704,2022YFB2701900);National Natural Science Foundation of China(62172410,62202460);the Fundamental Research Funds for the CentralUniversities of China收稿日期:2022-07-19定稿日期:2022-11-17686Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023differentials of reduced-round PICO,evaluates the security of PICO against differential cryptanalysisand provides more accurate results.Optimal differential trails are designed,and the probabilities fromround 1 to round 22 are presented.This paper shows that a 21-round differential distinguisher can befound with probability 260.75and a 22-round differential distinguisher can be found with probability262.39.A key-recovery attack on 26-round PICO can be formed with the time complexity 2101.11,data complexity 263and memory complexity 263.Finally,the security of PICO in the related-keysetting is studied and a weakness in its key schedule is found,resulting in the existence of related-keydistinguishers for any round with probability 1.Based on the distinguisher,a key-recovery attack onfull round PICO can be conducted in the related-key setting.The proposed model can be applied toother lightweight ciphers,especially block ciphers with larger block size or having many rounds.Key words:PICO;SP;differential cryptanalysis;SAT;key recovery attack;related-key attack1引言近年来,RFID、传感器网络、移动互联网等技术迅速发展.这些技术的应用组件是计算能力相对较弱的嵌入式处理器,计算可使用存储较小,同时能耗必须限制在某个范围之内,传统的密码算法无法适应于这种环境.为了应对资源受限的环境,出现了许多轻量级密码算法,比如 PRESENT1、PICCOLO2、TWINE3、SIMON4、SPECK4、SKINNY5、GIFT6、CRAFT7等.Feistel 结构和 SP 结构是目前分组密码算法设计使用最广泛的两种基本结构,如利用 Feistel 结构设计的密码算法 DES8,利用SPN 结构的密码算法 AES9、PRESENT1等.与 Feistel 结构相比,SP 结构具有更好的扩散性质,并且适合高速的硬件实现.PICO 算法10是 Bansod 等人设计的一种 SP 结构的迭代型轻量级密码算法,该算法的分组长度为 64 比特,密钥长度为 128 比特,加密轮数为 32 轮.与其他轻量级密码算法比如 PRESENT1相比,PICO 算法在软硬件实现方面有更好的表现.PICO 算法的硬件实现需要更少的等效门(gate equivalents,GEs),因此 PICO 算法的硬件实现占用更少的门面积以及更低的功耗;此外,PICO 算法的 S 盒和线性置换层都会使得其更好地抵抗差分、线性和其他攻击.在对称密码分析中,差分分析11和线性分析12是两种最主要的分析技术.在差分分析或者线性分析中,攻击者需要寻找一条最优的差分(线性)路径，这条路径有利于实现有效的(复杂度优于穷举攻击)差分(线性)攻击.无论对攻击者还是密码设计者来说,研究密码算法抵抗差分(线性)攻击的能力都是非常重要的.目前,自动化搜索技术是搜索分组密码算法的最优差分(线性)特征最有效的方法之一,这种方法降低了搜索差分(线性)特征的时间和人力成本.在过去的十年时间里,基于混合整数线性规划(MILP)的自动化搜索技术逐步发展,成为自动化密码分析技术中的一类重要方法.基于 MILP 的自动化搜索技术的关键点在于将搜索最优差分(线性)特征转化为 MILP 模型,可以使用 MILP 求解器(如Gurobi、SCIP 等)求解这个 MILP 模型,并将模型的解转化为一个最优差分(线性)特征.该方法最早由Mouha 等人13提出,他们使用该方法估计了分组密码算法的活跃 S 盒的数目;后来,Sun 等人14提出了贪婪算法等 MILP 建模方法,可以搜索轻量级分组密码算法的最优差分(线性)特征,并提高了搜索的效率.另一类自动化搜索技术基于布尔可满足性问题(Boolean satisfiability problem,SAT)或者可满足性模理论(satisfiability modula theories,SMT).基于 SAT 的搜索方法首先将目标问题转化为合取范式(conjunction normal form,CNF),使用 SAT 求解器(如 CaDiCaL15)判定这个合取范式是否可满足,如果可满足,求解器将会输出满足这个合取范式的变量赋值,这组赋值就对应了原目标问题的一个解.最初,基于 SAT/SMT 方法的技术由 Mouha 和 Preneel16提出,用于搜索 ARX 类算法的差分特征,后来该方法被用于搜索 SIMON 类密码算法的差分和线性特征17、ARX 结构的密码算法的线性迹18以及可分性19.本文的目标是对轻量级分组密码算法 PICO 进行差分分析.本文建立了搜索 PICO 密码算法差分特征和差分闭包的 SAT 模型,该模型也适用于其他轻量级密码算法的分析,比如 CRAFT、GIFT、PRESENT 等.与前人的工作20对比发现,本文所提 SAT 模型验证了他们对 PICO 算法的差分活跃王彩冰 等:对轻量级分组密码 PICO 算法的差分攻击687S 盒数目的分析结果;同时在最优差分概率方面,本文方法搜索到了更好的结果.马楚焱等人对 PICO 算法进行了零相关线性分析21,构造了 7 轮多维零相关线性区分器,对含白化密钥的 10 轮 PICO 算法实现了密钥恢复攻击.本文利用 21 轮的差分区分器,对 26 轮的 PICO 算法构造了密钥恢复攻击.当a=20,S=244时,攻击成功概率为 72.77%,数据复杂度为 264,时间复杂度为 2102.11,内存复杂度为264;当取 a=14,S=243时,成功概率为 61.11%,数据复杂度为 263,时间复杂度为 2101.11,内存复杂度为 263.最后研究了 PICO 算法抵抗相关密钥差分攻击的能力.本文发现 PICO 算法的密钥编排存在一个弱点,在相关密钥条件下,利用该弱点,可以构造 PICO 算法的任意轮相关密钥区分器并进行密钥恢复攻击.尽管 PICO 算法的设计者并没有在设计文档中提到 PICO 算法抵抗相关密钥攻击的能力,但我们认为这仍是 PICO 算法的一个严重缺陷.表1总结了 PICO 算法目前已有的公开分析结果.本文组织如下:第2节简要介绍了 PICO 算法和密码分析的一些预备知识;第3节介绍了搜索 SP 结构算法差分路径和差分闭包的自动化方法;第4节搜索了 PICO 算法的差分路径和差分闭包,并对 PICO算法构建了密钥恢复攻击以及相关密钥攻击;第5节总结.表 1 PICO 分析结果总结Table 1Summary of cryptanalytic results on PICO攻击类型轮数概率复杂度来源时间复杂度数据复杂度内存复杂度区分攻击差分攻击21263264264negl20零相关线性7-21差分攻击21260.75261.75261.75negl4.1差分攻击22262.39263.39263.39negl4.1相关密钥差分攻击任意轮1neglneglnegl4.3密钥恢复零相关线性10-268.7263.3242.321差分攻击26-2101.112632634.2差分攻击26-2102.112642644.2相关密钥差分攻击任意轮-2642502164.3 文献 20 搜索了 22 轮的最优差分路径概率为 263,没有计算闭包概率;表示成功概率为 61.11%;表示成功概率为 72.77%;negl 表示可忽略.2预备知识本节主要介绍所需要的预备知识.首先将简单介绍分组密码算法 PICO;然后介绍攻击所需要的差分分析的相关知识,包括差分特征以及差分闭包的定义、差分攻击的复杂度分析.最后简要介绍信噪比和成功概率的基本概念.2.1PICO 算法简介PICO 算法10是一个 SP 结构的轻量级分组密码,分组长度为 64 比特,密钥长度为 128 比特,加密轮数为 32 轮.PICO 算法的轮函数包括密钥加、S 盒置换、比特置换三个部分,图1展示了 PICO 算法的加密过程.PICO 算法的明文比特状态向量可以表示成如式(1)所示的 416 矩阵形式.将 64 比特的明文记为P=p0|p1|p63,那么第 1 行表示明文的前 16 比特 p0|p1|p15,第 4 行表示明文的最后 16比特 p48|p49|p63.P=p0p1p15p16p17p31p32p33p47p48p49p63.(1)688Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023图 1 PICO 算法的加密过程Figure 1 Encryption process of PICOPICO 算法的加密轮函数计算流程如下:(1)密钥加(AddRoundKey):将 64 比特的状态与 64 比特的子密钥异或.(2)S 盒置换(SubColumn):对状态矩阵的每一列并行进行 S 盒置换.S 盒的输入是状态矩阵的第 i列 Input(i)=pi|p16+i|p32+i|p48+i,输出为 Output(i)=qi|q16+i|q32+i|q48+i.PICO 算法的S 盒置换由下表给出(十六进制):表 2 PICO 算法的 S 盒Table 2S-box of PICO cipherx0123456789ABCDEFSx124D6FB8A5E39C70(3)比特置换(Permutation):将状态矩阵的第 i 行和 j 列元素 pi,j移到表3中对应的位置上.例如:将状态矩阵的第 0 行第 0 列元素移到新状态矩阵的第 0 行第 10 列上.表 3 PICO 算法的比特置换Table 3Permutation of PICO cipherij012345678910111213141500,101,51,122,62,123,03,110,13,30,152,90,23,122,21,81,413,80,61,11,152,43,50,122,141,143,40,110,41,72,32,83,1520,82,70,32,113,93,11,01,92,52,103,133,20,00,91,21,1033,103,70,71,31,130,142,152,02,10,53,142,130,133,61,61,11PICO 算法的加密轮数为 32 轮,每轮密钥加操作使用 1 个轮密钥加上 1 个白化密钥,共计 33 个长度为 64 比特的子密钥.每个 64 比特的子密钥是由 128 比特主密钥经过密钥编排算法产生.密钥编排流程如下.(1)密码算法的主密钥长度为 128 比特,记作 Key=k127k126k0.密钥状态可以分为 Ki和 Li两部分,其中 Ki是每轮密钥编排产生的子密钥.i=0 时,有:K0=k63k62k0,L0=k127k126k64.(2)生成子密钥 K1到 K32的密钥编排算法如下:Lj+1=Kj RCS(Lj,3)Lj,王彩冰 等:对轻量级分组密码 PICO 算法的差分攻击689Kj+1=Lj+1 LCS(Kj,7)j.其中,0 j 31,RCS(K,a)与 LCS(K,a)分别表示比特向量 K 右循环移位和左循环移位 a比特.2.2差分分析差分分析是针对分组密码算法最有力的攻击方法之一,最早由 Biham 和 Shamir 在对 DES 的分析中提出11.接下来介绍本文中使用的差分攻击的相关知识.分组密码使用密钥 K Fk2加密一个明文分组 M Fn2,得到密文分组 C Fn2,记作 C=EK(M).分组密码的解密和加密使用同样的密钥,是加密的逆变换,记作 M=DK(C).目前大多数分组密码算法都是迭代型分组密码,即加密函数是 r 个相似(或者相同)的轮函数 fi的复合,r 称为分组密码的轮数,记作EK(M)=fr fr1 f1().差分分析方法是一种选择明文攻击,其核心思想是寻找一个输入输出差分对(,),使得对任意满足=P1 P2的明文对(P1,P2),其对应的密文对(C1=EK(P1),C2=EK(P2)的差分 C1 C2以较高概率等于.对于一个随机置换 F:Fn2 Fn2,任意输入差分对应的输出差分是均匀分布的,即对于某个输入差分,得到任意输出差分的概率均为 2n.对于一个密码算法,如果找到一个概率远大于 2n的输入输出差分(,),那么可以将其与随机置换区分开.因此,在寻找分组密码的差分特征时,仅仅关心概率远远大于 2n的差分特征.定义 1 r 轮差分特征 C 是一个差分序列C=(C0f1 C1f2.fr Cr),其中 C0是明文对的异或值,Ci是第 i+1 轮输入差分也是第 i 轮的输出差分.定义 2 设 r 轮分组密码算法的明文对输入差分为 C0 Fn2,输出差分为 Cr Fn2,其差分概率为DP(C0EK Cr)=Pr(EK(X)EK(X C0)=Cr),其中 X 是服从 Fn2上均匀分布的随机变量.定义 3 如果一个密码算法是一个马尔可夫密码22并且 r 轮的子密钥是相互独立的,一个 r 轮差分特征的概率近似等于 r 个一轮差分特征的概率的乘积,即DP(C)ri=1Pr(Ci1fiCi).注意到,当一个攻击者构建和利用差分区分器时,一般不会关心差分路径的中间差分值,仅仅关心输入输出差分以及该差分的概率.但是,依据定义2,差分概率的精确计算需要遍历所有的明文 X Fn2.由于计算资源受限,这种计算方法是不可行的.因此攻击者为了获得一个高概率的差分特征,往往先搜索一个最优的 r 轮差分特征,依据该差分特征的输入输出差分,搜索所有拥有相同输入输出差分的差分特征,用这些 r 轮差分特征概率的和来估计差分特征 C0EK Cr的概率,即Pr(C0E Cr)C1,C2,Cr1Pr(C0f1C1f2frCr).为方便自动化搜索建模和表示,本文将差分路径的权重定义为 W=log2(DP(C).定义 4 除了利用高概率差分进行区分攻击之外,还可以利用差分攻击实现密钥恢复攻击.密钥恢复攻击一般分为以下三个阶段:数据收集阶段、密钥恢复阶段和穷举阶段.690Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023(1)数据收集阶段:攻击者在得到一个 r 轮的高概率(Pr)差分(区分器)(C0,Cr)之后,将根据输入、输出差分决定在区分器前后扩展 rb,rf轮,前后扩展的轮数所涉及的密钥记为 kb和 kf,密钥恢复攻击的目的就是恢复 kb和 kf的密钥比特.同时依据区分器的输入输出差分,可以推导得到明文、密文差分值(in,out).密钥恢复攻击所需要的数据量由差分区分器的概率 Pr 以及攻击者需要的正确对(即满足区分器输入输出差分的数据对)数量 d 决定,假设攻击者需要的正确对(P,C)和(P,C)数量为 d,那么攻击所需的数据量为 N=dPr.需要注意到,并不需要保存所有的 N 个数据对,因为只有密文差分 C C=out时,这个数据对才有可能是正确对.利用密文差分筛选后剩余的数据对数量记为 NF.(2)密钥恢复阶段:利用上步收集的数据对进行密钥恢复.假设区分器对应的数据状态对为(Pb,Cf),(Pb,Cf),即:Pb=Ekb(P),Pb=Ekb(P)和 Cf=Dkf(C),Cf=Dkf(C),其中 Ekb和 Dkf分别表示使用部分密钥 kb和 kf进行 rb和 rf轮部分加解密.攻击者通过猜测 kb和 kf,计算Pb,Pb以及 Cf,Cf,如果 Pb Pb=C0并且 Cf Cf=Cr,则给猜测的密钥 kb,kf对应的计数器加 1.在对所有数据对和猜测密钥进行上述操作后,选取数值最大的一个或几个计数器对应的密钥作为候选密钥.(3)穷举阶段:将候选密钥与剩余的未猜测的密钥比特结合,穷举剩余密钥,最终恢复出全部的正确密钥.定义 5(差分分析的复杂度)一般关注的复杂度包括时间复杂度 T、数据复杂度 D、内存复杂度 M.(1)时间复杂度:时间复杂度一般由所猜测的密钥比特数量以及明密文数据对的数量 NF决定.对所有保留的数据对(P,C)和(P,C),使用每一个猜测的密钥进行 rb轮加密和 rf轮解密,因此时间复杂度为 T=NF 2kb+kf.(2)数据复杂度:数据复杂度一般指攻击者询问加密(解密)算法的数据量,一般由区分器的概率和攻击者需要的正确对数量决定.(3)内存复杂度:内存复杂度一般指的是在攻击过程中需要的计算机内存的大小.此外,攻击者还会关注密钥恢复的成功概率,一个成功的差分攻击需要满足以下两个条件23:首先,差分区分器至少存在一个正确对满足输入输出差分,否则无法与随机的置换进行区分;其次,在密钥恢复步骤中,正确密钥的计数器与其他密钥计数器的比值较高,Biham 和 Shamir 观察到该数量比与差分攻击成功概率之间存在较强的关系11.差分攻击是一种统计攻击方法,统计攻击中定义了两种差错概率:“弃真”概率和“取伪”概率.“弃真”概率:在猜测的密钥是正确的情况下,攻击者认为所猜测的密钥是错误的事件发生的概率,用 表示;“取伪”概率:在猜测的密钥是错误的情况下,攻击者认为所猜测的密钥是正确的事件发生的概率,用 表示.因此,统计攻击的成功概率为 PS=1 .沿用之前的符号,差分特征的概率记为 Pr,=PrNF表示期望得到的正确对的数目.此外,Pw表示在给定差分的情况下,密钥被随机数据对建议的平均概率.为了计算成功概率,首先引入信噪比的定义.定义 6(信噪比11)如果一个明密文差分对(P,P),(C,C)满足区分器的输入输出差分,即Ekb(P)Ekb(P)=,Dkf(C)Dkf(C)=,其中(,)是区分器的输入输出差分,称这个明密文对是一组正确对,否则称为错误对.显然正确对必定给正确密钥投票,会给错误密钥随机投票;错误对给任意密钥随机投票.称正确密钥的得票数与错误密钥的平均得票数的比值为信噪比,记作 S/N 或 SN.根据信噪比的定义,可以得到 SN=PrPw.在密钥恢复阶段,正确密钥对应的计数器的值遵循二项式分布(NF,Pr);另一方面,假设在错误密钥的情况下,数据对满足差分的概率为 Pw,因此,错误密钥对应的计数器的值遵循二项式分布(NF,Pw).定义正确密钥计数器的值排在全部候选密钥计数器的前 2a为攻击成功,称 a 为攻击的优势.根据文献 23 的定理,可以得到成功概率 PS与 NF以及 SN之间的关系PS=SN1(12a)SN+1(x)dx.(2)其中,(x)表示标准正态分布的概率密度函数,表示标准正态分布的概率累积函数.王彩冰 等:对轻量级分组密码 PICO 算法的差分攻击6913基于 SAT 问题自动化搜索 PICO 差分特征与差分闭包布尔可满足性问题(SAT)是指判定给定的布尔表达式是否可满足的问题,即是否存在一组变量赋值,使得某个合取范式形式的布尔表达式为真.如果存在这样的一组赋值,说明该 SAT 问题是可满足的.SAT 问题属于判定性问题,也是第一个已知的 NP 完全问题.现代的 SAT 问题求解器大多使用了基于CDCL(conflict-driven clause-learning)24,25思想的求解算法.尽管 SAT 问题是一个 NP 完全问题,但是许多 SAT 实例,包括本文中基于 SAT 问题的模型,都可以在有限的时间内解决.本文中使用的求解器CaDiCaL15同样基于 CDCL 算法.我们注意到,文献 26 中,在搜索差分和线性路径方面,CaDiCaL求解器比 Cryptominisat 求解器速度更快,因此本文选择使用 CaDiCaL 求解器.目前,所有的 SAT 求解器将合取范式(CNF)形式的布尔表达式作为输入.合取范式形式的布尔表达式是由一个或多个子句以合取()的方式连接,而一个子句是由一个或多个布尔变量以析取()的方式组成.基于 SAT 方法的自动化密码分析方法的主要思想是,将搜索最优差分(线性)路径的问题转化为SAT 问题,用合取范式对差分(线性)路径的可行域进行刻画,利用 SAT 求解器进行求解,如果得到一个解使得 SAT 问题是可满足的,那么这个解就对应了一条差分(线性)路径.接下来将介绍如何将搜索轻量级分组密码算法的差分特征、差分闭包转化为 SAT 问题,用 CNF 形式的布尔表达式刻画可行域,通过求解 SAT 模型来寻找满足条件的差分路径.首先介绍轻量级分组密码常见的线性操作和非线性操作的建模方法.3.1线性操作模型轻量级分组密码算法一般采用简单的异或和分支操作构造线性层,因此,本文考虑这两种基本的比特级运算.模型 1(异或操作)对于 n 比特的异或操作,使用 和 表示输入差分,表示输出差分,即:=.当且仅当、和 的值满足以下约束,差分传播是合法的.i i i=1i i i=1i i i=1i i i=10 i n 1.(3)模型 2(分支操作)对于 n 比特的分支操作,使用变量 表示输入差分,和 表示输出差分,即:=.当且仅当、和 的值满足以下约束,差分传播是合法的.i i=1i i=1i i=1i i=10 i n 1.(4)3.2非线性操作模型轻量级对称密码算法中常用的非线性操作是 S 盒,本文采用文献 27 中构建 S 盒差分模型的方法.考虑对 S 盒的差分分布表 DDT 构建 SAT 模型,即用合取范式去刻画 S 盒的可行区域.一般来说,对于使用 S 盒的密码算法,在用自动化工具搜索其差分路径时,有两个分析目标:第一个目标是评估密码算法的最小活跃 S 盒个数,即搜索具有最少活跃 S 盒的差分路径;第二个目标是评估密码算法的最优差分概率,即搜索具有最大概率的差分特征.首先,考虑评估活跃 S 盒数量的 SAT 模型.模型 3(活跃 S 盒)使用向量(0,1,n1)和(0,1,n1)表示 n 比特的 S 盒的输入和输出差分,使用变量 表示该 S 盒是否活跃,即如果差分分布表中(0,1,n1)(0,1,n1)是可行的差分传播且概率小于 1,那么 =1;如果差分分布表中(0,1,n1)(0,1,n1)的概率为 1,那么 =0.不满足这两种情况的(0,1,n1,0,1,n1,)构成的集合称为 S 盒的不可行域.692Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023令 f(,)是一个(2n+1)比特的布尔函数,定义如下:f(,)=0,如果(,)位于不可行域中1,否则.(5)为了刻画 S 盒的可能的差分传播,只需要生成 f 的合取范式.可以使用基于 Espresso 算法的 LogicFriday 软件将 f 的真值表转化为合取范式的形式.在模型 3 中使用一个额外比特 标记 S 盒是否活跃,在概率模型中采用类似的思想,使用多个变量对 S 盒的差分概率进行编码.模型 4(概率)使用变量(0,1,n1)和(0,1,n1)表示 n 比特的 S 盒的输入和输出差分.以 PICO 算法为例,PICO 差分分布表(DDT)的元素仅有下面四种取值:0,2,4,16,对应的差分概率为 0,23,22,1.引入变量 p、q、r 将概率的权重进行编码,在此编码方式下,PICO 算法的 S 盒的概率权重 weight=p+q+r.用 Entry(|)表示输入差分 、输出差分为 的 DDT 的值.令 f(,p,q,r)是一个(2n+3)比特的布尔函数,定义如下:当 Entry(|)=0 时,f(,p,q,r)=0;当 Entry(|)=2 时,如果(p,q,r)=(1,1,1),那么 f(,p,q,r)=1 否则 f(,p,q,r)=0;当 Entry(|)=4 时,如果(p,q,r)=(1,1,0),那么 f(,p,q,r)=1,否则 f(,p,q,r)=0;当 Entry(|)=16 时,如果(p,q,r)=(0,0,0),那么 f(,p,q,r)=1,否则 f(,p,q,r)=0.3.3目标函数的刻画模型 5(PICO 算法差分特征目标函数)本文考虑自动化搜索 r 轮 PICO 算法差分特征.用 p(i,j)、q(i,j)、r(i,j)表示第 i 轮中的第 j 个 S 盒的使用的权重变量,这里 0 i r 1,0 j 15.那么,r轮 PICO 算法差分特征的概率权重表示为r1i=015j=0(p(i,j)+q(i,j)+r(i,j).如果目标定为求解权重不超过 的所有路线,那么目标函数应满足r1i=015j=0(p(i,j)+q(i,j)+r(i,j).一般来说,将 SAT 问题中形如r1i=015j=0(p(i,j)+q(i,j)+r(i,j)的约束称为布尔基数约束28.依据文献 18,29 中的方法,可以利用序列化编码的方法将布尔基数约束转化为合取范式.为了解决这一问题,需要借助辅助变量ui,j(0 i 3 16 r,0 j 1).下面分为两种情况进行讨论:=0 和 0.当 =0 时,布尔基数约束等价于下面的布尔表达式:pi,j=1,qi,j=1,ri,j=1,0 i 3 16 r,0 j 1.当 0 时,根据文献 27 中的方法,将引入(3 16 r)1)个辅助变量 ui,j(0 i 316r,0 j (1),如果r1i=015j=0(p(i,j)+q(i,j)+r(i,j),下面的约束(6)将不满足.为了表示更加简洁,将使用r1i=015j=0(p(i,j)+q(i,j)+r(i,j)=316(r1)i=0 x(i).x0 u0,0=1,u0,j=1,xi ui,0=1,ui1,0 ui,0=1,xi ui1,j1 ui,j=1,ui1,j ui,j=1,xi ui1,1=1,x(r1)161 u(r1)162,1=1.(6)王彩冰 等:对轻量级分组密码 PICO 算法的差分攻击693其中,1 i 3 16 (r 1),1 j 1.3.4差分闭包的 SAT 建模在之前的 3 个小节中,基于 SAT 方法,建立了搜索轻量级分组密码最优差分路径的自动化模型.利用这个模型,可以搜索到一条 r 轮最优差分特征,这条特征明确了每一轮的差分值.然而在密钥恢复攻击中,仅需要明确差分区分器的输入和输出差分,不关心中间轮数的差分值.因此,本小节引入差分闭包的概念,多条具有相同输入输出差分的 r 轮差分特征组成了一个差分闭包,差分闭包的概率则是所有 r 轮差分特征概率的和.同时,一般认为一个差分闭包的概率由一条最优的差分特征的概率主导23.因此,本小节给出了一个自动化搜索轻量级分组密码算法差分闭包的策略.设 =(0,1,n1)和 =(0,1,n1)为差分区分器的输入差分和输出差分.根据前面对 PICO 算法基本操作的约束,SAT 模型中 r 轮的差分特征的变量为 C=(C0,C1,Cr),Ci=(ci,0,ci,1,ci,n1),在原有的差分特征的 SAT 模型中添加下面的约束即可固定输入和输出差分,其中0 i n 1.i c0,i=0,i cr,i=0.(7)同时,在固定输入输出差分的基础上,原有的 SAT 问题中加入下面的约束可以排除已经搜到的解,其中i,j,0 i r,0 j n 1 是已经搜索到的一条 r 轮差分特征,算法1中用 Exclude()函数表示.r1i=1(n1j=0(i,j ci,j)=1.(8)算法 1 自动化搜索 PICO 算法差分闭包Input:轮数 r;概率最高的 r 轮差分特征(num 个)的概率权重 weight;输入输出差分(in,out)Output:num 个 r 轮差分闭包的概率列表 L1for 0 i num do2for weight w weight+4 do3Fixed(in,out)4Levery=/Levery 列表存储该闭包下每个差分路径的概率5sat,solution=model.solve()6while sat model is feasible do7Exclude(solution)8sat,solution=model.solve()9Pr=根据 solution 计算差分路径的概率10Levery.append(Pr)11end12for pr in Levery do13PrHull=PrHull+Pr/PrHull 表示差分闭包的概率14end15L.append(PrHull)16end17end18return L不断重复上述过程,直到 SAT 求解器返回该问题是不可满足的,此时求出了在该闭包中的所有 r 轮差分路径.但是,如果不考虑单条差分路径的概率,一个差分闭包中包含了大量的差分路径,搜索闭包中所有的差分路径需要花费大量的时间.注意到低概率的差分路径对差分闭包概率的影响很小,因此,考虑将目标函数固定在一个范围之内,仅搜索差分闭包中概率较高的差分路径.假设我们搜索到 r 轮 PICO 最优的差分特征的概率为 Pr,对应的概率权重记为 Weight.按照如下策略搜索差分闭包:(1)搜索概率为 Pr 的所有 r 轮差分特征,将搜索到的所有差分特征按照输入输出差分进行分组,把拥有相同输入输出差分的差分特征放在一个组内,以输入输出差分为每一分组的索引,每个分组694Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023对应了一个差分闭包;(2)按照每一个分组的索引,固定输入差分和输出差分,将概率权重约束在(Weight,Weight+4)范围内,建立差分闭包的 SAT 模型,搜索在该概率范围内的所有