Don’t Rush Quantum-Proof Encryption, Warns NSA Research Director

In 1994, an American mathematician named Peter Shor discovered a way to crack the codes that banks, e-commerce platforms and intelligence agencies use to secure their digital information. His technique, dubbed Shor’s algorithm, drastically shortened the time it took to find the prime numbers that underlie public-key cryptography, making codes that typically take thousands of years to break solvable in a matter of months. 

But there was a catch: Shor’s algorithm could only run on a quantum computer, and those didn’t exist yet.

A quarter-century and many research dollars later, the world still hasn’t created a quantum computer capable of breaking public-key encryption in any reasonable amount of time. However, those machines are much closer to the horizon today than they were in the mid-1990s, and the cybersecurity community is already hedging its bets against a future when digital secrets are knowable to anyone with the right hacking chops and a couple dozen qubits.

When it comes to fighting quantum-enabled threats, timing is of the essence, according to Dr. Deborah Frincke, director of the National Security Agency’s research branch.

Related: The Pentagon is Trying to Secure Its Networks Against Quantum Codebreakers

Related: The Pentagon Is Turning to Nature to Solve Its Most Complex Problems

Related: Lasers, AI, Hypersonics Top DARPA’s Small-Biz Wishlist

Since about the time Shor unveiled his algorithm, Frincke has heard scientists predict quantum computers would arrive within roughly two decades. While those early predictions were overly optimistic, today many more people are backing that 20-year timeframe, Frincke said in a conversation with Nextgov. As rapid advances in quantum technology push current encryption protocols closer to their expiration date, she said it’s time for the government to start adapting its digital security methods for the future.

In 2015, the NSA announced it would begin exploring encryption schemes that could withstand an assault by a quantum computer, and in 2016 the National Institute of Standards and Technology kicked off a competition to develop such "quantum-resistant” algorithms. NIST received nearly 70 submissions to the competition, and after more than a year of testing and analysis, researchers in January announced 26 algorithms would advance to the second round. 

Though NSA isn’t directly involved in the NIST competition, Frincke and her team are closely following its progression. The security community works to defend today’s information ecosystem against tomorrow’s codebreakers but Frincke noted it’s important cryptographers don’t rush their work. Quantum computers may pose a substantial threat to digital security, she said, but deploying new encryption schemes too quickly could create additional own risks.

"There are two ways you could make a mistake with quantum-resistant encryption: One is you could jump to the algorithm too soon and the other is you jump to the algorithm too late,” she said.

If a group rolls out a new encryption scheme before it’s been thoroughly vetted, they might overlook vulnerabilities that quantum computers—or even classical machines—could exploit, according to Frincke. Without proper guidance, it’s also fairly easy to make a mistake when implementing the algorithms themselves, she said, which could lead to even more weaknesses.

“It's very important that people wait for NIST to do its due diligence,” Frincke said.

Even after NIST selects its winners, the threats posed by quantum computers won’t simply disappear, according to Frincke. Cryptography schemes are only effective until people find a way to break them, and it’s possible new vulnerabilities will emerge years down the line, especially after viable quantum computers become a reality, she said.

"Shor's algorithm is the attack that was developed in the absence of a quantum computer,” Frincke said. “It's hard to predict what people will actually do with one."

But in the meantime, NIST working hard to cover its bases.

Today, the agency is running the 26 encryption schemes that remain in the competition through a roughly 18-month vetting process, with cryptographers across government, industry and academia testing the algorithms against various attacks and measuring their performance in a wide array of applications. In June 2020, NIST plans to narrow the pool to about a dozen algorithms and conduct further testing, according to Dustin Moody, the NIST mathematician who’s spearheading the competition. The agency expects to select about four to six “winning” algorithms and publish guidelines for using them some time in 2022, Moody told Nextgov.

Still, he admitted testing algorithms for quantum-resistance remains an imperfect science, mostly because researchers can’t use an actual quantum system to launch attacks. But estimating potential computing power and modeling various known attacks, Moody said teams developed strategies to assess encryption strength without a true quantum machine.

The most important metric for candidate algorithms is their ability to withstand attacks, but Moody said researchers are considering multiple factors when assessing a given scheme’s effectiveness. According to Moody, one of the most important considerations is latency, or the time it takes to encrypt and decrypt a chunk of data. 

As a general rule of thumb, longer encryption keys boost security but also increase the amount of time and power it takes to process data. Today, many government agencies and private companies rely on 2048-bit keys, but most of the quantum-resistant algorithms in the competition use keys that exceed 1,000 bytes, about quadruple the length of a standard 2048-bit key, Moody said. One particular algorithm relies on a key roughly one-megabyte long, more than 3,900-times longer than today’s standard key.

Each scheme comes with a tradeoff between security and speed, Moody said, and as such certain algorithms are better fit for certain applications. A company looking to encrypt a device on the internet of things may want to prioritize speed, and thus opt for low-latency scheme with a short key, while a group like the NSA that wants to optimize security would trade speed for a heftier, more-robust key. All algorithms in the competition are relatively secure and high-performing, Moody said, though NIST will likely select multiple winners to accommodate different applications.

There’s not any one [algorithm] that seems to win across every category,” he said. “They all have some really strong benefits and some really strong drawbacks.