7 ms·

Amongst the numerous reasons why you _don't_ want to rush into implementing new algorithms is even the _reference implementation_ (and most other early implemen

by dhx 11mo ago

Amongst the numerous reasons why you _don't_ want to rush into implementing new algorithms is even the _reference implementation_ (and most other early implementations) for Kyber/ML-KEM included multiple timing side channel vulnerabilities that allowed for key recovery.[1][2] djb has been consistent in view for decades that cryptography standards need to consider the foolproofness of implementation so that a minor implementation mistake specific to timing of specific instructions on specific CPU architectures, or specific compiler optimisations, etc doesn't break the implementation. See for example the many problems of NIST P-224/P-256/P-384 ECC curves which djb has been instrumental in fixing through widespread deployment of X25519.[3][4][5] [1] https://cryspen.com/post/ml-kem-implementation/ https://cryspen.com/post/ml-kem-implementation/ [2] https://kyberslash.cr.yp.to/faq.html https://kyberslash.cr.yp.to/faq.html / https://kyberslash.cr.yp.to/libraries.html https://kyberslash.cr.yp.to/libraries.html [3] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Constant_time_Montgomery_ladder https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic... [4] https://safecurves.cr.yp.to/ladder.html https://safecurves.cr.yp.to/ladder.html [5] https://cr.yp.to/newelliptic/nistecc-20160106.pdf https://cr.yp.to/newelliptic/nistecc-20160106.pdf

Foxboron 11mo ago
> See for example the many problems of NIST P-224/P-256/P-384 ECC curves What are those problems exactly? The whitepaper from djb only makes vague claims about NSA being a malicious actor, but after ~20 years no known backdoors nor intentional weaknesses has been reliably proven?
- supernetworks_ 11mo ago
  It would be wise for people to remember that it’s worth doing basic sanity checks before making claims like no backdoors from the NSA. strong encryption has been restricted historically so we had things like DES and 3DES and Crypto AG. In the modern internet age juniper has a bad time with this one https://www.wired.com/2013/09/nsa-backdoor/ https://www.wired.com/2013/09/nsa-backdoor/. Usually it’s really hard to distinguish intent, and so it’s possible to develop plausible deniability with committees. Their track record isn’t perfect. With WPA3 cryptographers warned about the known pitfall of standardizing a timing sensitive PAKE, and Harkin got it through anyway. Since it was a standard, the WiFi committee gladly selected it anyway, and then resulted in dragonbleed among other bugs. The techniques for hash2curve have patched that
  - UltraSane 11mo ago
    The NSA changed the S-boxes in DES and this made people suspicious they had planted a back door but then when differential cryptanalysis was discovered people realized that the NSA changes to S-boxes made them more secure against it.
    - timschmidt 11mo ago
      That was 50 years ago. And since then we have an NSA employee co-authoring the paper which led to Heartbleed, the backdoor in Dual EC DRBG which has been successfully exploited by adversaries, and documentation from Snowden which confirms NSA compromise of standards setting committees.
      - aw1621107 11mo ago
        > And since then we have an NSA employee co-authoring the paper which led to Heartbleed I'm confused as to what "the paper which led to Heartbleed" means. A paper proposing/describing the heartbeat extension? A paper proposing its implementation in OpenSSL? A paper describing the bug/exploit? Something else? And in addition to that, is there any connection between that author and the people who actually wrote the relevant (buggy) OpenSSL code? If the people who wrote the bug were entirely unrelated to the people authoring the paper then it's not clear to me why any blame should be placed on the paper authors.
        timschmidt 11mo ago
        > I'm confused The original paper which proposed the OpenSSL Heartbeat extension was written by two people, one worked for NSA and one was a student at the time who went on to work for BND, the "German NSA". The paper authors also wrote the extension. I know this because when it happened, I wanted to know who was responsible for making me patch all my servers, so I dug through the OpenSSL patch stream to find the authors.
        aw1621107 11mo ago
- chc4 11mo ago
  They're vulnerable to "High-S" malleable signatures, while ed25519 isn't. No one is claiming they're backdoored (well, some people somewhere probably are), but they do have failure modes that ed25519 doesn't which is the GP's point.
- crote 11mo ago
  As I understand it, a big issue is that they are really hard to implement correctly. This means that backdoors and weaknesses might not exist in the theoretical algorithm, but still be common in real-world implementations. On the other hand, Curve25519 is designed from the ground up to be hard to implement incorrectly: there are very few footguns, gotchas, and edge cases. This means that real-world implementations are likely to be correct implementations of the theoretical algorithm. This means that, even if P-224/P-256/P-384 are on paper exactly as secure as Curve25519, they could still end up being significantly weaker in practice.
  - bigbadfeline 11mo ago
    > As I understand it, a big issue is that they are really hard to implement correctly. Any reference for the "really hard" part? That is a very interesting subject and I can't imagine it's independent of the environment and development stack being used. I'd welcome any standard that's "really hard to implement correctly" as a testbed for improving our compilers and other tools.
    - vessenes 11mo ago
      I posted above, but most of the 'really hard' bits come from the unreasonable complexity of actual computing vs the more manageable complexity of computing-with-idealized-software. That is, an algorithm and compiler and tool safety smoke test and improvement thereby is good. But you also need to think hard about what happens when someone induces an RF pulse at specific timings targeted at a certain part of a circuit board, say, when you're trying to harden these algorithmic implementations. Lots of things that compiler architects typically say is "not my problem".
  - tptacek 11mo ago
    I tried to defend a similar argument in a private forum today and basically got my ass handed to me. In practice, not only would modern P-curve implementations not be "significantly weaker" than Curve25519 (we've had good complete addition formulas for them for a long time, along with widespread hardware support), but Curve25519 causes as many (probably more) problems than it solves --- cofactor problems being more common in modern practice than point validation mistakes. In TLS, Curve25519 vs. the P-curves are a total non-issue, because TLS isn't generally deployed anymore in ways that even admit point validation vulnerabilities (even if implementations still had them). That bit, I already knew, but I'd assumed ad-hoc non-TLS implementations, by random people who don't know what point validation is, might tip the scales. Turns out guess not. Again, by way of bona fides: I woke up this morning in your camp, regarding Curve25519. But that won't be the camp I go to bed in.
- vessenes 11mo ago
  in the NIST Curve arena, I think DJB's main concern is engineering implementation - from an online slide deck he published: We’re writing a document “Security dangers of the NIST curves” Focus on the prime-field NIST curves DLP news relevant to these curves? No DLP on these curves seems really hard So what’s the problem? Answer: If you implement the NIST curves, chances are you’re doing it wrong Your code produces incorrect results for some rare curve points Your code leaks secret data when the input isn’t a curve point Your code leaks secret data through branch timing Your code leaks secret data through cache timing Even more trouble in smart cards: power, EM, etc. Theoretically possible to do it right, but very hard Can anyone show us software for the NIST curves done right? As to whether or not the NSA is a strategic adversary to some people using ECC curves, I think that's right in the mandate of the org, no? If a current standard is super hard to implement, and theoretically strong at the same time, that has to make someone happy on a red team. At least, it would make me happy, if I were on such a red team.
  - tptacek 11mo ago
    He does a motte-and-bailey thing with the P-curves. I don't know if it's intentional or not. Curve25519 was a materially important engineering advance over the state of the art in P-curve implementations when it was introduced. There was a window of time within which Curve25519 foreclosed on Internet-exploitable vulnerabilities (and probably a somewhat longer period of time where it foreclosed on some embedded vulnerabilities). That window of time has pretty much closed now, but it was real at the time. But he also does a handwavy thing about how the P-curves could have been backdoored. No practicing cryptgraphy engineer I'm aware of takes these arguments seriously, and to buy them you have to take Bernstein's side over people like Neil Koblitz. The P-curve backdoor argument is unserious, but the P-curve implementation stuff has enough of a solid kernel to it that he can keep both arguments alive.
    - cryptonector 11mo ago
      Quite true, but the Dual_EC backdoor claim is serious. DJB's point that we should design curves with "nothing up my sleeve" is a nice touch.
- cryptonector 11mo ago
  Dual_EC's backdoor can't be proven, but it's almost certainly real.
glitchc 11mo ago
This logic does not follow. Your argument seems to be "the implementation has security bugs, so let's not ratify the standard." That's not how standards work though. Ensuring an implementation is secure is part of the certification process. As long as the scheme itself is shown to be provably secure, that is sufficient to ratify a standard. If anything, standardization encourages more investment, which means more eyeballs to identify and plug those holes.
- arccy 11mo ago
  this is like saying just use C and don't write any memory bugs. possible, but life could be a lot better if it weren't so easy to do so.
  - johncolanduoni 11mo ago
    Great, you’ve just convinced every C programmer to use a hand rolled AES implementation on their next embedded device. Only slightly joking.
    - rvba 11mo ago
      If the standard had clear algorhitm -> source code, thrn couldnt everyone copy from there though?
      - johncolanduoni 11mo ago
        AES is actually a good example of why this doesn’t work in cryptography. Implementing AES without a timing side channel in C is pretty much impossible. Each architecture requires specific and subtle constructions to ensure it executes in constant time. Newer algorithms are designed to not have this problem (DJB was actually the one who popularized this approach).
        tptacek 11mo ago
        Reconcile this claim with, for instance, aes_ct64 in Thomas Pornin's BearSSL? I'm familiar with Bernstein's argument about AES, but AES is also the most successful cryptography standard ever created.
mpyne 11mo ago
Given the emphasis on reliability of implementations of an algorith, it's ironic that the Curve 25519-based Ed25519 digital signature standard was itself specified and originally implemented in such a way as to lead to implementation divergence on what a valid and invalid signature actually was. See https://hdevalence.ca/blog/2020-10-04-its-25519am/ https://hdevalence.ca/blog/2020-10-04-its-25519am/ Not a criticism, if anything it reinforces DJB's point. But it makes clear that ease of (proper) implementation also needs to cover things like proper canonicalization of relevant security variables and that supporting multiple modes of operation doesn't actually lead to different answers of security questions meant to give the same answer.

by dhx 11mo ago

Foxboron 11mo ago

> See for example the many problems of NIST P-224/P-256/P-384 ECC curves What are those problems exactly? The whitepaper from djb only makes vague claims about NSA being a malicious actor, but after ~20 years no known backdoors nor intentional weaknesses has been reliably proven?

supernetworks_ 11mo ago
It would be wise for people to remember that it’s worth doing basic sanity checks before making claims like no backdoors from the NSA. strong encryption has been restricted historically so we had things like DES and 3DES and Crypto AG. In the modern internet age juniper has a bad time with this one https://www.wired.com/2013/09/nsa-backdoor/ https://www.wired.com/2013/09/nsa-backdoor/. Usually it’s really hard to distinguish intent, and so it’s possible to develop plausible deniability with committees. Their track record isn’t perfect. With WPA3 cryptographers warned about the known pitfall of standardizing a timing sensitive PAKE, and Harkin got it through anyway. Since it was a standard, the WiFi committee gladly selected it anyway, and then resulted in dragonbleed among other bugs. The techniques for hash2curve have patched that
- UltraSane 11mo ago
  The NSA changed the S-boxes in DES and this made people suspicious they had planted a back door but then when differential cryptanalysis was discovered people realized that the NSA changes to S-boxes made them more secure against it.
  - timschmidt 11mo ago
    That was 50 years ago. And since then we have an NSA employee co-authoring the paper which led to Heartbleed, the backdoor in Dual EC DRBG which has been successfully exploited by adversaries, and documentation from Snowden which confirms NSA compromise of standards setting committees.
    - aw1621107 11mo ago
      > And since then we have an NSA employee co-authoring the paper which led to Heartbleed I'm confused as to what "the paper which led to Heartbleed" means. A paper proposing/describing the heartbeat extension? A paper proposing its implementation in OpenSSL? A paper describing the bug/exploit? Something else? And in addition to that, is there any connection between that author and the people who actually wrote the relevant (buggy) OpenSSL code? If the people who wrote the bug were entirely unrelated to the people authoring the paper then it's not clear to me why any blame should be placed on the paper authors.
      - timschmidt 11mo ago
        > I'm confused The original paper which proposed the OpenSSL Heartbeat extension was written by two people, one worked for NSA and one was a student at the time who went on to work for BND, the "German NSA". The paper authors also wrote the extension. I know this because when it happened, I wanted to know who was responsible for making me patch all my servers, so I dug through the OpenSSL patch stream to find the authors.
        aw1621107 11mo ago
chc4 11mo ago
They're vulnerable to "High-S" malleable signatures, while ed25519 isn't. No one is claiming they're backdoored (well, some people somewhere probably are), but they do have failure modes that ed25519 doesn't which is the GP's point.
crote 11mo ago
As I understand it, a big issue is that they are really hard to implement correctly. This means that backdoors and weaknesses might not exist in the theoretical algorithm, but still be common in real-world implementations. On the other hand, Curve25519 is designed from the ground up to be hard to implement incorrectly: there are very few footguns, gotchas, and edge cases. This means that real-world implementations are likely to be correct implementations of the theoretical algorithm. This means that, even if P-224/P-256/P-384 are on paper exactly as secure as Curve25519, they could still end up being significantly weaker in practice.
- bigbadfeline 11mo ago
  > As I understand it, a big issue is that they are really hard to implement correctly. Any reference for the "really hard" part? That is a very interesting subject and I can't imagine it's independent of the environment and development stack being used. I'd welcome any standard that's "really hard to implement correctly" as a testbed for improving our compilers and other tools.
  - vessenes 11mo ago
    I posted above, but most of the 'really hard' bits come from the unreasonable complexity of actual computing vs the more manageable complexity of computing-with-idealized-software. That is, an algorithm and compiler and tool safety smoke test and improvement thereby is good. But you also need to think hard about what happens when someone induces an RF pulse at specific timings targeted at a certain part of a circuit board, say, when you're trying to harden these algorithmic implementations. Lots of things that compiler architects typically say is "not my problem".
- tptacek 11mo ago
  I tried to defend a similar argument in a private forum today and basically got my ass handed to me. In practice, not only would modern P-curve implementations not be "significantly weaker" than Curve25519 (we've had good complete addition formulas for them for a long time, along with widespread hardware support), but Curve25519 causes as many (probably more) problems than it solves --- cofactor problems being more common in modern practice than point validation mistakes. In TLS, Curve25519 vs. the P-curves are a total non-issue, because TLS isn't generally deployed anymore in ways that even admit point validation vulnerabilities (even if implementations still had them). That bit, I already knew, but I'd assumed ad-hoc non-TLS implementations, by random people who don't know what point validation is, might tip the scales. Turns out guess not. Again, by way of bona fides: I woke up this morning in your camp, regarding Curve25519. But that won't be the camp I go to bed in.
vessenes 11mo ago
in the NIST Curve arena, I think DJB's main concern is engineering implementation - from an online slide deck he published: We’re writing a document “Security dangers of the NIST curves” Focus on the prime-field NIST curves DLP news relevant to these curves? No DLP on these curves seems really hard So what’s the problem? Answer: If you implement the NIST curves, chances are you’re doing it wrong Your code produces incorrect results for some rare curve points Your code leaks secret data when the input isn’t a curve point Your code leaks secret data through branch timing Your code leaks secret data through cache timing Even more trouble in smart cards: power, EM, etc. Theoretically possible to do it right, but very hard Can anyone show us software for the NIST curves done right? As to whether or not the NSA is a strategic adversary to some people using ECC curves, I think that's right in the mandate of the org, no? If a current standard is super hard to implement, and theoretically strong at the same time, that has to make someone happy on a red team. At least, it would make me happy, if I were on such a red team.
- tptacek 11mo ago
  He does a motte-and-bailey thing with the P-curves. I don't know if it's intentional or not. Curve25519 was a materially important engineering advance over the state of the art in P-curve implementations when it was introduced. There was a window of time within which Curve25519 foreclosed on Internet-exploitable vulnerabilities (and probably a somewhat longer period of time where it foreclosed on some embedded vulnerabilities). That window of time has pretty much closed now, but it was real at the time. But he also does a handwavy thing about how the P-curves could have been backdoored. No practicing cryptgraphy engineer I'm aware of takes these arguments seriously, and to buy them you have to take Bernstein's side over people like Neil Koblitz. The P-curve backdoor argument is unserious, but the P-curve implementation stuff has enough of a solid kernel to it that he can keep both arguments alive.
  - cryptonector 11mo ago
    Quite true, but the Dual_EC backdoor claim is serious. DJB's point that we should design curves with "nothing up my sleeve" is a nice touch.
cryptonector 11mo ago
Dual_EC's backdoor can't be proven, but it's almost certainly real.

glitchc 11mo ago

This logic does not follow. Your argument seems to be "the implementation has security bugs, so let's not ratify the standard." That's not how standards work though. Ensuring an implementation is secure is part of the certification process. As long as the scheme itself is shown to be provably secure, that is sufficient to ratify a standard. If anything, standardization encourages more investment, which means more eyeballs to identify and plug those holes.

arccy 11mo ago
this is like saying just use C and don't write any memory bugs. possible, but life could be a lot better if it weren't so easy to do so.
- johncolanduoni 11mo ago
  Great, you’ve just convinced every C programmer to use a hand rolled AES implementation on their next embedded device. Only slightly joking.
  - rvba 11mo ago
    If the standard had clear algorhitm -> source code, thrn couldnt everyone copy from there though?
    - johncolanduoni 11mo ago
      AES is actually a good example of why this doesn’t work in cryptography. Implementing AES without a timing side channel in C is pretty much impossible. Each architecture requires specific and subtle constructions to ensure it executes in constant time. Newer algorithms are designed to not have this problem (DJB was actually the one who popularized this approach).
      - tptacek 11mo ago
        Reconcile this claim with, for instance, aes_ct64 in Thomas Pornin's BearSSL? I'm familiar with Bernstein's argument about AES, but AES is also the most successful cryptography standard ever created.

mpyne 11mo ago

Given the emphasis on reliability of implementations of an algorith, it's ironic that the Curve 25519-based Ed25519 digital signature standard was itself specified and originally implemented in such a way as to lead to implementation divergence on what a valid and invalid signature actually was. See https://hdevalence.ca/blog/2020-10-04-its-25519am/ https://hdevalence.ca/blog/2020-10-04-its-25519am/ Not a criticism, if anything it reinforces DJB's point. But it makes clear that ease of (proper) implementation also needs to cover things like proper canonicalization of relevant security variables and that supporting multiple modes of operation doesn't actually lead to different answers of security questions meant to give the same answer.