Problem Summary
Whilst 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.
Firstly, it is generally agreed that Shor’s algorithm will at some point allow quantum computers to break a number of currently used encryption algorithms – details further into this article.
If you then accept that a functioning quantum computer may be available at some point in the next 5-10 years, consideration needs to be given to 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, and 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 scheme requires both parties to share a single secret key to encrypt and decrypt data. This key is determined by the client and server 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. Unlike regular bits, qubits encode data as a superposition of all computable states. In layman’s term, this means a qubit represents some probability of 0 and some probability of 1, while a regular bit can only either be 0 or 1. This property of qubits enable Quantum Computers to offer significant speed ups for some computations.
In 1994, computer scientist Peter Shor published his eponymous algorithm, Shor’s algorithm, which takes advantage of the properties of Quantum Computers to provide significant speed up to solving two related mathematics problem: 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 current 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 for the session and decrypt all the data exchange 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 the time 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 for. 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 hard at work devising 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 4th round and is focusing on one remaining candidate for the key exchange algorithm, called 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 standardisation and adoption.
Thankfully, a NIST-approved solution exists to provide at least the security of current algorithms: hybrid key exchanges. By splitting the shared secret over multiple algorithms, the key exchange becomes as secure as the strongest algorithm used. 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 standardised 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.