Re: [Cfrg] Progress on curve recommendations for TLS WG

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Cfrg [mailto:[e-mail]] On Behalf Of D. J. Bernstein
<snip>

> 
> > Or should we be thinking about generating fresh curves using a public
> > process having verifiably random inputs? What would the likely impact
> > be on performance?

I do not want to delay the standardization of Curve25519, but I do not want
to close the door (*) on even-lower-risk curves.

(*no pun intended, note to self: avoid metaphors)

> 
> The impact depends on exactly which class of curves is chosen, raising the
> question of what manipulation is possible through this choice---I would
guess
> more than the manipulation possible for any of the proposals that are on
the
> table so far.
> 
> Dan Brown claims that choosing random curves (in some unspecified class)
is

Yes it's true that I was not completely specific in that email, partly
because my comment was a generic one, but also because of the context of the
existing practice and standards, aka state-of-the-art, especially P256
(minus the unexplained seed choice, of course).  E.g. selecting one of the
coefficients randomly (or by proxy, pseudorandomly), in such a way that to
obtain a random (but perhaps non-uniform) j-invariant, filtering the choice
based on a set of well-accepted criteria.   I felt that was implicit in most
of my messages to IETF: I don't think I ever proposed to overturning that
practice, perhaps just refining it.

Regardless, I'll try to be more specific. The class would be a subset of
those resisting all known attacks.  This subset could be determined by
narrowing based on potential security risks and efficiency benefits.  We
might narrow the set used for P256 further to account for more recent
discoveries: improved side channel resistance and efficiency and perhaps
various esoteric variants of DH problems.

> safer than choosing "special" curves. He says that this claim is justified
by
> "special" MOV-vulnerable curves and "special"
> SmartASS-vulnerable curves. However, he ignores
> 
>    * the fact that we always take "special" curves with unusually small
>      cofactors, and believe these to be more secure than random curves;

Choosing special parameters to avoid known attacks or potential attacks is
something I agree with. [[So, it is not something that I ignore, at least
generally.]]

The reason to choose special nearly-prime-order curves is to avoid the
Pohlig--Hellman attacks. 

For 256-bit order curve, the specialness of having a prime order removes
about 7.5 bits of choice from the class.  Heuristically, this does not seem
as large as a degree specialness as MOV-weak and SASS-weak curves, which may
be up at around 120 bits of specialness, but maybe I've miscalculated.

One could even avoid specialness of prime-order-curves by using random
curves with half-larger bit size, (e.g. 384 instead of 256) while, of
course, still checking resistance all known attack, including
Pohlig--Hellman and Pollard rho, so that the curve order has a prime factor
of at least 256 bits.  But these curves would be significantly slower.
Also, in the case, the curve group becomes more like a finite field group
with some small subgroups, so one would often need to do either cofactor
multiplication or order-checking, i.e. to avoid small-subgroup attacks, both
of which are costly.  

So, the slight specialness of nearly-prime order curves seems justifiable
for security and efficiency reasons.  

I'd suggest that, when choosing a random curve, we continue the practice of
using a (nearly) prime-order random curve.

> 
>    * the fact that we now take even more "special" curves that also have
>      unusually small twist cofactors, for the same reason; and

Requiring twist security seems like a good backup to, or even workaround to,
public key validation, and does not add much more specialness, again about
another 7 bits.  Relying on twist-security by allowing a static private key
to be applied to a point on the twist, is another interesting strategy whose
security I asked about in a different thread.  

I'd suggest that requiring twist-secure curves should be optional criteria
in selecting a random curve, because the benefit is rather small, and so is
the specialness.

This optionality introduces one bit of manipulability into the selection
criteria.

>    * five further counterexamples in Section 11 of a 2008 paper by
>      Koblitz, Koblitz, and Menezes (http://eprint.iacr.org/2008/390)---
>      in these five examples, under perfectly believable hypotheses,
>      random curve choices are _less_ secure than "special" curves.

Sure, their hypothesis are believable, but the MOV and SASS attacks are
actual attacks that work on prime-field curves, not binary-field elliptic
curves or higher genus (non-elliptic) curves.  

Also, some of the [KKM] examples seem to describe flukes.  I agree with
[KKM] that is possible that a special curve could resist some attack that
most random curves would not.  But selecting the special curve that resist
such an attack without knowing the attack would be a fluke, as I see it.
Anyway, the possibility [KKM] justifies having a special curve supported and
ready as a backup option in case of a disaster: aka algorithm agility.

//

Now to focus on the specialness of Curve25519. 

I understand (and trust) that special fields can lead to the best side
channel resistance and efficiency, so a special field is very justifiable.
Also, I'm not aware of any attacks based on the special fields.

I see the main benefit of the small size of A coefficient in the Curve25519
to help achieve the goal of rigidity, aka nothing-up-my-sleeve, aka
non-manipulability, aka no-back-door, aka non-malicious, aka
trustworthiness.  Again, this is justifiable.

Beyond rigidity, I see the smallness of A as making Curve25519 special.  In
bits, I'd estimate that it's special by a degree of (255-15)/2 = 120 bits.
I subtracted 15, for the small cofactor of the curve and its twist, and then
divided by two to account for isomorphisms of curves (because many different
A are isomorphic), but that's probably wrong, so please correct me.  I see
that a notably special.  To be fair, the MOV and SASS attacks on special
curves do not depend on coefficient size, so that's a good reason not to
worry about the specialness of the small A in Curve25519.  Again, I'm not
saying the specialness of Curve25519 is enough to delay its standardization.


If we could rigidly choose a random A, then not much of efficiency or side
channel resistance of Curve25519 would be lost, so this randomized A would
make Curve25519 even less risky, assuming the same level of rigidity.  

Granted: getting to such a similar level of rigidity might be hard.  I don't
think it would be feasible in the short time frame (one or two months) CFRG
is now aiming for.  But I think we could be possibly decide to undertake
such an endeavour, and then discuss options, which could take a long time, a
year maybe.

Best regards,

---Dan