WHY THIS MATTERS IN BRIEF
- Encryption is the primary tool that organisations and governments use to keep data safe and secure, when Quantum computers become more wide spread criminals, hackers and state sponsored actors will be able to use them to decrypt data and render most encryption algorithms obsolete
A time bomb is ticking. The impending exponential leap in processing power made possible by the advent of quantum computing will crack some cryptography, and researchers are trying hard to make sure that the fall out isn’t catastrophic. Today encryption underpins everything, so consequently a technology that can crack it could be very dangerous if it gets into the wrong hands.
If quantum computing takes three decades to truly arrive – en masse that is, then there’s no reason to panic – at least yet. If it lands in ten years, however, then your data is in serious trouble. While it is difficult to predict just when the precise moment when the first public crypto key will be broken we can be sure of two things – firstly that it will happen, and then secondly that it will happen sooner than we think because researchers are making significant advances in the quantum field every day.
All we need to avoid this oncoming crypto carnage is a new way to make public keys and to figure out a quantum resistant way to generate them. Fortunately, all of this is already underway.
But there are hurdles – standardisation and implementation. The usual banes of IT’s existence, combine those two with the pressure from that mystery deadline and you have a melodrama that would make Hollywood proud.
There have been measured responses to the threat – such as the NSA’s call last year to start planning to shift to quantum resistant encryption, while the National Institute for Standards and Technology (NIST) is running a competition to spur work on, and research into, post quantum algorithms. Both are signs of the slow, steady march of progress from security researchers in academia and industry.
But that march may need to be more of a jog, and maybe a sprint.
“We do have lots of algorithms that could potentially be used to ‘fix’ encryption, but it’s the timeframe on this thing that’s a concern because there are some estimates that suggest quantum computers could be widely available within the next 15 years,” says Dr Dustin Moody, a mathematician in the computer division at NIST, “but noone’s really quite sure about that because it’s a research thing. But the whole process to study algorithms, standardise them and get them deployed? Well, that can take 15 years or longer. So there could be a real issue with the time frame.”
No one knows when this will all happen for sure but Dr Michele Mosca, deputy director of the Institute for Quantum Computing at the University of Waterloo, Ontario is willing to try to put a number on it, estimating a one in seven chance that some fundamental public key crypto will be broken by quantum computing by the year 2026, and a one in two chance of the same by 2031. Fortunately though it’s not as though the security industry has been sitting around waiting for a firm deadline before starting work otherwise we’d all be in trouble.
“We do have it in hand but there are a lot of variables that cause us to make sure that we want this to be high priority for people,” says Moody.
“We don’t want people panicking. Quantum computers are not going to break all encryption.”
Indeed, symmetric algorithms are safe so long as keys are doubled in length – a comparatively easy change – but thanks to researcher Peter Shor, the public keys we use to secure online banking and E-Mail now have an expiration date that coincides with quantum’s birthday.
While at AT&T in the mid 1990’s, Shor, who’s a celebrity in crypto circles, wrote a quantum algorithm that could crack encryption based on integer factorisation and discrete logarithms – taking out RSA and the Diffie-Hellman key exchange in one fell swoop.
Impressive.
“Currently used public key cryptosystems and signatures will be catastrophically broken,” says Dr Tanja Lange, chair of the Coding Theory and Cryptology group at Technische Universiteit Eindhoven and coordinator of the European project PQCRYPTO – post-quantum cryptography for long-term security.
“An attacker needs about the same time to break the system as it takes the user to run it.”
We’ll also need a big enough quantum computer to make use of Shor’s work. Quantum computers are exponentially more powerful than today’s standard computers but they’re currently difficult to operate and program – algorithms must be written just so or the answers they return aren’t readable – and, furthermore, they’re not easy to build.
So we know the problem, and are well on the way to solving it, but it’s hard to meet a deadline when you don’t know when it is. Thankfully, we don’t need to wait for quantum computers to arrive to start protecting ourselves from their potential downsides.
“Quantum-resistant computing has nothing to do with quantum at all,” explains IBM cryptographer Vadim Lyubashevsky, “it doesn’t need quantum computing to exist to work. Even if somebody had a quantum computer, somebody without one can potentially resist all of these attacks.”
There are three potential solutions drawing attention from researchers, and NIST expects each to be represented in its competition – Lattice based encryption, Code based encryption, and finally Multi Variate Quadratic encryption.
Encryption is all about hard maths. Lattice based crypto secures information by using the incredibly difficult task of finding the nearest point in a multi-dimensional grid of points – the public key is an arbitrary location, while the private key is the “lattice point”. Code based crypto is based on how hard it is to decode a general linear code, while multi variate quadratic crypto systems use polynomial equations to secure encryption.
Lyubashevsky believes the real design work behind lattices is done, and some versions have already been standardised for specific uses by different organisations.
“If somebody was really serious about using lattice crypto then that could be done within a month or so,” says Lyubashevsky.
Indeed, it’s already been tested in the real world. Earlier this year Google ran a small trial on a slice of traffic in the Canary build of Chrome using the “New Hope” lattice based algorithm but made it clear it wasn’t a vote for that version to become a standard, merely a first punt at trialling encryption for the post quantum future.
Alongside lattice based, code based and multi variate there’s also hash based cryptography.
“We feel pretty confident, and so do most experts, that their security is well understood, and they could be standardised sooner, within the next year or two,” says Moody, “however they would only be used in a small number of applications, like digital code signing, so they’re not a solution for the entire problem that we have.”
On top of those post quantum crypto systems, there will also be security built using quantum ideas and eventually protection using quantum computers themselves, which could guarantee encryption via the laws of physics. But we still need protection in the meantime, notes Lange.
There is one potential quantum based system that could help. Quantum Key Distribution (QKD), which China have been busy getting to grips with recently, doesn’t require a quantum computer, it merely uses quantum physics to build a key, rather than relying on hard mathematics.
“The premise is that if I send a single photon of light, if somebody looks at that single photon, then it disturbs the properties of those photons,” explains Phil Sibson, a researcher on the subject at the University of Bristol and co-founder of quantum cryptography startup KETS, a Bristol University spin off.
“Encode data on that photon, and it’s unreadable, this is something fundamental to quantum mechanics.” However, it’s not quite ready. There are limitations in distance and the amount of data that can be sent, he says, as well as the possibility of side-channel attacks. For example, at the moment, sending one bit of QKD information across even today’s most advanced quantum networks and communications systems would take over 300 years – which is impractical, although – inevitably, over time it will get better.
“But in principle, this is a way to provide a robust security based on quantum mechanics,” adds Sibson.
QKD aside, of the three popular post quantum options, we don’t yet know which will be the best. Hopefully more than one will work and be widely applicable.
“Very importantly, it’s too early to pick a winner,” says Mosca, “the NIST project to standardise a handful of systems is a good approach to drive greater study and scrutiny so we can have greater confidence in the slate of alternatives.”
But NIST isn’t just running a Britain’s Got Talent for post quantum encryption algorithms – it hopes to drive their improvement, too.
“We don’t yet feel that any of the proposed algorithms are quite yet ready for standardisation for wide scale deployment and use,” says Moody, “for the most part, many of them are very, very new and haven’t had a lot of people studying their security. With all cryptographic algorithms, just the test of time – having people look at them for years – helps you have more confidence in their security.”
Hence NISTs competition, designed to focus the attention of academia and industry on scrutinising the proposed algorithms. The rules of the challenge are currently being discussed, with work set to begin early next month.
After post quantum encryption is security checked and standardised, which is expected to take several years, it will be time for the industry to get to work implementing new systems – and that could well be another hold-up.
“In the past, when there have been transitions from one cryptographic algorithm to another, it’s taken a long time – anywhere from five years to twenty years, so it’s really hard to get these changes made quickly,” says Moody. NIST has been advising a shift change to elliptic curve cryptography since 2000, and some organisations are only now starting the transition.
Why does it take so long? First, the need for the change must be publicised so companies are aware of the work they need to do, but flipping to new technologies simply doesn’t happen overnight.
“Once something is out there and in use, it just takes industry a long time, because they don’t want to replace all their brand new equipment, they kind of wait for it to come off line and then put in new algorithms, so it just takes time,” adds Moody.
But there’s another reason we simply don’t have time to dawdle – any data that’s sensitive in the longer term – decades instead of years – is already potentially a problem. Anyone who collects that data now will be able to crack it later, so it’s safe to assume governments and their spying agencies are hoovering up anything that’ll be useful, even if it’s decades old.
“That puts an urgency in the time frame,” says Moody, “if you want your data to be protected for ten years or something like that, you need to have these quantum resistant algorithms in place as soon as possible.”
And this isn’t theoretical. Lange points to the NSA’s XKeyscore program revealed by Edward Snowden that makes it clear spying agencies are storing vast quantities of encrypted data.
“Once a big quantum computer exists, it can casually break the public key components of those communications, derive the used symmetric key, and decrypt everything,” she says, “personally sensitive data such as health records are currently sent over the internet between caregiver, accounting centre and health insurance using systems we know not to resist quantum computers. Similar problems exist for legal or military data.”
It’s likely, though not guaranteed, that governments will be the first to get their hands on a quantum computer not only because of the large cost of building one, but because they’re well motivated by the leg up it would give them in digital spying and surveillance. Switching to post quantum encryption now means that when various state sponsored hackers get their hands on the exponential power of a quantum machine, your data will have a better chance of staying safe.
“If you want to protect in the future, then you can start using the algorithms that we have – using lattice cryptography, or maybe something else – in tandem with what’s being used now,” said Lyubashevsky, “that may feel risky given none of the quantum resistant systems are yet standardised, but you can use both the future stuff and the today methods at the same time, reducing risk. You can use them at the same time, and so you’ll be no less secure than you are now, with only adding a little bit extra time and communication.”
And all of this is why standards bodies and organisations need to respond to that ticking clock and move faster, Lange argues.
“The biggest challenge is to decide when a system is good enough to be standardised,” she says, “I’m sure that with enough work we will have better systems in three years. Does that mean we should wait for three years with standardising so that we get the better standard? Maybe. But how does that weigh against compromising all secrets for another three years?”
While she agrees with NIST that it’s still too early to standardise, Lange says it’s not too early to offer some advice.
“Users dealing with long term confidential data need expert recommendations and tools now,” she argues, “those recommendations must prioritise confidence and security over convenience. Those users will happily upgrade to a more convenient system once that is available.”
Simply put, move to post quantum now if you need to. Everything encrypted today must be considered compromised once a quantum computer exists. For Lange, the problem is clear, and she concludes:
“I would sure have sleepless nights if I had to ensure the long term secrecy of data.”