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

[Dan Brown <[e-mail]>]

From: Cfrg [mailto:[e-mail]] On Behalf Of Watson Ladd
Sent: Friday, August 15, 2014 2:24 PM
>On Aug 15, 2014 10:59 AM, "Dan Brown" <[e-mail]> wrote:
>>
>> Wrong about it being unconvincing: the severity of the attack is what 
>> matters,
>> not how common it is.  Why would anybody care whether it took six or
>> one-million trials to a find a weak 56-bit curve?
>What is it convincing of? If it takes 6 trials all randomly generated curves 
>are likely to fail. If it's 1 in a million, then rigidity or lack thereof is 
>more important to prevent underhandedness.

Only a few small points to be convinced of by the example y^2 = x^3+x^2+x / 
GF(2^255-19), all related to resisting a secret attack of severity and 
distribution about the same as the Pohlig--Hellman (PH) attack:

1) Rigidity does not help against such a severe attack.
2) The rigid example I found happened to fall into a hole covering about 
1-in-6 of curves, but that hole is very deep rendering the curves in the hole 
feasible to break.  This metaphorical hole for the PH attack does not have a 
sharp edge, but suppose the hole had a sharp edge for the secret attack, for 
the sake of simple example. If users selected their own curves at random, then 
5-in-6 users would be safe, and 1-in-6 unsafe due to the secret attack.  If 
CFRG selects one universal curve, somehow at random, then with a 5-in-6 
chance, all its users would be safe, but with 1-in-6 chance they'd all be 
unsafe.   Neither solution is great, but what else can we do against such a 
severe secret attack?  A rigid curve could be safe or unsafe, but one has no 
probabilistic argument of its being safe with probability 5-in-6, unless we 
assume a heuristic about the attack, which is a theoretically stronger 
assumption.  (Aside: the BARC example shows that this heuristic assumption is 
not just theoretically strong, it is practically wrong for the PH and MOV 
attacks because one can find PH and MOV weak curves without trial and error 
violating the heuristic assumption.)
3) The example I chose was y^2  = x^3 + x^2 + x, but the arguably more rigid 
curve y^2 = x^3 + x resists PH considerably better.  An adversary pushing the 
less secure curve might think up excuses to prefer the former, such as: the 
latter is more fragile, because somebody is more likely implement it with 
older Weierstrass code, which is more liable to have side channels, whereas 
y^2 =x^3 + x^2 + x would encourage people to use a Montgomery ladder. 
Accepting that adversary's argument would turn a 2^99 attack into a 2^56 
attack.  This just shows that one of the attacks we already know, the PH 
attack, is super-sensitive to the extent that there's that rigidity alone does 
not suffice to prevent underhandedness.

Just to be clear, in case you were wondering, the y^2 = x^3+x^2+x/ 
GF(2^255-19) example would not serve to convince anybody anything about the 
unexplained-seed used for P256, or even the ANSI curve generation method.

>>
>> Also, I assume that you are not referring to my BARC example, in which the
>> largest prime factor is two.   Maybe BARC is unconvincing for another 
>> reason,
>> which is?
>The endomorphism ring was shockingly large,

The BARC example was testing the utility of rigidity against secret attacks. 
If you know some (potential) attack using a large endomorphism ring, then just 
pretend that attack was somebody else's secret.  In my view, now BARC should 
be even more convincing that rigidity offers no protection against secret 
attacks of similar ilk, because it falls to a fourth attack.  How can four 
attacks on one rigid curve not be convincing of something?

> NUMS isn't a property of a curve but a generation method, etc.

The BARC example can be extended to other fields: any with p=3 mod 4 and p+1 
smooth, e.g. the field GF(2^521-1), so it is really not a single curve, though 
I guess I should have said that right away.

TLS has asked CFRG to recommend one or two curves. Some proposals for a few 
curves are being made to the IETF.  The NUMS property applies to anything that 
a user wants to trust from somebody else, whether software, hardware, a curve, 
a protocol.  So, it is a property of both the generation method and of the 
curve generated.  Surely, if somebody managed, in some ingenious fashion, 
generated a weak curve maliciously, be it Curve25519, Brainpool, or P256, that 
would be a violation of the NUMS property of others trusted the curve.  So, 
taking a generation method, a plausible setting, and then running some kind of 
execution of the curve generation method, the single curve that it outputs is 
fair game for testing of the NUMS property, because ultimately CFRG will be 
asking IETF to trust us.  If you're saying that nobody is making any NUMS 
property claims for Curve25519, only its generation method, then I'm saying 
it's better to have a curve which has some plausible NUMS property, even if it 
has to invoke some kind of fancy assumptions.

If IETF has a proposal or a request for just a generation method in which a 
pair, or larger set, of mutually trusting users generates their own curve, 
then those users could rely solely on the NUMS property of generation method, 
since they control the actual of execution of the generation method. 
(Nothing-up-your-sleeve is a vacuous goal.)

Anyway, the BARC example was trying to show that there is not any direct 
correlation between rigidity and security (whether NUMS or not).  I did say 
however, the rigidity can rule out certain kinds of secret attacks, so I think 
rigidity has some benefits, i.e. is a desideratum.

The BARC example is easily avoided by selecting some kind of randomized curve 
generation method.  Hence it also demonstrates a narrow utility of randomized 
curve generation methods in contributing to the NUMS property: in that it 
protects the user from dial-up weaknesses where the attacker can find weak 
curves without any searching.  In other words, the BARC example serves not 
just a criticism of rigid-only curves, but also as a demo a small degree of 
plausible usefulness for random curves.

> Really the only argument was supersingular curves,

Well, supersingularity is just a property of curves, not an attack.  I'm 
looking for arguments to resist attacks.  The supersingularity alone implies 
the MOV attack, but does not necessarily imply the PH attack.  It's the fact 
that p+1 is smooth plus supersingularity in BARC that leads to the PH attack 
working so well.  Also, I only know how to find supersingular curves when p=3 
mod 4 or p=2 mod 3.  Since p=1 mod 12 for Curve25519, I don't know how to find 
a supersingular curve over GF(2^255-19).  Is this planned?  If not, it is a 
side effect of rigidity, or some kind of non-rigidity?

Interestingly, BARC gives an example of an attack in which the field choice 
matters and the rarer field choices (the p+1 smooth ones) are the ones more 
vulnerable.  In other words, it actually lend some plausibility Brainpool's 
choice of random field sizes.

> which I admit being mildly convinced by.

I thought I'd never see this day :-)