Quantum Computers Are Not a Threat to 128-bit Symmetric Keys (23 minute read)

Tech cryptoquantumsecurity Read original

AES-128 and SHA-256 are safe against quantum computers, and the common belief that quantum computing halves symmetric key security is a misconception that could waste resources during post-quantum transitions.

What: A detailed technical analysis explaining why symmetric encryption algorithms like AES-128 and SHA-256 remain secure against quantum computers, despite widespread belief that 256-bit keys are needed for quantum resistance.

Why it matters: The misconception about quantum threats to symmetric keys could divert critical resources away from the urgent work of transitioning asymmetric cryptography (RSA, ECDH, ECDSA) which is genuinely vulnerable to quantum attacks via Shor's algorithm.

Takeaway: Focus post-quantum cryptography migration efforts exclusively on replacing asymmetric primitives (key exchange and digital signatures), not on upgrading AES-128 or SHA-256 which can remain unchanged.

Deep dive

Grover's algorithm provides quadratic speedup for searching (sqrt(N) instead of N operations), commonly misinterpreted as "halving" AES security from 128 bits to 64 bits
The critical limitation: Grover's algorithm requires sequential operations and cannot be efficiently parallelized like classical brute force attacks
When parallelizing Grover's across multiple quantum computers by partitioning the search space, the quadratic speedup degrades significantly—splitting work across 2^16 machines only saves 2^8 work per instance, not 2^16
Concrete attack cost: breaking AES-128 would require approximately 140 trillion quantum circuits with 724 logical qubits each running continuously for 10 years
The depth-width (DW) cost is approximately 2^104.5, and unlike Shor's algorithm, there's little room for optimization (only 17 bits come from potentially optimizable circuit parameters)
Comparison: breaking AES-128 with Grover is 2^78.5 (430 quintillion) times more expensive than breaking 256-bit elliptic curves with Shor's algorithm
NIST explicitly designates AES-128 as the security benchmark for Category 1 post-quantum algorithms and states that all AES key sizes (128, 192, 256) remain approved through 2035 and beyond
NIST's MAXDEPTH concept formalizes how the required sequential computation forces parallelization that limits Grover's practical advantage
German BSI and quantum computing expert Samuel Jaques independently reach the same conclusion using similar analysis
CNSA 2.0 requiring 256-bit keys is not a quantum adjustment—it's maintaining consistency with Suite B's Top Secret requirements for a uniform "256-bit security level" across all primitives
The practical challenge ignored in theoretical analysis: maintaining quantum coherence for a decade-long computation is essentially impossible with any foreseeable technology
Each logical T-gate in surface code architecture requires 2^16 physical operations, adding even more overhead not captured in the base estimates
Resources are finite: unnecessary symmetric key transitions create churn, complexity, and interoperability issues that detract from the urgent work of replacing quantum-vulnerable asymmetric cryptography

Decoder

Grover's algorithm: A quantum algorithm that can search through an unsorted database of N items in roughly sqrt(N) steps instead of N steps, providing quadratic speedup
Shor's algorithm: A quantum algorithm that can break RSA and elliptic curve cryptography exponentially faster than classical computers, making current asymmetric cryptography vulnerable
Symmetric cryptography: Encryption where the same key is used for both encryption and decryption (like AES), as opposed to asymmetric cryptography which uses public/private key pairs
Post-quantum cryptography (PQC): Cryptographic algorithms designed to be secure against both classical and quantum computer attacks
ML-KEM / ML-DSA: Module-Lattice-based Key Encapsulation Mechanism and Digital Signature Algorithm, NIST's new post-quantum standards replacing ECDH and RSA/ECDSA respectively
Logical qubit vs physical qubit: A logical qubit is an error-corrected qubit implemented using many physical qubits; quantum error correction requires thousands of physical qubits to create one reliable logical qubit
T-gate: A specific quantum gate operation that is particularly expensive in error-corrected quantum computing, often used as the unit for measuring quantum circuit cost
Depth × Width (DW) cost: A measure of quantum circuit cost where depth is sequential operations and width is parallel qubits, roughly analogous to CPU cycles × cores for classical computing
Surface code: A leading quantum error correction architecture that encodes logical qubits in a 2D lattice of physical qubits
CNSA 2.0: Commercial National Security Algorithm Suite 2.0, the NSA's cryptographic standard for protecting national security systems
Birthday bound: In cryptography, the phenomenon where collision probability grows with the square of attempts, requiring double the bit length (e.g., 256-bit hash for 128-bit collision security)

Original article

Both AES-128 and SHA-256 are safe against quantum computers. No symmetric key sizes have to change as part of the post-quantum transition. Almost all experts agree on this. The misconception is usually based on a misunderstanding of the applicability of a quantum algorithm called Grover's.