陳偉建，羅皓翔

LiCi密碼的差分故障攻擊

陳偉建1，羅皓翔2

（1. 電子科技大學(xué)信息與通信工程學(xué)院，四川 成都 611731；2. 電子科技大學(xué)格拉斯哥學(xué)院，四川 成都 611731）

LiCi輕量級分組密碼算法是2017年提出的一種新型密碼算法，其具有結(jié)構(gòu)微小、消耗能量少等優(yōu)點，適用于物聯(lián)網(wǎng)等資源受限的環(huán)境。在LiCi的設(shè)計文檔中，對該算法抵御差分攻擊和線性攻擊的能力進(jìn)行了分析，但LiCi算法對于差分故障攻擊的抵抗能力尚未得到討論。針對LiCi算法每輪迭代的移位規(guī)律，在第31輪迭代時的左半側(cè)多次注入單比特故障，結(jié)合其差分性質(zhì)，可以恢復(fù)32 bit長度的輪密鑰。根據(jù)LiCi算法的密鑰編排方案，再對第30、29、28、27、26輪迭代進(jìn)行同樣的差分故障攻擊，最終可以恢復(fù)全部原始密鑰。該攻擊共需要48個單比特故障，計算復(fù)雜度為232，說明LiCi算法難以抵抗差分故障攻擊。

LiCi密碼；輕量級分組密碼；差分故障攻擊；故障模型

1 引言

輕量級分組密碼算法因其結(jié)構(gòu)較為簡單、加解密速度快、消耗計算資源較少且利于軟硬件實現(xiàn)等特點，被廣泛應(yīng)用在物聯(lián)網(wǎng)終端中，如RFID、無線傳感器網(wǎng)絡(luò)（WSN）、智能卡等計算資源受限的終端設(shè)備。針對這些設(shè)備信息安全保護(hù)、傳輸?shù)男枨螅姸鄬W(xué)者提出了許多低成本、低能耗的輕量級密碼算法，如HIGHT[1]、PRESENT[2]、GIFT[3]、SPECK[4]、SMS4[5]等，這些算法具有擴(kuò)散快速、加解密一致、易于實現(xiàn)等特點。

2017年，Patil等[6]提出了一種新的輕量級分組密碼算法LiCi。該算法采用了平衡Feistel結(jié)構(gòu)，在LiCi算法的單輪加密結(jié)構(gòu)中，S盒可以影響到左右兩支，相比于普通的Feistel結(jié)構(gòu)分組密碼算法具有更快的擴(kuò)散性，能夠在較少的輪運算下產(chǎn)生數(shù)目最多的活躍S盒。該算法具有64 bit的分組長度和128 bit的密鑰長度，具有結(jié)構(gòu)緊湊、能耗低、占用面積小等特點。另外，LiCi算法可以很好地抵抗差分攻擊和線性攻擊。此后，許多學(xué)者對該算法的密碼安全性進(jìn)行了大量的評估，韋永壯等[7]提出了關(guān)于LiCi的16輪不可能差分分析，數(shù)據(jù)復(fù)雜度為259.76；信文倩等[8]利用12輪積分器對LiCi進(jìn)行13輪攻擊，得到恢復(fù)17 bit輪密鑰的數(shù)據(jù)復(fù)雜度為263；王紅艷等[9]針對LiCi進(jìn)行了積分區(qū)分器的搜索，發(fā)現(xiàn)LiCi存在12輪積分區(qū)分器，所需數(shù)據(jù)復(fù)雜度為261。但該算法能否較好地抵抗差分故障攻擊仍有待進(jìn)一步分析。

差分故障攻擊[10]是Biham和Shamir在1997年結(jié)合數(shù)學(xué)研究方法和物理方法的基礎(chǔ)上，提出的一種新的密碼分析方式。該方法被應(yīng)用在許多經(jīng)典分組密碼上，如GIFT[11]、SMS4[12]、Klein[13]、MIBS[14]、PRESENT[15]、TWINE[16]等。

本文基于LiCi算法本身的移位特性，結(jié)合S盒的差分性質(zhì)，對該算法進(jìn)行了差分故障攻擊。當(dāng)LiCi第31輪左半側(cè)注入單比特故障后，經(jīng)過S盒非線性變換、與右半側(cè)及密鑰進(jìn)行異或操作后，向左移位3 bit。此時故障會擴(kuò)散到新的左半側(cè)的兩個半字節(jié)，因此對一輪迭代中進(jìn)行8次不同位置的單比特故障注入，可以恢復(fù)該輪密鑰，具體的故障注入位置在下文進(jìn)行分析。此外，根據(jù)LiCi密鑰編排方案，需要連續(xù)6輪輪密鑰，才能推出完整的128 bit原始密鑰。因此，以同樣的方式攻擊第30、29、28、27、26輪迭代，共計48個單比特故障。結(jié)果證實LiCi算法在面對差分故障攻擊時并不安全。

2 LiCi密碼算法

2.1 符號與術(shù)語約定

為更好地理解推導(dǎo)過程，下面對本文常用符號進(jìn)行約定和說明。

2.2 LiCi加密流程

LiCi算法具有64 bit的分組長度和128 bit的密鑰長度，迭代輪數(shù)為31輪。該算法的單輪加密流程如圖1所示，包含S盒字節(jié)替換、密鑰異或運算、循環(huán)移位等。其中，字節(jié)替換部分是唯一的非線性運算，由8個并列4乘4的S盒實現(xiàn)。

圖1 LiCi加密流程

Figure 1 LiCi encryption processing

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

S盒變換對應(yīng)值如表1所示。

表1 LiCi的S盒

2.3 LiCi密鑰編排方案

根據(jù)文獻(xiàn)[8]的理論，6輪輪密鑰即可恢復(fù)128 bit原始密鑰的全部信息。因此，本文需對連續(xù)6輪迭代進(jìn)行差分故障攻擊。

3 LiCi算法的性質(zhì)

3.1 S盒差分性質(zhì)

與文獻(xiàn)[7]類似，本文對LiCi的S盒差分分布表進(jìn)行分析。當(dāng)給定輸出差分經(jīng)過S盒逆運算后，其對應(yīng)的輸入差分存在對應(yīng)的概率。若輸出差分為0001，則輸入差分為**11，其輸入差分可能為0011、0111、1011、1111這4種情況，且每種情況對應(yīng)的概率均為(0011)=(0111)=(1011)=(1111)=4/16 =1/4。當(dāng)輸出差分為其他值時，概率計算的方法同理，如表2所示（表中僅列出概率非1/16的部分）。那么在進(jìn)行密鑰恢復(fù)時，利用S盒特殊的輸入輸出差分中存在的概率，可以有效地降低密鑰猜測的復(fù)雜度，有助于密鑰的恢復(fù)。

表2 LiCi的S盒輸入/輸出差分對應(yīng)概率

3.2 密鑰編排性質(zhì)

本文主要針對參與左半側(cè)加密的輪密鑰進(jìn)行密碼學(xué)分析，通過差分故障的方法對左半側(cè)輪密鑰進(jìn)行恢復(fù)。而對于右半側(cè)輪密鑰，需要結(jié)合密碼編排規(guī)律進(jìn)行窮舉猜測。對右半側(cè)32 bit輪密鑰進(jìn)行窮舉的計算復(fù)雜度較高（為232），因此需要分析每兩輪輪密鑰之間的關(guān)系。本文發(fā)現(xiàn)LiCi算法連續(xù)兩輪之間右半側(cè)輪密鑰存在11 bit的重復(fù)區(qū)間，可以有效減少對右半側(cè)輪密鑰的窮舉復(fù)雜度，證明過程如下。

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

3.3 故障擴(kuò)散規(guī)律

LiCi的移位操作可以讓導(dǎo)入的故障進(jìn)行擴(kuò)散，為了提高差分故障攻擊分析的效率，找到合適的故障導(dǎo)入位置，需要對其故障擴(kuò)散規(guī)律進(jìn)行研究。首先考慮左半側(cè)輸出，根據(jù)圖1，左半側(cè)32 bit輸入在依次經(jīng)過S盒變換、與右半側(cè)輪密鑰加密運算、移位操作后，會作為輸出的左半側(cè)32 bit輸出。此外，會與左半側(cè)輪密鑰進(jìn)行加密，并經(jīng)過移位操作后，作為輸出的右半側(cè)輸出。該側(cè)的移位長度為左移3 bit，因此若將故障注入某個半字節(jié)中，在移位操作后故障會擴(kuò)散到左側(cè)相鄰的半字節(jié)中，如圖2所示。

圖2 LiCi左半側(cè)故障擴(kuò)散規(guī)律

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

其次，考慮右半側(cè)輸出，因該側(cè)的移位長度為先向左移3 bit，再向右移7 bit。此外，該側(cè)加密時會與導(dǎo)入故障的S盒直接進(jìn)行異或計算，因此，若將故障注入某個半字節(jié)中，在移位操作后故障會擴(kuò)散到右側(cè)相鄰的半字節(jié)中，如圖3所示。

圖3 LiCi右半側(cè)故障擴(kuò)散規(guī)律

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

圖2和圖3中的紫色部分，為故障擴(kuò)散的位置。借助這一擴(kuò)散規(guī)律，可以通過正確密文與錯誤密文的差分推出對應(yīng)該位置的密鑰值。因S盒是對4 bit長度的半字節(jié)值進(jìn)行代換，因此對一個S盒中故障的導(dǎo)入，1 bit、2 bit、3 bit和4 bit故障產(chǎn)生的效果是相同的?？紤]到故障長度越長，在實際操作中越難實現(xiàn)，本文采用單比特故障進(jìn)行導(dǎo)入。

4 LiCi算法的差分故障攻擊

4.1 攻擊基本假設(shè)

為了更好地進(jìn)行分析，在此提出兩點基本假設(shè)。

4.2 攻擊模型和原理

為便于計算，本文首先選擇在第31輪迭代時S盒操作前導(dǎo)入隨機(jī)故障。

隨機(jī)生成一組明文和密鑰，通過LiCi算法的加密流程得到正確的密文。之后在加密過程的第31輪其中一個半字節(jié)導(dǎo)入單比特故障，結(jié)合差分故障攻擊特點，獲取加密過程中密文的部分特性。進(jìn)一步通過加密算法的逆過程，推導(dǎo)出該輪部分輪密鑰。在同樣的密文和密鑰的條件下，多次重復(fù)上述過程，直到恢復(fù)的部分輪密鑰為唯一值。以相同的方式攻擊第31輪的其他7個半字節(jié)，直到恢復(fù)參與加密的左半側(cè)32 bit輪密鑰，接著對右半側(cè)32 bit輪密鑰進(jìn)行窮舉猜測。根據(jù)LiCi的密鑰更新方案，完整的128 bit原始密鑰可以由6個連續(xù)的輪密鑰推出。通過相同的步驟，分別獲取第30、29、28、27輪的輪密鑰，從而得到LiCi的整個原始密鑰。

4.3 攻擊具體步驟

攻擊步驟如下。

（1）隨機(jī)生成一組明文和密鑰，經(jīng)過31輪的LiCi密碼加密，得到正確的密文。

（2）使用原明文B和密鑰進(jìn)行加密。在LiCi第31輪迭代時，在任一半字節(jié)處誘導(dǎo)一個隨機(jī)的單比特故障，獲取故障密文，并與正確的密文進(jìn)行差分運算，得到兩側(cè)的差分故障密文。

（10）在獲取連續(xù)6輪輪密鑰后，根據(jù)LiCi密鑰編排方案，推出128 bit原始密鑰。

5 復(fù)雜度分析

本文根據(jù)故障傳播特性建立的攻擊方式，相較于對LiCi算法的密鑰進(jìn)行窮舉的方式有一定的優(yōu)化。傳統(tǒng)的窮舉密鑰方法，恢復(fù)出原始密鑰的復(fù)雜度為2128。本文首先對輸出差分的非零半字節(jié)所在位置的可能值進(jìn)行窮舉，再對右半側(cè)輪密鑰進(jìn)行窮舉，可以有效降低攻擊所需的復(fù)雜度。

5.1 數(shù)據(jù)復(fù)雜度

一個單比特故障能恢復(fù)4 bit密鑰，那么恢復(fù)LiCi一輪左半側(cè)32 bit密鑰最少需要8個單比特故障。為了恢復(fù)全部128 bit原始密鑰，需要連續(xù)6輪的輪密鑰，因此共需要48個單比特故障。

5.2 計算復(fù)雜度

6 結(jié)束語

本文提出了一種對LiCi密碼算法的單比特差分故障攻擊方法，通過分析移位操作的規(guī)律，并結(jié)合其差分特性，將單比特故障分別導(dǎo)入加密流程的第26、27、28、29、30和31輪迭代，可恢復(fù)這6輪右側(cè)輪密鑰，再對右側(cè)輪密鑰進(jìn)行窮舉。理論上，完全恢復(fù)原始的128 bit密鑰需要48個單比特故障，計算復(fù)雜度為232。結(jié)論表明，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]國家商用密碼管理辦公室. 無線局域網(wǎng)產(chǎn)品使用的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]. 電子與信息學(xué)報, 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].計算機(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算法的積分區(qū)分器搜索[J]. 小型微型計算機(jī)系統(tǒng), 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]. 計算機(jī)學(xué)報, 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]. 通信學(xué)報, 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]. 電子科技大學(xué)學(xué)報, 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]. 電子科技大學(xué)學(xué)報, 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

電子科技大學(xué)創(chuàng)新創(chuàng)業(yè)院長基金（2019007）

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

陳偉建, 羅皓翔. LiCi密碼的差分故障攻擊[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 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? ），男，浙江杭州人，電子科技大學(xué)教授，主要研究方向為無線與移動通信、物聯(lián)網(wǎng)信息安全、密碼學(xué)理論與技術(shù)。

羅皓翔（1999-），男，四川成都人，主要研究方向為密碼學(xué)理論、區(qū)塊鏈技術(shù)。