Eagle-128算法的相關(guān)密鑰-矩形攻擊

羅 偉 郭建勝

?

Eagle-128算法的相關(guān)密鑰-矩形攻擊

羅 偉*郭建勝

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

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

分組密碼；密碼分析；Eagle-128；相關(guān)密鑰-矩形攻擊

1 引言

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

本文指出了Jeong等人[14]給出的分析結(jié)果中存在的錯(cuò)誤，利用Eagle-128算法高次DDO結(jié)構(gòu)和SPN結(jié)構(gòu)存在的差分信息泄漏規(guī)律構(gòu)造了算法的高概率相關(guān)密鑰-矩形區(qū)分器，在相關(guān)密鑰-選擇明文條件下對(duì)算法進(jìn)行攻擊，恢復(fù)出了算法的64 bit密鑰。

2 Eagle-128算法介紹

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

S盒變換詳見(jiàn)文獻(xiàn)[10]。

3 輪函數(shù)差分特性分析

定義1 重量表示二元序列中1的個(gè)數(shù)。

3.1 高次DDO結(jié)構(gòu)差分特性分析

(1)當(dāng)輸入差分重量為1時(shí)，其輸出差分

(3)當(dāng)控制信息差分重量為1時(shí)，其輸出差分

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

表1 Eagle-128算法圈子密鑰

定義2 差分重量平衡性是指高次DDO結(jié)構(gòu)的控制信息差分重量為0時(shí)，輸入輸出差分重量相等。

3.2 SPN結(jié)構(gòu)差分特性分析

Eagle-128算法SPN結(jié)構(gòu)由兩層S盒變換和兩層P變換交替構(gòu)成。

4 相關(guān)密鑰-矩形區(qū)分器

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

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

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

圖3 第10輪差分傳遞情況

5 相關(guān)密鑰-矩形攻擊

相關(guān)密鑰-矩形攻擊算法：

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

6 結(jié)束語(yǔ)

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

[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] 詹英杰, 關(guān)杰, 丁林, 等. 對(duì)簡(jiǎn)化版LBLock算法的相關(guān)密鑰不可能差分攻擊[J]. 電子與信息學(xué)報(bào), 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] 吳文玲, 馮登國(guó), 張文濤. 分組密碼的設(shè)計(jì)與分析[M]. 北京: 清華大學(xué)出版社, 2009: 130-131.

羅 偉： 男，1987年生，碩士生，研究方向?yàn)榉纸M密碼設(shè)計(jì)與分析.

郭建勝： 男，1972年生，教授，研究方向?yàn)槊艽a學(xué)與信息安全.

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改回

國(guó)家自然科學(xué)基金(11204379)和河南省科技創(chuàng)新杰出青年計(jì)劃項(xiàng)目(104100510025)資助課題