Impossible Differential Cryptanalysis of Mysterion

doi:10.3969/j.issn.1671-1122.2021.08.006

Abstract

Abstract:

The Mysterion block cipher is a specific example of the XLS-designs, the main purpose of this algorithm is to improve the LS-designs and enhance the security of LS design strategy without affecting the implementation efficiency. Impossible differential cryptanalysis is applied to analyze Mysterion. Firstly, it proves that the truncated impossible differential of the Mysterion algorithm is upper bounded by 4 rounds. Then, using the information of the S-box breaks through the upper bound of truncated impossible differential of Mysterion and manages to get 5-round impossible differential. The Mysterion’s maximum round of impossible differential is one more than the Robin algorithm, which is the representative algorithm of LS-designs. From the perspective of impossible differential, the security of XLS-designs is weaker than LS-designs.

Key words: block cipher, XLS-designs, impossible differential cryptanalysis

CLC Number:

TP309

YANG Yunxiao, SHEN Xuan, SUN Bing. Impossible Differential Cryptanalysis of Mysterion[J]. Netinfo Security, 2021, 21(8): 43-51.

Figures/Tables 10

References 17

[1]	GROSSO V, LEURENT G, STANDAERT F X, et al. LS-designs: Bitslice Encryption for Efficient Masked Software Implementations[C]//Springer. Fast Software Encryption-21st International Workshop, March 3-5, 2014, London, UK. Berlin: Springer, 2015: 18-37.
[2]	LEANDER G, MINAUD B, RØNJOM S. A Generic Approach to Invariant Subspace Attacks: Cryptanalysis of Robin, iSCREAM and Zorro[C]//Springer. International Conference on the Theory and Applications of Cryptographic Techniques, April 26-30, 2015, Sofia, Bulgaria. Berlin: Springer, 2015: 254-283.
[3]	JOURNAULT A, STANDAERT F, VARICI K. Improving the Security and Efficiency of Block Ciphers Based on LS-designs[J]. Des. Codes Cryptogr, 2017, 82(2):495-509. doi: 10.1007/s10623-016-0193-8 URL
[4]	DAEMEN J, RIJMEN V. The Wide Trail Design Strategy[C]//Springer. Cryptography and Coding, 8th IMA International Conference, December 17-19, 2001, Cirencester, UK. Berlin: Springer, 2001: 222-238.
[5]	KNUDSEN L. DEAL-A 128-bit Block Cipher[J]. Norway: Department of Informatics, University of Bergen, Technical Report 151, 1998.
[6]	BIHAM E, BIRYUKOV A, SHAMIR A. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[C]//Springer. International Conference on the Theory and Application of Cryptographic Techniques, May 2-6, 1999, Prague, Czech Republic. Berlin: Springer, 1999: 12-23.
[7]	KIM J, HONG S, SUNG J, et al. Impossible Differential Cryptanalysis for Block[C]//Springer. 4th International Conference on Cryptology in India, December 8-10, 2003, New Delhi, India. Berlin: Springer, 2003: 82-96.
[8]	LUO Yiyuan, LAI Xuejia, WU Zhongming, et al. A Unified Method for Finding Impossible Differentials of Block Cipher Structures[J]. Information Sciences. 2014, 263(1):211-220. doi: 10.1016/j.ins.2013.08.051 URL
[9]	WU Shengbao, WANG Mingsheng. Automatic Search of Truncated Impossible Differentials for Word-oriented Block Ciphers[C]//Springer. 13th International Conference on Cryptology in India, December 9-12, 2012, Kolkata, India. Berlin: Springer, 2012: 283-302.
[10]	CUI Tingting, JIA Keting, FU Kai, et al. New Automatic Search Tool for Impossible Differentials and Zero-correlation Linear Approximations[J]. Sci. China Inf. Sci. 2021, 64(2):129103. doi: 10.1007/s11432-018-1506-4 URL
[11]	SUN Bing, LIU Zhiqiang, RIJMEN V, et al. Links Among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis[C]//Springer. 35th Annual Cryptology Conference, August 16-20, 2015, Santa Barbara, CA, USA. Berlin: Springer, 2015: 95-115.
[12]	SUN Bing, LIU Meicheng, GUO Jian, et al. Provable Security Evaluation of Structures Against Impossible Differential and Zero Correlation Linear Cryptanalysis[C]//Springer. 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 8-12, 2016, Vienna, Austria. Berlin: Springer, 2016: 196-213.
[13]	SHEN Xuan, LIU Guoqiang, SUN Bing, et al. Impossible Differentials of SPN Ciphers[C]//Springer. 12th International Conference, November 4-6, 2016, Beijing, China. Cham: Springer, 2016: 47-63.
[14]	GOST R 34. 12-2015 NATIONAL STANDARD OF THE RUSSIAN FEDERATION[S]. Moscow: Standartinform, 2015.
[15]	GUO Jian, PEYRIN T, POSCHMANN A. The PHOTON Family of Lightweight Hash[C]//Springer. 31st Annual Cryptology Conference, August 14-18, 2011, Santa Barbara, CA, USA. Berlin: Springer, 2011: 222-239.
[16]	SHEN Xuan, LIU Guoqiang, LI Chao, et al. Impossible Differential Cryptanalysis of Fantomas and Robin[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2018, 101-A(5):863-866.
[17]	SHEN Xuan. Construction and Application of Impossible Differentials of Block Ciphers[D]. Changsha: National University of Defense Technology, 2018.
	沈璇. 分组密码不可能差分的构造及其应用[D]. 长沙:国防科技大学, 2018.

	结构不可能差分轮数	算法不可能差分轮数
Robin算法^[16]	4	4
Mysterion算法	4	5

(i, j)	(x_i,x_j)	#(∆X₃\|ω(∆X₃)=8)	(i, j)	(x_i,x_j)	#(∆X₃\|ω(∆X₃)=8)
(0,2)	(1,1)	5	(2,5)	(8,8)	3
(0,7)	(1,1)	3	(2,6)	(8,8)	5
(0,7)	(8,8)	5	(3,6)	(1,8)	5
(1,2)	(8,8)	4	(5,6)	(8,8)	3
(1,3)	(1,1)	5	(5,7)	(1,1)	4
(1,6)	(1,1)	5	(6,7)	(8,1)	5
(1,7)	(1,1)	4

差分	#(∆X₄,∆Y₄)	N_∆值	搜索结果
(1,1)	2^47.85	8.28	可能
(1,2)	2^46.61	3.52	不可能
(1,3)	2^46.40	3.04	不可能
(1,4)	2^46.47	3.17	不可能
(1,5)	2^47.85	8.28	可能
(1,6)	2^46.74	3.84	不可能
(1,7)	2^46.95	4.44	不可能
(1,8)	2^47.84	8.24	可能
(1,9)	2^47.77	7.86	可能
(1,a)	2^48.16	10.27	可能
(1,b)	2^48.19	10.51	可能
(1,c)	2^47.54	6.68	不可能
(1,d)	2^47.62	7.07	可能
(1,e)	2^47.94	8.79	可能
(1, f)	2^47.90	8.55	可能