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

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

系统工程与电子技术 ›› 2025, Vol. 47 ›› Issue (9): 3099-3108.doi: 10.12305/j.issn.1001-506X.2025.09.32

• 通信与网络 • 上一篇

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

李雪莲¹^,*, 李程龙¹(), 裴焘²^,³, 高军涛⁴

1. 西安电子科技大学数学与统计学院，陕西西安 710071
2. 武汉船舶通信研究所，湖北武汉 430205
3. 武汉大学国家网络安全学院，湖北武汉 430072
4. 西安电子科技大学通信工程学院，陕西西安 710071

收稿日期:2024-05-17 出版日期:2025-09-25 发布日期:2025-09-16
通讯作者: 李雪莲 E-mail:18047288473@163.com
作者简介:李程龙（2000—），男，硕士研究生，主要研究方向为量子密码分析
裴　涛（1987—），男，高级工程师，硕士，主要研究方向为流密码
高军涛（1979—），男，副教授，博士，主要研究方向为伪随机序列、流密码
基金资助:
陕西省重点研发计划(2021ZDLGY06-04); 广西密码学与信息安全重点实验室基金(GCIS201802); 西安电子科技大学交叉培育项目（21103240011）资助课题

New quantum herding attack on hash with MD construction

Xuelian LI¹^,*, Chenglong LI¹(), Tao PEI²^,³, Juntao GAO⁴

1. School of Mathematics and Statistics，Xidian University，Xi’an 710071，China
2. Wuhan Maritime Communication Research Institute，Wuhan 430205，China
3. School of Cyber Science and Engineering，Wuhan University，Wuhan 430072，China
4. School of Telecommunications Engineering，Xidian University，Xi’an 710071，China

Received:2024-05-17 Online:2025-09-25 Published:2025-09-16
Contact: Xuelian LI E-mail:18047288473@163.com

摘要/Abstract

摘要：

针对 MD（Merkle-Damgard）哈希结构在量子环境下的安全性问题，提出BHT（Brassard-H?yer-Tapp）量子算法、 CNS（Chailloux-Naya Plasencia-Schrottenloher）量子算法分别与经典新牧群攻击结合的思路，构建两种攻击模式。首先，使用BHT量子算法构造 “可变长钻石树”，增加可连接节点的数量，提升攻击效率。在一定条件下，当恢复消息长度相同时，攻击复杂度更低。然后，以安全哈希算法（secure hash algorithm，SHA）-256为例，给出具体攻击复杂度。接着，提出CNS量子算法与新牧群攻击结合的攻击模式，攻击过程中不再需要量子随机存取储存器（quantum random access memory，qRAM），降低攻击实现成本。攻击模式可以在一定范围内选择消息长度进行恢复，优于现存方案中不可选择的情况。

关键词: 哈希函数, 牧群攻击, BHT(Brassard-H?yer-Tapp)算法, CNS(Chailloux-Naya Plasencia –Schrottenloher)算法

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

中图分类号:

TN 918.11

李雪莲, 李程龙, 裴焘, 高军涛. 面向MD哈希结构的量子新牧群攻击[J]. 系统工程与电子技术, 2025, 47(9): 3099-3108.

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.

图/表 6

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

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

New quantum herding attack on hash with MD construction

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 33

相关文章 1

编辑推荐

Metrics

本文评价