幾類高強度密碼S盒的安全性新分析

趙 穎，葉 濤，韋永壯,3

(1.桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004;2.桂林電子科技大學 廣西云計算與大數據協同創新中心，廣西 桂林 541004;3.桂林電子科技大學 廣西無線寬帶通信與信號處理重點實驗室, 廣西 桂林 541004)(*通信作者電子郵箱walker_wyz@guet.edu.cn)

幾類高強度密碼S盒的安全性新分析

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

(1.桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004;2.桂林電子科技大學 廣西云計算與大數據協同創新中心，廣西 桂林 541004;3.桂林電子科技大學 廣西無線寬帶通信與信號處理重點實驗室, 廣西 桂林 541004)(*通信作者電子郵箱walker_wyz@guet.edu.cn)

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

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

0 引言

對稱密碼算法由于具有加解密速度快、便于各種軟件和硬件平臺實現等優點，在網絡與信息安全領域發揮著越來越重要的作用。對稱密碼的分析與設計是一對相互對立又相互統一的矛盾體，兩者的互動推動著對稱密碼的發展[1]。密碼S盒是對稱密碼算法的核心部件，其安全強度與算法的安全性息息相關[2]，比如經典的差分密碼分析[3]、線性密碼分析[4]、相關密碼分析[5]、代數密碼分析[6]等，都是基于密碼S盒的統計特性來實現的。因此，設計及分析高強度的密碼S盒是目前業界重要的研究熱點。

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

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

本文利用密碼S盒輸入和輸出的代數關系，設計了一個算法來尋找S盒的非線性不變函數。基于該算法，針對Guo等的幾類S盒進行測試，結果表明：其中三類S盒存在相同的二次非線性不變函數。最后討論了這三類S盒替換Midori-64算法的S盒后得到的Midori-64變體算法的安全性。

1 基礎知識

1.1 五類高強度S盒

在FSE 2017上，Guo等[10]首先提出了兩個概念：密碼算法的密鑰編排分類和S盒的設計目標。

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

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

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

S盒的設計目標按照其控制的弱密鑰范圍分為以下兩類：

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

2)目標2(Goal 2)：確保僅含有一個弱密鑰。

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

圖1 五個新S盒的真值表

1.2 Midori-64算法

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

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

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

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

1)字節替代(SubCell)。

使用一個非線性的4位S盒對每個單元的狀態進行操作，Midori-64算法的S盒如圖3所示。x為S盒輸入，y為S盒輸出。

圖3 Midori-64算法的S盒

Fig. 3 S-box of Midori-64 algorithm

2)字節置換(ShuffleCell)。

字節置換主要是對矩陣S中的每一個位置按照如下順序進行替換。

3)列混淆(MixColumn)。

Midori-64算法的列混淆矩陣為一個二進制的正交矩陣，列混淆矩陣如下：

4)輪密鑰加(KeyAddition)。

輪密鑰加將第i輪的密鑰RKi與第i輪的狀態異或。

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

表1 Midori-64的部分輪常數[12]

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

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

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

F(U+c)=U+d

(1)

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

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

F(U+c)=U+d

(2)

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

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

(3)

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

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

(4)

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

2.2 S盒非線性不變函數的求解方法

假設S盒的非線性不變函數存在，將S盒的非線性不變函數用代數正規型進行表示：

(5)

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

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

(6)

轉化為代數正規型的形式即為式(7)：

(7)

具體求解步驟如下：

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

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

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

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

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

(8)

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

3 五類高強度S盒的安全性新分析

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

3.1 S盒的非線性不變函數求解算法及其應用

本節設計了一個算法來求解4位S盒的非線性不變函數。具體步驟如下：

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

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

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

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

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

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

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

(9)

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

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

具體分析過程如下：

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

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

(15)

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

(16)

此公式包含32個未知數，需要輸入33個不同的IV得到32個不同的表達式。利用高斯消元方法求解此32個表達式組成的方程所需的時間復雜度為323次簡單運算。存儲復雜度為N個分組長度，數據復雜度為N。

綜上，利用Guo等提出的S盒替換Midori-64的S盒后， Midori-64變體算法的弱密鑰為264個。注意到，Guo等設計的S1、S2、S3是應用在KSF1模式下，達到的目標為：存在的弱密鑰為c*2b個。Midori-64的密鑰編排模式遵循KSF2，此時Midori-64變體的弱密鑰空間遠遠大于c*2b。因此 Guo等設計的S1，S2，S3三類S盒沒有達到最初的設計目標，無法抵抗非線性不變攻擊。

4 結語

本文主要對Guo等設計的幾類S盒的安全性進行了新的評估。給出了求解S盒非線性不變函數的新算法，利用新算法測試Guo等的五類S盒。結果表明：其中S1、S2、S3存在相同的二次非線性不變函數。此外，用這三類S盒直接替換Midori-64的S盒來得到Midori-64變體算法，結果表明：Midori-64變體算法存在嚴重的安全漏洞。因此，這三類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] 草冠杰,馬建設,程雪岷.基于組合式爬山算法提高S盒非線性度的方法[J].計算機應用, 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。

國家自然科學基金資助項目(61572148)；廣西自然科學基金(杰出青年基金)資助項目(2015GXNSFGA139007)；廣西高等學校優秀中青年骨干教師培養工程項目(第2期)。

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

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.