Quantum Attack Reduces Keccak/SHA-3 Preimage Complexity to 2²⁸․⁹, Threatening Security

The security of cryptographic hash functions remains a crucial area of research, and scientists continually assess their resilience against both classical and quantum attacks. Ramin Rezvani Gilkolaei, from Guilan University, and colleagues demonstrate a detailed analysis of a quantum attack on the Keccak/SHA-3 hash function, specifically examining a preimage attack accelerated using Grover’s algorithm. Their work reveals that while a theoretical speed-up exists, reducing the classical computational effort from 2^57.8 to 2^28.9, the practical demands of building a quantum computer capable of executing this attack are immense. The team’s analysis, utilising Qiskit-based circuit synthesis, establishes that implementing this attack requires a prohibitively large number of qubits and gates, alongside an impractical execution time, effectively confirming that SHA-3 remains secure against foreseeable quantum computer attacks and highlighting the importance of hardware-aware complexity analysis in modern cryptanalysis.

Although the theoretical quantum speed-up is significant, the practical implementation proves exceptionally challenging, rendering attacks infeasible in terms of both resources and runtime. Using circuit synthesis within the Qiskit framework, the team determined that a 3-round Keccak quantum oracle requires 9,600 Toffoli gates, with additional gates needed for reversibility, and 3,200 logical qubits, translating to 3.2 million physical qubits. A full Grover search necessitates 7.47 × 10 13 two-qubit gates, and the estimated runtime ranges from 43 days to over 2,300 years, depending on machine characteristics and error rates. These findings conclusively demonstrate that a quantum attack on 3-round Keccak-256 is currently infeasible, not only due to the immense physical qubit requirements but also due to the substantial circuit depth and the accumulation of errors.

Quantum Attack Infeasibility on Keccak Hash

This work presents a comprehensive analysis of the feasibility of quantum attacks on the Keccak hash function, the basis of SHA-3. The central claim is that, despite the theoretical quadratic speedup offered by Grover’s algorithm, attacking Keccak with a quantum computer is currently and foreseeably infeasible. This is not due to limitations of the algorithm itself, but due to the immense practical challenges of building and operating a quantum computer capable of handling the required scale and complexity. Key findings include an estimated gate count of 7.47 × 10 13 gates for a preimage attack on a 3-round Keccak instance using Grover’s algorithm.

The analysis reveals a need for 3.2 million physical qubits, exceeding the capabilities of current or near-future quantum computers. The research emphasizes the importance of hardware-aware complexity analysis in cryptanalysis, revealing that the theoretical speed-up offered by Grover’s Algorithm is overshadowed by significant engineering overhead. The work confirms that SHA-3 remains secure against foreseeable quantum computer attacks targeting preimage vulnerabilities, and provides a rigorous methodology for assessing the feasibility of quantum cryptanalysis.

Quantum Keccak-256 Attack Needs 3200 Qubits

This work presents a detailed hardware analysis of accelerating a classical attack on the Keccak-256 cryptographic hash function using Grover’s Algorithm. Researchers focused on a 3-round Keccak-256 preimage attack, building upon previous classical cryptanalysis, and investigated the potential for quantum speed-up. The team meticulously constructed a quantum circuit model of the 3-round Keccak oracle using the Qiskit framework, enabling a precise estimation of resource requirements. Results demonstrate that implementing this quantum attack necessitates 3,200 logical qubits, further translating to 3.2 million physical qubits.

Keccak-256 Grover Attack, Hardware Limitations Revealed

This research presents a detailed hardware-conscious analysis of accelerating a classical preimage attack on the Keccak-256 hash function, using Grover’s Algorithm. The team demonstrates that while Grover’s Algorithm offers a theoretical quadratic speed-up, the practical implementation demands are currently prohibitive. Specifically, a three-round Keccak oracle requires approximately 9,600 Toffoli gates and a staggering 7.47 × 10 13 two-qubit gates for a complete Grover search. The researchers emphasize that the overhead associated with implementing Grover’s Algorithm dominates the potential benefits, rendering the attack infeasible for any foreseeable computer. Consequently, the security of SHA-3 is not currently threatened by quantum preimage attacks on reduced-round variants.