Grover's Algorithm vs Your Password: What the Math Actually Says
Grover’s algorithm is the quantum attack people actually mean when they worry about “quantum-proof” passwords. It does not instantly crack anything. It offers a quadratic speedup for unstructured search: a brute-force job that classically takes N tries needs roughly √N quantum iterations, which effectively halves the bit-strength of a password rather than collapsing it.
The quadratic speedup, in one line
If your password’s keyspace is 2^n possibilities, a classical attacker expects to search on the order of 2^n attempts. Grover reduces that to about 2^(n/2) iterations. So a 128-bit search becomes a 64-bit search — dramatic in theory, but it is a square root, not the exponential collapse Shor’s algorithm inflicts on RSA and elliptic-curve keys. Grover does not factor; it searches.
| Effective entropy | Classical work (~2^n) | Grover work (~2^(n/2)) | Practical verdict |
|---|---|---|---|
| 40 bits | ~1.1 × 10^12 | ~1.0 × 10^6 | Weak even today |
| 64 bits | ~1.8 × 10^19 | ~4.3 × 10^9 | Quantum-vulnerable long term |
| 80 bits | ~1.2 × 10^24 | ~1.1 × 10^12 | Borderline; add length |
| 128 bits | ~3.4 × 10^38 | ~1.8 × 10^19 | Safe; √ still leaves 64 bits |
Why Grover is far less scary in practice than on paper
Three things blunt Grover badly for password cracking:
- It is inherently sequential. Grover’s iterations cannot be parallelised the way classical GPU clusters split a wordlist; running M machines only gives a √M speedup, so you cannot simply throw hardware at it.
- Per-operation speed is glacial. Today’s quantum hardware runs gates at rates many orders of magnitude slower than a GPU hashes, and each Grover iteration needs the full hash circuit run coherently.
- Error correction is enormous. A cryptographically useful Grover run needs millions of stable logical qubits sustained over astronomically many iterations — far beyond current machines.
What it means for choosing a password
The defence is boring and effective: add length. Every extra random character roughly restores the bits Grover took away. A truly random 16-character password from a full keyset sits well above the 128-bit line after the square-root penalty. That is exactly why our password checker models Grover as √(guesses) rather than pretending quantum computers are magic.
For the other half of the quantum story — the public-key break that is exponential — read Post-Quantum Cryptography, Explained. And to see length in action, see How Long Does It Take to Crack a 16-Character Password?.