LBlock轻量级密码算法的唯密文故障分析

李 玮1,2,3,4吴益鑫1谷大武2曹 珊1廖林峰1孙 莉1刘 亚5刘志强2

1(东华大学计算机科学与技术学院 上海 201620)2(上海交通大学计算机科学与工程系 上海 200240)3(上海市可扩展计算与系统重点实验室(上海交通大学) 上海 200240)4(上海市信息安全综合管理技术研究重点实验室(上海交通大学) 上海 200240)5(上海理工大学计算机科学与工程系 上海 200093)

LBlock算法是在2011年ANCS会议上提出来的一种轻量级分组密码算法.它是一种具有Feistel结构的典型密码,并且广泛应用于物联网安全中.提出了针对Feistel结构的LBlock密码算法的新型唯密文故障分析方法,通过在算法的倒数第4轮导入故障,分别使用6种区分器对算法进行分析.在原有的SEI区分器、GF区分器、GF-SEI双重区分器、MLE区分器基础上,提出了GF-MLE双重区分器和MLE-SEI双重区分器作为新型区分器.仿真实验结果表明:可以在较短的时间内使用较少的故障数且以99%的成功概率恢复出主密钥并破译算法,其中提出的2种新型区分器比原有区分器所需故障数更少、效率更高.由此说明唯密文故障攻击对LBlock算法的安全性构成了巨大的威胁.

关键词轻量级密码;LBlock;唯密文故障攻击;物联网;密码分析

随着信息技术与计算机技术的不断发展,物联网正在逐渐深入到人们各个领域中.物联网将所有物品通过射频识别和红外感应器等信息传感设备与互联网连接起来,将人、数据与实体相联系,实现了人与物、物与物之间的信息交换与通信,以实现遍及智慧城市、智能家居、环境保护、智能交通和个人健康的智能化识别与管理[1-3].如图1所示.轻量级分组密码作为实现消息保密、数据完整性保护和实体认证的核心体制,其设计、分析与实现方法一直是密码学研究的主流,在物联网的安全领域发挥着重要的应用[4].

Fig. 1 The IoT scenario
图1 物联网概况图

LBlock算法是一种Feistel结构的轻量级分组密码算法,具有优良的软硬件实现效率,以及在处理器应用上具有良好的实现性能[5-6],因而可应用于RFID标签和其他低资源设备以保护物联网的安全.前人针对LBlock算法的安全性分析主要致力于传统密码分析,包括不可能差分分析、相关密钥不可能差分分析、截断差分分析、零相关线性分析、积分分析、Biclique分析和侧信道立方分析等多种密码分析方法[7-9].然而,在物联网环境中,单纯从LBlock算法的算法结构研究安全性已经远远不够,攻击者不仅可以进行传统密码分析,而且可以通过电路剖析和软件逆向分析等方式获取密码算法的硬件结构和内部编码方法,借助异常时钟、异常电流、微波辐射、激光照射、涡流磁场等方式干预密码变换的正常过程使其出错,并有可能实现比传统密码分析更有效地破译,从而实现密码算法内数据的复制、篡改或伪造.人们通常把这种攻击称为“故障分析”[10-19].由于其成功的攻击效果和潜在的发展前景,已经引起了国内外从事密码学和微电子领域的研究学者的极大关注,并成为密码工程和密码分析领域发展最为迅速的方向之一.

故障分析在其自身的发展中,逐步衍生出多种攻击方法.1997年,由Biham和Shamir提出的差分故障分析是目前分析范围最广、威胁最大且发展最迅速的一种攻击技术,被广泛应用于密码算法的安全性分析中[20].后来,无效故障分析、碰撞故障分析、不可能故障分析、代数故障分析、中间相遇故障分析、线性故障分析以及唯密文故障攻击等应运而生.它们充分结合了传统密码分析技术以及软硬件实现,具备独特的分析优势,不仅扩大了攻击面,而且提升了威胁性,在面向现实的运行环境下具有更加灵活的应用前景.

在故障分析中,唯密文故障攻击是目前唯一只需要知道错误密文就能进行攻击的技术,在唯密文攻击(ciphertext-only attack, COA)假设下,攻击者通过导入故障得到错误密文,解密密文之后得到中间状态,分析得到的中间状态的特性,就能以低的时间复杂度和数据复杂度推导出正确的密钥.目前,国内外的主要研究是基于代换置换网络(substitution permutation network, SPN)结构的唯密文故障分析方法.那么,具有Feistel结构的典型密码算法是否能够抵抗唯密文故障分析,已引起国内外研究学者的广泛关注.由此,本文提出了一种针对LBlock算法的新型唯密文故障分析方法,在较短时间内以较少故障就能够恢复主密钥,为物联网的安全提供了保障.

1相关工作

Boneh等学者于1997年利用随机故障成功破译RSA算法,此后故障分析在评测密码体制安全性的方法中占据了重要的位置[21].国内外研究学者自2012年起针对LBlock算法相继提出了故障分析方法.2012年,Zhao等学者首次使用差分故障攻击(differential fault analysis, DFA)对LBlock算法进行攻击,在随机单比特故障模型下,通过在加密算法第25~31轮导入7次故障,成功恢复倒数3轮的子密钥,进而恢复了主密钥[22].2013年,Jeong等学者对无线传感网络环境下的LBlock算法提出了改进的差分故障攻击方法,在随机半字节故障模型下,通过在算法的第30轮导入7次故障成功恢复了主密钥,同时在算法的第29轮导入5次故障也成功恢复主密钥,进一步减少了导入故障数[23].2018年,Wei等学者对LBlock算法提出了改进的差分故障攻击方法,在随机半字节故障模型下,通过在算法的第27~29轮导入13.3次故障,成功恢复主密钥,扩展了该方法的攻击轮数[24].2013年,Chen等学者针对LBlock算法提出了积分故障分析(integral fault attack, IFA),在随机半字节故障模型下,通过在算法的第24轮结束时导入120次故障成功恢复了主密钥,同时也提出了在半随机的半字节故障模型下,通过在加密的第23轮结束时在算法的右分支导入32次故障成功恢复了主密钥.该方法成功实现了对算法更深轮数进行攻击,且能够确定故障导入的具体位置[25].上述方法均属于选择明文攻击(chosen-plaintext attack, CPA),而本文针对LBlock提出的唯密文故障攻击(Ciphertext-only Fault Analysis,CFA)是唯一一种在只知道错误密文的情况下就能对算法进行攻击的方法.表1列出了现有的针对LBlock算法的故障分析方法的对比.

2013年,Fuhr等学者基于全零字节模型、半字节模型和随机字节模型,针对AES算法首次提出了唯密文故障攻击方法[26].该方法在算法运行时导入随机故障,使算法执行某些错误的操作,并产生错误的密文,解密密文得到中间状态,利用统计学的知识统计中间状态的分布律,从而恢复最后一轮子密钥.重复上述过程,即可恢复更多的子密钥,直至破译原始密钥.针对AES算法,在随机字节故障模型下,将故障导入在倒数第2轮的指定位置并用平方欧式距离SEI和极大似然估计MLE作为区分器,分别以320个故障和224个故障且99%的成功概率恢复出了AES算法的主密钥.2017年,Li等学者针对LED算法提出了新型的唯密文故障分析,除了Fuhr等人提出的SEI区分器之外,还提出了拟合优度检验GF作为新型区分器,又构建了GF-SEI双重区分器,以更少的故障数成功求得了LED的密钥,提高了故障攻击的效率[27].目前发表的唯密文故障分析都是针对SPN结构的加密算法.因而,Feistel结构密码算法的安全性是目前唯密文故障分析研究的热点.

Table1ComparisonofFaultAnalysisonLBlock
表1针对LBlock算法的故障分析对比

TypeAssumptionModelReferenceDFACPABit/NibbleRef [22-24]IFACPANibbleRef [25]CFACOANibbleThis paper

本文首次提出了针对Feistel结构的LBlock算法的新型唯密文故障分析,并且以更深轮数对算法进行攻击,实现了故障导入在倒数第4轮,在原有SEI区分器、GF区分器、MLE区分器和GF-SEI双重区分器的基础上,提出了GF-MLE双重区分器和MLE-SEI双重区分器统计分析中间状态的分布律,以更少的故障数且99%的成功率恢复了LBlock算法80比特的密钥,提高了故障攻击的效率并减少了故障攻击数.表2为统计故障分析AES算法、LED算法和LBlock算法的唯密文攻击结果对比.其中,Byte和Nibble分别表示字节和半字节故障模型,r表示算法的总轮数.攻击结果总结如下:

Table2ComparisonofCiphertext-OnlyFaultAttacksonaSubkeyofAES,LEDandLBlock
表2LBlock,LED和AES算法唯密文故障分析部分子密钥结果对比

DistinguisherSPNFeistelAES-128LED-128LBlock-80Fault ModelRound#FaultsFault ModelRound#FaultsFault ModelRound#FaultsSEIByter-1320Nibbler-1136Nibbler-351GFNibbler-1128Nibbler-347GF-SEINibbler-196Nibbler-336MLEByter224Nibbler-329GF-MLENibbler-328MLE-SEINibbler-322

1) 唯密文攻击不仅适用于SPN结构的密码算法,对于Feistel结构的密码算法同样可以进行攻击.

2) GF-MLE双重区分器与MLE-SEI双重区分器减少了故障数,提高了攻击效率.

3) 使用这6种区分器进行攻击的轮数在倒数第4轮.

本文首先对唯密文故障攻击的研究现状进行了探讨,接着详细介绍了LBlock算法,然后给出了故障模型与假设,详述唯密文故障攻击过程,最后分析攻击的实验结果并对本文进行总结,附录给出了实验的全部数据.

2LBlock算法

2.1术语说明

P=X1X0为消息明文,其中PX1为消息明文的左分支,X0为消息明文的右分支.C=X32X33为正确密文,为错误密文,其中为算法轮数,K为主密钥,ekd为主密钥K生成的第d轮子密钥,其中0≤dl-1.Xd为第d轮的左分支,也就是第d+1轮的右分支.<<<8为左移8位.

F为轮算法,SLDL分别表示S盒混淆层和P扩散层.SL-1DL-1分别表示S盒混淆层的逆运算和P置换的逆运算.

2.2LBlock密码算法

LBlock密码算法是一种具有Feistel结构的迭代型分组密码,分组长度为64 b,主密钥长度为80 b.迭代轮数为32轮.在加密算法中将消息明文分为32 b等长的左右2个分支.

该算法由3部分组成,分别为加密、解密和密钥编排方案.其中,解密过程是加密过程的逆.下面介绍算法的加密过程.算法结构如图2所示.

Fig. 2 The structure of LBlock
图2 LBlock算法的结构

LBlock算法前31轮都是左右交换操作,最后一轮不包含左右分支交换操作,每一轮变换之后的状态表示为

Xi=F(Xi-1,eki-1)⊕(Xi-2<<<8),

其中,2≤i≤33.在F轮函数中,首先将左分支与轮密钥进行异或运算.其次将左分支的每半个字节经过8个S盒进行置换变成另外一个半字节.之后将经过S混淆层之后的状态按照特定的交换规则,变换到不同的位置.最后密文输出为C=X32X33.

2.3密钥编排方案

密钥编排由3个步骤组成:

1) 选取80 b的主密钥K(ek79,ek78,…,ek0)的左侧32 b密钥(ek79ek78ek47ek46)作为第1轮加密的轮密钥ek0.

2) 对80 b的主密钥进行循环左移29 b操作,将得到的80 b作为新的主密钥.

3) 部分密钥位更新,更新规则如下:

[ek79ek78ek77ek76]=s9[ek79ek78ek77ek76],
[ek75ek74ek73ek72]=s8[ek75ek74ek73ek72],
[ek50ek49ek48ek47ek46]=
[ek50ek49ek48ek47ek46]⊕[i]2

其中,s8,s9均为4位S盒.

3唯密文故障分析

3.1故障模型和基本步骤

本文采用的唯密文故障分析的基本假设为:对随机明文采用同一个密钥进行加密,分析人员可以获得的是密码算法的任意错误密文.

LBlock算法中采用的S盒输入与输出均为4 b,因此本文采用随机半字节故障模型,诱发某一轮的存储单元发生4 b的随机错误.在本节中,导入故障轮数为倒数第4轮.

唯密文故障分析的基本步骤如下:

1) 选择随机明文并使用同一个密钥对其进行加密.当LBlock算法的加密过程运行到倒数第4轮时,导入随机故障,从而获得一组错误的密文.其中,故障导入既可以通过控制硬件实现中的异常时钟、异常电流、微波辐射、激光照射、涡流磁场等手段对真实的密码硬件实现来实现,也可以通过修改程序等软件模拟技术的方式来实现.

2) 解密错误密文得到中间状态.找到中间状态、子密钥和错误密文之间的关系,用关系式正确表达出来.

3) 利用构造的区分器统计中间状态值的分布律.从而恢复倒数3轮的子密钥中的部分位.因为在故障导入之后,加密过程中的某些中间状态值会呈现非均匀分布.

4) 重复上述过程,可以恢复倒数3轮的子密钥的全部位,最后结合密钥编排方案直至破译原始密钥.

3.2具体过程

本文首次提出了用唯密文故障分析的方法对Feistel结构算法进行破译.针对LBlock算法,本文在前人提出的SEI区分器、MLE区分器、GF区分器和GF-SEI双重区分器的基础上又提出了2种新型区分器用于唯密文故障分析.具体过程如下:

1) 使用同一个密钥对随机明文进行加密,在运算过程中的某一轮中导入随机半字节故障,故障导入的位置在倒数第4轮的左分支上8个半字节中的任意半个字节,根据故障导入的位置不同,则扩散路径也各不同,从而根据不同的故障扩散路径求得子密钥的不同的比特值.如图3所示,故障可以导入在X29的任意半个字节,图中阴影表示受故障影响的半字节.图3表示故障导入在X29的第1个半字节后的故障扩散路径.

Fig. 3 Fault diffusion path in the fifth countdown round
图3 故障导入在倒数第4轮后的扩散路径

2) 在运算过程中,中间状态X29的每个半字节都能用子密钥ek31的2个半字节、ek30的1个半字节、ek29的1个半字节和错误密文的4个半字节来表示:

其中,是已知的,所以通过该公式可以将中间状态X29表示出来.

3) 通过区分器对中间状态进行分析,计算出ek29的1个半字节、ek30的1个半字节、ek31的2个半字节.对于每一个子密钥的候选值,根据导入的故障数都能求出一组中间状态值.选择一个区分器,以这组数据为样本,计算出每个密钥候选值所对应的区分器的值,经过比较,区分器值最大或最小所对应的候选值,即为正确子密钥.

4) 将上述过程重复4次,即可恢复出子密钥ek31的8个半字节、ek30的4个半字节、ek29的4个半字节.上述过程重复8次,即可恢复出子密钥ek29ek30ek31的全部位,之后可通过密钥编排方案求出主密钥.

3.3区分器介绍

在3.2节的步骤3中所使用的区分器一共有6种,前4种是以前学者所提出的,后2种是本文所提出的新型区分器.

1) 平方欧氏距离(square euclidean imbalance, SEI)区分器

SEI区分器用于计算未知分布到均匀分布的距离,其中越不服从均匀分布的那一组样本值所对应的密钥候选值,即为所求的子密钥的部分位的解.表达式为

其中,M表示半个字节的所有可能值的个数,因此M=16.γ[m]表示实际得到的中间状态半字节值为m的样本个数;N为导入的故障数;每个密钥候选值都可以通过中间状态呈现的不同的分布律求出对应的SEI值.计算故障导入之后实际得到中间状态半字节值的分布与理论半字节值均匀分布的距离,即为当前样本的SEI值.当得到的SEI数值越大,表示这组样本越不服从均匀分布.因此,攻击者可以计算SEI的最大值来求出正确的候选值.

2) 拟合优度(goodness of fit, GF)区分器

GF区分器的使用条件为已知样本的分布律.攻击者通过比较得到的样本分布律是否满足所讨论模型下的理论分布律.若满足,则可求出子密钥的部分位.其中,4 b故障以按位与方式导入后,分布律如图4所示,并在GF区分器中使用该分布律.区分器表达式为

其中,M表示半个字节的所有可能值的个数;Om表示实际得到的值为m的样本个数;Hm表示在样本总数相同的情况下,值为m中的理论个数.通过区分器表达式可求出样本分布律是否满足理论分布律.其中,M=16,GF所求出的值越小越满足分布,即正确候选值.

Fig. 4 The bitwise-AND distribution of a nibble after fault injections
图4 半字节故障按位与导入后的分布律

3) GF-SEI双重区分器

GF-SEI双重区分器结合了GF区分器与SEI区分器的优点,先用拟合优度检验筛选出满足分布的样本.再用SEI区分器从中寻找最优样本,从而恢复一定的密钥比特.该方法进一步减少了故障数,提高了故障攻击的效率.

4) 极大似然估计(maximum likelihood estimate, MLE)区分器

MLE区分器作为唯密文故障分析的区分器之一适用于已知样本满足某种概率分布的情况下,攻击者计算得到样本出现的概率,当概率最大时,即为所求的子密钥:

其中,N表示故障数,表示倒数第4轮错误的中间状态值;P表示中间状态值出现的概率.概率分布如图4所示.若计算结果越大,则表示该组样本越接近实际概率.

5) GF-MLE区分器

为了减少故障,本文将GF区分器与MLE区分器相结合,构建了一个GF-MLE双重区分器,先用拟合优度检验筛选出符合中间状态值分布的所有样本组.再用MLE区分器从中选出更优样本,即为正确子密钥:


GF(k′)≤χα

其中,k表示子密钥候选值,0≤k≤216m表示每个候选值样本中所对应的所有中间状态值.求出每组样本对应的GF的值之后,我们可以通过自由度df查找上侧位卡方分布2中对应的临界2χα时,样本服从该已知分布.因而本文中M=16,df=M-1=15,使用GF区分器时的样本数量N=50并且Hm≥15时,N越大,恢复子密钥的成功率越高.如果GF>χα,则该候选值不是正确的子密钥的值;攻击者通过GF区分器筛选出满足GFχα的候选值k′,其中,k′⊆k.之后用MLE区分器从中寻找最优样本,从而恢复一定的密钥位.


RK=max(MLE(k′)),

其中,k′表示GF区分器筛选之后的候选值,MLE(k′)表示每组样本对应的MLE值;RK表示正确的候选值.从中选取MLE区分器最大的值,就是正确的子密钥.

6) MLE-SEI区分器

为了更进一步减少故障数,本文构建了一个MLE-SEI双重区分器,将MLE区分器与SEI区分器结合,先用MLE区分器筛选出符合中间状态值分布的一部分样本,再用SEI区分器选出更优样本:


k″=max(MLE(k)),

同上,k表示子密钥候选值,表示每个k所对应的所有中间状态值;k″表示筛选出符合中间状态值分布的一部分样本.


RK=max(SEI(k″)),

其中,m表示每个k″所对应的所有中间状态值,SEI(k″)表示部分样本分别对应的SEI值;从中选取SEI区分器最大的值,就是正确的子密钥.

4实验分析

Fig. 5 The probability of recovering a partial subkey using different faults
图5 不同故障数对应恢复出部分子密钥的概率

本实验在普通PC机器(CPU为Inter Core I7-7700K,4.2 GHz 内存16 GB)上使用Java语言编程进行算法的加解密实现和攻击操作,利用计算机软件来模拟故障的产生,从而得到错误密文,用编程实现从故障导入到唯密文攻击再到最后得到主密钥的全部过程.本文一共进行了1 000次实验,记录了恢复ek31,ek30ek29部分比特的SEI区分器、GF区分器、MLE区分器、GF-SEI和GF-MLE双重区分器所需的故障数和耗费时间.图5表示不同区分器导入不同的故障数所恢复正确密钥部分位的成功概率.其中,横坐标轴表示导入的故障数,纵坐标轴表示恢复出正确子密钥的成功率.图5中有6种不同线段,分别表示使用SEI区分器、GF区分器、GF-SEI双重区分器、MLE区分器、GF-MLE双重区分器和MLE-SEI双重区分器进行唯密文攻击的结果.从实验结果可知,在半字节随机故障模型下,当以99%的概率恢复出过程3中的子密钥时,SEI区分器、GF区分器、GF-SEI双重区分器、MLE区分器、GF-MLE双重区分器和MLE-SEI双重区分器分别需要51,47,36,29,28和22个故障数.由此分析,本文所提出的2种新型区分器可以减少攻击时使用的故障数,并且使用MLE-SEI双重区分器时故障数减少明显.

图6表示分别使用SEI区分器、GF区分器、GF-SEI双重区分器、MLE区分器、GF-MLE双重区分器和MLE-SEI双重区分器破译密钥时间消耗图.其中纵坐标轴表示消耗时间,以秒为单位,横坐标表示导入故障数.从实验结果可知,在半字节的随机故障模型下,6个区分器以99%的成功率破译密钥所需时间分别为130.4 s,87.4 s,50.0 s,43.2 s,37.0 s和28.4 s.不同的区分器所需时间相差较大,其中消耗时间最多的GF区分器,消耗时间是MLE-SEI消耗时间的5倍多.从结果可知,本文中所提出的双重区分器并不会增加消耗的时间,反而减少了消耗时间.

Fig. 6 The time shown with stacked charts of using different faults
图6 不同故障数对应消耗时间的堆积柱形图

由图5和图6可得,从各个区分器对算法的破译情况进一步分析,GF区分器的攻击效果比SEI区分器更佳,而GF-SEI双重区分器的攻击效果比GF和SEI区分器效果更佳,本文中所提出的2种新型区分器的攻击效果都比之前的4种区分器的攻击效果更佳.MLE-SEI双重区分器所需要的导入故障数和耗费的时间比前面5种区分器均明显减少.

5结束语

本文提出并讨论了LBock密码算法抗唯密文故障攻击的安全性.研究结果表明:在面向半字节的故障模型中,与原有的4种区分器相比,本文所提出的2种新型区分器所需故障数更少,故障攻击效率更高;以LBlock为代表的Feistel结构的密码算法易受到统计故障分析的威胁,此方法有助于优化唯密文故障攻击方法的攻击性能,提高故障攻击的效率和实用性.在下一步工作中,我们将进一步深入分析双重区分器的效率以及注入故障的分布律.

参考文献

[1]Alioto M, Shahghasemi M. The Internet of things on its edge: Trends toward its tipping point[J]. IEEE Consumer Electronics Magazine. 2018, 7(1): 77-87

[2]Ning Huansheng, Liu Hong, Yang L T. Cyberentity security in the Internet of things[J]. IEEE Computer, 2013, 46(4): 46-43

[3]Mayer C P. Security and privacy challenges in the Internet of things[J]. Electronic Communications of the European Association of Software Science and Technology, 2009, 17(3): 11-22

[4]Hong D, Sung J, Hong S, et al. HIGHT: A new block cipher suitable for low-resource device[G] //LNCS 4249: Proc of the 8th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2006: 46-59

[5]Wu Wenling, Zhang Lei. LBlock: A lightweight block cipher[G] //LNCS 6715: Proc of the 9th Int Conf on Applied Cryptography and Network Security. Berlin: Springer, 2011: 327-344

[6]Kelsey J, Schneier B, Wagner D A, et al. Side channel cryptanalysis of product ciphers[G] //LNCS 1485: Proc of the 5th Int Conf on Computer Security. Berlin: Springer, 1998: 97-110

[7]Minier M, Naya-Plascencia M. A related key impossible differential attack against 22 rounds of the lightweight block cipher LBlock[J]. Information Processing Letters, 2012, 112(16): 624-629

[8]Soleimany H, Nyberg K. Zero-correlation linear cryptanalysis of reduced-round LBlock[J]. Designs, Codes and Cryptography, 2014, 73(3): 683-698

[9]Zhan Yingjie, Guan Jie, Ding Lin, et al. Related-key impossible differential attack on reduced round LBlock[J]. Journal of Electronic and Information Technology, 2012, 34(9): 2161-2166 (in Chinese)

(詹英杰, 关杰, 丁林, 等. 对简化版LBlock算法的相关密钥不可能差分攻击[J]. 电子与信息学报, 2012, 34(9): 2161-2166)

[10]Boneh D, Demillo R A, Lipton R J. On the importance of checking cryptographic protocols for faults[G] //LNCS 1233: Proc of the 16th Int Conf on Theory and Application of Cryptographic Techniques. Berlin: Springer, 1997: 37-51

[11]Boneh D, Demillo R A, Lipton R J. On the importance of eliminating errors in cryptographic computations[J]. Journal of Cryptology, 2001, 14(2): 101-119

[12]Biehl I, Meyer B, Müller V. Differential fault attacks on elliptic curve cryptosystems[G] //LNCS 1880: Proc of the 20th Int Conf on Advances in Cryptology. Berlin: Springer, 2000: 131-146

[13]Fischer W, Reuter C A. Differential fault analysis on Grøstl[C] //Proc of the 7th Int Workshop on Fault Diagnosis and Tolerance in Cryptography. Piscataway, NJ: IEEE, 2012: 44-54

[14]Hemme L, Hoffmann L. Differential fault analysis on the SHA1 compression function[C] //Proc of the 6th Int Workshop on Fault Diagnosis and Tolerance in Cryptography. Piscataway, NJ: IEEE, 2011: 54-62

[15]Hoch J J, Shamir A. Fault analysis of stream ciphers[G] //LNCS 3156: Proc of the 6th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2004: 240-253

[16]Cnudde T, Nikova S. Securing the PRESENT block cipher against combined side-channel analysis and fault attacks[J]. IEEE Trans on Very Large Scale Integration Systems, 2017, 25(12): 3291-3301

[17]Ghosh S, Saha D, Sengupta A, et al. Preventing fault attacks using fault randomisation with a case study on AES[J]. International Journal of Applied Cryptography, 2017, 3(3): 225-235

[18]Wang An, Zhang Yu, Tian Weina, et al. Right or wrong collision rate analysis without profiling: Full-automatic collision fault attack[J]. Science China Information Sciences, 2018, 61(3): 032101:1-032101:11

[19]Breier J, Hou Xiaolu, Liu Yang. Fault attacks made easy: Differential fault analysis automation on assembly code[J]. IACR Trans on Cryptographic Hardware and Embedded Systems, 2018, 2018(2): 96-122

[20]Biham E, Shamir A. Differential fault analysis of secret key cryptosystems[G] //LNCS 1294: Proc of the 17th Int Conf on Advances in Cryptology. Berlin: Springer, 1997: 513-525

[21]Lin I C, Chang C C. Security enhancement for digital signature schemes with fault tolerance in RSA[J]. Information Sciences, 2007, 177(19): 4031-4039

[22]Zhao Liang, Nishide T, Sakurai K. Differential fault analysis of full LBlock[G] //LNCS 7275: Proc of the 3rd Int Workshop on Constructive Side-Channel Analysis and Secure Design. Berlin: Springer, 2012: 135-150

[23]Jeong K, Lee C, Lim J. Improved differential fault analysis on lightweight block cipher LBlock for wireless sensor networks[J]. EURASIP Journal on Wireless Communications and Networking, 2013, 2013(1): 151-159

[24]Wei Yuechuan, Rong Yisheng, Fan Cunyang. Differential fault attacks on lightweight cipher LBlock[J]. Fundamenta Informaticae, 2018, 157(1/2): 125-139

[25]Chen Hua, Fan Limin. Integral based fault attack on LBlock[G] //LNCS 8565: Proc of the 16th Int Conf on Information Security and Cryptology. Berlin: Springer, 2013: 227-240

[26]Fhur T, Jaulmes E, Lomne V, et al. Fault attacks on AES with faulty ciphertexts only[C] //Proc of the 8th Int Workshop on Fault Diagnosis and Tolerance in Cryptography. Piscataway, NJ: IEEE, 2013: 108-118

[27]Li Wei, Ge Chenyu, Gu Dawu, et al. Research on the LED lightweight cipher against the statistical fault analysis in Internet of Things[J]. Journal of Computer Research and Development, 2017, 54(10): 2205-2214 (in Chinese)

(李玮, 葛晨雨, 谷大武, 等. 物联网环境中LED轻量级密码算法的统计故障分析研究[J]. 计算机研究与发展, 2017, 54(10): 2205-2214)

Ciphertext-OnlyFaultAnalysisoftheLBlockLightweightCipher

Li Wei1,2,3,4, Wu Yixin1, Gu Dawu2, Cao Shan1, Liao Linfeng1, Sun Li1, Liu Ya5, and Liu Zhiqiang2

1(SchoolofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620)2(DepartmentofComputerScienceandEngineering,ShanghaiJiaoTongUniversity,Shanghai200240)3(ShanghaiKeyLaboratoryofScalableComputingandSystems(ShanghaiJiaoTongUniversity),Shanghai200240)4(ShanghaiKeyLaboratoryofIntegrateAdministrationTechnologiesforInformationSecurity(ShanghaiJiaoTongUniversity),Shanghai200240)5(DepartmentofComputerScienceandEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093)

AbstractThe lightweight cipher LBlock was proposed at ANCS in 2011. It has the structure of Feistel and is widely applied in the security of Internet of things (IoT). In this paper, a cipher-text fault analysis for LBlock cipher by injecting faults is proposed, and it is analyzed by 6 distinguishers in the last but 3 rounds. On the basis of original distinguishers as SEI, GF, GF-SEI, MLE, we propose GF-MLE and MLE-SEI distinguishers as new distinguishers. The simulation experiments show that the secret key can be recovered with over 99% success probability in a short period of time, and these two new distinguishers can not only improve the attacking efficiency, but also decrease the number of faults. This shows that the ciphertext-only fault analysis poses a great threat to the security of LBlock cipher.

Keywordslightweight cipher; LBlock; ciphertext-only fault analysis; Internet of things (IoT); cryptanalysis

通信作者孙莉(sli@dhu.edu.cn)

This work was supported by the National Natural Science Foundation of China (61772129) and the National Cryptography Development Fund (MMJJ20180101).

基金项目国家自然科学基金项目(61772129);国家密码发展基金项目(MMJJ20180101)

修回日期:2018-08-06

收稿日期2018-06-12;

中图法分类号TP309.7

(liwei.cs.cn@gmail.com)

LiWei, born in 1980. PhD, professor. Senior member of CCF. Her main research interests include the design and analysis of symmetric ciphers.

WuYixin, born in 1995. Master candidate. Her main research interests include security analysis of block ciphers.

GuDawu, born in 1970. PhD, professor and PhD supervisor. His research interests cover cryptology and computer security.

CaoShan, born in 1995. Master candidate. Her main research interests include security analysis of lightweight ciphers.

LiaoLinfeng, born in 1993. Master candidate. His main research interests include security analysis of symmetric ciphers.

SunLi, born in 1964. PhD, associate professor. Her main research interests include Internet of things.

LiuYa, born in 1983. PhD, lecturer. Her main research interests include the design and analysis of symmetric ciphers and computational number theory.

LiuZhiqiang, born in 1977. PhD, associate professor. His main research interests include cryptanalysis and design of block ciphers and hash functions.

附录A. 实验数据及结果.

明文:随机生成.

密钥:01 23 45 67 89 AB CD EF FE DC

实验结果:6种区分器均能恢复主密钥,实验数据如表A1和表A2所示.

TableA1ProbabilityofBreakingLBlockUsingDifferentDistinguishers

表A1不同区分器破译LBlock的成功概率

FaultsBeaking Probablity/%SEIGFGF-SEIMLEGF-MLEMLE-SEI0000000100000020000003000000400026050524213600370217138132208241014832931171753610042322831114529185401253282515471353283216601436403018631586384014641666343523831711849372879181115495928831981460664084201620635637872116236269388922212372694992232923697550942415317680439525282279775796263638868365982730298580739728343988907198293141939375993040529191829931424192867998

Continued(TableA1)

FaultsBeaking Probablity/%SEIGFGF-SEIMLEGF-MLEMLE-SEI324956949183100335261948988100345858989789100355267999488983661679696949937556296968510038646497958910039557199959510040678199979310041786799959510042738099969510043807899969810044768510095981004578811009810010046848810099961004787909998961004887909910096100498394100100961005088891009997100519193100100951005295931009698100538895100969910054929610010097100559597100989810056919510097981005796991009999100589497100979910059919710099991006094991001009910061979410010097100621009610010010010063999810010098100649798100100991006599971009998100669999991009910067100100100100100100689998100100100100699999100100991007010010010099100100

TableA2TimeofBreakingLBlockUsingDifferentDistinguishers

表A2不同区分器破译LBlock的消耗时间

FaultsLatency Time/sSEIGFGF-SEIMLEGF-MLEMLE-SEI00.00.00.00.00.00.017.593.626.74.919.82.827.694.98.45.39.63.637.695.06.07.66.84.8410.194.97.011.38.55.9512.590.88.514.410.57.1613.989.99.815.211.68.3716.894.911.117.113.59.7819.8102.812.620.914.610.9920.397.913.820.315.612.11026.0107.315.025.016.813.41123.199.716.522.418.214.51219.779.917.920.719.315.81323.484.919.223.620.617.21422.580.720.622.321.818.51523.778.522.023.623.119.91624.478.223.524.124.620.81727.783.724.727.625.621.91829.083.526.328.927.023.31930.385.827.530.828.124.62030.583.828.730.429.225.62131.283.730.531.130.926.92234.287.131.633.431.928.42336.189.033.135.633.529.52437.189.134.437.234.630.82541.494.235.740.835.831.92639.992.237.240.237.033.12743.195.238.343.238.234.52843.694.939.743.539.635.62945.698.040.747.140.536.73048.5100.841.949.041.838.13148.2101.643.348.843.239.33254.2107.044.753.644.540.63353.9107.546.154.746.041.73456.9109.547.657.647.542.8

Continued(TableA2)

FaultsLatency Time/sSEIGFGF-SEIMLEGF-MLEMLE-SEI3561.2113.648.862.648.744.23660.3113.550.060.949.946.03762.2115.251.462.551.247.23863.8116.252.764.152.647.93965.4118.254.365.854.149.14070.0123.055.470.655.350.34177.9130.356.779.456.551.74279.3131.458.680.258.352.94378.0130.259.479.659.254.24475.6126.260.876.460.655.44565.5114.862.465.862.256.74676.5130.163.777.163.557.94777.1130.464.777.964.759.64872.0123.666.472.366.260.74972.9125.267.873.367.761.55083.1139.068.883.668.762.85184.7141.270.985.371.164.15287.3144.671.987.971.865.25386.7141.172.987.873.166.65494.5154.374.495.374.568.25597.2157.376.098.575.869.75698.4158.477.099.376.871.95799.9160.578.7100.878.371.458100.6155.680.3101.480.472.259101.1161.281.5102.181.473.66093.6145.082.895.582.875.66182.7131.884.183.083.8144.96284.2133.385.484.885.3119.86386.5136.586.986.486.5125.06493.9146.688.594.188.4115.66594.1145.790.195.590.1103.36695.2146.392.195.991.999.46795.0146.6110.395.8109.9100.46891.7141.5112.892.5112.2102.26992.8143.1117.293.9116.3103.47094.1148.7118.195.9117.7105.0