NSA preps quantum-resistant algorithms to head off crypto-ap
Source: Dan Goodin
NSA preps quantum-resistant algorithms to head off crypto-apocalypse
Quantum computing threatens crypto as we know it. The NSA is taking notice.
D-Wave Systems
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:
For all that many people distrust the NSA, the NSA are certainly not the only ones worried about quantum computers, and it's not a surprising or controversial opinion among cryptographers that quantum security is an important consideration for long-term security. The surprising thing here would be if the NSA is planning to transition within a small number of years, since this suggests they are afraid of more imminent progress in developing a quantum computer than what's publicly known would suggest. (Together with the GCHQ's unusual step of publishing a candidate broken post-quantum scheme, this makes two important government agencies who are very worried about quantum computers in public very recently.)
This seems pretty unlikely to be a move to weaken or backdoor crypto.
(For the conspiracy theorists who think that the NSA has backdoored the NIST-standardized elliptic curves, wouldn't it be better if the NSA kept encouraging the public to use those instead?) It's going to be a huge amount of effort to develop, standardize, and deploy entirely new classes of algorithms. I assume/hope there will be some kind of initiative to have a set of NIST-standardized quantum-secure algorithms, maybe with a contest like for AES and SHA-3. After the Dual-EC debacle, NIST (John Kelsey) has publicly declared that they are re-evaluating their process and their relationship with the NSA.
Honestly, I think most of the academic crypto community sympathizes with the position NIST was put in and will probably put greater scrutiny on anything NIST produces in the future, but an open contest/feedback process with NSA input clearly labeled is likely to stimulate a lot of research in the area, produce some solid candidate algorithms and cryptanalysis that most people feel good about, and will be a good thing for everyone's security.
Last week's NSA update didn't say how long it would take for the new quantum-resistant algorithm recommendations to be published. If the past is any guide, they'll likely be rolled out gradually, in much the way support for elliptic-curve crypto was progressively introduced over the past decade and the way AES has slowly replaced the now-retired DES algorithm. Absent an imminent and credible threat, it will probably take decades for the new quantum-resistant crypto systems to be widely implemented.
| }
|