5 ms·

If you look at backdoored algorithms, there are red flags all over the place. A hallmark of DJB algorithms is that they use minimal constants that satisfy publi

by habitue 11y ago

If you look at backdoored algorithms, there are red flags all over the place. A hallmark of DJB algorithms is that they use minimal constants that satisfy publicly declared constraints. If you look at the spec for DUAL_EC_DRBG, the backdoored rng standard, the first thing that you notice is that the constants have no explanation for how they were derived, and that they are large enough to hide a cryptographic key in. If DJB releases a crypto algorithm with huge glaringly unexplained constants, you'd better believe people will ask questions. I don't think it's possible to both use "nothing up your sleeve numbers"[1] and to backdoor an algorithm. You'd likely need the computing power needed to brute force the EC in the first place in order to do it. [1] https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

tptacek 11y ago
It's funny that you would say this. * During the recent CFRG curve selection debacle, Microsoft pushed for a noncompatible variant to Curve25519 (now called "PinkBikeShed") on the basis of it having minimal parameters. * One of DJB's more notorious research papers, BADA55, is about the extent to which reliance on "easily explained math constants" is not actually safe. Also: the problem with Dual_EC is that it's a public key RNG. It's a construction that has no reason to exist. The reason you don't have to worry about DJB's (or Rogaway's or Shay Gueron's or whatever) documents having the Dual_EC problem is that none of them are going to propose a public key RNG.
- habitue 11y ago
  Thanks for the pointer to BADA55, I had not seen that. Do you think it's possible for constants (selected in the way the constants for ed25519 were selected) to be backdoored ala BADA55? It seems the vulnerabilities come from using hashing algorithms on some small constant, not from the constant itself being something simply constructed. Also, it looks like DJB did alight on PinkBikeShed originally[1] but rejected it for technical reasons. (Reasons I can't evaluate myself). Is my understanding correct that the PinkBikeShed curve has more minimal parameters than ed25519, but that it doesn't satisfy all of the security criteria that ed25519 does? [1] https://www.ietf.org/mail-archive/web/cfrg/current/msg05745.html https://www.ietf.org/mail-archive/web/cfrg/current/msg05745....
  - tptacek 11y ago
    There is a very fiddly technical reason why PinkBikeShed is more user-friendly than Curve25519. Bernstein would say that it's a powerful security argument, but it's more of a nice- to- have than a must-have. Curve25519 won because it had an installed base.
    - CiPHPerCoder 11y ago
      For anyone following this part of the comment thread, the mailing list discussion about these topics is worth a read too: https://www.ietf.org/mail-archive/web/cfrg/current/msg05619.html https://www.ietf.org/mail-archive/web/cfrg/current/msg05619....
      - acqq 11y ago
        The text sketches a proof how PinkBikeShed from Microsoft is worse. He also ends with "I didn't bother writing down a comprehensive critique of PinkBikeShed, and didn't imagine that anyone would ever try to revive that curve."
        tptacek 11y ago
        It's a whole lot of sentences for a very simple difference. I think "proof" is pushing it a bit far.
        acqq 11y ago
        He wrote a lot, but it's very clear what his principles in this case are. To be constructive, other experts should either point to the principles with which they disagree or if they do agree point to the errors in his use of them.
        tptacek 11y ago
        In that argument, Microsoft would say that performance being equal, it's more important for parameters to be minimal so that the curve is maximally rigid and trustworthy. Bernstein would say that it's more important that there are no implementation pitfalls, even very subtle ones that will be hard to exploit. I agree with Bernstein but I won't pretend it's a totally cut and dried argument. What won the argument wasn't so much the merits of Bernstein's case, but that Microsoft was in effect arguing for something that would break compatibility with the 25519 installed base.
- JoachimS 11y ago
  Of all the fighting that occured last year about new curces, the MS Curve25519 initiative was the ugliest and most dishonest.

by habitue 11y ago

tptacek 11y ago

It's funny that you would say this. * During the recent CFRG curve selection debacle, Microsoft pushed for a noncompatible variant to Curve25519 (now called "PinkBikeShed") on the basis of it having minimal parameters. * One of DJB's more notorious research papers, BADA55, is about the extent to which reliance on "easily explained math constants" is not actually safe. Also: the problem with Dual_EC is that it's a public key RNG. It's a construction that has no reason to exist. The reason you don't have to worry about DJB's (or Rogaway's or Shay Gueron's or whatever) documents having the Dual_EC problem is that none of them are going to propose a public key RNG.

habitue 11y ago
Thanks for the pointer to BADA55, I had not seen that. Do you think it's possible for constants (selected in the way the constants for ed25519 were selected) to be backdoored ala BADA55? It seems the vulnerabilities come from using hashing algorithms on some small constant, not from the constant itself being something simply constructed. Also, it looks like DJB did alight on PinkBikeShed originally[1] but rejected it for technical reasons. (Reasons I can't evaluate myself). Is my understanding correct that the PinkBikeShed curve has more minimal parameters than ed25519, but that it doesn't satisfy all of the security criteria that ed25519 does? [1] https://www.ietf.org/mail-archive/web/cfrg/current/msg05745.html https://www.ietf.org/mail-archive/web/cfrg/current/msg05745....
- tptacek 11y ago
  There is a very fiddly technical reason why PinkBikeShed is more user-friendly than Curve25519. Bernstein would say that it's a powerful security argument, but it's more of a nice- to- have than a must-have. Curve25519 won because it had an installed base.
  - CiPHPerCoder 11y ago
    For anyone following this part of the comment thread, the mailing list discussion about these topics is worth a read too: https://www.ietf.org/mail-archive/web/cfrg/current/msg05619.html https://www.ietf.org/mail-archive/web/cfrg/current/msg05619....
    - acqq 11y ago
      The text sketches a proof how PinkBikeShed from Microsoft is worse. He also ends with "I didn't bother writing down a comprehensive critique of PinkBikeShed, and didn't imagine that anyone would ever try to revive that curve."
      - tptacek 11y ago
        It's a whole lot of sentences for a very simple difference. I think "proof" is pushing it a bit far.
        acqq 11y ago
        He wrote a lot, but it's very clear what his principles in this case are. To be constructive, other experts should either point to the principles with which they disagree or if they do agree point to the errors in his use of them.
        tptacek 11y ago
        In that argument, Microsoft would say that performance being equal, it's more important for parameters to be minimal so that the curve is maximally rigid and trustworthy. Bernstein would say that it's more important that there are no implementation pitfalls, even very subtle ones that will be hard to exploit. I agree with Bernstein but I won't pretend it's a totally cut and dried argument. What won the argument wasn't so much the merits of Bernstein's case, but that Microsoft was in effect arguing for something that would break compatibility with the 25519 installed base.
JoachimS 11y ago
Of all the fighting that occured last year about new curces, the MS Curve25519 initiative was the ugliest and most dishonest.