Three years ago, we published an article with the dramatic-sounding title Serious Security: Post-Quantum Cryptography (and why we’re getting it).
As you probaby know, so-called quantum computers work in a rather mysterious way compared to conventional computers, inasmuch as they can perform certain sorts of calculation so that they effectively “compute” all possible answers simultaneously in what’s known in the jargon as a quantum superposition.
At some point, if the resulting superposition of entangled answers has not been affected by operating errors (quantum superpositions collapse when you try to observe them, settling into a specific condition that can be measured), you can extract the answer without having to repeat the calculation over and over again in a loop.
Almost as though…
Quantum computing makes it feel almost as though you could replace this sequential code…
-- try 1000 times to find a value of i that works, and report it for i = 1 to 1000 do if itworkedout(i) then return i end end -- or report that none of them worked out return nil
…with this rather magical-looking parallel code…
calculation = workitallout(range(1,1000)) -- get superposition inside box answer = disentangle(calculation) -- open box and peek at Schroedinger's cat return answer -- report what you saw
Not all algorithms can be converted into quantum-friendly equivalents, but some can, including one known as prime factorisation.
That’s where you take two prime numbers that have been multiplied together, giving an answer such as 15, and work backwards to figure out that 15 = 5×3, thus factoring the product into its original parts.
Of course, to factor 15 is easy enough by traditional brute force:
product = 15 for i = 1 to sqrt(product) do -- we don't need to go past the root if (product % i) == 0 then -- % computes the remainder of the division print(product, ' = ',i,' x ',product/i) -- it divides exactly! break end end
But numerous cryptographic algorithms, notably those widely used for public key cryptography, rely on the fact that this factoring process gets exponentially harder as the size of the variable product above increases.
Loosely speaking, for every digit you add to the value of product, the number of times you have to go round the loop goes up multiplicatively, not additively.
(Repeated addition is the same as multiplication, so that 12+12+12 = 12×3 = 36), but repeated multiplication is the same as exponentiation, so that 12×12×12 = 123 = 1728.)
In other words, adding one digit to the iteration count doesn’t mean you need to go round the loop 10 more times (additive), but that you need to go round 10 times more times (multiplicative).
Likewise, in binary arithmetic, each extra bit (short for binary digit, if you’ve ever wondered, which can be only 0 or 1) in an iteration count doubles the number of iterations needed.
For example, bumping up your iteration count from a 16-bit number to a 32-bit number would increase the number of bits needed to store the counter from 16 to 16+16 = 32 (a doubling).
But the number of iterations involved would increase from 216 = 65536 to 2(16+16) = 216×216 = 232 = 4,294,967,296 (a jump that’s exponential in the number of additional bits).
And the prime products we’re dealing with in modern cryptography can be thousands of bits long.
So although we can easily multiply together, say, two 3072-bit prime numbers to produce a 6144-bit prime product, we don’t currently know any reliably fast way to split that 6144-digit prime product back into its factors.
Discrepancy in effort
The discrepancy in effort between multiplying two known primes together, and splitting that product back into its two factors, is pretty much the computational basis of a lot of modern online security…
…so if quantum computers ever do become both reliable and powerful enough to work their superpositional algorithmic magic on 3072-digit prime factors, then breaking into messages we currently consider uncrackable in practice may become possible in theory.
Even if you’d have to be a nation state to have even the tiniest chance of succeeding, you’d have turned a feat that everyone once considered computationally unfeasible into a task might just be worth having a crack at.
This would undermine a lot of existing public-key crypto algorithms to the point that they simply couldn’t be trusted.
Even worse, quantum computers that could crack new problems might also be used to have a go at older cryptographic puzzles, so that data we’d banked on keeping encrypted for at least N years because of its high value might suddenly be decryptable in just M years, where M < N, perhaps less by an annoyingly large amount.
Beecause of this, the United States cryptographic standards body NIST has been running a Post Quantum Cryptography (PQC) competition for several years already, so that if quantum decryption ever does become a reality, we’ll be ready.
The competition isn’t finished yet – these sorts of standards take years to coalesce, for three main reasons:
- Good cryptography is hard.
- New algorithms need new analytical techniques.
- Trust and consensus are hard to build in a global environment.
OpenSSH takes a lead
Nevertheless, OpenSSH, one of the most widely-used secure remote access tools in the world, and a de facto standard in most Unix and Linux distros, has decided to get ahead of the PQC curve.
The newly-published OpenSSH 9, released last Friday, has already picked its own winner from NIST’s current shortlist, and will now use a public-key encryption system called NTRU Prime by default.
In both ssh, the client program used for connecting. and in sshd, the server program used for accepting secure connections:
[we now] use the hybrid Streamlined NTRU Prime + x25519 key exchange method by default (“sntrup761x25519-sha512@openssh.com”). The NTRU algorithm is believed to resist attacks enabled by future quantum computers and is paired with the X25519 ECDH key exchange (the previous default) as a backstop against any weaknesses in NTRU Prime that may be discovered in the future. The combination ensures that the hybrid exchange offers at least as good security as the status quo.
We are making this change now (i.e. ahead of cryptographically-relevant quantum computers) to prevent “capture now, decrypt later” attacks where an adversary who can record and store SSH session ciphertext would be able to decrypt it once a sufficiently advanced quantum computer is available.
What next?
The new OpenSSH version supports all the cryptographic algorithms that it did before, so your existing installations won’t break, and you don’t have to use NTRU Prime even in new OpenSSH installations if you don’t want to.
Presumably, if NTRU Prime doesn’t make NIST’s final, official list of winners, OpenSSH will quickly include one or all of the ultimate winners as well.
But for those who were wondering when they’ve be able to enter their own Post-Quantum Cryptographic era proactively, without waiting to see how either quantum computing or the NIST PQC contest pans out…
…that time is now.
Just don’t tell Schrödinger’s cat.
