LiCi密码的差分故障攻击

陈伟建，罗皓翔

LiCi密码的差分故障攻击

陈伟建1，罗皓翔2

（1. 电子科技大学信息与通信工程学院，四川 成都 611731；2. 电子科技大学格拉斯哥学院，四川 成都 611731）

LiCi轻量级分组密码算法是2017年提出的一种新型密码算法，其具有结构微小、消耗能量少等优点，适用于物联网等资源受限的环境。在LiCi的设计文档中，对该算法抵御差分攻击和线性攻击的能力进行了分析，但LiCi算法对于差分故障攻击的抵抗能力尚未得到讨论。针对LiCi算法每轮迭代的移位规律，在第31轮迭代时的左半侧多次注入单比特故障，结合其差分性质，可以恢复32 bit长度的轮密钥。根据LiCi算法的密钥编排方案，再对第30、29、28、27、26轮迭代进行同样的差分故障攻击，最终可以恢复全部原始密钥。该攻击共需要48个单比特故障，计算复杂度为232，说明LiCi算法难以抵抗差分故障攻击。

LiCi密码；轻量级分组密码；差分故障攻击；故障模型

1 引言

轻量级分组密码算法因其结构较为简单、加解密速度快、消耗计算资源较少且利于软硬件实现等特点，被广泛应用在物联网终端中，如RFID、无线传感器网络（WSN）、智能卡等计算资源受限的终端设备。针对这些设备信息安全保护、传输的需求，众多学者提出了许多低成本、低能耗的轻量级密码算法，如HIGHT[1]、PRESENT[2]、GIFT[3]、SPECK[4]、SMS4[5]等，这些算法具有扩散快速、加解密一致、易于实现等特点。

2017年，Patil等[6]提出了一种新的轻量级分组密码算法LiCi。该算法采用了平衡Feistel结构，在LiCi算法的单轮加密结构中，S盒可以影响到左右两支，相比于普通的Feistel结构分组密码算法具有更快的扩散性，能够在较少的轮运算下产生数目最多的活跃S盒。该算法具有64 bit的分组长度和128 bit的密钥长度，具有结构紧凑、能耗低、占用面积小等特点。另外，LiCi算法可以很好地抵抗差分攻击和线性攻击。此后，许多学者对该算法的密码安全性进行了大量的评估，韦永壮等[7]提出了关于LiCi的16轮不可能差分分析，数据复杂度为259.76；信文倩等[8]利用12轮积分器对LiCi进行13轮攻击，得到恢复17 bit轮密钥的数据复杂度为263；王红艳等[9]针对LiCi进行了积分区分器的搜索，发现LiCi存在12轮积分区分器，所需数据复杂度为261。但该算法能否较好地抵抗差分故障攻击仍有待进一步分析。

差分故障攻击[10]是Biham和Shamir在1997年结合数学研究方法和物理方法的基础上，提出的一种新的密码分析方式。该方法被应用在许多经典分组密码上，如GIFT[11]、SMS4[12]、Klein[13]、MIBS[14]、PRESENT[15]、TWINE[16]等。

本文基于LiCi算法本身的移位特性，结合S盒的差分性质，对该算法进行了差分故障攻击。当LiCi第31轮左半侧注入单比特故障后，经过S盒非线性变换、与右半侧及密钥进行异或操作后，向左移位3 bit。此时故障会扩散到新的左半侧的两个半字节，因此对一轮迭代中进行8次不同位置的单比特故障注入，可以恢复该轮密钥，具体的故障注入位置在下文进行分析。此外，根据LiCi密钥编排方案，需要连续6轮轮密钥，才能推出完整的128 bit原始密钥。因此，以同样的方式攻击第30、29、28、27、26轮迭代，共计48个单比特故障。结果证实LiCi算法在面对差分故障攻击时并不安全。

2 LiCi密码算法

2.1 符号与术语约定

为更好地理解推导过程，下面对本文常用符号进行约定和说明。

2.2 LiCi加密流程

LiCi算法具有64 bit的分组长度和128 bit的密钥长度，迭代轮数为31轮。该算法的单轮加密流程如图1所示，包含S盒字节替换、密钥异或运算、循环移位等。其中，字节替换部分是唯一的非线性运算，由8个并列4乘4的S盒实现。

图1 LiCi加密流程

Figure 1 LiCi encryption processing

其加密过程可由下式表示。

S盒变换对应值如表1所示。

表1 LiCi的S盒

2.3 LiCi密钥编排方案

根据文献[8]的理论，6轮轮密钥即可恢复128 bit原始密钥的全部信息。因此，本文需对连续6轮迭代进行差分故障攻击。

3 LiCi算法的性质

3.1 S盒差分性质

与文献[7]类似，本文对LiCi的S盒差分分布表进行分析。当给定输出差分经过S盒逆运算后，其对应的输入差分存在对应的概率。若输出差分为0001，则输入差分为**11，其输入差分可能为0011、0111、1011、1111这4种情况，且每种情况对应的概率均为(0011)=(0111)=(1011)=(1111)=4/16 =1/4。当输出差分为其他值时，概率计算的方法同理，如表2所示（表中仅列出概率非1/16的部分）。那么在进行密钥恢复时，利用S盒特殊的输入输出差分中存在的概率，可以有效地降低密钥猜测的复杂度，有助于密钥的恢复。

表2 LiCi的S盒输入/输出差分对应概率

3.2 密钥编排性质

本文主要针对参与左半侧加密的轮密钥进行密码学分析，通过差分故障的方法对左半侧轮密钥进行恢复。而对于右半侧轮密钥，需要结合密码编排规律进行穷举猜测。对右半侧32 bit轮密钥进行穷举的计算复杂度较高（为232），因此需要分析每两轮轮密钥之间的关系。本文发现LiCi算法连续两轮之间右半侧轮密钥存在11 bit的重复区间，可以有效减少对右半侧轮密钥的穷举复杂度，证明过程如下。

由式(2)~式(5)可知更新后的128 bit密钥为

3.3 故障扩散规律

LiCi的移位操作可以让导入的故障进行扩散，为了提高差分故障攻击分析的效率，找到合适的故障导入位置，需要对其故障扩散规律进行研究。首先考虑左半侧输出，根据图1，左半侧32 bit输入在依次经过S盒变换、与右半侧轮密钥加密运算、移位操作后，会作为输出的左半侧32 bit输出。此外，会与左半侧轮密钥进行加密，并经过移位操作后，作为输出的右半侧输出。该侧的移位长度为左移3 bit，因此若将故障注入某个半字节中，在移位操作后故障会扩散到左侧相邻的半字节中，如图2所示。

图2 LiCi左半侧故障扩散规律

Figure 2 Fault-diffusion law of LiCi on the left side

其次，考虑右半侧输出，因该侧的移位长度为先向左移3 bit，再向右移7 bit。此外，该侧加密时会与导入故障的S盒直接进行异或计算，因此，若将故障注入某个半字节中，在移位操作后故障会扩散到右侧相邻的半字节中，如图3所示。

图3 LiCi右半侧故障扩散规律

Figure 3 Fault-diffusion law of LiCi on the right side

图2和图3中的紫色部分，为故障扩散的位置。借助这一扩散规律，可以通过正确密文与错误密文的差分推出对应该位置的密钥值。因S盒是对4 bit长度的半字节值进行代换，因此对一个S盒中故障的导入，1 bit、2 bit、3 bit和4 bit故障产生的效果是相同的。考虑到故障长度越长，在实际操作中越难实现，本文采用单比特故障进行导入。

4 LiCi算法的差分故障攻击

4.1 攻击基本假设

为了更好地进行分析，在此提出两点基本假设。

4.2 攻击模型和原理

为便于计算，本文首先选择在第31轮迭代时S盒操作前导入随机故障。

随机生成一组明文和密钥，通过LiCi算法的加密流程得到正确的密文。之后在加密过程的第31轮其中一个半字节导入单比特故障，结合差分故障攻击特点，获取加密过程中密文的部分特性。进一步通过加密算法的逆过程，推导出该轮部分轮密钥。在同样的密文和密钥的条件下，多次重复上述过程，直到恢复的部分轮密钥为唯一值。以相同的方式攻击第31轮的其他7个半字节，直到恢复参与加密的左半侧32 bit轮密钥，接着对右半侧32 bit轮密钥进行穷举猜测。根据LiCi的密钥更新方案，完整的128 bit原始密钥可以由6个连续的轮密钥推出。通过相同的步骤，分别获取第30、29、28、27轮的轮密钥，从而得到LiCi的整个原始密钥。

4.3 攻击具体步骤

攻击步骤如下。

（1）随机生成一组明文和密钥，经过31轮的LiCi密码加密，得到正确的密文。

（2）使用原明文B和密钥进行加密。在LiCi第31轮迭代时，在任一半字节处诱导一个随机的单比特故障，获取故障密文，并与正确的密文进行差分运算，得到两侧的差分故障密文。

（10）在获取连续6轮轮密钥后，根据LiCi密钥编排方案，推出128 bit原始密钥。

5 复杂度分析

本文根据故障传播特性建立的攻击方式，相较于对LiCi算法的密钥进行穷举的方式有一定的优化。传统的穷举密钥方法，恢复出原始密钥的复杂度为2128。本文首先对输出差分的非零半字节所在位置的可能值进行穷举，再对右半侧轮密钥进行穷举，可以有效降低攻击所需的复杂度。

5.1 数据复杂度

一个单比特故障能恢复4 bit密钥，那么恢复LiCi一轮左半侧32 bit密钥最少需要8个单比特故障。为了恢复全部128 bit原始密钥，需要连续6轮的轮密钥，因此共需要48个单比特故障。

5.2 计算复杂度

6 结束语

本文提出了一种对LiCi密码算法的单比特差分故障攻击方法，通过分析移位操作的规律，并结合其差分特性，将单比特故障分别导入加密流程的第26、27、28、29、30和31轮迭代，可恢复这6轮右侧轮密钥，再对右侧轮密钥进行穷举。理论上，完全恢复原始的128 bit密钥需要48个单比特故障，计算复杂度为232。结论表明，LiCi密码算法不能很好地抵抗本文所提出的差分故障攻击。

[1]HONG D, SUNG J , HONG S , et al. HIGHT: a new block cipher suitable for low-resource device[C]//CHES 2006: 46-59.

[2]BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: an ultra-lightweight block cipher[C]//Proceeding of 9th International Workshop on Cryptographic Hardware and Embedded System. 2007: 450-466.

[3]BANIK S, PANDEY S K, PEYRIN T, et al. Gif: a small present[C]// Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded System. 2017: 321-345.

[4]BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and SPECK lightweight block ciphers[C]//Proceedings of the 52nd Annual Design Automation Conference. 2015: 175:1-175:6.

[5]国家商用密码管理办公室. 无线局域网产品使用的SMS4密码算法[EB].

Office of State Commercial Cipher Administration. Block cipher for WLAN products-SMS4[EB].

[6]PATIL J, BANSOD G, KANT K S. LiCi: a new ultra-lightweight block cipher[C]//International Conference on Emerging Trends & Innovation in Ict. 2017: 40-45.

[7]韦永壮, 史佳利, 李灵琛. LiCi分组密码算法的不可能差分分析[J]. 电子与信息学报, 2019, 41(7): 1610-1617.

WEI Y Z, SHI J L, LI L C. Impossible differential cryptanalysis of LiCi block cipher[J]. Journal of Electronics & Information Technology, 2019, 41(7):1610-1617.

[8]信文倩, 孙兵, 李超. LiCi算法的基于比特积分攻击[J].计算机工程, 2020, 46(7).

XIN W Q, SUN B, LI C. Bit-based integral attack on LiCi[J]. Computer Engineering, 2020, 46(7).

[9]王红艳, 韦永壮, 刘文芬. ANU, ANU-II和LiCi算法的积分区分器搜索[J]. 小型微型计算机系统, 2020, 41(7): 1470-1475.

WANG H Y, WEI Y Z, LIU W F. Integral distinguisher search of ANU, ANU-II and LiCi block ciphers[J]. Journal of Chinese Com- puter Systems, 2020, 41(7): 1470-1475.

[10]BIHAM E, SHAMIR A. Differential fault analysis of secret key cryptosystems[C]//1997 Annual International Cryptology Conference. 1997: 513-525.

[11]LUO H X, CHEN W J, MING X Y, WU Y F. General differential fault attack on PRESENT and GIFT cipher with nibble[J]. IEEE Access, 2021.

[12]张蕾, 吴文玲. SMS4密码算法的差分故障攻击[J]. 计算机学报, 2006(9): 1596-1602.

ZHANG L, WU W L. Differential fault analysis on SMS4[J]. Chinese Journal of Computers, 2006(9): 1596-1602.

[13]王永娟, 任泉宇, 张诗怡. 轻量级分组密码Klein的差分故障攻击[J]. 通信学报, 2016, 37(S1): 111-115.

WANG Y J, REN Q Y, ZHANG S Y. Differential fault attack on lightweight block cipher Klein[J]. Journal on Communications, 2016, 37(S1): 111-115.

[14]王永娟, 张诗怡, 王涛, 等. 对MIBS分组密码的差分故障攻击[J]. 电子科技大学学报, 2018, 47(4): 601-605.

WANG Y J, ZHANG S Y, WANG T, et al. Differential fault attack on block cipher MIBS[J]. Journal of University of Electronic Science and Technology of China, 2018, 47(4): 601-605.

[15]陈伟建, 赵思宇, 邹瑞杰, 等. PRESENT密码的差分故障攻击[J]. 电子科技大学学报, 2019, 48(6): 865-869.

CHEN W J, ZHAO S Y, ZOU R J, et al. The differential fault attack of PRESENT cipher[J]. Journal of University of Electronic Science and Technology of China, 2019, 48(6): 865-869.

[16]LUO H X, WU Y F, CHEN W J. Differential fault attack on TWINE block cipher with nibble[C]//2020 IEEE 20th International Conference on Communication Technology (ICCT). 2020: 1151-1155.

Differential fault attack on LiCi cipher

CHEN Weijian1, LUO Haoxiang2

1. School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China 2. Glasgow College, University of Electronic Science and Technology of China, Chengdu 611731, China

LiCi lightweight block cipher is a new algorithm proposed in 2017. With advantages of small structure and low energy consumption, LiCi is more suitable for resource-constrained environments such as the internet of things(IoT). In the design document of LiCi, the ability of LiCi algorithm to resist differential attack and linear attack is analyzed, but the resistance of LiCi algorithm to differential fault attack has not been discussed. According to the permutation law of each round iteration of LiCi algorithm, 32-bit key can be recovered by injecting a single bit fault into the left half of the 31st round iteration combined with its differential property. According to the key choreography scheme of the LiCi algorithm, the same differential fault attack was performed on iterations 30th, 29th, 28th, 27th and 26th round to recover all the original keys. The attack requires a total of 48-bit faults, and the computational complexity is 232, which indicates the LiCi algorithm is difficult to resist differential fault attacks.

LiCi cipher, lightweight block cipher, differential fault attack, fault model

TP309

A

10.11959/j.issn.2096−109x.2021033

2020−08−04；

2020−12−07

罗皓翔，lhx991115@163.com

电子科技大学创新创业院长基金（2019007）

Dean's Fund of Innovation and Entrepreneurship, UESTC (2019007)

陈伟建, 罗皓翔. LiCi密码的差分故障攻击[J]. 网络与信息安全学报, 2021, 7(2): 104-109.

CHEN W J, LUO H X. Differential fault attack on LiCi cipher[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 104-109.

陈伟建（1956− ），男，浙江杭州人，电子科技大学教授，主要研究方向为无线与移动通信、物联网信息安全、密码学理论与技术。

罗皓翔（1999-），男，四川成都人，主要研究方向为密码学理论、区块链技术。