LiCi算法的基于比特积分攻击

信文倩,孙 兵,李 超

(国防科技大学 文理学院,长沙 410073)

0 概述

随着信息时代的快速发展,物联网作为信息技术的重要组成部分,其通过智能感知、识别技术与普适计算等通信感知技术广泛应用于网络融合中。由于物联网中使用的微型计算设备的计算能力有限,因此为了保证信息安全,轻量级分组密码算法应运而生。轻量级分组密码算法是分组密码算法中的一种,相比普通的分组密码算法,该算法的分组长度相对较短,且算法结构简单,满足低耗能、低成本的需求。目前,轻量级分组密码算法主要有LED[1]、LBlock[2]、PRESENT[3]、HIGHT[4]、SPECK[5]等算法,这些算法均具有结构简单、加解密一致、容易实现等优点。

2017年,PATIL等人[6]提出一个分组长度为64比特、密钥长度为128比特的轻量级分组密码算法——LiCi算法。该算法结构类似于MISTY结构,在单轮加密结构中,非线性组件S盒会影响到加密结构的两支。相较于普通Feistel结构分组密码算法,LiCi算法具有扩散性快等优势。同时,相比于SP结构分组密码算法,LiCi算法对非线性组件输出结果进行复用,使之结构更加简单,具有占用面积小等特性。文献[7]对LiCi算法抵抗不可能差分攻击的能力进行了介绍。然而,关于LiCi算法抵抗积分攻击的能力目前尚不清楚,因此,本文利用积分攻击方法对该算法进行分析。

积分攻击是KNUDSEN等人[8]在总结Square攻击、Multiset攻击、Saturation攻击的基础上提出的一种密码分析方法。该攻击方法是一种选择明文攻击方法,与差分攻击[9]、线性攻击[10]、代数攻击[11]同为目前密码学界公认的最有效的几种分析方法。结合故障分析的思想,差分故障分析[12]、代数故障分析[13]、积分故障分析[14]等分析方法也受到密码学者们的广泛关注。积分分析方法提出后,其在AES[15]、Camellia[16]、FOX[17]、PRINCE[18]等算法中进行不同程度的分析应用。文献[19-20]提出比特的可分性质后,结合MILP搜索工具,利用可分性质对MISTY1进行全轮攻击。同时,文献[21]也基于比特的可分性质结合MILP搜索工具,进一步提升LBlock[2]、PRESENT[3]、SIMECK[22]等算法的积分分析结果。

本文基于比特的可分性质,结合MILP搜索工具对LiCi算法的积分区分器进行搜索。利用搜索得到的最长轮数的12轮积分区分器对LiCi算法进行13轮积分攻击,恢复17比特密钥信息,同时,为了得到更高轮数的攻击结果,利用10轮积分区分器向后攻击6轮,对LiCi算法进行16轮积分攻击。

1 LiCi算法介绍

1.1 LiCi算法加密过程

LiCi算法分组长度为64比特,密钥规模为128比特,其迭代轮数为31轮。LiCi算法的单轮加密结构如图1所示,基本操作包括字节替换、异或、密钥加、循环移位等步骤。字节替换是该算法中唯一的非线性组件,由8个并列的4进4出的S盒构成。

图1 LiCi算法单轮加密结构

加密过程设第i轮输入为Xi,Yi,i=0,1,2,…,29,30,分别代表第i轮输入的左分支和右分支;输出为Xi+1,Yi+1,分别代表输出的左分支和右分支。状态Xi,Yi到状态Xi+1,Yi+1的迭代过程表示如下:

Xi+1=[S[Xi]⊕Yi⊕RK1i]<<<3

Yi+1=[S[Xi+1]⊕Xi+1⊕RK2i]>>>7

(1)

其中,RK1i,RK2i均为轮密钥,Xi,(31,30,…,2,1,0)和Yi,(31,30,…,2,1,0)分别表示输入状态的64个比特的标号,如Xi,31表示第i轮左支输入的最高比特,Yi,0表示第i轮右支输入的最低比特。

1.2 LiCi算法密钥扩展方案

密钥扩展方案:种子密钥长度为128比特,记为K=K127K126…K2K1K0,RK1i,RK2i均表示第i轮轮密钥,其中RK1i应用于第i轮右支加密,RK2i应用于第i轮左支加密。轮密钥生成过程如下:

1)K=K127K126…K2K1K0

2)RK1i=K31K30K29…K2K1K0,RK2i=K63K62…K33K32,i∈{0,1,2,…}

3)Knew=K<<<13=K114K113…K1K0K127K126…K115

4)K=Knew

5)[K3K2K1K0]new=S[K3K2K1K0]

[K7K6K5K4]new=S[K7K6K5K4]

[K63K62K61K60K59]new=[K63K62K61K60K59]⊕i,i∈{0,1,2,…}

6)[K3K2K1K0]=[K3K2K1K0]new

[K7K6K5K4]=[K7K6K5K4]new

[K63K62K61K60K59]=[K63K62K61K60K59]new

7)经过3)～6)得到新的K,返回1),经过2)得到新的轮密钥。

轮密钥分析:若已知第i轮密钥RK2i,RK1i(其中i≥5),根据密钥扩展方案可以得知(RK2i-4,RK1i-4),…,(RK2i,RK1i)之间的关系。

假设已知(RK2i,RK1i)=(K63…K33K32,K31…K1K0),则根据密钥扩展方案中轮密钥生成方案可知(RK2i-1,RK1i-1)和(RK2i,RK1i)之间的某些比特信息等价,通过密钥生成方案中3)～6)可知,(RK2i-1,RK1i-1)与(RK2i,RK1i)相比,新引入13比特信息。同理,可以分析(RK2i-2,RK1i-2)和 (RK2i-1,RK1i-1),…,(RK2i-3,RK1i-3)和(RK2i-4,RK1i-4)之间的关系,5轮轮密钥总共包含116比特密钥信息,6轮轮密钥总共包含种子密钥128比特密钥信息。通过上述轮密钥分析,利用轮密钥之间的信息等价关系,在猜测密钥过程中可以降低密钥猜测量。

1.3 LiCi算法的S盒性质

LiCi算法4比特S盒如表1所示,输入为x,输出为S(x)。

表1 LiCi算法S盒

采用文献[23]中求S盒布尔函数表达式的方法来求解LiCi算法4比特S盒代数表达式。

性质1(S盒代数表达式) 设S盒输入为x=(x3,x2,x1,x0),输出为y=(y3,y2,y1,y0),则x和y之间的关系表达式如下:

y3=x0+x1+x3+x1x2+x1x3

y2=x0+x1+x3+x0x2+x0x3+x2x3+x0x1x2

y1=1+x2+x3+x0x1+x0x2+x1x3+x2x3+x0x1x3

y0=1+x1+x2+x3+x0x1

例如,输入x3x2x1x0=0001,经过S盒输出y3y2y1y0=1111。

2 基于比特的可分性质和MILP方法

2.1 基于比特的可分性质

定义1(比特积函数πu(x)和πU(X)[24]) 多重集的可分性质可通过比特积函数进行评估,比特积函数的定义如下:

其中,x[i]1=x[i],x[i]0=1。

定义3(可分路径[21]) 考虑可分析性质的传播{k}≜K0→K1→K2→…→Kr,对任意向量ki+1∈Ki+1使得ki能传播到ki+1,i∈{0,1,…,r-1},则(k0→k1→…→kr)为一条r轮可分路径。

上述内容是关于比特积函数、可分性和可分路径的介绍,下面对基于比特的可分性质经过复制操作、异或操作时的传播规则进行简要介绍,更多详情可参考文献[21,24]。

2.2 基本操作的MILP模型

基于比特的复制模型:假设输入可分性为a,经过基于比特的复制操作输出可分性为(a0,a1),记作a→(a0,a1),其中a,a0,a1∈{0,1}。a,a0,a1之间的关系如下:

a-a0-a1≥0,0≤a0≤1,0≤a1≤1

例如:1→(0,1)或1→(1,0),0→(0,0)。

基于比特的异或模型:假设输入可分性为(a0,a1),经过基于比特的异或操作输出可分性为a,记作(a0,a1)→a,其中a,a0,a1∈{0,1}。a,a0,a1之间的关系如下:

a-a0-a1≥0,0≤a0≤1,0≤a1≤1

例如:(0,1)→1,(1,0)→1,(0,0)→1,但是输入可分性为(1,1),经过异或操作可分性传播会中断。

S盒模型:利用文献[20]中的算法2可以得到LiCi算法S盒的可分性(详见开放科学(资源服务)标志码中附录部分),通过得到的S盒的可分性结合SageMath软件可得到S盒的线性不等式组。再利用文献[20]中的算法1对上述S盒线性不等式组进行简化,最终得到LiCi算法S盒的15个线性不等式(详见开放科学(资源服务)标志码中附录部分)。

基于比特的循环移位模型:假设输入n比特可分性为kn-1,…,k2,k1,k0,其中ki∈{0,1}。循环左移j位,输出为k(i+n-j)mod n,i∈{n-1,…,2,1,0};循环右移j位,输出为k(i+j)mod n,i∈{n-1,…,2,1,0}。

3 MILP方法在LiCi算法中的应用

3.1 LiCi算法MILP模型建立

对LiCi算法的基本操作建立MILP模型,在模型建立过程中,基于比特的复制模型、异或模型和S盒模型与已有文献[20]给出的模型构造基本相同,根据LiCi算法左支循环右移7位后直接得到输出值的结构特性,在最后一轮利用逆向思维构造LiCi算法MILP模型。

LiCi算法单轮可分性传播示意图如图2所示。

图2 LiCi算法单轮可分性传播示意图

第i(i∈{1,2,…,R-1})轮LiCi算法单轮MILP模型建立过程如下所示:

性质1(基于比特循环移位) 在单轮函数加密结构中,若输入可分性经过循环移位操作后,存在复制操作、异或操作或S盒,则直接对输入可分性建立基于比特的循环移位模型,反之,则最后一轮输入可分性经过循环移位操作时利用逆向思维建立基于比特的循环移位模型。以LiCi算法为例,最后一轮(第R轮)MILP模型建立过程如下:第R轮MILP模型建立过程1)～5)和第1轮至第R-1轮模型建立过程相同,6)和7)过程如下:

3.2 LiCi算法基于比特积分区分器搜索结果

目前搜索得到的LiCi算法平衡比特数最多,轮数最长的积分区分器为输入63比特活跃,输出43比特平衡的12轮积分区分器。

假设a表示活跃,b表示平衡,c表示常数,?表示未知,输入两支的单支为32比特,令标号31表示最高位,标号0表示最低位,输入两支标号表示如下:

10轮积分区分器:基于MILP搜索得到的平衡比特数最多,轮数最长的积分区分器为输入62比特活跃,输出64比特平衡的10轮积分区分器,输入记为(X0,Y0),输出记为(X10,Y10),输入输出状态表示如下:

X0:aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa

Y0:aaaa,aaaa,aaaa,aaaa,aaaa,aaca,aaaa,aaca

X10:bbbb,bbbb,bbbb,bbbb,bbbb,bbbb,bbbb,bbbb

Y10:bbbb,bbbb,bbbb,bbbb,bbbb,bbbb,bbbb,bbbb

12轮积分区分器:目前搜索得到的最长轮数积分区分器为12轮积分区分器,共有两个积分区分器,积分区分器1是输入63比特活跃,输出43比特平衡;积分区分器2是输入63比特活跃,输出6比特平衡。输入记为(X0,Y0),输出记为(X12,Y12),输入输出状态表示如下:

1)12轮积分区分器1

X0:aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa

Y0:aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaac

X12:bbbb,bbbb,bbbb,bbbb,bbbb,bb??,bb??,bbbb

Y12:???b,??bb,bbbb,bbbb,bbbb,bbbb,bbbb,b??b

2)12轮积分区分器2

X0:aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaac

Y0:aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa,aaaa

X12:????,??b?,bb??,b???,????,????,????,????

Y12:????,????,????,???b,???b,????,????,????

4 LiCi算法的密钥恢复攻击

4.1 13轮密钥恢复攻击

由于目前基于MILP搜索得到的最优12轮积分区分器输入活跃比特数为63比特,输出平衡比特数为43比特,利用12轮积分区分器时只能利用1组明文,通过猜测41比特密钥信息,对第13轮RK212的17比特密钥信息进行密钥恢复攻击。具体攻击过程和攻击结果如下:

1)对构造12轮积分区分器中263个明文进行加密,得到263个密文C0,C1,…,C263-1。

2)猜测第13轮41比特轮密钥RK212,(31,…,13,12,3,2,1,0),RK112,(28,25,24,23,…,13,12,3,1)解密第13轮,得到第12轮41比特输出X12,(31,…,13,12,3,2,1,0)和Y12,(23,…,13,12,3,1)。如下表示:

X12,(31,…,13,12,3,2,1…,0)=

S-1((Y13<<<7)⊕X13⊕RK2)12,(31,…,13,3,…,0)

Y12,(28,25,24,23,…,13,12,3,1)=

((Y13<<<7)⊕X13⊕RK212)(28,25,24,23,…,13,12,3,1)⊕

(X13>>>3)(28,25,24,23,…,13,12,3,1)⊕

RK112,(28,25,24,23,…,13,12,3,1)

(2)

验证X12,(31,…,13,12,3,2,1,0)和Y12,(28,25,24,23,…,13,12,3,1)是否为平衡比特,若为平衡比特,则猜测密钥为正确密钥,否则为错误密钥。密钥恢复攻击分为两步,第一步对轮密钥RK212,(31,…,13,12,3,2,1,0)进行密钥恢复攻击,错误轮密钥使X12,(31,…,13,12,3,2,1,0)为平衡比特的概率为2-24,经过1组明文后剩余错误密钥数目为(224-1)×2-24≈1。第二步对轮密钥RK212,(31,…,13,12,3,2,1,0)和RK112,(28,25,24,23,…,13,12,3,1)进行密钥恢复攻击,错误密钥使Y12,(28,25,24,23,…,13,12,3,1)为平衡比特的概率为2-17。由于第一步已经对RK212,(28,25,24,23,…,13,12,3,1)进行筛选,经过1组明文后RK212,(28,25,24,23,…,13,12,3,1)剩余错误密钥数目为1,经过第二步筛选后RK212,(28,25,24,23,…,13,12,3,1)剩余错误密钥数目为2-17<<1,可以恢复RK212,(28,25,24,23,…,13,12,3,1)共17比特密钥信息。由于经过第二步筛选,RK112,(28,25,24,23,…,13,12,3,1)错误密钥量为1,因此无法对RK112,(23,…,13,12)进行正确恢复。从而攻击数据复杂度为263个明文,时间复杂度为263×241=2104次查32比特S盒大表,相当于2104/16=2100次16轮加密。为猜测密钥,攻击需要对猜测密钥进行存储,存储复杂度为241。

针对式(2)的计算,可以通过“部分和”[25]技术对其进行改进,具体方式如下:

步骤1猜测RK212,(31,…,13,12,3,2,1,0)的一种可能值,并计算72比特三元组(Z12,(31,…,12,3,…,0),(Y13<<<7)(31,…,13,3,…,0),X13,(31,…,13,3,…,0)),其中Z12,(31,…,13,12,3,…,0)=((Y13<<<7)⊕X13⊕RK212)(31,…,13,3,…,0),用表T记录出现奇数次的三元组(Z12,(31,…,12,3,…,0),(Y13<<<7)(31,…,13,3,…,0),X13,(31,…,13,3,…,0)),求得最终结果⊕Z12,(31,…,12,3,…,0)。

步骤2猜测(RK2,RK1)12,(28,25,24,23,…,13,12,3,1)的一种可能值,对表T中标记的每一个三元组,计算W12,(28,25,24,23,…,13,12,3,1),其中W12,(28,25,24,23,…,13,12,3,1)=Z12,(28,25,24,23,…,13,12,3,1)⊕(X13⊕RK112,(28,25,24,23,…,13,12,3,1),求得最终结果⊕W12,(28,25,24,23,…,13,12,3,1)。

若步骤1中求得的值⊕Z12,(31,…,12,3,…,0)=0,则此次猜测的RK212,(31,…,13,12,3,2,1,0)有可能是正确密钥,否则一定是错误密钥。一个错误密钥满足⊕Z12,(31,…,12,3,…,0)=0的概率为2-24。若步骤2中求得的值⊕W12,(28,25,24,23,…,13,12,3,1)=0,则此次猜测的RK212,(28,25,24,23,…,13,12,3,1),RK112,(28,25,24,23,…,13,12,3,1)有可能是正确密钥,否则一定是错误密钥。一个错误密钥满足⊕W12,(28,25,24,23,…,13,12,3,1)=0的概率为2-17,因此,1个包含263个明文的明文组可以唯一确定17比特轮密钥RK212,(28,25,24,23,…,13,12,3,1)。

求解RK212,(28,25,24,23,…,13,12,3,1)的时间复杂度步骤如下:

步骤1对于224种RK212,(31,…,13,12,3,2,1,0)的可能值,需要处理的密文有263个,因此需要进行287次32比特S盒查表操作。

步骤2由于一共猜测了34比特密钥信息RK212,(28,25,24,23,…,13,12,3,1),RK112,(28,25,24,23,…,13,12,3,1),对于三元组中的每个(Z12,Y13<<<7,X13)28,25,24,23,…,13,12,3,1计算W12,(28,25,24,23,…,13,12,3,1),且(Z12,Y13<<<7,X13)(28,25,24,23,…,13,12,3,1)至多有251种可能,需要大约进行285次32比特S盒查表操作。综上,攻击时间复杂度为(287+285)≈287次查32比特S盒查表,相当于约283次16轮加密,相比于2100次16轮加密结果有了较大改进。

4.2 16轮密钥恢复攻击

为了得到更长轮数的攻击结果,结合密钥扩展方案的特性,本文选择利用10轮积分区分器向后攻击6轮,对16轮LiCi算法进行密钥恢复攻击。攻击过程至少需要猜测119比特密钥信息。第11轮攻击过程如图3所示。

图3 第11轮密钥恢复攻击

具体攻击过程如下:

步骤1对构造10轮积分区分器中262个明文进行加密,得到262个密文C0,C1,…,C262-1。

步骤2猜测第16轮64比特轮密钥(RK215,RK115),解密第16轮,得到第15轮64比特输出X15,(31,30,…,2,1,0)和Y15,(31,30,…,2,1,0)。

步骤3根据步骤2的结果,猜测第15轮64比特轮密钥(RK214,RK114),结合密钥扩展方案和轮密钥的关系可以得知,这一步只需要猜测13比特信息。解密第15轮,得到第14轮64比特输出。

步骤4根据步骤3的结果,猜测第14轮64比特轮密钥(RK213,RK113),结合密钥扩展方案和轮密钥的关系可以得知,这一步只需要猜测13比特信息。解密第14轮,得到第13轮64比特输出。

步骤5根据步骤4的结果,猜测第13轮64比特轮密钥(RK212,RK112),结合密钥扩展方案和轮密钥的关系可以得知,这一步只需要猜测13比特信息。解密第13轮,得到第12轮64比特输出。

步骤6根据步骤5的结果,猜测第12轮64比特轮密钥(RK211,RK111),结合密钥扩展方案和轮密钥的关系可以得知,这一步只需要猜测13比特信息。解密第12轮,得到第11轮64比特输出。

步骤7根据步骤6的结果,猜测第11轮44比特轮密钥(RK210,(21,20,…,2,1,0),RK110,(21,20,…,2,1,0)),结合密钥扩展方案和轮密钥的关系可以得知,这一步只需要猜测3比特信息。解密第11轮,得到第10轮42比特输出(X10,(19,…,2,1,0),Y10,(21,20,…,2,1,0)),具体表示如下:

X10,(19,…,2,1,0)=S-1((Y11<<<7)⊕X11⊕RK210)(19,…,2,1,0)

Y10,(21,20,…,2,1,0)=((Y11<<<7)⊕X11⊕RK210)(21,20,…,2,1,0)⊕

(X11>>>3)(21,20,…,2,1,0)⊕

RK110,(21,20,…,2,1,0)

(3)

验证X10,(19,18,…,2,1,0)和Y10,(21,20,…,2,1,0)是否为平衡比特,若为平衡比特,则猜测密钥为正确密钥,否则为错误密钥。

步骤8重新选择一组构造10轮积分区分器的明文,重复步骤1～步骤7直至密钥唯一确定。

结合密钥扩展方案和轮密钥的分析,上述攻击共需要猜测119比特密钥信息。对于正确密钥可以保证X10,(27,26,…,1,0)和Y10,(27,26,…,1,0)为平衡比特,错误密钥使X10,(27,26,…,1,0)和Y10,(27,26,…,1,0)为平衡比特的概率为2-42,经过1组明文后剩余错误密钥数目为(2119-1)×2-42≈277,为确定唯一密钥需要3组明文,剩余错误密钥数量为(2119-1)×2-42×3≈2-7。从而攻击数据复杂度为262×3=263.6个明文,时间复杂度为262×(2119+277+235)≈2177次查32比特S盒大表,相当于2177/16=2173次16轮加密。为猜测密钥,攻击需要对猜测密钥进行存储,存储复杂度为2119。由于利用10轮积分区分器向后扩展6轮对LiCi算法进行16轮积分攻击,第10轮输出和第16轮密文信息以及第12～第16轮的轮密钥的每一比特信息均几乎相关,因此未能利用“部分和”技术降低时间复杂度。

根据攻击步骤1～步骤8结合LiCi算法密钥扩展算法可知,利用10轮积分区分器向后扩展2轮～6轮时,攻击时间复杂度均大于2128。

5 结束语

本文将基于比特的积分性质和MILP搜索工具相结合,得到平衡比特数目最多、轮数最长的积分区分器为12轮积分区分器,利用12轮积分区分器对LiCi算法进行13轮积分攻击,攻击数据复杂度约为263,时间复杂度约为2100次16轮加密,存储复杂度约为241。利用“部分和”技术可以将时间复杂度降为283次16轮加密。为得到更长轮数的攻击结果,利用构造的10轮积分区分器向后攻击6轮,对16轮算法实施密钥恢复攻击,攻击数据复杂度约为263.6,时间复杂度约为2173次16轮加密,存储复杂度约为2119。本文在积分攻击层面对LiCi算法进行分析,结果表明,13轮LiCi算法不能抵抗积分攻击。下一步将基于比特的可分性,在搜索积分区分器时对输入可分性的初始值和积分区分器的轮数与平衡比特数目之间的关系进行研究。