SHA-256 exhibits strong resistance to collision attacks, a property attributed to its intricate design. Recently, Li et al. proposed a novel semi-free-start (SFS) collision attack targeting 39-step SHA-256, advancing prior methodologies. Despite these advancements, increasing the number of attackable rounds for SHA-256 remains challenging. This study demonstrates the conversion of a semi-free-start collision into a full collision attack through a specialized quantum technique. Using a quantum approach, our method targets 39-round SHA-256, leveraging frameworks that transform SFS collisions into two-block collisions, thereby establishing a new benchmark for collision attacks.The quantum analysis method proposed in this paper achieves a circuit depth of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$T_F \le 3.4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>T</mi> <mi>F</mi> </msub> <mo>≤</mo> <mn>3.4</mn> </mrow> </math></EquationSource> </InlineEquation> and a circuit width of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$S_F \le 2.4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>S</mi> <mi>F</mi> </msub> <mo>≤</mo> <mn>2.4</mn> </mrow> </math></EquationSource> </InlineEquation>. With a quantum computer of size S, this attack achieves a collision within time <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$t = 2^{124}/\sqrt{S}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <msup> <mn>2</mn> <mn>124</mn> </msup> <mo stretchy="false">/</mo> <msqrt> <mi>S</mi> </msqrt> </mrow> </math></EquationSource> </InlineEquation>. The attack is effective when the quantum computer size satisfies <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$2.4 \le S < 2^8$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2.4</mn> <mo>≤</mo> <mi>S</mi> <mo><</mo> <msup> <mn>2</mn> <mn>8</mn> </msup> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, this study investigates the conditions required to transform a semi-free-start collision into a two-block collision. It also examines the conversion of semi-free-start or free-start collision attacks into two-block collisions across various hash functions. The results indicate that the unique properties of quantum computing establish new benchmarks for collision attacks on hash functions.

Quantum collision attacks on reduced SHA-256.

期刊论文
发表日期：

2025年12月23日

查看全文

Bao-Min Zhou,
Hong-Wei Sun,
Xue Zhang,
Ke-Jia Zhang,
Long Zhang

摘要

SHA-256 exhibits strong resistance to collision attacks, a property attributed to its intricate design. Recently, Li et al. proposed a novel semi-free-start (SFS) collision attack targeting 39-step SHA-256, advancing prior methodologies. Despite these advancements, increasing the number of attackable rounds for SHA-256 remains challenging. This study demonstrates the conversion of a semi-free-start collision into a full collision attack through a specialized quantum technique. Using a quantum approach, our method targets 39-round SHA-256, leveraging frameworks that transform SFS collisions into two-block collisions, thereby establishing a new benchmark for collision attacks.

The quantum analysis method proposed in this paper achieves a circuit depth of $T_F \le 3.4$ $T_{F} \leq 3.4$ and a circuit width of $S_F \le 2.4$ $S_{F} \leq 2.4$ . With a quantum computer of size S, this attack achieves a collision within time $t = 2^{124}/\sqrt{S}$ $t = 2^{124} / \sqrt{S}$ . The attack is effective when the quantum computer size satisfies $2.4 \le S < 2^8$ $2.4 \leq S < 2^{8}$ . Furthermore, this study investigates the conditions required to transform a semi-free-start collision into a two-block collision. It also examines the conversion of semi-free-start or free-start collision attacks into two-block collisions across various hash functions. The results indicate that the unique properties of quantum computing establish new benchmarks for collision attacks on hash functions.