https://www.computerweekly.com/feature/Prepare-now-for-quantum-computers-QKD-and-post-quantum-encryption
Quantum computers have been on the horizon for several years, but recent breakthroughs mean we could expect to see enterprise-level quantum computers within 20 years.
Quantum computers use the principles of quantum mechanics, such as superposition and Entanglement, to perform their processes. While current computers use binary digits (bits), quantum computers use quantum bits (qubits), which can be in superpositions of states. This allows quantum computers to perform multiple calculations simultaneously, making them exponentially faster.
Given their ability to perform multiple processes simultaneously, quantum computers will enable many useful applications, such as imaging technologies and the modelling of chemical reactions. But these are just two areas in which quantum computers are expected to have a huge impact.
Quantum computers are still very much at the experimental stage, mostly under the remit of private research and development laboratories. However, it is only a matter of time before the engineering hurdles are overcome and quantum computers become cost-effective.
Attempting to prophesise when technology will become available is always risky. That said, many professionals believe the 20-year time-frame is realistic, but quantum computers are likely to become available to governments, universities and research institutes a bit sooner.
Quantum computers will have grave consequences for current encryption algorithms. “In the world of counting on being able to hide the key through prime numbers, when quantum comes online, all of a sudden that does not work so well,” says Jeff Hudson, CEO of Venafi. “Quantum computers can theoretically instantaneously work what would take a long time for standard computers.”
The current encryption protocols are based on complex mathematical problems. These mathematical problems are so complicated that it would take many years for conventional computers to solve them without the encryption key. “The flaw at the moment is that the message and the private key travel together, so if you have enough processing power you can work out the key and compromise the data,” says Colin Tankard, managing director of Digital Pathways. “That is where quantum computing is going to break encryption, because it will be able to process it really quickly.”
It is believed that a sufficiently powerful quantum computer running Shor’s algorithm could easily break these encryptions in a fraction of the time a conventional computer would take. “For a normal computer it is still around 70 years before they can break AES256 encryption,” says Tankard. “The faster the processor, the quicker that is going to be.”
This will effectively make current encryption methods obsolete. If they can be compromised, then all confidential communications become vulnerable to interception and manipulation. Given that the vast majority of confidential information is transmitted via the internet, new types of encryption methods will be needed which are resistant to attacks using quantum computers.
“A lot of the information that we exchange now is sensitive for a certain time in the future. In the case of credit card information, it is sensitive until the expiry date of the credit card,” says Robert Young, director of the Lancaster Quantum Technology Centre at Lancaster University, and co-founder of Quantum Base. “If someone were to record that communication now, in three years’ time a quantum computer comes along, then they can decrypt that communication and make money from the credit card details.”
One possible solution to the threat of quantum computers attacking encrypted communications over the internet is to use quantum key distribution (QKD). This is the method of transmitting the encryption key at the photonic level.
Quantum key distribution (QKD) is the method by which encryption keys are generated using a pair of entangled photons, and transmitted separately to the message. QKD is different to post-quantum cryptography, which is based on mathematical problems so complex that not even a quantum computer can solve them in a short enough time.
Through the use of quantum entanglement, it is known whether the encryption key has been intercepted and/or manipulated, before the transmission has even arrived. In the quantum realm, the very act of observing the transmitted information changes it. Thus, any attempt to intercept the signal is automatically detected by both the sender and the receiver.
Once it has been determined that the encryption is secure and has not been intercepted, permission is given to transmit the encrypted message over a public internet channel.
As the encryption key is transmitted separately to the message, using entangled photons, it is generally believed to be impossible for a quantum computer to intercept the key or decrypt the transmitted message. However, research has demonstrated that vulnerabilities exist.
QKD is a technology still very much in its infancy. Due to the light signal deterioration in fibre-optic cables, an effect known as decoherence, the current range of QKD is only a few hundred metres. It is possible to get around this by installing quantum repeaters, otherwise known as quantum network nodes, which are essentially miniature quantum laboratories that repair the quantum signal, to boost the signal over longer distances. For these quantum repeaters to be effective, however, they would need to be installed every 50km.
The need for quantum repeaters could be circumvented to a certain degree by relying on satellite communications. Instead of transmitting the light signal using below-ground fibre-optic cables, transmission stations can send the signal to a satellite. The satellite then transmits the signal to another satellite, before beaming it down to a different ground station.
The advantage of this method is that it does not rely so much on quantum repeaters, as the lack of atmosphere between satellites means that the signal will not deteriorate due to decoherence. “Once you get out of the atmosphere, the noise and break-up of signals gets less and less, and therefore QKD is not as restricted,” says Tankard.
Furthermore, QKD is only useful in cases of point-to-point communication for agreeing the encryption keys. Modern on-demand services, such as verifying identities and data integrity, rely on authentication and integrity mechanisms, rather than encryption.
This means that QKD would not easily integrate with the internet’s current infrastructure. “It is easier to exchange a symmetric key – a one-time pad – and send somebody a hard drive filled with random data and to communicate securely using it, than it is to use QKD,” says Young.
The claims that QKD is “unhackable” have also been questioned. A number of attacks have been proposed against QKD systems, which may be able to subvert the hardware components and obtain the shared key without alerting the sender or receiver. Also, denial of service (DoS) attacks could potentially interfere with paths carrying the QKD transmission, thereby disrupting the QKD network.
In 2016, the UK’s National Cyber Security Centre (NCSC) published a whitepaper reviewing the limitations of QKD technology, concluding that QKD at that time was not viable as an appropriate method for quantum-resistant encryption. While the report highlighted the potential advantages of QKD, it concluded that QKD has fundamental practical limitations, does not address large parts of the security problem and is poorly understood in terms of potential attacks.
The report recommended that: “The best practical approach to quantum security is to evolve current security applications and packet-based communication protocols towards adopting post-quantum public key cryptography. Software or firmware implementations of post-quantum cryptography should be easier to develop, deploy and maintain, have lower lifecycle support costs, and have better understood security threats than QKD-based solutions.”
Rather than adopting an entirely new method of transmitting the encryption key, as used in QKD systems, other encryption methods are available. Instead of relying on prime-factor based methods for encrypting data, post-quantum encryption uses techniques that have been described as “quantum-resistant”.
There are several variations of quantum-resistant algorithms available. One of the simplest proposed methods is to use symmetric cryptographic algorithms and hash functions. While Grover’s algorithm could theoretically speed up the attack against such ciphers, this can be offset by extending the length of the encryption key, otherwise known as key-length. This has happened before, when encryption went from 512-bit keys to 1,024-bit keys. Other approaches include lattice-based cryptography and multivariate cryptography.
The US National Institute of Standards and Technology (Nist) is planning to publish new post-quantum cryptography algorithms once a selection process is completed.
However, describing something as quantum-resistant is something of a misnomer, as proof is still required. Quantum computers have not been used to their full capacity, and these new quantum-resistant algorithms have not been empirically tested against an attack from a quantum computer.
All that can be said of these quantum-resistant algorithms is that they are sufficiently different from existing encryption algorithms, such that it would be difficult for a quantum computer to decrypt. How these new algorithms perform in the wild is yet to be seen, and will not be seen for several years. “The problem is you cannot prove a negative,” says Young. “Even though there is no current algorithm to attack those algorithms, it doesn’t mean they are invulnerable – it only means that they are so new that we do not have anything yet.”
Although quantum computers are still in development, it is only a case of “when” rather than “if” they are available. “Once they get that breakthrough, the costs really start to come down to become commercially viable,” says Tankard.
Waiting until quantum computers are released before acting will be far too late for many organisations, especially those in sensitive markets, such as finance or research. Organisations need to start preparing now for post-quantum encryption. “There is a highly vulnerable period when you might have nation-states with quantum computers but smaller commercial companies that do not,” says Tankard. “How do you protect yourself in that transition period?”
One of the first things organisations can do in preparation is to identify, and gain intelligence about, the locations of all their encryption systems. It is important to identify not only where each is located, but the strength of the encryption and what it is used for. This record needs to be regularly maintained and reviewed, as redundant systems are replaced and newer devices are included within the organisation’s network.
“We have seen just a little bit of the problem going from SHA1 to SHA2, as a lot of companies did not know where their SHA1s were and they had to switch them out as they were not secure any more,” says Hudson. “They have got to be ready to take out these encryption schemes and replace them with quantum-proof algorithms.”
Second, it will be important to prepare for the likely requirement to change existing encryption protocols for new ones. This process will be easier if there are clear records of the encryption systems used, as detailed above.
As occurred when switching to SHA2, challenges should be expected when upgrading encryption algorithms. Improvements in processing power already mean the length of number-based keys have to be increased periodically. “An elliptic curve for a 1,024-bit key would require an incredibly powerful quantum computer to attack it,” says Young. “If you increase key-lengths then you can at least be reassured that attackers will go for the lowest hanging fruit.”
At the time of the SHA2 upgrade, there were far fewer devices. Now, there are exponentially more devices within the business environment. Previously, upgrading was a manual operation, but this is no longer practical due to the number of devices in the typical workplace. “The world is still stuck in this thinking that I will put people against this problem,” says Hudson. “It used to work when the number of machine identities was low, but that is not the case any more.”
Instead, Hudson believes organisations should consider automating the upgrading of encryption algorithms, noting that this would require significant preparation. Waiting until the encryption algorithms have to be upgraded will be too late. “To be ready to deal with quantum computers, people need to start now,” he says.
Quantum computers are coming, whether we are ready for them or not. Now is the time to begin planning for upgrading current encryption algorithms to quantum-resistant ones. This is especially true for those organisations that transmit long-term confidential data.
QKD has the potential to provide protection against attacks from quantum computers. However, the technology’s current limitations do not yet make it sufficiently viable as a means of protection. Organisations should therefore maintain awareness of the latest developments in quantum-resistant encryption algorithms to ensure they are fully prepared for the post-quantum age of computing.
27 Sep 2018