自動化搜索ARX分組密碼不可能差分與零相關線性閉包

韓亞

?

自動化搜索ARX分組密碼不可能差分與零相關線性閉包

韓亞1,2

（1. 中國科學院信息工程研究所信息安全國家重點實驗室，北京100093； 2. 中國科學院大學，北京 100049）

首先，構造了ARX分組密碼差分特征及線性掩碼的傳播方程；然后，利用SAT求解器求解傳播方程并且判定該傳播系統是否為有效傳播；最后，遍歷差分特征及線性掩碼自動化搜索不可能差分及零相關線性閉包。利用該算法搜索TEA、XTEA和SIMON的不可能差分與零相關線性閉包，并得到TEA、XTEA及SIMON族分組密碼的最優不可能差分與零相關線性閉包。此外，利用差分以及線性分布表，該算法能有效搜索基于S盒分組密碼的不可能差分及零相關線性閉包。

不可能差分；零相關線性；ARX結構；SAT求解器

1 引言

不可能差分分析[1]由Knudsen提出用于分析DEAL分組密碼，隨后Biham等[2]利用該方法分析Skipjack[2]和IDEA[3]。針對AES[4,5]、CLEFIA[6]和LBlock[7]等分組密碼，不可能差分分析已經成為一種行之有效的攻擊方法。不可能差分分析利用差分傳播概率為零的區分器（不可能差分）篩除錯誤輪密鑰，并通過窮舉候選密鑰恢復正確密鑰。零相關線性分析方法由Bogdanov等[8]第一次提出用于分析分組密碼算法。現在，零相關線性分析已經成功應用到CLEFIA[9]、LBlock[10,11]和SIMECK[12]等分組密碼中。與不可能差分分析類似，零相關線性分析利用線性傳播掩碼為零的區分器（零相關線性閉包）篩除錯誤輪密鑰，結合窮舉恢復正確密鑰。不可能差分分析與零相關線性分析區分器的長度直接決定其攻擊輪長度。因此，如何有效地搜索更長更多的不可能差分及零相關線性閉包至關重要。

早期密碼研究者利用中間相錯法（miss-in- the-middle）搜索不可能差分及零相關線性閉包。2003年，Kim等[13]提出了一種自動化搜索不可能差分的方法——方法，該方法只適用于搜索具有雙射輪函數的分組密碼算法。2009年，Luo等[14]通過改進方法提出一種搜索不可能差分方法——UID方法。UID方法提出了更一般化的不可能差分判定條件。2012年，Wu等[15]提出了更一般化的自動化搜索不可能差分方法——WW方法。WW方法通過構建輪差分路徑傳播方程，并通過全部求解線性方程以及部分求解非線性方程判定不可能差分，最后通過窮舉輸入輸出差分自動化搜索分組密碼輪不可能差分。由于方法、UID方法以及WW方法不能夠有效地刻畫差分經過“&”運算以及模加運算的傳播方程，因此，這3種方法都不適用于搜索ARX結構分組密碼的不可能差分。

ARX結構分組密碼輪函數由模加運算（addition）、循環移位運算（rotation）和異或運算（XOR）組成。Lipmaa等[16]給出對數時間算法計算差分特征值經過模加運算的差分傳播概率，并給出差分傳播以概率1經過模加運算的傳播條件。Wallén[17]給出線性掩碼經過模加運算的相關系數計算方程，并給出線性掩碼以概率1經過模加運算的傳播條件。結合Lipmaa和Wallén提出的計算方程，通過構造ARX分組密碼差分，線性傳播方程，利用求解器的方法實現自動化搜索ARX結構分組密碼的不可能差分和零相關線性閉包。

本文利用SAT/SMT求解器，通過構建差分及線性掩碼傳播方程，自動化搜索ARX結構分組密碼的不可能差分及零相關線性閉包。結果如表1所示。

表1 最優不可能差分及零相關線性閉包輪數

2 差分、線性掩碼部件傳播模型

ARX結構分組密碼輪函數包括模加運算、循環移位運算、異或運算和分支操作。差分及線性掩碼經過各部件的傳播可以通過方程的形式表示。

2.1 模加運算

(2)

否則

其中

(4)

(5)

(7)

2.2 循環移位運算

(9)

2.3 異或運算

(11)

2.4 分支運算

(13)

2.5 類SIMON輪函數

(15)

(16)

則差分傳播概率為

(18)

則線性平方相關系數為

(20)

3 算法實現

3) 求解。利用SAT/SMT求解器求解并返回結果。

step 1;

step 2;

step 3;

break;

else

總條數加1;

end if

end for

end for

其中，稱step1、step2、step3為一個會話，遍歷與的時間復雜度為個會話。當取值較大時，計算機很難實現整個搜索過程。因此，在遍歷與時，限制其漢明重量使。因此該算法的時間復雜度約為O()，數據復雜度為O()，空間復雜度為O(1)。當取值為128時，所需時間復雜度約為O()，數據復雜度為O()，空間復雜度為O(1)。

表2 TEA和XTEA分組密碼搜索結果

4 應用

4.1 TEA和XTEA

TEA是由Wheeler等[19]提出的一種輕量級分組密碼算法。TEA的分組長度為64 bit，密鑰長度為128 bit。TEA分組密碼輪函數包括模加運算、循環移位和異或運算，輪函數表示為

XTEA是Needham等[19]對TEA的一種改進方案，保持了TEA的分組長度和密鑰長度，改進了輪函數結構，輪函數表示為

(23)

TEA和XTEA分組密碼輪函數如圖1所示。

遍歷所有輸入輸出漢明重量為1的差分、線性特征值，利用差分以及線性經過分組密碼部件傳播模型并結合TEA和XTEA輪函數結構，構建輪差分（線性掩碼）傳播方程滿足差分傳播概率(線性掩碼相關系數)。解析輪差分（線性掩碼）傳播方程為SAT求解器識別模型，并判斷該條路徑是否為不可能差分（零相關線性掩碼）。該搜索算法對TEA和XTEA分組密碼的搜索結果如表2所示。

4.2 SIMON

SIMON[20]是NSA提出的輕量級分組密碼算法。SIMON是類Feistel結構分組密碼，其分組長度為，表示為SIMON2n，字長度。SIMON分組密碼輪函數表示為

循環移位常數，，。SIMON分組密碼輪函數如圖2所示。

利用該搜索算法，針對不同版本的SIMON分組密碼搜索結果如表3所示。

5 結束語

本文利用SAT/SMT求解器，提出一種全新的自動化搜索分組密碼不可能差分和零相關線性閉包的方法。該方法針對分組長度大于64 bit的ARX結構分組密碼算法仍然有效。本文應用該方法搜索TEA、XTEA及SIMON分組密碼的不可能差分及零相關線性閉包。針對TEA和XTEA，最優不可能差分及零相關線性閉包長度分別為15輪、15輪。本文提出的SIMON32/48/64/96/128的最優不可能差分及零相關線性閉包長度分別為11輪、12輪、13輪、16輪和19輪。

表3 SIMON分組密碼搜索結果

[1] KNUDSEN L R. Deal - a 128 bit block cipher[J]. Complexity, 1998.

[2] BIHAM E, BIRYUKOV A, SHAMIR A. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials[C]//Advances in Cryptology — EUROCRYPT ’99. 1999:12-23.

[3] BIHAM E, BIRYUKOV A, SHAMIR A. Miss in the middle attacks on IDEA and Khufu[C]//The International Workshop on FAST Software Encryption. 1999:124-138.

[4] PHAN C W. Impossible differential cryptanalysis of 7-round advanced encryption standard(AES)[J]. Information Processing Letters, 2004, 91(1):33-38.

[5] LU J, DUNKELMAN O, KELLER N, et al. New impossible differential attacks on AES[C]// Progress in Cryptology-INDOCRYPT. 2008:279-293.

[6] BOURA C, NAYA-PLASENCIA M, SUDER V. Scrutinizing and improving impossible differential attacks: applications to CLEFIA, camellia, lblock and simon[C]//The International Conference on the Theory and Application of Cryptology and Information Security. 2014:179-199.

[7] CHEN J, FUTA Y, MIYAJI A, et al. Improving impossible differential cryptanalysis with concrete investigation of key scheduling algorithm and its application to lblock[C]//The 8th International Conference on Network and System Security. 2014:184-197.

[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] YI W T, CHEN S Z. Improved integral and zero-correlation linear cryptanalysis of reduced-round CLEFIA block cipher[J]. IACR Cryptology ePrint Archive, 2016:149.

[10] SOLEIMANY H, NYBERG K. Zero-correlation linear cryptanalysis of reduced-round LBlock[J]. Designs Codes & Cryptography, 2014, 73(2):683-698.

[11] XU H, JIA P, HUANG G, et al. Multidimensional zero-correlation linear cryptanalysis on 23-round LBlock-s[M]//Information and Communications Security. Berlin: Springer, 2015.

[12] ZHANG K, GUAN J, HU B, et al. Security evaluation on simeck against zero correlation linear cryptanalysis[J]. IACR Cryptology ePrint Archive, 2015.

[13] KIM J, HONG S, SUNG J, et al. Impossible differential cryptanalysis for block cipher structures[C]//The 4th International Conference on Cryptology. 2003:82-96.

[14] LUO Y, LAI X, WU Z, et al. A unified method for finding impossible differentials of block cipher structures[J]. Information Sciences, 2014, 263(1):211-220.

[15] WU S, WANG M. Automatic search of truncated impossible differentials for word-oriented block ciphers[C]//The International Conference on Cryptology. 2012:283-302.

[16] LIPMAA H, MORIAI S. Efficient algorithms for computing differential properties of addition[C]//The 8th International Workshop on Fast Software Encryption. 2001:336-350.

[17] WALLéN J. Linear approximations of addition modulo 2n[C]//The 10th International Workshop on Fast Software Encryption (2003). 2003:261-273.

[18] K?LBL S, LEANDER G, TIESSEN T. Observations on the SIMON block cipher family[C]// Advances in Cryptology - CRYPTO 2015:161-185.

[19] WHEELER D J, NEEDHAM R M. Tea, a tiny encryption algorithm[M]//Fast Software Encryption. Berlin : Springer, 1994:363-366.

[20] BEAULIEU R, SHORS D, SMITH J, et al. The simon and speck families of lightweight block ciphers[J]. IACR Cryptology ePrint Archive, 2013(6): 404.

Automatic method for searching impossible differentials and zero-correlation linear hulls of ARX block ciphers

HAN Ya1,2

(1. The State Key Lab of Information Security, Institute of Information Engineering, Chinese Academy of Science, Beijing 100093, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)

Firstly, the differences and linear masks propagation equations of ARX ciphers were established. Secondly, the propagation equations were solved by SAT solver and judged valid or not. Finally, differences and linear masks were traversed to search impossible differentials and zero-correlation linear hulls automatically. The proposed algorithm was applied to TEA, XTEA and SIMON family block ciphers. The optimal impossible differentials and zero-correlation linear hulls for TEA, XTEA and SIMON family block ciphers were proposed. Moreover，with DDT and LAT, the algorithm can also be applied to search the impossible differentials and zero-correlation linear hulls of S-box based block ciphers.

impossible differential, zero-correlation linear hull, ARX structure, SAT solver

TP309

A

10.11959/j.issn.2096-109x.2017.00175

韓亞（1989-），男，河南商丘人，中國科學院信息工程研究所博士生，主要研究方向為密碼學。

2017-05-10；

2017-06-15。

韓亞，hanya@iie.ac.cn

國家自然科學基金資助項目（No.61379142）；國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2013CB834203）

The National Natural Science Foundation of China (No. 61379142), The National Basic Research Program of China (973 Program)(No. 2013CB834203)