喬青藍(lán)，董麗華

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

近年來RFID標(biāo)簽、智能卡和FPGA的影響不斷擴(kuò)大。在這些設(shè)備中，內(nèi)存、電池供電和計算能力有限，因而硬件和軟件的效率與安全性至關(guān)重要，進(jìn)而設(shè)計資源受限條件下的輕量級密碼算法已經(jīng)成為信息安全領(lǐng)域的重大挑戰(zhàn)。在過去的十幾年里，許多流密碼，例如Grain[1-2]、Trivium[3]、MICKEY 2.0[4]等被相繼提出。然而為了抵抗時間記憶數(shù)據(jù)權(quán)衡(TMD)攻擊[5-6]，所有這些密碼都使用了一個相對較大的內(nèi)部狀態(tài)來生成密鑰流，并不適用于資源受限的情況。

2015年，ARMKNECHT等[7]學(xué)者為減少內(nèi)部狀態(tài)同時不損害其對時間記憶數(shù)據(jù)權(quán)衡攻擊的安全性，給出了一個全新的設(shè)計原則，即密鑰不僅參與初始化階段(KLA)，還參與了密鑰生成階段(PRGA)?；谶@一原理，他們提出了第一個小狀態(tài)流密碼Sprout。眾多密碼學(xué)者針對Sprout進(jìn)行了密碼分析[8-13]。雖然分析發(fā)現(xiàn)Sprout結(jié)構(gòu)是不安全的，但是近幾年基于此原理相繼提出了許多超輕量級流密碼，例如Plantlet[14-15]，Lizard[16]以及Fruit v2[17]等。其中Fruit v2[17]是2016年，Ghafari為了抵抗針對Sprout的密鑰恢復(fù)攻擊，通過使用更復(fù)雜的輪密鑰函數(shù)對Sprout結(jié)構(gòu)給出的改進(jìn)版本。目前Fruit族已有4個版本： Fruit-v2[17]、Fruit-80[18]、Fruit-128[19]和Fruit-F[20-21]。但是Fruit族作為Sprout的繼承者，內(nèi)部依然存在著與Sprout類似的弱點。2017年，文獻(xiàn)[22]對Fruit進(jìn)行了快速相關(guān)攻擊，并指出使用262.8輪Fruit加密和222.3個密鑰流可以有效確定其80位密鑰。隨后他們對Plantlet和Fruit進(jìn)行區(qū)分攻擊[23]，并提出Fruit的首個密鑰恢復(fù)攻擊，結(jié)果顯示Fruit中至少有264個弱密鑰。2019年，文獻(xiàn)[24]對類Grain小狀態(tài)流密碼發(fā)起了快速相關(guān)攻擊，并指出對于Fruit v2使用255.34加密和255.62個密鑰流比特可以有效確定密鑰，對于Fruit 80使用262.82的數(shù)據(jù)和內(nèi)存復(fù)雜度以及264.47的時間復(fù)雜度可以有效確定密鑰。2019年，文獻(xiàn)[25]采用分而治之的方法對Fruit進(jìn)行攻擊，比窮舉密鑰搜索快16.96倍左右。2020年，文獻(xiàn)[20]提出了具有長周期的輕量級輪密鑰的小狀態(tài)流密碼Fruit-F以避免快速相關(guān)攻擊。同年，文獻(xiàn)[26]對Fruit-80進(jìn)行相關(guān)攻擊，結(jié)果顯示可以恢復(fù)Fruit-80的全部密鑰，因此設(shè)計者對于密鑰流的長度限制是不夠的。由此可見，F(xiàn)ruit族密碼結(jié)構(gòu)雖然是對Sprout的改進(jìn)，但其結(jié)構(gòu)依然存在著弱性，需要進(jìn)一步研究和改進(jìn)。

另一方面，在密碼算法的實現(xiàn)中，通常使用寄存器來存儲數(shù)據(jù)和內(nèi)部狀態(tài)，因而使用具有較低代價如電壓跳變、時鐘刺激、激光等方法，即可向寄存器中注入錯誤[27-29]，因此差分錯誤攻擊對密碼算法具有巨大的威脅。1997年，文獻(xiàn)[30]首次提出了差分錯誤攻擊的概念，將這種攻擊方法應(yīng)用于分組密碼算法，成功攻擊了數(shù)據(jù)加密標(biāo)準(zhǔn)(Data Encryption Standand，DES)，此后差分錯誤攻擊成功地應(yīng)用于眾多分組密碼算法[31-40]。一般來說，差分錯誤攻擊對于流密碼算法同樣有效。2004年，文獻(xiàn)[41]在其發(fā)表的論文中試圖找到一種差分錯誤攻擊的方法，用來分析所有流密碼。2008年，文獻(xiàn)[42]對Trivium進(jìn)行了差分錯誤攻擊，通過注入43個錯誤成功恢復(fù)了Trivium的密鑰。同年，文獻(xiàn)[43]對該攻擊算法做了進(jìn)一步改進(jìn)，只需一位錯誤注入就可以恢復(fù)密鑰。2009年，文獻(xiàn)[44]介紹了一種基于真實故障模型的針對GRAIN-128的故障攻擊并給出了對抗措施。2011年，文獻(xiàn)[45]證明了Grain-128也可以通過在非線性反饋移位寄存器(Nonlinear Feedback Shift Register，NFSR)中誘發(fā)故障而受到攻擊，該攻擊需要在NFSR中注入56個錯誤，計算復(fù)雜度約為221。2012年，BANIK等學(xué)者分別在寬松故障模型下[46]和嚴(yán)格故障模型下[47]對Grain族進(jìn)行差分錯誤攻擊。2012年，文獻(xiàn)[48]對Trivium算法進(jìn)行了錯誤攻擊，該模型不假定攻擊者可以同步故障注入的時間。2013年，文獻(xiàn)[49]提出了對MICKEY-128 2.0的差分錯誤攻擊。2015年，文獻(xiàn)[50]對Grain的差分錯誤攻擊提出了進(jìn)一步的改進(jìn)，進(jìn)一步減少了錯誤插入數(shù)量 。目前對于流密碼的錯誤攻擊的研究成果主要集中在對Trivium，Grain，MICKEY，Rabbit和Sosemnauk等密碼。在小狀態(tài)流密碼方面，2015年，文獻(xiàn)[8]對Sprout進(jìn)行了差分錯誤攻擊，攻擊中通過使用120個錯誤恢復(fù)了Sprout的密鑰。基于此，2017年，文獻(xiàn)[15]對Plantlet進(jìn)行了差分錯誤攻擊，僅需要4個故障就可以在數(shù)小時內(nèi)恢復(fù)Plantlet的密鑰，隨后，文獻(xiàn)[51]首次對Lizard進(jìn)行了差分錯誤攻擊，并且表明只需要5個錯誤就可以恢復(fù)內(nèi)部狀態(tài)，但不能恢復(fù)完整密鑰。目前對輕量級小狀態(tài)流密碼的差分錯誤攻擊研究成果較少，針對Fruit族的差分錯誤攻擊更是尚未展開，因此筆者嘗試將差分錯誤攻擊應(yīng)用于小狀態(tài)流密碼Fruit族的安全性分析。

在相對寬松的錯誤模型假設(shè)下(即攻擊者可在密碼內(nèi)部狀態(tài)的某個隨機(jī)位置在每次重啟執(zhí)行過程的同一時刻注入單個錯誤)，通過求解利用輸出函數(shù)的一階差分性質(zhì)得到的內(nèi)部狀態(tài)的線性方程組，筆者分析了密碼的整個內(nèi)部狀態(tài)。研究結(jié)果表明，在216.3的時間復(fù)雜度下即可恢復(fù)Fruit v2和Fruit-80的內(nèi)部狀態(tài)。在恢復(fù)密鑰部分，借助Cryptominisat-2.9.5 SAT解算器[40]對非線性方程組進(jìn)行求解，只需要大約10 min即可完成所有方程的求解。通過統(tǒng)計顯示，攻擊所需錯誤個數(shù)為27.3。

1 Fruit流密碼的介紹

Fruit系列流密碼是超輕量級小狀態(tài)流密碼的最新版本，正是由于它較小的內(nèi)部狀態(tài)吸引了全世界密碼學(xué)界的廣泛關(guān)注。該系列目前由4個版本的密碼組成：Fruit v2、Fruit-80、Fruit-128和Fruit-F。每個版本的密碼在密碼分析方面都有獨特的挑戰(zhàn)。本節(jié)將深入介紹Fruit族的算法結(jié)構(gòu)。

2016年，GHAFARI等學(xué)者在IACR(eprint)的網(wǎng)頁上首次非正式地介紹了Fruit v2密碼并進(jìn)行了簡單的密碼分析[17]。2018年，F(xiàn)ruit-80作為更易于實現(xiàn)和安全的更新版本而出現(xiàn)[18]。

Fruit-v2和Fruit-80在設(shè)計中的新想法如下所示：

(1) 新的輪密鑰函數(shù)(Sprout的大多數(shù)弱點與輪密鑰函數(shù)有關(guān))；

(2) 新的初始化過程，以加強(qiáng)對相關(guān)密鑰攻擊的抵抗能力；

(3) 防止線性反饋移位寄存器(Linear Feedback Shift Register，LFSR)初始化后內(nèi)部狀態(tài)全為零的新思路(與Grain家族和Sprout不同)；

(4) 增加線性反饋移位寄存器的大小以在每次加載中獲得更長的密鑰流；

(5) 新的針對非線性反饋移位寄存器的更輕的反饋函數(shù)和輸出函數(shù)(與Grain-v1和Sprout相比)。

1.1 Fruit族密碼結(jié)構(gòu)

通過對比如表1所示的Fruit族的各版本結(jié)構(gòu)，可以發(fā)現(xiàn)除了輪密鑰及內(nèi)部更新函數(shù)，結(jié)構(gòu)的其他部分大體相同。

表1 Fruit 族相關(guān)密碼對比

因此，筆者對各版本的相同結(jié)構(gòu)部分給出了如圖1所示Fruit族小狀態(tài)流密碼的廣義模型，此模型由以下幾部分組成。

圖1 Fruit 族小狀態(tài)流密碼的廣義模型

LFSR：設(shè)m為線性反饋移位寄存器的內(nèi)部狀態(tài)的大小，Lt=(lt，…，lt+m-1)為線性反饋移位寄存器在時刻t的內(nèi)部狀態(tài)，f為線性反饋移位寄存器的內(nèi)部狀態(tài)更新函數(shù)，即Lt+1=(lt+1，…，lt+m)，lt+m=f(Lt)，并且其逆過程是Lt-1=(lt-1，…，lt+m-2)，lt-1=f′(Lt)。

NFSR和計數(shù)器：設(shè)m′為非線性反饋移位寄存器的內(nèi)部狀態(tài)的大小，Nt=(nt，…，nt+m′-1)為t時刻非線性反饋移位寄存器的內(nèi)部狀態(tài)，非線性反饋移位寄存器按以下方式遞歸更新：

(1)

1.2 Fruit族密碼的完整數(shù)學(xué)描述

圖2 Fruit v2的具體結(jié)構(gòu) 圖3 Fruit-80的具體結(jié)構(gòu)

(2)

其中，

(3)

(4)

(5)

其中，

(6)

g函數(shù)：非線性反饋移位寄存器的反饋更新函數(shù)如下：

(7)

Fruit-80的非線性反饋移位寄存器的反饋函數(shù)與Fruit v2大致相同，不同之處為Fruit-80的g函數(shù)少了計數(shù)器的參與：

(8)

f函數(shù)：Fruit v2和Fruit-80的線性反饋移位寄存器的反饋更新函數(shù)為

lt+43=lt⊕lt+8⊕lt+18⊕lt+23⊕lt+28⊕lt+37。

(9)

h函數(shù)：此函數(shù)從LFSR和NFSR狀態(tài)中生成預(yù)輸出流，如下所示：

h(lt+6，lt+15，lt+1，lt+22，nt+35，lt+27，lt+11，lt+33，nt+1，nt+33，lt+42)=
lt+6lt+15⊕lt+1lt+22⊕nt+35lt+27⊕lt+11lt+33⊕nt+1nt+33lt+42。

(10)

(11)

輸出函數(shù)：輸出密鑰流由非線性反饋移位寄存器的7位、線性反饋移位寄存器的1位和h函數(shù)的輸出產(chǎn)生，如下所示：

(12)

其中，BFruit v2={0，7，13，19，24，29，36}，BFruit-80={0，7，19，29，36}。

密碼初始化：在初始化階段，首先進(jìn)行密鑰加載。將80位的密鑰K分別載入線性反饋移位寄存器和非線性反饋移位寄存器，其中K的前37位載入非線性反饋移位寄存器，即n0=k0，n1=k1，…，n36=k36，剩余的43位載入線性反饋移位寄存器，即l0=k37，l1=k38，…，l42=k79，兩個計數(shù)器均置為0，F(xiàn)ruit v2的IV通過在前面添加1個比特1和9個比特0，在后面添加50個比特0，擴(kuò)展為130個比特IV′，形如：IV′=1000000000v0v1，…，v6900…00。Fruit-80的IV通過在前面添加1個比特1和9個比特0擴(kuò)展為80個比特IV′，即，IV′=1000000000v0v1，…，v69。

2 故障位置檢測算法

本節(jié)借鑒MAITRA等[8]所提出的基于特征向量和錯誤路徑之間的相關(guān)性確定位置的方法，給出適用于所有Fruit族的故障位置識別算法，并使用此算法對Fruit v2和Fruit-80進(jìn)行實際故障位置識別。

在攻擊之前，先來介紹一些將要使用的符號：

(1)St=[nt，nt+1，…，nt+m′-1，lt，lt+1，…，lt+m-1]，用于表示t時刻的內(nèi)部狀態(tài)。其中nt+i(lt+i)表示t時刻的第i位非線性反饋移位寄存器(線性反饋移位寄存器)。當(dāng)t=0時，為了方便起見，使用S0=[n0，n1，…，nm′-1，l0，l1，…，lm-1]來表示密鑰流產(chǎn)生階段的初始內(nèi)部狀態(tài)。

當(dāng)0≤i≤λ-1，為了形成密鑰流序列的惟一模式，給出以下定義[8]。

定義1特征向量Q(φ)，將其定義為

(13)

其中，

(14)

這個概率是通過預(yù)先進(jìn)行足夠多的實驗來估計的。特征向量Q(φ)可以在攻擊的離線階段被預(yù)先計算出來，然后存儲起來與差分密鑰流進(jìn)行比較。

定義2假設(shè)在未知位置δ(0≤δ≤80)注入了一個錯誤，定義

(15)

未知位置δ(0≤δ≤80)的錯誤路徑Γ(δ)可以定義為

(16)

注意，在這種情況下沒有概率，也就是說，可以通過比較每個Q(φ)和Γ(δ)來估計準(zhǔn)確的錯誤位置。

① maxφμ(Q(φ)，Γ(δ))

②μ(Q(δ)，Γ(δ))

③α(Q(δ))=#|{μ(Q(φ)，Γ(δ))>μ(Q(δ)，Γ(δ))}|

圖4統(tǒng)計了Fruitv2和Fruit-80的maxφμ(Q(φ)，Γ(δ))和μ(Q(δ)，Γ(δ))指標(biāo)：

(a) Fruit v2 (b) Fruit-80

在圖4中，當(dāng)μ(Q(δ)，Γ(δ))接近maxφμ(Q(φ)，Γ(δ))，即α(Q(δ))較小時，更容易定位這些錯誤。然而，如果μ(Q(δ)，Γ(δ))遠(yuǎn)小于maxφμ(Q(φ)，Γ(δ))，即α(Q(δ))較大，則意味著從差分密鑰流中更難定位該特定錯誤位置。將文獻(xiàn)[8]中的圖3和文獻(xiàn)[15]中的圖3與筆者的結(jié)果進(jìn)行對比發(fā)現(xiàn)，與Sprout和Plantlet相比，F(xiàn)ruit v2和Fruit-80的α(Q(δ))更小，更易定位錯誤位置。

下面對錯誤位置檢測方法進(jìn)行具體描述：假設(shè)每個錯誤都是在每次初始化過程結(jié)束后的初始內(nèi)部狀態(tài)隨機(jī)注入的，統(tǒng)計密碼在狀態(tài)φ處注入錯誤后的特征向量Q(φ)，在具體實現(xiàn)時令λ=64，在攻擊之前用隨機(jī)的密鑰初始化向量對將密碼算法運行215輪，統(tǒng)計注入錯誤前后密鑰流之間的關(guān)系，并計算(Q(0)，Q(1)，…，Q(m+m′))，然后獲取在具體位置δ注入錯誤對應(yīng)的錯誤路徑Γ(δ)，通過對Γ(δ)和Q(φ)(0≤φ≤m+m′)比較來確定錯誤位置。確認(rèn)錯誤位置的具體步驟為

① 在任意位置注入一個錯誤δ；

③ 對每個狀態(tài)位置φ計算μ(Q(φ)，Γ(δ))；

④ 對于每個錯誤，根據(jù)μ(Q(φ)，Γ(δ))建立一個等級表Tδ，以更高的優(yōu)先級排列可能的錯誤位置φ。

算法1給出了檢測錯誤位置的一般步驟。

算法1位置識別算法。

輸入：簽名向量(Q(0)，Q(1)，…，Q(m+m′))以及τ個不同的錯誤δ1，δ2，…，δτ。

輸出：候選等級表Tδ。

Fori=1 toτdo

獲取錯誤路徑：

Forφ=0 tom+m′ then

計算μ(Q(φ)，Γ(δi))

計算maxφμ(Q(φ)，Γ(δi))

End

找到maxφμ(Q(φ)，Γ(δi))對應(yīng)的φ0，令δi=φ0

計算μ(Q(δi)，Γ(δi))

Ifμ(Q(δi)，Γ(δi))=maxφμ(Q(φ)，Γ(δi)) then

Tδ=[φ0]

ElseTδ=[φ0]

計算μ(Q(φ)，Γ(δi))中次小于maxφμ(Q(φ)，Γ(δi))的系數(shù)對應(yīng)φ1

重復(fù)第1步

Tδ=[φ0，φ1]

以此類推

End

returnTδ。

算法1的整體復(fù)雜度為τ(m+m′)。使用上述識別算法對Fruit v2和Fruit-80進(jìn)行了實際錯誤位置識別。實驗結(jié)果表明，對于Fruit v2在第一次篩選之后全部故障位置都被精確識別出，因此Fruit v2準(zhǔn)確識別單個錯誤的復(fù)雜度為一次算法的復(fù)雜度O(26.3)。而對于Fruit-80第一次篩選之后只有小部分故障位置沒有精確識別出，其中最難識別的故障為l23，對應(yīng)T23的長度為2，即Fruit-80準(zhǔn)確識別單個錯誤的復(fù)雜度為執(zhí)行兩次算法的復(fù)雜度O(27.3)。預(yù)計算階段即計算特征向量Q(φ)的時間復(fù)雜度為O(226.5)，數(shù)據(jù)復(fù)雜度為O(211.5)。

3 針對Fruit v2和Fruit-80的差分錯誤攻擊

一旦攻擊者能夠推斷出注入錯誤的位置，就可以繼續(xù)使用此信息對密碼發(fā)起攻擊。在本節(jié)中，將在最寬松的假設(shè)下對Fruit家族進(jìn)行攻擊，即假設(shè)攻擊者有能力執(zhí)行以下操作：

① 在同一個隨機(jī)寄存器位置注入多個時間同步的單位翻轉(zhuǎn)錯誤；

② 重置執(zhí)行密碼的設(shè)備并重新啟動密碼。

在本節(jié)中，將以Fruit v2為例來說明新方法，但是，這種攻擊同樣適用于Fruit系列的任何版本。這種錯誤攻擊主要基于Fruit系列的各版本的輸出布爾函數(shù)h的特定性質(zhì)，即h函數(shù)滿足文獻(xiàn)[46]中提出的如下仿射差分函數(shù)性質(zhì)：

定義5對于具有q個變量的布爾函數(shù)F，如果F滿足對任意一個非零向量α∈{0，1}q，F(xiàn)(x)+F(x+α)是一個仿射函數(shù)，則α是F的一個仿射差分。如果布爾函數(shù)沒有仿射差分，則稱其為抗仿射差分函數(shù)。

例如，對于Fruit v2的濾波函數(shù)h(式10)，滿足

h(lt+1)+h(lt+1+1)=(lt+6×lt+15⊕lt+1×lt+22⊕nt+35×lt+27⊕lt+11×lt+33⊕nt+1×nt+33×

lt+42)+(lt+6×lt+15⊕(lt+1+1)×lt+22⊕nt+35×lt+27⊕lt+11×lt+33⊕

nt+1×nt+33×lt+42)=lt+22。

(17)

可見h是仿射差分為α={0，0，1，0，0，0，0，0，0，0，0}的一個仿射函數(shù)。

利用這一差分性質(zhì)，在密鑰流產(chǎn)生階段開始時，可以對線性反饋移位寄存器的狀態(tài)變量建立若干個線性方程，并通過求解這些方程得到完整的線性反饋移位寄存器狀態(tài)。而非線性反饋移位寄存器的移位性質(zhì)將幫助確定非線性反饋移位寄存器的狀態(tài)位。鑒于這一背景，內(nèi)部狀態(tài)恢復(fù)過程將包括以下步驟：

① 攻擊者在隨機(jī)選擇的線性反饋移位寄存器位置注入一個錯誤，并通過比較無錯誤和錯誤密鑰流及上一節(jié)中提出的錯誤位置識別算法來確定錯誤位置。

② 通過比較特定密鑰流產(chǎn)生階段中的無錯誤和錯誤密鑰流，根據(jù)布爾函數(shù)h的仿射差分性質(zhì)，可以得到PRGA開始時線性反饋移位寄存器狀態(tài)位的線性方程。運行適當(dāng)次數(shù)的錯誤攻擊，得到幾個這樣的線性方程組，通過求解線性方程組得到線性反饋移位寄存器狀態(tài)。

③ 如上所述，將無錯誤和錯誤密鑰流在某些其它PRGA輪中進(jìn)行比較，得到在PRGA開始時非線性反饋移位寄存器的某些特定位置的值，根據(jù)非線性反饋移位寄存器的移位性質(zhì)確定非線性反饋移位寄存器的值。

3.1 確定LFSR的內(nèi)部狀態(tài)

lt+22=l37⊕l33⊕l29⊕l28⊕l24⊕l23⊕l18⊕l14⊕l6⊕l8⊕l0。

(18)

以此類推，可以獲得43個變量為l0，l1，…l42的線性方程，其中27≤t≤68。用矩陣表示為LY=W，矩陣L是線性函數(shù)lt+22，其中27≤t≤68，Y=[l0，l1，…，l42]T，W是一個列向量：

(19)

使用Matlab對矩陣L進(jìn)行逆運算，結(jié)果證明矩陣L是可逆的，所以通過注入錯誤和計算W可以立刻求出向量Y=L-1W。此時可以確定線性反饋移位寄存器的全部狀態(tài)。主要消耗時間與內(nèi)存的是Y=L-1W的計算過程，它大概需要43×43位來存儲L-1和433≈O(216.3)的時間復(fù)雜度。

3.2 確定NFSR的內(nèi)部狀態(tài)

在注入錯誤之前可以使用相同的(K，IV)對密碼進(jìn)行重置，F(xiàn)ruit v2和Fruit-80的密鑰流輸出函數(shù)的表達(dá)式為式(12)；由于現(xiàn)在線性反饋移位寄存器的內(nèi)部狀態(tài)已知，如果錯誤位置在n33，那么注入錯誤后產(chǎn)生的密鑰流輸出函數(shù)分別為

nt+1(nt+33+1)lt+42⊕nt⊕nt+7⊕nt+13⊕nt+19⊕nt+29⊕nt+24⊕nt+36⊕lt+38，

(20)

nt+1nt+24⊕nt+1(nt+33+1)lt+42)⊕nt⊕nt+7⊕nt+19⊕nt+29⊕nt+36⊕lt+38。

(21)

3.3 密鑰恢復(fù)階段

在之前的分析中成功地恢復(fù)了Fruit系列密碼的內(nèi)部狀態(tài)S0，然而這并不能直接恢復(fù)密鑰。因為在輕量級流密碼算法中，密鑰不僅參與初始化階段，而且也參與了密鑰生成階段，這使得密鑰恢復(fù)變得更加困難。

在Fruit v2和Fruit-80中參與非線性反饋移位寄存器更新的輪密鑰函數(shù)的每個密鑰位都是由計數(shù)器Cr決定的，在初始化的第1階段(Fruit v2為130輪，F(xiàn)ruit-80為80輪)，Cr從0開始計數(shù)直到結(jié)束，在初始化的第2階段，Cr的7位被重新分配，由非線性反饋移位寄存器的6比特最低有效位和線性反饋移位寄存器的1比特最低有效位組成。因此對于Fruit v2和Fruit-80可以將密鑰恢復(fù)階段分為3步進(jìn)行。

3.3.1 獲取連續(xù)128位輪密鑰比特

密鑰恢復(fù)過程中的難點主要是內(nèi)部狀態(tài)更新過程中有輪密鑰函數(shù)和計時器的參與，而輪密鑰函數(shù)和計時器都是未知的，又由于輪密鑰函數(shù)中參與的密鑰是由計時器決定的，因此，首先對計時器Cr進(jìn)行猜測，Cr由7比特組成，因此Cr有27種可能性。在密鑰流產(chǎn)生階段的初始時期，內(nèi)部狀態(tài)S0已知。

nt+35lt+27⊕nt+1nt+42⊕nt+1nt+33lt+42。

(22)

對于Fruit v2，由于輪密鑰只參與非線性反饋移位寄存器的更新，因此可以通過輸出函數(shù)zt來獲取非線性反饋移位寄存器的反饋位(即n36)的值，再通過非線性反饋移位寄存器的更新函數(shù)獲取這一時刻的輪密鑰函數(shù)k′的值：

nt-7×nt-17⊕nt-4×nt-22×nt-30⊕nt-27×nt-29×nt-31×nt-33。

(23)

3.3.2 根據(jù)輪密鑰函數(shù)建立方程組

對于Fruit v2，可以建立針對k′的方程組。由于對每個計時器的值都可以構(gòu)成一個輪密鑰函數(shù)k′，假設(shè)在密鑰流產(chǎn)生階段Cr輸出為127，此時：

s=31，y+32=63，u+64=79，p=15，q+16=47，r+48=79 。

(24)

因此可以建立方程組：

(25)

為了消除方程組中的二次項，猜測：(k0，k1，k2，…，k31)，通過高斯消去求解128個線性方程組來獲取其余的48位密鑰，因此獲取密鑰的復(fù)雜度為27×232×1283=260。

(26)

為降低計算的難度，筆者猜測(k0，k1，k2，…，k15，…，k48)，將非線性函數(shù)組轉(zhuǎn)換為線性函數(shù)方程組，然后使用高斯消去求解128個線性方程組獲取剩余的32位密鑰，此時獲取密鑰的復(fù)雜度為27×248×1283=277；復(fù)雜度相對較高，也可以直接使用SAT解算器求解128個非線性方程來獲取80位密鑰，因此獲取密鑰的復(fù)雜度由SAT解算器確定。借鑒文獻(xiàn)[52]中表5使用SAT解算器對Grain差分錯誤攻擊所建立的方程進(jìn)行求解的結(jié)果，估算出求解128個非線性方程所需的時間最多為3.2 s。因此求解27個這樣的方程組所需時間大概為409.6 s。

3.3.3 檢測密鑰的正確性

通過上述方法，可以得到27組候選密鑰，在這一階段要從候選的密鑰中選擇一個正確的密鑰。逆運算密碼80輪，判斷計時器Cr的7位是否符合前6位來自非線性反饋移位寄存器的最低有效位，第7位為1。

上述方法對Fruit v 2和Fruit-80均適用，因為這兩個密碼算法的輪密鑰函數(shù)中密鑰的參與位置由計數(shù)器Cr決定，且3個輪密鑰函數(shù)的周期都是有限且在密鑰流限制范圍內(nèi)的，因此可以建立有限個方程并確保所有密鑰位均參與運算，通過求解方程組獲取密鑰。

3.4 復(fù)雜度分析

錯誤個數(shù)直接取決于要執(zhí)行的重置密鑰IV的數(shù)量，以便覆蓋線性反饋移位寄存器中幾乎所有位置，由于每次重置密鑰和IV后正好有一個錯誤注入，因此錯誤注入的預(yù)期數(shù)目為mlnm(對于m=43，這大約等于27.3)。此后，該攻擊需要在一個m×m矩陣和一個m×1向量之間進(jìn)行一次矩陣乘法來恢復(fù)LFSR，并通過求解幾個方程來獲得非線性反饋移位寄存器狀態(tài)。由于恢復(fù)內(nèi)部狀態(tài)建立的方程均為線性方程，因此可以通過高斯消去法求解方程組，因此恢復(fù)線性反饋移位寄存器的時間復(fù)雜度為O(m3)，恢復(fù)非線性反饋移位寄存器的時間復(fù)雜度為O((m′)3)。最后，該攻擊需要建立輪密鑰函數(shù)的非線性方程組來恢復(fù)密鑰，求解非線性方程組部分給出兩個方案：一是猜測部分密鑰線性化方程，將問題簡化為用高斯消去法求解線性方程組，這使得攻擊的復(fù)雜度很大，為了簡化計算難度、降低攻擊復(fù)雜度；在方案二中，使用SAT解算器求解所有的非線性方程組，統(tǒng)計求解的時間。具體的攻擊復(fù)雜度對比如表2至表4。

表2 針對Fruit v2和Fruit-80的DFA復(fù)雜度對比

表3 SAT解算器恢復(fù)密鑰時間對比 s

表4 Fruit v2和Fruit-80復(fù)雜度對比

4 結(jié)束語

借鑒MAITRA等對Sprout的差分錯誤攻擊和BANIK等對Grain的分析，在精確識別錯誤的基礎(chǔ)上，筆者研究了在相對寬松的錯誤模型下，針對Fruit v2和Fruit-80的差分錯誤攻擊(DFA)。筆者所提出的攻擊對Fruit v2和Fruit-80進(jìn)行差分錯誤分析。研究結(jié)果表明，精確識別單個錯誤所需的預(yù)計算階段的時間復(fù)雜度為O(226.5)，數(shù)據(jù)復(fù)雜度為O(211.5)。以概率1識別Fruit v2單個錯誤的復(fù)雜度為O(26.3)，識別Fruit-80的復(fù)雜度為O(27.3)。Fruit v2和Fruit-80恢復(fù)內(nèi)部狀態(tài)的復(fù)雜度為O(216.3)(線性反饋移位寄存器)和O(26.2)(非線性反饋移位寄存器)。而在恢復(fù)密鑰部分，如果使用猜測部分密鑰簡化方程的方式恢復(fù)密鑰，F(xiàn)ruit v2恢復(fù)全部密鑰的復(fù)雜度為O(260)，而Fruit-80恢復(fù)全部密鑰的復(fù)雜度為O(277)，因此與Fruit v2相比，F(xiàn)ruit-80具有更強(qiáng)的抗差分錯誤攻擊的能力。但是如果使用SAT解算器求解非線性方程組來恢復(fù)密鑰，只需要大約10 min即可完成所有方程的求解，對Fruit-80具有很大的威脅，需要引起更多的關(guān)注。