面向MD哈希结构的量子新牧群攻击

doi:10.12305/j.issn.1001-506X.2025.09.32

Abstract

Abstract:

Aiming at the security issues of MD （Merkle-Damgard） with hash structure in the quantum environment, the idea of combining BHT （Brassard-H?yer-Tapp） quantum algorithm and CNS （Chailloux-Naya Plasencia-Schrottenloher） quantum algorithm with the classical new herding attack respectively is proposed, and two attack modes are constructed. Firstly, the BHT quantum algorithm is used to construct a “variable length diamond tree” to increase the number of connected nodes and improve the attack efficiency. Under certain conditions, when the length of recovery message is the same, the attack complexity is lower. Then, taking secure hash algorithm （SHA）-256 as an example, the specific attack complexity is given. Then, an attack mode combining CNS quantum algorithm with new herding attack is proposed, which no longer needs quantum random access memory （qRAM） in the attack process, reducing the attack implementation cost. The attack mode can select the message length for recovery within a certain range, which is better than the non-selectable case in the existing schemes.

Key words: hash function, herding attack, BHT （Brassard-H?yer-Tapp） algorithm, CNS （Hailloux-Naya Plasencia–Schrottenloher） algorithm

CLC Number:

TN 918.11

Xuelian LI, Chenglong LI, Tao PEI, Juntao GAO. New quantum herding attack on hash with MD construction[J]. Systems Engineering and Electronics, 2025, 47(9): 3099-3108.

Figures/Tables 6

References 33

1	张勋才, 牛莹, 崔光照, 等. 基于自组装DNA计算的RSA密码系统破译方案[J]. 系统工程与电子技术, 2010, 32 (5): 1094- 1099. doi: 10.3969/j.issn.1001-506X.2010.05.045
	ZHANG X C, NIU Y, CUI G Z, et al. Breaking the RSA public key cryptosystem using self-assembly of DNA tilings[J]. Systems Engineering and Electronics, 2010, 32 (5): 1094- 1099. doi: 10.3969/j.issn.1001-506X.2010.05.045
2	谢邦勇, 熊萍, 王德石. 时空混沌保密通信系统的微扰攻击法[J]. 系统工程与电子技术, 2009, 31 (3): 677- 680. doi: 10.3321/j.issn:1001-506X.2009.03.045
	XIE B Y, XIONG P, WANG D S. Slight perturbation attack on spatiotemporal chaotic cryptosystem[J]. Systems Engineering and Electronics, 2009, 31 (3): 677- 680. doi: 10.3321/j.issn:1001-506X.2009.03.045
3	SHOR P W. Algorithms for quantum computation: discrete logarithms and factoring [C]// Proc. of the 35th Annual Symposium on Foundations of Computer Science, 1994: 124−134.
4	SIMON D R. On the power of quantum computation[J]. SIAM Journal on Computing, 1997, 26 (5): 1474- 1483. doi: 10.1137/S0097539796298637
5	KUWAKADO H, MORII M. Quantum distinguisher between the 3-round feistel cipher and the random permutation[C]// Proc. of the IEEE International Symposium on Information Theory, 2010: 2682–2685.
6	KUWAKADO H, MORII M. Security on the quantum-type even-mansour cipher[C]//Proc. of the International Symposium on Information Theory and its Applications, 2012: 312–316.
7	张中亚, 吴文玲, 邹剑. 多轮EM结构的量子差分碰撞密钥恢复攻击[J]. 计算机研究与发展, 2021, 58 (12): 2811- 2818. doi: 10.7544/issn1000-1239.2021.20200427
	ZHANG Z Y, WU W L, ZOU J. Quantum differential collision key recovery attack of multi-round EM structure[J]. Journal of Computer Research and Development, 2021, 58 (12): 2811- 2818. doi: 10.7544/issn1000-1239.2021.20200427
8	GROVER L K. A fast quantum mechanical algorithm for database search[C]//Proc. of the 28th annual ACM symposium on Theory of computing, 1996: 212−219.
9	AMY M, MATTEO O, GHEORGHIU V, et al. Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3[C]// Proc. of the Selected Areas in Cryptography, 2017: 317–337.
10	BRASSARD G, HOYER P, TAPP A. Quantum cryptanalysis of hash and claw-free functions[C]//Proc. of the LATIN’98: Theoretical Informatics, 1998: 163–169.
11	CHAILLOUX A, PLASENCIA M N, SCHROTTEN-LOHER A. An efficient quantum collision search algorithm and implications on symmetric cryptography[C]//Proc. of the Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, 2017: 211–240.
12	HOSOYAMADA A, SASAKI Y. Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound[C]// Proc. of the Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2020: 249–279.
13	DONG X Y , GUO J, LI S, et al. Triangulating rebound attack on aes-like hashing[C]// Proc. of the Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, 2022: 94–124.
14	DONG X Y, SUN S W, SHI D P, et al. Quantum collision attacks on aes-like hashing with low quantum random access memories[C]// Proc. of the Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020: 727–757.
15	董炳佑, 刘泰, 崔玉龙, 等. 改进的五轮Grøstl-512的量子碰撞攻击[J]. 密码学报, 2021, 8 (6): 974- 988.
	DONG B Y, LIU T, CUI Y L, et al. Improved quantum collision attack on 5-round Grøstl-512[J]. Journal of Cryptologic Research, 2021, 8 (6): 974- 988.
16	NI B Y, DONG X Y, JIA K T, et al. （Quantum） Collision attacks on reduced Simpira v2[J]. IACR Transactions on Symmetric Cryptology, 2021, 2012 (2): 222- 248.
17	AKINORI H , YU S. Quantum collision attacks on reduced SHA-256 and SHA-512[C]//Proc. of the Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, 2021: 616–646.
18	SCHROTTENCOHER A, STEVENS M. Simplified MITM modeling for permutations: new (quantum) attacks[C]//Proc. of the Advances in Cryptology - CRYPTO 2022-42nd Annual International Cryptology Conference, 2022: 717–747.
19	IVAN D. A design principle for hash functions[C]//Proc. of the Advances in Cryptology-CRYPTO’89, 9th Annual International Cryptology Conference, 1989: 416–427.
20	MERKLE R C. A certified digital signature[C]//Proc. of the Advances in Cryptology - CRYPTO’89, 9th Annual International Cryptology Conference, 1898: 218–238.
21	RIVEST R L. The MD5 message digest algorithm: RIPEMD-1281 [S]. Reston: Internet Activities Board, 1992.
22	National Institute of Standards and Technology. Secure Hash standard: FIPS-1801[S]. Gaithers-burg: Federal Information Processing Standard, 1995.
23	National Institute of Standards and Technology. Secure hash standard (SHS): FIPS 180-2[S]. Gaithers-burg: Federal Information Processing Standard, 2002.
24	PAULO S L, BARRETO M, RIJMEN V. Encyclopedia of cryptography and security [M]. New York: Springer, 2011: 1384–1385.
25	JOUX A. Multicollisions in iterated hash functions application to cascaded constructions[C]//Proc. of the Advances in Cryptology – CRYPTO 2004, 24th Annual International CryptologyConference, 2004: 306–316.
26	KELSEY J, KOHNO T. Herding hash functions and the nostradamus attack[C]// Proc. of the Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Crypto graphic Techniques, 2006: 183–200.
27	BENEDIKT B J, FISCHLIN M, HUPPERT M. Nostradamus goes quantum[C]//Proc. of the Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, 2022: 583–613.
28	DONG X Y, LI S, PHUONG P, et al. Quantum attacks on hash constructions with low quantum random access memory[C]// Proc. of the Advances in Cryptology - ASIACRYPT 2023, 29th Annual International Conference on the Theory and Applications of Crypto graphic Techniques, 2023: 3–33.
29	陈士伟, 金晨辉. 对强化MD结构杂凑函数的一个新的“牧群”攻击[J]. 电子与信息学报, 2010, 32 (8): 1953- 1955.
	CHEN S W, JIN C H. A new herding atlack on hash functions with strengthening Merke – Damgard （MD） construction[J]. Journal of Electronics & Information Technology, 2010, 32 (8): 1953- 1955.
30	BAO Z Z, GUO J, LI S, et al. Evaluating the security of merkle-damgard hash functions and combiners in quantum settings[C]// Proc. of the Network and System Security - 16th International Conference, 2022: 687–711.
31	GROVER L K. A fast quantum mechanical Algorithm for database search[C]//Proc. of the 28th Annual ACM Symposium on Theory of Computing, 1996: 212–219.
32	BRASSARD G, HOYER P, MOSCA M, et al. Quantum amplitude amplification and estimation[J]. Quantum Computation and Quantum Information, 2002, 305, 53- 74.
33	BELLARE M, KOHNO T. Hash function balance and its impact on birthday attacks[C]//Proc. of the Advances in Cryptology – EUROCRYPT 2004, 10th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2004: 401–418.

New quantum herding attack on hash with MD construction

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 33

Related Articles 1

Recommended Articles

Metrics

Comments