Lesson 23: Hash Preimage Attacks with Grover's Algorithm¶
23.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Define preimage, second-preimage and collision resistance and give their classical security levels.
- Construct a Grover oracle for a hash preimage search.
- Compute quantum security levels for hash functions and symmetric ciphers.
- Compare Grover and BHT collision search and explain why BHT is rarely practical.
- State and justify the "double the key/output length" rule and its limitations.
23.2 Cryptographic Hash Functions¶
Definition. A cryptographic hash function \(H:\{0,1\}^{*}\to\{0,1\}^{m}\) maps arbitrary-length input to an \(m\)-bit digest, and should satisfy:
| Property | Requirement | Classical cost |
|---|---|---|
| Preimage resistance | given \(y\), hard to find \(x\) with \(H(x)=y\) | \(2^{m}\) |
| Second-preimage resistance | given \(x_1\), hard to find \(x_2\ne x_1\) with \(H(x_2)=H(x_1)\) | \(2^{m}\) |
| Collision resistance | hard to find any \(x_1\ne x_2\) with \(H(x_1)=H(x_2)\) | \(2^{m/2}\) (birthday) |
The \(2^{m/2}\) birthday bound is why SHA-256 offers "128-bit collision resistance" and why digest lengths are chosen at twice the desired security level even classically.
Where hashes are used: digital signatures, password storage, blockchain proof-of-work, message authentication (HMAC), commitment schemes, key derivation.
23.3 Grover Preimage Attack¶
Framing it as unstructured search¶
Given a target digest \(y\), define
Searching over \(x\in\{0,1\}^{n}\) (an \(n\)-bit input space) is exactly Grover's unstructured search with \(N = 2^n\).
Effective security is halved: an \(m\)-bit hash gives \(m/2\) bits of quantum preimage security.
Building the oracle¶
|x> (n qubits) --[ H_circuit ]--*--[ H_circuit^-1 ]-- (uncomputed)
|
|0> (m qubits) --[ digest ]--|-------------------
|
|-> ancilla -------------------[X]------------------ <- phase kickback
Concretely:
- Compute the digest reversibly: \(|x\rangle|0^m\rangle \to |x\rangle|H(x)\rangle\).
- Compare with the target \(y\): apply \(X\) gates on the digest bits where \(y_j = 0\), then a multi-controlled \(Z\) (or a multi-controlled \(X\) onto the \(|-\rangle\) ancilla), then undo the \(X\) gates. This flips the phase precisely when \(H(x) = y\).
- Uncompute the digest by running the hash circuit in reverse, restoring \(|x\rangle|0^m\rangle\).
Uncomputation is mandatory. A leftover digest register stays entangled with \(|x\rangle\) and destroys the interference the diffusion operator depends on (L11 §5).
Cost. The oracle costs two full hash evaluations (compute + uncompute) plus the comparator. Reversible SHA-256 circuits have been estimated at \(\approx 5\times10^{5}\) Toffoli gates each.
23.4 Quantum Security Levels¶
| Primitive | Classical security | Grover security | Verdict |
|---|---|---|---|
| SHA-256 preimage | 256 bits | 128 bits | safe |
| SHA-256 collision | 128 bits | 128 bits (BHT: 85) | safe |
| SHA-1 preimage | 160 bits | 80 bits | already broken classically for collisions |
| SHA3-512 preimage | 512 bits | 256 bits | very safe |
| AES-128 key search | 128 bits | 64 bits | deprecated for post-quantum |
| AES-256 key search | 256 bits | 128 bits | recommended |
| 3DES (112-bit) | 112 bits | 56 bits | broken |
NIST post-quantum security categories (used to grade PQC candidates):
| Category | "At least as hard as..." |
|---|---|
| 1 | AES-128 key search (Grover) |
| 2 | SHA-256 collision search |
| 3 | AES-192 key search |
| 4 | SHA-384 collision search |
| 5 | AES-256 key search |
23.5 Collision Search: Grover vs BHT¶
The BHT algorithm (Brassard–Høyer–Tapp, 1997)¶
- Classically compute and store \(H(x_i)\) for \(k\) random inputs — a sorted table.
- Use Grover to search the remaining \(2^m - k\) inputs for one whose digest is in the table. The "marked" fraction is \(k/2^m\), so Grover needs \(O(\sqrt{2^m/k})\) queries.
- Total cost \(\approx k + \sqrt{2^m/k}\), minimised at \(k = 2^{m/3}\), giving
For SHA-256: \(2^{85}\) instead of \(2^{128}\).
Why BHT is not a practical threat¶
The memory requirement is fatal. \(2^{85}\) entries of 32 bytes is
Total world data storage is on the order of \(10^{2}\) zettabytes (\(10^{23}\) bytes) — BHT needs about \(10^{4}\) times that, in quantum-random-access memory, which does not exist even in prototype form.
The parallel-hardware comparison. Bernstein (2009) showed that when you account for the cost of memory access (which grows with the square root of memory size in any physically realisable 2-D layout), classical parallel rho-based collision search with the same hardware budget matches or beats BHT. The practical consensus:
Collision resistance is NOT effectively halved by quantum computers. Only preimage resistance is. Digest lengths chosen for classical collision resistance remain adequate.
Summary of the real threat model¶
| Attack | Classical | Quantum (realistic) |
|---|---|---|
| Preimage on \(m\)-bit hash | \(2^m\) | \(2^{m/2}\) (Grover) — genuine halving |
| Collision on \(m\)-bit hash | \(2^{m/2}\) | \(\approx2^{m/2}\) — no practical gain |
| \(k\)-bit symmetric key | \(2^k\) | \(2^{k/2}\) (Grover) — genuine halving |
| RSA / ECC | sub-exponential | polynomial (Shor) — catastrophic |
23.6 Solved Problems¶
Problem 1 — Grover iterations and runtime for a SHA-256 preimage¶
Compute the number of Grover iterations, total gate count and runtime for a SHA-256 preimage attack, assuming \(10^{9}\) logical gates per second and \(5\times10^{5}\) Toffoli gates per hash evaluation.
Solution.
Iterations. \(N = 2^{256}\), \(M=1\):
Gates. Each iteration = 2 hash evaluations + diffusion:
Runtime.
Comparison. The age of the universe is \(1.4\times10^{10}\) years. This attack would take \(6\times10^{17}\) times longer.
Problem 2 — Bitcoin proof-of-work under Grover¶
Bitcoin mining searches for a nonce such that \(\mathrm{SHA256}^2(\text{block}) < T\), where the target \(T\) makes the success probability about \(2^{-76}\) per attempt. Compare classical and Grover mining.
Solution.
Classical. Expected attempts \(= 2^{76} = 7.6\times10^{22}\). The Bitcoin network computes \(\approx 6\times10^{20}\) hashes/second, so a block takes
Grover. The search space per block is \(2^{76}\) effectively, so
At \(10^{6}\) gates per iteration and \(10^{9}\) gates/s:
A quantum miner would be catastrophically slower than existing ASICs, which perform \(\sim10^{14}\) hashes/second each at negligible energy per hash.
Three structural reasons Grover does not threaten Bitcoin:
- Grover is inherently sequential. Its iterations cannot be parallelised beyond a \(\sqrt P\) gain, whereas classical mining parallelises perfectly (\(P\) machines give \(P\times\) speed).
- Logical gate speed is \(\sim10^{6}\) times slower than an ASIC hash pipeline, because of error-correction cycles.
- Difficulty adjusts. Even a quantum advantage would simply raise the difficulty.
The real quantum threat to Bitcoin is Shor breaking ECDSA signatures — exposing coins whose public keys are revealed on-chain — not Grover breaking the proof-of-work.
Problem 3 — Choosing a hash length for a 30-year secret¶
*A document must remain secure until 2060. Assume large fault-tolerant quantum computers exist by
- What digest length gives at least 128-bit post-quantum preimage security, and what symmetric key length?*
Solution.
Hash. Grover halves preimage security:
Symmetric key.
Public key. Neither doubling nor any key-size increase helps against Shor. Must migrate to ML-KEM-1024 (key encapsulation) and ML-DSA-87 or SLH-DSA (signatures) — see L25.
Complete 2060-safe profile:
| Function | Choice |
|---|---|
| Symmetric encryption | AES-256-GCM |
| Hash | SHA-384 or SHA3-384 |
| Key exchange | ML-KEM-1024, ideally hybridised with X25519 |
| Signatures | ML-DSA-87 or SLH-DSA-SHA2-256s |
Hybrid mode (classical + post-quantum combined) is the current best practice: it is secure if either component holds, protecting against both quantum attacks and undiscovered flaws in the new lattice schemes.
Problem 4 — Second preimage vs collision cost, worked¶
For a 128-bit hash, compute classical and quantum costs for (a) preimage, (b) collision by birthday, (c) collision by BHT. State the memory needed in each case.
Solution.
(a) Preimage.
(b) Collision, classical birthday.
Naive memory \(2^{64}\times16\) bytes \(= 3\times10^{20}\) bytes — but Pollard's rho / van Oorschot–Wiener achieves the same time with \(O(1)\) memory using distinguished points, and parallelises perfectly.
(c) Collision, BHT.
but requires \(2^{42.7}\) entries of qRAM:
of quantum-accessible memory with \(O(1)\) access — hardware that does not exist.
Verdict table.
| Attack | Time | Memory | Feasible? |
|---|---|---|---|
| Classical preimage | \(3.4\times10^{38}\) | \(O(1)\) | no |
| Grover preimage | \(1.4\times10^{19}\) | \(O(1)\) | borderline, far future |
| Classical collision (rho) | \(1.8\times10^{19}\) | \(O(1)\) | borderline — this is the real threat |
| BHT collision | \(7\times10^{12}\) | 110 TB qRAM | no |
The lesson: for a 128-bit hash, the classical birthday attack is already the binding constraint. Quantum computing changes little. This is why MD5 (128-bit) is deprecated for collision resistance today, for entirely classical reasons.
Problem 5 — Designing a Grover attack on a password hash¶
A system stores \(\mathrm{SHA256}(\text{password})\). Passwords are 8 characters from a 95-character printable set. Compare classical and Grover attacks, and evaluate the effect of adding a key-stretching function with \(10^{5}\) iterations (PBKDF2).
Solution.
Search space.
Classical. Expected \(\frac{N}{2} = 3.3\times10^{15}\) hashes. A GPU rig at \(10^{10}\) SHA-256/s:
Grover.
At \(10^{6}\) gates per iteration and \(10^{9}\) logical gates/s:
Only about 5× faster than the classical GPU rig, despite the quadratic asymptotic advantage — because logical quantum gates are so much slower than classical ones. The constant factors dominate at these scales.
With PBKDF2 (\(10^{5}\) iterations). Every hash evaluation becomes \(10^{5}\) times more expensive, for both attackers:
Conclusions.
- Key stretching is effective against both classical and quantum attackers — it multiplies both costs by the same factor.
- Grover's quadratic gain is real but modest here; the classical constant-factor advantage of ASICs/GPUs largely offsets it.
- The best defence is entropy. Moving to a 16-character password gives \(N = 95^{16} = 2^{105}\), so Grover needs \(2^{52.5}\) iterations — over \(10^{9}\) years at the assumed rate.
Practical recommendation: long passphrases + a memory-hard KDF (Argon2id, scrypt). Memory-hard functions are particularly good anti-quantum defences, since qRAM is the scarcest quantum resource.
23.7 Practice Problems¶
- Grover security level of SHA-512 preimage? [Ans: 256 bits]
- Iterations to find a SHA-1 (160-bit) preimage with Grover? [Ans: \(\approx8.6\times10^{23}\)]
- Why must the hash circuit be uncomputed inside the Grover oracle?
- BHT query count and memory for a 192-bit hash. [Ans: \(2^{64}\) queries, \(\sim2^{64}\) qRAM entries]
- A 6-character password from 62 symbols: Grover iterations? [Ans: \(N=5.7\times10^{10}\), \(k\approx1.9\times10^5\)]
- Explain why doubling the key length restores security against Grover but not against Shor.
- Which NIST security category does AES-192 define? [Ans: category 3]
23.8 Summary¶
- Hash properties: preimage and second preimage cost \(2^m\) classically; collisions cost \(2^{m/2}\) (birthday).
- A Grover preimage attack needs \(O(2^{m/2})\) queries — the oracle computes the hash, compares with the target via a multi-controlled phase flip, then uncomputes.
- Preimage security is genuinely halved by Grover: SHA-256 → 128 bits, AES-128 → 64 bits, AES-256 → 128 bits.
- Collision security is not meaningfully reduced in practice: BHT's \(2^{m/3}\) needs \(2^{m/3}\) qRAM, which is infeasible; classical parallel rho matches it at equal hardware cost.
- Constant factors matter: logical quantum gates are \(\sim10^{6}\) times slower than ASIC operations, so Grover's asymptotic edge often evaporates at practical sizes (Bitcoin mining, password cracking).
- The rule: double symmetric keys and digest lengths (AES-256, SHA-384); replace public-key algorithms entirely.
Next lesson: L24 — The HHL algorithm for linear systems.
Practise now: unit2-algorithms-lab.html → Crypto Security Calculator: enter key/digest
lengths and gate speeds to compute classical and Grover attack times side by side.