加密算法Simpira v2的不可能差分攻击

doi:10.19665/j.issn1001-2400.2022.05.023

摘要/Abstract

摘要：

评估适用于各类应用场景中,对称加密算法的安全强度对系统中数据机密性至关重要。Simpira v2是2016年在亚密会上发布可以实现高吞吐量的密码置换算法族,非常适用于信息系统中保护数据的机密性。Simpira-6是Simpira v2族加密算法中6分支的情形,分组长度为128 b比特(bit)。研究了Simpira-6作为Even-Mansour结构下的置换加密算法的安全强度,使用不可能差分攻击基本原理,首先构造一条当前最长的9轮Simpira-6不可能差分链,但基于此攻击需要的复杂度超过穷尽搜索;其次,在Simpira v2的安全性声明下,攻击7轮Simpira-6恢复384位主密钥,攻击需要数据和时间复杂度分别为2^57.07个选择明文和2^57.07次加密;最后,在Even-Mansour安全性声明下对8轮Simpira-6进行不可能差分攻击,恢复768位主密钥,攻击需要数据和时间复杂度分别为2¹⁶⁸个选择明文和2¹⁶⁸次加密。首次对Simpira v2 6分支情形的不可能差分攻击,为未来运用Simpira v2保护数据机密性提供重要的理论依据。

关键词: 分组密码加密系统, 不可能差分攻击, 安全性分析, Simpira v2, 广义Feistel结构, Even-Mansour结构, 安全性声明

Abstract:

It is important to evaluate the security of symmetric encryption algorithms used in various application scenarios for protecting data securely.Simpira v2 is a family of cryptographic permutations with a high throughput proposed in ASIACRYPT 2016.It is very suitable for protecting the confidentiality of data in the information system.Simpira-6 is the case of 6 branches in the Simpira v2 encryption algorithm family,and its block length supports bits.This paper studies the security analysis of Simpira-6 as the permutation algorithm of Even-Mansour structure against impossible differential attacks.First,we propose the longest 9-round impossible differential for Simpira-6 currently,on the basis of which the adversary executes the impossible differential attack,whose time complexity is higher than that of the exhaustive search.Second,under the security claim of Simpira v2,we present a 7-round impossible differential attack on Simpira-6 to recover the 384-bit master key.The data and time complexities of this attack are 2^57.07chosen plaintexts and 2^57.077-round Simpira-6 encryptions,respectively.Third,under the security claim of Even-Mansour,we present an 8-round impossible differential attack on Simpira-6 to recover all 768 bits keys.The data and time complexities are 2¹⁶⁸chosen plaintexts and 2¹⁶⁸ 8-round Simpira-6 encryptions.Those attacks are the first analytical result on Simpira-6 against the impossible differential attack.These results provide an important theoretical foundation for the application of Simpira v2 in future.

Key words: block cipher cryptographic systems, impossible differential attacks, security analysis, Simpira v2, Generalized Feistel Structure, Even-Mansour structure, security claim

中图分类号:

TN918.4

刘亚,宫佳欣,赵逢禹. 加密算法Simpira v2的不可能差分攻击[J]. 西安电子科技大学学报, 2022, 49(5): 201-212.

LIU Ya,GONG Jiaxin,ZHAO Fengyu. Impossible differential attack on the encryption algorithm Simpira v2[J]. Journal of Xidian University, 2022, 49(5): 201-212.

图/表 13

图1

图2

图3

图4

图5

图6

表1

图7

图8

图9

图10

图11

表2

参考文献 18

[1]	GUERON S, MOUHA N.Simpirav2: A Family of Efficient Permutations Using the AES Round Function[C]//International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2016:95-125.
[2]	TJUAWINATA I, TAO H, WU H. Cryptanalysis of Simpira v2[C]//Australasian Conference on Information Security and Privacy. Berlin: Springer, 2017:384-401.
[3]	ZONG R, DONG X, WANG X. Impossible Differential Attack on Simpira v2[J]. Science China Information Sciences, 2018, 61(3):71-83.
[4]	叶涛, 韦永壮, 李灵琛. KNOT认证加密算法的零和区分器分析[J]. 西安电子科技大学学报, 2021, 48(1):76-86.
	YE Tao, WEI Yongzhuang, LI Lingchen. Analysis of Zero-Sum Distinguisher of the KNOT Authenticated Encryption Algorithm[J]. Journal of Xidian University, 2021, 48(1):76-86.
[5]	王省欣, 胡伟, 谭静, 等. AES相关故障注入攻击[J]. 西安电子科技大学学报, 2021, 48(4):192-199.
	WANG Xingxin, HU Wei, TAN Jing, et al. Correlation Fault Attack on AES[J]. Journal of Xidian University, 2021, 48(4):192-199.
[6]	谷大武, 张驰, 陆相君. 密码系统的侧信道分析:进展与问题[J]. 西安电子科技大学学报, 2021, 48(1):14-21.
	GU Dawu, ZHANG Chi, LU Xiangjun. Progress of and Some Comments on the Research of Side-Channel Attack for Cryptosystems[J]. Journal of Xidian University, 2021, 48(1):14-21.
[7]	WANG Q, JIN C. More Accurate Results on the Provable Security of AES Against Impossible Differential Cryptanalysis[J]. Designs Codes and Cryptography, 2019, 87(12):3001-3018. doi: 10.1007/s10623-019-00660-7
[8]	LIU Y, ZANG T, GU D, et al. Improved Cryptanalysis of Reduced-Version QARMA-64/128[J]. IEEE Access, 2020, 8(99):8361-8370. doi: 10.1109/ACCESS.2020.2964259
[9]	石新蕾, 刘亚, 陆海宁, 等. 21轮CRAFT算法不可能差分分析[J]. 计算机应用研究, 2021, 38(9):2825-2830.
	SHI Xinlei, LIU Ya, LU Haining, et al. Impossible Differential Cryptanalysis of 21-Round CRAFT[J]. Application Research of Computers, 2021, 38(9):2825-2830.
[10]	李明明, 郭建胜, 崔竞一, 等. Midori-64算法的截断不可能差分分析[J]. 软件学报, 2019, 30(8):2337-2348.
	LI Mingming, GUO Jiansheng, CUI Jingyi, et al. Truncated Impossible Differential Cryptanalysis of Midori-64[J]. Journal of Software, 2019, 30(8):2337-2348.
[11]	TOLBA M, ELSHEIKH M, YOUSSEF A M. Impossible Differential Cryptanalysis of Reduced-Round Tweakable TWINE[C]//International Conference on Cryptology in Africa. Berlin: Springer, 2020:91-113.
[12]	GUPTA S K, GHOSH M, MOHANTY S K. Cryptanalysis of Kalyna Block Cipher Using Impossible Differential Technique[J]. Proceedings of the Sixth International Conference on Mathematics and Computing, 2021, 1262:125-141.
[13]	魏悦川, 潘晓中, 戎宜生, 等. 对PRINCE分组密码的不可能差分攻击[J]. 西安电子科技大学学报, 2017, 44(1):119-124.
	WEI Yuechuan, PAN Xiaozhong, RONG Yisheng, et al. Impossible Differential Cryptanalysis on the PRINCE[J]. Journal of Xidian University, 2017, 44(1):119-124.
[14]	KNUDSEN L R. DEAL-A 128-bit Block Cipher[EB/OL].[1998-02-21].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7982&rep=rep1&type=pdf .
[15]	BIHAM E, BIRYUKOV A, SHAMIR A. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[C]//Advances in Cryptology — EUROCRYPT 1999.Berlin:Springer, 1999:12-23.
[16]	EVEN S, MANSOUR Y. A Construction of a Cipher from a Single Pseudorandom Permutation[C]//Advances in Cryptology-ASIACRYPT'91. Berlin: Springer, 1991:210-224.
[17]	DUNKELMAN O, KELLER N, SHAMIR A. Minimalism in Cryptography:The Even-Mansour Scheme Revisited[C]//Advances in Cryptology-EUROCRYPT 2012. Berlin: Springer, 2012:336-354.
[18]	DAEMEN J, RIJMEN V. Understanding Two-Round Differentials in AES[C]//International Conference on Security & Cryptography for Networks. Berlin: Springer, 2006:78-94.

ΔP₀(ΔP₂、ΔP₄)	ΔC₁(ΔC₃、ΔC₃)	K₀(K₂、K₄)
(00000000000000)	(0**00**0)	[0,5,10,15]
(00000000000000)	(*000*0)	[4,9,14,3]
(00000000000000)	(000000)	[8,13,2,7]
(00000000000000)	(0*000*)	[12,1,6,11]

算法	轮数	恢复的主密钥数/bit	数据复杂度 (个选择明文)	时间复杂度	攻击方法	来源
Simpira-3	9	256	2²²	2²⁴次解密	截断差分攻击	文献[2]
	10	128	2³⁴	2⁷⁰次解密	不可能差分攻击	文献[2]
	10	128	2⁵³	2⁸⁵次解密	飞去来攻击	文献[2]
Simpira-4	7	256	2⁵⁷	2⁵⁷次加密	不可能差分攻击	文献[3]
Simpira-4	8	512	2¹⁷⁰	2¹⁷⁰次加密	不可能差分攻击	文献[3]
Simpira-6	7	384	2^57.07	2^57.07次加密	不可能差分攻击	文中
Simpira-6	8	768	2¹⁶⁸	2¹⁶⁸次加密	不可能差分攻击	文中