Re: [TLS] Safe ECC usage

[Dan Brown <[e-mail]>]

> D. J. Bernstein writes
> 
> Dan Brown writes:
> > Brainpool and RFC 5639 recommends pseudo-random parameters to avoid
> > unanticipated attacks, and you are arguing against this
> recommendation
> > by anticipating from known attacks.
> 
> No, and no.
> 
> The Brainpool standard (from which RFC 5639 is derived) says that the
> unexplained NIST seeds leave "an essential part of the security
> analysis open" and that this is a "major issue." I completely agree
> with this.
> 
> There are two reasonable ways to address this problem. One way, which
> Brainpool uses, is to generate curves "in a pseudo-random manner using
> seeds that are generated in a systematic and comprehensive way,"
> subject of course to other requirements. Another way, which I use, is
> to take the smallest possible curves meeting the other requirements.

[DB] Yes. Security requirement 5 says "verifiably pseudo-random ..." and
then refers to Section 5, where it is applied to the field size p.  Earlier
it noted that existing field sizes are all "special".  As you noted, using a
random prime instead of a special one incurs a computational cost.  So, I
think I was reasonable to infer that Brainpool was implying that special
fields were lacking in security.  (The implication against special values
may then be inferred further.)  But now, I notice that the Brainpool
document gives another reason to avoid special fields, so your
interpretation is more reasonable than mine. 

> 
> Both of these approaches are clear improvements over what NIST/NSA did.

[DB] Not disputing that.  All they had to do was reveal how their seeds were
generated.

> As Brainpool puts it, choosing fully explained seeds will "enhance
> trust in the recommended curves." Choosing smallest curves has the same
> effect. There's no contradiction between these statements.
> 
[DB] I am not asking whether anybody trusts which curve.  I am asking for
formal claims of security, even ones that contain an unknown variable.

> There is zero reason to believe that either of these approaches is more
> secure than the other. There is, in particular, zero reason to believe
> that either approach is safer against "unanticipated attacks." You are
> wrong to attribute any such belief to the Brainpool standard; the
> document says no such thing. All available evidence is that both
> approaches are fine; if we've missed an attack then we have no way to
> guess whether the attack is more likely to apply to one curve or to the
> other.

[DB] No.  

This is the essence of what I've been trying to say about Curve25519 being
special.  I will try again.  

Assume we trust the verifiably pseudo-random generation algorithms.  Then we
have a proof that Brainpool are invulnerable to the "missed attack" with
probability equal to the density of the vulnerable curves.  We have no such
proof for special curves such as Curve25519, because we do not know the
nature of the missed attack.

We cannot assume that a missed attack will render a uniformly random set of
vulnerable curves.

You provided valid arguments in favour of Curve25519 if the missed attacks
are similar to known attacks, with which I agree, but that does not go as
far as the Brainpool.

Therefore, in terms of security, Brainpool >~ Curve25519 >> P256, if we
posit missed EC attacks and trust hash functions, else Brainpool ==
Curve25519 == P256 if not.  (I'm using >~ for slightly better, and >> for
considerably better.)

> 
> My reason for not taking the Brainpool approach is that it has a rather
> heavy cost. We have enough problems deploying secure crypto without
> incurring unnecessary costs; if we can afford extra costs then I'd
> rather put those into taking steps that actually matter for security,
> such as adding defenses against quantum computers. So I prefer the
> second approach. Conversely, Brainpool does not discuss the second
> approach, and does not state any reason to avoid the approach.
> 

[DB] Agreed, to this end, I just want to quantify the security gains, so the
cost-benefit analysis can be better formalized.

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.