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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 SIMON系列密碼

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

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

1.1 輪函數(shù)

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

圖1 SIMON輪函數(shù)

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

(1)

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

1.2 密鑰擴展算法

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

Ki=

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

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

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

圖2 AFA框架

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

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

2)故障信息利用。

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

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

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

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

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

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

(2)

(3)

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

此外，引入tmp5、tmp6、tmp7、tmp8，利用如下操作表示SIMON32/64全輪正確加密過程，引入變量個數(shù)16×4×32=2 048,方程個數(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 故障模型設定

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

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

3.3 故障已知模型

首先，構建倒數(shù)6輪錯誤加密過程代數(shù)方程。除此之外，在故障已知情況下，還可以找出更多關于正確和錯誤加密中間狀態(tài)比特的關系式。以圖3為例，假設故障注入L26,0，可以得到式(4)～(10)。當故障注入L26，R26其余位置時，故障信息表示的代數(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 對SIMON128/128的代數(shù)故障攻擊

4.1 故障模型設定

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

圖4 文獻[15]使用的故障模型

4.2 故障已知模型

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

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

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

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

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

Xt,m=

(13)

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

對所有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的值，可以動態(tài)地構建關于Xt,m的代數(shù)方程(14)：

(14)

4.3 故障未知模型

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

圖6 SIMON128/128故障未知模型

5 攻擊實驗

5.1 實驗配置

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

5.2 SIMON32/64攻擊結果

下面給出一個攻擊實例。

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3 SIMON128/128攻擊結果

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

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

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

5.4 同已有工作的比較

本文對SIMON密碼代數(shù)故障攻擊結果與已有工作的比較如表3～4所示。代數(shù)故障攻擊與差分故障相比，具有下列優(yōu)點：1)故障注入深度較大。代數(shù)故障攻擊無需進行具體推導，只要列出描述故障信息的代數(shù)方程即可，因此它能夠實現(xiàn)較深輪的故障分析。2)故障數(shù)較少。由于代數(shù)故障攻擊能夠將故障注入較深輪，且能充分利用故障信息，因此它所需的故障數(shù)大大低于差分故障攻擊。3)攻擊通用性強，自動化程度高。差分故障攻擊需結合具體密碼進行推導，相比之下，代數(shù)故障攻擊方法相對固定，且攻擊過程利用解析器完成，自動化程度較高。

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

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

表3 對SIMON32/64的攻擊結果

表4 對SIMON128/128的攻擊結果

6 結語

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

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].計算機應用研究,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].通信學報,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].計算機學報,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。

國家自然科學基金資助項目(61272491, 61309021, 61472357)。

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

1001- 9081(2017)07- 1953- 07

10.11772/j.issn.1001- 9081.2017.07.1953