趙 穎，葉 濤，韋永壯,3

(1.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004;2.桂林電子科技大學(xué) 廣西云計(jì)算與大數(shù)據(jù)協(xié)同創(chuàng)新中心，廣西 桂林 541004;3.桂林電子科技大學(xué) 廣西無(wú)線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室, 廣西 桂林 541004)(*通信作者電子郵箱walker_wyz@guet.edu.cn)

幾類高強(qiáng)度密碼S盒的安全性新分析

趙 穎1，葉 濤2，韋永壯1,3*

(1.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004;2.桂林電子科技大學(xué) 廣西云計(jì)算與大數(shù)據(jù)協(xié)同創(chuàng)新中心，廣西 桂林 541004;3.桂林電子科技大學(xué) 廣西無(wú)線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室, 廣西 桂林 541004)(*通信作者電子郵箱walker_wyz@guet.edu.cn)

針對(duì)幾類高強(qiáng)度密碼S盒是否存在新的安全性漏洞問(wèn)題，提出了一種求解S盒非線性不變函數(shù)的算法。該算法主要基于密碼S盒輸入和輸出的代數(shù)關(guān)系來(lái)設(shè)計(jì)。利用該算法對(duì)這幾類密碼S盒進(jìn)行測(cè)試，發(fā)現(xiàn)其中幾類存在相同的非線性不變函數(shù);此外，如果將這些S盒使用于分組密碼Midori-64的非線性部件上，將會(huì)得到一個(gè)新的變體算法。利用非線性不變攻擊對(duì)其進(jìn)行安全性分析，結(jié)果表明：該Midori-64變體算法存在嚴(yán)重的安全漏洞，即在非線性不變攻擊下，存在264個(gè)弱密鑰，并且攻擊所需的數(shù)據(jù)、時(shí)間及存儲(chǔ)復(fù)雜度可忽略不計(jì)，因此這幾類高強(qiáng)度密碼S盒存在新的安全缺陷。

S盒；非線性不變函數(shù)；Midori-64算法；非線性不變攻擊；弱密鑰

0 引言

對(duì)稱密碼算法由于具有加解密速度快、便于各種軟件和硬件平臺(tái)實(shí)現(xiàn)等優(yōu)點(diǎn)，在網(wǎng)絡(luò)與信息安全領(lǐng)域發(fā)揮著越來(lái)越重要的作用。對(duì)稱密碼的分析與設(shè)計(jì)是一對(duì)相互對(duì)立又相互統(tǒng)一的矛盾體，兩者的互動(dòng)推動(dòng)著對(duì)稱密碼的發(fā)展[1]。密碼S盒是對(duì)稱密碼算法的核心部件，其安全強(qiáng)度與算法的安全性息息相關(guān)[2]，比如經(jīng)典的差分密碼分析[3]、線性密碼分析[4]、相關(guān)密碼分析[5]、代數(shù)密碼分析[6]等，都是基于密碼S盒的統(tǒng)計(jì)特性來(lái)實(shí)現(xiàn)的。因此，設(shè)計(jì)及分析高強(qiáng)度的密碼S盒是目前業(yè)界重要的研究熱點(diǎn)。

在2011年美國(guó)國(guó)際密碼年會(huì)上(Annual Cryptology Conference ,CRYPTO 2011)，Leander等[7]利用S盒混淆能力差的代數(shù)性質(zhì)，提出一種新的分組密碼攻擊方法——不變子空間攻擊，并對(duì)SP結(jié)構(gòu)的分組密碼算法PRINT進(jìn)行不變子空間攻擊，說(shuō)明其存在嚴(yán)重的安全漏洞。進(jìn)一步，在2015年的歐洲密碼年會(huì)上(Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2015)，Leander等[8]提出了不變子空間攻擊的一般方法，并對(duì)三個(gè)密碼算法Robin、iSCREAM和Zorro進(jìn)行分析，發(fā)現(xiàn)iSCREAM存在一定的安全漏洞。在2016年亞洲密碼年會(huì)上(International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2016)，Todo等[9]利用密碼S盒的輸入和輸出代數(shù)關(guān)系，提出了非線性不變攻擊方法，并證明了不變子空間攻擊是非線性不變攻擊的一種特例。此外，針對(duì)輕量級(jí)分組密碼算法Midori-64，他們還給出了一種非線性不變攻擊方法。

在2017年國(guó)際快速軟件加密會(huì)議上(International Conference on Fast Software Encryption, FSE 2017)，Guo等[10]提出了幾類高強(qiáng)度的密碼S盒，并說(shuō)明這些新S盒足以抵抗不變子空間攻擊。注意到，Guo等提出的幾類新密碼S盒是否足夠安全？特別是當(dāng)這些S盒部署在具體算法(比如Midori-64算法)的非線性組件里時(shí)，算法整體的安全性如何評(píng)價(jià)呢？這兩個(gè)問(wèn)題亟待解決。

本文利用密碼S盒輸入和輸出的代數(shù)關(guān)系，設(shè)計(jì)了一個(gè)算法來(lái)尋找S盒的非線性不變函數(shù)?；谠撍惴ǎ槍?duì)Guo等的幾類S盒進(jìn)行測(cè)試，結(jié)果表明：其中三類S盒存在相同的二次非線性不變函數(shù)。最后討論了這三類S盒替換Midori-64算法的S盒后得到的Midori-64變體算法的安全性。

1 基礎(chǔ)知識(shí)

1.1 五類高強(qiáng)度S盒

在FSE 2017上，Guo等[10]首先提出了兩個(gè)概念：密碼算法的密鑰編排分類和S盒的設(shè)計(jì)目標(biāo)。

密碼算法的密鑰編排分為以下兩類：

1)密鑰編排函數(shù)1(Key Schedule Function 1, KSF1)：每一輪都使用單密鑰，如Midori-128、LED-64[11]；

2)密鑰編排函數(shù)2(Key Schedule Function 2, KSF2)：兩個(gè)密鑰交替使用，如Midori-64、LED-128[11]。

S盒的設(shè)計(jì)目標(biāo)按照其控制的弱密鑰范圍分為以下兩類：

1)目標(biāo)1(Goal 1)：確保弱密鑰空間中含有的弱密鑰的數(shù)目為c*2b，其中c為一個(gè)較小的常數(shù)，b為密鑰含有的單元的個(gè)數(shù)；

2)目標(biāo)2(Goal 2)：確保僅含有一個(gè)弱密鑰。

Guo等[10]給出了五類新密碼S盒的真值表，參見圖1。其中x為S盒輸入，y為S盒輸出。其中S1，S2，S3是在KSF1和Goal 1的條件下，利用S盒的差分分布表，經(jīng)過(guò)計(jì)算機(jī)搜索得到的；S4是在KSF2和Goal 1的條件下，利用S盒的差分分布表，經(jīng)過(guò)計(jì)算機(jī)搜索得到的；S5是在KSF1和Goal 2的條件下，利用S盒的差分分布表，經(jīng)過(guò)計(jì)算機(jī)搜索得到的。S1，S2，S3，S4，S5的最大差分可能性都為2-2，線性逼近的最大偏離值為2-2。

圖1 五個(gè)新S盒的真值表

1.2 Midori-64算法

在ASIACRYPT 2015上，Banik等[12]提出Midori-64輕量級(jí)分組加密算法。Midori-64由于低功耗、低延時(shí)、輪數(shù)少等諸多優(yōu)點(diǎn)得到了廣泛關(guān)注。Midori-64的整體加密流程如圖2所示。其中：P為輸入的明文，C為輸出的密文，WK為一個(gè)64比特的白化密鑰，Ki(i=0,1,…,14)為第i輪加密時(shí)使用的子密鑰，αi為64比特的輪常數(shù)，RKi(i=0,1,…,14)為異或輪常數(shù)αi之后的輪密鑰。

圖2 Midori-64加密算法[12]

Midori-64密碼算法每次可以處理64比特的數(shù)據(jù)，這64比特的數(shù)據(jù)被放在一個(gè)4×4的矩陣S中。

Midori-64算法的輪函數(shù)包括以下4個(gè)組件：字節(jié)替代、字節(jié)置換、列混淆、輪密鑰加。下面分別介紹這4個(gè)組件。

1)字節(jié)替代(SubCell)。

使用一個(gè)非線性的4位S盒對(duì)每個(gè)單元的狀態(tài)進(jìn)行操作，Midori-64算法的S盒如圖3所示。x為S盒輸入，y為S盒輸出。

圖3 Midori-64算法的S盒

Fig. 3 S-box of Midori-64 algorithm

2)字節(jié)置換(ShuffleCell)。

字節(jié)置換主要是對(duì)矩陣S中的每一個(gè)位置按照如下順序進(jìn)行替換。

3)列混淆(MixColumn)。

Midori-64算法的列混淆矩陣為一個(gè)二進(jìn)制的正交矩陣，列混淆矩陣如下：

4)輪密鑰加(KeyAddition)。

輪密鑰加將第i輪的密鑰RKi與第i輪的狀態(tài)異或。

Midori-64算法的密鑰編排非常簡(jiǎn)單。128比特的密鑰被表示成為兩個(gè)64比特key0和key1，K=key0‖key1。WK=key0⊕key1,RKi=key(i mod 2)⊕αi，其中，αi每一個(gè)位置的最低位只有0或1兩種情況，其他的位置為0，αi的部分編排如表1所示。

表1 Midori-64的部分輪常數(shù)[12]

2 不變子空間攻擊和非線性不變攻擊

2.1 不變子空間攻擊和非線性不變攻擊的基本思想

不變子空間和非線性不變攻擊是兩種弱密鑰條件下的攻擊方法。當(dāng)且僅當(dāng)輸入每一輪加密輪函數(shù)的密鑰都是弱密鑰時(shí)，才能構(gòu)造出概率為1的全輪區(qū)分器，進(jìn)而利用這兩種方法對(duì)算法進(jìn)行攻擊。注意到，近幾年設(shè)計(jì)的若干輕量級(jí)密碼算法為了提高加密的速度，減少消耗的內(nèi)存，密鑰編排算法簡(jiǎn)單。甚至直接將主密鑰用于加密，這可能為攻擊者所利用，從而進(jìn)行非線性不變攻擊和不變子空間攻擊。

F(U+c)=U+d

(1)

則對(duì)應(yīng)的弱密鑰為k=u+c+d，其中u∈U，且有式(2)存在：

Fk(U+d)=F((U+d)+(u+c+d))=

F(U+c)=U+d

(2)

注意到，不變子空間攻擊的本質(zhì)思想是利用輪函數(shù)將空間U+c映射到U+d。如果輸入的所有輪密鑰為弱密鑰，則上述性質(zhì)(2)對(duì)于任意輪都是滿足的。此外，U的維數(shù)決定了弱密鑰空間的大小。假設(shè)U的維數(shù)為b，密鑰一共含有m個(gè)單元，則對(duì)應(yīng)的弱密鑰空間為mb。

非線性不變攻擊是不變子空間攻擊的推廣形式[9]，不變子空間攻擊為非線性不變攻擊的特例，在不變子空間中使用的非線性不變函數(shù)為指示函數(shù)δA(x)。

(3)

尋找輪函數(shù)的非線性不變函數(shù)g是非線性不變攻擊的關(guān)鍵。非線性不變函數(shù)必須滿足式(4)對(duì)于所有的輸入xi-1都成立，其中，xi-1為輪函數(shù)的輸入，xi為輪函數(shù)的輸出，Constant為常數(shù)，此時(shí)輸入的密鑰定義為弱密鑰。

g(xi-1)⊕g(xi)=Constant⊕g(keyi-1)

(4)

進(jìn)一步，如果存在一個(gè)非線性不變函數(shù)可以穿透輪函數(shù)，并且每一輪輸入的密鑰都為弱密鑰，那么此非線性不變函數(shù)同樣也可以穿透這個(gè)輪函數(shù)相對(duì)應(yīng)的密碼算法，最終得到輸入的明文和輸出的密文之間滿足g(P)+g(C)=Constant這樣的關(guān)系，利用這種關(guān)系可以對(duì)SPN結(jié)構(gòu)的分組密碼算法進(jìn)行弱密鑰條件下的區(qū)分攻擊。弱密鑰空間為2m×(n-f)，其中n為S盒的位數(shù)，f代表非線性不變函數(shù)非線性部分所含的變量個(gè)數(shù)。

2.2 S盒非線性不變函數(shù)的求解方法

假設(shè)S盒的非線性不變函數(shù)存在，將S盒的非線性不變函數(shù)用代數(shù)正規(guī)型進(jìn)行表示：

(5)

方法一 如果函數(shù)g為S盒的非線性不變函數(shù)，則對(duì)于所有的n比特的輸入x和相應(yīng)的n比特S盒的輸出S(x)都滿足式(6)：

g(x)+g(S(x))=Constant

(6)

轉(zhuǎn)化為代數(shù)正規(guī)型的形式即為式(7)：

(7)

具體求解步驟如下：

步驟1 對(duì)于式(7)，固定λ1,λ2,…,λu的值(u的最大漢明重量取2)，固定常數(shù)Constant的值為0。

步驟2 遍歷所有的x的值，如果對(duì)于所有的x和S(x)都有式(7)成立，則對(duì)應(yīng)的Constant為0，保存此時(shí)的系數(shù)λ1，λ2,…,λu。

如果都有式(7)不成立，則對(duì)應(yīng)的Constant為1，將此時(shí)的系數(shù)λ1,λ2,…,λu保存。

步驟3 改變?chǔ)?,λ2,…,λu的值，進(jìn)行步驟2操作，直到遍歷所有的λ1,λ2,…,λu。針對(duì)Constant取0和取1，分別得到若干組λ1,λ2,…,λu。

方法二 將式(7)進(jìn)行變形得到如下的等式關(guān)系(8)：

(8)

對(duì)于式(8)，固定Constant為0，遍歷所有的輸入x，計(jì)算xu⊕S(x)u(u的最大漢明重量取2)，可以得到一個(gè)關(guān)于系數(shù)λ1，λ2，…，λu的方程組。如果方程組有解，則得到的解即為λ1,λ2,…,λu的值。固定Constant為1，利用上述Constant取0的同樣方法求解λ1,λ2,…,λu。

3 五類高強(qiáng)度S盒的安全性新分析

本章設(shè)計(jì)了一個(gè)求解S盒非線性不變函數(shù)的算法，利用它對(duì)Guo等的幾類S盒進(jìn)行測(cè)試。進(jìn)一步利用其中三類S盒存在非線性不變函數(shù)的缺陷，構(gòu)造弱密鑰條件下的區(qū)分器，進(jìn)而對(duì)Midori-64變體進(jìn)行非線性不變攻擊。

3.1 S盒的非線性不變函數(shù)求解算法及其應(yīng)用

本節(jié)設(shè)計(jì)了一個(gè)算法來(lái)求解4位S盒的非線性不變函數(shù)。具體步驟如下：

步驟1 針對(duì)S盒遍歷所有的輸入x，得到對(duì)應(yīng)的輸出為y，并將對(duì)應(yīng)的x、y按行分別存儲(chǔ)在矩陣X、Y中。

步驟2 建立兩個(gè)16×10的矩陣X1、Y1，其中，X1[0][0]～X1[0][3]中存儲(chǔ)x[0][0]～x[0][3]的值，X1[0][4]～X1[0][9]中存儲(chǔ)x[0][i]*x[0][j] 的值，i，j為 [1，2，3，4]中兩個(gè)不重復(fù)的數(shù)。Y1[0][0]～Y1[0][3]中存儲(chǔ)的為y[0][0]～y[0][3]的值，Y1[0][4]～Y1[0][9]中存儲(chǔ)y[0][i]*y[0][j]的值，i，j為 [1，2，3，4]中兩個(gè)不重復(fù)的數(shù)。同理，按照以上的方法對(duì)X1、Y1、X、Y第1～15行執(zhí)行同樣的操作。最終輸出矩陣X1，Y1。

步驟3X1，Y1中每一個(gè)位置的值按位異或，得到一個(gè)新的矩陣Z。

步驟4 定義一個(gè)10維的向量A，向量中的每一個(gè)位置的值只有0或1兩種情況，遍歷A中的所有的值，對(duì)于每一種情況，用Z*A，最終得到一個(gè)列向量。如果列向量中的值都相等，則保存A中的對(duì)應(yīng)的值到A1中。

步驟5A1中的每一行代表一個(gè)非線性不變函數(shù)的表達(dá)式。第1～3列代表的系數(shù)為λ1～λ3，第4～9列代表的系數(shù)為λ12,λ13,λ14,λ23,λ24,λ34。每一行數(shù)值為1時(shí)表示系數(shù)存在，數(shù)值為0時(shí)表示系數(shù)不存在。至此恢復(fù)二次非線性不變函數(shù)的一次和二次項(xiàng)系數(shù)，也就得到了此S盒的二次非線性不變函數(shù)。

利用此算法對(duì)Guo等提出的幾類S盒進(jìn)行測(cè)試，結(jié)果表明：S1、S2、S3存在相同的二次非線性不變函數(shù)，參見式(9)。S4、S5不存在二次非線性不變函數(shù)。

g(x)=x[2]⊕x[3]⊕x[4]⊕x[2]·x[3]

(9)

3.2 Midori-64變體的非線性不變攻擊

分別用含有非線性不變函數(shù)的三類S盒即S1、S2、S3部署在Midori-64的S盒組件上，結(jié)果表明：Midori-64變體算法存在嚴(yán)重的安全漏洞，即弱密鑰空間為264。

具體分析過(guò)程如下：

對(duì)于S盒，利用尋找到的非線性不變函數(shù)g，可以得到式(10)對(duì)于所有的S盒都成立：

g(xi)⊕g(S(xi))=0

(10)

其中:xi為一個(gè)第i個(gè)S盒的輸入，S(xi)為第i個(gè)S盒輸入為xi時(shí)對(duì)應(yīng)的輸出。又知Midori-64的S層一共采用了16個(gè)相同的S盒，可以得到關(guān)于S層的非線性不變函數(shù)，參見式(11):

(11)

經(jīng)過(guò)S層后，算法將通過(guò)字節(jié)置換，由于字節(jié)置換作用于每一個(gè)位置。所以，式(11)經(jīng)過(guò)字節(jié)置換后仍舊成立。又知Midori-64的列混淆矩陣為正交矩陣，yi為第i個(gè)位置經(jīng)過(guò)L層后的輸出。利用Todo等[9]的結(jié)論：如果針對(duì)S層的非線性不變函數(shù)的最高階數(shù)為二次，并且列混淆矩陣是正交矩陣，則S層的非線性不變函數(shù)對(duì)于L層同樣也是成立的?？傻檬?12)是恒成立的：

(12)

最后進(jìn)行輪密鑰加，輪密鑰RKi的編排為RKi=Ki mod 2⊕αi，αi為輪常數(shù)。Midori-64的輪常數(shù)每一個(gè)位置的十六進(jìn)制形式僅包含0或1，轉(zhuǎn)化為4位的二進(jìn)制后，在第2、3位都為零。為了保證密鑰RKi對(duì)于非線性不變函數(shù)為線性的運(yùn)算，需要K0，K1每個(gè)單元的第2、3位固定為0，其他的位置可以為任意的值。此時(shí)的密鑰為弱密鑰，弱密鑰空間為264。如果輸入的密鑰滿足以上條件，則輪函數(shù)經(jīng)過(guò)輪密鑰加后存在式(13)成立：

(13)

Midori-64一共加密了16輪，如果每一輪輸入的密鑰都為弱密鑰，則根據(jù)式(13)可以得到輸入的明文和密文之間的關(guān)系如式(14)、(15)：

(14)

(15)

當(dāng)輸入的密鑰不是弱密鑰時(shí)，式(15)成立的概率為0.5。當(dāng)輸入的密鑰為弱密鑰時(shí)，式(15)以概率1成立。所以，判斷輸入的密鑰是否為弱密鑰時(shí)，需要輸入明文和密文對(duì)進(jìn)行驗(yàn)證，輸入N對(duì)明密文，如果均滿足式(15)，則使用的密鑰不是弱密鑰的概率為2-N+1；如果至少存在一對(duì)明密文不滿足，則使用的密鑰不是弱密鑰。當(dāng)明密文對(duì)的數(shù)目取40時(shí)，可知弱密鑰條件下，可以以概率1-2-40+1=1構(gòu)造出區(qū)分器。隨后利用此區(qū)分器對(duì)密碼算法進(jìn)行區(qū)分攻擊。在Midori-64的密碼分組鏈接(Cipher Block Chaining, CBC)工作模式下，輸入相同的明文和不同的初始向量IV，得到不同的密文。根據(jù)非線性不變函數(shù)式(6)得到式(16)：

(16)

此公式包含32個(gè)未知數(shù)，需要輸入33個(gè)不同的IV得到32個(gè)不同的表達(dá)式。利用高斯消元方法求解此32個(gè)表達(dá)式組成的方程所需的時(shí)間復(fù)雜度為323次簡(jiǎn)單運(yùn)算。存儲(chǔ)復(fù)雜度為N個(gè)分組長(zhǎng)度，數(shù)據(jù)復(fù)雜度為N。

綜上，利用Guo等提出的S盒替換Midori-64的S盒后， Midori-64變體算法的弱密鑰為264個(gè)。注意到，Guo等設(shè)計(jì)的S1、S2、S3是應(yīng)用在KSF1模式下，達(dá)到的目標(biāo)為：存在的弱密鑰為c*2b個(gè)。Midori-64的密鑰編排模式遵循KSF2，此時(shí)Midori-64變體的弱密鑰空間遠(yuǎn)遠(yuǎn)大于c*2b。因此 Guo等設(shè)計(jì)的S1，S2，S3三類S盒沒有達(dá)到最初的設(shè)計(jì)目標(biāo)，無(wú)法抵抗非線性不變攻擊。

4 結(jié)語(yǔ)

本文主要對(duì)Guo等設(shè)計(jì)的幾類S盒的安全性進(jìn)行了新的評(píng)估。給出了求解S盒非線性不變函數(shù)的新算法，利用新算法測(cè)試Guo等的五類S盒。結(jié)果表明：其中S1、S2、S3存在相同的二次非線性不變函數(shù)。此外，用這三類S盒直接替換Midori-64的S盒來(lái)得到Midori-64變體算法，結(jié)果表明：Midori-64變體算法存在嚴(yán)重的安全漏洞。因此，這三類S盒是不安全的。

References)

[1] LAI X. On the design and security of block ciphers [EB/OL]. [2016- 12- 16]. https://www.researchgate.net/publication/242506184_On_the_design_and_security_of_block_ciphers.

[2] 草冠杰,馬建設(shè),程雪岷.基于組合式爬山算法提高S盒非線性度的方法[J].計(jì)算機(jī)應(yīng)用, 2015,35(8):2195-2198.(CAO G J, MA J S, CHENG X M. Method for increasing S-box nonlinearity based on combination of hill climbing [J]. Journal of Computer Applications, 2015, 35(8): 2195-2198.)[3] BIHAM E, SHAMIR A. Differential cryptanalysis of the full 16-round DES [C]// Annual International Cryptology Conference, LNCS 740. Berlin: Springer, 1992: 487-496.

[4] MATSUI M. Linear cryptanalysis method for DES cipher [C]// Workshop on the Theory and Application of of Cryptographic Techniques, LNCS 765. Berlin: Springer, 1993: 386-397.

[5] BIHAM E. New types of cryptanalytic attacks using related keys [J]. Journal of Cryptology, 1994, 7(4): 229-246.

[6] COURTOIS N T, PIEPRZYK J. Cryptanalysis of block ciphers with overdefined systems of equations [C]// International Conference on the Theory and Application of Cryptology and Information Security, LNCS 2501. Berlin: Springer, 2002: 267-287.

[7] LEANDER G, ABDELRAHEEM M A, ALKHZAIMI H, et al. A cryptanalysis of PRINTcipher: the invariant subspace attack [C]// Annual Cryptology Conference, LNCS 6841. Berlin: Springer, 2011: 206-221.

[8] LEANDER G, MINAUD B, R?NJOM S. A generic approach to invariant subspace attacks: cryptanalysis of Robin, iSCREAM and Zorro [C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2015: 254-283.

[9] TODO Y, LEANDER G, SASAKI Y. Nonlinear invariant attack: practical attack on full SCREAM, iSCREAM, and Midori64 [EB/OL]. [2016- 11- 06]. http://eprint.iacr.org/2016/732.pdf.

[10] GUO J, JEAN J, NIKOLIC I, et al. Invariant subspace attack against Midori64 and the resistance criteria for S-box designs [J]. IACR Transactions on Symmetric Cryptology, 2016, 2016(1): 33-56.

[11] GUO J, PEYRIN T, POSCHMANN A, et al. The LED block cipher [C] // International Workshop on Cryptographic Hardware and Embedded Systems, LNCS 6917. Berlin: Springer, 2011: 326-341.

[12] BANIK S, BOGDANOV A, ISOBE T, et al. Midori: a block cipher for low energy [C]// International Conference on the Theory and Application of Cryptology and Information Security, LNCS 9453. Berlin: Springer, 2014: 411-436.

Newsecurityanalysisofseveralkindsofhigh-levelcryptographicalS-boxes

ZHAO Ying1, YE Tao2, WEI Yongzhuang1,3*

(1.GuangxiKeyLaboratoryofCryptographyandInformationSecurity,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China;2.GuangxiCooperativeInnovationCenterofcloudcomputingandBigData,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China;3.GuangxiKeyLaboratoryofWirelessWidebandCommunicationandSignalProcessing,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

Focusing on the problem whether there are new security flaws of several kinds of high-level cryptographic S-boxes, an algorithm for solving the nonlinear invariant function of S-boxes was proposed, which is mainly based on the algebraic relationship between the input and output of the cryptographic S-boxes. Using the proposed algorithm, several kinds of S-boxes were tested and it was found that several of them had the same nonlinear invariant function. In addition, if these S-boxes were used to non-linear parts of the block cipher Midori-64, a new variant algorithm would be obtained. The security analysis was carried out by non-linear invariant attack. The analytical results show that the Midori-64 variant is faced with serious secure vulnerability. In other words, there exist 264weak keys when nonlinear invariant attack is applied to the Midori-64 variant, meanwhile data, time and storage complexity can be neglected, consequently some high-level cryptographic S-boxes have security flaws.

S-box; nonlinear invariant function; Midori-64 algorithm; nonlinear invariant attack; weak key

2017- 03- 17;

2017- 04- 29。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572148)；廣西自然科學(xué)基金(杰出青年基金)資助項(xiàng)目(2015GXNSFGA139007)；廣西高等學(xué)校優(yōu)秀中青年骨干教師培養(yǎng)工程項(xiàng)目(第2期)。

趙穎(1991—)，女，陜西咸陽(yáng)人，碩士研究生，主要研究方向：分組密碼的分析與設(shè)計(jì)； 葉濤(1991—)，男，黑龍江伊春人，碩士研究生，主要研究方向：分組密碼的設(shè)計(jì)與分析； 韋永壯(1976—)，男，廣西田陽(yáng)人，教授，博士，主要研究方向：密碼學(xué)。

1001- 9081(2017)09- 2572- 04

10.11772/j.issn.1001- 9081.2017.09.2572

TP309.7

A

This work is partially supported by the National Natural Science Foundation of China (61572148), the Guangxi Natural Science Fund (Fund for Distinguished Young Scholars) (2015GXNSFGA139007), the Project of Outstanding Young Teachers Training in Higher Education Institutions of Guangxi (the second period).

ZHAOYing, born in 1991, M. S. candidate. Her research interests include analysis and design of block cipher .

YETao, born in 1991, M. S. candidate. His research interests include analysis and design of block cipher.

WEIYongzhuang, born in 1976, Ph. D. ,professor. His research interest include cryptography.