Keccak Under Quantum Scrutiny: Is SHA-3 Still Secure?

Author: Denis Avetisyan

A new analysis reveals the quantum resources needed to crack reduced-round versions of the Keccak hash function, suggesting current cryptographic standards remain robust against near-term quantum attacks.

Researchers assessed the feasibility of a quantum preimage attack on 3-round Keccak using Grover’s algorithm and Qiskit Modeling, demonstrating impractical qubit and gate requirements for a successful breach.

Despite theoretical advances suggesting quantum algorithms pose a threat to symmetric cryptography, realizing practical quantum attacks remains a significant challenge. This is explored in ‘Quantum Resource Analysis of Low-Round Keccak/SHA-3 Preimage Attack: From Classical 2^57.8 to Quantum 2^28.9 using Qiskit Modeling’, which rigorously assesses the feasibility of a Grover-based attack on the Keccak-256 hash function. Our analysis reveals that, while offering a substantial theoretical speedup, implementing this attack requires an impractical number of qubits and gates-orders of magnitude beyond current and foreseeable quantum hardware capabilities. Does this hardware-conscious approach represent a necessary paradigm shift in evaluating the true security of cryptographic algorithms in the quantum era?

The Evolving Landscape of Cryptographic Hashing

SHA-3 represents a pivotal advancement in cryptographic hashing, widely implemented across diverse security protocols and data storage systems. Built upon the Keccak permutation – a complex, non-linear transformation of data – SHA-3 offers a robust alternative to the older SHA-2 family and, crucially, avoids the structural similarities to MD5 and SHA-1 that led to their vulnerabilities. This design philosophy provides a strengthened defense against collision attacks and ensures data integrity in applications ranging from digital signatures and message authentication to blockchain technologies and secure data transmission. Its adoption as a NIST standard in 2015 cemented SHA-3’s position as a cornerstone of modern cybersecurity, providing a vital layer of protection for digital information worldwide.

The looming development of quantum computing presents a fundamental challenge to the established foundations of data security, particularly for algorithms like SHA-3 that underpin much of modern digital infrastructure. While currently reliant on the computational difficulty of problems for classical computers, these algorithms become vulnerable as quantum computers leverage principles of quantum mechanics to solve those same problems with exponentially increased speed. Specifically, algorithms that once required centuries to crack could potentially be compromised in mere hours or days, threatening the confidentiality and integrity of sensitive information. This shift necessitates proactive investigation into quantum-resistant cryptography and a comprehensive understanding of how existing algorithms, such as SHA-3, fare against emerging quantum attack vectors, ensuring a smooth transition to a post-quantum security landscape.

The looming potential of quantum computation compels a rigorous assessment of contemporary cryptographic algorithms, including the Keccak permutation at the heart of SHA-3. A primary concern centers on preimage attacks, where an attacker attempts to find an input that produces a given hash output; quantum algorithms, notably those leveraging Grover’s algorithm, could theoretically accelerate such attacks. However, a recent study comprehensively evaluates Keccak’s resistance, quantifying the computational resources – specifically, the number of quantum gates and qubits – required to mount a successful preimage attack. The findings demonstrate that, with current and near-future quantum technology, executing such an attack remains computationally infeasible, requiring resources far exceeding projected capabilities. This assessment provides crucial insight into the continued viability of SHA-3 as a secure hashing algorithm in the face of the evolving quantum threat landscape, though continued monitoring and adaptation will be essential as quantum computing advances.

Deconstructing the Keccak Permutation

The Keccak permutation operates on a state comprised of $5 \times 5 \times w$ bits, where $w$ is typically 64, 128, 160, 256, or 512. This state is repeatedly transformed through five core operations applied in sequence. These operations – Theta, Rho, Pi, Chi, and Iota – are applied iteratively for a defined number of rounds, typically between 24 and 72, depending on the security level and desired output length. Theta introduces XOR operations based on the state’s bit patterns, while Rho performs bitwise rotations. Pi rearranges the bits through a series of lane and bit permutations. Chi is the sole non-linear function, implemented using Boolean XOR and AND operations. Finally, Iota introduces round-dependent constants to the state via XOR, providing asymmetry and preventing attacks. The consistent application of these five operations constitutes a complete round of the Keccak permutation.

The Chi function within the Keccak permutation is responsible for the algorithm’s non-linearity, and represents the most computationally intensive step. It operates on the state’s bits by applying bitwise XOR operations conditioned on other bits, and is exclusively implemented using Toffoli gates – a reversible, controlled-controlled-NOT gate. Specifically, for each bit in the state, Chi computes $x_i \oplus (x_{i+1} \oplus x_{i+2}) \oplus (x_{i+1} \oplus x_{i+2} \oplus x_{i+3})$ where all indices are modulo 5. The use of only Toffoli gates ensures reversibility, a crucial property for certain cryptographic applications and for constructing a quantum oracle to simulate the Keccak permutation.

The Theta and Pi functions within the Keccak permutation are linear transformations designed to ensure rapid diffusion and permutation of the state’s bits. Theta operates on the state’s columns, XORing column and row parity, while Pi performs a bit-level permutation based on a fixed pattern. These functions, when combined, propagate changes across the entire state with high efficiency. Complementing these, the Rho function introduces bit rotation within each lane of the state array, further mixing the data and contributing to the overall non-linearity of the permutation. These three functions, though linear individually, collectively contribute significantly to the security and mixing properties of the Keccak algorithm.

The construction of a quantum oracle capable of simulating the Keccak permutation relies directly on a detailed understanding of its constituent functions – Theta, Rho, Pi, Chi, and Iota. Our specific oracle implementation requires the precise replication of Keccak’s logic using reversible quantum gates, specifically Toffoli gates. The current design utilizes 9,600 Toffoli gates to accurately represent the Keccak permutation, necessitating a clear mapping between each function’s bitwise operations and their equivalent quantum gate network. Accurate simulation demands a precise gate count and arrangement, directly informed by the decomposition of each function within the Keccak algorithm.

Simulating Keccak and Applying Grover’s Algorithm

A quantum oracle simulating the 3-round Keccak permutation was constructed using the Qiskit software development kit. This oracle functions as a black box representing the cryptographic hash function targeted by the quantum attack. Specifically, the implementation models the Keccak-f permutation, a core component of the Keccak hash algorithm, over three rounds of processing. The oracle’s input consists of a 160-bit state, and its output is the resulting state after the three rounds of Keccak-f application. This allows the oracle to be queried by Grover’s algorithm to evaluate potential preimage candidates without explicitly calculating the full hash function each time, effectively encapsulating the cryptographic transformation within the quantum circuit.

The circuit depth of the quantum oracle is a critical factor influencing the overall complexity of any quantum preimage attack utilizing it. A deeper oracle circuit necessitates a correspondingly greater number of quantum gates in the subsequent attack algorithm, such as Grover’s algorithm, to achieve a successful result. This is because each layer of the oracle contributes to the total gate count and, consequently, to the quantum resources – qubit count and circuit depth – required for the entire attack. Increasing the oracle’s depth directly translates to a more computationally expensive attack, potentially exceeding the capabilities of current and near-term quantum hardware. Therefore, minimizing the oracle’s circuit depth is a key optimization strategy for reducing the resources needed to mount a practical quantum attack.

Grover’s algorithm was utilized to perform a preimage attack against the implemented Keccak-based quantum oracle. This search algorithm iteratively amplifies the probability of measuring the correct input that yields a specified hash output. The algorithm operates by applying a series of quantum operations, including a diffusion operator and the quantum oracle itself, to a superposition of all possible inputs. Each iteration effectively rotates the state vector closer to the solution, reducing the search space from $2^n$ to approximately $\sqrt{2^n}$ for an $n$-bit input, representing a quadratic speedup over classical brute-force methods. However, the number of iterations, and therefore the total circuit complexity, is directly linked to the size of the input and the accuracy required for the preimage identification.

Quantum resource estimation for a preimage attack against the implemented Keccak permutation, utilizing Grover’s algorithm, determined a computational cost of approximately $7.47 \times 10^{13}$ 2-qubit gates. This figure represents the total number of 2-qubit gate operations required to achieve a statistical likelihood of success for the attack. The estimation accounts for the oracle implementation’s complexity and the inherent requirements of Grover’s algorithm for searching the input space. This substantial gate count indicates that, with current quantum hardware capabilities, mounting a successful attack against the implemented cryptographic function remains computationally infeasible and highlights the significant challenges in scaling quantum algorithms to address practical cryptographic problems.

The Persistence of Security in a Quantum Age

The realization of practical quantum computation hinges critically on overcoming the inherent fragility of quantum information. Quantum systems are exceptionally susceptible to environmental noise, leading to errors that rapidly corrupt computations. Consequently, quantum error correction stands as a foundational requirement, not merely an optimization, for building fault-tolerant quantum computers. This process doesn’t eliminate errors, but rather distributes the information of a single logical qubit across multiple physical qubits, enabling the detection and correction of errors without collapsing the quantum state. Without robust error correction, even the most sophisticated quantum algorithms would quickly become unreliable, rendering complex computations – including those vital for breaking modern cryptographic schemes – impossible. The development of effective error correction codes, therefore, isn’t simply a technical challenge; it is the key to unlocking the full potential of quantum computing and ensuring its secure application in fields ranging from materials science to secure communication.

Quantum information is notoriously fragile, susceptible to errors from both environmental disturbances – known as decoherence – and imperfections in the quantum gates that manipulate it. To combat this, researchers employ quantum error correction, and a promising approach involves the Surface Code. This code doesn’t attempt to prevent errors, but rather distributes the information of a single logical qubit across multiple physical qubits arranged in a two-dimensional grid. By cleverly encoding information in this manner, errors affecting individual physical qubits can be detected and corrected without collapsing the quantum state. This redundancy effectively shields the encoded quantum information, dramatically increasing its stability and allowing for more complex and sustained computations. The Surface Code’s relatively simple structure also makes it a leading candidate for practical implementation in future quantum computers, offering a pathway towards fault-tolerant quantum computing.

A recent analysis indicates that mounting a quantum attack against the Keccak-256 cryptographic hash function, even after only three rounds of processing, demands substantial computational resources. The study reveals that such an attack would necessitate approximately 3.2 million qubits. This figure is not simply a count of theoretical qubits, but reflects the practical reality of quantum error correction; the analysis assumes a ratio of 1,000 physical qubits are required to reliably encode a single, error-corrected logical qubit. This high qubit count underscores the considerable engineering challenges inherent in building a quantum computer powerful enough to compromise even a relatively small number of rounds within this widely-used cryptographic standard, highlighting the current and near-future security of Keccak-256 against quantum threats.

The computational demands placed upon a quantum attack targeting Keccak-256 are staggering, extending far beyond the capabilities of currently conceivable quantum technology. Analysis indicates that successfully breaking Keccak-256 via quantum means would necessitate a runtime exceeding 2,367 years, a figure derived from the required scale of qubits and the anticipated operational speeds. This prolonged timeframe isn’t merely a matter of technological advancement; it represents a fundamental barrier, effectively safeguarding the cryptographic hash function against quantum decryption for the foreseeable future. Consequently, Keccak-256 demonstrates a robust level of near-term resilience, ensuring its continued viability as a secure hashing algorithm in a world increasingly conscious of quantum threats.

The study of cryptographic systems, much like observing any complex structure, reveals inherent limitations and eventual decay. While advancements in quantum computing, specifically Grover’s algorithm, offer potential acceleration in attacking hash functions like Keccak, the practical realities-the exponential growth in required qubits and gate complexity-introduce constraints. As the article demonstrates with its analysis of 3-round Keccak, these improvements age faster than they can be understood. This echoes Max Planck’s observation: “A new scientific truth does not triumph by convincing its opponents and making them understand, but rather because its opponents die, and a new generation grows up that is familiar with it.” The lifecycle of cryptographic security isn’t about achieving invulnerability, but about extending the period before a system succumbs to the inevitable forces of computational advancement.

What Lies Ahead?

The demonstration of a quantum attack-however impractical with current architectures-on reduced-round Keccak serves as a predictable milestone. Any improvement ages faster than expected; the theoretical reduction from 2^57.8 to 2^28.9 steps is less a victory and more an acknowledgement of entropy’s inevitable advance. The limitations revealed aren’t necessarily inherent to the algorithm itself, but rather to the medium of implementation-the exponential cost in qubits and gate complexity. The pursuit of fault-tolerant quantum computation remains the critical, and perpetually receding, horizon.

Future work will undoubtedly focus on resource optimization – squeezing more attack power from fewer qubits. However, the more interesting trajectory lies in examining the boundaries of reversible computing. The inherent structure of Keccak, designed with reversibility in mind, presents both opportunities and constraints for quantum attack vectors. Understanding these constraints is crucial; rollback is a journey back along the arrow of time, and some paths are more efficiently blocked than others.

Ultimately, the security of cryptographic hashes isn’t a static property. It’s a dynamic relationship between algorithmic complexity and the evolving capabilities of both classical and quantum computation. The current findings suggest a reprieve, not a resolution. The question isn’t whether SHA-3 will eventually succumb, but how gracefully it will age.

Original article: https://arxiv.org/pdf/2512.14759.pdf

Contact the author: https://www.linkedin.com/in/avetisyan/

The Evolving Landscape of Cryptographic Hashing

Deconstructing the Keccak Permutation

Simulating Keccak and Applying Grover’s Algorithm

The Persistence of Security in a Quantum Age

What Lies Ahead?

See also: