馬云飛，王 韜，陳 浩，黃長陽

(軍械工程學(xué)院 信息工程系，石家莊 050003) (*通信作者電子郵箱fcz1992@sina.com)

輕量級(jí)分組密碼SIMON代數(shù)故障攻擊

馬云飛*，王 韜，陳 浩，黃長陽

(軍械工程學(xué)院 信息工程系，石家莊 050003) (*通信作者電子郵箱fcz1992@sina.com)

針對(duì)SIMON現(xiàn)有故障攻擊中存在的故障深度小、手工推導(dǎo)復(fù)雜等問題，給出一種代數(shù)故障攻擊(AFA)方法。首先給出SIMON核心運(yùn)算‘&’代數(shù)表示方法并構(gòu)建全輪正確加密代數(shù)方程組；其次注入故障并將故障信息表示為代數(shù)方程，提供故障已知和故障未知兩種模型，給出兩種模型故障表示方法；最后利用CryptoMinisat- 2.9.6解析器求解方程組恢復(fù)密鑰。實(shí)驗(yàn)結(jié)果表明：利用單比特故障對(duì)SIMON32/64進(jìn)行攻擊，故障位置選取第26輪，故障已知和未知模型僅需5個(gè)和6個(gè)故障即可恢復(fù)全輪密鑰；利用n比特寬度故障對(duì)SIMON128/128進(jìn)行攻擊，故障位置選取第65輪，兩種模型均只需2個(gè)故障即可恢復(fù)全輪密鑰。此外，對(duì)比故障已知和未知模型發(fā)現(xiàn)，隨故障數(shù)遞增密鑰求解時(shí)間的決定因素將由故障信息量變?yōu)榉匠探M計(jì)算量。

SIMON;故障攻擊;代數(shù)攻擊;代數(shù)故障攻擊;輕量級(jí)分組密碼

0 引言

SIMON[1]是一類特別適合于資源受限環(huán)境的超輕量級(jí)分組密碼。自2013年被美國國家安全局提出以來，SIMON受到了學(xué)者廣泛關(guān)注,主要攻擊方法包括：線性攻擊[2]、不可能差分攻擊[3-4]、代數(shù)攻擊[5]、立方攻擊[6]。與其他輕量級(jí)分組密碼不同，絕大部分SIMON密碼要求的門電路數(shù)小于1 000(輕量級(jí)分組密碼要求門電路數(shù)小于2 000)，這使得SIMON在硬件和軟件方面均表現(xiàn)出良好的性能。

故障攻擊[7]是一種利用密碼設(shè)備在外界干擾下(溫度、電壓、電磁脈沖等)[8-9]產(chǎn)生的故障行為或錯(cuò)誤信息來恢復(fù)密鑰的攻擊方法。它由Boneh等在1996年首次提出，并成功破解了RSA(Rivest-Shamir-Adleman)簽名算法。1997年，Biham等[10]將差分思想與故障攻擊結(jié)合，提出了差分故障攻擊(Differential Fault Attack, DFA)。2010年，Courtois等[11]提出代數(shù)故障攻擊(Algebraic Fault Attack, AFA)思想，解決了差分故障攻擊手工分析復(fù)雜、故障信息利用率低、通用性差的問題，實(shí)現(xiàn)了故障攻擊的自動(dòng)化。此后，研究者又對(duì)PRESENT[12]、Piccolo[13]等密碼進(jìn)行了代數(shù)故障攻擊。

目前關(guān)于SIMON的故障攻擊研究現(xiàn)狀如下：在FDTC2014上，Tupsamudre等[14]假設(shè)故障注入倒數(shù)第2輪左半部分，利用單比特模型和單字節(jié)模型，通過差分推導(dǎo)得出結(jié)論“至少需要n/2個(gè)單比特故障或者n/8個(gè)單字節(jié)故障可以恢復(fù)最后一輪n比特輪密鑰”。Takahashi等[15]針對(duì)同樣的注入位置，將故障寬度擴(kuò)展到半輪。他們主要分析了SIMON核心部件‘&’的差分特性。實(shí)驗(yàn)結(jié)果表明，僅需要7.82個(gè)故障可以恢復(fù)SIMON128/128的全部輪密鑰。在FDTC2015上，Vásquez等[16]在文獻(xiàn)[14]基礎(chǔ)上，將單比特故障注入位置加深1輪，利用相似的差分分析方法，降低了攻擊所需要的故障數(shù)量同時(shí)減少了選取的故障注入位置。

盡管對(duì)SIMON的差分故障攻擊取得了較好的攻擊效果，但是上述研究存在如下問題：1)故障深度較小。由于故障注入較深輪時(shí)，故障傳播路徑復(fù)雜，差分攻擊難以根據(jù)最后一輪輸出推斷出故障的傳播情況，因此差分攻擊往往只能實(shí)現(xiàn)淺輪故障注入的分析；2)差分攻擊需要復(fù)雜的手工推導(dǎo)，自動(dòng)化、通用性較差。

針對(duì)上述問題，本文給出SIMON密碼代數(shù)故障攻擊。主要工作和創(chuàng)新點(diǎn)如下：1)采用單比特故障已知和故障未知模型對(duì)SIMON32/64進(jìn)行代數(shù)故障攻擊，故障位置選取第26輪，兩種模型分別僅需5個(gè)和6個(gè)故障即可恢復(fù)全部密鑰，優(yōu)于文獻(xiàn)[16]所需的50.85個(gè)故障；2)采用n比特寬度故障已知和未知模型對(duì)SIMON128/128進(jìn)行代數(shù)故障攻擊，故障位置選取第65輪，兩種模型均只需2個(gè)故障即可恢復(fù)全部密鑰，優(yōu)于文獻(xiàn)[15]所需的7.82個(gè)故障；3)對(duì)比故障已知和未知模型，發(fā)現(xiàn)當(dāng)故障數(shù)較小時(shí)，故障信息量與密鑰求解時(shí)間成反比，而當(dāng)故障數(shù)較大時(shí)，故障信息量與密鑰求解時(shí)間成正比。

1 SIMON系列密碼

SIMON系列輕量級(jí)分組密碼采用平衡Feistel結(jié)構(gòu)。為了提高算法靈活性，設(shè)計(jì)者提供了10個(gè)版本，均可用SIMON 2n/mn表示(如表1)。其中：n代表字長，2n表示分組長度，mn表示密鑰長度。這10個(gè)版本分別為：32/64，48/72，48/96，64/96，64/128，96/96，96/144，128/128，128/192，128/256。本文選擇的研究對(duì)象是SIMON32/64、SIMON128/128。

表1 SIMON系列密碼參數(shù)

1.1 輪函數(shù)

SIMON輪函數(shù)(見圖1)包含3種操作：按位異或(⊕)、按位與(&)、循環(huán)左移(<<<)。

圖1 SIMON輪函數(shù)

設(shè)Lr和Rr分別表示經(jīng)過r輪加密后中間狀態(tài)的左半部分和右半部分，則對(duì)于輪密鑰Kr∈GF(2)n,SIMON每一輪加密過程可以用式(1)表示：

(1)

其中F(Lr)=((Lr<<<1)&(Lr<<<8))⊕(Lr<<<2)。

1.2 密鑰擴(kuò)展算法

SIMON系列分組密碼的輪函數(shù)是相同的，其不同之處在于密鑰擴(kuò)展算法。假設(shè)初始密鑰為K0，K1，…，Km-1,利用輪密鑰遞推公式可以得到全部輪密鑰K0，K1，…，Kr-1。根據(jù)初始密鑰字長m不同，遞推公式分為3種：

Ki=

其中，常量c=0xff…fc，c的二進(jìn)制位數(shù)與輪密鑰Ki相同。z0,z1,z2,z3,z4是5個(gè)不同的二進(jìn)制常量數(shù)列，不同版本的SIMON密碼可采用不同的z，關(guān)于z0,z1,z2,z3,z4數(shù)列的具體值可以參考文獻(xiàn)[1]。

2 代數(shù)故障攻擊框架

如圖2所示，P、C、K分別代表明文，密文以及初始密鑰。假設(shè)U表示故障注入輪的中間狀態(tài)，Uf表示故障注入后的中間狀態(tài)，KU表示從故障注入輪到最后一輪的輪密鑰集合，則正確明文C=F(U,KU)，而錯(cuò)誤密文C*=F(Uf,KU)。正確加密和錯(cuò)誤加密過程之間最明顯的關(guān)聯(lián)是：ΔU=U⊕Uf，ΔC=C⊕C*。此外，如果能夠推斷出故障注入位置，通過分析故障傳播路徑，還可以得到更多關(guān)于正確、錯(cuò)誤加密的關(guān)系式。一般的代數(shù)故障攻擊共分為3步。

圖2 AFA框架

1)構(gòu)建正確加密過程代數(shù)方程。

在代數(shù)攻擊中，為充分利用明文和密文信息，首先要構(gòu)建全輪加密過程的代數(shù)方程。這需要攻擊者對(duì)密碼的輪函數(shù)以及密鑰擴(kuò)展算法進(jìn)行深入的分析；更重要的是，他們能夠?qū)⒁环N密碼的核心操作表示成代數(shù)方程，例如S盒、模加運(yùn)算、‘&’運(yùn)算等。

2)故障信息利用。

首先，攻擊者需要決定故障模型，一個(gè)故障模型由3部分組成：故障注入位置，故障寬度以及故障是否已知。故障注入位置可以是某一輪，也可以是某一輪的一部分，例如在文獻(xiàn)[14]中選取倒數(shù)第二輪左半部分。故障寬度是指一次故障注入可能會(huì)影響到的比特位數(shù)，典型的故障寬度有：1(bit)，4(Nibble)，8(Byte)。故障是否已知是指攻擊者在注入故障后，是否知道故障準(zhǔn)確信息。故障已知模型側(cè)重于理論分析，主要用于探究密碼特性，而故障未知模型更加側(cè)重實(shí)際，用于評(píng)估密碼的安全性。在確定了故障模型后，便可分析故障傳播路徑，列出關(guān)于故障信息的代數(shù)方程。一個(gè)有效方程要保證同時(shí)包含正確加密變量和錯(cuò)誤加密變量。

3)代數(shù)方程組求解。

在將正確加密過程和故障信息全部轉(zhuǎn)化為代數(shù)方程后，需要利用一定的方法來求解。由于方程數(shù)量較大，一般有4種方法：基于可滿足性問題(SATisfiability problem, SAT)的方法(借助Minisat、CryptoMinisat等解析器)，基于優(yōu)化的方法(借助CPLEX、SCIP解析器)，基于線性化的方法(直接線性化、擴(kuò)展線性化)以及基于Gr?bner基的方法。本文采取第一種方法，利用CryptoMinisat- 2.9.6進(jìn)行求解。

3 對(duì)SIMON32/64的代數(shù)故障攻擊

3.1 密鑰擴(kuò)展算法和輪函數(shù)的代數(shù)方程構(gòu)建

作為SIMON密碼的核心部件，‘&’操作可以通過降次實(shí)現(xiàn)。由于在SAT方法中，所有運(yùn)算都需要轉(zhuǎn)化為異或(⊕)和合取(∨)操作，因此可以利用式(2)所示方法，對(duì)‘&’進(jìn)行轉(zhuǎn)化。對(duì)于代數(shù)方程x1&x2⊕x3⊕x4⊕x5⊕x6=0，引入q=x1&x2，可將其轉(zhuǎn)化為式(3)：

(2)

(3)

對(duì)于SIMON32/64的密鑰擴(kuò)展算法，引入4組變量tmp1、tmp2、tmp3、tmp4，利用如下操作來表示整個(gè)過程，引入變量個(gè)數(shù)16×4×28=1 792,方程個(gè)數(shù)16×5×28=2 240。

此外，引入tmp5、tmp6、tmp7、tmp8，利用如下操作表示SIMON32/64全輪正確加密過程，引入變量個(gè)數(shù)16×4×32=2 048,方程個(gè)數(shù)(5×16+3×16)×32=4 096。

fori=1to32Ri=Li-1;tmp5=Li-1<<<1;tmp6=Li-1<<<8;tmp7=Li-1<<<2;tmp8=tmp5&tmp6;Li=tmp8⊕tmp7⊕Ri-1⊕Ki-1; end

3.2 故障模型設(shè)定

對(duì)SIMON32/64的攻擊采用單比特模型。為充分利用故障信息，盡可能將故障位置注入較深輪。經(jīng)過簡單估算，發(fā)現(xiàn)將單比特故障注入倒數(shù)第7輪時(shí)，最后一輪剛好可以覆蓋全部比特，此時(shí)故障信息利用程度最高，因此選擇L26作為故障注入位置。單比特故障注入L26,0時(shí)的故障傳播路徑如圖3所示。

圖3 單比特故障注入L26,0時(shí)的故障傳播路徑

3.3 故障已知模型

首先，構(gòu)建倒數(shù)6輪錯(cuò)誤加密過程代數(shù)方程。除此之外，在故障已知情況下，還可以找出更多關(guān)于正確和錯(cuò)誤加密中間狀態(tài)比特的關(guān)系式。以圖3為例，假設(shè)故障注入L26,0，可以得到式(4)～(10)。當(dāng)故障注入L26，R26其余位置時(shí)，故障信息表示的代數(shù)方程組與此類似。

(4)

(5)

(6)

(7)

(8)

(9)

(10)

3.4 故障未知模型

(1⊕x0)∨(1⊕x1)∨…∨(1⊕x31)=1

(11)

xu∨xv=1; 0≤u

(12)

4 對(duì)SIMON128/128的代數(shù)故障攻擊

4.1 故障模型設(shè)定

如圖4所示，T為SIMON128/128總輪數(shù)，文獻(xiàn)[15]采用的故障位置是LT-2，故障寬度為半輪長度nbit。該文獻(xiàn)通過分析‘&’的差分特性，能夠恢復(fù)SIMON128/128全部密鑰，且僅需要7.82個(gè)故障。本文試圖將故障注入位置加深1輪，故障寬度不變，進(jìn)一步證明代數(shù)故障攻擊的有效性。

圖4 文獻(xiàn)[15]使用的故障模型

4.2 故障已知模型

全輪正確加密代數(shù)方程組構(gòu)建與3.1節(jié)類似，這里不再贅述，主要關(guān)注故障信息的利用。以故障值ΔLT-3=0x 01 00 00 00 08 00 00 00為例，得到其故障傳播路徑如圖5所示，故障信息的代數(shù)方程表示與3.3節(jié)中類似。但是，總共有264種ΔLT-3，不可能把它們?nèi)勘硎境鰜?。這里采取一種動(dòng)態(tài)的方法：每次攻擊根據(jù)故障值推斷出故障傳播情況并且動(dòng)態(tài)地構(gòu)建代數(shù)方程組。

圖5 故障值ΔLT-3=0x 01 00 00 00 08 00 00 00時(shí)的故障傳播路徑

一種動(dòng)態(tài)的代數(shù)故障攻擊步驟如下：

1)根據(jù)ΔLT-3推斷故障傳播路徑。

假設(shè)Xt,m(T-3≤t≤T,0≤m≤127)表示t輪第m比特的故障傳播情況，Xt,m=1表示該比特受到了故障傳播的影響(不一定會(huì)發(fā)生翻轉(zhuǎn))，而Xt,m=0則表示不會(huì)受到影響。通過分析SIMON輪函數(shù)，容易得到Xt,m的迭代計(jì)算公式，如式(13)所示：

Xt,m=

(13)

2)動(dòng)態(tài)地構(gòu)建故障信息代數(shù)方程。

對(duì)所有Xt,m=1(0≤m≤63)，通過判斷Xt-1,(m+1)%64、Xt-1,(m+2)%64、Xt-1,(m+8)%64、Xt-1,m+64的值，可以動(dòng)態(tài)地構(gòu)建關(guān)于Xt,m的代數(shù)方程(14)：

(14)

4.3 故障未知模型

本文提供另外一種模型，在該模型下攻擊者不需要知道故障值。如圖6所示，為了更好地同故障已知模型比較，故障注入位置仍選取LT-3。盡管故障傳播的內(nèi)部結(jié)構(gòu)無法知道，但利用錯(cuò)誤密文仍然可以構(gòu)建代數(shù)方程。對(duì)每次故障注入，將后3輪的錯(cuò)誤加密過程用代數(shù)方程表示出來，并代入錯(cuò)誤密文。此時(shí)，中間狀態(tài)LT-3可看成是全新的變量，而RT-3保持與全輪正確加密時(shí)同樣的值，該值不變是正確加密與錯(cuò)誤加密過程的唯一聯(lián)系。即使如此，由于故障寬度較大，涉及的密鑰信息較多，在故障未知的情況下利用代數(shù)故障攻擊仍可求出唯一解，后續(xù)仿真實(shí)驗(yàn)驗(yàn)證了這一結(jié)論。

圖6 SIMON128/128故障未知模型

5 攻擊實(shí)驗(yàn)

5.1 實(shí)驗(yàn)配置

本文利用C++語言(Visual C++6.0)模擬故障注入過程，并通過程序?qū)⒋鷶?shù)方程組全部寫入一個(gè)記事本，最后使用CryptoMinisat解析器進(jìn)行密鑰求解。解析器版本為2.9.6，程序運(yùn)行環(huán)境如下：Intel i5- 4570芯片,3.20 GHz,4.00 GB內(nèi)存,Windows 7(32位)操作系統(tǒng)。

5.2 SIMON32/64攻擊結(jié)果

下面給出一個(gè)攻擊實(shí)例。

1)SIMON32/64全輪正確加密方程構(gòu)建。

固定初始密鑰K(K0,K1,K2,K3)=0x 0100 0908 1110 1918，隨機(jī)生成明文P=0x 9ae5 173a，正確加密產(chǎn)生密文C=0x 99e3 7944。利用3.1節(jié)所述方法構(gòu)建全輪正確加密代數(shù)方程組。

2)故障注入及故障信息利用。

利用程序仿真故障注入過程，在第26輪注入單比特隨機(jī)故障，4次實(shí)驗(yàn)得到4個(gè)錯(cuò)誤密文：C1=0x 4d03 5804,C2=0x 01f5 de92,C3=0x d817 2131,C4=0x 670b 9b97。在故障已知模型下，假設(shè)攻擊者已知故障注入位置，可以利用該信息，而在故障未知模型下，則不能使用該信息。根據(jù)3.3、3.4節(jié)所述方法構(gòu)建故障信息方程，在故障已知模型下，總共引入8 083個(gè)變量，10 469個(gè)代數(shù)表達(dá)式，腳本大小約189 KB。在故障未知模型下，總共引入8 173個(gè)變量，11 921個(gè)代數(shù)表達(dá)式，腳本大小約為204 KB。

3)基于SAT的代數(shù)方程組求解。

利用CryptoMinisat執(zhí)行代數(shù)方程組腳本，在兩種模型下得到相同結(jié)果，如表2所示，初始密鑰64比特編號(hào)為2～65，其中編號(hào)為負(fù)代表密鑰值是0，編號(hào)為正代表密鑰值是1。根據(jù)表2，求得的密鑰值是：0000000100000000000010010000100000010001000100000001100100011000,轉(zhuǎn)換為十六進(jìn)制，即：0x 0100 0908 1110 1918, 求解結(jié)果正確。

表2 解析器求解代數(shù)方程組結(jié)果

此外，提高故障數(shù)作進(jìn)一步實(shí)驗(yàn)。當(dāng)密鑰求解時(shí)間超過3 600 s時(shí)，認(rèn)為攻擊失敗。對(duì)每個(gè)故障數(shù)，分別執(zhí)行100次攻擊，觀察攻擊成功率和平均求解時(shí)間隨故障數(shù)增長的變化情況(見圖7～8)。得出下列結(jié)論：

圖7 故障已知模型不同故障數(shù)攻擊結(jié)果

1)在故障已知模型中，當(dāng)故障數(shù)≥5時(shí)，攻擊成功率≥99%，因此為保證成功率故障數(shù)至少為5。此外，觀察發(fā)現(xiàn)當(dāng)故障數(shù)≥7時(shí)，利用CryptoMinisat- 2.9.6解析器求解時(shí)間均小于1 s。

2)在故障未知模型中，當(dāng)故障數(shù)≥6時(shí)，攻擊成功率≥97%，因此為保證成功率故障數(shù)至少為6。當(dāng)故障數(shù)為20時(shí)，平均求解時(shí)間仍然有224 s，可見求解速度大大低于故障已知模型，這是由于該模型可利用的故障信息較少。

3)一般情況下，隨故障數(shù)增加成功率會(huì)提高，而平均求解時(shí)間會(huì)降低，但圖8中的折線出現(xiàn)一定的波動(dòng)，原因是：隨著故障數(shù)增加，雖然信息量多了，但過多的方程數(shù)可能增加了計(jì)算負(fù)擔(dān)，使得求解時(shí)間出現(xiàn)反彈。

圖8 故障未知模型不同故障數(shù)攻擊結(jié)果

5.3 SIMON128/128攻擊結(jié)果

對(duì)SIMON128/128的仿真實(shí)驗(yàn)與SIMON32/64類似。實(shí)驗(yàn)表明，利用兩種模型對(duì)SIMON128/128進(jìn)行代數(shù)故障攻擊，均只需要2個(gè)故障即可實(shí)現(xiàn)。在兩種模型下，利用2個(gè)故障分別執(zhí)行200次攻擊實(shí)驗(yàn)，求解時(shí)間分布如圖9～10所示。結(jié)果表明：在故障已知模型中，大部分隨機(jī)數(shù)據(jù)可以在10 s內(nèi)得出結(jié)果，而在故障未知模型中需要的時(shí)間則相對(duì)較多。這主要是由于兩種模型能夠利用的故障信息量不同導(dǎo)致的。上述兩種模型攻擊成功率分別為98.5%和94.81%。

圖9 故障已知模型求解時(shí)間分布(故障數(shù)=2)

此外，進(jìn)一步增加故障數(shù)量，對(duì)于每個(gè)故障數(shù)分別作200組隨機(jī)數(shù)據(jù)攻擊實(shí)驗(yàn)。如圖11所示，當(dāng)故障數(shù)>2時(shí)，兩種模型平均求解時(shí)間均小于1 s。觀察發(fā)現(xiàn)：故障已知模型一開始平均求解時(shí)間低于故障未知模型，這是由于故障已知模型中可以獲得的故障信息更多；但隨著故障數(shù)的遞增，故障已知模型的平均求解時(shí)間開始高于故障未知模型，因?yàn)榇藭r(shí)兩種模型的故障信息都已足夠，代數(shù)方程數(shù)量成為了決定求解時(shí)間的主要因素。

5.4 同已有工作的比較

本文對(duì)SIMON密碼代數(shù)故障攻擊結(jié)果與已有工作的比較如表3～4所示。代數(shù)故障攻擊與差分故障相比，具有下列優(yōu)點(diǎn)：1)故障注入深度較大。代數(shù)故障攻擊無需進(jìn)行具體推導(dǎo)，只要列出描述故障信息的代數(shù)方程即可，因此它能夠?qū)崿F(xiàn)較深輪的故障分析。2)故障數(shù)較少。由于代數(shù)故障攻擊能夠?qū)⒐收献⑷胼^深輪，且能充分利用故障信息，因此它所需的故障數(shù)大大低于差分故障攻擊。3)攻擊通用性強(qiáng)，自動(dòng)化程度高。差分故障攻擊需結(jié)合具體密碼進(jìn)行推導(dǎo)，相比之下，代數(shù)故障攻擊方法相對(duì)固定，且攻擊過程利用解析器完成，自動(dòng)化程度較高。

圖10 故障未知模型求解時(shí)間分布(故障數(shù)=2)

圖11 兩種模型平均求解時(shí)間隨故障數(shù)變化

表3 對(duì)SIMON32/64的攻擊結(jié)果

表4 對(duì)SIMON128/128的攻擊結(jié)果

6 結(jié)語

本文對(duì)SIMON32/64和SIMON128/128進(jìn)行代數(shù)故障攻擊，相比原有差分故障攻擊，提高了故障深度，大大減少了所需故障數(shù)，且整個(gè)攻擊過程通用性強(qiáng)、自動(dòng)化程度高。SIMON密碼的設(shè)計(jì)者主要考慮了算法實(shí)現(xiàn)的簡易，而沒有考慮代數(shù)故障攻擊的可能性，因此需要對(duì)密碼設(shè)備加強(qiáng)防護(hù)以防范此類攻擊。

References)

[1] BEAULIEU R, SHORS D, SMITH J, et al. The SIMON and speck families of lightweight block ciphers [EB/OL]. (2013- 06- 19) [2017- 01- 16]. http://eprint.iacr.org/2013/404.pdf.

[2] ALIZADEH J, BAGHERI N, GAURAVARAM P, et al. Linear cryptanalysis of round reduced SIMON [EB/OL]. (2014- 10- 16) [2017- 01- 16]. http://eprint.iacr.org/2013/663.pdf.

[3] ALKHZAIMI H A, LAURIDSEN M M. Cryptanalysis of the SIMON family of block ciphers [EB/OL]. (2013- 08- 28) [2017- 01- 16]. http://eprint.iacr.org/2013/543.pdf.

[4] ALIZADEH J, ALKHZAIMI H A, AREF M R, et al. Cryptanalysis of SIMON variants with connections [C]// RFIDSec 2014: Proceedings of the 10th Workshop on Radio Frequency Identification: Security and Privacy Issues. Berlin: Springer, 2014: 90-107.

[5] RADDUM H. Algebraic analysis of the SIMON block cipher family [C]// LatinCrypt 2015: Proceedings of the Fourth International Conference on Cryptology and Information Security in Latin America. Berlin: Springer, 2015: 157-169.

[6] 萬劉蟬,韋永壯.簡化SIMON類算法的立方測試與分析[J].計(jì)算機(jī)應(yīng)用研究,2017,34(1):246-250.(WAN L C, WEI Y Z. Cube test and analysis for reduced SIMON family of block ciphers [J]. Application Research of Computers, 2017, 34(1): 246-250.)

[7] BONEH D, DEMILLO R A, LIPTON R J. On the importance of checking cryptographic protocols for faults [C]// EUROCRYPT 1997: Proceedings of the 14th Annual EUROCRYPT Conference on the Theory and Applications of Cryptologic Techniques. Berlin: Springer, 1997: 37-51.

[8] BAR-EL H, CHOUKRI H, NACCACHE D, et al. The sorcerer’s apprentice guide to fault attack [EB/OL]. (2004- 05- 07) [2017- 01- 16]. http://eprint.iacr.org/2004/100.pdf.

[9] FUKUNAGA T, TAKAHASHI J. Practical fault attack on a cryptographic LSI with ISO/IEC 18033- 3 block ciphers [C]// FDTC 2009: Proceedings of the 2009 Fault Diagnosis and Tolerance in Cryptography. New York: ACM, 2009: 84-92.

[10] BIHAM E, SHAMIR A. Differential fault analysis of secret key cryptosystems [C]// CRYPTO 1997: Proceedings of the 17th Annual International Cryptology Conference. Berlin: Springer, 1997: 513-525.

[11] COURTOIS N, WARE D, JACKSON K. Fault-algebraic attacks on inner rounds of DES [EB/OL]. (2010- 09- 22) [2017- 01- 16]. http://www.nicolascourtois.com/papers/dfasolv.pdf.

[12] 吳克輝,趙新杰,王韜,等.PRESENT密碼代數(shù)故障攻擊[J].通信學(xué)報(bào),2012,33(8):85-92.(WU K H, ZHAO X J, WANG T, et al. Algebraic fault attack on PRESENT [J]. Journal on Communications, 2012, 33(8): 85-92.)

[13] 趙新杰,郭世澤,王韜,等.Piccolo密碼代數(shù)故障分析研究[J].計(jì)算機(jī)學(xué)報(bào),2013,36(4):882-894.(ZHAO X J, GUO S Z, WANG T, et al. Research of algebraic fault analysis on Piccolo [J]. Chinese Journal of Computers, 2013, 36(4): 882-894.)

[14] TUPSAMUDRE H, BISHT S, MUKHOPADHYAY D. Differential fault analysis on the families of SIMON and SPECK ciphers [EB/OL]. (2014- 05- 30) [2017- 01- 16]. http://eprint.iacr.org/2014/267.pdf.

[15] TAKAHASHI J, FUKUNAGA T. Fault analysis on SIMON family of lightweight block ciphers [C]// ICISC 2014: Proceedings of the 2014 International Conference on Information Security and Cryptology. Berlin: Springer, 2014: 175-189.

[16] VáSQUEZ J C G, BORGES F, PORTUGAL R, et al. An efficient one-bit model for differential fault analysis on SIMON family [C]// FDTC 2015: Proceedings of the 2015 Fault Diagnosis and Tolerance in Cryptography. Washington DC: IEEE Computer Society, 2015: 61-70.

This work is partially supported by the National Natural Science Foundation of China (61272491, 61309021, 61472357).

MAYunfei, born in 1992, M. S. candidate. His research interests include side-channel cube attack on lightweight block ciphers, algebraic fault attack.

WANGTao, born in 1964, Ph. D., professor. His research interests include network security, cryptology.

CHENHao, born in 1987, Ph. D. candidate. His research interests include algebraic fault attack on stream ciphers.

HUANGChangyang, born in 1994, M. S. candidate. His research interest include side-channel attack on symmetric ciphers.

AlgebraicfaultattackonlightweightblockciphersSIMON

MA Yunfei*, WANG Tao, CHEN Hao, HUANG Changyang

(DepartmentofInformationEngineering,OrdnanceEngineeringCollege,ShijiazhuangHebei050003,China)

To solve the problems of small fault depth and complex manual deduction in previous fault attacks on SIMON, an Algebraic Fault Attack (AFA) method was proposed. Firstly, Correct equations of full-round SIMON encryption was established based on the algebraic representation of SIMON core operation ‘&’. Then faults were injected into the internal states and two models were provided for fault representation based on whether attackers knew the exact fault information or not. Finally, a CryptoMinisat- 2.9.6 solver was used for round-keys recovery. The simulation results show that the fault-known and fault-unknown model need 5 and 6 faults to recover the entire key set with single-bit faults injected in the 26th round of SIMON32/64. As for SIMON128/128, two models both need only 2 faults to recover the entire key set withn-bit length faults injected in the 65th round. Moreover, it can be found that the influencing factor of average solving time will change from fault information to computation with fault number growing.

SIMON; fault attack; algebraic attack; Algebraic Fault Attack (AFA); lightweight block cipher

TP309.2

:A

2017- 02- 08;

:2017- 03- 18。

國家自然科學(xué)基金資助項(xiàng)目(61272491, 61309021, 61472357)。

馬云飛(1992—)，男，吉林德惠人，碩士研究生，主要研究方向：輕量級(jí)分組密碼旁路立方攻擊、代數(shù)故障攻擊； 王韜(1964—)，男，河北石家莊人，教授，博士生導(dǎo)師，主要研究方向：網(wǎng)絡(luò)安全、密碼學(xué)； 陳浩(1987—)，男，湖北武漢人，博士研究生，主要研究方向：流密碼代數(shù)故障攻擊； 黃長陽(1994—)，男，黑龍江望奎人，碩士研究生，主要研究方向：對(duì)稱密碼旁路攻擊。

1001- 9081(2017)07- 1953- 07

10.11772/j.issn.1001- 9081.2017.07.1953