The Spectral Invariant Subspace of Word-Based Block Ciphers

doi:10.3969/j.issn.1671-1122.2024.12.004

Abstract

Abstract:

This paper combined the idea of invariant subspace attacks with linear cryptanalysis, and proposed a spectral invariant subspace analysis method. This approach leveraged the property of spectral invariant subspaces to distinguish a block cipher by examining whether a pair of input/output linear masks resides within the same non-trivial subspace. Firstly, it demonstrated that if an S-box satisfied the spectral invariant subspace property, it was linearly equivalent to several smaller S-boxes operating in parallel. Secondly, an efficient algorithm for searching spectral invariant subspaces of S-boxes was presented, which proved effective for commonly used sizes of S-boxes. Furthermore, if the S-boxes employed in a word-based block cipher shared the same spectral invariant subspace, then it followed that the entire cipher possesses this characteristic as well. By utilizing this property, an infinite-round distinguisher with probability 1 for the target cipher was constructed. This paper offered new insights into the relationship between S-boxes and block cipher security and provided valuable guidance for designing new block ciphers. As application, an infinite-round distinguisher with probability 1 specifically for variant Midori128 was developed.

Key words: linear cryptanalysis, word-based block ciphers, spectral invariant subspace, Midori128

CLC Number:

TP309

CUI Ting, ZHOU Yidong, CHEN Shiwei, ZHANG Yi. The Spectral Invariant Subspace of Word-Based Block Ciphers[J]. Netinfo Security, 2024, 24(12): 1845-1854.

Figures/Tables 6

References 29

[1]	NBS. Data Encryption Standard(DES), FIPS PUB 46[M]. Washington: NBS, 1977.
[2]	BIHAM E, SHAMIR A. Differential Cryptanalysis of DES-Like Cryptosystems[C]// Springer. 10th Annual International Cryptology Conference. Heidelberg: Springer, 2007: 2-21.
[3]	MATSUI M. Linear Cryptanalysis Method for DES Cipher[C]// Springer. Workshop on the Theory and Application of Cryptographic Techniques. Heidelberg: Springer, 1993: 386-397.
[4]	BAO Zhenzhen, GUO Jian, LING San, et al. PEIGEN-A Platform for Evaluation, Implementation, and Generation of S-Boxes[J]. IACR Transactions on Symmetric Cryptology, 2019(1): 330-394.
[5]	KIM J, HONG S, SUNG J, et al. Impossible Differential Cryptanalysis for Block Cipher Structures[C]// Springer. The 4th International Conference on Cryptology (INDOCRYPT 2003). Heidelberg: Springer, 2003: 82-96.
[6]	KNUDSEN L, WAGNER D. Integral Cryptanalysis[C]// Springer. The 9th International Workshop on Fast Software Encryption. Heidelberg: Springer, 2002: 112-127.
[7]	WAGNER D. The Boomerang Attack[C]// Springer. 6th International Workshop on Fast Software Encryption. Heidelberg: Springer, 1999: 156-170.
[8]	LEANDER G, ABDELRAHEEM M A, ALKHZAIMI H, et al. A Cryptanalysis of PRINT Cipher: The Invariant Subspace Attack[C]// Springer. Cryptology-CRYPTO 2011: 31st Annual Cryptology Conference. Heidelberg: Springer, 2011: 206-221.
[9]	GUO Jian, JEAN J, NIKOLIC I, et al. Invariant Subspace Attack against Midori64 and the Resistance Criteria for S-Box Designs[EB/OL]. (2016-10-12)[2024-10-10]. https://eprint.iacr.org/2016/973.
[10]	BIRYUKOV A, DE C C, BRAEKEN A, et al. A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms[C]// Springer. Cryptology-EUROCRYPT 2003:International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2003: 33-50.
[11]	BIRYUKOV A, SHAMIR A. Structural Cryptanalysis of SASAS[C]// Springer. Cryptology-EUROCRYPT 2001:International Conference on the Theory and Application of Cryptographic Techniques. Heidelberg: Springer, 2001: 395-405.
[12]	CHABAUD F, VAUDENAY S. Links between Differential and Linear Cryptanalysis[C]// Springer. Workshop on the Theory and Application of Cryptographic Techniques. Heidelberg: Springer, 1995: 356-365.
[13]	BLONDEAU C, NYBERG K. New Links between Differential and Linear Cryptanalysis[C]// Springer. Cryptology-EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2013: 388-404.
[14]	WU Wenling, ZHANG Lei. LBlock: A Lightweight Block Cipher[C]// Springer. Applied Cryptography and Network Security:9th International Conference (ACNS 2011). Heidelberg: Springer, 2011: 327-344.
[15]	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, 83(1): 48-59.
[16]	BEIERLE C, JEAN J, KOLBL S, et al. The SKINNY Family of Block Ciphers and its Low-Latency Variant MANTIS[C]// Springer. Cryptology-CRYPTO 2016: 36th Annual International Cryptology Conference. Heidelberg: Springer, 2016: 123-153.
[17]	BANIK S, BOGDANOV A, ISOBE T, et al. Midori: A Block Cipher for Low Energy[C]// Springer. Cryptology-ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2015: 411-436.
[18]	O’DONNELL R. Analysis of Boolean Functions[M]. Cambridge: Cambridge University Press, 2014.
[19]	BOGDANOV A, RIJMEN V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers[J]. Designs, Codes and Cryptography, 2014, 70(3): 369-383.
[20]	CHEN Zhan, CHEN Huaifeng, WANG Xiaoyun. Cryptanalysis of Midori128 Using Impossible Differential Techniques[C]// Springer. Information Security Practice and Experience:12th International Conference (ISPEC 2016). Heidelberg: Springer, 2016: 1-12.
[21]	TOLBA M, ABDELKHALEK A, YOUSSEF A M. Improved Multiple Impossible Differential Cryptanalysis of Midori128[J]. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2017, 100(8): 1733-1737.
[22]	CUI Yaxin, XU Hong, TAN Lin, et al. SAT-Aided Differential Cryptanalysis of Lightweight Block Ciphers Midori, MANTIS and QARMA[C]// Springer. International Conference on Information and Communications Security. Heidelberg: Springer, 2023: 3-18.
[23]	BOGDANOV A, WANG Meiqin. Zero Correlation Linear Cryptanalysis with Reduced Data Complexity[C]// Springer. 19th International Workshop on Fast Software Encryption. Heidelberg: Springer, 2012: 29-48.
[24]	SUN Bing, LIU Zhiqiang, RIJMEN V, et al. Links among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis[C]// Springer. Annual Cryptology Conference. Heidelberg: Springer, 2015: 95-115.
[25]	HAN Guoyong, ZHAO Hongluan. Revisited Security Evaluation on Midori-64 against Differential Cryptanalysis[J]. KSII Transactions on Internet and Information Systems, 2024, 18(2): 478-493.
[26]	LI Yanjun, LIN Hao, BI Xinjie, et al. MILP-Based Differential Cryptanalysis on Full-Round Shadow[EB/OL]. (2024-03-01)[2024-10-10]. https://doi.org/10.1016/j.jisa.2023.103696.
[27]	ASKIN Ö B, BEYNE T. Poster: Generic Multidimensional Linear Cryptanalysis of Feistel Ciphers[C]// ACM. The 2023 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2023: 3621-3623.
[28]	XU Zhichao, XU Hong, TAN Lin, et al. Linear Cryptanalysis of SPECK and SPARX[EB/OL]. (2024-06-01)[2024-10-10]. https://doi.org/10.1016/j.jisa.2024.103773.
[29]	HADIPOUR H, GERHALTER S, SADEGHI S, et al. Improved Search for Integral, Impossible Differential and Zero-Correlation Attacks[J]. IACR Transactions on Symmetric Cryptology, 2024(1): 234-325.

S盒	${{V}_{1}}$	${{V}_{2}}$
$SS{{b}_{0}}$	(0000)	(0000)
$SS{{b}_{1}}$	(0000)	(00****00)
$SS{{b}_{2}}$	(0****000)	(0000**)
$SS{{b}_{3}}$	(0*000*)	(000**0)