針對(duì)Fruit v2和Fruit-80的差分錯(cuò)誤攻擊

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

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

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

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

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

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

1 Fruit流密碼的介紹

Fruit系列流密碼是超輕量級(jí)小狀態(tài)流密碼的最新版本，正是由于它較小的內(nèi)部狀態(tài)吸引了全世界密碼學(xué)界的廣泛關(guān)注。該系列目前由4個(gè)版本的密碼組成：Fruit v2、Fruit-80、Fruit-128和Fruit-F。每個(gè)版本的密碼在密碼分析方面都有獨(dú)特的挑戰(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作為更易于實(shí)現(xiàn)和安全的更新版本而出現(xiàn)[18]。

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

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

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

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

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

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

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

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

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

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

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

LFSR：設(shè)m為線性反饋移位寄存器的內(nèi)部狀態(tài)的大小，Lt=(lt，…，lt+m-1)為線性反饋移位寄存器在時(shí)刻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和計(jì)數(shù)器：設(shè)m′為非線性反饋移位寄存器的內(nèi)部狀態(tài)的大小，Nt=(nt，…，nt+m′-1)為t時(shí)刻非線性反饋移位寄存器的內(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ù)少了計(jì)數(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，兩個(gè)計(jì)數(shù)器均置為0，F(xiàn)ruit v2的IV通過在前面添加1個(gè)比特1和9個(gè)比特0，在后面添加50個(gè)比特0，擴(kuò)展為130個(gè)比特IV′，形如：IV′=1000000000v0v1，…，v6900…00。Fruit-80的IV通過在前面添加1個(gè)比特1和9個(gè)比特0擴(kuò)展為80個(gè)比特IV′，即，IV′=1000000000v0v1，…，v69。

2 故障位置檢測算法

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

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

(1)St=[nt，nt+1，…，nt+m′-1，lt，lt+1，…，lt+m-1]，用于表示t時(shí)刻的內(nèi)部狀態(tài)。其中nt+i(lt+i)表示t時(shí)刻的第i位非線性反饋移位寄存器(線性反饋移位寄存器)。當(dāng)t=0時(shí)，為了方便起見，使用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)

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

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

(15)

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

(16)

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

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

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

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

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

(a) Fruit v2 (b) Fruit-80

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

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

① 在任意位置注入一個(gè)錯(cuò)誤δ；

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

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

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

算法1位置識(shí)別算法。

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

輸出：候選等級(jí)表Tδ。

Fori=1 toτdo

獲取錯(cuò)誤路徑：

Forφ=0 tom+m′ then

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

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

End

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

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

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

Tδ=[φ0]

ElseTδ=[φ0]

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

重復(fù)第1步

Tδ=[φ0，φ1]

以此類推

End

returnTδ。

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

3 針對(duì)Fruit v2和Fruit-80的差分錯(cuò)誤攻擊

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

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

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

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

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

例如，對(duì)于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}的一個(gè)仿射函數(shù)。

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

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

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

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

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

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

(18)

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

(19)

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

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

在注入錯(cuò)誤之前可以使用相同的(K，IV)對(duì)密碼進(jìn)行重置，F(xiàn)ruit v2和Fruit-80的密鑰流輸出函數(shù)的表達(dá)式為式(12)；由于現(xiàn)在線性反饋移位寄存器的內(nèi)部狀態(tài)已知，如果錯(cuò)誤位置在n33，那么注入錯(cuò)誤后產(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ù)密鑰。因?yàn)樵谳p量級(jí)流密碼算法中，密鑰不僅參與初始化階段，而且也參與了密鑰生成階段，這使得密鑰恢復(fù)變得更加困難。

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

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

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

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

(22)

對(duì)于Fruit v2，由于輪密鑰只參與非線性反饋移位寄存器的更新，因此可以通過輸出函數(shù)zt來獲取非線性反饋移位寄存器的反饋位(即n36)的值，再通過非線性反饋移位寄存器的更新函數(shù)獲取這一時(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ù)建立方程組

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

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

(24)

因此可以建立方程組：

(25)

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

(26)

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

3.3.3 檢測密鑰的正確性

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

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

3.4 復(fù)雜度分析

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

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

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

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

4 結(jié)束語

借鑒MAITRA等對(duì)Sprout的差分錯(cuò)誤攻擊和BANIK等對(duì)Grain的分析，在精確識(shí)別錯(cuò)誤的基礎(chǔ)上，筆者研究了在相對(duì)寬松的錯(cuò)誤模型下，針對(duì)Fruit v2和Fruit-80的差分錯(cuò)誤攻擊(DFA)。筆者所提出的攻擊對(duì)Fruit v2和Fruit-80進(jìn)行差分錯(cuò)誤分析。研究結(jié)果表明，精確識(shí)別單個(gè)錯(cuò)誤所需的預(yù)計(jì)算階段的時(shí)間復(fù)雜度為O(226.5)，數(shù)據(jù)復(fù)雜度為O(211.5)。以概率1識(shí)別Fruit v2單個(gè)錯(cuò)誤的復(fù)雜度為O(26.3)，識(shí)別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)的抗差分錯(cuò)誤攻擊的能力。但是如果使用SAT解算器求解非線性方程組來恢復(fù)密鑰，只需要大約10 min即可完成所有方程的求解，對(duì)Fruit-80具有很大的威脅，需要引起更多的關(guān)注。