up:: Breaking Today’s Cryptography MOC

Grover’s Algorithm

Grover’s algorithm is a quantum search algorithm that finds a target inside an unstructured space of N possibilities in roughly the square root of N steps, instead of the up-to-N steps a classical brute-force search needs. That square-root speedup is called quadratic, and in cryptography it matters for one specific thing: it makes brute-forcing a symmetric key or a hash preimage faster. It halves the effective strength of ciphers like AES and hash functions like SHA-256, which you fix by using a longer key or a bigger hash. It’s the manageable half of the quantum threat, and the opposite of Shor’s algorithm, which fully breaks public-key cryptography.

The short version:

• Grover’s algorithm gives a quadratic (square-root) speedup on unstructured search: about √N steps where a classical search takes N.
• Against symmetric cryptography, that halves the effective security bits. An n-bit key drops to roughly n/2 bits of brute-force resistance.
• The fix is size, so AES-128 (which drops to about 64 bits) moves up to AES-256 (which stays near 128 bits and is safe). SHA-256 stays useful for most work, and SHA-384 covers high-assurance and national-security use.
• Grover weakens, it does not break. Symmetric ciphers and hashes survive the quantum era with bigger parameters. Nothing needs a brand-new algorithm family the way public-key does.
• The common “double your key size” advice is roughly right, and it’s actually conservative, because Grover’s speedup doesn’t parallelize well and running it at cryptographic scale demands enormous, deep quantum circuits.

An everyday way to picture it

Imagine a combination padlock with a million possible settings, and no clever shortcut, so the only way in is to try combinations. A classical attacker works through them one at a time and might try all million. Grover’s algorithm lets a quantum attacker home in on the right setting in about a thousand tries, the square root of a million. Now scale that up. A 128-bit key is 2^128 possible settings; Grover cuts the work to about 2^64. That’s still an astronomically large number, and it’s exactly why the answer is to reach for a bigger lock rather than to throw the lock away.

What is Grover’s algorithm?

Grover’s algorithm is a quantum algorithm for unstructured search, published by Lov Grover at Bell Labs in 1996. Unstructured means there’s no order or pattern to exploit, so classically you can only check candidates one by one. Given a way to recognize the right answer when you see it (an “oracle”), Grover finds a marked item among N candidates using about √N oracle queries, versus the O(N) a classical exhaustive search needs. That square-root relationship is the whole story, and it’s provably close to the best any quantum algorithm can do for pure unstructured search.

The speedup is real and general, and it’s also modest compared to the quantum attack people usually have in mind. Grover doesn’t solve the underlying math of a cipher or find hidden structure. It just makes blind guessing faster. That’s why its cryptographic effect is a reduction in security margin rather than a collapse.

Source: Lov K. Grover, “A fast quantum mechanical algorithm for database search,” 1996, arXiv:quant-ph/9605043.

How does Grover’s algorithm work?

At a high level, Grover’s algorithm amplifies the probability of measuring the correct answer through a repeated two-part cycle, a process called amplitude amplification. The steps:

1. Prepare a superposition across all N candidate states at once, so every possible answer is present with a small equal probability.
2. Apply the oracle, a quantum operation that recognizes the correct state and marks it by flipping its phase (an “inversion”).
3. Apply the diffusion operator, an “inversion about the mean” that nudges probability toward the marked state and away from the rest.
4. Repeat steps 2 and 3 about (π/4)√N times, each cycle growing the correct answer’s probability a little more.
5. Measure, and with high probability you read out the marked answer.

Two practical constraints fall out of this:

1. The algorithm is inherently sequential, since each iteration builds on the last, which limits how much you can speed it up by throwing more hardware at it.
2. It needs an oracle that can check a candidate, which for a cipher means running the encryption inside a quantum circuit, so the “queries” are far from free.

Both of these make a real-world Grover attack much heavier than the clean √N count suggests.

Source: Grover, arXiv:quant-ph/9605043.

Why does Grover’s algorithm only halve symmetric security?

The halving comes straight out of the square root. A symmetric key with n bits has 2^n possible values. A classical brute-force search takes on the order of 2^n tries. Grover reduces that to about √(2^n) = 2^(n/2) tries. Cutting the exponent in half is the same as cutting the “bits of security” in half. So an n-bit key offers roughly n/2 bits of brute-force resistance against an idealized Grover attacker, and an n-bit hash output offers roughly n/2 bits of preimage resistance.

NIST states this directly: Grover’s search “proffers a quadratic speedup on unstructured search problems,” and while that “does not render cryptographic technologies obsolete, it can have the effect of requiring larger key sizes, even in the symmetric key case.” Their remedy is simple: “doubling the key size will be sufficient to preserve security.” NIST also notes that an exponential speedup for search is provably impossible, which is why symmetric algorithms and hash functions are expected to remain usable in a quantum era.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

Is AES quantum-safe against Grover’s algorithm?

AES is safe against Grover as long as the key is big enough, and for AES that means 256-bit. Walking the numbers:

1. AES-128 has 128 bits of classical security. Under an idealized Grover attack that drops to about 64 bits of effective strength, which is below the comfort line for long-term protection. This is the one symmetric primitive worth moving off of.
2. AES-256 has 256 bits classically and about 128 bits against Grover, which stays comfortably safe. This is the recommended standard for post-quantum margin.

That’s why the U.S. National Security Agency’s CNSA 2.0 suite mandates AES-256 for national-security systems and drops the smaller AES key sizes. The structure of AES stays intact, and the entire response is a parameter change: use the 256-bit key.

Sources: NIST, NISTIR 8105, csrc.nist.gov/pubs/ir/8105/final; NSA, “Announcing the Commercial National Security Algorithm Suite 2.0,” September 2022, nsa.gov and CNSA 2.0 algorithm specification.

What about hash functions like SHA-256 and SHA-384?

Hash functions absorb Grover the same way, by sizing the output. Grover speeds up preimage search, the job of finding an input that hashes to a given digest, and halves the preimage resistance of an n-bit hash to about n/2 bits. So SHA-256 keeps roughly 128 bits of preimage resistance against a quantum attacker, which stays strong for the vast majority of uses. For high-assurance and long-horizon integrity, larger outputs give more room: SHA-384 and SHA-512 keep about 192 and 256 bits. NIST’s guidance for hash functions under quantum pressure is simply “larger output needed,” never a replacement.

Collision resistance is a separate question, and it’s the one people most often get wrong. Classically, finding a collision already takes only about 2^(n/2) work because of the birthday effect, so a 256-bit hash gives about 128-bit collision resistance even today. Quantum collision-finding algorithms exist, but in realistic cost models that account for memory and hardware they offer little or no practical advantage over the classical birthday attack. The upshot is that keeping SHA-256 or SHA-3 is fine for most work, and moving to SHA-384 is the high-assurance choice, which is exactly what CNSA 2.0 requires for national-security systems.

Sources: NIST, NISTIR 8105, Table 1, csrc.nist.gov/pubs/ir/8105/final; NSA, CNSA 2.0.

Why isn’t Grover’s algorithm the catastrophic one?

Because Grover and Shor’s algorithm deliver completely different kinds of speedup, and that difference decides everything about the migration. The contrast:

1. Shor gives an exponential speedup against the specific math behind public-key cryptography (integer factorization and discrete logarithms). Rather than shrinking a key’s strength, it dissolves the hard problem those algorithms rest on entirely, so RSA, ECC, and Diffie-Hellman fall completely and have to be replaced by new post-quantum algorithms.
2. Grover gives a quadratic speedup against blind search, which touches every cipher and hash equally but only halves the margin. Symmetric cryptography and hashing keep working, upsized.

So the honest headline runs deeper than “quantum breaks encryption.” Quantum shatters the public-key half through Shor and merely dents the symmetric half through Grover. That asymmetry is why the transition is overwhelmingly a public-key migration, and why symmetric primitives are part of the mitigation instead of the exposure.

Source: NIST, NISTIR 8105 (public-key algorithms fall; symmetric algorithms need larger key sizes), csrc.nist.gov/pubs/ir/8105/final.

Is the “double your key size” rule actually right?

Yes, and it errs on the safe side for defenders. As a rule of thumb, doubling the key length restores the security bits that Grover’s square root takes away, and NIST endorses it as sufficient. Two facts make the true picture even more comfortable than that rule implies:

1. Grover barely parallelizes. The √N speedup is fundamentally serial. Splitting the search across M quantum machines only gives each one a √(N/M) share, so a thousand machines buy you about a 31x speedup rather than a thousandfold one. A classical brute-force search parallelizes cleanly; Grover does not, which erodes much of its edge in practice.
2. The circuits are enormous and deep. NIST limits attack cost by a maximum circuit depth (MAXDEPTH), motivated by “the difficulty of running extremely long serial computations.” Under that limit, breaking AES-128 costs on the order of 2^170 / MAXDEPTH quantum gates, and NIST concludes the reference primitives “provide substantially more quantum security than a naïve analysis might suggest.” Detailed resource estimates for running Grover against AES confirm the qubit counts and circuit depths are staggering.

So the “double it” heuristic is the conservative planning line. NIST itself notes the halving assumption “may be overly conservative, as quantum computing hardware will likely be more expensive to build than classical hardware.” Doubling gives you a wide, defensible margin.

Sources: NIST, “Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process,” December 2016, csrc.nist.gov; Grassl, Langenberg, Roetteler & Steinwandt, “Applying Grover’s algorithm to AES: quantum resource estimates,” 2016, arXiv:1512.04965; NIST, NISTIR 8105, csrc.nist.gov/pubs/ir/8105/final.

What is the quantum impact on each primitive?

Primitive	Classical security	Quantum attack	Effective post-quantum strength	What to do
AES-128	128-bit	Grover	~64-bit (idealized)	Move to AES-256
AES-256	256-bit	Grover	~128-bit	Keep, it’s safe
SHA-256	128-bit preimage	Grover	~128-bit (preimage), fine for most	Keep; use SHA-384 for high assurance
SHA-384 / SHA-512	192 / 256-bit preimage	Grover	~192 / 256-bit	Keep, high-assurance choice
RSA, ECC, DH	varies	Shor	Broken	Replace with post-quantum algorithms

The table makes the split obvious. Everything Grover touches survives with a bigger parameter. Everything Shor touches has to be replaced.

Has faster search forced bigger keys before?

Yes, and recently enough to be a live lesson rather than ancient history. The Data Encryption Standard (DES) shipped in the 1970s with a 56-bit key. As classical computing got cheaper, brute-forcing that key went from theoretical to routine. In July 1998, the Electronic Frontier Foundation’s purpose-built “Deep Crack” machine won RSA Security’s DES Challenge II-2 by recovering a DES key through exhaustive search in about 56 hours. The response wasn’t a new kind of cryptography. It was a bigger key space, delivered by AES (standardized as FIPS 197 in 2001) with 128, 192, and 256-bit options.

Grover’s algorithm is the same shape of problem one layer out. Faster search pressures short keys, and the field answers with longer ones. The DES story is why AES was built with a 256-bit option in the first place, and that option is exactly what carries AES safely into the quantum era.

Sources: Electronic Frontier Foundation, “Cracking DES” / RSA DES Challenge II-2, 1998, as recounted in Simon Singh, The Code Book, 1999; NIST, “Advanced Encryption Standard (AES),” FIPS 197, 2001, csrc.nist.gov/pubs/fips/197/final.

Common misconceptions

• “Grover breaks AES the way Shor breaks RSA.” No. Grover only halves brute-force resistance, which a bigger key restores. Shor dissolves the math public-key rests on, so those algorithms have to be replaced outright.
• “AES is quantum-broken, so we need a post-quantum cipher.” No. There’s no new symmetric family required. AES-256 has about 128 bits of strength against Grover and stays safe.
• “A quantum computer that breaks RSA-2048 also cracks AES-256.” No. Those are different attacks with wildly different costs. A machine able to run Shor against RSA is nowhere near able to run Grover against AES-256 at scale.
• “Grover makes SHA-256 unsafe.” No. SHA-256 keeps roughly 128-bit preimage resistance under Grover, which stays strong for most uses. SHA-384 is the high-assurance upgrade, driven by policy margin rather than a break.
• “You can just run Grover on a thousand quantum computers to break AES-256 fast.” No. Grover’s speedup is serial and parallelizes poorly, so a thousand machines give roughly a 31x gain, not a thousandfold one.
• “Grover halves every cipher’s security equally, so all symmetric crypto is at equal risk.” Mostly, with one caveat. Certain legacy ciphers with special algebraic structure can fall to other quantum attacks faster than Grover, so the clean halving is the rule for standard modern primitives, and unusual constructions deserve their own review.

Questions people ask

Does Grover’s algorithm break AES? No. It halves AES’s brute-force resistance, so AES-128 drops to about 64 bits (weak) and AES-256 drops to about 128 bits (safe). Standardizing on AES-256 is the entire fix, and CNSA 2.0 already requires it for national-security systems.

Do I have to replace my symmetric encryption for the quantum transition? No new algorithm family is needed. The work is a parameter change: prefer AES-256 for anything with a long protection lifetime, and phase out under-sized keys and obsolete ciphers. That’s very different from the public-key side, which does require replacement.

Is SHA-256 still safe against quantum computers? For most purposes, yes. Grover leaves SHA-256 with about 128-bit preimage resistance, and its collision resistance is governed by the classical birthday bound, which quantum attacks don’t meaningfully beat in realistic cost models. SHA-384 is the choice where you want extra margin or must meet CNSA 2.0.

Why do people say “just double the key size”? Because Grover’s square-root speedup cuts the security bits in half, and doubling the key length puts them back. NIST endorses doubling as sufficient, and notes it’s likely conservative given how expensive quantum hardware will be.

How is Grover different from Shor? Grover is a quadratic speedup on blind search that dents symmetric cryptography and hashes. Shor is an exponential speedup on factoring and discrete logs that fully breaks public-key cryptography. Grover means bigger keys; Shor means new algorithms.

Has anyone run Grover against a real cipher yet? Not at cryptographic scale, and it isn’t close. Running Grover against AES needs a large, fault-tolerant quantum computer executing very deep circuits, well beyond today’s noisy hardware. Published resource estimates show the required qubit counts and circuit depths are enormous.

Does Grover threaten Harvest Now, Decrypt Later? Only weakly, and only for data protected by under-sized symmetric keys. Data encrypted with AES-256 stays safe against Grover, so HNDL risk is driven overwhelmingly by the public-key layer that Shor breaks, not by the symmetric layer.

Which of my systems should I actually worry about for Grover? Anything relying on 64-bit or 128-bit symmetric strength for long-lived confidentiality, plus legacy ciphers like 3DES and low-entropy secrets or tokens. Modern AES-256 and appropriately sized hashes already carry the margin they need.

---

Everything here is the map, given freely. When your team needs this turned into a cryptographic inventory and a dated plan for your own estate, that’s what an alignment briefing is for.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.