輕量級分組密碼算法ESF的安全性分析

尹 軍 馬楚焱 宋 健 曾 光 馬傳貴

1(數學工程與先進計算國家重點實驗室(中國人民解放軍信息工程大學) 鄭州 450001)2(中國科學院信息工程研究所 北京 100093)3(中國科學院大學 北京 100049) 4(國防科學技術大學 長沙 410073)5(陸軍航空兵學院 北京 101116) (yinjun66888@163．com)

2017-06-11；

2017-08-03

國家自然科學基金項目(61502532,61379150,61772519,61309016,61502529)；數學工程與先進計算國家重點實驗室開放基金課題(2016A02)；河南省重點科技攻關計劃項目(122102210126,092101210502) This work was supported by the National Natural Science Foundation of China (61502532, 61379150, 61772519, 61309016, 61502529), the Open Foundation of the State Key Laboratory of Mathematical Engineering and Advanced Computing (2016A02), and the Key Scientific and Technological Project of Henan Province (122102210126, 092101210502).

輕量級分組密碼算法ESF的安全性分析

尹 軍1,2,3馬楚焱4宋 健1曾 光1馬傳貴5

1(數學工程與先進計算國家重點實驗室(中國人民解放軍信息工程大學) 鄭州 450001)2(中國科學院信息工程研究所 北京 100093)3(中國科學院大學 北京 100049)4(國防科學技術大學 長沙 410073)5(陸軍航空兵學院 北京 101116) (yinjun66888@163．com)

自動化分析是當前對密碼算法進行安全性評估的重要方法之一，具有高效、易實現的特點.對面向位的分組密碼，自從Sun等人在2014年亞洲密碼年會上提出基于MILP問題的差分和線性自動化搜索方法，該方法受到了許多密碼學者的關注.目前，針對求解多輪密碼算法MILP模型，如何減少變量和約束不等式的研究工作相對較少，還有很多問題有待解決.根據異或操作的差分傳播模式，在2017年歐洲密碼年會上，Sasaki等人給出了不帶假設變量的新約束不等式，該約束不等式在降低變量和約束數量的前提下保留了異或操作的差分傳播性質.同時，對于S盒的性質，當輸入差分變量(線性掩碼)非零時，該S盒必定活躍，Sun等人用了4個約束不等式來刻畫該性質，經過簡單的變換，可以用1個約束來表示該性質.基于這些精煉的約束和自動化搜索方法，針對輕量級分組密碼算法ESF，建立單密鑰下精煉的差分和線性MILP模型，首次給出了ESF算法在單密鑰情形下的差分和線性分析結果，得到了15輪ESF算法差分最小活躍S盒數量為19和16輪ESF算法線性最小活躍S盒數量為15.此外，還搜索到了輪數最長的不可能差分和零相關線性逼近區分器.

差分密碼分析；線性密碼分析；不可能差分；零相關線性逼近；ESF；MILP

當前，對于輕量級分組密碼的設計與分析越來越受到人們關注，密碼學者提出了許多輕量級分組密碼算法，比較知名的算法有LBlock[1]，PRESENT[2]，SKINNY[3]，RECTANGLE[4]等.

對分組密碼2種經典的密碼分析方法是差分密碼分析[5]和線性密碼分析[6].差分密碼分析是1990年由Biham和Shamir提出的，他們利用這種方法攻擊了DES密碼算法，其主要思想是通過分析一個特選的明文對差分對相應密文對差分的影響來恢復密鑰信息.差分攻擊最重要的步驟是尋找高概率差分特征.線性密碼分析是Matsui[6]在1993年的歐洲密碼年會(歐密會)上提出來的，它屬于已知明文攻擊范疇，通過分析明密文之間的線性關系，構建明密文之間線性偏差不為0的線性逼近表達式，利用該線性逼近表達式來恢復密鑰.此外，在上述2種密碼分析方法的基礎上，提出了許多擴展的密碼分析方法，例如不可能差分密碼分析[7]、零相關線性逼近[8]等，不可能差分密碼分析的基本思想就是利用概率為零(或者非常小)的差分特征，排除那些導致差分概率為零(或者非常小)的差分特征對應的密鑰.零相關線性逼近是由Bogdanov和Rijmen首次提出，通過尋找密碼算法中相關度為零的線性逼近表達式，區分密碼算法與隨機置換,進行密鑰恢復.

在上面2類密碼分析方法中，尋找最優的差分特征和線性逼近是進行有效攻擊的關鍵，其復雜度要低于暴力搜索.自動化分析是非常流行和高效的尋找最優差分和線性特征的方法，其主要思想是通過編程軟件，自動化搜索差分和線性特征.目前，這類工作已經取得了很多成果，在1994年歐洲密碼年會上，Matsui提出了分支定界搜索算法，搜索DES的差分特征[9];在2013年Mouha和Preneel構造了一個工具，基于可滿足性模問題(satisfiability modulo theories, SMT)，搜索流密碼Salsa20的最優差分特征[10];此外，計算活躍S盒數量的下界是另外一種評估分組密碼抵抗差分和線性分析的方法.在2011年Mouha等人將計算活躍S盒數量的問題轉化成混合整數線性規劃(mixed-integer linear programming, MILP)問題，應用于面向字的分組密碼[11];在2014年亞洲密碼年會上，Sun等人擴展了Mouha等人的方法,對面向位的分組密碼,在單密鑰和相關密鑰模型建立MILP模型，分別計算最小活躍S盒數量的下界，搜索到了許多密碼算法差分和線性特征[12]；2016年Cui等人在差分和線性MILP方法基礎上，實現了不可能差分和零相關線性逼近的自動化搜索[13].同時，在2017年歐洲密碼年會上，Sasaki等人擴展MILP方法，提出了新的自動化搜索不可能差分的工具[14].

ESF[15]是劉宣等人基于吳文玲研究員的 LBlock 算法改進的輕量級分組密碼算法，同時在置換層還采用了PRESENT算法的P置換形式，分組長度64 b,密鑰長度80 b.針對ESF的密碼分析,劉宣等人給出了ESF算法8輪不可能差分區分器來攻擊11輪 ESF算法[16]，攻擊的數據和時間復雜度分別是259和275.5.隨后，陳玉磊等人利用文獻[16]中劉宣等人給出的8輪不可能差分區分器，根據輪密鑰之間的關系，通過改變原有輪數擴展和密鑰猜測的順序，改進了11輪ESF的不可能差分攻擊結果，攻擊的數據和時間復雜度[17]分別是253和232.

本文的主要貢獻有4個方面：

1) 根據Sasaki等人在2017年亞洲密碼年會上給出的改進XOR操作約束*該約束出現在Sasaki等人在2017年歐洲密碼年會上作的報告slide中，具體請參考https://eurocrypt2017.di.ens.fr/slides/A09-new-impossible-differential.pdf.，以及我們改變的S盒相關的約束，建立了更加精煉的MILP模型，大大減少了建立MILP模型的約束和變量數量；

2) 基于精煉的MILP模型，建立單密鑰下ESF算法的差分和線性MILP模型，首次給出了ESF算法在單密鑰情形下的差分和線性分析結果；

3) 基于精煉的MILP模型，建立ESF算法的不可能差分和零相關線性逼近MILP模型，給出了ESF算法的不可能差分和零相關線性分析結果.

4) 在輸入輸出差分只有一個活躍半字節的情形下，通過Gurobi軟件求解該模型，搜索到了15輪ESF算法差分最小活躍S盒數量為19；在輸入輸出掩碼只有一個活躍比特位的情形下，搜索得到16輪ESF算法線性最小活躍S盒數量為15.此外，我們還搜索到最長9輪的不可能差分和8輪的零相關線性區分器.具體的攻擊結果如表1所示:

Table 1 The Attack Results for ESF

1 準備知識

本節首先給出常用的符號和術語說明，然后簡要描述輕量級分組密碼算法ESF.

1.1常用的符號和術語

Li:第i輪ESF算法輸出的左32 b;

Ri:第i輪ESF算法輸出的右32 b;

F:輪函數;

Ki:第i輪32 b子密鑰;

ΔX:表示X1和X2的差分，X1⊕X2=ΔX;

<<<7:循環左移7 b.

1.2ESF算法

ESF算法是基于Lblock算法改進的輕量級分組密碼算法，分組長度64 b，密鑰長度80 b，迭代輪數為32輪.ESF算法采用廣義的Feistel結構，輪函數為SPN結構.一輪的ESF加密流程如圖1所示*圖1和圖2由TikZ for Cryptographers產生，具體詳情請參考http://www.iacr.org/authors/tikz/..其中輪函數F為SPN結構，由非線性變換S函數和置換函數P組成，輪函數F如圖2所示.輪函數F為F(Ri,Ki)=P(S(Ki⊕Ri))，其中的S函數是一個非線性變換，由8個并行的4×4的S盒構成，8個S盒的具體分布如表2所示.

Fig. 1 1-round ESF encryption圖1 1輪ESF加密過程

Fig. 2 The round function of ESF圖2 ESF輪函數

Table 2 The S-Boxes of ESF

具體變換如下：

a=a7‖a6‖…‖a0→b=b7‖b6‖…‖b0,

b7=S7(a7),

b6=S6(a6),

b5=S5(a5),

b4=S4(a4),

b3=S3(a3),

b2=S2(a2),

b1=S1(a1),

b0=S0(a0).

P置換函數將32 b的(b31‖b30‖…‖b1‖b0)映射成(c31‖c30‖…‖c1‖c0)，具體如下：

b=(b31‖b30‖…‖b1‖b0)→c=(c31‖c30‖…‖c1‖c0),當i=0,1,…,7時，

b4i‖b4i+1‖b4i+2‖b4i+3→ci‖ci+8‖ci+16‖ci+24.

在本文中，我們只考慮單密鑰情形下的密碼分析.因此對于密鑰擴展算法，具體細節可參考文獻[15].

2 基于MILP問題的自動化分析技術

在本節中，我們主要介紹MILP，后面詳細介紹基于MILP模型自動化搜索差分特征、線性特征、不可能差分和零相關線性逼近，具體應用于ESF算法上產生約束不等式的過程.同時給出我們優化的MILP模型.

2.1混合整數線性規劃(MILP)

MILP問題是運籌學中的一類優化問題，旨在線性約束條件下求解目標函數的最小值或最大值.目前，求解這類問題目前有很多成熟的商業軟件，例如Gurobi[18],Cplex[19],MAGMA[20]等.下面具體給出MILP的定義.

定義1. MILP.假設A∈m×n，b∈m和c1,c2,…,cn∈n,尋找一個向量x=(x1,x2,…,xn),在相應的線性約束條件Ax≤b下求解線性函數c1x1+c2x2+…+cnxn的最小值或者最大值.

2.2建立改進的自動化搜索差分特征MILP模型

根據Sun等人對面向位的分組密碼建立差分特征自動化搜索方法，通過對密碼算法的每輪差分變量使用二元域上的0和1變量來描述，同時這些變量受限于密碼算法特殊的操作和結構.根據文獻[12,21]，下面介紹建立ESF算法差分特征搜索MILP模型的過程.

在ESF算法中，一共包含4個操作:循環移位、P置換、XOR(異或)操作、S盒，其中循環移位和P置換，可以根據相應的比特位置給出等式約束.重點考慮2個操作：

首先對于S盒，引入新的0-1變量At表示S盒是否活躍，定義為

2.2.1 ESF算法XOR操作差分約束

假設XOR操作的輸入差分分別為Δa和Δb，輸出差分為Δc.其中Δa=(Δa0,Δa1,…,Δa31)，Δb=(Δb0,Δb1,…,Δb31)，Δc=(Δc0,Δc1,…,Δc31).同時對0≤i≤31，滿足有Δai⊕Δbi=Δci.下面給出對異或操作差分約束：

(1)

其中,di是假設的0,1變量，0≤i≤31.

在2017年歐洲密碼年會上，Sasaki等人針對XOR操作，改進了Sun等人給出的約束式(1).給出了不帶假設的0-1變量約束式(2)，對于ESF算法，每輪可以減少32個變量和32個約束.這樣可以顯著減少求解MILP模型的時間，提高效率，增加攻擊輪數.

(2)

2.2.2 ESF算法S盒操作差分約束

假設(Δx0,Δx1,Δx2,Δx3)和(Δy0,Δy1,Δy2,Δy3)分別表示ESF算法4×4的S盒的輸入和輸出差分，At表示這個S盒是否活躍.

首先，為了保證Δx0,Δx1,Δx2,Δx3有任意一個是1時，At=1，用不等式約束：

我們通過分析上面的4個不等式，對其進行改進，使用1個不等式來表示這個約束條件：

Δx0+Δx1+Δx2+Δx3-4At≤0.

(3)

這樣給出的約束不等式能夠保證S盒差分傳播的正確性，同時，在建立ESF算法的MILP模型中，每輪可以減少24個約束.

其次，當At=1時，Δx0,Δx1,Δx2,Δx3必定有一個非零，用不等式約束為

Δx0+Δx1+Δx2+Δx3-At≥0.

(4)

最后,對于雙射的S盒,因為非零的輸入差分必然導致非零的輸出差分,反之亦然,用不等式約束為

(5)

除了式(3)～(5)對S盒差分的約束，Sun等人還提出了2套系統的方法，通過產生線性不等式來描述S盒的差分性質，使得刻畫的S盒差分性質更加精確.這2種方法分別是邏輯狀態模型和S盒所有可能差分模式的凸閉包H表示.對于第2種方法，在n維空間計算所有離散點的凸閉包H表示，通過SAGE中Sage.geometry.polyhedron類Inequality_generator()函數即可以得到凸閉包的H表示[22].但是，該函數產生的不等式非常多，對于ESF的每個S盒，都有大于300個不等式，因此要盡量減少不等式的數量，因此Sun等人設計了一個貪心算法來最大數量移除一部分不等式.表3給出了ESF算法8個S盒使用不同方法產生的不等式數量結果.

Table 3 The Number of Differential Inequalities Obtained by Different Methods

2.3建立自動化搜索線性特征MILP模型

為了自動化搜索ESF算法的線性特征，需要考慮ESF算法基本操作的線性掩碼傳播模式.因為位的旋轉是一個簡單的置換，可以根據相應的位給出等式約束，下面重點給出異或、分支和S盒操作的線性掩碼傳播約束.

首先對于S盒，引入新的0-1變量At表示線性活躍S盒，定義為

根據文獻[12,21]，下面具體給出對ESF算法操作的線性掩碼變量約束.

2.3.1 ESF算法XOR操作線性掩碼約束

假設ESF算法XOR操作中，a=(a0,a1,…,a31)和b=(b0,b1,…,b31)是異或操作的輸入掩碼，c=(c0,c1,…,c31)是其輸出掩碼，約束如下：

a=b=c.

2.3.2 ESF算法分支操作線性掩碼約束

在ESF算法分支操作中，a=(a0,a1,…,a31)是輸入掩碼，b=(b0,b1,…,b31)和c=(c0,c1,…,c31)是輸出掩碼，約束如下：對0≤i≤31，ai⊕bi⊕ci=0，根據式(2)，約束為

2.3.3 ESF算法S盒線性掩碼約束

假設(x0,x1,x2,x3)和(y0,y1,y2,y3)分別表示ESF算法4×4的S盒的輸入和輸出掩碼，At表示這個S盒是否活躍.

1) 為了保證輸出掩碼y0,y1,y2,y3有任意一個是1時，At=1，用不等式約束：

y0+y1+y2+y3-4At≤0.

(6)

2) 當At=1時，y0,y1,y2,y3必定有一個非零，用不等式約束：

y0+y1+y2+y3-At≥0.

(7)

3) 對于雙射的S盒，因為非零的輸入線性掩碼必然導致非零的輸出線性掩碼，反之亦然，用不等式約束：

(8)

除了式(6)～(8)對S盒線性掩碼的約束，計算S盒所有非零線性偏差線性掩碼傳播模式的凸閉包H表示，然后利用Sun等人給出的貪心算法來來選擇最大數量移除不可能線性掩碼模式不等式.通過不同方法產生的不等式數量結果如表4所示:

Table 4 The Number of Inequalities Obtained by Different Methods

對于異或操作約束、S盒操作約束、邏輯狀態模型、凸閉包H表示、貪心算法，詳細內容請參閱文獻[12,21].

2.4建立自動化搜索不可能差分MILP模型

為了搜索ESF算法的不可能差分，根據Cui等人和Sasaki等人給出的自動化搜索不可能差分工具，只需要簡單修改一下基于MILP模型的差分特征搜索工具，就可以得到自動化搜索不可能差分的MILP模型.

假設ΔI和ΔO分別表示輸入和輸出的差分，為了測試(ΔI,ΔO)是不可能的差分對，在建立的差分MILP模型中增加固定的輸入和輸出差分的某些比特作為約束，在該模型中不必考慮目標函數，如果MILP求解器輸出錯誤信息(例如Gurobi輸出infeasible)，那么就可以知道這是一條不可能差分路徑.

2.5建立自動化搜索零相關線性逼近MILP模型

基于MILP模型搜索零相關線性逼近，跟搜索不可能差分類似，只需要修改相應的線性特征MILP模型，就可以得到自動化搜索零相關線性逼近的MILP模型.

對于建立不可能差分和零相關線性逼近自動化分析MILP模型，詳細內容請參閱文獻[13-14].

3 輕量級分組密碼ESF的安全性分析

根據第2節所敘，結合ESF算法的加密過程，用Python編程分別產生自動化搜索差分特征、線性特征、不可能差分和零相關線性逼近“lp”文件格式的MILP模型，并且調用Gurobi7.0.2來求解相應的MILP模型.求解MILP模型的實驗環境在一臺服務器上進行，該服務器配置如表5所示：

Table 5 Experimental Environment for Solving MILP Model

3.1ESF算法差分分析結果

通過建立r輪ESF算法的差分MILP模型，可以知道產生的差分MILP模型有373r+1個不等式、72r+64個變量，ESF算法前15輪在單密鑰情形下差分活躍S盒數量的下界，如表6所示：

Table 6 The Results for Single-key Differential Analysis on ESF

從表6我們知道對于15輪的ESF算法最小差分活躍S盒數量是19.對于超過15輪的模型，由于求解花費的時間關系(超過15 d)，我們只考慮前15輪的模型.因為ESF算法S盒的最優差分概率是2-2，估計全輪(32=15+15+2)的ESF最大差分概率是(2-2)19+19+1=2-78，小于暴力搜索成功的概率2-64.因而，我們證明ESF對單密鑰差分攻擊是安全的.

3.2ESF算法線性分析結果

建立r輪ESF算法的線性MILP模型，對于r輪ESF算法，線性MILP模型有421r+1個不等式、104r+64個變量.ESF算法前16輪在單密鑰情形下線性活躍S盒數量的下界，如表7所示.

從表7可知，對于16輪的ESF算法最小線性活躍S盒數量是15.對于超過16輪的模型，跟ESF算法差分分析一樣，由于求解模型花費的時間關系(超過12 d)，我們只考慮前16輪的模型.因為ESF算法S盒的最大線性偏差為ε=±2-2，估計全輪(32=16+16)的ESF最小活躍S盒數量為30(實際的大于30)，由堆積引理[6]，最大線性偏差的平方為ε2=2-58,那么對全輪的線性攻擊需要已知的明文量約為258，小于暴力搜索需要的明文量264.但是，實際所需要的明文量肯定比258大，是否存在全輪活躍S盒數小于32的線性路徑仍然不能確定.因而，對于證明全輪ESF是否抵抗線性攻擊仍然是一個開放問題.

Table 7 The Results for Linear Analysis on ESF

3.3ESF算法不可能差分分析結果

根據2.4節自動化搜索不可能差分方法，建立r輪ESF算法的不可能差分MILP模型.即在相應的差分MILP模型的基礎上增加2個約束，分別將輸入和輸出差分的1個半字節位置固定為常數，其他位置為0，并計算模型是否有解,總共需要遍歷(16×16)2=216種情形.共搜索到2 108條9輪ESF的不可能差分，沒有搜索到10輪的不可能差分.其中7條如下所示(輸入輸出數值用16進制表示):

3.4ESF算法零相關線性逼近分析結果

根據2.5節自動化搜索零相關線性逼近的方法，建立r輪ESF算法的零相關線性逼近MILP模型，對于每輪的MILP模型，分別在相應的線性MILP模型基礎上增加了2個約束，分別是固定輸入和輸出掩碼的1個比特位置為1，其他位全為0，總共需要遍歷642=4096種情形.共搜索到925條8輪的零相關線性逼近，在此條件下，沒有搜索到9輪的零相關線性逼近.其中的7條如下所示(輸入輸出數值用16進制表示)：

4 結束語

在本文中，基于Sun等人給出的差分和線性自動化搜索方法，根據Sasaki等人改進的XOR操作約束和我們改進的S盒相應的約束，進一步精煉MILP模型，減少了ESF算法產生MILP模型的變量和約束數量，使得MILP問題的求解更加高效.我們將優化的MILP模型應用到輕量級分組密碼算法ESF，在單密鑰情形下成功獲取了減輪ESF算法的差分和線性最小活躍S盒數量，并搜索到最長的不可能差分和零相關線性區分器.同時，證明了全輪ESF足夠抵抗差分攻擊，然而對于證明全輪ESF是否抵抗線性攻擊仍然是一個開放問題.

[1] Wu Wenling, Zhang Lei. LBlock: A lightweight block cipher[G] //LNCS 6715: Proc of the 9th Int Conf on Applied Cryptography and Network Security (ACNS 2011). Berlin: Springer, 2011: 327-344

[2] Bogdanov A, Knudsen L R, Leander G, et al. PRESENT: An ultra-lightweight block cipher[G] //LNCS 4727: Proc of the 9th Int Workshop on Cryptographic Hardware and Embedded Systems (CHES 2007). Berlin: Springer, 2007: 450-466

[3] Beierle C, Jean J, K?lbl S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS [G] //LNCS 9815: Advances in Cryptology (CRYPTO 2016). Berlin: Springer, 2016: 123-153

[4] Zhang Wentao, Bao Zhenzhen, Lin Dongdai, et al. RECTANGLE: A bit-slice lightweight block cipher suitable for multiple platforms [J]. Science China Information Sciences, 2015, 58(12): 1-15

[5] Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems [G] //LNCS 537: Advances in Cryptology(CRYPT0 1990). Berlin: Springer, 1990: 2-21

[6] Matsui M. Linear cryptanalysis method for DES cipher [G] //LNCS 765: Advances in Cryptology (EUROCRYPT 1993). Berlin: Springer, 1993: 386-397

[7] Biham E, Biryukov A, Shamir A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials [G] //LNCS 1592: Advances in Cryptology (EUROCRYPT 1999). Berlin: Springer, 1999: 12-23

[8] Bogdanov A, Rijmen V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers [J]. Designs Codes & Cryptography, 2014, 70(3): 369-383

[9] Matsui M. On correlation between the order of S-boxes and the strength of DES[G] //LNCS 950: Advances in Cryptology (EUROCRYPT 1994). Berlin: Springer, 1994: 366-375

[10] Mouha N, Preneel B. Towards finding optimal differential characteristics for ARX: Application to Salsa20[EB/OL]. [2017-06-11]. http://eprint.iacr.org/2013/328.

[11] Mouha N, Wang Qingju, Gu Dawu, et al. Differential and linear cryptanalysis using mixed-integer linear programming[G] //LNCS 7537: Proc of the 7th Int Conf on Information Security and Cryptology (Inscrypt 2011). Berlin: Springer, 2011: 57-76

[12] Sun Siwei, Hu Lei, Wang Peng, et al. Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers[G] //LNCS 8873: Advances in Cryptology (ASIACRYPT 2014). Berlin: Springer, 2014: 158-178

[13] Cui Tingting, Jia Keting, Fu Kai, et al. New automatic search tool for impossible differentials and zero-correlation linear approximations[EB/OL]. [2017-06-08]. https://eprint.iacr.org/2016/689

[14] Sasaki Y, Todo Y. New impossible differential search tool from design and cryptanalysis aspects[G] //LNCS 10212: Advances in Cryptology (EUROCRYPT 2017). Berlin: Springer, 2017: 185-215

[15] Liu Xuan, Zhang Wenying, Liu Xiangzhong, et al. Eight-sided fortress: A lightweight block cipher [J]. Journal of China Universities of Posts and Telecommunications, 2014, 21(1): 104-108

[16] Liu Xuan, Liu Feng, Meng Shuai. Impossible differential cryptanalysis of lightweight block cipher ESF [J]. Computer Engineering & Science, 2013, 35(9): 89-93 (in Chinese)

(劉宣, 劉楓, 孟帥. 輕量級分組密碼算法ESF的不可能差分分析[J]. 計算機工程與科學, 2013, 35(9): 89-93)

[17] Chen Yulei, Wei Hongru. Impossible differential cryptanalysis of ESF [J]. Computer Science, 2016, 43(8): 89-91 (in Chinese)

(陳玉磊，衛宏儒. ESF算法的不可能差分密碼分析[J]. 計算機科學, 2016, 43(8): 89-91)

[18] Gurobi. Gurobi optimizer reference manual[EB/OL]. [2017-06-03]. http://www.gurobi.com

[19] IBM. User-Manual CPLEX 12[EB/OL]. [2017-06-03]. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html

[20] Computational Algebra Group. School of Mathematics and Statistics, University of Sydney: Magma Computational Algebra System[EB/OL]. [2017-06-03]. http://magma.maths.usyd.edu.au

[21] Sun Siwei, Hu Lei, Song Lin, et al. Automatic security evaluation of block ciphers with S-bP structures against related-key differential attacks[G] //LNCS 8567: Proc of the 9th Int Conf on Information Security and Cryptology (Inscrypt 2013). Berlin: Springer, 2013: 39-51

[22] Stein W. Sage Tutorial v8.0[EB/OL]. [2017-05-23]. http://doc.sagemath.org/html/en/tutorial/tour.html

SecurityAnalysisofLightweightBlockCipherESF

Yin Jun1,2,3, Ma Chuyan4, Song Jian1, Zeng Guang1, and Ma Chuangui5

1(StateKeyLaboratoryofMathematicalEngineeringandAdvancedComputing(PLAInformationEngineeringUniversity),Zhengzhou450001)2(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)3(UniversityofChineseAcademyofSciences,Beijing100049)4(NationalUniversityofDefenseTechnology,Changsha410073)5(ArmyAviationInstitute,Beijing101116)

Automatic analysis is one of the important methods to evaluate the security of cryptographic algorithms. It is characterized by high efficiency and easily implement. In ASIACRYPT 2014, Sun et al. presented a MILP-based automatic search differential and linear trails method for bit-oriented block ciphers, which has attracted the attention of many cryptographers. At present, there are still a lack of research about solving the MILP model, such as how to reduce the number of variables and constraint inequalities. According to the differential propagation model of the XOR operation, in EUROCRYPT 2017, Sasaki et al. gave a set of new constraints without dummy variables. The new constraint inequalities can not only preserve the differential propagation for XOR operation, but also reduce the number of variables. At the same time, Sun et al. uses four constraints to describe the property when the input differential variable (the linear mask variable) of an S-box is non-zero and the S-box must be an active, but in this paper, we just use one constraint. Based on these refined constraints and the automatic method for finding high probability trails of block cipher, we establish the refined differential and linear MILP model under the single key assumption for the lightweight block cipher ESF. We have found that the minimum number of active S-boxes in 15-round differential trail of ESF is 19 and the number is 15 in 16-round linear trail. Moreover, we find so far the longest impossible differential and zero-correlation linear approximation distinguishers of ESF.

differential cryptanalysis; linear cryptanalysis; impossible differential; zero-correlation linear approximation; ESF; MILP

TP309.7

YinJun, born in 1993. Master candidate. His main research interests include automatic analysis of cryptographic algorithms.

MaChuyan, born in 1994. Master candidate. His main research interests include automatic analysis of block ciphers.

SongJian, born in 1993. Master candidate. His main research interests include security analysis of cryptographic protocols.

ZengGuang, born in 1980. PhD, associate professor. His main research interests include security analysis of Hash function.

MaChuangui, born in 1962. Professor and PhD supervisor. His main research interests include network and information security.