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

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

2. 河南省網(wǎng)絡密碼技術重點實驗室, 鄭州 450001

1 引言

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

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

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

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

2 SLIM 算法簡介

2.1 符號說明

本文所用符號如表1 所示.

表1 符號說明Table 1 Symbol description

2.2 SLIM 算法介紹

SLIM 算法是Aboushosha 等人[16]于2020 年提出的一種基于Feistel 結構的輕量級分組密碼算法,其分組長度為32 比特, 主密鑰長度為80 比特, 迭代輪數(shù)為32 輪, SLIM 算法中所有迭代操作都是基于半字節(jié)的. 令M=L0||R0表示32 比特明文, 則中間狀態(tài)為Li=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 個相同的4×4 S 盒, 見表2.

圖1 SLIM 算法結構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 算法的密鑰擴展方案設計思路較為獨特, 其主密鑰為80 比特, 記為MK = mk79mk78···mk0.首先將主密鑰劃為5 等份, 分別作為前5 輪輪密鑰, 即K1= mk15mk14···mk0,K2= mk31mk30···mk16,K3=mk47mk46···mk32,K4=mk63mk62···mk48,K5=mk79mk78···mk64, 再將MK 存儲于兩個長度為40 比特的寄存器中, 即MK=MSB||LSB, 每輪寄存器執(zhí)行下列偽代碼(算法1), 并輸出16比特輪密鑰K.

算法1 密鑰擴展算法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 算法結構性質

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

圖3 SLIM 算法故障擴散實例Figure 3 Example of fault propagation process in SLIM algorithm

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

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

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

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

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

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

(3)Y1∩Y2=m;

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

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

4 SLIM 算法的差分故障攻擊

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

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

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

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

4.1 攻擊模型分析

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

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

下面進行主密鑰MK=MSB||LSB 的恢復. 為表示方便, 記密鑰擴展算法第r輪結束時寄存器LSB與MSB 的狀態(tài)分別為Ur和V r. 首先考慮已知K32和K31條件下K30的恢復, 根據(jù)密鑰擴展算法可知,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 復雜度分析

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

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

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

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

6 結果對比

6.1 與其他輕量級分組密碼的對比

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

表7 輕量級分組密碼差分故障分析結果對比Table 7 Comparison of differential fault analysis results of lightweight block ciphers

6.2 不同故障注入策略的對比

7 實驗仿真結果及分析

7.1 實驗環(huán)境

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

7.2 實驗結果

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

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

圖5 恢復主密鑰所需故障注入總組數(shù)對應的實驗組數(shù)Figure 5 Number of experiments corresponding to total number of fault injections

8 結束語

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

作者信息

高楊(1994-), 河南洛陽人, 碩士. 主要研究領域為密碼算法設計與側信道分析.gaoyang_1279@126.com

王永娟(1982-), 河南開封人,研究員. 主要研究領域為側信道分析與密碼系統(tǒng)安全.pinkywyj@163.com

高光普(1984-), 天津人, 講師.主要研究領域為對稱密碼設計與分析.guangpu.gao@gmail.com

袁慶軍(1993-), 河北衡水人,講師. 主要研究領域為側信道攻擊與防護技術.gcxyuan@outlook.com

王燦(1999-), 四川達州人, 碩士研究生在讀. 主要研究領域為側信道分析.1095976715@qq.com

附錄

表8 中實驗1 具體攻擊流程:

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

K29K28K27K26K25K24K23 1a991be4556655585bbd90bfd993 K22K21K20K19K18K17K16 b99508b9e2be0133b07c52bb4386 K15K14K13K12K11K10K9 23edc10a257c75cc8c45d7e203bf K8K7K6K5K4K3K2 16a06704d4d98d26ca73d166141d

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

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