Grover’s Algorithm vs SHA-256: What’s Actually at Risk

Lov Grover introduced his quantum search algorithm in 1996, two years after Peter Shor unveiled his algorithm for factoring and discrete logarithms. Both algorithms threaten cryptography. They do so in different ways, and the difference is what most coverage gets wrong.

What Is Grover’s Algorithm

All public-key cryptography that depends on factoring or discrete logarithms falls to Shor. That includes RSA, ECDSA, Diffie-Hellman, and ElGamal. That’s the headline threat to the modern internet.

Grover is a quantum search algorithm. It speeds up brute-force searching across an unstructured set of possibilities. The speedup is quadratic. For an unstructured search across N items, classical algorithms take N steps on average, and Grover takes √N. Applied to hash functions like SHA-256, that quadratic speedup halves the effective security level.

A classical preimage attack against SHA-256 requires 2^256 operations, which is infeasible by any margin anyone has invented. Grover reduces the work to 2^128 operations. Still infeasible by any margin anyone has invented.

That’s the executive summary. SHA-256 stays standing.

Why the Math Is Reassuring

Start with the scale of 2^128. The number is far beyond what any engineered system can perform on human timescales. Bitcoin’s entire global mining network does about 7 × 10^20 SHA-256 hashes per second, or about 2^70 per second. At that aggregate rate, a classical system would need around 15 billion years to perform 2^128 SHA-256 evaluations, comparable to the age of the universe.

A practical Grover attack involves far more than a one-to-one mapping between quantum operations and hash evaluations. Each iteration needs a fault-tolerant quantum circuit for SHA-256 plus error correction overhead. The real-world cost ends up higher than the bare number suggests.

The quadratic speedup is the entire substance of Grover’s threat to SHA-256. NIST built that math into its post-quantum design assumptions. A 256-bit hash provides about 128 bits of preimage resistance against a Grover-equipped attacker. NIST treats that level of security as enough margin for most general-purpose applications.

The same arithmetic applies to symmetric ciphers like AES. AES-256 drops to 2^128 effective security under Grover, which is still comfortable. AES-128 falls to a Grover-attack workload around 2^64, with real-world quantum cost factors that complicate the headline number but don’t move the conclusion. Systems designed to stay secure for decades routinely prefer AES-256.

Where Grover Actually Bites

Some corners of the Bitcoin protocol have halved security levels worth taking seriously.

Bitcoin addresses don’t store SHA-256 alone. Legacy P2PKH and SegWit P2WPKH addresses store HASH160, which is RIPEMD-160 applied to SHA-256 of the public key. That gives 160-bit classical preimage security against finding a public key that hashes to a given address. Grover would reduce that effective preimage security to about 80 bits.

80-bit security isn’t on the side of comfort. It’s below the threshold NIST considers acceptable for new systems. A quantum computer large enough to run Grover at 2^80 work is still science fiction, but a less distant science fiction than the 2^128 machine needed to break SHA-256 directly.

If an attacker can generate a public/private key pair whose HASH160 matches a target address, they can sign transactions that drain the funds at that address. That’s the attack. Whether it’s practical depends on quantum hardware that doesn’t exist yet, and on whether attackers find it cheaper than picking other targets.

The Bitcoin Mining Question

Bitcoin mining is essentially a giant Grover-suitable problem. You’re searching for a nonce that produces a block hash below a target. Classical miners do this by brute force.

A quantum miner running Grover would, in theory, find valid nonces with quadratic speedup. In practice, that theoretical advantage runs into problems that have kept anyone from building a quantum miner.

Grover’s algorithm is inherently sequential at the level of each search instance. You can’t parallelize a single Grover run the way classical miners parallelize hashing. A quantum miner would need to run very fast Grover instances to compete with classical ASICs, which are designed for the kind of massively parallel brute force that classical mining rewards.

The other problem is gate speed. Current quantum hardware operates at megahertz timescales. Bitcoin ASICs do gigahash-per-second per chip. That’s a gap of several orders of magnitude before the Grover speedup is even factored in. Quadratic speedup of a slow process is still a slow process.

There’s an additional wrinkle. Bitcoin mining rewards the first miner to find a valid hash. Classical mining is structured around throughput. Even with Grover-style quadratic speedup, a quantum miner’s serial gate operations would lose the race to ASICs that can attempt billions of hashes per second in parallel. 

The quantum advantage requires a quantum computer both extremely large and extremely fast, capable of outpacing the global ASIC fleet. No such machine is on any near-term hardware roadmap.

Quantum mining analyses consistently find the same answer. Under realistic near-term assumptions, a quantum miner running Grover would lose to modern ASICs by orders of magnitude, and the gap only closes under hardware assumptions that no one currently knows how to build. The economic case isn’t there.

What About Collision Attacks

A different concern is finding collisions instead of preimages. The Brassard-Høyer-Tapp algorithm, published in 1997, theoretically provides cubic-root speedup for collision finding. Applied to SHA-256, that would reduce the workload from 2^128 (the classical birthday bound) to about 2^85.

2^85 is more plausible than 2^128. Plausible and feasible aren’t the same thing. The algorithm demands significant amounts of quantum memory, which is the kind of resource even harder to scale than qubit count. Daniel Bernstein and others have argued that BHT in its standard form isn’t a viable threat against SHA-256 once you account for the memory and price-performance picture honestly.

For Bitcoin, collision attacks on SHA-256 wouldn’t enable theft of coins. They could enable certain kinds of consensus mischief, like producing two different blocks with the same hash. The practical risk from this scenario is currently very low.

For comparison, classical collision attacks on weaker hashes like MD5 and SHA-1 have been demonstrated in published research, with practical impact on certificate forgery and other attack surfaces. SHA-256 has no such break, and a quantum-assisted attack reduces the security margin without crossing into the demonstrated territory.

What This All Adds up To

Grover’s algorithm is the smaller half of the quantum threat to Bitcoin. SHA-256 has plenty of margin to spare. HASH160’s 160-bit output drops to about 80-bit preimage security under Grover, which doesn’t leave a comfortable long-term margin. That’s why some quantum-resistance proposals for Bitcoin focus on retiring HASH160 addresses in favor of schemes that don’t bottleneck on a 160-bit hash.

There are paths forward. Bitcoin can adopt addresses that use full SHA-256 hashes, or signature schemes built on quantum-resistant primitives. None of those changes are imminent. The Bitcoin development conversation is currently occupied by Shor-related questions, which is fair, because Shor breaks things Grover doesn’t touch.

If you’re going to take one thing from any quantum-versus-Bitcoin discussion, take this. Shor breaks signatures. Grover halves hashes. Hashes that started at 256 bits keep a comfortable margin. Hashes that started at 160 bits lose much more of theirs. The fix is to use bigger hashes, which is exactly the path NIST and most cryptography standards are taking.