积分攻击改进——随机线性区分与密钥恢复攻击

doi:10.11959/j.issn.1000-436x.2023085

摘要/Abstract

摘要：

在 4 轮 AES 的积分攻击和碰撞攻击的基础上，提出了一种利用明文和中间状态的某些分组之间线性偏差分布的不均匀性的针对4轮SP结构分组密码的随机线性区分攻击。进一步结合预计算，提出了对4轮AES类分组密码的密钥恢复攻击。对 LED-64 算法给出了具体区分攻击和密钥恢复攻击的结果。其中，对于 1-Step 的LED-64算法，在数据复杂度为2⁸，计算复杂度为2¹⁶次基本运算的条件下，区分成功的概率是85%；对于2-Step的 LED-64 算法，相关密钥条件下的密钥恢复攻击的计算复杂度为 2¹⁴次基本运算，数据复杂度为 2⁸，预计算存储复杂度为2³⁸个半字节。

关键词: 积分攻击, 区分攻击, 分组密码分析, AES, LED

Abstract:

Based on the integral attack and collision attack of four rounds of AES, a random linear distinguish attack against four rounds of SP block ciphers was proposed, which took advantage of the non-uniformity of linear biases’ distribution between some blocks of plaintext and inner state.Combined with precomputation, a key recovery attack against four rounds of AES-like block ciphers was proposed.For LED-64, the results of distinguish attack and key recovery attack were given.Therein for LED-64 of 1-Step, the probability of successful distinguish attack is 85% under the condition that the data complexity is 2⁸ and the computational complexity is 2¹⁶ basic operation.For LED-64 of 2-Step, the calculation complexity of the key recovery attack under the condition of related key is 2¹⁴ basic operation, the data complexity is 2⁸, and the precomputation storage complexity is 2³⁸ half bytes.

Key words: integral attack, distinguish attack, block cipher analysis, AES, LED

中图分类号:

TN92

杜少宇. 积分攻击改进——随机线性区分与密钥恢复攻击[J]. 通信学报, 2023, 44(4): 145-153.

Shaoyu DU. Improved integral attack——random linear distinguish and key recovery attack[J]. Journal on Communications, 2023, 44(4): 145-153.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

表2

参考文献 23

[1]	BOGDANOV A , KNUDSEN L R , LEANDER G ,et al. PRESENT:an ultra-lightweight block cipher[C]// Proceedings of Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2007: 450-466.
[2]	GUO J , PEYRIN T , POSCHMANN A ,et al. The LED block cipher[C]// Proceedings of Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2011: 326-341.
[3]	WU W L , ZHANG L . LBlock:a lightweight block cipher[C]// Proceedings of Applied Cryptography and Network Security. Berlin:Springer, 2011: 327-344.
[4]	KNUDSEN L , LEANDER G , POSCHMANN A . PRINT cipher:a block cipher for IC-printing[C]// Proceedings of Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2010: 16-32.
[5]	LALLEMAND V , NAYA-PLASENCIA M . Cryptanalysis of KLEIN[C]// Proceedings of Fast Software Encryption. Berlin:Springer, 2014: 451-470.
[6]	BEAULIEU R , TREATMAN-CLARKS , SHORS D ,et al. The SIMON and SPECK lightweight block ciphers[C]// Proceedings of 2015 52nd ACM/EDAC/IEEE Design Automation Conference. Piscataway:IEEE Press, 2015: 1-6.
[7]	DAEMEN J , KNUDSEN L , RIJMEN V . The block cipher square[C]// Proceedings of Fast Software Encryption. Berlin:Springer, 1997: 149-165.
[8]	LI Y J , WU W L . Improved integral attacks on Rijndael[J]. Journal of Information Science and Engineering, 2011,27(6): 2031-2045.
[9]	LI Y J , WU W L , ZHANG L . Integral attacks on reduced-round ARIA block cipher[C]// Proceedings of Information Security Practice and Experience. Berlin:Springer, 2010: 19-29.
[10]	ZABA M R , RADDUM H , HENRICKSEN M ,et al. Bit-pattern based integral attack[C]// Proceedings of Fast Software Encryption. Berlin:Springer, 2008: 363-381.
[11]	XIA T F , ZHAO Z Y , LI W ,et al. A new kind of integral cryptanalysis for the round-reduced AES[J]. Electrical Engineering and Computer Science, 2019,3: 6-9.
[12]	LI H , REN J J , CHEN S Z . Improved integral attack on reduced-round SIMECK[J]. IEEE Access, 2019,7: 118806-118814.
[13]	ELSHEIKH M , YOUSSEF A M . Integral cryptanalysis of reduced-round tweakable TWINE[C]// Proceedings of Cryptology and Network Security. Berlin:Springer, 2020: 485-504.
[14]	DUO L , LI C , FENG K Q . Square like attack on Camellia[C]// Proceedings of Cryptology and Network Security. Berlin:Springer, 2007: 269-283.
[15]	LI Y J , WU W L , ZHANG L T ,et al. Improved integral attacks on reduced round Camellia[EB].[2011-04-11].
[16]	CHEN L L , WANG G L , ZHANG G Y . MILP-based related-key rectangle attack and its application to GIFT,Khudra,MIBS[J]. The Computer Journal, 2019,62(12): 1805-1821.
[17]	XIANG Z J , ZHANG W T , BAO Z Z ,et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]// Proceedings of Advances in Cryptology. Berlin:Springer, 2016: 648-678.
[18]	ISOBE T , SHIBUTANI K . Security analysis of the lightweight block ciphers XTEA,LED and Piccolo[C]// Proceedings of Information Security and Privacy. Berlin:Springer, 2012: 71-86.
[19]	MENDEL F , RIJMEN V , TOZ D ,et al. Differential analysis of the LED block cipher[C]// Proceedings of Advances in Cryptology. Berlin:Springer, 2012: 190-207.
[20]	NIKOLI? I , WANG L , WU S . Cryptanalysis of round-reduced LED[C]// Proceedings of Fast Software Encryption. Berlin:Springer, 2013: 112-129.
[21]	DINUR I , DUNKELMAN O , KELLER N ,et al. Key recovery attacks on 3-roundeven-mansour,8-Step LED-128,and full AES2[C]// Proceedings of Advances in Cryptology. Berlin:Springer, 2013: 337-356.
[22]	MAXIMOV A , JOHANSSON T . A linear distinguishing attack on scream[J]. IEEE Transactions on Information Theory, 2007,53(9): 3127-3144.
[23]	SUN L , WANG W , WANG M . More accurate differential properties of LED64 and Midori64[J]. IACR Transactions on Symmetric Cryptology, 2018(3): 93-123.

攻击假设	Step	计算复杂度	数据复杂度	存储复杂度/半字节	攻击成功概率	文献
单密钥	1	2 ³⁹	2 ³⁵	0	0.92	本文
选择密钥	1	2 ¹⁶	2⁸	0	0.85	本文
选择密钥	3.75	2 ¹⁶	—	2 ¹⁶	—	文献[2]
选择密钥	4	2 ^33.5	—	2 ³²	—	文献[20]
选择密钥	5	2 ^60.2	—	2 ⁶¹	—	文献[20]
选择密钥	5	2 ^57.7	—	2 ^58.5	—	文献[23]

攻击假设	Step	计算复杂度	数据复杂度	存储复杂度/半字节	攻击成功概率	文献
单密钥	1	2 ¹⁰	2⁴	2 ³⁸	1	本文
选择密钥	2	2 ¹⁴	2⁸	2 ³⁸	1	本文
选择密钥	2	2 ⁵⁶	2⁸	2 ¹¹	—	文献[18]
选择密钥	3	2 ^60.2	2 ⁴⁹	2⁶⁰	—	文献[21]
选择密钥	4	2 ^62.7	2 ^62.7	2 ^62.7	—	文献[19]
选择密钥	4	2 ^60.8	2 ^60.8	2^60.8	—	文献[23]