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

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

2017-06-11；

2017-08-03

國家自然科學(xué)基金項(xiàng)目(61502532,61379150,61772519,61309016,61502529)；數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室開放基金課題(2016A02)；河南省重點(diǎn)科技攻關(guān)計(jì)劃項(xiàng)目(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).

輕量級(jí)分組密碼算法ESF的安全性分析

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

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

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

差分密碼分析；線性密碼分析；不可能差分；零相關(guān)線性逼近；ESF；MILP

當(dāng)前，對(duì)于輕量級(jí)分組密碼的設(shè)計(jì)與分析越來越受到人們關(guān)注，密碼學(xué)者提出了許多輕量級(jí)分組密碼算法，比較知名的算法有LBlock[1]，PRESENT[2]，SKINNY[3]，RECTANGLE[4]等.

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

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

ESF[15]是劉宣等人基于吳文玲研究員的 LBlock 算法改進(jìn)的輕量級(jí)分組密碼算法，同時(shí)在置換層還采用了PRESENT算法的P置換形式，分組長度64 b,密鑰長度80 b.針對(duì)ESF的密碼分析,劉宣等人給出了ESF算法8輪不可能差分區(qū)分器來攻擊11輪 ESF算法[16]，攻擊的數(shù)據(jù)和時(shí)間復(fù)雜度分別是259和275.5.隨后，陳玉磊等人利用文獻(xiàn)[16]中劉宣等人給出的8輪不可能差分區(qū)分器，根據(jù)輪密鑰之間的關(guān)系，通過改變?cè)休啍?shù)擴(kuò)展和密鑰猜測的順序，改進(jìn)了11輪ESF的不可能差分攻擊結(jié)果，攻擊的數(shù)據(jù)和時(shí)間復(fù)雜度[17]分別是253和232.

本文的主要貢獻(xiàn)有4個(gè)方面：

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

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

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

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

Table 1 The Attack Results for ESF

1 準(zhǔn)備知識(shí)

本節(jié)首先給出常用的符號(hào)和術(shù)語說明，然后簡要描述輕量級(jí)分組密碼算法ESF.

1.1常用的符號(hào)和術(shù)語

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

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

F:輪函數(shù);

Ki:第i輪32 b子密鑰;

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

<<<7:循環(huán)左移7 b.

1.2ESF算法

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

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

Fig. 2 The round function of ESF圖2 ESF輪函數(shù)

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置換函數(shù)將32 b的(b31‖b30‖…‖b1‖b0)映射成(c31‖c30‖…‖c1‖c0)，具體如下：

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

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

在本文中，我們只考慮單密鑰情形下的密碼分析.因此對(duì)于密鑰擴(kuò)展算法，具體細(xì)節(jié)可參考文獻(xiàn)[15].

2 基于MILP問題的自動(dòng)化分析技術(shù)

在本節(jié)中，我們主要介紹MILP，后面詳細(xì)介紹基于MILP模型自動(dòng)化搜索差分特征、線性特征、不可能差分和零相關(guān)線性逼近，具體應(yīng)用于ESF算法上產(chǎn)生約束不等式的過程.同時(shí)給出我們優(yōu)化的MILP模型.

2.1混合整數(shù)線性規(guī)劃(MILP)

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

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

2.2建立改進(jìn)的自動(dòng)化搜索差分特征MILP模型

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

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

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

2.2.1 ESF算法XOR操作差分約束

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

(1)

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

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

(2)

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

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

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

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

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

(3)

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

其次，當(dāng)At=1時(shí)，Δx0,Δx1,Δx2,Δx3必定有一個(gè)非零，用不等式約束為

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

(4)

最后,對(duì)于雙射的S盒,因?yàn)榉橇愕妮斎氩罘直厝粚?dǎo)致非零的輸出差分,反之亦然,用不等式約束為

(5)

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

Table 3 The Number of Differential Inequalities Obtained by Different Methods

2.3建立自動(dòng)化搜索線性特征MILP模型

為了自動(dòng)化搜索ESF算法的線性特征，需要考慮ESF算法基本操作的線性掩碼傳播模式.因?yàn)槲坏男D(zhuǎn)是一個(gè)簡單的置換，可以根據(jù)相應(yīng)的位給出等式約束，下面重點(diǎn)給出異或、分支和S盒操作的線性掩碼傳播約束.

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

根據(jù)文獻(xiàn)[12,21]，下面具體給出對(duì)ESF算法操作的線性掩碼變量約束.

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

假設(shè)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)是輸出掩碼，約束如下：對(duì)0≤i≤31，ai⊕bi⊕ci=0，根據(jù)式(2)，約束為

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

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

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

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

(6)

2) 當(dāng)At=1時(shí)，y0,y1,y2,y3必定有一個(gè)非零，用不等式約束：

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

(7)

3) 對(duì)于雙射的S盒，因?yàn)榉橇愕妮斎刖€性掩碼必然導(dǎo)致非零的輸出線性掩碼，反之亦然，用不等式約束：

(8)

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

Table 4 The Number of Inequalities Obtained by Different Methods

對(duì)于異或操作約束、S盒操作約束、邏輯狀態(tài)模型、凸閉包H表示、貪心算法，詳細(xì)內(nèi)容請(qǐng)參閱文獻(xiàn)[12,21].

2.4建立自動(dòng)化搜索不可能差分MILP模型

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

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

2.5建立自動(dòng)化搜索零相關(guān)線性逼近MILP模型

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

對(duì)于建立不可能差分和零相關(guān)線性逼近自動(dòng)化分析MILP模型，詳細(xì)內(nèi)容請(qǐng)參閱文獻(xiàn)[13-14].

3 輕量級(jí)分組密碼ESF的安全性分析

根據(jù)第2節(jié)所敘，結(jié)合ESF算法的加密過程，用Python編程分別產(chǎn)生自動(dòng)化搜索差分特征、線性特征、不可能差分和零相關(guān)線性逼近“l(fā)p”文件格式的MILP模型，并且調(diào)用Gurobi7.0.2來求解相應(yīng)的MILP模型.求解MILP模型的實(shí)驗(yàn)環(huán)境在一臺(tái)服務(wù)器上進(jìn)行，該服務(wù)器配置如表5所示：

Table 5 Experimental Environment for Solving MILP Model

3.1ESF算法差分分析結(jié)果

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

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

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

3.2ESF算法線性分析結(jié)果

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

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

Table 7 The Results for Linear Analysis on ESF

3.3ESF算法不可能差分分析結(jié)果

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

3.4ESF算法零相關(guān)線性逼近分析結(jié)果

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

4 結(jié)束語

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

[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)

(劉宣, 劉楓, 孟帥. 輕量級(jí)分組密碼算法ESF的不可能差分分析[J]. 計(jì)算機(jī)工程與科學(xué), 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)

(陳玉磊，衛(wèi)宏儒. ESF算法的不可能差分密碼分析[J]. 計(jì)算機(jī)科學(xué), 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.