The Quantum Resistance: Safety in the Age of Quantum Computing

To understand how quantum computers will be able to crack today’s encryption, it’s worth considering how cryptography works today.

There are two commonly used types of cryptography: symmetric and asymmetric. It is asymmetric cryptography that is at risk to quantum computers. Its algorithms consist of two mathematically linked keys – a private and a public key. The public key encrypts, while the private key is known only by the party and is used to decrypt the information.

Asymmetric cryptography is the most used in day-to-day communication, with many types of encryption falling under this umbrella.

Perhaps the most widely used is RSA, which is used to secure web browsers, chat applications, VPNs and more. These algorithms are based on a complex maths problem known as prime factorisation. The longer the key – the more bits – the harder it is to replicate the maths.

Current computers do not have the computing power to break the RSA algorithm. But we know that it will be possible with quantum computers thanks to Shor’s algorithm, devised by Peter Shor in 1994.

And in factoring these numbers on a quantum computer, an attacker will be able to reverse engineer, or factor, the private key.

“It's not breaking the encryption. It is breaking the keys,” says Kevin Bocek, vice president of security strategy & threat intelligence at Venafi, a cybersecurity firm protecting machine identities.

The rough estimate is that two qubits per bit of the key is needed to break the encryption. So for RSA 2048, a quantum computer would need 4,096 qubits. But it’s not quite that simple, says IBM cryptographer Vadim Lyubashevsky, who has been working on the post-quantum problem since 2002.

“Just measuring qubits is somewhat deceptive,” he says. That’s because these estimates refer to a qubit that is free from errors that today’s fledgling quantum computers are very much prone to.

“Unfortunately, when you're building a quantum computer, things are very unstable. So in order to create one of these logical qubits, it may need per qubit say, 1000 actual physical qubits.”

IBM’s quantum computer is currently capable of 50 qubits, Google’s 72, Intel’s 49. All of these are far from the perfect, error free qubits, known as logical qubits (the best way to measure the effective power of a quantum computer is quantum volume).

But computer scientists are working to improve these numbers. And when a fully functioning quantum computer arrives on the scene, the security implications could be severe, with a quantum computer replicating the identity of another machine by replicating digital certificates such as SSL/TLS that tell us a computer is genuine.

“The risk is of a quantum computer being able to recreate these identities, these keys, essentially, out of thin air,” says Bocek. “And one machine now could look like another machine, one machine could break our privacy. So now we could have a whole bunch of masquerading, marauding machines and so our private communications, whether we're a business or us personally – becomes known to everybody.”

We’ve already seen the dangers of expired digital certifcates. In 2017, hackers managed to steal 145 million customer records from Equifax undetected in part because of an expired digital certificate.

But in a post-quantum world, it won’t be your average cybercriminal carrying out quantum attacks.

Despite the potentially serious implications of this looming threat, quantum computers will only be available to a small number of people. That’s because they are incredibly difficult to build, requiring very specific parts, and will need to be kept in controlled lab environments. And they’ll be expensive.

This means that they will remain firmly under the control of nation states, a small handful of large commercial entities and academic organisations.

Or, as Bocek puts it: “Terrorists can't conjure up a quantum computer with pieces ordered on eBay”.

While they will likely remain firmly in the hands of powerful nation states, that does not guarantee they will not be misused to further the goals of one nation state over another.

“So whether that is eavesdropping, spying on a certain set of adversaries, or whether a nation state wanted to convey this as a weapon to destroy or create havoc in commerce – that's the way that these will be used,” says Bocek.

“Another type of attack may be to create havoc and uncertainty. A nation state might look to create distrust maybe in the banking or financial systems as retribution. And so, be able to masquerade or change certain trades or banking operations.”

In extreme cases, they could hypothetically be used to disrupt banking operations that spell a recession, says Bocek.

Professor Michele Mosca, co-founder of the Institute for Quantum Computing at the University of Waterloo, says that if the adequate defences aren’t developed in time, then “critical IT infrastructures will fail with no quick fix. Unlike today’s hacks, where we detect and remediate as quickly as we can, in this scenario the new tools needed to remediate haven’t yet been developed”.

And if they are developed but not robustly deployed in time in the real-world, “migration will be managed as a crisis,” says Mosca.

“This will be disruptive, expensive and worst of all lead to very bad designs and implementations. Bad designs and implementations can be hacked without a quantum computer.”

In 2017, Mosca estimated that there’s a one in six chance of quantum computers being able to break RSA 2048 by 2027. So, what can be done to defend against quantum attacks?

Some algorithms cannot be cracked by Shor’s algorithm, such as SHA-256, which is used in hashing for securely storing passwords, or AES, which is used to encrypt files and hard disks.

But these cannot be used for machine identities or to encrypt web communications. Instead, we will require new encryption tools that are based on different mathematical principles to defend against a quantum attack.

These will be bigger and larger keys, ones that are immune to quantum attacks.

So how close are we to having these quantum-safe algorithms?

“These fundamental low-level tools already exist,” says Mosca. “But they aren’t deployed widely in real-world systems.”

Tech heavyweights such as Google, IBM and Microsoft are among the players developing these. Recently, Thales announced a partnership with ISARA Corp and ID Quantique to develop quantum-safe algorithms.

“We have the algorithms now and we're reasonably certain of their security. They exist now,” says Lyubashevsky, who has helped IBM develop three sets of post-quantum algorithms: Crystals Dilithium, Crystals Kyber and Falcon.

“It's just a matter of being standardised. And they're already being used in some parts. Anyone can use them.”

But Mosca says that while – by some interpretations – we have these algorithms today, they haven’t been scrutinised enough yet.

“At the other end, one might argue we’re at least a decade away from robust, widescale, standardised deployment of quantum-safe crypto in critical real-world systems,” he says.

The beacon for all these efforts and the body that will decide the next encryption standards is the National Institute of Standards and Technology (NIST). The US government-backed organisation is running a ‘competition’ to determine a handful of quantum-safe algorithms that will become the new standards.

NIST is well versed here, having created the standards for all the previous encryptions and replacing them when they are cracked, all by a deadline.

“So we have some practice at this, we know what it's going to be like,” says Bocek.

Despite learning from the previous changes, it’s “not easy”, says Dustin Moody, the mathematician overseeing NIST’s post-quantum standards competition.

“It's very, very slow, and you never completely get rid of the older [cryptography standards],” he says of the process of introducing new standards, adding that this time around it’s “going to be somewhat of a more painful transition”.

However, Moody is confident that the standards will be in place before a large scale quantum computer will threaten cryptography.

In January, NIST narrowed the pool of potential encryption tools that will hold up in a post-quantum world down to 26 cryptographic algorithms.

These are selected on two criteria: security and performance. The process essentially involves researchers trying to break the post-quantum algorithms and making corrections where necessary.

Given that quantum computers are still in the nascent stage, researchers estimate “as best they can” how many operations a quantum computer would need to do” to break it, says Moody.

These algorithms will also need to be able to withstand current decryption techniques and need to work in big computers, smartphones and smaller, IoT devices.

“We want quantum-resistant algorithms that can perform this sort of lightweight cryptography,” Moody said in a NIST blog post.

Moody says that the aim is to narrow the quantum-safe tools down to a small handful to avoid confusion among industry. NIST is aiming to publish these standards in 2022, alongside guidance that explains the pros and cons of each type of quantum-safe encryption.

Once the standards are out, it will be down to industry to adopt them, knowing that the standards have the backing of the US government.

“These fundamental tools, even if standardised, need to be deployed in real-world systems,” says Mosca. “This is not easy either, but some companies are taking serious steps.”

Google, for example, has tested some post-quantum algorithms in Chrome, while Amazon, Microsoft, IBM and Cisco are among others that have been exploring it.

But a lot more needs to be done, says Mosca, and it will test the “broader complacency when it comes to cyber risk” among organisations.

“There is still a long hard road ahead, so we cannot be complacent,” he says, adding that researchers will need to continue studying what “novel quantum attacks” may be used to compromise the proposed quantum-safe alternatives.

So what, should businesses be doing now?

Moody says that one of the main things that organisations can do right now is to “be aware of the threat” and know that a transition is on the horizon.

“We recommend that they do a kind of a quantum risk analysis, where they look at the cryptography that they’re using right now,” he says.

“See what's vulnerable and what isn't, what public key cryptography they’re using; what their vendors are using; what products they're buying.”

Bocek agrees that organisations should be carrying out an audit of their current encryption keys, adding that automation is one way to swap out the keys at scale.

And businesses don’t necessarily have to wait for the standards, says Lyubashevsky. For example, a bank wanting to ensure its one-to-one transaction with its customers are quantum safe today, it could put one of the algorithms on its mainframe to protect itself.

That’s exactly what IBM is doing now with some of its customers, carrying out assessments to see if it’s the right time to start migrating.

“There are right ways and wrong ways to incorporate these algorithms,” adds Lyubashevsky.

He says the wrong way to approach it is take the post-quantum algorithm and simply hard code it into a system and be done with it.

“The better way is to do it in a very agile, modular way; to say, look, here's the place where our algorithm will go, we kind of know approximately how big the keys will be, we know how big the communication is going to be. And so then if you start migrating towards that type of architecture, and that type of security, it should be very easy to take whatever algorithms NIST will give, which will be some very small variation of what already has been submitted.”

All of these approaches lead to a position known as being ‘quantum agile’, where it’s easy to swap out old crypto for new post-quantum crypto.

But while quantum-safe algorithms are essentially already here and standardisation isn’t far off, that’s not cause to relax.

For some time now, security experts have been worried about a concept known as ‘record now, break later’. This means that anything currently encrypted with public key cryptography could be copied down now, stored, and decrypted when quantum computers are powerful enough.

“We need to have these standards in place as soon as possible because somebody could simply take your data right now and copy it down,” explains Moody. “And it's encrypted using current public key cryptography. And then if a quantum computer comes out in 10 years, they could go back and decrypt your data.”

“This is definitely the major worry right now, that somebody is harvesting data,” agrees Lyubashevsky.

Of course, there’s plenty of data that will be useless in ten or 15 years’ time, or of no real security value. A message containing the family secret recipe to the perfect quiche is unlikely to draw the attention of a nation state, but for high-value data – be it medical patents or sensitive government cables – the hypothetical risk is too great to ignore.

And products such as satellites and trains with lifetime cycles of ten to 30 years that cannot be easily replaced once rolled out, should be considering quantum-safe encryption.

That’s why some organisations are already looking to implement quantum-safe encryption on their most valuable data now.

Mosca says that quantum key distribution (QKD) is one way to future proof against future quantum attacks. QKD “provides key agreement through a non-confidential but authentic channel (including a quantum channel),” he says. “QKD cannot be mathematically cryptanalysed, so it’s resilient to ‘record now break later’ attacks.”

Although these are commercially available now, it cannot provide digital signatures like RSA, so is not a silver bullet.

Above all, the main things for businesses to do now is be aware of the threat on the horizon, carry out an audit of their public encryption keys, keep an eye on NIST’s standards, and aim at being quantum agile.

What happens when the next cryptography standards are here? Will they be the last upgrade, or will another algorithm or technology come along and break these post-quantum algorithms?

Lyubashevsky says breaking post-quantum algorithms is unlikely. Instead, it’ll be that a faster, more efficient algorithm will come along and supersede the incoming generation of cryptography.

“There is no one hundred percent guarantee in crypto.”