基于字的分组密码的谱值不变子空间

doi:10.3969/j.issn.1671-1122.2024.12.004

摘要/Abstract

摘要：

文章将不变子空间的思想与线性密码分析相结合，提出一种谱值不变子空间分析方法，通过考察输入输出线性掩码是否属于同一个非平凡的线性子空间来区分密码算法。首先，证明了如果一个S盒存在谱值不变子空间，则该S盒与多个小规模S盒的并置线性等价。其次，给出S盒谱值不变子空间的高效搜索算法，能够快速给出常见规模S盒的谱值不变子空间。特别地，对于基于字的分组密码，证明了若S盒存在谱值不变子空间，则整体轮函数也存在谱值不变子空间，因此可以构造概率为1的无限轮密码区分器。该方法揭示了S盒特性与安全性之间新的内在联系，为后续密码算法的设计与评估提供了参考。作为谱值不变子空间分析方法的应用，构造了变体Midori128的概率为1的无限轮区分器。

关键词: 线性密码分析, 基于字的分组密码, 谱值不变子空间, Midori128

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

中图分类号:

TP309

崔霆, 周屹东, 陈士伟, 张奕. 基于字的分组密码的谱值不变子空间[J]. 信息网络安全, 2024, 24(12): 1845-1854.

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.

图/表 6

图1

图2

图3

图4

图5

表1

参考文献 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)