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

From: Dan Brown <[email-masked]>
Date: Wed, 6 Aug 2014 18:05:57 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] 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

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 15 Aug 2014 13:12:13 +0200

D. J. Bernstein wrote on 01.08.2014 03:36:
> However, the following recent analysis shows that the Brainpool curves,
> which were advertised as "generated in a systematic and comprehensive
> way" covering several different security levels, actually gave the curve
> generator the flexibility to secretly choose from among more than
> 1000000 curves for any particular prime:
> 
>    http://safecurves.cr.yp.to/bada55.html
>    http://safecurves.cr.yp.to/bada55/bada55-20140722.pdf

This statement is so skewed and misleading that I can not refrain from commenting:

- In this analysis, a significant part of this flexibility comes from the choice of the hash function. Specifically, the
BADA55 curves were generated using one of the numerous version of Keccak. However, Keccak wasn't even invented at the
time the Brainpool curves were generated.

 - The method used to generate the coefficients of the Brainpool curves was taken from ANSI X9.62 (including the use of
SHA-1), which was - at least at that time - the only reference for a method for pseudo-random curve generation. There is
only the slight deviation that the second coefficient was computed in exactly the same way as the first one, while ANSI
X9.62 computes the fraction of these, but this straightforward simplification does not introduce significant flexibility.

- Pi and e are by far the most prominent mathematical constants, while cosinus(1) (used in that analysis) is quite
arbitrarily chosen. Expressing Pi as 4*arctan(1) doesn't change this fact.

It is perfectly OK to point out that the Brainpool curves do not allow optimal performance, or that Montgomery and
Edwards curves allow simplified arithmetic. But it is not ok to imply that the Brainpool curves could potentially have
been designed with a backdoor built in. This suggestion is completely unjustified, misleading and gives a false color.

-- 
Johannes

---

From: Alyssa Rowan <[email-masked]>
Date: Fri, 15 Aug 2014 13:35:24 +0100

On 15 August 2014 12:12:13 BST, Johannes Merkle <[email-masked]> wrote:

>- The method used to generate the coefficients of the Brainpool curves
>was taken from ANSI X9.62 (including the use of
>SHA-1), which was - at least at that time - the only reference for a
>method for pseudo-random curve generation. There is
>only the slight deviation that the second coefficient was computed in
>exactly the same way as the first one, while ANSI
>X9.62 computes the fraction of these, but this straightforward
>simplification does not introduce significant flexibility.
>
>- Pi and e are by far the most prominent mathematical constants, while
>cosinus(1) (used in that analysis) is quite
>It is perfectly OK to point out that the Brainpool curves do not allow
>optimal performance, or that Montgomery and
>Edwards curves allow simplified arithmetic. But it is not ok to imply
>that the Brainpool curves could potentially have
>been designed with a backdoor built in. This suggestion is completely
>unjustified, misleading and gives a false color.

Respectfully, deferring choices made in the curve generation process back to ANSI X9.62 (even though it may have made sense at the time) doesn't alleviate any potential concerns about lack of rigidity in those choices; it merely means they weren't Brainpool's own choices, and no-one thought to question them at the time quite as deeply as they do today.

If X9.62's choices had full, rigid, transparent explanations, perhaps this discussion would have not arisen, and in that vein perhaps neither would Brainpool? But they did not (and although Certicom/NSA indeed seem to have performed a brute-force seed search for the SECG/NIST curves, we may never be certain what all the parameters of that search were): so here we are.

Please do not take the BADA55 paper personally; it is simply an entertaining, instructive demonstration of how, just because a conjurer seems to have nothing up their sleeves, doesn't necessarily mean they can't do magic tricks and perhaps we should all remember to look under their hat, too. :-)

- --
/akr

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 15 Aug 2014 16:22:33 +0200

Alyssa Rowan wrote on 15.08.2014 14:35:
> Respectfully, deferring choices made in the curve generation process back to ANSI X9.62 (even though it may have
> made sense at the time) doesn't alleviate any potential concerns about lack of rigidity in those choices; it merely
> means they weren't Brainpool's own choices, and no-one thought to question them at the time quite as deeply as they
> do today.
> 
> If X9.62's choices had full, rigid, transparent explanations, perhaps this discussion would have not arisen, and in
> that vein perhaps neither would Brainpool? But they did not (and although Certicom/NSA indeed seem to have
> performed a brute-force seed search for the SECG/NIST curves, we may never be certain what all the parameters of
> that search were): so here we are.
> 

The issue many people on this list (including me) have with the NIST curves is not the curve generation method but the
unexplained seeds. If you mean to imply that the method itself is suspicious, independent of the seeds, then this is a
position I have not yet seen expressed, and I doubt that many people will find it plausible.

Actually, this is the core of the problem with the discussion on rigidity: It is more about sense than about facts. Do
you feel comfortable with this generation procedure or with those constants, or with others? Something that you might
deem very straightforward and rigid may look arbitrary and even suspicious to others. Rigidity can not be measured
objectively. This makes it easy to argue against one or the other approach.

It is important that, whatever curves CFRG selects, anyone can feel comfortable with their rigidity and that there
will be no doubts about their security and the lack of back-doors. The BADA55 paper and the post I was responding to,
though intended to be provocative and entertaining, introduce FUD in that respect and are contra-productive. I am
quite sure that one could also construct a "one in a million curve" using a seed-less approach very similar to
curve25519, but this would only introduce more unjustified discredit and FUD.

We should focus on establishing trust not FUD.

-- 
Johannes

---

From: Watson Ladd <[email-masked]>
Date: Fri, 15 Aug 2014 07:29:06 -0700

On Aug 15, 2014 7:23 AM, "Johannes Merkle" <[email-masked]>
wrote:
> > Respectfully, deferring choices made in the curve generation process
back to ANSI X9.62 (even though it may have
> > made sense at the time) doesn't alleviate any potential concerns about
lack of rigidity in those choices; it merely
> > means they weren't Brainpool's own choices, and no-one thought to
question them at the time quite as deeply as they
> > do today.
> >
> > If X9.62's choices had full, rigid, transparent explanations, perhaps
this discussion would have not arisen, and in
> > that vein perhaps neither would Brainpool? But they did not (and
although Certicom/NSA indeed seem to have
> > performed a brute-force seed search for the SECG/NIST curves, we may
never be certain what all the parameters of
> The issue many people on this list (including me) have with the NIST
curves is not the curve generation method but the
> unexplained seeds. If you mean to imply that the method itself is
suspicious, independent of the seeds, then this is a
> Actually, this is the core of the problem with the discussion on
rigidity: It is more about sense than about facts. Do
> you feel comfortable with this generation procedure or with those
constants, or with others? Something that you might
> deem very straightforward and rigid may look arbitrary and even
suspicious to others. Rigidity can not be measured
> It is important that, whatever curves CFRG selects, anyone can feel
comfortable with their rigidity and that there
> will be no doubts about their security and the lack of back-doors. The
BADA55 paper and the post I was responding to,
> curve25519, but this would only introduce more unjustified discredit and
FUD.

Hic rhodes, hic saltus.

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

---

From: Dan Brown <[email-masked]>
Date: Fri, 15 Aug 2014 15:44:04 +0000

> From: Cfrg [mailto:[email-masked]] On Behalf Of Johannes Merkle
> Sent: Friday, August 15, 2014 10:23 AM
> 
> are contra-productive. I am quite sure that one could also construct a
"one in a
> million curve" using a seed-less approach very similar to curve25519, but
this
> would only introduce more unjustified discredit and FUD.
> 

[DB] I thought I already did this, and more, in my email to this list with
subject "Bad and Rigid Curve".  I found a one-in-2^128 curve that is
seed-less.  Oh well, I suppose I cannot expect everybody to read everything
I write, or at least agree with it.

But maybe the point was that BARC seemed insufficiently similar to
Curve25519. 

Here's something more similar to Curve25519, but I need to count points and
factor, so I've use Sage, whose session I manually re-typed here (to save
myself from learning how to cutting-and-paste from the VM I'm using):

sage: E = EllipticCurve(GF(2^255-19),[0,1,0,1,0]); E
y^2 = x^3 + x^2 + x
sage: factor(E.order())
2^4 * 67 * 557233194274943 * 2014538529699005948261 *
4811068624484807686053494972215370277
sage: log(481106862448480768605349497215370277.0,2.0)
112

This curve is similar to Curve25519, same field, same equation shape, but
smaller x^2 coefficient, namely 1 instead of the value used in Curve25519,
which is about half a million, if I recall correctly.

If this curve had been proposed before the Pohlig--Hellman attack had been
made public, then it would be vulnerable to 2^56 step secret attack, yet the
best public attack would have been 2^128-step Pollard rho.

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 15 Aug 2014 18:41:29 +0200

>> curve25519, but this would only introduce more unjustified discredit and

Consider Dan Brown's construction as an example. You may consider his construction artificial as he considers attacks
that are already known. However, this is exactly my point: You can find such examples if you stretch the boundaries of
the scope in order to increase the degrees of freedom. In order to create sufficient flexibility, the BADA55 paper has
generalized the method(s) of ANSI and Brainpool in many aspects, but these generalizations are much less natural and
straightforward as the original approaches. In the same vein, one could slightly modify the rules for selecting the
curve parameters used in a seed-less approach, and this generalization would certainly provoke your criticism as not
being straightforward. So we would arrive at an example that does not really show anything but could be easily mistaken
by someone with less insight (e.g. the press) to wrongly conclude that the seed-less approach is generally suspicious.
This FUD effect would be bad.

For this reason, I tried to appeal to stop this unfortunate discussion in which contrived examples are used to discredit
much more straightforward approaches, but unfortunately, my post seem to have stimulated it.

-- 
Johannes

---

From: Watson Ladd <[email-masked]>
Date: Fri, 15 Aug 2014 10:07:03 -0700

On Aug 15, 2014 9:41 AM, "Johannes Merkle" <[email-masked]>
wrote:
> >> though intended to be provocative and entertaining, introduce FUD in
that
> > respect and are contra-productive. I am
> >> quite sure that one could also construct a "one in a million curve"
using
> > a seed-less approach very similar to
> >> curve25519, but this would only introduce more unjustified discredit
and
> > FUD.
> >>
> >
> > Hic rhodes, hic saltus.
>
> Consider Dan Brown's construction as an example. You may consider his
construction artificial as he considers attacks
> that are already known. However, this is exactly my point: You can find
such examples if you stretch the boundaries of
> the scope in order to increase the degrees of freedom. In order to create
sufficient flexibility, the BADA55 paper has
> generalized the method(s) of ANSI and Brainpool in many aspects, but
these generalizations are much less natural and
> straightforward as the original approaches. In the same vein, one could
slightly modify the rules for selecting the
> curve parameters used in a seed-less approach, and this generalization
would certainly provoke your criticism as not
> being straightforward. So we would arrive at an example that does not
really show anything but could be easily mistaken
> by someone with less insight (e.g. the press) to wrongly conclude that
the seed-less approach is generally suspicious.
> This FUD effect would be bad.

Put the string BADA55 in the hex output of the parameters to convince us.
It's that simple. The reason Dan Brown's example isn't convincing is that
having only  prime factors of not that small size is common.

>
> For this reason, I tried to appeal to stop this unfortunate discussion in
which contrived examples are used to discredit

---

From: Dan Brown <[email-masked]>
Date: Fri, 15 Aug 2014 17:36:00 +0000

> Sent: Friday, August 15, 2014 12:41 PM
> To: Watson Ladd
> Cc: [email-masked]
> Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
> 
> >>
really
> show anything but could be easily mistaken by someone with less insight
(e.g.
> the press) to wrongly conclude that the seed-less approach is generally
> suspicious.
which
> contrived examples are used to discredit much more straightforward
> approaches, but unfortunately, my post seem to have stimulated it.
> 

I disagree with some of the points above.  So: 

Contrived examples are useful when abstractions get too numerous and
difficult and hard to compare. They can more efficient at conveying an idea,
in using fewer words.  I hope that the CFRG will not misunderstand the
contrivances, but rather try to see the points they demonstrate.  I agree
that contrivances may not be interesting to be engineering and the general
public, who are more concerned with the end results, but researchers should
be able to consider them if it is for the purposes of clarity.

Nobody will ever be able to fully resolve the possibility of secret attacks.
So rather than dismissing the possibility as FUD, we should try to do what
we can to minimize this threat.  That's the whole reason for being of the
disciplines of public cryptanalysis and of provable security.  If any time
somebody proposes an algorithm with no published attacks, then they should
not be able dismiss any criticisms by crying FUD, right?

CFRG are neither the press nor the end user. I expect CFRG to be able to
engage in technical discussions, without censuring itself because of
possible misunderstanding by non-technical.

My BARC example was merely meant to demonstrate that rigidity alone does not
support the security of Curve25519 against secret attacks.  Rather, if the
maturity of cryptanalysis suggests that all known attacks are public, then
Curve25519 is secure.  Or, perhaps maturity of public cryptanalysis only
suggests that any weak curve classes differ from the Pohlig--Hellman and MOV
weak classes in the sense that the secret class is only reachable by trying
multiple curves and we heuristically expect it to apply to all curves with
equal probability.  In fact, I already tried make this abstract argument
long ago on the TLS and CFRG lists: that one needs to assume that some
secret attack which Curve25519 can resists is an attack that affects all
curves with equally likelihood, which sounds like a plausible assumption,
and indeed is a weaker assumption than assuming no secret attacks. That
said, it is not true for the some of the known attacks, at least the PH and
MOV attacks.  I'm not sure if this abstract argument sounded believable, so
I provided the BARC example as a demonstration.  

The 56-bit secure y^2 = x^3 + x^2 + x variant of Curve25519 may perhaps only
demonstrate something vastly weaker abstract idea: that a rigid curve can be
weaker than expected curve just by a fluke, in other words, that bad luck is
possible.  I don't know enough to be completely sure whether this particular
example is much worse than average, or if it qualifies as a one-in-a-million
type of fluke.  Of course, once a random curve is selected, it can suffer
from bad luck too.  In the case of a fixed random curve, at least we can
form an argument about a priori probabilities.  So, that's why I'm saying
that this is a much weak abstract idea, because it hinges on the notion of a
priori probabilities.  Selecting random curves more often would be costly,
but would improve this particular aspect.

Best regards,

Dan

---

From: Dan Brown <[email-masked]>
Date: Fri, 15 Aug 2014 17:59:27 +0000

From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
> The reason Dan Brown's example isn't convincing is that having only  prime 
> factors of not that small size is common.

Right about it being common: Dickman's function says the chance of the largest 
prime factor of that size is about 15%.

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?

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?

---

From: Watson Ladd <[email-masked]>
Date: Fri, 15 Aug 2014 11:23:58 -0700

> 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.

> largest prime factor is two.   Maybe BARC is unconvincing for another
reason,

The endomorphism ring was shockingly large, NUMS isn't a property of a
curve but a generation method, etc. Really the only argument was
supersingular curves, which I admit being mildly convinced by.

Sincerely,
Watson Ladd

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 15 Aug 2014 11:50:30 -0700

On Fri, Aug 15, 2014 at 11:23 AM, Watson Ladd <[email-masked]> wrote:
> 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.
>
>>
> The endomorphism ring was shockingly large, NUMS isn't a property of a curve
> but a generation method, etc. Really the only argument was supersingular
> curves, which I admit being mildly convinced by.
>

If CFRG is going to seriously consider random curves, can we at least
generate good random curves?  I don't think it's *that* hard.  Choose
a good algorithm to turn a seed into a curve, and then use something
like H(next week's top NY Times headline, next week's top Al-Jazeera
headline, next week's S&P 500 close, next week's weather, etc...).

The point being that there are lots of degrees of freedom this way,
but no one (not even the NSA) would be able to control enough of them
to select for any property of the curve.

--Andy

---

From: Dan Brown <[email-masked]>
Date: Fri, 15 Aug 2014 21:19:40 +0000

From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
Sent: Friday, August 15, 2014 2:24 PM
>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.

>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 :-)

---

From: Watson Ladd <[email-masked]>
Date: Fri, 15 Aug 2014 19:14:46 -0700

> unexplained-seed used for P256, or even the ANSI curve generation method.

If I tell the method to ignore Polig-Helman, it spits out a curve that
is vulnerable. That's why the only convincing part of your email was
supersingularity, but even that was only convincing me that minimal
parameters could cause some property to be true.
> has to invoke some kind of fancy assumptions.

At the risk of making this WG even less effective than it already is:

Mathematical objects exist independently of human perception.
Properties are properties of objects. How NUMS is a random curve I
write in this email? Since you don't know how I made it, you can't
decide, so NUMS isn't a property of the curve. To the extent there is
a NUMS property, it's a property of algorithms A for deciding that a
curve is "acceptable". One set of algorithms applies publically known
criteria, then finds the minimal curve satisfying these criteria.
Another set accept curves with an auxiliary input that shows that they
were made by taking some inputs and hashing them. The second set
accepts manipulatable curves.

All of this machinery is inherent in DJBs paper. Heck, it's defined
there, somewhere between the third and fifth time I laughed.

What you showed is a fairly minimal set of parameters can be
supersingular, which is an obviously special property. It screams 'I'm
special' the way having BADA55 in hex does. But whereas DJB showed
that an algorithm A exists to make BADA55 curves that people think
weren't manipulatable, and that we have A' to get property P, where P
could imply "there exists a circuit with area time product < K and
success probability p in solving the DLP on curve K", you've had much
less freedom in your choice of P: there are very few supersingular
curves, and the other properties you mentioned could trivially have
worked in DJB's attack.

The best you can get is that minimal parameters is no worse than
hashing constants, but I don't think you can even get that. Of course
we could do some sort of S&P 500 related generation, but it's
completely pointless: if a significant fraction of curves are weak,
we're still up the creek, and I'm pretty willing to say you will not
get CurveBADA55 out of whatever generation with primes just above a
power of 2 with bounded c, or Solinas type trinomials and minimal
parameter satisfying the properties at safecurves.cr.yp.to.

> side effect of rigidity, or some kind of non-rigidity?

The existence of efficient public key cryptography implies P!=NP. Any
argument that's actually strong in ruling out attacks would be
evidence for P!=NP. Even something like "an attack on this curve has
to work for a proportion 1/x of non-isogenous curves" would pretty
impressive. We're really, really, bad at lower bounds. We can't even
separate NC from P. We can't show hash functions exist, or even
formalize what a hash function should do. You aren't going to get
anything worthwhile without a lot of struggle, and some luck. To the
extent we have a formalization of anti-manipulation, it's the one DJB
used.

We can't hope to do more than avoid publically known attacks, think
really hard about solving the DLP, think about implementation issues
that have doomed cryptosystems and design standards to avoid them. And
despite that work being done for RSA we've seen steady chopping away
at the complexity of the NFS, together with persistent implementation
issues.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "D. J. Bernstein" <[email-masked]>
Date: 16 Aug 2014 02:16:27 -0000

Less rigidity means a larger collection of curves available for secret
selection by the curve generator. This is important in the following
scenario, which shouldn't be exaggerated but also shouldn't be ignored:

   * the curve generator is malicious;
   * the curve generator knows an attack that the public doesn't know;
   * some curve in the larger collection is vulnerable to the attack;
   * no curves in the smaller collection are vulnerable to the attack.

A much simpler issue is that any curve, even an honestly generated one,
might turn out to be vulnerable to a secret attack. We do _not_ have any
way to protect against this---but, again, it's not the same issue. What
we _do_ have are ways to stop the curve generator from amplifying a
one-in-a-million secret attack into a guaranteed attack. Dan Brown is
confusing these two issues when he says that "rigidity alone" does not
ensure safety "against secret attacks".

One way to achieve a reasonable level of rigidity is to choose the curve
that is as _small_ as possible---while obeying public security criteria,
obviously. (My experience is that defining "small" as "smallest cost",
averaged in any plausible way across platforms, minimizes wiggle room:
it's vastly more difficult to reach truly top speed than to merely come
close. But that isn't the topic of this message.)

What do we know, for various definitions of "small", about the security
of taking the smallest curve? Answer: Maybe it's more secure than
others. Maybe it's less. We simply don't know. The literature has

   * examples of attacks where the smallest curve resisting other
     attacks is _more_ secure than average and

   * examples of attacks where the smallest curve resisting other
     attacks is _less_ secure than average.

Maybe a secret attack would be of the first type, or maybe it would be
of the second type. In a previous message I pointed to seven known
examples of the first type (for various notions of smallness) and two
known examples of the second type. Koblitz, Koblitz (the co-inventor of
ECC), and Menezes wrote a long paper http://eprint.iacr.org/2008/390
with a section devoted to this issue:

   11.1. Special or random selection of parameters?

   A general philosophy one often encounters in cryptography is that
   whenever possible parameters should be chosen by some random process.
   If a special choice is made to increase efficiency, there is always
   the risk that the same property that made the choice so attractive
   will also lead to vulnerability to an unanticipated attack.

   [... several pages describing five detailed examples of how special
   choices can _improve_ security ...]
   
   Our purpose in giving these examples is not to lobby for the use of
   special curves in preference to random ones. Rather, our point is
   that conventional wisdom may turn out to be wrong and that, as far as
   anyone knows, either choice has risks. The decision about what kind
   of curve to use in ECC is a subjective one based on the user's best
   guess about future vulnerabilities.

   As frequently happens in cryptography, a close examination of a
   commonly accepted viewpoint on security issues reveals that opposing
   opinions or interpretations cannot be ruled out. Much as we might
   wish to convey to the outside world an impression of self-confidence
   and mathematical certainty about our recommendations (see Section 2),
   there is ample reason to wonder whether this self-confidence is
   justified.

Brown keeps claiming, incorrectly, that the risks are entirely on one
side. His argument consists of pointing to the well-documented risks on
that side (such as MOV, one of the examples I had given) while ignoring
the well-documented risks on the other side.

---Dan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 16 Aug 2014 03:23:02 -0000

Is anyone actually planning to propose "random" curves here? Dan Brown
said he would but didn't follow through. Brainpool already has RFCs.

Johannes Merkle writes:
> Pi and e are by far the most prominent mathematical constants, while
> cosinus(1) (used in that analysis) is quite arbitrarily chosen.

MD5 uses sin(1). This is one of several "nothing up my sleeve numbers"
cited in http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number.

Please point to the cryptographic papers disputing this "nothing up my
sleeves" designation and arguing that switching MD5 from sin(1) to e
would be less suspicious. Surely you're not claiming that the public
would have been more suspicious of cos(1) than of sin(1)?

> Keccak wasn't even invented at the time the Brainpool curves were
> generated.

Sure, but Brainpool could easily have argued for switching to the 1996
European hash function RIPEMD-160 from famed cryptographers Dobbertin,
Bosselaers, and Preneel. The SHA-1 critique in

   http://homes.esat.kuleuven.be/~bosselae/ripemd160.html

includes items from 2004 as the last three sentences but is otherwise
pre-2000 material. Do you seriously believe that switching from NSA's
SHA-1 to respectable RIPEMD-160 would have made people reject the
Brainpool curves as being potentially backdoored?

How about 192-bit Tiger, from famed cryptographers Anderson and Biham,
for extra security? Or RIPEMD-256? Or RIPEMD-320? Or one of the versions
of Whirlpool, from famed cryptographers Rijmen and Barreto? Or, back in
the NSA universe, SHA-256 or SHA-384 or SHA-512?

If you count carefully you'll see 11 different hash functions here, more
than the 10 Keccak versions that were used to manipulate BADA55-VPR-224.

> The method used to generate the coefficients of the Brainpool curves
> was taken from ANSI X9.62

http://projectbullrun.org/dual-ec/dualec-author.html illustrates NSA's
influence over ANSI. Anyway, what relevance does the identity of the
curve generator (or generators) have to the measurement of rigidity?

> There is only the slight deviation

So you're admitting that Brainpool _didn't_ actually take the same
method; it manipulated the method (to simplify it, you say). Even
without this admission, how exactly is the Brainpool procedure less
suspicious than the BADA55-VPR-224 procedure?

There's a "BADA55" in the BADA55-VPR-224 output, but a real attack along
the same lines wouldn't have anything obvious. Meanwhile the Brainpool
procedure has an embarrassing 26DC5C6CE94A4B44F330B5D9 overlap, which
you previously admitted was "unfortunate".

> But it is not ok to imply that the Brainpool curves could potentially
> have been designed with a backdoor built in.

The statement you're responding to is that the curve generator had the
flexibility to secretly choose from among more than 1000000 curves for
any particular prime. If the curve generator secretly knew a weakness in
just one of these >1000000 curves then the curve generator could have
chosen that curve.

You seem to think that the flexibility was somewhat less because (e.g.)
the public wouldn't have accepted cos(1). But this doesn't fundamentally
change the picture. I don't mean to exaggerate the risk here---note that
SafeCurves marks Brainpool's rigidity as an acceptable "mostly rigid"---
but I don't see how you can justify your claim of zero risk.

---Dan