对简化版MORUS算法的改进动态立方攻击*

李俊志, 关 杰

(信息工程大学,河南 郑州 450001)

MORUS 算法[1]是2014 年由Wu 等人提出的认证加密算法,该算法提交到了CAESAR 竞赛[2]中,并经过层层筛选进入了竞赛的第3 轮.MORUS 算法有MORUS-640-128 和MORUS-1280-256 两个版本,前者的内部状态为640 比特,密钥规模为128 比特;后者的内部状态1 280 比特,密钥规模256 比特.本文分析的对象是MORUS-640-128-v1.MORUS 可以完成加密和认证两个方面的工作,其加密过程类似流密码,将生成的密钥流与明文进行异或,认证过程将消息注入到内部状态中参与运算,生成或验证认证码.算法由循环移位、与和异或这3 种运算组成,适用于硬件实现同时具有优良的软件实现效率.

MORUS 算法提出以后,由于其高效的软硬件实现效率和简洁的结构受到人们的广泛关注,但是由于其内部状态规模较大(640 比特),初始化迭代轮数较多(16 轮),并没有出现比较好的分析结果.文献[3]对初始化3 步的简化版MORUS 算法进行了区分攻击和密钥分割攻击,其中,区分攻击的复杂度可以忽略,密钥分割攻击的复杂度为O(2106.8).此外,作者利用差分自动推演方法给了对初始化4 步的简化版MORUS 算法的差分-区分攻击,所需数据量为O(2105).文献[4]给出了对MORUS 算法在SAT 攻击下的一些结果.文献[5]给出了对4 轮MORUS算法的立方攻击(cube attack).文献[6]利用可分性的方法给出了对5 轮MORUS 算法的立方攻击.

立方攻击[7]是2009 年由Dinur 和Shamir 提出的,该分析方法将目标算法看成黑盒多项式,没有利用算法的结构信息,可以用于分析内部结构未知的算法.目前,该方法已被应用于分析序列密码、分组密码和杂凑函数等的安全性,对Trivium、Grain 等算法取得了较好的攻击结果[8,9].动态立方攻击(dynamic cube attack)[10]由Dinur和Shamir 在2011 年提出,它可以看成是立方攻击的改进,其原理如下:猜测一部分和密钥有关的信息,并根据算法在立方测试(cube test)中表现出来的不同性质区分出正确的猜测值,从而恢复出密钥信息.由于它利用了算法的结构特点,往往可以取得比单纯立方攻击更好的效果.动态立方攻击在序列密码、分组密码和杂凑函数的分析中得到应用,其中,对满轮的Grain-128 的2118大小的密钥子空间,可以低于穷举攻击215倍的复杂度恢复出所有密钥[10],对杂凑函数Keccak 取得了目前最好的分析结果[11],在分析分组密码KATAN32 和SIMON32 时也取得了较好的效果[12].

本文提出一种改进的动态立方攻击方法,优化了动态立方攻击的立方集合的选取规则,提出了优先猜测关键值并恢复相应的关键秘密信息的方法,据此给出了成功率更高的秘密信息恢复方法.利用该方法分析了初始化5 步的简化版MORUS 算法,最终以O(295.05)的复杂度恢复所有128 比特密钥,攻击的成功率大于92%.

1 基础知识

1.1 立方攻击

立方攻击目前已被应用于分析序列密码、分组密码和杂凑函数等的安全性.立方攻击是一种选择明文攻击(对于分组密码)或选择IV 攻击(对于序列密码),也是一种密钥恢复攻击,可以应用于密码算法的内部结构未知的条件下.

立方攻击可以实施的条件是密码算法的输出比特可以表示成关于密钥比特和明文比特(对于分组密码)或IV 比特(对于序列密码)的次数较低的多变量多项式,这个多项式称为主多项式.

令p(x1,…,xn,v1…,vm)为主多项式在GF(2)上的代数正规型,其中,xi(1

其中,tI是只含有公开变量的单项式,tI中变量下标的集合I(I⊂{1,2,…,n})称为立方集合,pS(I)称为I在p中的超级多项式(superpoly).在上述分解中,pS(I)中变量的下标都不在立方集合I中,并且q中的任一单项式中都至少缺少下标在I中的一个变量.

下面给出包含立方攻击主要思想的定理.

定理1[7].如果主多项式有如下分解:

对密码算法的立方攻击可以分为预处理阶段和在线攻击阶段两个阶段:在预处理阶段,攻击者需要找到合适的立方集合,然后寻找尽可能多的最大项和对应的线性超级多项式,并将其组成方程组;在线攻击阶段,攻击者求出预处理阶段得到的线性超级多项式的值,并解方程组恢复密钥.

1.2 立方测试

立方测试的原理也是通过公开变量的值来评估超级多项式,只不过它的目的不是恢复密钥,而是通过立方测试将密码算法和随机函数区分开,或者是根据超级多项式的某些代数性质检测出它的非随机性.一种常用的立方测试是平衡性测试,根据超级多项式的0,1 不平衡性,将其与随机函数区分开.此外,其他有效的区分性质包括低代数次数、线性变量和中性变量等.

1.3 动态立方攻击

动态立方攻击的原理如下:猜测一部分和密钥有关的信息,并根据算法在立方测试中表现出来的不同性质区分出正确的猜测值,从而恢复出密钥信息.在文献[10]中,作者给出了进行动态立方攻击的一般步骤,概括如下.

算法1.动态立方攻击[10].

· Step 1.选择需要消去(即使这个内部状态取0)的内部状态比特,并给出该内部状态比特取0 时动态变量的取值或条件;

· Step 2.选择一个进行立方测试时区分效果较好的立方集合,根据所选的立方集合确定需要猜测的秘密变量的表达式,以便在立方求和时可以计算动态变量的值;

· Step 3.对每个秘密变量可能的猜测值,将动态变量设置成合适的值,在Step 2 中得到的立方集合的阶较大的立方子集上进行立方求和,将针对不同立方子集对应的立方和构成一个集合,计算集合中元素取值的重量(其中取值为1 的元素个数),根据重量取值按照由小到大的顺序进行排序,得到一个由重量及相应猜测值构成的有序表;

· Step 4.根据Step3 中得到的有序表,给出秘密变量可能的候选值(一般选择表中排序靠前的部分作为秘密变量的候选值),进而求出部分或所有秘密变量的值.

其中:前两步是离线阶段,攻击者具有控制密钥的能力,其复杂度为预计算的复杂度;后两步为在线阶段,目的是恢复密钥.

1.4 改进的动态立方攻击

我们在对动态立方攻击研究时发现,算法1 的Step 2 中,立方集合的选取规则和Step 4 中秘密变量的恢复方法可以进行改进.我们尝试优化了动态立方攻击的立方集合的选取规则,提出了优先猜测关键值并恢复相应的关键秘密信息的方法,据此提出了一种改进的动态立方攻击方法,从而提高了原始攻击的成功率并降低了攻击的复杂度.具体改进如下.

观察1.虽然算法1 的Step 2 中选取的立方集合对猜测值的区分效果较好,但是并不是它的所有阶较大的立方子集的区分效果都很好,有些立方子集对正确和错误猜测值求和的结果相差很小,如果将此立方子集列入统计,则会对后面的排序结果造成干扰.

改进1.为了避免这样的干扰,我们不再选择大的立方集合,而是直接测试较小的立方集合对猜测值的区分能力,从中选取所需的区分能力强的立方集合,进而为下一步恢复秘密信息提供了攻击基础.

观察2.当需要猜测的表达式的个数较小时,通过对求和表排序得到正确猜测值的方法成功率较低,有时正确猜测值的排序甚至在表的后半部分中,此时以可接受的成功率得到正确秘密信息的计算复杂度将近似穷举攻击.研究发现:当选择合适的立方集合后,待猜测值组成的集合中存在着某些关键猜测值,在固定其他猜测值的情况下,关键猜测值取值正确时对应立方和为0 的概率往往比关键猜测值错误时对应立方和为0 的概率高,可据此恢复关键猜测值.

改进2.根据内部状态的表达式选定关键猜测值,离线阶段选定合适的立方集合;在线阶段,穷举猜测值进行立方求和后,得到一个由重量及相应猜测值构成的表,我们按照关键猜测值的取值将表进行分类(t个关键猜测值则分为2t类),将每类表中所有的重量相加,对应重量和最小的猜测值即为正确的关键猜测值.

以下我们对5 轮简化版MORUS 算法进行了改进的动态立方攻击,通过实验验证,改进的方法可以提高正确恢复关键猜测值的成功率.

2 MORUS 算法

MORUS 算法分为初始化、关联数据处理、加密、认证码生成和解密与验证这5 个阶段.由于本文的攻击条件将关联数据设置为0,只涉及初始化阶段和加密阶段,下面只对算法的这两个阶段进行描述,详细的算法请参考设计报告.

2.1 符号说明

·Si:第i步的内部状态,0≤i≤16;

·:第i步更新第k轮的内部状态,0≤k≤4;

·:第i步第k轮内部状态的第l块128 比特分组,0≤l≤4;

·:第i步第k轮内部状态第l块分组的第j比特,0≤j≤127;

·Rotl(x,n):将128 比特长的x分成4 块32 比特字,每块循环左移n比特;

· 0n:n长全0 比特串;

· 1n:n长全1 比特串;

· (·)4:16 进制表示;

·const0:128 比特常数(000101020305080d1522375990e97962)4;

·const1:128 比特常数(db3d18556dc22ff12011314273b528dd)4.

2.2 MORUS算法的状态更新函数

MORUS 算法的状态更新函数为Si+1=StateUpdate(Si,mi),算法初始化过程共有16 步这样的更新函数,每步更新函数包含5 轮相似的更新过程,具体过程如下.

·Si+1更新:Fork=0 to 4,

状态更新函数如图1 所示.

Fig.1 Update function of MORUS图1 MORUS 算法的状态更新函数

2.3 MORUS算法的初始化阶段

MORUS 的初始化阶段包括将密钥K和初始向量IV 注入到内部状态中,并运行16 步状态更新函数.密钥和IV 的加载方式如下:

2.4 MORUS算法的加密阶段

在算法的加密阶段,128 比特的明文Pi与密钥流进行异或运算得到密文Ci,设明文消息的长度为msglen,令:

3 对5 步MORUS 算法的改进动态立方攻击

动态立方攻击的过程可以分为离线阶段和在线阶段:离线阶段主要是收集必要的信息,为恢复秘密信息做准备;在线阶段的主要目的是恢复密钥.下面对简化版MORUS 算法的动态立方攻击按照这两个阶段进行说明.

由于MORUS 算法密钥流每次输出128 比特,相当于128 个关于密钥和IV 的多项式,在进行立方测试时,可以分别利用每个比特的信息.下面我们以第0 比特为例进行分析,其他比特的分析类似.

3.1 离线攻击阶段

· 步骤1:寻找合适的表达式化简方法.

寻找动态IV、需要穷举的秘密信息、关键猜测值和对应的立方集合中的必选IV 集合,使得动态IV 满足动态立方攻击条件时能够以合适的方式化简表达式.

输出密钥流的第0 比特为:

故当s-3,314=0 且s-3,186⊕s-3,570=0 时,有s-2,251=0.

分别将s-3,314和s-3,186⊕s-3,570表示成关于密钥和IV 的表达式.

将s-3,314和s-3,186⊕s-3,570简单表示成如下形式:

·s-3,314=v82⊕F1=v82⊕v127·(v111⊕F4)⊕F3;

·s-3,186⊕s-3,570=v97⊕F2.

其中,F1和F2是关于密钥和IV 的多项式;而v82只出现在s-3,314的一次项中,且在s-3,186⊕s-3,570中不出现;v97只出现在s-3,186⊕s-3,570的一次项中,且在s-3,314中不出现;v127和v111均不包含在F3和F4中.

当v111=F4,v82=F3,v92=F2时,s-2,251恒为0.根据观察2 我们发现:若选取的立方集合能够以较大概率将s-2,251是否为0 区分开,则能以较大概率判断出v111=F4,进而根据v111的取值恢复出F4.这样,我们令v111为关键猜测值,F4为关键秘密信息,对应的v127为必选IV,同时将v82和v97列为动态变量.

需要说明的是:上述化简方式并不唯一,还可以找到其他的关键猜测值及其对应的秘密信息,为攻击者提供更多的信息.

· 步骤2:寻找合适的立方集合.

此步需要根据步骤1 中确定的表达式化简方法和必选IV 集合,寻找满足区分条件的足够数量的立方集合.

在对初始化5 步的MORUS 算法进行立方测试的过程中我们发现:当立方集合大小为9 时,输出比特的立方和存在明显的0/1 不平衡性,而且可以保证在可接受的时间内找到足够数量符合条件的立方集合,我们将立方阶定为9.

立方集合中包含必选IV 和候选IV,其中必选IV 是由步骤1 中关键秘密因素确定的.为了降低复杂度,候选IV 则从s-3,314和s-3,186⊕s-3,570的表达式中均不包含的IV 集合中选取,这样可使需要穷举的秘密信息尽可能少.经统计可知,s-3,314和s-3,186⊕s-3,570中一共包含了88 个IV 比特,未包含40 个IV 比特的序号集合如下:

T={1,3,15,17,18,22,27,28,34,35,40,41,42,47,54,55,56,60,64,65,66,67,73,74,75,79,80,83,93,105,112,113,114,116,117,120,122,123,124,126}.

在立方测试时,为了检测s-2,251是否为0 时立方测试时表现出的差别,在离线阶段则赋予攻击者额外的能力,可以在立方求和时强制将s-2,251设置为0.

算法2.寻找MORUS 算法的立方集合.

输入:立方阶d,候选IV 集合A,必选IV 集合B,区分度δ,立方集合目标个数n;

输出:候选立方集合.

初始化:C=∅

· Step 1.从A中任选d-|B|个IV,与B组成立方集合C′;

· Step 2.随机选取m组密钥,遍历立方集合C′,其他IV 设置为0,运行立方测试算法,在算法运行中强制将s-2,251设置为0,对输出结果求和,结果为sumc;

· Step 3.随机选取m组密钥,遍历立方集合C′,其他IV 设置为0,运行立方测试算法,对输出结果求和,结果为;

· Step 5.如果|C|=n,或Step 1 中已将A遍历,则输出C并终止算法;否则返回Step 1,重新寻找立方集合.如例1,设置候选IV 集合A={vi|i∈T},必选IV 集合B={v127},n=400,m=1000,δ=0.05.运行算法2,找到其中一个立方集合C′={v3,v18,v27,v42,v65,v73,v114,v126,v127},随机选取1 000 组密钥,分别执行Step 2 和Step 3 时得到:,差值129>50,这个立方集合将具有较好的区分效果.

与算法1 中的立方集合选取方式进行对比,我们的改进在于增加了区分度的判决筛选过程:1000·δ.如果立方集合不满足此筛选条件,在线阶段使用此立方集合则会对恢复秘密信息造成干扰,降低成功率.

我们搜索了关于输出密钥流前32 比特的立方集合及其对应的秘密信息(具体如表1 所示).本文的实验环境为Intel i5,3.2GHzCPU,4GB 内存,Windows7 32 位操作系统,对表中每个关键猜测值和必选IV,搜索到足够数量的立方集合所需时间为几十分钟到几天不等.需要指出的是:对其他的96 个密钥流输出比特进行考察将得到更多此类信息,能够进一步降低攻击复杂度.

Table 1 Dynamic cube attack key information of MORUS reduced to 5 rounds表1 5 步简化版MORUS 算法动态立方的重要信息

3.2 在线攻击阶段

· 步骤3:恢复MORUS 算法的秘密信息

本步骤是在线攻击阶段,此时密钥固定,主要目的是利用上一步中得到的秘密信息及其对应的立方集合,恢复其中的关键秘密信息,进而恢复部分(或全部)密钥.

算法3.恢复MORUS 算法的关键秘密信息.

输入:秘密信息及其立方集合、关键秘密信息c;

输出:c的值.

初始化:令sum0=0,sum1=0.

· Step 1.将关键猜测值设置为0,穷举剩下需要猜测的秘密信息,对每个猜测值,设置相应的动态IV 取值,运行立方测试算法,将输出结果加到sum0上;

· Step 2.将关键猜测值设置为1,穷举剩下需要猜测的秘密信息,对每个猜测值,设置相应的动态IV 取值,运行立方测试算法,并将求和的结果加到sum1上;

· Step 3.若sum0

利用算法3 可以恢复关键秘密信息,关键秘密信息一般是一个非线性表达式,对于一些特殊的非线性表达式,我们可采取执行下述操作从中直接恢复某些ki的信息:

当这个表达式中存在密钥比特ki与IV 比特vj的乘积项kivj时,且vj在表达式其他部分中不出现时,可分别令vj=0 或1,执行算法3,并对两次求得的关键秘密信息做模2 和,结果即为ki.

如例1,利用算法3 中的方法恢复关键秘密信息F4时,随机选取了100 组密钥,实验所得恢复的F4与真实值相等的概率为ps=90%.由于F4的表达式中含有项v2(k11⊕1),可以按照上述方法,通过改变v2的值直接求出k11的值.表1 中列出了恢复关键秘密信息的成功率ps和利用该秘密信息能够直接求出的密钥比特.为了对比,我们使用算法1 中恢复秘密信息的方法,实验发现成功率约为65%,远小于本文恢复关键秘密信息的成功率.

由表1 可知,表中标*的项共23 个,运行算法3,可求出23 个关键秘密信息.其中,能够直接求出16 个密钥比特和12 个关于密钥的线性方程,共28 比特密钥信息.下面给出恢复所有密钥的方法.

算法4.恢复简化版MORUS 算法所有密钥.

· Step 1.对表1 中23 个关键秘密信息,运行算法3,可求出23 个关键秘密信息的值;

· Step 2.对表1 中28 个密钥信息,改变相应的IV 比特,运行算法3,求出28 个关键秘密信息的值;

· Step 3.对于上述51 个关键秘密信息,穷举其中错误值小于5 的所有情况,对每一种情况,修正相应的关键猜测值,求出16 个密钥比特和12 个关于密钥的线性方程,并得到修正的23 个关于密钥的方程;

· Step 4.穷举剩余112 个密钥比特:

➢ Step 4-1.代入12 个关于密钥的线性方程和23 个非线性方程进行验证:若出现矛盾,则返回Step 3 中穷举下一个错误情况;否则,将此密钥代入MORUS 算法进行进一步检验;

➢ Step4-2.若通过检验,则输出此密钥为正确密钥,算法终止;否则,返回Step 3 中穷举下一个错误情况.

为保证攻击的成功率,算法4 中采用了试错与穷举相结合的方法.Step 1 和Step 2 的复杂度为(23+28)×400×23×29≈226.32,Step 3 中穷举所有错误情况的复杂度为,Step 4 中密钥能够通过每个线性方程的概率为1/2,而经验证,这23 个非线性式子每个等于0 的概率均为1/2,且近似两两独立,可以认为密钥通过这23 个非线性方程中每个的概率均为1/2.因此,密钥通过第1 层检验的概率为1/235,故恢复所有128 比特密钥的计算复杂度为O(226.32+218.05×2112-35)≈O(295.05).攻击的数据复杂度为O(226.32).在计算成功率时,为简化计算,将恢复单个关键秘密信息的成功率ps均假设为最低值96%(实际的成功率应大于计算值),此时,51 个值中正确的个数x服从二项分布B(51,0.96),近似服从正态分布N(48.96,1.96),则p(x≥47)≈0.92.因此,算法4 恢复所有密钥的成功率大于92%.表2 给出了现有不同攻击方法的结果的比较.

Table 2 Results of attacks on MORUS表2 对MORUS 算法的攻击结果对比

从攻击结果的对比可以发现:目前本文给出的改进的动态立方攻击是对MORUS-640-128 算法轮数最多的恢复密钥攻击之一,并且本文的攻击相比文献[6]的结果在计算复杂度方面有较大优势.可见,动态立方攻击对此类算法是一种比较有效的攻击方法.另外,文献[4]中利用SAT 求解器恢复内部状态攻击的计算复杂度大大高于穷举攻击,仅对该算法抵抗基于SAT 的代数攻击能力给出了一个参考.

4 总结

MORUS 算法的内部状态更新函数与传统的基于移位寄存器的序列密码有明显区别,基于移存器的序列密码每次只更新几个比特,而MORUS 算法每次更新128 比特,导致其内部状态各比特的代数表达式复杂程度接近,给动态立方攻击带来了一定的困难.本文改进了动态立方攻击方法,优化了立方子集合的选取规则,给出了新的秘密信息恢复方法.对初始化5 轮的MORUS 算法进行了动态立方攻击,最终以O(295.05)的复杂度恢复了所有128 比特密钥.结果表明:动态立方攻击针对MORUS 算法的攻击效果很好,并且有进一步提升的空间.下一步拟将改进的动态立方攻击应用于分析其他算法.