Skip links

NSA: We ‘don’t know when or even if’ a quantum computer will ever be able to break today’s public-key encryption

America’s National Security Agency has published an FAQ about quantum cryptography, saying it does not know “when or even if” a quantum computer will ever exist to “exploit” public-key cryptography.

In the document, titled Quantum Computing and Post-Quantum Cryptography FAQ, the NSA said it “has to produce requirements today for systems that will be used for many decades in the future.” With that in mind, the agency came up with some predictions [PDF] for the near future of quantum computing and their impact on encryption.

Is the NSA worried about the threat posed by a “cryptographically relevant quantum computer” (CRQC)? Apparently not too much.

“NSA does not know when or even if a quantum computer of sufficient size and power to exploit public key cryptography (a CRQC) will exist,” it stated, which sounds fairly conclusive – though in 2014 the agency splurged $80m looking for a quantum computer that could smash current encryption in a program titled Owning the Net, so the candor of the paper’s statements is perhaps open to debate.

What the super-surveillance agency seems to be saying is that it’s not a given that a CRQC capable of breaking today’s public-key algorithms will ever emerge, though it wouldn’t be a bad idea to consider coming up with new techniques that could defeat a future CRQC, should one be built.

It’s almost like the NSA is dropping a not-so-subtle hint, though why it would is debatable. If it has a CRQC, or is on the path to one, it might want to warn allies, vendors, and citizens to think about using quantum-resistant technologies in case bad people develop a CRQC too. But why would the spies tip their hand, so? It’s all very curious.

Progress on quantum computers has been steadily made over the past few years, and while they may not ever replace our standard, classical computing, they are very effective at solving certain problems

Eric Trexler, VP of global governments at security shop Forcepoint, told The Register: “Progress on quantum computers has been steadily made over the past few years, and while they may not ever replace our standard, classical computing, they are very effective at solving certain problems. This includes public-key asymmetric cryptography, one of the two different types of cryptosystems in use today.”

Public-key cryptography is what the world relies on for strong encryption, such as TLS and SSL that underpin the HTTPS standard used to help protect your browser data from third-party snooping.

In the NSA’s summary, a CRQC – should one ever exist – “would be capable of undermining the widely deployed public key algorithms used for asymmetric key exchanges and digital signatures” – and what a relief it is that no one has one of these machines yet. The post-quantum encryption industry has long sought to portray itself as an immediate threat to today’s encryption, as El Reg detailed in 2019.

“The current widely used cryptography and hashing algorithms are based on certain mathematical calculations taking an impractical amount of time to solve,” explained Martin Lee, a technical lead at Cisco’s Talos infosec arm. “With the advent of quantum computers, we risk that these calculations will become easy to perform, and that our cryptographic software will no longer protect systems.”

Given that nations and labs are working toward building crypto-busting quantum computers, the NSA said it was working on “quantum-resistant public key” algorithms for private suppliers to the US government to use, having had its Post-Quantum Standardization Effort running since 2016. However, the agency said there are no such algos that commercial vendors should adopt right now, “with the exception of stateful hash signatures for firmware.”

Smart cookies will be glad to hear that the NSA considers AES-256 and SHA-384 “safe against attack by a large quantum computer.”

Jason Soroko, CTO of Sectigo, a vendor that advertises “quantum safe cryptography” said the NSA report wasn’t conclusive proof that current encryption algos were safe from innovation.

“Quantum computers alone do not crack public key cryptography,” he said, adding that such a beast would need to execute an implementation of Shor’s algorithm. That algo was first described in 1994 by an MIT maths professor and allows for the calculation of prime factors of very large numbers; a vital step towards speeding up the decryption of the product of current encryption algorithms.

“Work on quantum resistant cryptographic algorithms is pushing forward based on the risk that ‘Universal’ quantum computers will eventually have enough stable qubits to eventually implement Shor’s algorithm,” continued Soroko. “I think it’s important to assume that innovation in both math and engineering will potentially surprise us.”

While advances in cryptography are of more than merely academic interest to the infosec world, there is always the point that security (and data) breaches occur because of primarily human factors. Ransomware, currently the largest threat to enterprises, typically spreads because someone’s forgotten to patch or decommission a machine on a corporate network – or because somebody opens an attachment from a malicious email.

Or there’s the old joke about rubber hose cryptanalysis, referring to beating the passwords out of a captured sysadmin.

Talos’ Lee concluded: “In a world where users will divulge their passwords in return for chocolate or in response to an enticing phishing email, the risk of quantum computers might not be our biggest threat.” ®