The threat to internet security from quantum computing
Source: John Leonard
The heady, Bondesque combination of espionage and quantum computing proved irresistible to headline writers everywhere. "NSA racing to build quantum computer that would open the door to easily breaking the strongest encryption tools in the world" panted the Daily Mail in one example.
"I'd be amazed if they weren't working on it," said Professor Alan Woodward of Surrey University, listing a large number of organisations and research facilities where the world's brightest minds are wrestling with the problem of harnessing the bizarre properties of subatomic particles to create a practical, working, general-purpose quantum computer.
"As Moore's Law reaches its physical limits pretty much every university computer science department in the world has someone working on quantum computing," Woodward went on. "And the majority of them are trying to factor prime numbers which lies behind key cryptography, as a proof of concept."
In this context the NSA's "doomsday weapon" against cryptography looks slightly less menacing, especially since it has to share a $80m budget with other computing projects under the umbrella of the "Penetrating Hard Targets" programme. For the purpose of comparison, in December the UK government announced a £270m investment over the next five years in quantum computing research in recognition of its potential benefits to the economy.
Like nuclear fusion, universal quantum computers always seem to be five years away. And as with that promised source of infinite free energy, the problems are to do with the engineering rather than the science. Current systems tend to be either very unstable or very large.
Which is not to say that no progress is being made. In fact a working quantum computer made by Canadian firm D-Wave already exists, with a 512-qubit processor that uses a process called quantum annealing. Investors include Google and NASA. However, this is a specialist device rather than a general-purpose one and is not suited to factorisation problems such as cracking public key encryption.
"The D-Wave computer is great for solving optimisation queries like the well-known ‘travelling salesman problem'," said Woodward. "But it won't run Shor's algorithm with the speed advantage everyone wants."
Shor's algorithm, and others like it, make use of quantum computers' ability to perform multiple calculations at the same time rather than having to follow a painstaking step-by-step process as digital machines do. It is used to factorise large numbers, something that classical computing finds very difficult.
The difficulty in factorising large numbers has long been exploited by public key encryption (PKE). PKE provides the underlying security for the entire internet, offering a secure means of transmitting encryption and decryption cyphers between trusted parties. It relies on one-way functions such as multiplying two large prime numbers to create a larger number. This is simple to do, but to reverse the process, to crack the key to discover the constituent factors, can take many years with even the most powerful classical computers as they crunch through all the possibilities, one by one.
Qubits, superposition & entanglement
In classical computing a bit can be 0 or 1. However, at the subatomic level items such as photons as photons and electrons exhibit a number of disconcerting characteristics, such being able to exist in two states at the same time, only "deciding" which to adopt once they are observed.
While in this in-between state, called superposition, a subatomic object represents both 1 and 0 at the same time. So a qubit, the basic unit of information in quantum computing, can be 1, 0, both or neither.
In a quantum computer a qubit is entangled with one or more other qubits. If the quantum state (represented by 1 or 0) of one qubit is known, then the quantum states of of the entangled qubits will be known too.
For two entangled qubits the number of possible superpositions is four (10, 11, 01, 00), for three it is eight and for 500 it is 2 to the power of 500 - an enormous number.
Running calculations across such systems using appropriate algorithms allows the computations to be done in parallel, rather than in the step-by-step linear processes followed by classical computers, allowing enormous increases in processing speed when solving certain types of problems.
But a quantum computer running something like Shor's algorithm could do it in seconds. And once these one-way functions become two-way functions, they are effectively useless for key transmission.
Scary stuff, but probably still some way off, even for a well-resourced organisation like the NSA. The barriers to engineering a stable general-purpose quantum computer remain daunting. That said, progress is being made, and Professor Woodward has few doubts that sooner or later a tipping point will be reached, after which progress will be rapid.
"In the early 80s computers were huge mysterious things which sat in special chilled rooms that could only be entered by the high priests - the operators and technicians," he said. "But look at how fast things changed. Quantum computers are at a similar stage now, but there have been some real advances in the last couple of years."
Storing quantum data for meaningful periods of time is one of these advances. Given their extreme sensitivity to the external environment, very low temperatures (close to 0 K or -273 degrees C) are typically required to stabilise the quantum bits (qubits) of data for more than a few seconds. However, last year a Canadian-led group of of international researchers managed to preserve the quantum state of phosphorus atoms embedded in a silicon wafer for 39 minutes at room temperature, beating the previous record by 100 times.
The number of interacting qubits is increasing too. In 2012 a US-led team created a quantum simulator consisting of a supercooled two-dimensonal grid of beryllium ions that could engineer interactions among hundreds of qubits -10 times more than previous devices.
Once a stable quantum computer has been created there remains the small matter of programming it. Quantum computers and digital computers are very different beasts. Although quantum computers can potentially run computations many orders of magnitude faster than even the quickest supercomputer, the results are probabilistic rather than definitive and algorithms to run on them must be designed accordingly.
So, perhaps of more pressing concern is the rumoured compromise by the NSA of the random number generators used by RSA key generation algorithms. This is possible because they are not really random.
"Computers struggle to generate random numbers because everything they do is non-random. However, computer-generated random numbers are still very hard to crack. It's like drilling through a 50-foot wall with a hand drill compared with drilling through a 100-foot wall," said Carson Sweet, CEO of security firm CloudPassage. "There is technically a difference but the practical real-world difference should be considered as well."
Since the NSA revelations, Sweet said there has been a surge of interest in his firm's cloud security services, with customers worried about weakened encryption. While the NSA might still ultimately be able to crack it, said Sweet, using strong encryption will make life much harder for them.
"The stronger the encryption and key management, the more resources have to be committed to break it," he said.
Rather than worrying solely about compromised encryption, said Sweet, firms should beware of putting data into the cloud without properly protecting it, or trying to shoehorn firewalls and intrusion-prevention systems designed for on-premise installations into the cloud environment. "We see that a lot, and it never works," he said.
Woodward agreed that protective technologies are underused. "People should encrypt their laptop hard drives. With modern processors there's virtually no performance overhead to worry about but most people still don't do it."
So, PKE is not dead yet. When that day arrives though, as it surely will given the depth and breadth of research going on, public key encryption as we know it is dead. What will take its place?
Alternatives to the RSA method of prime factorisation, such as elliptic curve cryptography (ECC) as used by Bitcoin, have been around some time but these too may be vulnerable to cracking by quantum computers.
But the very technology that will one day break PKE may also replace it in the shape of quantum key distribution (QKD). PKE is computationally inefficient, and is only necessary to ensure secure transmission of the keys. The promise of QKD is that much more efficient symmetric keys could be transmitted with very low chance of their being intercepted, doing away with the need for PKE.
QKD makes use of the phenomenon that a quantum particle exists in two states simultaneously until it is measured. If a qubit is intercepted by an eavesdropper its state changes and an error message is produced.
No security system is perfect, and QKD is still open to side channel attacks targeting a weak link - usually people - but it is more secure than what we have now.
"In the last 10 years equipment has become commercially available to deploy QKD." said Woodward.
While currently limited to distances of a couple of hundred miles or so and low data rates, nevertheless QKD has been successfully deployed in the metropolitan areas of Geneva and Tokyo and in Los Alamos National Laboratory in the US and is no doubt the indeterminate shape of things to come.
| }
|