謝敏，李嘉琪，田峰

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071）

1 引言

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

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

2 FeW 算法介紹

2.1 FeW 的加密算法

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

圖1 FeW 的輪結(jié)構(gòu)

表1 FeW 的S 盒

2.2 FeW 的F 函數(shù)

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

圖2 FeW 的F 函數(shù)

表2 P 置換

2.3 FeW 的密鑰編排算法

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

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

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

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

3 FeW 的DFA 過程

3.1 故障模型

本文用到的符號(hào)說明如下。

i：輪數(shù)，0≤i≤31。

Sk：第k個(gè)S 盒，0≤k≤7。

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

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

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

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

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

本文采用的故障模型包括以下2 個(gè)基本假設(shè)。

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

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

3.2 攻擊過程

3.2.1 輪密鑰恢復(fù)

FeW-64-80 和FeW-64-128 具有相同的輪結(jié)構(gòu)、迭代次數(shù)和分組長度，因此以下分析過程對(duì)它們均完全適用。

圖3 故障傳播路徑

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

下面，利用算法結(jié)構(gòu)推導(dǎo)出第31 輪S 盒的輸入IN。

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

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

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

又由S2和S3不是活動(dòng)S 盒可知

從而有

由此，可得關(guān)于未知量y0,y1,…,y7的16 個(gè)方程，即

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

綜上，在第31 輪引入一次單字節(jié)故障，總能夠獲得該輪2 個(gè)活動(dòng)S 盒的輸出差分。

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

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

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

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

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

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

表3 固定輸入差分下輸出差分與輸入的對(duì)應(yīng)關(guān)系

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

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

3.2.2 主密鑰恢復(fù)

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

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

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

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

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

硬件配置為一臺(tái)PC 機(jī)（CPU 為Intel Core i5-7300HQ 2.5 GHz，操作系統(tǒng)64 位，內(nèi)存16 GB），編程環(huán)境為Eclipse 平臺(tái)下的Java 語言。

3.3.2 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

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

表4 2 組一萬次模擬攻擊結(jié)果

圖4 展示了FeW 一萬次實(shí)驗(yàn)中恢復(fù)輪密鑰所需故障次數(shù)的分布情況。結(jié)果表明，大多數(shù)情況下20 次以內(nèi)的故障注入即可恢復(fù)輪密鑰。

圖4 Few 一萬次實(shí)驗(yàn)中恢復(fù)輪密鑰所需故障次數(shù)的分布情況

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

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

4 結(jié)束語

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