Countdown to the Crypto-Apocalypse

The race to update encryption before quantum computing becomes a reality.

|
Sep 1 2015, 12:29pm

Photo: Giacomo Carena/Flickr

Last month, the National Security Agency quietly announced it would be abandoning the cryptography algorithms it has used since 2005 for fear of the coming computing revolution.

"Our ultimate goal is to provide cost effective security against a potential quantum computer," the agency wrote on its website.

Today, data is encrypted one of two ways: via symmetric or asymmetric encryption. In the former case, two parties each have access to a private key, which they use to decrypt data sent between them. Asymmetric cryptography makes use of two different keys, one that is public and used for sending someone encrypted data, and another that is private and is used by the recipient to decrypt this data.

Overall, this paradigm has proven to be remarkably secure and efficient. In order to crack the two most common methods of encryption, RSA and ECC, a computer has to sort through the factors of huge prime numbers or find a specific point along an elliptical curve, which has been shown to be so time consuming that it would be impossible for all the conventional computers to crack some of the larger keys before the heat death of the universe.

Unlike a digital computer which encodes data in binary bits (either 0 or 1), a quantum computer codes data in qubits, which can be both a 0 and 1 simultaneously. This ability means that quantum computers will be able to perform massive numbers of calculations simultaneously—like, say, the factors of a really large prime number used to encrypt some data.

This gives scientists barely enough time to develop and deploy a cypher that is capable of withstanding a quantum attack

"The cryptography tools that are the foundation of cybersecurity are all threatened by quantum computation," said Michele Mosca, co-founder of the University of Waterloo's Institute for Quantum Computing. "Once we fully harness the quantum world it could complete shatter the currently deployed public key cryptography... and it can sufficiently compromise symmetric key ciphering. That's the catastrophe looming."

Mosca predicts there is a 1-in-7 chance that by 2026 a quantum computer will be capable of breaking RSA-2048 encryption, a common standard that the government declared safe to use until 2030. By 2031, this chance increases to 1-in-2.

If Mosca is correct, this gives scientists barely enough time to develop a cypher that is capable of withstanding a quantum attack, much less distribute it and persuade the industry to switch over.

"What we're trying to do here is a fundamental change [and] it takes a lot of time," said Mosca. "Once the quantum computing capabilities are available, there's not much we can do. You can't make up for lost time and it really takes one to two decades to do this properly."

Mosca pointed to the "painful" transition from the Data Encryption Standard (DES) to the Advanced Encryption Standard (AES) in the late 90s. AES is the Advanced Encryption Standard and according to a call put out by the National Institute of Standards and Technology in 1997 was supposed to be "capable of protecting sensitive government information well into the next century." In 2001 the National Institute of Standards and Technology had selected the new encryption standard. By 2003 it was approved for use in encrypting classified information.

Now, only 12 years later, the NSA is working on new standards yet again and advising its clients to "prepare for the upcoming quantum resistant algorithm transition."

These new algorithms fall into one of two broad categories: quantum and post-quantum.

The former makes use of a series of photons to encrypt keys, whereas the latter is more or less indistinguishable from the encryption methods we use today, just with different math problems or larger keys.

(It was long assumed that quantum cryptography would be unbreakable due to a fundamental tenet of quantum mechanics which dictates that observation changes or destroys the photons being observed, but it turns out that quantum algorithms are not as foolproof as computer scientists once thought. For instance, there is research dating back to 2010 demonstrating how it would be possible for hackers to intercept quantum encrypted messages by blinding the receiving detector using lasers.)

The most pressing challenge when it comes to developing quantum resistant cryptography may have very little to do with science and mathematics, however. "As with most of the big problems facing the world, the hardest part is the social part," Mosca said.