up:: The Threat MOC

Grover on AES

Grover on AES is the specific question of what Grover’s algorithm does to the Advanced Encryption Standard, and the answer is the reassuring half of the quantum threat: Grover halves the effective key strength, so AES-128 drops to about 64 bits of brute-force resistance while AES-256 drops to about 128 bits and stays comfortably safe. AES is not broken by a quantum computer the way RSA is broken by Shor’s. The entire response is a parameter change, standardize on the 256-bit key, and NIST assesses even that as conservative, because Grover parallelizes poorly and running it against AES at cryptographic scale demands staggeringly deep quantum circuits. This is why the symmetric layer is part of the mitigation and the public-key layer is the exposure.

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

The short version:

• Grover’s algorithm searches an N-key space in about √N steps instead of up to N, which halves the effective security bits of any symmetric cipher.
• AES-128 has 128 bits of classical strength, which Grover reduces to about 64 bits of effective search, below the line for long-term protection, so it is the one AES size worth moving off.
• AES-256 has 256 bits classically and retains about 128 bits against Grover, which is astronomically out of reach, so it is the conservative quantum-safe answer.
• NIST calls Grover’s halving assumption likely conservative, because the search is inherently serial (it parallelizes poorly) and needs enormous, deep circuits, so real AES-256 security is even higher than the naive n/2 count.
• CNSA 2.0 already mandates AES-256 for U.S. national-security systems and drops the smaller key sizes, which is the clearest signpost that AES survives the quantum era with a bigger key.
• Grover is the manageable dent; Shor’s is the catastrophe. Confusing the two is the most common quantum-crypto error.

An everyday way to picture it

Imagine a combination lock with a number of settings so vast that trying them one at a time would outlast the universe, which is roughly what a 128-bit key is: about 2^128 possible values. A classical attacker has no shortcut and must grind through them. Grover’s algorithm is a quantum trick that lets an attacker home in on the right setting in about the square root of the number of tries, so 2^128 work becomes about 2^64. That sounds alarming until you notice the answer is not to throw the lock away but to reach for a bigger one. Double the key to 256 bits, and the square root lands back at about 2^128, which is once again past any machine that could ever be built. The whole story of Grover on AES is that a bigger lock defeats a faster search.

Does Grover’s algorithm break AES?

Grover’s algorithm does not break AES; it weakens it by a fixed, well-understood amount that a larger key restores. The mechanism is a square-root speedup on unstructured search. A symmetric key with n bits has 2^n possible values, a classical brute-force search takes on the order of 2^n tries, and 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 AES key offers roughly n/2 bits of brute-force resistance against an idealized Grover attacker.

That halving is the beginning and end of Grover’s effect on AES. It does not exploit any structure in the cipher, it does not recover the key from a mathematical shortcut, and it does not touch the design of AES at all. It only makes blind key-guessing faster, which is why the fix is size rather than a new algorithm. This is the opposite of what Shor’s algorithm does to RSA and elliptic-curve cryptography, where it solves the exact hard problem those systems rest on and the algorithms stop working entirely.

Source: NIST, NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

Why does AES-128 drop to about 64 bits?

AES-128 drops to about 64 bits because 128 halved is 64, straight from the square-root speedup. AES-128 has 128 bits of classical security, meaning a classical brute-force attack costs on the order of 2^128 operations, which is safe by an enormous margin today. Under an idealized Grover attack, that effective cost falls to about 2^64 operations, and 64 bits of symmetric strength is below the comfort line for anything that must stay secret for a long time.

The practical read is calibrated. A 64-bit effective search is still a very large number, and Grover’s serial, circuit-heavy nature (covered below) means an actual attack is far harder than the clean 2^64 suggests, so AES-128 is not a five-alarm emergency. It is the one AES key size worth planning to retire for long-lived protection, in the same way the field retired short keys before. For anything with a multi-year confidentiality lifetime, the conservative move is to standardize on AES-256 rather than lean on AES-128’s post-quantum margin.

Source: NIST, NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

Why is AES-256 the conservative answer?

AES-256 is the conservative answer because 256 halved is 128, and 128 bits of security is past the reach of any machine that could plausibly exist. AES-256 has 256 bits of classical strength, so an idealized Grover attack leaves about 128 bits of effective resistance, which is the same security level that AES-128 provides against a classical attacker, a level the entire industry treats as safe. Moving from AES-128 to AES-256 is a parameter change, not a migration to a new algorithm family, because the AES structure is identical and only the key length and round count differ.

Comparing the AES key sizes under Grover makes the choice obvious:

AES key size	Classical security	Effective strength under Grover (idealized)	Verdict
AES-128	128-bit	~64-bit	Retire for long-lived protection
AES-192	192-bit	~96-bit	Safe, but AES-256 is the cleaner target
AES-256	256-bit	~128-bit	The conservative quantum-safe choice

The effective numbers come from halving the classical strength under an idealized Grover attack, and they are deliberately pessimistic, so the real margin is wider than the table shows. AES-256’s roughly 128 bits is a wide moat that no foreseeable quantum machine threatens, which is exactly why it is the standard answer for the symmetric side of the transition.

Source: NIST, NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

Why does NIST view Grover as less threatening than it sounds?

NIST views Grover as far less threatening than a naive n/2 read because two properties of a real Grover attack make it much harder to run than the clean square-root count implies. The halving is a worst-case idealization that ignores the actual cost of executing the search on hardware.

1. Grover barely parallelizes. The √N speedup is fundamentally serial, so splitting the search across M quantum machines gives each one only a √(N/M) share of the work. A thousand machines buy roughly a 31-fold speedup rather than a thousandfold one. Classical brute force splits cleanly across machines, and Grover does not, which erases much of its apparent edge in any real deployment.
2. The circuits are enormous and deep. NIST bounds attack cost with 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 naive analysis suggests.

NIST states the planning consequence directly: doubling the key size is sufficient to preserve security, and the halving assumption may be overly conservative, since quantum hardware will likely be more expensive to build than classical hardware. Detailed peer-reviewed resource estimates for running Grover against AES confirm the picture, with qubit counts and circuit depths so large that a real attack sits far beyond the idealized 2^(n/2).

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

What does CNSA 2.0 require for AES?

CNSA 2.0, the NSA suite that sets post-quantum requirements for U.S. National Security Systems, mandates AES-256 and drops the smaller AES key sizes for national-security work. It treats AES the way the analysis above says to: not as a broken primitive needing replacement, but as a surviving one needing its largest key. That is a sharp contrast with how the same suite handles public-key cryptography, where it removes RSA and ECDH outright in favor of ML-KEM and ML-DSA.

That split is strong public evidence for exactly how the quantum threat is shaped. The most conservative cryptographic authority in the U.S. government keeps AES in place and simply requires the 256-bit key, while it retires the classical public-key algorithms entirely. When the people who protect classified traffic decide AES survives with a bigger key while RSA does not survive at all, that is the clearest available confirmation that Grover dents the symmetric layer and Shor breaks the public-key layer.

Source: NSA, “Announcing the Commercial National Security Algorithm Suite 2.0,” CSA U/OO/194427-22, September 2022, nsa.gov.

How does Grover on AES compare to Shor on RSA?

Grover on AES and Shor on RSA are the two halves of the quantum threat, and they could hardly be more different in what they do and what they cost you. Setting them side by side is the fastest way to see why the transition is overwhelmingly a public-key project:

	Grover on AES	Shor on RSA / ECC
Speedup	Quadratic (square-root)	Exponential
Effect on the algorithm	Halves effective key strength	Solves the underlying hard problem outright
Verdict	Weakened, survives with a bigger key	Broken, must be replaced
The fix	Move to AES-256	Replace with ML-KEM, ML-DSA
Relative cost of the attack	Enormous serial circuits, parallelizes poorly	Far cheaper in logical qubits than a same-scale Grover run

The counterintuitive line worth holding onto is the last one. A quantum computer able to run Shor against RSA-2048 is nowhere near able to run Grover against AES-256 at scale, because the AES search demands vastly deeper circuits. So the arrival of a machine that breaks RSA does not simultaneously break AES-256, which is another reason the symmetric layer is treated as part of the mitigation rather than the exposure. The full contrast lives in Grover’s Algorithm and Shor’s Algorithm.

Source: NIST, NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

Does Grover on AES change harvest-now-decrypt-later?

Grover on AES barely moves the harvest-now-decrypt-later picture, because HNDL is a public-key problem and AES-256 stays safe against Grover. Recorded traffic becomes readable later when a quantum computer breaks the key-establishment that set up the session, which is ECDH, DH, or RSA key transport, all of which fall to Shor. The bulk data itself, encrypted under AES-256, does not open just because Grover exists.

The one narrow exception is long-lived data still protected by AES-128 or by legacy symmetric constructions. Where a dataset must stay confidential for many years and is encrypted under a 128-bit key, Grover’s reduction to about 64 bits of effective strength is worth taking seriously as part of the harvesting calculation, and the fix is the same parameter change: re-encrypt under AES-256. Certain legacy ciphers with special algebraic structure can also fall to other quantum attacks faster than Grover, so old symmetric gear deserves its own review, but modern AES-256 carries the margin it needs.

Source: NIST, NISTIR 8105, April 2016, csrc.nist.gov/pubs/ir/8105/final.

Common misconceptions

• “Grover breaks AES the way Shor breaks RSA.” No. Grover only halves brute-force resistance, which a bigger key restores, so AES-256 stays safe. Shor dissolves the math public-key rests on, so RSA and ECC have to be replaced outright.
• “AES is quantum-broken, so we need a post-quantum cipher.” No. There is no new symmetric family to migrate to. AES-256 keeps about 128 bits of strength against Grover and remains the standard.
• “Grover halves AES-256 to a dangerous level.” No. AES-256 retains about 128 bits under Grover, the same level AES-128 gives against classical attackers, which the whole industry treats as safe.
• “A quantum computer that breaks RSA-2048 also cracks AES-256.” No. Those are different attacks with wildly different costs, and a machine that can run Shor against RSA is nowhere near able to run Grover against AES-256 at scale.
• “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 31-fold gain, not a thousandfold one.
• “AES-128 is fine forever because 64 bits is still a big number.” For long-lived confidentiality it is the size to retire, because 64 bits of effective strength is below the durable-protection line. AES-256 is the conservative default for anything that must stay secret for years.

Questions people ask

Does Grover’s algorithm break AES-256? No. Grover halves AES-256’s effective strength to about 128 bits, which stays comfortably safe, and NIST assesses even that halving as conservative because the attack parallelizes poorly and needs enormous circuits. AES-256 is the quantum-safe symmetric standard.

Do I have to replace AES 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 AES-128 and obsolete ciphers. That is very different from the public-key side, which does require replacement.

Why is AES-256 recommended over AES-128 for post-quantum? Because Grover halves each, so AES-128 drops to about 64 bits (below the durable line) and AES-256 drops to about 128 bits (safe). Standardizing on AES-256 is the entire symmetric fix, and CNSA 2.0 already requires it for national-security systems.

How much does Grover actually speed up an AES key search? It gives a square-root speedup in theory, turning a 2^n search into about 2^(n/2). In practice the speedup is smaller than that ideal, because Grover is serial and parallelizes poorly, and running it against AES needs extraordinarily deep fault-tolerant circuits.

Has anyone run Grover against AES? Not at cryptographic scale, and it is not close. Published resource estimates show the qubit counts and circuit depths required are enormous, well beyond today’s noisy hardware, which is part of why NIST treats AES-256 as safe.

Is AES-192 quantum-safe? Yes. AES-192 retains about 96 bits against Grover, which is safe, though AES-256 is the cleaner conservative target and the one CNSA 2.0 mandates. For a fresh standardization decision, AES-256 is the simplest defensible choice.

What about hashes like SHA-256 under Grover? Hashes absorb Grover the same way, by sizing the output, so SHA-256 keeps roughly 128 bits of preimage resistance and stays fine for most work, with SHA-384 as the high-assurance step. The pattern is identical to AES: a bigger parameter, not a new family.

Go deeper

The algorithm and its contrast: Grover’s Algorithm (the full square-root-search treatment) · Shor’s Algorithm (the exponential attack that actually breaks public-key) · the threat pillar

The cipher and its cousins: AES (Advanced Encryption Standard) · AES-128 · AES-192 · AES-256 · FIPS 197 · Symmetric-Key Cryptography

The rest of the symmetric-and-hash survival story: SHA-256 · SHA-384 · NSA CNSA 2.0 · Cryptographically Relevant Quantum Computer (CRQC)

---

Everything here is the map, given freely. When your team needs its symmetric estate sorted into what survives on a bigger key and what has to move, that’s what an alignment briefing is for.

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