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

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 factorization.

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 = 2 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 than the size of the variable product above increases.

Loosely speaking, for every digit you add to the value of productthe number of times you have to go round the loop goes up multiplicativelynot 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 does not 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 digitif 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 do not 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 could not 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

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 is not 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 9released 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 sshdthe 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 (ie 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 will not break, and you do not have to use NTRU Prime even in new OpenSSH installations if you do not want to.

Presumably, if NTRU Prime does not 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 been 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 do not tell Schrödinger’s cat.


.

Source

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 factorization.

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 = 2 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 than the size of the variable product above increases.

Loosely speaking, for every digit you add to the value of productthe number of times you have to go round the loop goes up multiplicativelynot 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 does not 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 digitif 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 do not 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 could not 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

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 is not 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 9released 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 sshdthe 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 (ie 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 will not break, and you do not have to use NTRU Prime even in new OpenSSH installations if you do not want to.

Presumably, if NTRU Prime does not 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 been 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 do not tell Schrödinger’s cat.


.

Source

More from author

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Related posts

Advertismentspot_img

Latest posts

Senators Urge FTC to Probe ID.me Over Selfie Data – Krebs on Security

Some of more tech-savvy Democrats in the U.S. Senate are asking the Federal Trade Commission (FTC) to investigate identity-proofing company ID.me for “deceptive statements”...

Personal Information of Nearly Two Million Texans Exposed

The personal information of nearly two million Texans was exposed for nearly three years due to a programming issue at the Texas Department of...

Critical VMware Bug Exploits Continue, as Botnet Operators Jump In

Recently uncovered VMware vulnerabilities continue to anchor an ongoing wave of cyberattacks bent on dropping various payloads. In the latest spate of activity,...

Want to stay up to date with the latest news?

We would love to hear from you! Please fill in your details and we will stay in touch. It's that simple!