The race to protect sensitive encrypted data and communications using current techniques from the threat of being broken by quantum computers in the future takes a small step forward today.
This is the last day the U.S. National Institute of Standards and Technology (NIST) will accept ideas for new quantum-resistant cryptographic algorithms to be used in current public key infrastructures that will hopefully be unbreakable to the next generation of supercomputers.
NIST and other experts aren’t even sure when viable large-scale quantum computers able to crunch fast enough to break algorithms like RSA-2048, ECC (elliptic curve cryptosystem) and DSA, which are used for encrypting data and in common protocols like TLS (transport layer security) to enable secure Web page communications; IPSec, used in VPNs; and SSH for secure file transfers. Should these protocols be broken online payment systems, blockchains, IoT devices and other systems would be vulnerable to attack.
However, given the number of countries, big technology companies (IBM, Google, Microsoft) and universities pouring billions into research, an increasing number of organizations – including the U.S. National Security Agency – think the possibility is uncomfortably close.
A NIST project organizer said Tuesday that it has already received some submissions, but “a flurry” of last minute of submissions are expected today, Those deemed complete will be publicly posted at www.nist.gov/pqcrypto. The first of two conferences to discuss the proposals will be held in April 2018.
It will be a few years before NIST agrees on one or more approved algorithms, but a Canadian expert lauds its work. “It’s a tremendously important and valuable initiative,” Michele Mosca, mathematics professor and co-founder of the University of Waterloo’s Institute for Quantum Computing, said in an interview this week. “It’s central to what’s needed to get done.”
“It’s one of the most valuable things to be happening to prepare our world to be safe in the context of quantum computers.”
“We’re lucky that it didn’t get started any later,” he adds. “It’s not the only thing we need – there’s actually a long road ahead –but if you don’t start you’ll never get there.”
And getting started is what a number of organizations have to do, he insists. In 1994 he recalls experts predicting that in 20 years (that is, 2014) a quantum computer would be able to break the RSA cipher. “That gave us plenty of time to prepare, but we did not aggressively prepare,” Mosca said. “Things went rather slowly. Now we’re at the point where we really do need to worry that we might not be ready in time.”
He believes there’s a one in six chance within the next 10 years someone will have a quantum computer that can break RSA 2048 encryption – and that prediction was made before China announced it is making a U$10 billion investment in quantum computing.
A quantum computer manipulates photons, atoms, electrons, molecules to create qubits. Unlike current computers, qubits can be zeros, ones or both at the same time enabling superfast computation. If the system can be tamed. (Want more detail? Start with “Quantum Computing 101.”
If you judge news headlines – and Mosca says we shouldn’t – the new era is around the corner. Earlier this month IBM said it built a quantum computer that handles 50 quantum bits, or qubits. The company is also making a 20-qubit system available through its cloud computing platform. However, others noted there were no details in the announcement. Also, the quantum state of both systems is only 90 microseconds. That isn’t crypo-breaking speed.
But Mosca says how many qubits an institution says it has created or how many numbers it has factored is irrelevant right now. However, there are certain key demonstrations that have been occurring “at an alarmingly fast rate.”
Several platforms have achieved the first three key stages of building a quantum computer, he said. Now they are working on stage four, where a machine’s logical memory has a longer lifetime than the physical memory. If and when that happens their emphasis will switch from working on the physics of a quantum computer to the engineering – in other words, trying to make it scale.
Things are getting warm enough that the U.S. National Security Agency (NSA), responsible for creating U.S. encryption protocols and breaking foreign ones, said in 2015 that it wants to shift its publicly-known Suite B crypto algorithms to quantum-resistant cipher suites as soon as possible.
Encryption works by scrambling data using a mathematical key, which can be public or private. The most common private key is AES (Advanced Encryption Standard). RSA’s encryption is the most widely used public key algorithm,
Mosca said that generally, encryption algorithms should be resistant to quantum computers as long as their key length is increased. However, other parts of an encryption scheme, including key agreement and digital signatures, which are used to ensure authenticity and integrity of a message or software, has to be updated. Hence the NIST competition.
Some current algorithms may work
“There’s a small handful of mathematical algorithms that seem to work and have withstood the test of time, at least against classical attacks,” said Mosca. “They are resilient to known cryptographic attack methods, so that’s a good start. But it’s a far, far cry from what we need. We [also] need a very intense effort to discover new methods to cryptanalyze them – much harder than we’ve tried before. Especially with quantum attacks, which is challenging because we don’t have the quantum computers to try, so we have to analytically deduce algorithms and try to discover whether they would work or not.”
The algorithms that may be workable include lattice-based cryptosystems; code-based systems; elliptic curve isogeny-based systems; multivariant-based and hash-based systems (which are only good for signatures). These all generate larger public key sizes than currently used; some isogeny ciphers generate signature sies of 141,312 bytes. Security isn’t the only thing, Mosca adds: Solutions also need efficiency (ability to scale) for high volume use.
“We’re not saying stop using RSA and ECC,” he added. “In fact we I say use it for the next 20 years at least. But you have to layer in some quantum-resistant cryptography on top of that”
Ideally, algorithms approved by NIST would be able to “plug in” to existing TLS, IPsec, SSH and other protocol systems. However, Mosca admits it won’t be smooth. The new solutions will have to work with current protocols and scale.
What he is certain about is that CISOs and makers of products that use security protocols have to start looking now, if they aren’t already, for quantum-resistant solutions.
The University of Waterloo and McMaster University have collaborated in setting up openquantumsafe.org, a platform where developers can prototype and benchmark quantum-resistant solutions. The site has two pieces: An open source C library for quantum-resistant cryptographic algorithms, including a common API; and prototype integrations into protocols and applications, including the OpenSSL library.
‘Have a plan’
Mosca predicts in the next six to 18 months organizations will be differentiated by whether they have a well-articulated quantum risk management plan.
Some industries in Canada – he wouldn’t say which – are ahead of others, where security is vital and regulators are already thinking about what will be needed.
Others are still in ‘wait and see mode.’ “They might get lucky and things work out OK, but they might not, and might realize five years from now there’s one small thing they should have done to prepare for the day.”
“If you believe, ‘Our vendors will solve this for us,’ it’s worth checking that hypothesis,” Mosca said, “because some vendors aren’t doing anything because customers aren’t asking about it.”
“You have to have a plan, you have to start convincing people it’s a good plan and over time you have to implement the plan. But right now, step one is have a plan.”
As for those who are waiting for NIST to issue a new standard, Mosca says that could be a mistake. Remember any solution has to be validated, certified and integrated into your environment. That could take years. For some applications, a solution might be easy. But CISOs need to worry about those where it won’t.
“Start testing the alternatives with your system,” he advised, “see if they’ll still work. If not, you have figure out what you’re going to do.”
For more on what to do read the NIST report on Post-Quantum Cryptography , check out the European Telecommunications Standards Institute (ETSI) quantum safe web site, and the Global Risk Institute’s Methodology for Quantum Risk Assessment.