NSA preps quantum-resistant algorithms to head off crypto-apocalypse

The National Security Agency is advising US agencies and businesses to prepare for a time in the not-too-distant future when the cryptography protecting virtually all e-mail, medical and financial records, and online transactions is rendered obsolete by quantum computing.

Quantum computers have capabilities that can lay to ruin all of the public-key cryptographic systems currently in use. These capabilities, which aren't known to be present in the classical computers of today, include the ability to almost instantly find the prime factors of extremely large numbers, using a method called Shor's algorithm. Quantum computing is also believed to be capable of tackling other mathematical problems classical computers can't solve quickly, including computing discrete logarithm mod primes and discrete logs over elliptic curves.

The difficulty of factoring and computing discrete log primes and elliptic curve discrete logs play an essential role in cryptographers' confidence in RSA, elliptic curve cryptography, and other public-key crypto systems. When implemented correctly, most scientists and cryptographers believe that the crypto can't be defeated with today's computers before the end of the universe.

The end is nigh

At the moment, quantum computers are believed to be little more than a theoretical phenomenon. Consider, for instance, that the biggest number factored to date using Shor's algorithm is just 21. But a significant percentage of computer scientists say practical quantum computing is only a matter of time, and once that happens (anywhere in the next 10 to 50 years, most of them forecast), public-key crypto systems that form the bedrock of most modern data protection will be trivial to break. Such a doomsday scenario would jeopardize not only all transactions and records going forward, but it would also allow attackers to decrypt more than half a century's worth of old communications, assuming someone took the time to collect and store the encrypted data.

NSA officials, in their mission of protecting vital US national security information and systems from theft or damage, have long recommended a regimen of crypto algorithms for protecting classified information. Last week, agency officials updated the guidance to help agencies and the private contractors who cater to them begin a transition to what's known as quantum resistant crypto.

"Our ultimate goal is to provide cost effective security against a potential quantum computer," officials wrote in a statement posted online. "We are working with partners across the USG, vendors, and standards bodies to ensure there is a clear plan for getting a new suite of algorithms that are developed in an open and transparent manner that will form the foundation of our next Suite of cryptographic algorithms."

In a nutshell, the guidance advises using the same regimen of algorithms and key sizes that have been recommended for years. Those include 256-bit keys with the Advanced Encryption Standard, Curve P-384 with Elliptic Curve Diffie-Hellman key exchange and Elliptic Curve Digital Signature Algorithm, and 3072-bit keys with RSA encryption. But for those who have not yet incorporated one of the NSA's publicly recommended cryptographic algorithms—known as Suite B in NSA parlance—last week's advisory recommends holding off while officials plot a new move to crypto algorithms that will survive a post-quantum world.

"Until this new suite is developed and products are available implementing the quantum resistant suite, we will rely on current algorithms," officials wrote. "For those partners and vendors that have not yet made the transition to Suite B algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition."

"Really worried about quantum computers"

The advisory is significant because it signals the growing recognition that quantum computing could soon represent a practical threat on US national security. Until now, the lack of consensus about how long it will take for scientists to build a working quantum computer has kept the NSA from making such concrete recommendations.

"What the NSA is saying in this release is that they are really worried about quantum computers right now, worried enough that they are planning a big effort to switch all of the public-key crypto used by anyone who interacts with classified data to post-quantum algorithms," Nadia Heninger, an assistant professor of computer and information science at the University of Pennsylvania, wrote in an e-mail to Ars. "This will have a big impact for the security industry, since companies that produce products that they want to sell to the government will need to implement these algorithms, and they are likely to be deployed widely as a result."

In the two years following the leak of thousands of classified documents by former NSA subcontractor Edward Snowden, trust in the agency's recommendations has eroded in many circles. The relationship between the NSA and cryptographers hit an especially sour note following revelations the NSA-developed cryptographic standard known as Dual_EC_DRBG may contain a backdoor that allows agency insiders to decrypt data.

Heninger said the recommendations remain important despite the revelations. She noted that the Government Communications Headquarters, the NSA's British counterpart, has also recently called attention to the threat of quantum computing. Not long ago, the agency published a paper describing an attempt to build a post-quantum cryptosystem and a quantum attack against this system. GCHQ officials took the step with the hope of stoking research in the public community. Heninger wrote: