輕量級(jí)分組密碼SLIM 的差分故障攻擊*

高 楊, 王永娟, 高光普, 袁慶軍, 王 燦

1. 戰(zhàn)略支援部隊(duì)信息工程大學(xué), 鄭州 450001

2. 河南省網(wǎng)絡(luò)密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室, 鄭州 450001

1 引言

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展, 當(dāng)前各行業(yè)對(duì)硬件相關(guān)產(chǎn)業(yè)的需求愈發(fā)旺盛. 在以智能芯片為首的硬件平臺(tái)中, 傳統(tǒng)密碼算法暴露出硬件實(shí)現(xiàn)成本代價(jià)高和電路耗費(fèi)開(kāi)支大的現(xiàn)實(shí)問(wèn)題. 為應(yīng)對(duì)該問(wèn)題, 近年來(lái)學(xué)界提出了一些適用于這類(lèi)資源受限設(shè)備的分組密碼算法, 即輕量級(jí)分組密碼算法. 相較傳統(tǒng)分組密碼算法, 輕量級(jí)密碼使用更簡(jiǎn)單的組件以減少實(shí)現(xiàn)所需的硬件成本, 同時(shí)采取更多的迭代輪數(shù)以保證其實(shí)現(xiàn)安全. 在低功耗情況下, 輕量級(jí)分組密碼算法僅需要少量硬件和軟件資源, 便可為設(shè)備提供安全性加密保障.常見(jiàn)的輕量級(jí)算法包括LBlock[1]、Piccolo[2]、TWINE[3]、MIBS[4]、PRESENT[5]等, 這些算法在設(shè)計(jì)時(shí)往往考慮到已有的傳統(tǒng)攻擊方法, 同時(shí)保證硬件高效實(shí)現(xiàn), 以達(dá)到安全和效率的平衡.

故障攻擊由Boneh 等人[6]于1996 年提出用于攻擊RSA 簽名算法. 1997 年, Biham 等人[7]改進(jìn)形成差分故障分析方法, 并憑借這種新方法成功攻擊了分組密碼DES 算法. 差分故障攻擊將側(cè)信道攻擊和傳統(tǒng)密碼分析思想結(jié)合, 對(duì)基于硬件實(shí)現(xiàn)的輕量級(jí)密碼算法攻擊效果顯著, 近年來(lái), 人們不斷提出新的差分故障攻擊方法, 成功分析了LED[8]、SIMON[9]、FeW[10]、SM4[11]、KLEIN[12]等密碼算法.

輕量級(jí)分組密碼的基本數(shù)據(jù)單元均為半字節(jié), 因此往往采用半字節(jié)故障注入模型對(duì)其進(jìn)行差分故障分析. 2010 年, Wang 等[13]首次提出將單個(gè)隨機(jī)半字節(jié)故障注入PRESENT 算法的密鑰擴(kuò)展方案, 結(jié)合其他密碼分析方法恢復(fù)全輪密鑰. 另一方面, 學(xué)者對(duì)實(shí)際攻擊中半字節(jié)故障注入的實(shí)現(xiàn)展開(kāi)分析研究. 2013年, Moro 等[14]提出了強(qiáng)電磁場(chǎng)故障注入技術(shù). 針對(duì)一些實(shí)際的現(xiàn)場(chǎng)可編程門(mén)陣列和專(zhuān)用集成電路芯片上的實(shí)驗(yàn)表明, 該方法可以產(chǎn)生若干半字節(jié)故障. 2014 年, Endo 等[15]研究了多點(diǎn)激光注入, 即在運(yùn)行的密碼模塊兩處或多處同時(shí)注入故障, 可在算法的一輪或幾輪產(chǎn)生多個(gè)半字節(jié)故障. 考慮到SLIM 算法每輪中間狀態(tài)與S 盒數(shù)據(jù)處理單元均為半字節(jié), 本文采用基于多個(gè)半字節(jié)的隨機(jī)故障注入模型進(jìn)行分析.

輕量級(jí)分組密碼算法SLIM[16]由Aboushosha 等人于2020 年提出, 分組長(zhǎng)度為32 比特, 密鑰長(zhǎng)度為80 比特. 該算法采用典型的Feistel 結(jié)構(gòu), 所需硬件成本僅為553 等效門(mén)電路, 適用于物聯(lián)網(wǎng)環(huán)境下的射頻識(shí)別標(biāo)簽及智能卡的防護(hù). 由于SLIM 算法面世時(shí)間較短, 目前僅有文獻(xiàn)[16] 對(duì)其抗線性攻擊和差分攻擊的安全性進(jìn)行了分析. 本文采用差分故障攻擊方法對(duì)SLIM 算法展開(kāi)研究, 主要成果和創(chuàng)新點(diǎn)如下:基于SLIM 算法的故障擴(kuò)散規(guī)律, 分別在第2 至32 輪注入寬度為1 至4 個(gè)半字節(jié)的故障, 最少注入62組故障即可將主密鑰恢復(fù)的計(jì)算復(fù)雜度降低至23; 在此基礎(chǔ)上, 結(jié)合S 盒差分分布特性對(duì)差分故障攻擊的成功率進(jìn)行定量分析, 計(jì)算出各輪輪密鑰的恢復(fù)概率及主密鑰恢復(fù)故障注入組數(shù)期望值68.15, 對(duì)差分故障攻擊的理論研究和SLIM 算法的軟硬件實(shí)現(xiàn)方面均有一定指導(dǎo)意義; 通過(guò)1000 次仿真模擬實(shí)驗(yàn), 得到恢復(fù)主密鑰故障注入組數(shù)均值69.07 組, 與理論值較為接近.

2 SLIM 算法簡(jiǎn)介

2.1 符號(hào)說(shuō)明

本文所用符號(hào)如表1 所示.

表1 符號(hào)說(shuō)明Table 1 Symbol description

2.2 SLIM 算法介紹

SLIM 算法是Aboushosha 等人[16]于2020 年提出的一種基于Feistel 結(jié)構(gòu)的輕量級(jí)分組密碼算法,其分組長(zhǎng)度為32 比特, 主密鑰長(zhǎng)度為80 比特, 迭代輪數(shù)為32 輪, SLIM 算法中所有迭代操作都是基于半字節(jié)的. 令M=L0||R0表示32 比特明文, 則中間狀態(tài)為L(zhǎng)i=Ri-1,Ri=F(Ri-1)⊕Li-1,i=1,2,··· ,31, 密文輸出可表示為C=L32||R32=F(R31)⊕L31||R31, 加密流程如圖1 所示. 輪函數(shù)F如圖2 所示, 其中混淆層S 是輪函數(shù)F 的非線性組件, 并列排布著4 個(gè)相同的4×4 S 盒, 見(jiàn)表2.

圖1 SLIM 算法結(jié)構(gòu)Figure 1 Structure of SLIM algorithm

圖2 SLIM 算法輪函數(shù)示意圖Figure 2 Schematic diagram of round function

表2 SLIM 算法S 盒Table 2 S-box of SLIM algorithm

SLIM 算法P 層基于半字節(jié)置換, 如下所示.

SLIM 算法的密鑰擴(kuò)展方案設(shè)計(jì)思路較為獨(dú)特, 其主密鑰為80 比特, 記為MK = mk79mk78···mk0.首先將主密鑰劃為5 等份, 分別作為前5 輪輪密鑰, 即K1= mk15mk14···mk0,K2= mk31mk30···mk16,K3=mk47mk46···mk32,K4=mk63mk62···mk48,K5=mk79mk78···mk64, 再將MK 存儲(chǔ)于兩個(gè)長(zhǎng)度為40 比特的寄存器中, 即MK=MSB||LSB, 每輪寄存器執(zhí)行下列偽代碼(算法1), 并輸出16比特輪密鑰K.

算法1 密鑰擴(kuò)展算法Input: MSB, LSB Output: Ki 1 for i ＜= 32 do 2LSB = (LSB ?2)⊕MSB;3LSB = S[LSB39LSB38LSB37LSB36] || ··· || S[LSB3LSB2LSB1LSB0];4MSB = LSB ⊕(MSB ?3);5Ki = MSB[15 : 0];6i = i+1;7 end

3 SLIM 算法結(jié)構(gòu)性質(zhì)

3.1 SLIM 算法故障擴(kuò)散規(guī)律

圖3 SLIM 算法故障擴(kuò)散實(shí)例Figure 3 Example of fault propagation process in SLIM algorithm

3.2 SLIM 算法S 盒差分分布情況

在SLIM 算法中, 輪函數(shù)的非線性變換復(fù)雜性基于4 比特S 盒. 因此, 研究S 盒的差分分布特性是很有必要的. 給定α ∈F42(α／=0),m ∈F42, 且滿(mǎn)足S(m ⊕α)⊕S(m)=β, 則稱(chēng)m為S 盒輸入值,α為S盒輸入差分,β為S 盒輸出差分. SLIM 算法S 盒在輸入差分一定情況下輸出差分與輸入值的對(duì)應(yīng)關(guān)系如表4 所示.

表4 SLIM 算法S 盒差分分布表Table 4 Differential distribution table of S-box in SLIM

觀察該表, 容易歸納出SLIM 算法S 盒的差分分布統(tǒng)計(jì)特性:

(1) 固定輸入值m, 共有15 種可能的“輸入-輸出”差分對(duì)(Din,Dout), 且Din與Dout分別遍歷0x1到0xF 這15 個(gè)數(shù);

(2) 當(dāng)m一定時(shí), (1) 中的15 組(Din,Dout) 有3 組對(duì)應(yīng)可能輸入值記為集合Y1, 3 組對(duì)應(yīng)可能輸入值記為集合Y2, #Y1=#Y2=4; 其余9 組對(duì)應(yīng)可能輸入值記為集合Zi(i=1,2,··· ,9),#Zi=2;

(3)Y1∩Y2=m;

(4)Zi ∩Zj=m,(i,j=1,2,··· ,9);

(5) 固定輸入差分Din, 對(duì)應(yīng)輸出差分Dout可能有4, 6, 7, 8 種取值, 不存在Dout為5 種的情況.

4 SLIM 算法的差分故障攻擊

本文采用基于多個(gè)半字節(jié)的隨機(jī)故障注入模型對(duì)SLIM 算法進(jìn)行分析, 在此給出攻擊條件以及具體假設(shè):

(1) 攻擊者可以完全掌握密碼設(shè)備, 可在加密過(guò)程中任意時(shí)刻任意位置注入若干半字節(jié)的隨機(jī)故障.故障值非零, 但具體值未知.

(2) 攻擊者可以在同一位置重復(fù)多次注入隨機(jī)故障.

(3) 攻擊者可以反復(fù)重啟密碼設(shè)備, 加密相同的明文和初始密鑰.

4.1 攻擊模型分析

為求解差分方程, 可在S 盒差分分布表中搜索. 首先進(jìn)行一次故障注入, 找到滿(mǎn)足差分方程的密鑰候選值集合, 再進(jìn)行多次故障注入, 對(duì)所得多個(gè)密鑰候選值集合求交集, 可得半字節(jié)輪密鑰的具體值. 特別地, 由表3 知右半部分注入的半字節(jié)故障相互之間對(duì)密文沒(méi)有影響, 因此可在一輪中同時(shí)注入多個(gè)半字節(jié)故障進(jìn)行差分故障分析.

表3 故障擴(kuò)散位置索引Table 3 Index of fault diffusion position

下面進(jìn)行主密鑰MK=MSB||LSB 的恢復(fù). 為表示方便, 記密鑰擴(kuò)展算法第r輪結(jié)束時(shí)寄存器LSB與MSB 的狀態(tài)分別為Ur和V r. 首先考慮已知K32和K31條件下K30的恢復(fù), 根據(jù)密鑰擴(kuò)展算法可知,V32=S[(U31?2)⊕V31]⊕(V31?3), 即U31?2 =S-1[V32⊕(V31?3)]⊕V31, 于是有下列等式成立:

4.2 攻擊流程

表5 不同輪中故障注入寬度Table 5 Width of fault injection in different rounds

5 復(fù)雜度分析

證明: 由差分分布表統(tǒng)計(jì)特性(2) 知, 對(duì)于某一差分方程, 當(dāng)兩組故障注入后所得可能輸入值集合完全相同時(shí), 需要繼續(xù)注入故障. 反之, 若兩次所得可能輸入值集合不同, 求其交集即為差分方程的解. 具體情形如圖4 所示.

圖4 兩組故障注入后差分方程有無(wú)唯一解的情形Figure 4 Conditions whether or not differential equations have unique solutions

注入l組故障后各輪密鑰Kr(r=2,3,··· ,32) 的恢復(fù)概率均可計(jì)算得到, 如表6 所示:

表6 不同故障注入組數(shù)下輪密鑰恢復(fù)概率(%)Table 6 Probability of round key recovery in different times of faults injection (%)

6 結(jié)果對(duì)比

6.1 與其他輕量級(jí)分組密碼的對(duì)比

隨著側(cè)信道分析技術(shù)的發(fā)展, 近兩年提出的輕量級(jí)算法通常具備一定的抗故障攻擊能力. SLIM 算法的抗差分故障分析手段主要體現(xiàn)在采用了較為復(fù)雜的密鑰擴(kuò)展方案. 早期輕量級(jí)分組密碼密鑰擴(kuò)展方案往往采用類(lèi)似PRESENT 算法的設(shè)計(jì), 如2009 年提出的MIBS, 2011 年提出的LBlock 等. 在此類(lèi)算法中求出倒數(shù)3 至5 輪密鑰即可逆推主密鑰. 在SLIM 算法中, 由于采用LSB 和MSB 兩個(gè)互相影響的寄存器存儲(chǔ)密鑰中間值, 無(wú)法僅通過(guò)倒數(shù)若干輪密鑰完成主密鑰的恢復(fù). 表7 給出了半字節(jié)故障模型下常見(jiàn)輕量級(jí)分組密碼算法的差分故障分析結(jié)果.

表7 輕量級(jí)分組密碼差分故障分析結(jié)果對(duì)比Table 7 Comparison of differential fault analysis results of lightweight block ciphers

6.2 不同故障注入策略的對(duì)比

7 實(shí)驗(yàn)仿真結(jié)果及分析

7.1 實(shí)驗(yàn)環(huán)境

硬件配置為一臺(tái)PC 機(jī)(CPU 為Intel?CoreTM i7-10875H 5.0 GHz, 操作系統(tǒng)為64 位, 內(nèi)存為12 GB), 編程環(huán)境為Microsoft Visual Studio 2015 平臺(tái)下的Visual C++ 語(yǔ)言.

7.2 實(shí)驗(yàn)結(jié)果

明文選取12 345 678, 80 比特主密鑰隨機(jī)選取. 為了消除模擬故障注入過(guò)程中的人工干預(yù), 采用輕量級(jí)流密碼Trivium 算法生成偽隨機(jī)01 數(shù)據(jù)流, 隨機(jī)截取4 比特作為故障值. 模擬1000 組試驗(yàn), 實(shí)驗(yàn)結(jié)果如圖5 所示. 經(jīng)計(jì)算, 恢復(fù)主密鑰MK 所需故障注入組數(shù)均值為69.07 組, 與理論期望值較為接近. 表8 給出十次實(shí)驗(yàn)中各輪故障注入組數(shù).

表8 十次實(shí)驗(yàn)中各輪故障注入組數(shù)Table 8 Number of fault injections per round in 10 experiments

圖5 恢復(fù)主密鑰所需故障注入總組數(shù)對(duì)應(yīng)的實(shí)驗(yàn)組數(shù)Figure 5 Number of experiments corresponding to total number of fault injections

8 結(jié)束語(yǔ)

本文針對(duì)SLIM 算法提出了一種基于半字節(jié)的故障攻擊策略, 在第2 至32 輪注入寬度為1 至4 個(gè)半字節(jié)的故障, 可將恢復(fù)主密鑰MK 的計(jì)算復(fù)雜度降低至23. 通過(guò)分析輪函數(shù)故障擴(kuò)散規(guī)律和S 盒差分分布特性, 運(yùn)用相關(guān)數(shù)學(xué)知識(shí)求取輪密鑰恢復(fù)概率, 并計(jì)算恢復(fù)主密鑰所需故障注入組數(shù)期望68.15. 進(jìn)一步地, 利用軟件進(jìn)行1000 次仿真實(shí)驗(yàn), 故障注入組數(shù)均值為69.07 組, 與理論期望值較為接近. 文中對(duì)SLIM 算法差分故障攻擊的復(fù)雜度分析和成功率證明, 為研究其他輕量級(jí)密碼算法的故障攻擊成功率提供了思路, 下一步將針對(duì)其他密碼算法展開(kāi)類(lèi)似討論和研究. 另一方面, 在后續(xù)研究中將繼續(xù)探索減小故障注入寬度的方法, 盡可能通過(guò)少量故障恢復(fù)密鑰值, 從而提升故障攻擊效率, 同時(shí)運(yùn)用已有結(jié)論分析SLIM算法硬件實(shí)現(xiàn)中抗差分故障攻擊的相關(guān)性能.

作者信息

高楊(1994-), 河南洛陽(yáng)人, 碩士. 主要研究領(lǐng)域?yàn)槊艽a算法設(shè)計(jì)與側(cè)信道分析.gaoyang_1279@126.com

王永娟(1982-), 河南開(kāi)封人,研究員. 主要研究領(lǐng)域?yàn)閭?cè)信道分析與密碼系統(tǒng)安全.pinkywyj@163.com

高光普(1984-), 天津人, 講師.主要研究領(lǐng)域?yàn)閷?duì)稱(chēng)密碼設(shè)計(jì)與分析.guangpu.gao@gmail.com

袁慶軍(1993-), 河北衡水人,講師. 主要研究領(lǐng)域?yàn)閭?cè)信道攻擊與防護(hù)技術(shù).gcxyuan@outlook.com

王燦(1999-), 四川達(dá)州人, 碩士研究生在讀. 主要研究領(lǐng)域?yàn)閭?cè)信道分析.1095976715@qq.com

附錄

表8 中實(shí)驗(yàn)1 具體攻擊流程:

明文為12 345 678, 80 比特主密鑰隨機(jī)選取(程序預(yù)置), 截取Trivium 算法生成數(shù)據(jù)流(非零) 作為故障值:

K29K28K27K26K25K24K23 1a991be4556655585bbd90bfd993 K22K21K20K19K18K17K16 b99508b9e2be0133b07c52bb4386 K15K14K13K12K11K10K9 23edc10a257c75cc8c45d7e203bf K8K7K6K5K4K3K2 16a06704d4d98d26ca73d166141d

(11) 由密鑰擴(kuò)展方案結(jié)合文中4.1 節(jié)分析可推知K1左13 比特為1001101010011, 窮舉剩余3 比特可得K1的值為9a9b, 至此恢復(fù)出完整主密鑰值8d26ca73d166141d9a9b.

在實(shí)際攻擊過(guò)程中, 差分方程為S(K ⊕R)⊕S(K ⊕R*)=L ⊕L*的形式, 上述攻擊流程中密鑰侯選值集合與表4 中m解集不同, 但該方程可以轉(zhuǎn)化為S(m)⊕S(m ⊕f) =f′, 具有與表4 相同的S 盒差分分布統(tǒng)計(jì)特性.