动态聚集效应及其在SIMON算法上的应用.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(4):737751密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]动态聚集效应及其在 SIMON 算法上的应用*牛开路1,2,晁佳豪3,王 薇1,2,41.山东大学 网络空间安全学院,青岛 2662372.山东大学 密码技术与信息安全教育部重点实验室,济南 2501003.华东师范大学 软件学院,上海 2000624.泉城实验室,济南 250103通信作者:王薇,E-mail:摘要:SIMON 算法是美国国家安全局(NSA)在 2013 年发布的轻量级分组密码算法,自提出以来就受到密码学界的广泛关注.本文通过对 SIMON 的差分/线性掩码传播进行深入分析,根据每轮的输入差分/掩码空间来动态调整窗口内活跃比特的位置,使其尽量位于每轮的输出最密集的 w 个比特处,同时动态调整窗口外部的比特取值,将静态窗口转化为动态窗口,使其包含更多的差分/线性路径,得到具有更高概率的差分/线性壳.分别以 SIMON64、SIMON96 和 SIMON128 为例,进行了差分和线性壳的搜索.在差分分析方面,将已有的 SIMON128 的区分器提高 3 轮,得到 44 轮的高概率差分;在线性分析方面,将已有的 SIMON64 和 SIMON96 的区分器提高 1 轮,分别得到 24 和 34 轮的线性壳,将 SIMON128 提高3 轮,得到 45 轮的线性壳.这是目前对 SIMON 算法搜索差分/线性区分器的最优结果.关键词:分组密码;SIMON;差分分析;线性分析;聚集效应中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000623中文引用格式:牛开路,晁佳豪,王薇.动态聚集效应及其在 SIMON 算法上的应用J.密码学报,2023,10(4):737751.DOI:10.13868/ki.jcr.000623英文引用格式:NIU K L,CHAO J H,WANG W.Dynamic clustering effect and applications on SIMONJ.Journal of Cryptologic Research,2023,10(4):737751.DOI:10.13868/ki.jcr.000623Dynamic Clustering Effect and Applications on SIMONNIU Kai-Lu1,2,CHAO Jia-Hao3,WANG Wei1,2,41.School of Cyber Science and Technology,Shandong University,Qingdao 266237,China2.Key Laboratory of Cryptologic Technology and Information Security,Ministry of Education,ShandongUniversity,Jinan 250100,China3.School of Software,East China Normal University,Shanghai 200062,China4.Quan Cheng Laboratory,Jinan 250103,ChinaCorresponding author:WANG Wei,E-mail:Abstract:SIMON is a lightweight block cipher published by the National Security Agency(NSA)in 2013.Since it was proposed,it has received extensive attention from the cryptography community.*基金项目:国家重点研发计划(2018YFA0704702,2022YFB2701700);山东省自然科学基金面上项目(ZR2020MF053)Foundation:National Key Research and Development Program of China(2018YFA0704702,2022YFB2701700);Shandong Provincial Natural Science Foundation(ZR2020MF053)收稿日期:2022-06-04定稿日期:2022-10-25738Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023This paper analyzes the difference/linear mask propagation of SIMON,adjusts the position of theactive bits in the window dynamically according to the input difference/mask space of each round,sothat it can be located at the densest w-bit of the output of each round instead of the fixed window.Moreover,the value of the bits outside the window is adjusted dynamically.By doing this,the staticwindow can be converted into is a dynamic one,so that it involves more differential/linear trails,andresults in differentials/linear hulls with higher probability.SIMON64,SIMON96 and SIMON128 aretaken as examples,their differentials and linear hulls are found using the improved algorithms designedin this paper.With respect to differentials,a 44-round distinguisher of SIMON128 is obtained,whichimproves the published results by 3 rounds.With respect to linear hulls,the existing distinguishers ofSIMON64 and SIMON96 are improved by 1 round,and achieve 24 and 34 rounds,respectively,and a45-round linear hull for SIMON128 is obtained,which is improved by 3 rounds.Key words:block cipher;SIMON;differential cryptanalysis;linear cryptanalysis;clustering effect1引言为了在资源受限的物联网设备如 RFID 标签、智能卡等部署密码算法,以保证安全通信等需求,在过去十几年里,已经有许多轻量级密码被提出,如 HIGHT1、DESL2、PRESENT3、LBlock4、PRINCE5、TWINE6、SKINNY7等2013 年美国国家安全局(NSA)发布了两个新的轻量级分组密码族 SIMON 和 SPECK8,它们具有优越的软硬件性能,有望纳入 ISO 标准,其安全性引起了密码学界的广泛关注.到目前为止,已经有大量相关研究工作918,结果表明,差分分析和线性分析仍然是对其最有效的攻击方法.此外,这些工作还表明大量的差分和线性路径具有很强的聚集效应,即存在许多差分或线性掩码在头尾相同的路径.高概率的差分或线性区分器的构造即是将这些头尾相同的路径累积在一起的结果.将分组密码和随机置换进行区分,是开展密钥恢复攻击的关键.同时,分组密码常作为伪随机置换,用于构造杂凑函数、消息认证码和认证加密算法等,因此分组密码区分攻击的研究具有重要的理论意义和应用价值.Leurent 等人19在 2021 年的亚密会(AsiaCrypt)上提出以一种更系统的方式来探索 SIMON 和SIMECK 的聚集效应(clustering effect).他们考虑的是一类活跃比特仅位于一个 w 位的固定窗口中的路径,并通过结合这个类中所有具有相同输入/输出的路径来计算一个差分或线性壳的概率,改进了之前的区分器,同时他们利用这些区分器,提出了目前对 SIMON 和 SIMECK 最好的密钥恢复攻击.SIMON 和SIMECK 的轮函数结构相同,区别仅在于 SIMON 的旋转常量是(8,1,2),而 SIMECK 的是(5,0,1).由于 SIMON 的轮函数中循环移位的常数比 SIMECK 更大,扩散相对更快,使得固定窗口内包含的路径更少,导致他们在 SIMON 上得到区分器的概率下界不像 SIMECK 那样紧密.如文献 19 中所说,还需要进一步的工作去捕获 SIMON 的更好的聚集效应.本文主要基于文献 19 的工作,提出一种新的动态窗口模型1,能够根据每轮的输入空间来动态调整窗口内活跃比特的位置,使其尽量位于每轮输出最密集的 w 个活跃比特处,同时也能动态调整窗口外比特的取值,使其尽量吻合更多的输出.这样使得该窗口对应的空间能够涵盖更多具有相同输入/输出的路径,通过结合这些路径能够找到具有更高概率下界和更长轮数的差分或线性区分器.表1将本文结果与现有最佳结果进行了比较.2预备知识本节首先给出符号定义,然后对 SIMON 算法、差分分析和线性分析进行简要介绍.1更多的实验数据细节及实验代码请见https:/ 等:动态聚集效应及其在 SIMON 算法上的应用739表 1 SIMON 的差分和线性区分器结果比较Table 1Comparison of differential and linear distinguishers of SIMON版本轮数概率(log2)来源类型SIMON642360.8415线性壳2462.4本文线性壳SIMON963393.5719线性壳3493.99本文线性壳SIMON12841123.7414差分44126.66本文差分42125.0719线性壳45124.95本文线性壳注:线性壳的概率为线性概率 LP.2.1符号说明本文所使用的符号定义如表2所示.表 2 符号定义Table 2Notations符号释义符号释义Sd(x)x 循环左移 d 位i第 i 轮的线性掩码Li,Ri第 i 轮输入状态的左、右分支x yx 和 y 的点乘,x y=n1i=0 xiyiki第 i 轮的子密钥x ix 左移 i 位r轮数xyx 和 y 按位与i第 i 轮的差分xyx 和 y 按位或2.2SIMON 算法简介轻量级分组密码算法 SIMON 基于 Feistel 结构,分组长度为 2n-bit,n 是字大小,可取 16、24、32、48 和 64-bit,密钥长度 k 可取 2n、3n 和 4n-bit,其版本记为 SIMON2n,对于不同版本的具体参数见表3.表 3 SIMON 不同版本的参数Table 3Parameters for different versions of SIMON分组长度 2n-bit密钥长度 k-bit迭代轮数 r3264324872,96366496,12842,449696,14452,54128128,192,25668,69,72SIMON 算法的轮函数简单,只包括与运算()、异或运算()和移位运算(Sd),其中移位运算的旋转常量(a,b,c)=(8,1,2).轮函数的具体表示为:f(x)=S8(x)S1(x)S2(x).740Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023对于输入(Li1,Ri1),经过一轮加密后得到输出为:Li=f(Li1)Ri1 ki1,Ri=Li1.轮函数的结构示意图如图1所示.本文工作不考虑密钥 k 的参与,故省略描述密钥生成算法,更多细节请参考文献 8.图 1 SIMON 的轮函数Figure 1 Round function of SIMON2.3差分分析原理差分分析是由 Biham 和 Shamir20于 1990 年提出的一种选择明文攻击,是分析迭代型分组密码安全性的重要手段.其主要目标是寻找跨越 r 轮的高概率差分(r ),即满足输入差分 =P1 P2的明文对(P1,P2),经过 r 轮加密后得到的密文对(C1,C2)满足输出差分=C1 C2的概率 Pr 22n.具体来说,一条 r 轮差分特征由一系列一轮差分构成,记为:Q=(0 1 2 r1 r).用 R 来表示一个密码算法的轮函数,那么第 i 轮的差分转移(transition)概率为:Pri1 i=PrxR(x)R(x i1)=i.其中,x F2n2.在独立性假设的前提下,一条 r 轮差分特征的概率可以表示为:PrQ=ri=1Pri1 i.通过收集所有输入差分和输出差分相同的差分特征,可以将一条 r 轮差分的概率表示为:Prr =1r1ri=1Pri1 i.(1)可以用一个差分转移矩阵 D 来存储所有的转移概率 Pri1 i,迭代 r 轮得到 Dr,它直接给出了所有的 r 轮差分的概率.牛开路 等:动态聚集效应及其在 SIMON 算法上的应用7412.4线性分析原理线性分析是 Matsui21于 1993 年提出的一种已知明文攻击,与差分分析一样,已成为分析迭代型分组密码安全性的重要手段.借助线性概率22,可将线性分析与差分分析对应起来.其主要目标是寻找跨越r 轮的高线性概率线性壳(r ).即对于输入掩码 和输出掩码,LP(r )22n.具体来说,一条 r 轮线性路径由一系列线性掩码构成,记为:G=(0 1 2 r1 r).同样用 R 来表示一个密码算法的轮函数,那么第 i 轮的线性相关度定义为:c(i1 i)=2Prxi1 x=i R(x)1.其中,x F2n2.在独立性假设的前提下,一条 r 轮线性路径的线性概率可以表示为:LP(G)=ri=1c2(i1 i).1994 年,Nyberg23提出了线性壳的概念,将一组具有相同输入、输出掩码的线性路径同时考虑,得到一条 r 轮线性壳,相应的线性概率为:LP(r )=12r1ri=1c2(i1 i).与差分类似,可以用一个线性转移矩阵 C 来存储所有的 c2(i1 i),迭代 r 轮得到 Cr,它直接给出了所有的 r 轮线性壳的线性概率.3静态窗口的聚集效应本节主要介绍 Klbl 等人24在 2015 年美密会上给出的 SIMON-like 轮函数 f 的差分或线性转移概率的计算公式,及 Leurent 等人19在 2021 年亚密会上提出的静态窗口聚集效应的工作原理.3.1SIMON-like 轮函数的差分/线性转移概率Klbl 等人24在 2015 年的美密会上发表了对 SIMON-like 密码轮函数 f 的观察.对于给定的输入差分或线性掩码 和经过一轮 f 后的输出差分或线性掩码,他们给出了能精确计算经过轮函数 f 的差分或线性转移概率的公式.这里参考文献 19 的刻画方式:对于差分转移概率,有Prxf(x)f(x )=2 dim(U),if U0,else.其中,x Fn2,U是输入差分 对应的转移空间:U=Img(x 7 f(x)f(x )f()f().(2)对于 Feistel 结构的轮函数,一轮的差分转移概率为:Pr(L,R)(L,R)=2 dim(UL),if L=Rand R L UL0,else.742Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023对于线性转移概率,有c2(x ,f(x)=2 dim(V),if V0,else.其中,x Fn2,V是输出掩码 对应的转移空间:V=Img(x 7 Sa(Sba(x)Sab(x)Sc().对于 Feistel 结构的轮函数,一轮的线性转移概率为:c2(L,R)(L,R)=2 dim(VR),if R=Land L R VR0,else.以差分为例,要得到一轮的差分转移概率及相应的 f 函数的输出差分,关键是确定 dim(U),即U.由等式(2)可见,U的计算分为两步:(1)确定像空间 Img(x 7 f(x)f(x )f().对给定的,利用高斯消元法,计算构成该空间的一组 n-bit 的基向量 A,根据 A张成向量空间A2,即为像空间;(2)将向量空间A中的每一个元素与常数 c=f()异或得到转移空间 U.从而,在实际代码中,要访问所有输出差分 U,基于 Leurent 等人给出的代码25,给出算法1如下(访问所有 V可类似实现).算法 1 访问所有的 UInput:差分 Data:X 为 n 维数组,存储 n-bit 向量.1c f();/f 为轮函数2for i=0 to n 1 do3Xi=f(1 i)f(1 i)f();4end5X Gauss(X);/对 X 数组进行高斯消元6for i=0 to n 1 do7if Xi!=0 then8A.add(Xi);/A存储基向量9end10end11 c;12for i=1 to 2len(A)1 do13z=_builtin_ctz(i);/_builtin_ctz(i)返回 i 的二进制下末尾的 0 的个数14=Az;/相当于枚举A中的一个元素与 c异或得到一个新的 15end16从第 11 步到第 15 步中,共得到 2len(A)个 构成转移空间 U.3.2静态窗口模型根据3.1节中对 SIMON-like 密码轮函数的分析,我们能更高效地计算一轮的差分转移矩阵 D 和线性转移矩阵 C,从而得到 r 轮的概率转移情况但是,若要存储 SIMON-like 轮函数在整个分组空间上的转移矩阵,则需要 O(22n)量级的内存,当 n 32 时,已经超出了我们现有的计算能力.要想降低内存,一个直接的思路,就是限制矩阵的输入输出规模,即输入差分/线性掩码及输出差分/线性掩码的取值空间.文献 19 中仅考虑一类只可能在每个字的低 w 比特构成的固定窗口内活跃的路径,其中 w n.以2将基向量组 A张成向量空间,指的是将 A中的所有基向量进行线性组合,共有 2len(A)1 种非零组合,记为A.牛开路 等:动态聚集效应及其在 SIMON 算法上的应用743差分为例,他们定义 w为窗口内差分的向量空间,2w为考虑一轮的差分转移时的向量空间 w w,根据等式(1),对于给定的 0,r,可以通过对所有中间状态在 2w内的特征求和,来计算差分 0r r的概率,即Pr0r r=12r12wri=1Pri1 i.这样,仅需要 O(22w)量级的内存来存储差分转移矩阵,其中,w 的大小可根据实际资源情况确定另外,为了降低计算复杂度及有利于进行密钥恢复攻击,他们只考虑低汉明重量的固定输入差分 0,如(0,1).由于 SIMON 和 SIMECK 具有相对较低的扩散性,他们在差分概率(或线性壳的线性概率)上得到了更紧密的下界.但是相比于 SIMECK,SIMON 轮函数中循环移位的常数更大,扩散更快,需要更大的活跃比特窗口,且得到的转移矩阵更稀疏,因此在 SIMON 上得到的下界不像 SIMECK 那样紧密.如文献 19 中所述,需要进一步的工作去捕获 SIMON 的更完善的聚集效应.4动态窗口的聚集效应本文模型对差分分析和线性分析同样适用,为方便理解,本节主要以差分为例进行介绍.根据3.2节的分析可得,把活跃比特窗口固定在每个字的最低 w 比特对输出差分的取值情况限制太强,从而过滤掉了许多高概率的差分特征,因此,对 SIMON 的聚集效应的分析结果并不显著.从这一点出发,如果能够大致判断出差分传播路径在每一轮的活跃比特比较密集的位置集合,并以此为依据,对每一轮的活跃比特窗口进行动态选取,使得尽可能多的差分路径都在窗口内活跃,应该能获得更好的结果.同时,差分的传播概率与整个分组的差分值相关,窗口外的比特的取值也会影响差分路径的概率,如果可以动态调整窗口外差分比特的取值,也有助于改进 SIMON 的差分区分器的概率.根据这两点思路,本节给出改进的动态窗口模型和相应的算法.4.1动态窗口模型从以上两点出发,本节提出一种动态窗口模型 W,由两部分完成动态窗口的位置选取和参数设置.以下仍用差分进行说明.先确定一个长度为 n-bit 的比特串 BS 作为初始向量,然后用一个最大长度为 w(w n)的数组 AC来确定窗口内活跃比特的位置.对 BS 从高到低进行编号,0 对应最右侧的比特,数组 AC 的每一项为活跃比特在该比特串中的编号,即 0 ACi n1.遍历数组 AC 中的比特在 BS 中对应位置处的所有取值情况,就得到了动态窗口 W 的整个差分向量空间 w举例说明如下:若 BS=10110,AC=0,2,则 w=10010,10011,10110,10111.而所谓动态,是指每轮的 BS 和 AC 根据差分传播路径的密集程度动态调整.当输入差分固定时,与之对应的所有 r 轮差分特征也随之确定,我们要做的就是尽可能地将其中高概率的差分特征聚集起来.因此可以根据已得到的迭代了 i1 轮的差分转移矩阵,结合第 i1 轮的输入差分的向量空间,预先计算其经过第 i 轮轮函数 f 后的输出差分活跃比特较为密集的位置,得到第 i 轮的动态窗口 W.同时,这个窗口也作为第 i+1 轮的输入窗口,决定了其输入差分的向量空间.如此迭代 r 轮就可以确定每轮的动态窗口及差分转移矩阵(最开始的输入差分窗口由固定的输入差分直接确定).和3.2节类似,我们在动态窗口对应的向量空间内通过将每轮差分转移矩阵相乘的方式来求得 r 轮差分的概率.4.2动态窗口选取记(W(i1)L,W(i1)R)为第 i1 轮的输入差分对应的左右两个字的动态窗口,i1l和 i1r分别为其对应的差分向量空间.则输入窗口(W(i1)L,W(i1)R)经过一轮加密之后对应的输出窗口为(W(i)L,W(i)R),根据 SIMON 轮函数的结构,有W(i)R=W(i1)L,ir=i1l.744Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023从而,仅需动态确定 W(i)L.如前所述,可以根据输入差分的整个向量空间 i1l i1r来预判其经过轮函数 f 后的输出差分活跃比特的密集区域,并把窗口选取在该位置,来得到窗口 W(i)L.下面进一步分析该过程.令输入差分的左右两个字为(,),那么经过一轮 f 后的输出差分为(,),其中 U.具体的差分转移情况如图2所示.图 2 一轮加密的差分转移情况Figure 2 Differential propagation of 1-round encryption根据3.1节的式(2),记 c=f(),则 U可由一组基向量 A和常数 c计算得到,令 A,那么对于所有的 U,有 =c,即(,)1round (,)=(c,).本文的目标是要让窗口 W(i)L尽可能包含高概率输出差分的活跃比特密集的位置,也就是使得其对应的差分向量空间 il包含尽可能多的正确输出差分 c.其中,对给定的 和,c 为定值,而 与基向量组 A相关,取值不确定,即为活跃比特.基于这一发现,本文的动态窗口 W(i)L由“确定的”BS和“活跃的”AC 来共同构成向量空间 il.确定窗口 W(i)L的 BS.对整个输入差分空间对应的输出表达式中的确定值 c 进行统计,确定输出窗口 W(i)L的 BS.具体地,遍历输入差分的两个字 i1l,i1r,得到 c 的所有可能取值.为降低内存占用,我们不记录每种可能的具体取值,而是对每种可能值的每一比特进行相应的权重累积(以差分转移矩阵 Di1,处的概率值为权重,相当于尽量保留高概率的路径),最后根据每个比特对应的权重值来决定 BS 中相应位置的比特为 1 或 0,详细过程如算法2所示.确定窗口 W(i)L的 AC.分两种情况.(1)由算法2确定的窗口 W(i)L的 BS 是通过对所有的 c 进行加权统计得来的,这意味着并不是所有的 c 都等于 BS,那么二者不等的比特位置可在一定程度上成为活跃比特数组 AC 中的元素.(2)因为对任一输入差分(,)经过一轮加密后的输出空间主要由基向量组 A所决定,那么 A中基向量的活跃比特也可在一定程度上成为活跃比特数组 AC 中的元素.考虑到若 c 与窗口 W(i)L不吻合,则对所有的 A,输出差分 c 都将位于窗口之外,第一种情况对差分转移概率的影响更大.具体地,对于第一种情况,遍历输入差分的两个字 i1l,i1r,得到所有的 c,将其与 BS不等的比特施加相应的权重(权重为差分转移矩阵 Di1,处的概率与一轮差分转移概率 2 dim(U)的乘积).对于第二种情况,遍历 i1l,将每个 对应的基向量组 A中的所有基向量做或运算,对所得结果的非零比特施加相应的权重(因为第一种情况相对更重要,故这里的权重相对较小).结合这两部分权重得到最终的活跃比特的权重数组,将其按从大到小排序,取前 w 个权重值对应的索引作为活跃比特数组 AC 的元素,详细过程如算法3所示.按照这种求解方式迭代 r 轮,就可以确定每轮的输出窗口(W(i)L,W(i)R)及相应的(il,ir).牛开路 等:动态聚集效应及其在 SIMON 算法上的应用745算法 2 确定窗口 W(i)L的 BSInput:差分(,)的向量空间 i1l i1rOutput:窗口 W(i)L的 BSData:BSP 为长度为 n 的权重数组,初始化为 0;Di1为前 i 1 轮的动态窗口决定的差分转移矩阵.1BS=0;2for i1ldo3for i1rdo4=c;5for i=0 to n 1 do6if(1 i)!=0 then7BSPi=BSPi+Di1,;8else9BSPi=BSPi Di1,;10end11end12end13end14for i=n 1 to 0 do15BS=BS 1;16if BSPi 0 then17BS=BS1;18end19end20return BS.算法 3 确定窗口 W(i)L的 ACInput:差分(,)的向量空间 i1l i1r;算法2确定的窗口 W(i)L的 BS.Output:窗口 W(i)L的 ACData:bits 为长度为 n 的数组;ACP 为长度为 n 的权重数组,初始化为 0;Di1为前 i 1 轮的动态窗口决定的差分转移矩阵;p为 经过 f 的差分转移概率 2 dim(U).1AC=0;2for i1ldo3for i1rdo4=c BS;5for i=0 to n 1 do6if(1 i)!=0 then7ACPi=ACPi+Di1,p;8end9end10end11bits0n 1=0;12for i=0 to len(A)1 do13for k=0 to n 1 do14if Ai(1 k)!=0 then15bitsk=bitskAi;16end17end18end19s=Sum(bits);/Sum 对 bits 数组所有项求和20for i1rdo21for i=0 to n 1 do22ACPi=ACPi+Di1,p(bitsi/s);23end24end25end26ACP,index=sort(ACP);/对 ACP 权重数组按从大到小排序,同时返回对应的索引数组27for i=0 to w 1 do28if ACPindexi!=0 then29AC.add(indexi);30end31end32return AC.746Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.20234.3差分转移时的优化和3.2节的固定窗口模型类似,窗口确定后,就可以在窗口对应的向量空间内通过差分转移矩阵相乘的方式,将所有位于窗口内的差分路径的概率进行累积来得到一条差分的概率.但是因为本文的窗口是动态的,所以在每轮进行差分转移的时候会更复杂一些,需要对基向量组进行修正.如4.2节所述,对每轮的输入差分(,),其中 i1l,i1r,输出差分的左半部分为 c,它并不一定属于输出窗口 W(i)L的向量空间 il.我们分成 和 c 两部分进行分析.首先,已知 由基向量组 A所决定,而一开始根据 求得的 A是分布在整个 n-bit 字的空间上的,因此,需要删除那些位于输出窗口 W(i)L之外的基向量.其次,c 同样可能位于输出窗口 W(i)L之外,在进行差分转移时也需要结合这一点进行调整.具体地,在对窗口外的基向量进行处理时,最简单的做法就是判断该基向量中是否有活跃比特不属于活跃比特数组 AC,若是,则直接删除.但是,由算法1发现,基向量组 A由高斯消元法确定,而高斯消元法得到的结果并不唯一,存在其他的等价形式.因此直接删除可能导致“误操作”.举例说明:将基向量组 A写成矩阵的形式,每一行代表一个基向量的二进制形式.设:A=100100100100111,AC=2,3,4.若按照最简单的做法,A中的三个基向量在窗口外的 0,1 位置均有活跃比特,与 AC 不吻合,均需被删除.但是可以使用初等行变换将 A化成其他的等价形式.方法是先将 A中每个基向量对应于 AC中活跃比特的位置置零,得到 A,再对 A进行高斯消元.过程如下:A=000100000100011Gauss A=000100000100000,然后将 A A的初等行变换同步到原来的 A上,得到A=100100100111100.可以发现,A中的第三个基向量是位于窗口内的,应该被保留.同时,对于前两个基向量,并不是直接删除,而是继续结合 c 的取值做进一步判断.对于所有的 c,最直接的做法就是判断其是否位于输出窗口 W(i)L的向量空间 il之外,若是,则直接忽略,不再计算相应的差分转移.但是,考虑到前面那些位于窗口外的基向量,和同样位于窗口外的c 异或后,可能会抵消掉位于窗口外的活跃比特,从而回到窗口对应的向量空间内.因此,将上一步位于窗口外的基向量先保存下来,以用于这一步的优化.通过这两步处理来尽可能保留下更多位于窗口内的路径,从而提高差分的概率.5SIMON 算法的动态聚集效应我们利用第4节所介绍的动态窗口模型对分组密码 SIMON 进行高概率的差分和线性壳的搜索,主要针对 SIMON64、SIMON96 和 SIMON128 这三个版本,且均是在窗口大小 w=14 的情况下得到的结果3.令 m=maxw|U|,本文算法的时间复杂度的上界为 r 22w m log2(m)次基本运算(相比3因实验环境所限,本文的窗口比 Leurent 等人19的 w=18,19 更小,但实验结果更优.如果本文的窗口进一步增大,应该会包含更多的路线,得到更好的结果.牛开路 等:动态聚集效应及其在 SIMON 算法上的应用747原来的静态窗口模型多了一个常数 log2(m),且 log2(m)264的 24 轮差分;对于概率为 295.34的 SIMON96 的 31 轮差分14,得到 32 轮概率为 294的差分;对于概率为 2124.6的 SIMON128 的 41 轮差分特征10,在相同轮数下的差分概率为 2113.8,且能继续扩展,得到概率为2126.66的 44 轮差分.据我们所知,这是目前对于 SIMON128 的最长轮数的差分区分器.具体结果见表4所示.表 4 SIMON 的高概率差分搜索结果Table 4Results of differentials for SIMON版本轮数输入活跃比特输出活跃比特概率(log2)文献SIMON6421XL,19,XR,13,XR,17,XR,21YL,1360.2126XL,26,XR,24,XR,28YL,24,YL,28,YR,2657.5724XL,26,XR,24,XR,28YL,24,YL,28,YR,2655.14本文23XL,0,XR,2,XR,30YL,2,YL,6,YL,30,YR,461.9314XL,19,XR,13,XR,17,XR,21YL,13,YL,17,YR,1560.43本文SIMON9631XL,14,XR,0,XR,8,XR,12,XR,16YL,0,YL,8,YL,12,YR,2,YR,1095.341432XL,14,XR,0,XR,8,XR,12,XR,16YL,14,YR,0,YR,8,YR,1294本文SIMON12841XL,6,XR,0,XR,4,XR,8YL,0,YL,4,YL,8,YR,6123.7414XL,12,XR,6,XR,10,XR,14YL,6,YL,10,YL,14,YR,12113.8本文44XL,12,XR,6,XR,10,XR,14XL,20,XR,6,XR,14,XR,18126.66本文注:(XL,XR)和(YL,YR)分别代表输入差分和输出差分,XL和 XR分别代表输入差分的左右两个分支.5.2高线性概率的线性壳搜索结果同样使用已有成果中给出的最优线性壳的输入作为本文实验的输入掩码,在相同轮数下得到的线性壳的线性概率更高,且能够得到线性概率高于 22n的更长轮数的线性壳.具体地,利用文献 19 中提出的差分与线性路径之间的对应关系,将 SIMON64 的一个 23 轮的最优差分的输入差分转化为线性壳的输入掩码,得到了一个概率为 262.4的 24 轮线性壳;对于概率为 291.8的 SIMON96 的 31 轮线性壳15,继续扩展得到了概率为 293.41的 33 轮的线性壳;对于概率为 293.57的 SIMON96 的 33 轮线性壳19,扩展到 34 轮,概率为 293.99;对于概率为 2121.15的 SIMON128 的 41 轮线性壳15,在相同轮数下,找到的线性壳概率为 2110.5,且能继续扩展,得到概率为 2124.95的 45 轮线性壳.据我们所知,这是目前对于 SIMON64、SIMON96 和 SIMON128 的最长轮数的线性壳.具体结果见表5.5.3结果对比和实验验证为了验证本文的动态窗口模型能够通过聚集更多的头尾输入和输出差分/线性掩码相同的路径,得到具有更紧密的概率下界的差分或线性壳,分别用文献 19 的固定窗口模型和本文的动态窗口模型对输入差分固定为(0 x0,0 x1)的 SIMON64 进行搜索,对比每轮输出的最大概率,具体搜索结果见表6.748Journal of Cryptologic Research 密码学报 Vol.10,No.4,Aug.2023表 5 SIMON 的高线性概率的线性壳搜索结果Table 5Results of linear hulls for SIMON版本轮数输入活跃比特输出活跃比特概率(log2(LP)文献SIMON6423XL,2,XL,30,XR,0YL,28,YR,2,YR,26,YR,3060.8415XL,2,XL,30,XR,0YL,28,YR,2,YR,26,YR,3059.25本文24XL,10,XL,14,XL,18,XR,12YL,14,YL,18,YR,1262.4本文SIMON9631XL,2,XL,6,XL,14,XL,46,XR,0YL,4,YL,12,YR,2,YR,6,YR,1491.81533XL,2,XL,6,XL,14,XL