12 ms·

OpenSSH now uses hybrid post-quantum streamlined NTRU Prime X25519 by default

raimue 5y ago
Previous discussion: https://news.ycombinator.com/item?id=30953634 https://news.ycombinator.com/item?id=30953634
adhesive_wombat 5y ago
I wonder how much of the warehoused data[1] being sat on by security agencies will be decrypted in any meaningful timeframe. [1]: E.g. the exabytes at https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center, but there's lots of these agencies in the world
- flatiron 5y ago
  Once there is a tingle it’ll happen they’ll reissue keys and reencrypt. Nobody is going go “oh well out of business time was a good run”
  - adhesive_wombat 5y ago
    But all the data up to that point is wide open. If it ever becomes practical to decrypt captured data, there's going to be some interesting leaks from non-quantum-proof encryption age. Also lots of cryptocurrencies will shit themselves, which might be a feature or a bug, depending on your perspective.
    - SnowHill9902 5y ago
      You have to operate under the assumption that state agencies already have access to your communications. Also, 256 bit hashes are considered broken but that doesn’t mean state agencies can break the at a sufficient rate or that they are interested in breaking cryptocurrencies.
      - johnthescott 5y ago
        which well known 256 bit hash is broken?
        jagger27 5y ago
        Let’s assume you’re right and the crypto itself is sound. I agree that is likely and doubt any TLAs have a significant mathematical edge. Does the NSA just stop there and call it a day? No, of course they write Stuxnet. They attack everything else. What well known piece of software isn’t broken?
        SnowHill9902 5y ago
        FreeBSD?
        jagger27 5y ago
        I think you mean OpenBSD. From their homepage: > Only two remote holes in the default install, in a heck of a long time! FreeBSD, not so much. https://www.cvedetails.com/vulnerability-list/vendor_id-6/product_id-7/Freebsd-Freebsd.html https://www.cvedetails.com/vulnerability-list/vendor_id-6/pr...
        staticassertion 5y ago
        Keep in mind that openbsd has a tiny base install, so it's not exactly surprising that there aren't a lot of remote exploits. Nothing's listening by default, so why would there be? By the time you set up OpenBSD to do anything, that's gonna change.
        jagger27 5y ago
        Indeed. “Default install” is a big asterisk.
        SnowHill9902 5y ago
- shapefrog 5y ago
  Decrypting against leaked / found private keys is likely the path for now - but on the infinite timeline - 100% will be decryptable.
po1nt 5y ago
It's hard for me to comprehend simple asymmetric encryption let alone understand how this solution is quantum proof. Everytime I read something like this I wonder if I'll ever catch up with the times.
- floatboth 5y ago
  IIUC, NTRU is only "quantum proof" because there is no (publicly known) quantum algorithm for breaking it, while there is Shor's for everything discrete logarithm based (both RSA and elliptic curve anything).
  - bawolff 5y ago
    Until we prove P!=NP that (i.e. its only secure because we dont know how to solve it) is pretty much true of all crypto algorithms, even classically.
    - gpm 5y ago
      This is true, but we don't know even more for quantum computers, because we have spent a lot less time studying quantum algorithms, so not yet having found an algorithm is much weaker evidence that the algorithm doesn't exist.
- 0xdeadb00f 5y ago
  I can understand Curve25519, Diffie-Hellman, but lattice-based crypto goes way over my head.
- eximius 5y ago
  I have a really old (college) implementation of plain old NTRU in Python, if you'd like a little insight into what NTRU is and how it works at a superficial level (kind of like how RSA is never textbook RSA). There are also some slides explaining the math, but you have to be comfortable with some college level group theory (even reading my own slides is hard because I haven't used it since then). The short answer is that NTRU uses convolution polynomial lattices. Breaking the cryptosystem requires finding a "short" basis for a lattice described by the private key. There are efficient algorithms for this in R^2, but not for high dimensional convolutional polynomial spaces (LLL Reduction is the best I'm aware of, which is greater than O(d^5) where d is the number of dimensions https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...). Do note the impl I did is absolutely terrible and probably subtly buggy but might get the idea across. Also, it splits the message into blocks and encrypts that instead of just wrapping a symmetric encryption algorithm because I was young and naive. :) https://github.com/logannc/pyNTRUEncrypt https://github.com/logannc/pyNTRUEncrypt
_vdpp 5y ago
Am I alone in wondering if quantum attacks on existing algorithms are still very hypothetical and may never come to fruition?
- klyrs 5y ago
  Folks in quantum computing seem to think that's it's a near-certainty, "just an engineering problem." As long as you don't ask for a specific timeline, they won't even lie.
- staticassertion 5y ago
  The "Too Much Crypto" paper is pretty reasoned. See section 5.2, and 5.2.3 - "Should we care?"
  - staticassertion 5y ago
    I forgot to link it... https://eprint.iacr.org/2019/1492.pdf https://eprint.iacr.org/2019/1492.pdf
vzaliva 5y ago
It mentions only "key exchange method". Does it mean we can keep our old keys or it requires different types of keys to be used?
- sz3 5y ago
  Different keys. For example, you might currently be using a public/private keypair for 4096-bit RSA. That keypair (by definition) only works for the RSA key exchange algorithm. Likewise, an x22519 keypair is for the x25519 key exchange. A sntrup761x25519 keypair will be its own thing. As an aside, a sntrup761x25519 public key will be two public keys glued together (one for each algorithm). [1] Likewise for the private key. (one could reuse an existing x25519 keypair for the x25519 component of sntrup761x25519, but it seems like a bad idea) [1] https://github.com/openssh/openssh-portable/blob/master/kexsntrup761x25519.c#L42-L70 https://github.com/openssh/openssh-portable/blob/master/kexs...
  - ttybird2 5y ago
    Same keys, servers and clients will keep using their ed25519 keys for authenticating each other, the keys for the key exchange are negotiated on login.
    - sz3 5y ago
      Huh! Thanks for the correction. That makes a lot of sense -- I have some more reading to do...
pabs3 5y ago
There is a comment on LWN saying that the addition of NTRU Prime for PQC is a little premature: https://lwn.net/Articles/890788/ https://lwn.net/Articles/890788/ > The addition of NTRU Prime for PQC is a little premature, because a new paper just came out which showed that many LWE schemes are weaker than was previously thought. The paper admits that it is not directly applicable to NTRU (which is not an LWE scheme), but it might be adaptable to it. > https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4c... > https://doi.org/10.5281/zenodo.6412487 https://doi.org/10.5281/zenodo.6412487 > > NTRU-based cryptosystems are among the leading candidates for lattice-based post-quantum cryptography. In this work, we propose improvements to the dual attack on LWE, and as such our attack is not immediately applicable to NTRU-based cryptosystems. It is an interesting question whether ideas from this work can be adapted to similar improvements to attacks on NTRU. Specifically, there appear to be similarities between the dual attack on LWE and the so-called “hybrid attack” [How07, Wun16] on NTRU. The hybrid attack also involves enumerating over parts of the secret, and then invoking some distinguisher to determine whether a resulting vector is close to a certain constant lattice. It seems reasonable to the writers of this paper that ideas similar to those presented here can be used to reduce the running time of such attacks as well, though anything definitive would of course require further research.
- nullc 5y ago
  It's pretty easy for openssh to change kex ciphers-- they're not used for persistent keys, and they're negotiated every session. How many more years should it go with no attempt at resisting future decryption by quantum computers just for the sake of potentially keeping the surface of legacy ciphers that would need to be carried around one entry shorter, should it become necessary to replace this cipher? I think instead, it could be easily argued that it was long past due: it could have been deployed several years ago. The security story for lattice crypto will probably remain dubious for the forseeable future (unless it gets converted to outright broken). But on desktop computers and servers lattice crypto is so cheap that most applications can just throw it in just-in-case. Unfortunately, the obvious alternatives like code base crypto have operating costs that make them harder to justify on a just-in-case basis.

Previous discussion: https://news.ycombinator.com/item?id=30953634 https://news.ycombinator.com/item?id=30953634

I wonder how much of the warehoused data[1] being sat on by security agencies will be decrypted in any meaningful timeframe. [1]: E.g. the exabytes at https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center, but there's lots of these agencies in the world

flatiron 5y ago
Once there is a tingle it’ll happen they’ll reissue keys and reencrypt. Nobody is going go “oh well out of business time was a good run”
- adhesive_wombat 5y ago
  But all the data up to that point is wide open. If it ever becomes practical to decrypt captured data, there's going to be some interesting leaks from non-quantum-proof encryption age. Also lots of cryptocurrencies will shit themselves, which might be a feature or a bug, depending on your perspective.
  - SnowHill9902 5y ago
    You have to operate under the assumption that state agencies already have access to your communications. Also, 256 bit hashes are considered broken but that doesn’t mean state agencies can break the at a sufficient rate or that they are interested in breaking cryptocurrencies.
    - johnthescott 5y ago
      which well known 256 bit hash is broken?
      - jagger27 5y ago
        Let’s assume you’re right and the crypto itself is sound. I agree that is likely and doubt any TLAs have a significant mathematical edge. Does the NSA just stop there and call it a day? No, of course they write Stuxnet. They attack everything else. What well known piece of software isn’t broken?
        SnowHill9902 5y ago
        FreeBSD?
        jagger27 5y ago
        I think you mean OpenBSD. From their homepage: > Only two remote holes in the default install, in a heck of a long time! FreeBSD, not so much. https://www.cvedetails.com/vulnerability-list/vendor_id-6/product_id-7/Freebsd-Freebsd.html https://www.cvedetails.com/vulnerability-list/vendor_id-6/pr...
        staticassertion 5y ago
        Keep in mind that openbsd has a tiny base install, so it's not exactly surprising that there aren't a lot of remote exploits. Nothing's listening by default, so why would there be? By the time you set up OpenBSD to do anything, that's gonna change.
        jagger27 5y ago
        Indeed. “Default install” is a big asterisk.
      - SnowHill9902 5y ago
shapefrog 5y ago
Decrypting against leaked / found private keys is likely the path for now - but on the infinite timeline - 100% will be decryptable.

po1nt 5y ago

It's hard for me to comprehend simple asymmetric encryption let alone understand how this solution is quantum proof. Everytime I read something like this I wonder if I'll ever catch up with the times.

floatboth 5y ago
IIUC, NTRU is only "quantum proof" because there is no (publicly known) quantum algorithm for breaking it, while there is Shor's for everything discrete logarithm based (both RSA and elliptic curve anything).
- bawolff 5y ago
  Until we prove P!=NP that (i.e. its only secure because we dont know how to solve it) is pretty much true of all crypto algorithms, even classically.
  - gpm 5y ago
    This is true, but we don't know even more for quantum computers, because we have spent a lot less time studying quantum algorithms, so not yet having found an algorithm is much weaker evidence that the algorithm doesn't exist.
0xdeadb00f 5y ago
I can understand Curve25519, Diffie-Hellman, but lattice-based crypto goes way over my head.
eximius 5y ago
I have a really old (college) implementation of plain old NTRU in Python, if you'd like a little insight into what NTRU is and how it works at a superficial level (kind of like how RSA is never textbook RSA). There are also some slides explaining the math, but you have to be comfortable with some college level group theory (even reading my own slides is hard because I haven't used it since then). The short answer is that NTRU uses convolution polynomial lattices. Breaking the cryptosystem requires finding a "short" basis for a lattice described by the private key. There are efficient algorithms for this in R^2, but not for high dimensional convolutional polynomial spaces (LLL Reduction is the best I'm aware of, which is greater than O(d^5) where d is the number of dimensions https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...). Do note the impl I did is absolutely terrible and probably subtly buggy but might get the idea across. Also, it splits the message into blocks and encrypts that instead of just wrapping a symmetric encryption algorithm because I was young and naive. :) https://github.com/logannc/pyNTRUEncrypt https://github.com/logannc/pyNTRUEncrypt

_vdpp 5y ago

Am I alone in wondering if quantum attacks on existing algorithms are still very hypothetical and may never come to fruition?

klyrs 5y ago
Folks in quantum computing seem to think that's it's a near-certainty, "just an engineering problem." As long as you don't ask for a specific timeline, they won't even lie.
staticassertion 5y ago
The "Too Much Crypto" paper is pretty reasoned. See section 5.2, and 5.2.3 - "Should we care?"
- staticassertion 5y ago
  I forgot to link it... https://eprint.iacr.org/2019/1492.pdf https://eprint.iacr.org/2019/1492.pdf

vzaliva 5y ago

It mentions only "key exchange method". Does it mean we can keep our old keys or it requires different types of keys to be used?

sz3 5y ago
Different keys. For example, you might currently be using a public/private keypair for 4096-bit RSA. That keypair (by definition) only works for the RSA key exchange algorithm. Likewise, an x22519 keypair is for the x25519 key exchange. A sntrup761x25519 keypair will be its own thing. As an aside, a sntrup761x25519 public key will be two public keys glued together (one for each algorithm). [1] Likewise for the private key. (one could reuse an existing x25519 keypair for the x25519 component of sntrup761x25519, but it seems like a bad idea) [1] https://github.com/openssh/openssh-portable/blob/master/kexsntrup761x25519.c#L42-L70 https://github.com/openssh/openssh-portable/blob/master/kexs...
- ttybird2 5y ago
  Same keys, servers and clients will keep using their ed25519 keys for authenticating each other, the keys for the key exchange are negotiated on login.
  - sz3 5y ago
    Huh! Thanks for the correction. That makes a lot of sense -- I have some more reading to do...

pabs3 5y ago

There is a comment on LWN saying that the addition of NTRU Prime for PQC is a little premature: https://lwn.net/Articles/890788/ https://lwn.net/Articles/890788/ > The addition of NTRU Prime for PQC is a little premature, because a new paper just came out which showed that many LWE schemes are weaker than was previously thought. The paper admits that it is not directly applicable to NTRU (which is not an LWE scheme), but it might be adaptable to it. > https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4c... > https://doi.org/10.5281/zenodo.6412487 https://doi.org/10.5281/zenodo.6412487 > > NTRU-based cryptosystems are among the leading candidates for lattice-based post-quantum cryptography. In this work, we propose improvements to the dual attack on LWE, and as such our attack is not immediately applicable to NTRU-based cryptosystems. It is an interesting question whether ideas from this work can be adapted to similar improvements to attacks on NTRU. Specifically, there appear to be similarities between the dual attack on LWE and the so-called “hybrid attack” [How07, Wun16] on NTRU. The hybrid attack also involves enumerating over parts of the secret, and then invoking some distinguisher to determine whether a resulting vector is close to a certain constant lattice. It seems reasonable to the writers of this paper that ideas similar to those presented here can be used to reduce the running time of such attacks as well, though anything definitive would of course require further research.

nullc 5y ago
It's pretty easy for openssh to change kex ciphers-- they're not used for persistent keys, and they're negotiated every session. How many more years should it go with no attempt at resisting future decryption by quantum computers just for the sake of potentially keeping the surface of legacy ciphers that would need to be carried around one entry shorter, should it become necessary to replace this cipher? I think instead, it could be easily argued that it was long past due: it could have been deployed several years ago. The security story for lattice crypto will probably remain dubious for the forseeable future (unless it gets converted to outright broken). But on desktop computers and servers lattice crypto is so cheap that most applications can just throw it in just-in-case. Unfortunately, the obvious alternatives like code base crypto have operating costs that make them harder to justify on a just-in-case basis.