OpenSSH goes Post-Quantum, switches to qubit-busting crypto by default

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 conjoined 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 5+5+5+5 = 5×4 = 20), but repeated multiplication is the same as exponentiation, so that 5*5*5*5 = 5⁴ = 625.)

In other words, adding one digit to product doesn’t mean you need to go round the loop just 10 more times (additive), but that you need to go round 10 times more times (multiplicative).

Similarly, factoring a 20-digit product doesn’t take 20/10 = 2 times longer than a 10-digit product, but takes 10¹⁰ = 10,000,000,000 times longer, because there are 10 extra digits, each of which expands the amount of work 10 times.

And the prime products we’re dealing with in modern cryptography can be hundreds, or even thousands, of digits long.

So although we can easily, multiply together, say, two 1000-digit prime numbers to produce a 2000-digit prime product, we don’t currently know any way to split that 2000-digit prime product back into its factors, even if we use thousands of fast computers for hundreds of years.

Discrepancy in effort

That discrepancy in effort 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 2000-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, turning a feat that everyone once considered computationally unfeasible into a task might just be worth having a crack at 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 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 the NIST finalists, 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 OpneSSH 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 ultimate “winner’s shortlist”, OpenSSH will quickly include one or all of the ultimate official winners as well.

But for those who were wondering when they’ve be able to 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.