3 ms·

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

36 points by Sami_Lehtinen 4y ago

olliej 4y ago
There are some minor errors and omissions in this article, but honestly with the exception of the OpenSSL/sshd/etc stuff at the end it does a reasonable job of providing a lay explanation of the core problem with existing cryptography. You could possibly make it more accurate by saying “with clock arithmetic”, but I simply don’t think that adds enough to the “correctness” side to warrant the complexity it adds. It also provides a reasonable explanation of the slowness of standards development - again for the layperson, it isn’t perfect. Seriously if there was version that stripped out the OpenSSL integration of a PQC algorithm it would be a nice article to point some non-tech friend or family member, etc to.
politelemon 4y ago
> 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. I believe they'll have to start on it now, or hopefully they have already started on including others. NIST have already announced some finalists. Kyber, Dilithium, Falcon and Sphincs+. NTRU Prime was a third round candidate but didn't make it to the finals. It isn't a fourth round candidate either. https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4 https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standar...
- truffdog 4y ago
  The report is pretty interesting- > The NTRU Prime submission [60], which consists of two structured-lattice-based cryp- tosystems, was first proposed in [231] as an exploration of the design space of “NTRU- like” cryptosystems, with the goal of reducing the attack surface with only minor loss of efficiency. Design. NTRU Prime has several unusual design features. It has two variants: Streamlined NTRU Prime, which is modeled after the original NTRU, and NTRU LPRime, which com- bines some aspects of NTRU with some aspects of Ring-LWE cryptosystems (in the style of Lyubashevsky-Peikert-Regev [150]). In addition, NTRU Prime is constructed over a dif- ferent ring: the “NTRU Prime ring,” Zq[x]/(x p −x−1). Finally, certain key parts of NTRU Prime are designed to operate deterministically (e.g., using rounding rather than random noise and eliminating the possibility of random decryption failures). The submitters have argued that these features improve the security of the scheme. Security. The current version of NTRU Prime has performance and concrete security es- timates (e.g., quantitative estimates of the computational resources required for usage and cryptanalysis) that are roughly comparable to other lattice-based cryptosystems.13 As a result, the current version of NTRU Prime is notable more for its unusual design features, and claims that it offers higher security in a qualitative sense. In order to state these claims, the designers of NTRU Prime have advocated for a spe- cific approach to security analysis, based on a taxonomy of security risks [15]. This taxon- omy is used to justify various design decisions, such as using rounding rather than random noise, and eliminating the possibility of decryption failures. However, some care is needed when reading this taxonomy, as it is a matter of subjective judgement which risks are the most serious and what is the best way of mitigating those risks. One particular issue is the choice of the NTRU Prime ring (rather than a cyclotomic ring), which is claimed to eliminate the possibility of certain kinds of algebraic attacks. To date, most work on the cryptanalysis of algebraically structured lattices (see Appendix C) has focused on cyclotomic rings, because they are widely used and simpler to analyze. Relatively little is known about the security of cryptographic schemes that use the NTRU Prime ring. ... > Overall assessment. The case for NTRU Prime relies substantially on the claim that its unusual choice of ring provides a security benefit over the algebraic structures used by the other lattice candidates, i.e., the claim that (1) there is likely to be an attack that signifi- cantly diminishes the security of NTRU, KYBER, and Saber, and (2) no similar attack is likely to affect NTRU Prime. At the end of the third round, the evidence for these two points is not particularly convincing. No algebraic attack has been published that directly impacts the concrete or asymptotic security of any of the third-round structured lattice can- didates.14 From a practical perspective, it seems likely that an unexpected breakthrough in cryptanalysis of any structured lattice scheme would reduce the community’s confidence in all such schemes, including NTRU Prime. For these reasons, NIST is not moving NTRU Prime to the fourth round of the evalua- tion process. In order to hedge against the possibility of a security vulnerability involving structured lattice KEMs, NIST will consider standardizing a KEM that is not based on lattices, after a fourth round of evaluation.

36 points by Sami_Lehtinen 4y ago

There are some minor errors and omissions in this article, but honestly with the exception of the OpenSSL/sshd/etc stuff at the end it does a reasonable job of providing a lay explanation of the core problem with existing cryptography. You could possibly make it more accurate by saying “with clock arithmetic”, but I simply don’t think that adds enough to the “correctness” side to warrant the complexity it adds. It also provides a reasonable explanation of the slowness of standards development - again for the layperson, it isn’t perfect. Seriously if there was version that stripped out the OpenSSL integration of a PQC algorithm it would be a nice article to point some non-tech friend or family member, etc to.

politelemon 4y ago

> 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. I believe they'll have to start on it now, or hopefully they have already started on including others. NIST have already announced some finalists. Kyber, Dilithium, Falcon and Sphincs+. NTRU Prime was a third round candidate but didn't make it to the finals. It isn't a fourth round candidate either. https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4 https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standar...

truffdog 4y ago
The report is pretty interesting- > The NTRU Prime submission [60], which consists of two structured-lattice-based cryp- tosystems, was first proposed in [231] as an exploration of the design space of “NTRU- like” cryptosystems, with the goal of reducing the attack surface with only minor loss of efficiency. Design. NTRU Prime has several unusual design features. It has two variants: Streamlined NTRU Prime, which is modeled after the original NTRU, and NTRU LPRime, which com- bines some aspects of NTRU with some aspects of Ring-LWE cryptosystems (in the style of Lyubashevsky-Peikert-Regev [150]). In addition, NTRU Prime is constructed over a dif- ferent ring: the “NTRU Prime ring,” Zq[x]/(x p −x−1). Finally, certain key parts of NTRU Prime are designed to operate deterministically (e.g., using rounding rather than random noise and eliminating the possibility of random decryption failures). The submitters have argued that these features improve the security of the scheme. Security. The current version of NTRU Prime has performance and concrete security es- timates (e.g., quantitative estimates of the computational resources required for usage and cryptanalysis) that are roughly comparable to other lattice-based cryptosystems.13 As a result, the current version of NTRU Prime is notable more for its unusual design features, and claims that it offers higher security in a qualitative sense. In order to state these claims, the designers of NTRU Prime have advocated for a spe- cific approach to security analysis, based on a taxonomy of security risks [15]. This taxon- omy is used to justify various design decisions, such as using rounding rather than random noise, and eliminating the possibility of decryption failures. However, some care is needed when reading this taxonomy, as it is a matter of subjective judgement which risks are the most serious and what is the best way of mitigating those risks. One particular issue is the choice of the NTRU Prime ring (rather than a cyclotomic ring), which is claimed to eliminate the possibility of certain kinds of algebraic attacks. To date, most work on the cryptanalysis of algebraically structured lattices (see Appendix C) has focused on cyclotomic rings, because they are widely used and simpler to analyze. Relatively little is known about the security of cryptographic schemes that use the NTRU Prime ring. ... > Overall assessment. The case for NTRU Prime relies substantially on the claim that its unusual choice of ring provides a security benefit over the algebraic structures used by the other lattice candidates, i.e., the claim that (1) there is likely to be an attack that signifi- cantly diminishes the security of NTRU, KYBER, and Saber, and (2) no similar attack is likely to affect NTRU Prime. At the end of the third round, the evidence for these two points is not particularly convincing. No algebraic attack has been published that directly impacts the concrete or asymptotic security of any of the third-round structured lattice can- didates.14 From a practical perspective, it seems likely that an unexpected breakthrough in cryptanalysis of any structured lattice scheme would reduce the community’s confidence in all such schemes, including NTRU Prime. For these reasons, NIST is not moving NTRU Prime to the fourth round of the evalua- tion process. In order to hedge against the possibility of a security vulnerability involving structured lattice KEMs, NIST will consider standardizing a KEM that is not based on lattices, after a fourth round of evaluation.