3 ms·

I don't think that's the thesis. I think the thesis is that there could be a "BADA55 construction" even in Curve25519. Even though all of the individual pieces

by fryguy 11y ago

I don't think that's the thesis. I think the thesis is that there could be a "BADA55 construction" even in Curve25519. Even though all of the individual pieces are justifiable, for instance the 2^255-19 is justifiable because it's the smallest number. They knew the entire curve before trying to make it popular. Also, they could have used 2^255+95 because it's the smallest larger than 2^255 with some justification that it needed to be larger than 2^255. With enough arbitrary decisions a "one-in-a-million" vulnerability is possible. The premise of this curve is that there are no arbitrary decisions, since you commit to supporting the curve before even knowing what it is. I think the analogy is someone shuffling a deck of cards, and taking a peek at the first card. Then betting someone $20 that it's the ace of spades. The process is justifiable, because you don't have any control of what the top card happens to be. It's just that you know what card it is and wouldn't make the bet if you didn't know it was already an ace of spades. Similarly, Curve25519 might have been constructed and happened to have the "one-in-a-million" vulnerability. How many other "Curve25519s" are there that we didn't hear about. Imagine that instead, the procedure was shuffle the cards after you commit to the bet. I really doubt there's anything wrong with 25519. I feel like if anything, if djb et al knew about some vulnerability in curves that 25519 happened to have before releasing it, they would have put the weakness as one of the failing criteria to pick a new set of parameters.

tptacek 11y ago
I'm pretty sure the authors aren't suggesting that Curve25519 has been tampered with, because the FAQ for this paper suggests (a) that they continue to recommend Curve25519, and (b) that they are proposing this curve because they're concerned that there aren't any good alternatives to Curve25519 with trustworthy seeds. Curve25519 follows roughly the same generation procedure as Microsoft's NUMS: it uses minimal parameters that satisfy a performance/security goal. NUMS starts from a security level, selects the smallest prime that satisfies that level, and then selects the smallest Edwards 'd' that passes security criteria. Curve25519 selects a prime of sufficient security as close as possible to a power of 2 (making it sparse and thus fast to do math on in software), and then selects a minimal Montgomery A given security criteria. $1MM and 25519 represent two different schools of thought about how to generate curves. $1MM says, generate random unstructured parameters, and come up with a randomness procedure that is difficult to impeach. 25519 says generate minimal parameters that achieve particular performance goals. Both schools of thought address the concern that the curve generation procedure might be untrustworthy, but in different ways: the former by somehow proving randomness, the latter by removing degrees of freedom. 25519's school of thought has pretty much won the Internet.
- sarciszewski 11y ago
  I really appreciate the level-headed discussion in this thread so far, especially the comment I'm replying to. It's a stark contrast to the CFRG mailing list. (At least, so far, no one has tried to derail discussion here with "hey check out my custom cipher it's soooo secure but you need to compress the data before encrypting it or else you can observe a repeated structure out of it".) I like 25519's school of thought. If you use the smallest possible value for a given performance/security goal, there's less room for conspiracy theory (provided the person making the theory understands what's even going on).

by fryguy 11y ago

tptacek 11y ago

I'm pretty sure the authors aren't suggesting that Curve25519 has been tampered with, because the FAQ for this paper suggests (a) that they continue to recommend Curve25519, and (b) that they are proposing this curve because they're concerned that there aren't any good alternatives to Curve25519 with trustworthy seeds. Curve25519 follows roughly the same generation procedure as Microsoft's NUMS: it uses minimal parameters that satisfy a performance/security goal. NUMS starts from a security level, selects the smallest prime that satisfies that level, and then selects the smallest Edwards 'd' that passes security criteria. Curve25519 selects a prime of sufficient security as close as possible to a power of 2 (making it sparse and thus fast to do math on in software), and then selects a minimal Montgomery A given security criteria. $1MM and 25519 represent two different schools of thought about how to generate curves. $1MM says, generate random unstructured parameters, and come up with a randomness procedure that is difficult to impeach. 25519 says generate minimal parameters that achieve particular performance goals. Both schools of thought address the concern that the curve generation procedure might be untrustworthy, but in different ways: the former by somehow proving randomness, the latter by removing degrees of freedom. 25519's school of thought has pretty much won the Internet.

sarciszewski 11y ago
I really appreciate the level-headed discussion in this thread so far, especially the comment I'm replying to. It's a stark contrast to the CFRG mailing list. (At least, so far, no one has tried to derail discussion here with "hey check out my custom cipher it's soooo secure but you need to compress the data before encrypting it or else you can observe a repeated structure out of it".) I like 25519's school of thought. If you use the smallest possible value for a given performance/security goal, there's less room for conspiracy theory (provided the person making the theory understands what's even going on).