Quantum computers: what does it mean for you today?

December 8, 2015

Quantum computers are said to be coming quite soon and will change the world forever. While that phrase would typically mean a revolution in physics and medicine, the change which is undoubtfully hanging in the air is the change of the information security paradigm.

Quantum computers: what does it mean for you today?

The discussions surrounding quantum computers, which are able — among other things — to quickly decrypt ciphers, have been going on for decades. The idea remained a utopian concept upheld by scientists and did not crystalize in any realistic tech elaboration.

Now we have reached the tipping point. In August the US National Security Agency (NSA) issued a new edition of its security recommendations for the industry. Ironically the NSA, notorious for its pervasive wide-scale surveillance methods, at the same time performs a completely opposite function in this regard.

The organization is designed to maintain secrecy of the critical and classified state-relevant information and propose recommendations on the most preferable and efficient encryption methods and other means on information protection to state organizations and private users. The major change which fueled the discussion on quantum computers was the agency’s decision to move away from the recommended crypto standard, known as SUITE B.

The NSA explains this decision by citing recent physics and technology breakthroughs evolving at a much faster pace than was previously assumed. The agency states, that practical quantum computers might become a reality quite soon, weakening existing systems based on encryption, digital signatures, or key exchange and making them vulnerable to the new generation of attacks.

To put it simply, the NSA revoked previous recommendations on ciphers and encryption algorithms but has not introduced the new ones, suggesting that users caught in limbo wait for some time until the next iteration of their recommendations are published. The latest recommendations are nowhere near, so while we are stuck in the waiting room, let’s ponder over possible development and outcomes of the quantum revolution.

In theory

Website certificates, software digital signatures, encrypted communication in web banking tools, instant messengers and other commodity apps all rely on a couple of relevantly simple math tricks.

Each of these use cases employs the principle of cryptography based on asymmetric keys. This means that the processes of ciphering and deciphering are performed via a pair of ‘mathematically’ connected keys, with the encryption key being publicly known and the decryption key available to the sole owner (a bank, an app developer, etc).

This math trick presupposes that while the public key is known, the private key cannot be calculated in an adequate period of time. Here is where the upcoming quantum computers become a serious problem. Where today’s average computer would spend thousands of years to calculate a particularly long succession of numbers the private key essentially is, a quantum computer would process this heavy load in a matter of minutes.

Is it a realistic threat to us? Well, the potential game change is massive. All online correspondence would lose their privacy, so an adversary would have no problem posing as a major bank or even the almighty Apple, as there would be no adequate means of confirming identity online. ‘The end is nigh,’ a pessimist would say. I – being an utter optimist – would respond: ‘Well, this threat is so superficial. There have to be much more of them!’

The Scientific Monitor

Until recently, folks who would get worried about the above mentioned possibility, could enjoy untroubled sleep. Researchers working on quantum computing faced two fundamental problems. First, the state of the quantum system (meaning, the solution of the math problem) was hard to calculate.

Second, the so-called ‘qubits’ (or ‘quantum bits’) are very unstable and hard to keep in a stable state: with more qubits, the system becomes more unstable. That means, the existing quantum computers are based on two to four qubits, whereas the task of cracking today’s crypto systems requires hundreds or even thousands of qubits!

Quantum computers: what does it mean for you today?

Four qubit chip. Photo by Eric Lucero, Martinis Group, University of California, Santa Barbara

A couple of years ago, it was widely acknowledged that the process of creating a practical quantum computer (which would pose a real threat to encryption algorithms) would take another two or even four decades. However, the evolution sped up unexpectedly. Recently a successful project by researchers from the University of New South Wales in Australia made some headlines. The scientists managed to create a quantum logic gate.

The solutions proposed by the group is even more fascinating due to the fact the researchers based their approach on the upgrade of usual silicon chips, making the would-be quantum computer a relatively affordable, scalable and backward-compatible with the ordinary PCs. The only drawback is that it requires ultra-low operational temperatures, yet the scientists are optimistic to increase the number of qubits to hundreds or even thousands without a particular effort.

The best-case scenario presupposes that the fist production quantum computer is to arrive in just 5 years, leveraging a modest number of qubits. To pose a threat to current cryptography methods, a quantum computer would need to evolve for another decade. Pessimists prefer to stick to their previous forecast, which is several decades.

Realists state that quantum algorithms are still a murky business and have to be thoroughly studied and analyzed, which might imply quantum computers are not capable of cracking ciphers at all. Only the course of the history is capable of proving them wrong, but if the ‘optimists’ are right, it’s time to get ready.

‘Getting ready’ could be easy and hard at the same time. The thing that needs to be changed in order to initiate the quantum era is the migration of current encryption protocols onto post-quantum algorithms (those not cracked by quantum computers). Fortunately, these are real.

However, we should bear in mind the experience we obtained during the last two years: outdated and/or flawed deployments of encryption systems which are largely vulnerable to Heartbleed or POODLE attacks, are still being used by even major companies. That means even successful security solutions cannot be applied at scale fast enough. And this is the reason why we should bother about ‘post-quantum’ encryption today.

“Given the poor rate of adoption or proper implementation of high-quality cryptography as it is, we do not foresee a smooth transition to counterbalance cryptographic failures at scale,” said Juan-Andreas Guererro-Saade, a researcher at GReAT, in his entry for Kaspersky Lab 2016 cybersecurity forecast.

Luckily, some serious industry organizations like NIST have already initiated the standardization process. At the moment experts discuss the viability of various new-generation algorithms to replace RSA and ECDH, which might grow unreliable in the post-quantum world.

A practical guide

So, what would an average concerned user entertain themselves with, while we are waiting for quantum crypto doom to happen? First, one should critically assess REAL threats and the value of the potentially vulnerable data.

Digital certificates for web banking and apps are terminable, so by the time quantum computers are around current certificates would be void, and there is a hope the upcoming certificated would be signed by algorithms cryptically resilient to quantum-based methods.

Companies watching out for threats (including Kaspersky Lab), would probably enable some ‘quantium’-grade security checks for websites, say, a red indicator in the browser’s address bar would alert a user if a web pages uses outdated encryption algorithms.

The same approach would apply to digital signatures for apps or encryption for traffic exchanged between IM users. They are likely to be adequately protected by the time quantum computers become everyday reality.

What is the threat is after all? The threat is the ability of organizations like NSA to collect an awful lot of encrypted traffic today. By now, it’s just a huge useless chunk of information stored in the data centers, waiting for next-generation quantum technologies which might finally decrypt the data.

It would all go down to one factor: the value of your traffic for them and whether it is worth storing and decrypting. Would it be equally valuable in the next 10-20 years? The answer might be ‘yes’ for certain user groups: contractors having access to top-secret information, reporters, doctors and lawyers working with confidential sources, or civil activists acting against repressive governments.

Should one belong to this high-risk group, they must assess the levels of risks they are running, and apply post-quantum methods to protect sensitive data today, to be spared some nasty consequences tomorrow.

There are certain approaches which might be used in this respect:

  1. Avoid asymmetric keys. ‘Quantum algorithms are capable of solving NP-complete problems which serve the basis of today’s asymmetric cryptography; thus compromising elyptic curve encryption and RSA, El Gamal signatures and encryption, as well as Diffy-Hellman algorithm, comments Victor Alyushin, an expert at Kaspersky Lab.

The solution might be either to use alternative key exchange protocols, or enable physical exchange of keys. For instance, the Threema mobile messenger presupposes that both interlocutors exchange QR codes on their phones, making further communication quite resistant to compromise.
  2. Use higher grade encryption. While production quantum computers might be a decade away, hackers do not sit idle and will continue to develop new and sophisticated crypto attacks, so the use of a RSA-8192 or a P-256 keys is totally justified for sensitive documents.
  3. Leverage stronger symmetric encryption algorithms. ‘Quantum computers are able to efficiently crack passwords and discover symmetric encryption keys: for example, a quantum computer cracks a 2N-byte long key in the same time it takes an ordinary computer to crack a N-byte long key. Consequently, it makes sense to double the length of symmetric keys to preserve the same grade of cryptographic resilience,’ says Alyushin.

It should be taken into account that practical attacks on AES are growing in number and level of sophistication, so, regardless of the fact they are still mostly unsuccessful, the migration onto 256-bit encryption would not hurt, even if the emerging quantum threat is not taken into consideration yet.

  1. Approach experimental ‘post-quantum’ solutions. They vary in terms of practical value and convenience, and their cryptographic resilience is, in some cases, highly debatable. However, if you are an early adopter, we recommend you check out the short review of existing utilities based on one of the most promising ‘post-quantum’ lattice-based cryptography systems.

The unexpected epilogue

While quantum computing would be a breaking point for Internet security and might result in some scandalous breaches, we still have to acknowledge this reality is years ahead.

That said, most of breaches and hacks throughout all these years have been caused by mundane reasons: deployment flaws, vulnerable software, weak passwords and other instances of irresponsible security practices.

So those worried about the security of their data in the advent of quantum computing should primarily concentrate on choosing right means of storing the valuable information, securing communication channels, as well as using robust encryption technologies and reliable counter agents. This would help to keep your secrets intact before quantum computers become the part of the everyday reality.