What is long-term data security and how do quantum computers break most cryptosystems?

By Scram Software 06 October 2017

We often store sensitive data on devices that can become compromised. For example, it might be a USB disk that we misplaced, or cloud storage that gets compromised. The best way to protect data is via encryption – without the appropriate decryption key, data will be safe from prying eyes and sabotage, both now and in the foreseeable future.

When encryption is used in a business or government environment, it is often to satisfy privacy legislation that mandates the safeguarding of sensitive or personally identifiable information (PII). This legislation often requires the confidentiality of such information be preserved long periods of time – for example, securing medical records even after a person dies.

It is precisely the long-term security provided by many encryption systems (also known as cryptosystems) that is under severe threat. A new category of computer based on entirely different physics – the quantum computer – is currently in development at research organisations within Google, IBM, UCSB and other institutions. Quantum computers have been theoretically proven to break most of today’s commonly used crypto systems. Although the development of quantum computers is still in its infancy, world experts predict that it would only be 15-20 years before a sufficiently powerful quantum computer could be built to crack conventional cryptography.

Documents leaked by Snowden revealed that the NSA had a project for developing quantum computing capability to crack cryptography. So real is this threat that since December 2016, America’s NIST (National Institute for Standards and Technology) has been soliciting proposals from around the world to evaluate and eventually standardise post-quantum public key cryptography, stating that “we must begin now to prepare our information security systems to be able to resist quantum computing.”

This technology development directly impacts the technology buying decisions of CISOs and CTOs today. A cryptosystem that is secure today may not be secure in 20 years’ time, yet data needs to be safeguarded in the long term. This leaves a buyer of encryption products with two choices:

  1. Purchase a cryptosystem that is long-term secure. Only a minority of systems currently meet this requirement. They can be easily identified as featuring “quantum resistant” or “post-quantum” cryptography; OR
  2. Purchase a cryptosystem that is not long-term secure, and accept that encrypted data will only remain confidential until about the year 2030.

This paper is an excellent high-level introduction to the technical details behind quantum computers and their impact in breaking many of today’s commonly used encryption systems.

What is long-term data security?

Properly encrypting your data keeps it safe… for now. And in 5 or 10 years’ time. But as computing technology improves there will come a time when conventional encryption will not be safe against any sufficiently-equipped adversary. Once a cryptosystem is broken, then any unencrypted plaintext data it encrypted is available, and all secrets are accessible.

But data security is not a fixed absolute; it depends on the way encryption is implemented and used, and also on the resources of the attacker. Data security also degrades over time! Planning for long-term data security then means protecting sensitive data over a minimum of 20-30 year timeframes, which can only be achieved by predicting the efficiency of potential data attacks into the future and selecting technology accordingly.

Long-term data security is increasingly seen as a problem for legislators and technologists. For example, German law stipulates that medical and legal data remain confidential from third parties even after death of a patient or client. Likewise, some confidential data archives will likely have lifetimes longer than the time it takes for new computer paradigms to threaten conventional cryptographic algorithms.

Current and future technologies

We’ll start by investigating the expected direction of computer technology over the coming decades. In particular, we’ll discuss a new computing paradigm that threatens conventional cryptographic approaches, and some suggestions on mitigating this risk.

Classical and quantum computers

“Classical” computers are the computers we already know and use. Formally known as binary digital electronic computers, they operate by representing information as sequences of zeroes and ones (“binary digits” or “bits”) and processing them with devices based on the physics of electrons (“electronic computers”). Each bit can hold one of two values: “0” or “1”; there are no intermediate values. Electronic computers execute algorithms on these bits using simple logic operations (AND, OR, NOT, etc.) to form useful results.

A new class of computing devices was proposed in the early 1980s involving quantum bits (“qubits”) instead of bits. Unlike bits, qubits can be in a combination of states, and so hold a superposition of “0” and “1” states at any one time. As the number of qubits increases, so too does the number of states simultaneously held by the set of qubits. Qubits are processed using quantum computers. These execute algorithms using quantum gates, which are logical building-blocks that operate on all possible states of a set of qubits simultaneously. Once a quantum computation is complete, the output is measured, which causes the multiple entangled superposition of states to collapse to a single classical state. Quantum computers with many qubits are theoretically capable of operating much quicker than any classical computer.

Quantum computers are not a replacement for classical computers – both have their strengths and weaknesses. However, quantum computers are fantastic for solving particular mathematical problems where classical computers struggle, so a problem that may take a classical computer quadrillions of years to solve will take a sufficiently powerful quantum computer just a few days.

Several types of encryption rely on these kinds of mathematical problems, and so “cracking” many types of encryption will be possible with quantum computers.

Classical and quantum algorithms

An algorithm is a sequence of steps taken by a computer in order to solve a problem.
One important quantum algorithm is Shor’s algorithm, developed in 1995, which decomposes an integer (a whole number) into its multiplicative factors. For example, the number 2457 can be factored into 3x3x3x7x13.

Factorisation of numbers becomes difficult as the numbers increase. Previously, it could take quadrillions of computing-years to factor a large integer on a classical computer; Shor’s algorithm operating on a sufficiently powerful quantum computer, could instead factor the same number in several computing-days.

Cryptography and quantum computers

Cryptographic algorithms are used to encrypt a plaintext into a scrambled ciphertext using a unique key. The ciphertext can only be converted back to a readable plaintext using a complementary decryption algorithm, together with the key. The key encapsulates all of the secrecy in this process, and data can only be decrypted with the correct key. There is no secrecy embodied in the algorithm, which is assumed to be known by any potential attacker.

Quantum breakable: classical public-key cryptography

One form of cryptographic algorithm is public-key cryptography, where two parties (traditionally denoted “Alice” and “Bob”) wish to communicate secretly over an insecure channel.

In public-key cryptography Alice and Bob each create public and private keys. Alice’s public key is sent to Bob, and used by him to encrypt messages to Alice, which can only be decrypted by her with her private key (which she keeps secret). Likewise, Bob’s public key is sent to Alice for her to encrypt messages to Bob.

Public and private keys are related by integer factorisations. Improved approaches to factoring large numbers, such as Shor’s Algorithm running on a sufficiently large quantum computer, will improve the likelihood of breaking public-key cryptography. These algorithms are therefore deemed quantum-breakable, because their protection decreases as quantum computers become more powerful.

Commonly used algorithm Security against quantum computers
RSA-1024, RSA-2048, RSA-4096 Insecure
ECC-256, ECC-521 Insecure
Diffie-Hellman Insecure
Elliptic curve Diffie-Hellman Insecure

Quantum resistant: classical symmetrical

Another form of classical cryptographic algorithm uses symmetrical encryption, where Alice and Bob share a single key and this is used for all encryption and decryption operations. In general, symmetrical encryption algorithms like AES and its now-insecure predecessor, DES, do not involve integer factorisation, and so Shor’s algorithm provides no benefit. However, symmetric encryption algorithms are affected by a different quantum attack: Grover’s Algorithm does provide a significant speed-up by finding the solution in the square-root of the time of a classical computer.

For example, if a classical computer needs to search 256 possible keys to be guaranteed to crack DES encryption, a quantum computer running Grover’s Algorithm only needs to do 228 searches. This is easier to understand when written in conventional notation:

Classical computer: 256 searches = 72,057,594,037,927,936
Quantum computer: 228 searches = 268,435,456

When measured in terms of time – assuming both computers can search at the same speed, if it takes a classical computer 1 day to crack a particular 56-bit encryption, it would take the quantum computer just 0.322 milliseconds – or one thousandth the blink of an eye.

If it took a classical computer 1 year to crack 64-bit encryption, it would take a quantum computer 7.3 milliseconds.

Therefore, to counteract this quantum speed-up, larger key sizes must be used. For symmetric encryption to be regarded as quantum-resistant, it needs to have a key length of 256-bits. An encryption system like AES-256 will be equivalent to AES-128 in a post-quantum world.

Commonly used algorithm Security against quantum computers
3DES Insecure
AES-128 Insecure
AES-256 Secure
Salsa20 Secure

Long-term data security in a post-quantum world

The arrival of quantum computing is a paradigm shift that has changed our views on data security. If we’d like to maintain secrecy of our data over the coming decades, what should we do today?

Quantum-attack resistance of current and new cryptosystems

Luckily, not all of today’s cryptosystems are expected to yield to quantum attack. Shor’s algorithm (and similar algorithms) shows promise only for cryptosystems based on integer factorisation, however other cryptosystems are available that rely on different “safer” mathematical bases.

For example, the symmetrical AES algorithm uses a substitution-permutation network to scramble and unscramble data, and as such its security is weakened slightly by quantum attacks. To compensate for this weakening, we simply double the key length, with no change to the algorithm. This gets us back to a secure cipher, resistant to quantum attack.

So selection of a quantum-resistant algorithm like AES-256, judiciously configuration and carefully integrated, will result in a cryptosystem that will be secure today and in decades’ time. This is the approach taken by Scram Software with its ScramFS encrypted file system.

In addition, new cryptosystems are being developed that do not rely on quantum-breakable algorithms. Several approaches have been proposed, and some are receiving institutional support. The US National Institute of Standards and Technology (NIST) estimates that quantum computers will be able to crack existing public-key infrastructure by 2029. Whether these new post-quantum cryptosystems will be available before the advent of sufficiently-powerful quantum computers remains to be seen.

Summary

Securing data now for a future post-quantum world is not a simple task, and involves many subtle design decisions. However it is possible to make strong predictions about how some current cryptosystems will become progressively less-secure, while others will remain safe in the face of these new technologies.

When making buying decisions now, it is important to choose a cryptosystem that is post-quantum secure to ensure the long term security of encrypted data.

Leave a comment

Send us a message

The field is required.




Cant read the image? click here to refresh