Eagle-128算法的相關密鑰-矩形攻擊

羅 偉 郭建勝

?

Eagle-128算法的相關密鑰-矩形攻擊

羅 偉*郭建勝

(解放軍信息工程大學 鄭州 450001)

該文利用高次DDO(Data Dependent Operations)結構的差分重量平衡性和SPN結構的高概率差分對構造了Eagle-128分組密碼算法的兩條5輪相關密鑰-差分特征，通過連接兩條5輪特征構造了完全輪相關密鑰-矩形區分器，并對算法進行了相關密鑰-矩形攻擊，恢復出了Eagle-128算法的64 bit密鑰。攻擊所需的數據復雜度為281.5個相關密鑰-選擇明文，計算復雜度為2106.7次Eagle-128算法加密，存儲復雜度為250Byte存儲空間，成功率約為0.954。分析結果表明，Eagle-128算法在相關密鑰-矩形攻擊條件下的有效密鑰長度為192 bit。

分組密碼；密碼分析；Eagle-128；相關密鑰-矩形攻擊

1 引言

作為基于高次DDO結構的分組密碼算法的典型代表，Eagle-128算法由Moldovyan等人[10]于2006年提出。針對該算法的安全性，設計者構造了三條兩輪循環差分特征，并聲稱當輪數大于8輪時，Eagle-128算法能夠有效抵抗差分攻擊。2007年，Jeong等人[14]對Eagle-128算法進行了相關密鑰-擴大飛來去器攻擊，試圖恢復算法的64 bit密鑰，這也是之前針對該算法的唯一分析結果。

本文指出了Jeong等人[14]給出的分析結果中存在的錯誤，利用Eagle-128算法高次DDO結構和SPN結構存在的差分信息泄漏規律構造了算法的高概率相關密鑰-矩形區分器，在相關密鑰-選擇明文條件下對算法進行攻擊，恢復出了算法的64 bit密鑰。

2 Eagle-128算法介紹

Eagle-128算法分組規模為128 bit，密鑰規模為256 bit，迭代輪數為10輪。算法整體結構和圈函數結構分別如圖1(a)和圖1(b)所示，圈函數中SPN結構和SPN-1結構分別如圖1(c)和圖1(d)所示。

S盒變換詳見文獻[10]。

3 輪函數差分特性分析

定義1 重量表示二元序列中1的個數。

3.1 高次DDO結構差分特性分析

(1)當輸入差分重量為1時，其輸出差分

(3)當控制信息差分重量為1時，其輸出差分

記表示輸入數據差分為，控制信息差分為時，基本單元輸出差分為的概率。根據性質1(3)， ，其中。從而，文獻[14]得到“ 對任意成立”(見文獻[14]3.3節性質1(d))的結論是錯誤的。

表1 Eagle-128算法圈子密鑰

定義2 差分重量平衡性是指高次DDO結構的控制信息差分重量為0時，輸入輸出差分重量相等。

3.2 SPN結構差分特性分析

Eagle-128算法SPN結構由兩層S盒變換和兩層P變換交替構成。

4 相關密鑰-矩形區分器

定義3[15]若明文四元組及對應密文四元組滿足矩形區分器中的差分特征，則稱其為正確四元組。

圖2 結構的兩條最優差分特征(a)e19→e6,8,12,21,23,27; (b)e12→e1,3,9,11,20,26,28

表2 Eagle-128算法的兩條高概率相關密鑰-差分特征

圖3 第10輪差分傳遞情況

5 相關密鑰-矩形攻擊

相關密鑰-矩形攻擊算法：

相關密鑰-矩形攻擊算法的成功率和復雜度分析分別由定理1和定理2給出。

6 結束語

本文對Eagle-128算法在相關密鑰-矩形條件下的安全性進行評估，利用密鑰差分構造了算法的高概率相關密鑰-矩形區分器，首次給出算法正確的安全性分析結果。本文的分析結果表明，Eagle-128算法選用的SPN結構數據處理規模較小，存在明顯的差分不平衡特性，造成信息泄漏；與此同時，高次DDO結構具有的差分重量平衡性使得攻擊者能夠構造高概率差分特征。因此，利用高次DDO結構設計密碼算法時應當充分考慮高次DDO結構與其它編碼環節、圈子密鑰與數據的結合方式，消除高次DDO結構和其它編碼結構在差分分析條件下存在的信息泄漏規律。

[1] Biryukov A and Nikolic I. Automatic search for related-key differential characteristics in byte-oriented block ciphers: application to AES, Camellia, Khazad and Others[J]., 2010, 6110: 322-344.

[2] Biryukov A and Nikolic I. Search for related-key differential characteristics in DES-Like ciphers[J]., 2011, 6733: 18-34.

[3] 詹英杰, 關杰, 丁林, 等. 對簡化版LBLock算法的相關密鑰不可能差分攻擊[J]. 電子與信息學報, 2012, 34(9): 2161-2166.

Zhan Ying-jie, Guan Jie, Ding Lin,.. Related-key impossible differential attack on reduced round LBlock[J].&, 2012, 34(9): 2161-2166.

[4] Biham E, Dunkelman O, and Keller N. Related-key boomerang and rectangle attacks[J]., 2005, 3494: 507-525.

[5] Biham E, Dunkelman O, and Keller N. The rectangle attack-rectangling the Serpent[J]., 2001, 2045:340-357.

[6] Kim J,Hong S, Preneel B,.. Related-key boomerang and rectangle attacks: theory and experimental analysis[J]., 2012, 58(7): 4948-4966.

[7] Isobe Takanori, Sasaki Yu, and Chen Jia-geng. Related-key boomerang attacks on KATAN32/48/64[J]., 2013, 7959: 268-285.

[8] Moldovyan A A and Moldovyan N A. A cipher based on data-dependent permutation[J]., 2002, 15(1): 61-72.

[9] Moldovyan A A, Moldovyan N A, and Sklavos N. Controlled elements for designing ciphers suitable to efficient VLSI implementation[J], 2006, 32(2/3): 149-163.

[10] Moldovyan N A, Moldovyan A A, Eremeev M A,.. New class of cryptographic primitives and cipher design for networks security[J]., 2006, 2(2): 114-125.

[11] Sklavos N, Moldovyan N A, and Koufopavlou O. High speed networking security: design and implementation of two new DDP-based ciphers[J]., 2005, 10(1/2): 219-231.

[12] Sklavos N, Moldovyan N A, Moldovyan A A,. CHESS-64, a block cipher based on data-dependent operations: design variants and hardware implementation efficiency[J].2005, 4(4): 323-334.

[13] Thi Bac-do, Hieu Minh-nguyen, and Ngoc Duy-ho. An effective and secure cipher based on SDDO[J]., 2012, 4(11): 1-10.

[14] Jeong K, Lee C, Sung J,.. Related-key amplified boomerang attacks on the full-round Eagle-64 and Eagle- 128[J]., 2007, 4586: 143-157.

[15] 吳文玲, 馮登國, 張文濤. 分組密碼的設計與分析[M]. 北京: 清華大學出版社, 2009: 130-131.

羅 偉： 男，1987年生，碩士生，研究方向為分組密碼設計與分析.

郭建勝： 男，1972年生，教授，研究方向為密碼學與信息安全.

Related-key Rectangle Attack on Eagle-128 Algorithm

Luo Wei Guo Jian-sheng

(,450001,)

By utilizing the balanceable difference weight of high order Data Dependent Operations (DDO) and the high probability differentials of SPN structures, two 5-round related-key differentials of Eagle-128 are constructed. A full round related-key rectangle distinguisher of Eagle-128 is constructed by connecting two 5-round related-key differentials, and a related-key rectangle attack is proposed on the cipher to recover 64 bit of the master key. The corresponding data complexity is about 281.5related-key chosen-plain-text, the computation complexity is about 2106.7encryptions of the cipher, and the storage complexity is about 250Byte of storage space. The success rate of the attack is about 0.954. The analysis results show that the practical length of Eagle-128’s master key is 192 bit.

Block cipher; Cryptanalysis; Eagle-128; Related-key rectangle attack

TN918.1

A

1009-5896(2014)06-1520-05

10.3724/SP.J.1146.2013.01239

羅偉 luowei.crypt@gmail.com

2013-08-15收到，2013-12-13改回

國家自然科學基金(11204379)和河南省科技創新杰出青年計劃項目(104100510025)資助課題