Harvest now, decrypt later: tomorrow's threat but today’s risk
What is harvest now, decrypt later?
Whether it be your ISP, someone on the same network as you, or even someone that works at a chokepoint (like an undersea cable or hub, or aforementioned ISP), there’s many people that can read your internet traffic; which is why the SSL and TLS standards were invented: to prevent bad actors from reading your data. This dictates everything from HTTPS traffic, including bank transactions, to most VPNs – so even traffic routed privately between businesses can be affected. These are the same protocols that handle your APEX traffic. However, security cannot be mathematically guaranteed when using this protocol – even though the whole of the internet relies upon it.
Harvest now, decrypt later – as the name suggests – is where an actor will gather data that is being sent over the public internet, with the hope that in the future they will possess the technology required to break the encryption mechanisms in place on that data. Unfortunately, this isn't just a hypothetical: there have been real world examples of HNDL, some of which storing information in the zettabyte to yottabyte range, some of which as far back as 2013.
What exactly is vulnerable?
Although this all may seem quite scary, it’s not all so bad: almost all modern symmetric cryptosystems remain unphased by the advancements in the field of quantum computers. This includes your hashes – such as SHA, bCrypt, etc – and your symmetric encryption – like AES. In fact, most modern day browsers support post-quantum key-exchange, and Cloudflare already uses a post-quantum key-exchange protocol by default.
So where does it all break down? Well, with asymmetric systems – such as RSA and ECDH – they all suffer from the same fatal flaw: they rely on the fact that it is computationally infeasible to factor a large enough composite number formed of two primes (ECDLP is trivial if the EC can be broken into prime order subgroups[1][2]).
Although each algorithm goes about key-sharing in a slightly different way – for example: ECDH uses points on an elliptic curve rather than large numbers – they each cling dearly to the rope of computationally infeasible factoring; a rope that’s getting pretty thin.
What can quantum computers do that classical computers can't?
Instead of using traditional bits, either a one (1) or a zero (0), quantum computers use qubits – which are in a superposition of the two quantum states: spin up, and spin down.
You might be thinking: woah, woah; what are we talking about? If not then maybe skip this section. 😅 Qubits can be in any combination of states. Let’s say that spin up (U) corresponds to one (1) and spin down (D) corresponds to zero (0): then we can obviously represent data like we already do. But, the advantage lies not with what we could already do, but with the quirks of qubits.
Qubits, when not being measured, lie somewhere in between our 'one' and 'zero': and when measured, they collapse into one of the two states; and have a given probability of each, and can each be entangled (their probabilities linked) – properties that allow for the ability to factor large numbers in a reasonable timeframe.
Better guess method
We’re going to need to understand a little modular arithmetic. If you've never done this, or want a quick refresher: imagine the hour hand on a clock; it's two o'clock, that means that in fourteen (14) hours, what time is it? That's right, four o'clock. This is working (mod 12). We can represent this as follows:
2 + 14 ≡ 4 (mod 12)
We use the identity symbol (≡) to represent that it is congruent – for example: 16 is not exactly equal, but it is the same as 4, when working within our modulus of 12 (ℤ12). Now if we had a 13 hour clock, and we were to perform the same calculation, what would we get?
2 + 14 ≡ 3 (mod 13)
In modular arithmetic, you can apply the modulus operator whenever you want. That means that the 14 in the last equation can be replaced with a 1 (14 mod 13 = 1), this prevents numbers from getting stupidly large and reduces computation time.
Now this is going to sound a little random, so stay with me here; let’s say we can find a number of the form:
xr ≡ 1 (mod N)
where r is even, then we've practically won. The above can be written as (by moving then one then difference of two squares):
xr - 1 ≡ 0 (mod N)
(xr/2 + 1)(xr/2 - 1) ≡ 0 (mod N)
and thus either (xr/2 + 1) or (xr/2 - 1) is a factor of a multiple of N – which can be factored further much faster (via Euclid's algorithm).
Once we have the factors of the public key, N, then we have the private key (woohoo!), or in the case of ECDH we can easily calculate the private key.
If all of that went over your head, then what we want to do is find two numbers (x and r), where r is even and multiplying x by itself r times gives a remainder of 1 when we divide it by N.
We can do this on a classical computer by choosing a random number for x (with the caveat that x cannot share factors with N), and repeatedly multiplying x with itself until it returns a remainder of 1 with N. If r happens to be odd, you can always try again. The caveat?: it's slow, very slow.
How a quantum computer helps
One neat thing about modular arithmetic (that is: working with remainders) is that it repeats! As such, this means that if we add N to our original xr, then we will also have another valid answer, and so on; which means that if we keep multiplying x with itself, we will get more valid answers, repeating every r multiples. So that’s our answer: we can rephrase this problem as finding how often xr repeats mod N.
Shor's algorithm uses this to its advantage using the Quantum Fourier Transform (QFT); the idea is that the qubits – which behave as if they are in both states until they are observed – can be acted upon with the function (xr) in such a way that the repeating 1s combine and the other pseudo-random data cancels out: revealing the period, and thus r[3].
From the above graph, you can see how our random number (3) to the power of the x-axis repeats every 12; a quantum fourier transform of this function would reveal the value in a much shorter time than a classical fast fourier transform. This means that r is 12, and thus, 36+1 or 36-1 is a multiple of a factor of N.
Well, isn't 36 going to be huge (especially when working with bigger numbers)? Well, we are still working mod 35, so it cannot grow larger than that. We get our answers of 30 and 28: and indeed; 30 is 5 times 6, and 5 is a factor. This seems precarious, but for larger numbers this process scales much more nicely.
Now that we know how to break it; how do we, well, not?
Post-Quantum Key Exchange (PQKX)
Learning With Errors (LWE)
Let's understand the basics: the learning with errors key exchange. First, we must work modulo some number, let’s say 47. Let us choose some random large (pretend they are) prime numbers:
x = 5
y = 7
z = 11
This will be our private key. Let’s also generate some equations, with the corresponding answers:
3x + 5y + z (=61) ≡ 14 (mod 47)
2x + 4y + 3z (=71) ≡ 24 (mod 47)
x + y + 7z (=89) ≡ 42 (mod 47)
In reality, we would need far more equations; but wait! Why can't we just solve for the answers? Well, we can – to solve this we can slightly change the equations:
(1) 3x + 5y + z ≡ 15 (mod 47)
(2) 2x + 4y + 3z ≡ 22 (mod 47)
(3) x + y + 7z ≡ 45 (mod 47)
Since our numbers are so small, we can’t change any of the coefficients, but with large enough numbers we could and should.
Well, now what? We have false equations; and we sent those out as our public key (in reality we would have many, many more). We can send messages by combining these equations until: we have something close to 0 or our modulus (47) for a zero-bit, or; we have something close to our modulus over 2 (23.5) for a one-bit.
Lets send a one-bit from our public key. We can add together equations (2) and (3), from our public key (we pretend this is much larger):
3x + 5y + 10z ≡ 20 (mod 47)
We then get a one-bit (as it is closer to 23.5 than it is to 0 or 47). We can send 3x + 5y + 9z to the private key owner – with enough equations combined it will be too difficult to brute-force the equations used – and they use their values for x, y, and z to calculate the true value, which should be close to what we got.
3x + 5y + 10z (=160) ≡ 19 (mod 47)
Aaand we also got a one-bit! Now you only have to do it at least 255 more times – and with much larger numbers.
Doesn't this mean there is a chance that this could fail? Yes: Kyber-512 has a probability of failure of less than 2-139[4], which is so ridiculously small that it is about the same probability that I take any random grain of sand on earth (including under the ocean floor, with ~263 grains of sand), mark it, distribute it randomly and choose another random grain of sand and get that same one, then do it again and get the same one twice in a row, then flip thirteen (13) coins and have them all land on heads.
The errors we introduce make it infeasible to brute force, and there is currently no known good algorithm that makes it feasible for a quantum computer to solve. However, for computational security against current classical computers, ridiculous keysizes are necessary. To combat this, we can use polynomial rings.
Ring Learning With Errors (RLWE) and Lattice-based cryptography (KYBER)
To achieve quantum security, a lot of equations are required, which I have actually implemented before, and it is very slow: taking seconds to complete. This speed of key-sharing is unacceptable, so other technologies are used to reduce key-sharing time. One of these is Ring Learning With Errors, and another is Lattice-based cryptography[4].
In reality, you can have the equations be modulo some other equation: this is called a ring; which greatly reduces the computation needed to be secure against brute force attacks. The major speedup in Ring Learning With Errors (RLWE) compared to traditional matrix-based Learning With Errors (LWE) is in the ability to perform a Number Theoretic Transform (NTT) on a polynomial. This NTT is essentially a Discrete Fourier Transform (DFT) on a polynomial over discrete n-th (or 2n-th) roots of unity (essentially reducing a polynomial into a series of powers of the 2n-th root of unity); reducing complex matrix multiplication to a NTT, addition of the NTT vectors, and an inverse-NTT (or iNTT). This is a massive speedup and took me from seconds to milliseconds to share a key (but it was in a much faster language). If you are curious about how this would be implemented, I have done that here.
Lattice-based systems, like those used within CRYSTALS-KYBER, are the most common algorithms in use today. KYBER is a recognised standard by NIST (as FIPS 203)[6] and is used within some systems today, most notably as a part of the signal protocol[5]. It is a much more efficient protocol than traditional RLWE techniques and miles beyond the enormous keysizes needed for matrix-based LWE.
Conclusion
While harvest now, decrypt later presents a serious threat to the internet and data security, the rollout of post-quantum security is slow; it is also not currently known when quantum computers will break traditional encryption (Q-Day, if you will), if they will at all.
As a developer, there is not much you can do except trust in the tools you are given, especially in APEX: Cloudflare actually supports a combination of elliptic curve diffie hellman and kyber 768, even reading this blog you are most likely using X25519MLKEM768, which is a quantum safe protocol.
If you liked this blog, please pass it to your colleagues, and check out our other blogs.
