Re: [TLS] Using Brainpool curves in TLS

[Nico Williams <[e-mail]>]

On Wed, Oct 16, 2013 at 10:53 AM, Johannes Merkle
<[e-mail]> wrote:
>> Curve25519 picks the smallest value of A that meets the parameters.
> Why the smallest, not the largest negative? Why using little /big endian (don't know which was used) instead of the
> other? Why choosing exactly these conditions (you phrase it "parameters").

Endianness has no impact on the mathematics involved.

Smallest because there is such a thing (as opposed to largest, which
is unbound).  It could have been smallest absolute value, allowing one
more degree of freedom.  Perhaps there's a class of attacks that works
with positive As and not with negative As (or vice-versa)?  But that
seems unlikely.

> Don't get me wrong. I admit that the construction of Curve25519 is extremely rigid, and even more rigid than that of the
> Brainpool curves. I only point to the fact that there is no perfect rigidity.

Agreed.  I like DJB's curve constructions because as much as possible
is explained verifiably.

>> is deterministic. Brainpool is close enough that I would say "quite
>> rigid" as opposed to "deterministic construction". Basically, the
>
> I think we can agree on that statement.

Agreed.

But the SafeCurves site doesn't focus only on construction rigidity,
and it doesn't discount Brainpool on account of rigidity in its
construction.  SafeCurves also covers other issues.  SafeCurves
declares Brainpool curves not safe according to the following
criteria:

 - feasibility of efficient constant-time implementation
   http://safecurves.cr.yp.to/ladder.html

 - twist security
   http://safecurves.cr.yp.to/twist.html

   IIUC this means that when using non-twist secure curves one has to
validate that peers' public keys are on the curve being used, which in
turn would require exchanging not just public keys but also Schnorr
signatures (and, of course, verifying those signatures before using
peers' public keys for any other purpose).

 - completeness
   http://safecurves.cr.yp.to/complete.html

   This is an argument that's purely about implementation complexity
and performance.  I'm not sure how concerned to be about this -- less
than about the previous two concerns above, no doubt.

 - indistinguishability of public key values from random
   http://safecurves.cr.yp.to/ind.html

   No EC curve has this.  But for some curves one can construct a
mapping between any point and some small set of non-points all of
which can then be mapped right back into the original.  And such a
mappings can be made constant-time in the case of the three given safe
curves.  But no such mappings are known for the other curves
(including Brainpool).

   This is primarily a problem for protocols aiming for privacy
protection and for some ZKPPs (e.g., EKE) (but not for, say, J-PAKE,
which, incidentally, uses Schnorr signatures to verify public key
validity).

Nico
--