Contrary to popular superstition, AES 128 is just fine in a post-quantum world

On Monday Valsorda finally channelled years’ worth of frustration fueled by the widely held misunderstanding into a blog post titled Quantum Computers Are Not a Threat to 128-bit Symmetric Keys. “There’s a common misconception that quantum computers will ‘halve’ the security of symmetric keys, requiring 256-bit keys for 128 bits of security,” he wrote. “That is not an accurate interpretation of the speedup offered by quantum algorithms, it’s not reflected in any compliance mandate, and risks diverting energy and attention from actually necessary post-quantum transition work.” That’s the easy part of the argument. The much harder part is the math and physics that explains it. At its highest level it comes down to a fundamental difference in the way a brute-force search works on classical computers versus the way it works using Grover’s algorithm. Classical computers can perform multiple searches simultaneously, a capability that allows large tasks to be broken into smaller pieces to complete the overall job faster. Grover’s algorithm, by contrast, requires a long-running serial computation, where each search is done one at a time. With a normal brute force search, if I interrupt it halfway through, I have roughly a 50% chance of it already being successful. So I can have two computers doing the search, each over 50% of the keys, and be done in half the time. But with Grover’s, if I interrupt halfway through, the probability of getting the correct answer is only 25%. So instead of using two computers on half of the search space, I now need four. So if you look at coreseconds, the classical algorithms cost what they cost, independent of how many computers you use in parallel. You can increase cores and your time goes down by the corresponding amount. But with the quantum algorithm, coreseconds are not independent of the parallelization strategy. Having more cores does not reduce the time by the same amount, to the point that if you went to the maximally parallel instance where each QC has to check only a single key, you need 2128 QCs, and not 264, i.e. you’re no better than classical. Valsorda’s post provides a more mathematically detailed explanation, as does this video. Valsorda listed a litany of sources that support the assertion that AES is perfectly acceptable in a post-quantum world, including from the National Institute of Standards and Technology (here, here, and here), the German Federal Office for Information Security (here), and Samuel Jaques, an assistant professor in the Department of Combinatorics and Optimization at the University of Waterloo (here). The exception to these recommendations is spelled out in the NSA’s version 2 of the Commercial National Security Algorithm Suite, which mandates AES 256. Valsorda said requirements for 256-level security were in place even in the predecessor algorithm suite, and weren’t specific to quantum readiness. “As far as I can tell, its intention is to avoid the very same fragmentation introduced by security levels by picking one oversized primitive for all settings.” He further said 256-bit AES is also warranted in certain cases, such as to avoid the possibility of collisions, in which two keys randomly end up equal because of the birthday paradox. So the next time you hear someone say quantum computing reduces the security of AES by a factor of two, kindly remind them that’s a superstition that’s distracting engineers from the real and considerable work in preparing the world for the advent of CRQC. It’s a tall enough order updating asymmetric algorithms known to be vulnerable to Shor’s algorithm, which breaks them in polynomial time, specifically cubic time, a massive advantage compared with the exponential time provided by today’s classical computers. “Conflating necessary and unnecessary changes will cause needless churn and take resources away from the urgent updates,” Valsorda argued. “We’re lucky we can leave the symmetric cryptography (sub-)systems untouched; we should take that blessing and focus on the work that actually needs doing, which is plenty.”