改進的減輪E2算法中間相遇攻擊

杜小妮; 孫瑞; 鄭亞楠; 梁麗芳

doi:10.11999/JEIT230655

改進的減輪E2算法中間相遇攻擊

doi: 10.11999/JEIT230655

杜小妮^{1, 3, ,},
孫瑞^{1, 2},
鄭亞楠¹,
梁麗芳¹

1.
西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院蘭州 730070
2.
西北師范大學(xué)密碼技術(shù)與數(shù)據(jù)分析重點實驗室蘭州 730070
3.
甘肅省數(shù)學(xué)與統(tǒng)計學(xué)基礎(chǔ)學(xué)科研究中心蘭州 730070

基金項目: 甘肅省自然科學(xué)基金重點資助項目(23JRRA685)，國家自然科學(xué)基金(62172337)，甘肅省基礎(chǔ)研究創(chuàng)新群體項目(23JRRA684)

詳細信息

作者簡介:
杜小妮：女，教授，研究方向為應(yīng)用密碼學(xué)

孫瑞：女，碩士生，研究方向為應(yīng)用密碼學(xué)

鄭亞楠：女，碩士生，研究方向為應(yīng)用密碼學(xué)

梁麗芳：女，博士生，研究方向為應(yīng)用密碼學(xué)

通訊作者:
杜小妮　ymldxn@126.com

中圖分類號: TN918.2; TP309.7
計量
- 文章訪問數(shù): 295
- HTML全文瀏覽量: 132
- PDF下載量: 67
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2023-07-03
- 修回日期: 2023-12-20
- 網(wǎng)絡(luò)出版日期: 2024-02-04
- 刊出日期: 2024-06-30

Improved Meet-in-the-middle Attacks on Reduced-round E2

DU Xiaoni^{1, 3
, ,},
SUN Rui^{1, 2},
ZHENG Yanan¹,
LIANG Lifang¹

1.
College of Mathematics and Statistic, Northwest Normal University, Lanzhou 730070, China
2.
Key Laboratory of Cryptography and Data Analytics, Northwest Normal University, Lanzhou 730070, China
3.
Gansu Provincial Research Center for Basic Disciplines of Mathematics and Statistics, Lanzhou 730070, China

Funds: The Key Project of Gansu Natural Science Foundation (23JRRA685), The National Natural Science Foundation of China (62172337), The Funds for Innovative Fundamental Research Group Project of Gansu Province (23JRRA684)

摘要

摘要: E2算法是AES首輪征集的15個候選算法之一，具有優(yōu)良的軟硬件實現(xiàn)效率和較強的安全性。該文利用多重集和差分枚舉技術(shù)，對E2算法進行中間相遇攻擊。首先以E2-128為例，改進了已有的4輪中間相遇區(qū)分器，將5輪密鑰恢復(fù)攻擊預(yù)計算復(fù)雜度降低為${2^{31}}$次5輪算法加密。其次針對E2-256，將所得區(qū)分器向后增加兩輪，構(gòu)造了6輪中間相遇區(qū)分器，并實現(xiàn)了9輪中間相遇攻擊，攻擊所需的數(shù)據(jù)復(fù)雜度為${2^{105}}$個選擇明文，存儲復(fù)雜度為${2^{200}}$ Byte，時間復(fù)雜度為${2^{205}}$次9輪算法加密。與現(xiàn)有對E2算法的安全性分析結(jié)果相比，該文實現(xiàn)了對E2-256最長輪數(shù)的攻擊。
- 分組密碼 /
- E2算法 /
- 中間相遇攻擊 /
- 差分枚舉技術(shù)
Abstract: E2 is one of the 15 candidate algorithms in the first round of AES, which has the characteristics of excellent software and hardware implementation efficiency and strong security. The meet-in-the-middle attacks on E2 are carried out in this paper by using multiset tabulation technique and differential enumeration technique. First, E2-128 is taken as an example to improve the existing 4-round meet-in-the-middle distinguisher, and the pre-computation complexity of 5-round key recovery attack is reduced to ${2^{31}}$ 5-round encryptions. Second, for E2-256, a 6-round distinguisher is constructed from the new 4-round distinguisher by extending two rounds backward, and then a 9-round meet-in-the-middle attack is presented, whose data complexity is ${2^{105}}$ chosen plaintexts, memory complexity is ${2^{200}}$ Byte, and time complexity is ${2^{205}}$ 9-round encryptions. Compared with the existing security analysis results of E2, the scheme achieves the longest number of attack rounds for E2-256.
- Block cipher /
- E2 /
- Meet-in-the-middle attack /
- Differential enumeration technique

HTML全文

圖 1 E2算法加密流程

下載: 全尺寸圖片幻燈片

圖 2 4輪E2-128中間相遇區(qū)分器

下載: 全尺寸圖片幻燈片

圖 3 5輪E2-128中間相遇攻擊

下載: 全尺寸圖片幻燈片

圖 4 6輪E2-256中間相遇區(qū)分器

下載: 全尺寸圖片幻燈片

圖 5 9輪E2-256中間相遇攻擊

下載: 全尺寸圖片幻燈片

表 1 E2算法攻擊結(jié)果對比

來源	攻擊方法	算法版本	輪數(shù)	時間復(fù)雜度	預(yù)計算復(fù)雜度	數(shù)據(jù)復(fù)雜度
文獻[13]	截斷差分	E2-128/E2-128	$ 7/8 $	–	–	${2^{91}}/{2^{94}}$
文獻[14]	不可能差分	E2-128/E2-256	$ 7/8 $	${2^{115.5}}/{2^{214}}$	–	${2^{120}}/{2^{121}}$
文獻[15]	中間相遇攻擊	E2-128	5	${2^{48}}$	${2^{48}}$	$ 14 $
本文	中間相遇攻擊	E2-128	5	${2^{47.9}}$	${2^{31}}$	$ 12 $
本文	中間相遇攻擊	E2-256	9	${2^{205}}$	${2^{200.6}}$	${2^{105}}$

下載: 導(dǎo)出CSV

參考文獻(16)

[1]	WU Wenling and ZHANG Lei. LBlock: A lightweight block cipher[C]. The 9th International Conference on Applied Cryptography and Network Security, Nerja, Spain, 2011: 327–344. doi: 10.1007/978-3-642-21554-4_19.
[2]	GUPTA K C, PANDEY S K, and SAMANTA S. FUTURE: A lightweight block cipher using an optimal diffusion matrix[C]. The 13th International Conference on Cryptology in Africa, Fes, Morocco, 2022: 28–52. doi: 10.1007/978-3-031-17433-9_2.
[3]	杜小妮, 鄭亞楠, 梁麗芳, 等. RAIN-128算法的中間相遇攻擊[J]. 電子與信息學(xué)報, 2024, 46(1): 327–334. doi: 10.11999/JEIT221593. DU Xiaoni, ZHENG Yanan, LIANG Lifang, et al. Meet-in-the-middle attack on RAIN-128[J]. Journal of Electronics & Information Technology, 2024, 46(1): 327–334. doi: 10.11999/JEIT221593.
[4]	李超, 孫兵, 李瑞林. 分組密碼的攻擊方法與實例分析[M]. 北京: 科學(xué)出版社, 2010. LI Chao, SUN Bing, and LI Ruilin. Attack Method of Block Cipher and Case Analysis[M]. Beijing: Science Press, 2010.
[5]	蔣梓龍, 金晨輝. Saturnin算法的不可能差分分析[J]. 通信學(xué)報, 2022, 43(3): 53–62. doi: 10.11959/j.issn.1000-436x.2022045. JIANG Zilong and JIN Chenhui. Impossible differential cryptanalysis of Saturnin algorithm[J]. Journal on Communications, 2022, 43(3): 53–62. doi: 10.11959/j.issn.1000-436x.2022045.
[6]	DIFFIE W and HELLMAN M. Special feature exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer, 1977, 10(6): 74–84. doi: 10.1109/C-M.1977.217750.
[7]	DUNKELMAN O, KELLER N, and SHAMIR A. Improved single-key attacks on 8-round AES-192 and AES-256[C]. The 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2010: 158–176. doi: 10.1007/978-3-642-17373-8_10.
[8]	SHI Danping, SUN Siwei, DERBEZ P, et al. Programming the Demirci-Sel?uk meet-in-the-middle attack with constraints[C]. The 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia, 2018: 3–34. doi: 10.1007/978-3-030-03329-3_1.
[9]	任炯炯, 侯澤洲, 李曼曼, 等. 改進的減輪MIBS-80密碼的中間相遇攻擊[J]. 電子與信息學(xué)報, 2022, 44(8): 2914–2923. doi: 10.11999/JEIT210441. REN Jiongjiong, HOU Zezhou, LI Manman, et al. Improved meet-in-the-middle attacks on reduced-round MIBS-80 cipher[J]. Journal of Electronics & Information Technology, 2022, 44(8): 2914–2923. doi: 10.11999/JEIT210441.
[10]	BIRYUKOV A, DERBEZ P, and PERRIN L. Differential analysis and meet-in-the-middle attack against round-reduced TWINE[C]. The 22nd International Workshop on Fast Software Encryption, Istanbul, Turkey, 2015: 3–27. doi: 10.1007/978-3-662-48116-5_1.
[11]	LI Manman and CHEN Shaozhen. Improved meet-in-the-middle attacks on reduced-round Joltik-BC[J]. IET Information Security, 2021, 15(3): 247–255. doi: 10.1049/ise2.12019.
[12]	KANDA M, MORIAI S, AOKI K, et al. E2-a new 128-bit block cipher[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2000, E83-A(1): 48–59.
[13]	MORIAI S, SUGITA M, AOKI K, et al. Security of E2 against truncated differential cryptanalysis[C]. The 6th International Conference on Selected Areas in Cryptography, Ontario, Canada, 2000: 106–117. doi: 10.1007/3-540-46513-8_8.
[14]	WEI Yuechuan, YANG Xiaoyuan, LI Chao, et al. Impossible differential cryptanalysis on tweaked E2[C]. The 6th International Conference on Network and System Security, Wuyishan, China, 2012: 392–404. doi: 10.1007/978-3-642-34601-9_30.
[15]	官翔, 魏悅川, 楊曉元. E2算法的中間相遇攻擊[J]. 計算機工程與科學(xué), 2015, 37(3): 524–528. doi: 10.3969/j.issn.1007-130X.2015.03.019. GUAN Xiang, WEI Yuechuan, and YANG Xiaoyuan. Meet-in-the-middle attacks on E2[J]. Computer Engineering & Science, 2015, 37(3): 524–528. doi: 10.3969/j.issn.1007-130X.2015.03.019.
[16]	任炯炯, 陳少真. 11輪3D密碼算法的中間相遇攻擊[J]. 通信學(xué)報, 2015, 36(8): 182–191. doi: 10.11959/j.issn.1000-436x.2015131. REN Jiongjiong and CHEN Shaozhen. Meet-in-the-middle attack on 11-round 3D cipher[J]. Journal on Communications, 2015, 36(8): 182–191. doi: 10.11959/j.issn.1000-436x.2015131.