陳偉建，羅皓翔

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-），男，四川成都人，主要研究方向為密碼學理論、區塊鏈技術。