FeW 的差分故障攻擊

謝敏，李嘉琪，田峰

（西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室，陜西 西安 710071）

1 引言

近年來，隨著物聯網的快速發展，輕量級分組密碼算法相關的研究十分熱門。傳統密碼分析方法在輕量級算法研究中取得了不錯的成果，如在MIBS[1]、LBlock[2]、TWINE[3]等算法的分析中，利用多種分析方法相結合的方式獲得更高輪數的攻擊[4-6]。與傳統密碼分析方法不同，差分故障攻擊（DFA,differential fault attack）[7]利用加密算法的特點和最大似然估計技術來推測加密系統中的關鍵信息，其密鑰搜索空間遠小于差分密碼分析和線性密碼分析等方法。故障攻擊[8]自提出后一直不斷發展和改進，差分故障攻擊作為故障攻擊的一種方法，對輕量級密碼算法構成嚴重威脅[9-11]。

FeW 是Kumar 等[12]在2014 年提出并于2019 年正式發表的一種輕量級分組密碼算法，它可以在規格很小的硬件和微型控制器上實現。此外，Kumar等[13]還提出了一種基于FeW 的哈希函數HeW，它在軟硬件實現上都擁有很高的效率。FeW 的設計采用了廣義Feistel 結構，分組長度為64 bit，輪數為32 輪，密鑰長度分為80 bit 和128 bit 這2 個版本，分別記為FeW-64-80 和FeW-64-128。算法結構中包含半字節置換、非線性層和線性層。FeW 對于差分、不可能差分、線性、零相關、相關密鑰等分析方法都具有良好的安全性。Shibayama 等[14]利用高階差分攻擊了12 輪FeW-64-80，時間復雜度和數據復雜度均為263.2。Aayush 等[15]使用神經網絡模式識別的技術分析了FeW 算法，實驗結果表明，FeW 算法的遺傳偏差很小，能有效抵御該類攻擊。但是目前還沒有人評估過FeW 面對差分故障攻擊時的安全性，因此對FeW 進行差分故障攻擊是十分必要的。

2 FeW 算法介紹

2.1 FeW 的加密算法

FeW 算法的分組長度為64 bit，密鑰長度分為80 bit 和128 bit 這2 種，明文經過32 輪迭代得到密文。該算法采用了廣義Feistel 結構，如圖1 所示，其中使用到的S 盒如表1 所示。

圖1 FeW 的輪結構

表1 FeW 的S 盒

2.2 FeW 的F 函數

FeW 的F 函數如圖2 所示，它由P 置換（如表2所示）、8 個4 bit 的S 盒以及2 個16 bit 的線性擴散函數L1和L2構成。線性擴散函數L1和L2分別為

圖2 FeW 的F 函數

表2 P 置換

2.3 FeW 的密鑰編排算法

2.3.1 FeW-64-80 的密鑰編排算法

FeW-64-80 的80 bit 主密鑰存儲在名為MK=(K0K1…K78K79)的特定寄存器中，并由其更新算法進行64 輪計算，每次取最左側16 bit 為密鑰編排子密鑰ki，每2 次更新計算所得共計32 bit 作為輪密鑰RKi。當i＜ 64時，MK 的更新算法執行以下計算。

2.3.2 FeW-64-128 的密鑰編排算法

FeW-64-128 的 128 bit 主密鑰存儲在名為MK=(K0K1…K126K127)的特定寄存器中，并由其更新算法進行64 輪計算，每次取最左側16 bit 為密鑰編排子密鑰ki，每2 次更新計算所得共計32 bit 作為輪密鑰RKi。當i＜ 64時，MK 的更新算法執行以下計算。

3 FeW 的DFA 過程

3.1 故障模型

本文用到的符號說明如下。

i：輪數，0≤i≤31。

Sk：第k個S 盒，0≤k≤7。

IN =(in0,in1,…,in7)：第31 輪中8 個S 盒32 bit輸入的半字節塊表示。

ΔIN=(Δin0,Δin1,…,Δin7)：第31 輪中8 個S盒32 bit 輸入差分的半字節塊表示。

OUT=(out0,out1,…,out7)：第31 輪中8 個S盒32 bit 輸出的半字節塊表示。

ΔOUT=(Δ out0,Δout1,…,Δout7)=(y0y1y2y3…y30y31)：第31 輪中8 個S 盒32 bit 輸出差分的半字節塊表示和比特表示。

x=(x0x1…x15)：線性擴散函數L1的16 bit 輸入的比特表示。

本文采用的故障模型包括以下2 個基本假設。

假設1攻擊者可以選擇需要的明文，并且可以獲得相應的正確密文和錯誤密文，即選擇明文攻擊（CPA,chosen plaintext attack）。

假設2攻擊者可以在加密過程中的某一輪導入單字節故障，但是故障導入的具體位置和故障值是未知的。

3.2 攻擊過程

3.2.1 輪密鑰恢復

FeW-64-80 和FeW-64-128 具有相同的輪結構、迭代次數和分組長度，因此以下分析過程對它們均完全適用。

圖3 故障傳播路徑

由圖3 可知，該單字節故障經過線性擴散函數L1后會擴散到兩字節的密文，即影響密文CL*中最左側16 bit 的。對于第31 輪右半段的輸入和S 盒的輸入IN，有，根據FeW 算法最后一輪的結構易知，因此一旦確定了S 盒的輸入IN，也就確定了輪密鑰RK31。

下面，利用算法結構推導出第31 輪S 盒的輸入IN。

1)計算S0的輸入差分Δi n0和S1的輸入差分Δin1

2)計算S0的輸出差分Δout0和S1的輸出差分Δout1

由圖3 可知，故障傳播到CL處時將影響它最左側的16 bit 密文，設這16 bit 密文差分為，則

又由S2和S3不是活動S 盒可知

從而有

由此，可得關于未知量y0,y1,…,y7的16 個方程，即

求解上述方程組，可得S0和S1的輸出差分為

綜上，在第31 輪引入一次單字節故障，總能夠獲得該輪2 個活動S 盒的輸出差分。

3)求S 盒輸入IN 及輪密鑰

利用FeW 算法S 盒的差分特性來確定相應活動S 盒的輸入，為此給出了S 盒輸入輸出差分對應的所有可能輸入，如表3 所示。由表3 可知，對任意一對可能的輸入輸出差分，FeW 算法S 盒的所有可能輸入至多有4 個。設第31 輪8 個S 盒的輸入in0,in1,…,in7的候選值集合分別為E0,E1,…,E7，候選值個數分別為n0,n1,…,n7。首次故障引入可以使其中2 個S 盒的輸入候選值個數減少到2 個或4 個。采用2 種方式來確定最終的IN。

①多次引入故障直至IN 確定

一次故障引入可以得到某2 個S 盒的輸入inα、inβ的候選值集合Oα、Oβ，其中α,β∈{0,1,2,3,4,5,6,7}，將集合Oα、Oβ與Eα、Eβ分別取交集得到新的Eα和Eβ，則nα和nβ隨之減小。通過不斷引入新的故障，直到所有 S 盒輸入候選值個數n0,n1,…,n7都為1，則此時E0,E1,…,E7中唯一的元素即可確定第31 輪S 盒的輸入IN。

②利用故障攻擊完成初篩，然后通過窮舉計算確定最終的IN。

由表3 知，對于任意inα，首次故障引入將以較大概率使Eα中的元素減少到2 個。一旦在所有位置完成首次故障引入，即為初篩完成，此時剩余的候選值將非常少，可以通過少量的加密驗證來確定最終的IN。

表3 固定輸入差分下輸出差分與輸入的對應關系

設初篩完成后in0,in1,…,in7的候選值個數分別為m0,m1,…,m7，此時 IN 的可能值共有T=m0m1…m7種，故所需加密驗證次數最多為T=m0m1…m7次。

確定IN 的值后，即可恢復輪密鑰RK31=IN⊕CR。

3.2.2 主密鑰恢復

根據FeW 的密鑰編排算法，攻擊者若能獲得主密鑰寄存器MK 的某一輪全部位置的比特值，就能通過密鑰編排算法向上逆推最終獲得全部主密鑰。FeW-64-80 和FeW-64-128 具有不同的密鑰編排算法，下面分別給出它們的主密鑰恢復過程。

對于FeW-64-80，從其密鑰編排算法的最后一輪向上逆推，易知密鑰編排算法第58 輪MK 的值僅由RK31的25 bit、RK30的26 bit 和RK29的29 bit 共同決定。利用3.2.1 節中差分故障攻擊獲得RK31后，向上解密一輪，在注入故障，可恢復RK30，之后再向上解密一輪，用同樣的方式可獲得RK29，在此3輪輪密鑰的基礎上，利用密鑰編排算法的逆算法即可完全恢復FeW-64-80 的80 bit 主密鑰。

同理，對于FeW-64-128，易知其密鑰編排算法第54 輪MK 的值僅由RK31的22 bit、RK30的26 bit、RK29的26 bit、RK28的26 bit 和RK27的29 bit 共同決定，利用3.2.1 節中差分故障攻擊獲得該5 輪輪密鑰，即可完全恢復FeW64-128 的128 bit 主密鑰。

3.3 實驗仿真結果和分析

3.3.1 實驗環境

硬件配置為一臺PC 機（CPU 為Intel Core i5-7300HQ 2.5 GHz，操作系統64 位，內存16 GB），編程環境為Eclipse 平臺下的Java 語言。

3.3.2 實驗設計

恢復最后一輪輪密鑰為一次完整實驗，該實驗過程對密鑰編排算法不同的 FeW-64-80 和FeW-64-128 沒有區別，但本文仍分為FeW-64-80和FeW-64-128 這2 組實驗，其中明文、主密鑰、單字節故障位置及故障差分值均完全隨機選取。每次故障引入后，執行以下過程。

1)由3.2 節所示的攻擊過程，完成對IN 候選值集合E0,E1,…,E7的篩選，故障次數加1。

2)判斷IN 候選值個數n0,n1,…,n7是否均小于16，若不是，則直接返回步驟1)繼續執行；若是，則對IN 恰好完成初篩，記錄該故障次數為完成初篩所用的故障數，并根據此時IN 候選值個數n0,n1,…,n7計算得到本次實驗所需的加密驗證次數T=n0n1…n7，完成初篩后不再執行此判斷。

3)判斷n0,n1,…,n7是否均為1，若不全為1，則繼續引入新的故障；若全為1，記錄此時的故障次數即為恢復輪密鑰所需的故障次數，一次實驗結束。

3.3.3 實驗結果

表4 展示了針對FeW-64-80 和FeW-64-128 這2 種算法各2 組（共4 組）一萬次實驗的結果。由表4可知，不同的密鑰編排算法對單輪輪密鑰恢復沒有影響。因此，將4 組結果相結合作為FeW 算法單輪差分故障攻擊的結論，即平均15.91 次故障引入可以恢復32 bit 輪密鑰；若采用初篩后窮舉的方式，則需要平均8.30 次故障引入和199 次加密驗證才可以恢復32 bit輪密鑰。

表4 2 組一萬次模擬攻擊結果

圖4 展示了FeW 一萬次實驗中恢復輪密鑰所需故障次數的分布情況。結果表明，大多數情況下20 次以內的故障注入即可恢復輪密鑰。

圖4 Few 一萬次實驗中恢復輪密鑰所需故障次數的分布情況

根據實驗結果可知，對于FeW-64-80，平均需要15.91×3=47.73 次故障引入才可以直接恢復主密鑰。若采用初篩后窮舉的方式，則進行199×3=597，約 210次加密驗證才可將故障次數降為8.30×3=24.90 次。

對于FeW-64-128，平均需要15.91×5=79.55 次故障引入才可以直接恢復主密鑰。若采用初篩后窮舉的方式，則進行199×5=995，約210次加密驗證才可將故障次數降為8.30×5=41.50 次。

4 結束語

本文利用FeW 算法線性擴散函數的特點，采用差分故障對其進行了攻擊。通過在第31 輪右側輸入引入單字節隨機故障，較好地完成了FeW 的差分故障攻擊。實驗結果表明，平均需要15.91 次故障可恢復FeW 單輪輪密鑰，根據FeW 的密鑰編排算法，恢復80 bit 主密鑰和128 bit 主密鑰分別需要3 輪和5 輪輪密鑰；此外，由于故障引入恢復效率的變化，本文提出了一種初篩加窮舉的密鑰恢復策略，結合210的窮舉搜索，可將主密鑰恢復平均所需故障引入次數降低一半，為同類攻擊提供了新的思路。差分故障攻擊對FeW 是十分有效的，為了避免此類攻擊，需要對加密設備進行保護。