Subject: Re: [Cfrg] new curves or old (was: Actual security levels for IETF crypto)

From: Dan Brown <[email-masked]>
Date: Mon, 3 Nov 2014 18:14:08 +0000

To slightly clarify my yes vote:

I'm fine if we recommend two curves over the same special prime, one curve rigid/special, one curve random in some sense to be determined. Further, these two curves need not be recommended at the same time. couldn't we decide on the field and shape first: we're nearly done there,right?

I've heard a few times that whatever curve we recommend would be used for many years without much change: if so I'd want a more conservative option, which to me includes a random j-invariant. (see my email to the list on bad and rigid curves). I'm fine with having a less random option too: that's what NIST‎ did with binary-field  curves, and SECG had the secp256k1 (see BitCoin) alternative to P256. Some have said options are bad, but if we state what's different, then maybe it's good. surely each IETF protocol has an idea of their efficiency needs and the value of the info they need to protect.

Best regards, 

-- Dan
  Original Message  
From: Paterson, Kenny
Sent: Monday, November 3, 2014 11:44 AM
To: D. J. Bernstein; [email-masked]
Subject: Re: [Cfrg] new curves or old (was: Actual security levels for IETF crypto)

Hi Dan,

Indeed, there's ambiguity in your post and in the ones to which it refers.

The full and explicit intention of my question was this: do we want to
clear the table completely and generate some fresh curves according to
some to-be-agreed procedure, or not.

If the RG said "yes" to this question, then the procedure we use would be
up for discussion.

The agreed upon procedure need not involve any randomness, and it could be
one that leads to curves already on the table, which would (if we don't
cook the books in writing down the procedure!) validate the rigidity of
the process by which those curves were produced in the first place. If so,
then great, we'd have further evidence of the unimpeachability of our
recommendations.

The agreed upon procedure might involve randomness, in which case it would
be much less likely to produce curves which are currently on the table.

It would be for the RG to decide, by consensus if possible, by majority if
not, by fiat if necessary, what the procedure would be.

Cheers

Kenny 

On 03/11/2014 08:27, "D. J. Bernstein" <[email-masked]> wrote:

>Paterson, Kenny writes:
>> - Who on the list would be in favour of using a to-be-agreed procedure
>> to generate new curves
>
>There's an important ambiguity here:
>
> * Is the idea to throw away all of the current curve proposals, such
> as Curve25519 and E-521 and Microsoft's "NUMS" curves?
>
> This is clearly what Torsten Schütze's "yes" means. He says that
> the disadvantage of having to "wait" for new curves is outweighed
> by the need for "TRUST" in "the selected curves". Evidently he's
> claiming that CFRG can't trust any of the existing proposals. (If
> CFRG _does_ trust one of the proposals, then it can simply take
> that one without having to wait, so the argument makes no sense.)
>
> * Or is the idea to have CFRG pick a new curve _and_ one of the
> current curves?
>
> This is clearly what Paul Lambert's "yes" means: "Good options for
> optimized and random primes is valuable. ... ensure that there are
> well documented options for a variety of market applications." This
> is asking CFRG to pick a random-prime option _and_ to pick a faster
> option, based on the claim that having both options would provide
> benefits for applications; there's nothing here saying that the
> faster options on the table should be thrown away.
> 
> It's not as clear if this is what Benjamin Black's "yes" means. He
> advocates a "process" to "allow both random and selected primes";
> on the other hand, what he had said earlier was that he wanted to
> reject "_ALL_ current candidates in favor of CFRG generating new
> ones". I can't figure out whether he's advocating throwing away the
> "NUMS" curves, for example.
>
> Dan Brown's "yes" is even less clear. He says that he wants a
> "random" curve using a "special prime"---this part is clear enough,
> and quite different from taking a random prime---but I have no idea
> whether he's asking for this "random" curve to coexist with a
> better-optimized curve using the same prime, or to coexist with a
> better-optimized curve using a different prime, or to be the sole
> CFRG output.
>
>Apparently the motivation for some people to ask for "new curves" is
>that they want some sort of "randomness", but they can't even agree on
>what the desired "randomness" actually is (prime? curve? hashing? ...),
>and whether the resulting "random" curve is supposed to be the sole CFRG
>output or merely an extra option.
>
>My own view is that
>
> * the best curves have already been found---for example, if CFRG
> wants a curve at a stratospheric >2^250 security level, then E-521
> is the best choice;
>
> * _replacing_ these curves with other curves at similar security
> levels would be a mistake---especially if the replacements use
> random primes, forcing users down to much lower security levels for
> any particular performance level; and
>
> * _supplementing_ these curves with additional options at similar
> security levels would also be a mistake---we have enough trouble
> getting security right without this sort of distraction.
>
>Many arguments have already been given in favor of the current
>proposals, and I won't repeat those arguments here, but let me add a
>suggestion for people who think that it's possible to do better: please
>_first_ generate your curves and _then_ ask CFRG to consider them. This
>is particularly important for "random" curves:
>
> * Decades of successful attacks show that it's much, much, much
> easier to say "generate a random number" than to actually do it in
> a secure way---and that's in the easy situation of generating
> random numbers for oneself, whereas CFRG is facing the tougher
> problem of convincing third parties years later that the results
> weren't manipulated.
>
> * Brainpool claimed to have "verifiably pseudo-random curves" from
> hashing "seeds that are generated in a systematic and comprehensive
> way" as a substitute for true randomness, but we showed that more
> than a million curves could be generated with similar explanations
> (and Johannes Merkle has already admitted several bits of this
> flexibility---we can discuss the other bits if necessary).
>
> * Dan Brown said back in April that he would specify "a method to
> generate random curves (and constants)" but as far as I know he
> never followed through.
>
>It's natural to overestimate the security, simplicity, and speed of a
>solution that hasn't actually been specified yet.
>
>I realize that curves can be costly to generate (for example, quite a
>bit of CPU time was spent locating E-521, and I've heard amusing ideas
>for even more expensive curve-generation procedures), but I don't see
>any excuse for not producing scaled-down prototypes. Concrete curve
>proposals are important as a basis for comparison.
>
>---Dan
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg