The Quantum Computing Encryption Problem

Problem Summary

While the generally supported opinion is that we are still a number of years away from a functional quantum computer, there is a significant quantum computing-related problem that needs to be considered right now.

First, it is generally agreed that Shor’s algorithm will eventually allow quantum computers to break a number of currently used encryption algorithms—details are further in this article.

If you accept that a functioning quantum computer may be available sometime in the next 5-10 years, consider whether those computers may be used to decrypt sensitive data being sent right now using potentially breakable algorithms.

This article explains the issues with current encryption algorithms. It explains the “Harvest Now, Decrypt Later” challenge that needs to be addressed as soon as possible, including on the HPE NonStop.

How do we communicate securely over a network?

To better understand the implications of the problems exposed in the remainder of this article, let’s review how protocols used to secure communications over a network work. To do this, we will briefly study how the TLS protocol works.

Transport Layer Security (TLS) builds upon TCP to provide secrecy (no one can eavesdrop on your communication) and authentication (no one can pretend to be your intended recipient). TLS encrypts the data sent over the network using a symmetric encryption algorithm like AES or ChaCha to provide this secrecy. However, such a scheme requires both parties to share a single secret key to encrypt and decrypt data. The client and server determine this key during the handshake that initiates the session using a key exchange algorithm, such as elliptic curve Diffie-Hellman (ECDH), Diffie-Hellman (DH), or RSA for older versions of the protocol.

Below is a diagram giving a high-level overview of a TLS 1.3 session. Note the two ClientHello and ServerHello unencrypted messages during which the key exchange is performed.

TLS isn’t the only protocol to follow this pattern, in fact, most protocols do: SSH, PGP or the Signal Protocol (used by the Signal app or Google to provide end-to-end encrypted RCS communications) are some other common examples. Furthermore, all these protocols always perform their key exchange using one of the same standard algorithms: RSA, DH, and ECDH.

Quantum Computing and its impact on Cryptography

In Quantum Computing, data is encoded as qubits. Qubits encode data as a superposition of all computable states, unlike regular bits. In layman’s terms, this means a qubit represents some probability of 0 and some probability of 1, while a regular bit can only be either 0 or 1. This property of qubits enables Quantum Computers to offer significant speed-ups for some computations.

In 1994, computer scientist Peter Shor published his eponymous algorithm, Shor’s algorithm. This algorithm takes advantage of the properties of Quantum Computers to significantly speed up the solving of two related mathematics problems: prime factorization and discrete logarithm. These two problems happen to be the foundation of the most widespread asymmetric encryption algorithms currently in use: RSA, DH, ECDH, etc…

Below is a comparison of Shor’s algorithm with the General Number Field Sieve algorithm (GNFS), the current fastest algorithm able to handle large numbers such as those used in cryptography. This representation is not accurate, instead it aims at highlighting the scale of the exponential speed up provided by Shor’s algorithm. To account for the expected difference in speed between early quantum computers and modern classical computers, Shor’s algorithm here only performs one operation per second (1 Hz) while the GNFS performs 10 billion operations per second (10 GHz). Note that the y-axis uses a logarithmic scale.

However, the development of current Quantum Computers is slow and current models are far from reaching the status of Cryptographically Relevant Quantum Computers (CRQC), a quantum computer powerful enough to represent a concrete threat to cryptography. Therefore, our currently secured communication protocols are still safe for the moment.

Or are they?

“Harvest Now, Decrypt Later” attack

The idea behind “Harvest Now, Decrypt Later” attacks is to record encrypted traffic now and store it until a method becomes available to decipher the data.

For example, a TLS handshake and session recorded by an attacker in 2024 includes a key exchange using an algorithm such as Diffie-Hellman. Eventually, the attacker gains access to a CRQC and uses Shor’s algorithm to break this Diffie-Hellman key exchange and obtain the shared secret. The attacker is now able to derive the symmetric encryption key used for the remainder of the session and decrypt all the data exchanged between the two parties.

By the time we reach “Y2Q” (the time at which a CRQC becomes available), the data exchanged may not be relevant anymore: the credit card details used to make a payment have now expired, the private business project discussed in an email has now gone public, etc…… but this is not the case for all data. For example, a parent filing their tax return may list all their children’s Social Security Numbers when declaring them as dependents, exposing them to identity theft.

The time to full quantum-safety is the time it takes for developers to secure data, plus the time it takes for data to become irrelevant. If this time is longer than it takes researchers to develop a CRQC, then data will be compromised.

Here’s a diagram illustrating the two different timelines. It shows a hypothetical timeline of post-quantum cryptography (PQC). Segments on the timeline represent pieces of information streamed and how long they remain relevant. The colour of the segment indicates what kind of cryptography was used at the time the data was sent over the network.  When Y2Q is reached, all data protected by classical algorithms is compromised, and data that was streamed long before Y2Q still ends up being compromised. However, the earlier PQC is adopted, the less likely data that is still relevant ends up being compromised.

What can be done against such attack?

The time needed for data to become irrelevant and the time needed to develop a CRQC are both out of our control as developers. The only variable we can act upon is the time needed to secure data against quantum computing. For this reason, cryptographers and computer scientists are already working hard to devise new signature and key exchange algorithms that can resist quantum computers. In 2016, NIST launched the Post Quantum Cryptography Competition to gather and test candidates. Currently, the competition is undergoing the 4^th round and focuses on one remaining candidate for the key exchange algorithm, CRYSTALS-Kyber.

However, it is easy to underestimate the work left for us to do. Indeed, these new algorithms haven’t gone through years of cryptanalysis like the current algorithms have. As a result, the cryptographic community doesn’t have the same level of trust towards these algorithms as it does for RSA or DH. For this reason, we are still far from completing the slow processes of standardization and adoption.

Thankfully, a NIST-approved solution exists to provide at least the security of current algorithms: hybrid key exchanges. The key exchange becomes as secure as the strongest algorithm by splitting the shared secret over multiple algorithms. In the case of TLS, two such hybrid key exchanges are under review as IETF drafts to become standard named groups. In accordance with NIST specifications, X25519Kyber768Draft00 and SecP256r1Kyber768Draft00 each combine a standardized ECDH curve with CRYSTALS-Kyber to provide both the security of modern key exchanges and our best effort at security against CRQC.

What’s next?

Infrasoft takes the threat of quantum computing very seriously and has already implemented and made available these new hybrid key exchanges to users of our uLinga suite of products. Connections made over TLS, including Kafka and HTTPS, can now be negotiated to use these new algorithms.

If you’d like to take a deeper look at the threat of Quantum Computing and its impact on all aspects of cryptography, on asymmetric encryption and beyond, we invite you to attend our session at this year’s Technical Boot Camp in September or to email us at productinfo@infrasoft.com.au to enquire.