← Back to Blog Education

Grover's Algorithm: The Quantum Attack on AES and Why It Isn't as Scary as Shor's

9 min read

The One Paragraph Version

Grover's algorithm, published by Lov Grover in 1996, is a quantum search algorithm that speeds up brute force attacks on symmetric encryption by a quadratic factor. An AES-256 key, which would take 2^256 operations to crack classically, needs roughly 2^128 quantum operations under Grover. That is still astronomically large. AES-256 remains secure in a post-quantum world. AES-128, however, drops to a 2^64 effective security level against Grover, which is considered too weak for long-term protection. Grover is a real but manageable threat. Shor's algorithm, which breaks RSA and ECC entirely, is not.

What Grover's Algorithm Actually Does

Classical search over N items (for example, trying every possible 128-bit key against an AES ciphertext) takes O(N) operations on average. Grover's algorithm runs in O(sqrt(N)). This is called a quadratic speedup, because the attack cost changes from N to the square root of N.

The practical consequence: for any symmetric primitive with a k-bit key, Grover gives an attacker an effective security level of k/2 bits. AES-256 becomes 128-bit secure. AES-128 becomes 64-bit secure.

Why AES-256 Survives

A 128-bit effective security level is still well beyond the practical reach of any quantum computer. Running Grover on 2^128 operations would require a continuously operating fault-tolerant quantum computer for longer than the current age of the universe.

NIST made this explicit in its FIPS 203, 204, and 205 publications on August 13, 2024. Those standards specify security categories that map to symmetric key strengths (category 1 equals AES-128, category 3 equals AES-192, category 5 equals AES-256). NSA CNSA 2.0, published September 7, 2022, requires AES-256 for quantum-resistant symmetric encryption across National Security Systems.

Where Grover Actually Bites: Legacy Symmetric Crypto

The real victims of Grover are:

AES-128 used for long-term data protection. Effective 64-bit security is too weak.
Triple-DES (3DES) with 112-bit effective key. Already deprecated; Grover makes it laughable.
SHA-1 collisions. Hash function preimage attacks also benefit from Grover.
HMAC-SHA-1. Same story.

If your system still uses AES-128 for anything that needs to remain confidential for decades, you have a harvest-now-decrypt-later problem whose solution is upgrading to AES-256, not switching algorithms entirely.

Why Grover Is Not the Crisis

The reason cryptographers worry far more about Shor than about Grover:

Shor is exponential. Doubling the RSA key size barely slows Shor. Doubling the AES key size turns Grover's 2^128 into 2^256, which is pure arithmetic of impossibility.
Grover is provably optimal. Bennett, Bernstein, Brassard, and Vazirani proved in 1997 that you cannot do better than quadratic speedup for unstructured search. Shor, by contrast, exploits the structure of period finding, so there is nothing structural to save RSA or ECC.
Mitigations are trivial for symmetric. Use larger keys. AES-256, ChaCha20-Poly1305 (256-bit key), SHA-384 or SHA-512 for hashes, HMAC-SHA-256 or stronger.

Real-World Recommendations

Primitive	Classical Security	Post-Grover	Recommendation
AES-128	128 bits	64 bits	Upgrade for long-term data
AES-256	256 bits	128 bits	Keep
ChaCha20-Poly1305	256 bits	128 bits	Keep
SHA-256	128 bits (collision) / 256 (preimage)	64 / 128	Prefer SHA-384+ for long-term
SHA-3 (256)	Same as SHA-256	Same as SHA-256	Prefer SHA3-384 for long-term
HMAC-SHA-256	256 bits	128 bits	Keep; prefer SHA-384 for high-assurance

Practical Impact on Hybrid Post Quantum Cryptography

Every hybrid PQC scheme currently deployed (X25519 + ML-KEM in Signal PQXDH, Chrome, iMessage PQ3) derives a symmetric session key that uses AES-256-GCM or ChaCha20-Poly1305. Those symmetric ciphers remain quantum-safe after key derivation. The vulnerable links are the key exchange (X25519, broken by Shor) and the signature algorithm (Ed25519, also broken by Shor), which the hybrid replaces.

Frequently Asked Questions

When was Grover's algorithm published?

Lov Grover published the algorithm at the 28th ACM Symposium on Theory of Computing (STOC) in May 1996. The arXiv preprint is quant-ph/9605043.

Can Grover break AES-256?

Not in any practical sense. Grover reduces the effective security of AES-256 from 2^256 to 2^128 operations. 2^128 is still astronomically large, well beyond the reach of any fault-tolerant quantum computer that might exist in the coming decades.

Does Grover affect hash functions?

Yes, but less dramatically than the popular framing suggests. For a hash with n-bit output, Grover speeds up preimage attacks from 2^n to 2^(n/2). Collision attacks via birthday paradox are not accelerated by Grover (they already run in 2^(n/2) classically).

Should I double my symmetric key sizes preemptively?

If you already use AES-256 or ChaCha20-Poly1305 (256-bit), no. If you still use AES-128 for data that needs decade-scale protection, yes. NSA CNSA 2.0 mandates AES-256 for National Security Systems.

Sources

Protect Your Data Before Q-Day Arrives

QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.

Try QNSQY

Originally published at quantumsequrity.com/blog/grover-algorithm-explained-layman.