What would happen if cryptography stopped working tomorrow? For one thing, the Internet would effectively stop working. Signed software updates would no longer be possible. No one would be able to prove their identities online. A trustless Internet makes it hard to exchange any kind of sensitive information, which is where much of the value lies. Forget any kind of secure attestation, and any service that relies on it. Say bye-bye to everything from VoIP to online banking.
The blanket breaking of classical crypto isn’t a remote idea. In fact, warned Michele Mosca, it’s less a question of if rather than when, thanks to the magic of quantum computing. Mosca, co-founder of the University of Waterloo’s Institute for Quantum Computing, spends his time studying the effect of quantum computation on cryptography, and he’ll be talking about it at the SecTor conference this October. The bottom line: We should be worried.
A quantum future
Whereas classic computers calculate numbers one after the other, quantum computers use the weirdness of quantum mechanics to compute things at the same time. Instead of using regular electronic relays to represent binary bits, they use qbits, which allow them to hold many numbers in state simultaneously.
This doesn’t give quantum computers infinite, godlike mathematical powers, but it does allow them to do some things particularly well, points out Mosca. One of those things is identifying repeating patterns over vast quantities of numbers. When it comes to cracking conventional cryptography, that’s important.
During cryptanalysis, researchers can use the public encryption keys to produce a series of numbers that aren’t entirely random. They repeat over time. If a computer can identify the repeating pattern – known as the period of a sequence – in those numbers, then it can break the encryption mechanism.
“Classically, we know how hard that is. The number of elements of the sequence that you have to look at to find the period is roughly the square root of the period,” he said. “Usually for the numbers we deal with, that’s insanely large.”
Quantum computers are good at finding those patterns, even if they don’t necessarily know what the numbers inside them are. That’s enough information to crack the code, Mosca points out. “Finding the period of a sequence will allow you to break RSA cryptography.”
He believes that there’s a one in seven probability that quantum computers will evolve to the point where they can threaten classical encryption techniques within ten years, and gives a 50-50 chance of them being developed in 15 years.
When we hit that point, depending on the capabilities of the quantum computer, he envisages machines that can break a 2048-bit RSA key in a day. Some of his research explores reducing that overhead to minutes, and using quantum machines with a smaller number of qbits to do it.
Preparing for quantum code breakers
So, what can we do to prepare for the time when the encryption that we’ve been relying on no longer works? There are algorithms already in development that their developers hope will thwart quantum attacks. The problem is that not enough people are researching them, Mosca warned.
Cryptographic algorithms need extensive review and testing to increase the accepted level of confidence in them. The newer algorithms simply don’t carry adequate confidence in their proof against classical computing attacks, let alone quantum ones. The latter problem is especially difficult, because we don’t have the quantum computers to test them against, he pointed out.
All of this points to a major challenge. We know that quantum computing is highly likely. Ignoring it now could carry grave consequences later. He uses what he calls the ‘XYZ’ argument to illustrate this.
We know that it will take Y years to produce tools that are quantum-safe.
We want to make our data confidential for a period of X years after that point.
The date when someone finally flicks the switch on a quantum computer capable of attacking classical cryptography, we can call Z.
“You need X plus Y to be less than Z. But if Z is less than X plus Y, you have a problem,” he said.
This means that we should already be starting to plan for this future, he said, because while it may seem like science fiction, it isn’t. It’s a fact-based narrative with a highly probable endpoint.
“So, you need a ten- to fifteen-year plan,” he said. “You can’t delay starting. We want this to be a gradual migration to a new, quantum-resistant ecosystem. Given that it takes over a decade in many cases to prepare and deploy a new system, you have to start the process now.”
Plans are cheap. Reacting in a panic is expensive, and error-prone. Unfortunately, people tend not to plan ahead for highly probable but distant threats when moderately probable and more immediate ones demand their attention. The result? Not many people have it on their radar.
Some do. NIST is mulling the prospect of quantum attacks on crypto (see the NIST draft report on the issue here), and the NSA was anxious enough to recommend a shift to a new standard that’s as quantum-ready as the agency can make it until public standards emerge. Under its new regime, 2048-RSA and Diffie-Helman keys are out. 3072 bits are now the base standard for those algorithms.
It’s going to be a very different world in the next 20 years. It isn’t often that we move entirely from one computing paradigm to another, but when it happens, it can be seismic. Come and hear Mosca talk more about it at SecTor’s tenth anniversary conference, Oct 17-29, at Toronto’s Metropolitan Convention Centre. Register here.
There are 0 comments