基于Grover量子搜索算法的MD5碰撞攻击模型

doi:10.3969/j.issn.1671-1122.2024.08.007

摘要/Abstract

摘要：

量子计算天然的并行性使其在密码学领域具有巨大潜力，而在信息安全领域，Hash函数的安全性至关重要。因此，后量子密码学概念的提出使得Hash函数在后量子时代的研究价值凸显。文章提出了一种基于Grover量子搜索算法的MD5碰撞攻击模型，运用模差分分析法，通过对输入的量子叠加态进行约束搜索以找到满足碰撞条件的目标态，再根据差分构造出与之相碰撞的消息。此外，文章探讨了量子搜索算法中的迭代过程及其关键操作，设计了相应的Oracle黑盒的量子线路，并对其进行性能分析，结果表明，与经典算法相比，该模型显著降低了攻击的计算复杂度，为后量子密码时期Hash函数的研究提供了新的思路和方法，也为防御此类攻击提供了有益参考。

关键词: 量子计算, 碰撞攻击, Grover量子搜索算法, MD5算法

Abstract:

Quantum computing’s inherent parallelism underscores its immense potential in cryptography and in information security, where Hash function security stands paramount. Consequently, the emergence of post-quantum cryptography underscores the importance of Hash functions research in this new era. This paoper proposed an MD5 collision attack model based on Grover’s quantum search algorithm. This model applied modular difference analysis to constrain input quantum superposition states. The goal was to seek the target state meeting collision criteria. Upon finding it, this paper constructed a colliding message based on the identified difference. Moreover, this paper delved into the iterative procedures and pivotal operations of quantum search algorithms. This paper also crafted tailored Oracle black box quantum circuits, and assessed the performance of these circuits to evaluate their effectiveness. Findings reveal that this model drastically cuts down on computational intricacies during attacks. It presents novel perspectives and approaches for the research of Hash functions in the post-quantum cryptography era. It also provides useful reference for defending against such attacks.

Key words: quantum computing, collision attack, Grover’s quantum search algorithm, MD5 algorithm

中图分类号:

TP309

张兴兰, 李登祥. 基于Grover量子搜索算法的MD5碰撞攻击模型[J]. 信息网络安全, 2024, 24(8): 1210-1219.

ZHANG Xinglan, LI Dengxiang. MD5 Collision Attack Model Based on Grover’s Quantum Search Algorithm[J]. Netinfo Security, 2024, 24(8): 1210-1219.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

表1

参考文献 29

[1]	BENIOFF P. The Computer as a Physical System: A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines[J]. Journal of Statistical Physics, 1980, 22(5): 563-591.
[2]	FEYNMAN R P. Simulating Physics with Computers[J]. International Journal of Theoretical Physics, 1982, 21(6): 467-488.
[3]	WEI Shijie, WANG Tao, RUAN Dong, et al. Quantum Computing[J]. Scientia Sinica (Informationis), 2017, 47(10): 1277-1299.
	魏世杰, 王涛, 阮东, 等. 量子算法的一些进展[J]. 中国科学:信息科学, 2017, 47(10): 1277-1299.
[4]	WANG Lina, TANG Chuan, TIAN Qianfei, et al. Analysis on the Development Strategies and Trends of Quantum Computing[J]. World Sci-Tech R & D, 2019, 41(6): 569-584.
	王立娜, 唐川, 田倩飞, 等. 全球量子计算发展态势分析[J]. 世界科技研究与发展, 2019, 41(6): 569-584.
[5]	CLERK A A, DEVORET M H, GIRVIN S M, et al. Introduction to Quantum Noise, Measurement, and Amplification[J]. Reviews of Modern Physics, 2010, 82(2): 1155-1208.
[6]	TACCHINO F, CHIESA A, CARRETTA S, et al. Quantum Computers as Universal Quantum Simulators: State-of-the-Art and Perspectives[EB/OL]. (2019-12-19)[2024-04-15]. https://onlinelibrary.wiley.com/doi/10.1002/qute.201900052.
[7]	MERMIN N D. Quantum Computer Science: An Introduction[M]. Cambridge: Cambridge University Press, 2007.
[8]	KRANTZ P, KJAERGAARD M, YAN F, et al. A Quantum Engineer’s Guide to Superconducting Qubits[EB/OL]. (2019-06-17)[2024-04-15]. https://pubs.aip.org/aip/apr/article/6/2/021318/570326/A-quantum-engineer-s-guide-to-superconducting.
[9]	JAMES D, KWIAT P, MUNRO W, et al. On the Measurement of Qubits[EB/OL]. (2001-03-21)[2024-04-15]. https://arxiv.org/pdf/quant-ph/0103121.
[10]	DEUTSCH D, JOZSA R. Rapid Solution of Problems by Quantum Computation[J]. Proceedings of the Royal Society A Mathematical and Physical Sciences, 1992, 439(1907): 553-558.
[11]	SHOR P W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring[C]// IEEE. Proceedings 35th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1994: 124-134.
[12]	GROVER L K. Quantum Mechanics Helps in Searching for a Needle in a Haystack[J]. Physical Review Letters, 1997, 79(2): 325-328.
[13]	HARROW A W, HASSIDIM A, LLOYD S. Quantum Algorithm for Linear Systems of Equations[EB/OL]. (2009-09-30)[2024-04-15]. https://arxiv.org/pdf/0811.3171.
[14]	LI Zhaokai, LIU Xiaomei, XU Nanyang, et al. Experimental Realization of a Quantum Support Vector Machine[EB/OL]. (2015-04-08)[2024-04-15]. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.114.140504.
[15]	LLOYD S, MOHSENI M, REBENTROST P. Quantum Principal Component Analysis[J]. Nature Physics, 2014, 10: 631-633.
[16]	OHZEKI M. Message-Passing Algorithm of Quantum Annealing with Nonstoquastic Hamiltonian[EB/OL]. (2019-01-24)[2024-04-15]. https://arxiv.org/pdf/1901.06901.
[17]	WU Hongjun. The Hash Function JH 1[EB/OL]. (2011-01-16)[2024-04-15]. https://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf.
[18]	BERNSTEIN D J, LANGE T. Post-Quantum Cryptography[J]. Nature, 2017, 549(7671): 188-194.
[19]	WANG Xiaoyun, YU Hongbo. How to Break MD5 and Other Hash Functions[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2005: 19-35.
[20]	ZHANG Yizhi, ZHAO Yi, TANG Xiaobin. MD5 Algorithm[J]. Computer Science, 2008, 35(7): 295-297.
	张裔智, 赵毅, 汤小斌. MD5算法研究[J]. 计算机科学, 2008, 35(7): 295-297.
[21]	BIHAM E, SHAMIR A. Differential Cryptanalysis of DES-Like Cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3-72.
[22]	DRAPER T G. Addition on a Quantum Computer[EB/OL]. (2000-08-07)[2024-04-15]. https://doi.org/10.48550/arXiv.quant-ph/0008033.
[23]	HASANIJAFARI S, PARSAMEHR S. Solving the Fourier Transform Issue Using Quantum Coherent States[J]. International Journal of Theoretical Physics, 2019, 58(8): 2407-2413.
[24]	LIU Xin, GUO Heng, SUN Rujun, et al. The Characteristic Analysis and Exascale Scalability Research of Large Scale Parallel Applications on Sunway Taihu Light Supercomputer[J]. Chinese Journal of Computers, 2018, 41(10): 2209-2220.
	刘鑫, 郭恒, 孙茹君, 等. “神威·太湖之光”计算机系统大规模应用特征分析与E级可扩展性研究[J]. 计算机学报, 2018, 41(10): 2209-2220.
[25]	ZHANG Xinglan, ZHANG Feng. Quantum Solving Euler’s Totient Function to Crack RSA[J]. Netinfo Security, 2023, 23(7): 1-8.
	张兴兰, 张丰. 量子求解欧拉函数破解RSA算法[J]. 信息网络安全, 2023, 23(7): 1-8.
[26]	ZHOU Lin, GUO Bing. Design of Improved TR Gate Cascade Quantum Comparator[J]. Computer Engineering and Applications, 2021, 57(19): 112-115. doi: 10.3778/j.issn.1002-8331.2009-0193
	周林, 郭兵. 改进TR门级联的量子比较器设计[J]. 计算机工程与应用, 2021, 57(19): 112-115. doi: 10.3778/j.issn.1002-8331.2009-0193
[27]	LI Haisheng, FAN Ping, XIA Haiying, et al. Efficient Quantum Arithmetic Operation Circuits for Quantum Image Processing[J]. Science China Physics, Mechanics & Astronomy, 2020, 63(8): 33-45.
[28]	KARZ J, LINDELL Y. Introduction to Modern Cryptography. 2nd ed[M]. Boca Raton: CRC Press, 2014.
[29]	BAO Zhenzhen, GUO Jian, LI Shun, et al. Evaluating the Security of Merkle-Damgård Hash Functions and Combiners in Quantum Settings[C]// Springer. International Conference on Network and System Security. Heidelberg: Springer, 2022: 687-711.

算法	时间复杂度	存储复杂度
文献[28]算法	$O\left( {{2}^{\frac{n}{2}}} \right)$	$O\left( 1 \right)$
文献[19]算法	$O\left( {{2}^{\sqrt{n}}} \right)$	$O\left( N \right)$
文献[29]算法	$O\left( {{2}^{\frac{n}{3}}} \right)$	$O\left( {{2}^{\frac{n}{3}}} \right)$
本文算法	$O\left( {{2}^{\frac{\sqrt{n}}{2}}} \right)$	$O\left( N \right)$