Subject: Re: [TLS] Safe ECC usage

From: "D. J. Bernstein" <[email-masked]>
Date: 1 Oct 2013 14:35:11 -0000

Dan Brown writes:
> You noted that curve sizes p,p-1, and p+1 are weak.
> These might be called special curve sizes, since for a random curve,
> of order p+d, we expect |d| around p^(1/2), and for these d is much
> smaller.

There is already overwhelming evidence that the size of d is not what
matters. For example, the next attack that you should learn is one that
breaks group order p+6m+2 if p=12m^2-1; in this case the gap from p is
more than 80% of its maximum possible value.

What's actually going on is that the additive group F_p has order p; the
multiplicative group F_p^* has order p-1; the group F_{p^2}^* has order
p^2-1; the group F_{p^3}^* has order p^3-1; etc. For roughly the first
dozen groups in this list we have discrete-logarithm algorithms fast
enough to worry about. There are known methods to "transfer" ECDLP over
F_p into these discrete-logarithm problems---but only if the EC group
has order dividing p, p-1, p^2-1, p^3-1, etc. This is why p+1 is a
problem (it divides p^2-1); it's why p+6m+2 is a problem if p=12m^2-1
(p+6m+2 divides p^3-1); etc.

> Of course, it's a logical leap to
> jump from small d to small curve coefficients,

It's even worse than a logical leap: CM theory shows that each d that
isn't extremely close to +-2 sqrt(p) corresponds to a huge number of
different curve coefficients. There's overwhelming evidence that the
correlation is negligible, making coefficient size useless as a
predictor of the size of d---never mind the question of what any of this
has to do with ECC security.

> but if we are going to be prudent, then why not avoid small
> coefficients too?

Calling this "prudent" has zero justification from the extensive
literature on ECC security analysis. You could, with exactly the same
amount of justification, claim that _large_ coefficients are more likely
to be weak and that choosing small coefficients is the safest strategy.

What actually matters is that taking large coefficients imposes an extra
cost, both in cryptographic performance and in the human effort required
to rule out back doors. These are resources taken away from things that
actually matter for security. If this were the only bad cryptographic
decision then it wouldn't be a huge problem, but unfortunately it's just
one of many things that people screw up.

---D. J. Bernstein
   Research Professor, Computer Science, University of Illinois at Chicago

---

From: Dan Brown <[email-masked]>
Date: Tue, 1 Oct 2013 15:51:07 +0000

> D. J. Bernstein writes

[DB] Thanks for the advice, but what I need to learn, or remember, is no
justification for the security of Curve25519.

> breaks group order p+6m+2 if p=12m^2-1; in this case the gap from p is

[DB] In case, anybody gets scared here, standards already have the MOV test
rule this class out.  In my weak defense, negligible fraction of p are
affected here.  More strongly, please remember that we are talking about
hypotheticals here: maybe there exists undiscovered attacks, e.g. against
P256 or Curve25519.  If the evidence is so overwhelming, then maybe we
should worry much less about P256?  That said, your argument is cogent, and
I take new, so this discussion has proven fruitful for improving the
justification Curve25519, at least to me.

> What's actually going on is that the additive group F_p has order p;
> the multiplicative group F_p^* has order p-1; the group F_{p^2}^* has
> order p^2-1; the group F_{p^3}^* has order p^3-1; etc. For roughly the
> first dozen groups in this list we have discrete-logarithm algorithms
> fast enough to worry about. There are known methods to "transfer" ECDLP
> over F_p into these discrete-logarithm problems---but only if the EC
> group has order dividing p, p-1, p^2-1, p^3-1, etc. This is why p+1 is
> a problem (it divides p^2-1); it's why p+6m+2 is a problem if p=12m^2-1

[DB] Excellent explanation, though not one I needed.

> isn't extremely close to +-2 sqrt(p) corresponds to a huge number of

[DB] Good point, the case for Curve25519 is growing yet stronger.  But how
much is huge?  I have much to learn, I know, but my understanding is that
there are about p isomorphism classes of curves, and on the order of p^(1/2)
of curve orders, so about p/^(1/2) curves per order.  I could be wrong, but
I think that a reasonable heuristic is for a random curve by isomorphism
class, its corresponding coefficient (if its equation is pushed into a
one-parameter family of equations) is approximately.  Hmm, let's see, so
what the smallest coefficient be, on average?  This problem is probably a
well known problem, but here is a crude approximation: p^(1/2).  Consider
the probability that all coefficients have size larger than p^(1/2).  For
each individual coefficient the chance is (p - p^(1/2))/p = 1 - p^(-1/2).
Now (1-p^(-1/2))^(p^(1/2)) is the probability that they all are larger, and
this e^(-1).

> predictor of the size of d---never mind the question of what any of
> this has to do with ECC security.
> 

[DB] I know, from the current literature, which is why I said I feel
Curve25519 is safe. Again, I am only talking about unanticipated
hypothetical attacks.

> amount of justification, claim that _large_ coefficients are more
> likely to be weak and that choosing small coefficients is the safest
> strategy.

[DB] Agreed to an extent: coefficient size is just an arbitrary way to test
pseudo-random uniformity.  For example, what is the P-value of the
coefficient size of Curve25519?  (Compared to random curves of any size).
You correctly argue that coefficient-size is not a concern based on current
literature, and that it improves efficiency, so therefore, it seems
economical to ignore a low P-value for this statistic.  Also, taking your
argument further, one could apply any other arbitrary statistic.  One could
then contrive some weird statistic with a low P-value to deliberate reject
some given curve.  The point of coefficient size as a statistic is just that
it is a nothing-up-my-sleeve statistic.  I thought all that was implicit in
what I said.

> 
> What actually matters is that taking large coefficients imposes an
> extra cost, both in cryptographic performance and in the human effort
> required to rule out back doors. These are resources taken away from

[DB] Back doors in the case P256, and pseudo-random curves, require
unpublished attacks, perhaps surprising ones.  (Aside: even if back doors
are inserted by adversary #1, it may be possible for adversary #2 to find
the attack too, so the concern may extend beyond the back door.)  I am
concentrating on the issue of unpublished attacks of elliptic curves,
because that is one of logical pre-requisite to a back door.  (An
alternative logical pre-requisite is an unpublished attack on SHA-1, or how
it is used in the generation of P256, but that is an orthogonal issue to
Curve25519.)

Brainpool and RFC 5639 recommends pseudo-random parameters to avoid
unanticipated attacks, and you are arguing against this recommendation by
anticipating from known attacks.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Oct 2013 16:19:44 -0000

Dan Brown writes:
> 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.

Both of these approaches are clear improvements over what NIST/NSA did.
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.

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.

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. 

---D. J. Bernstein

---

From: Dan Brown <[email-masked]>
Date: Wed, 2 Oct 2013 18:47:39 +0000

> unexplained NIST seeds leave "an essential part of the security
> analysis open" and that this is a "major issue." I completely agree
> with this.
> 
> 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
[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.

> guess whether the attack is more likely to apply to one curve or to the

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

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 3 Oct 2013 01:04:55 -0000

We're hypothesizing an attack A that isn't publicly known, and
considering the following probabilities:

   Pr[A succeeds against a NIST P-256 user];
   Pr[A succeeds against a brainpoolP256r1 user];
   Pr[A succeeds against a Curve25519 user].

NSA had considerable power to manipulate the NIST P-256 curve choice and
thus, at least potentially, the first probability. Under a wide range of
reasonable assumptions on A this would allow NSA to create a very high
first probability.

There's far less room for Brainpool manipulation, although still some
(why SHA-1? why not right to left? why pi instead of e or sqrt(2)? and
so on), maybe enough to exploit. There's essentially zero room for
Curve25519 manipulation.

We have no basis for comparing the probabilities outside the case of
manipulation. Perhaps

   Pr[A succeeds against a brainpoolP256r1 user]
   < Pr[A succeeds against a Curve25519 user],

but there's zero justification for this guess. Perhaps

   Pr[A succeeds against a brainpoolP256r1 user]
   > Pr[A succeeds against a Curve25519 user],

but there's also zero justification for this guess. This is wild
speculation, completely divorced from rational risk management.

Dan Brown writes:
> a proof that Brainpool are invulnerable to the "missed attack" with
> probability equal to the density of the vulnerable curves

There is no such proof, and there never will be any such proof. I hope
you're not trying to bamboozle the innocent reader with bogus claims of
provability!

But that's not the big issue here. The big issue is that, even in a
fantasy world of proving the (rather implausible) statement

   Pr[A succeeds against a brainpoolP256r1 user]
   = Pr[A succeeds against a user of a random curve],

we still wouldn't have any basis for comparing the Brainpool and
Curve25519 probabilities. You claim that

   Pr[A succeeds against a user of a random curve]
   < Pr[A succeeds against a Curve25519 user]

but you have zero justification for this claim. One could just as well
claim the opposite, namely that

   Pr[A succeeds against a user of a random curve]
   > Pr[A succeeds against a Curve25519 user],

which would also have zero justification. Maybe big coefficients are
more secure than small coefficients, but maybe they're _less_ secure.

---D. J. Bernstein

---

From: Dan Brown <[email-masked]>
Date: Thu, 3 Oct 2013 14:37:06 +0000

D. J. Bernstein writes:
> NSA had considerable power to manipulate the NIST P-256 curve choice
> and thus, at least potentially, the first probability. Under a wide
> range of reasonable assumptions on A this would allow NSA to create a
> very high first probability.
> 

Agreed.  Good point.

Alternatively, it is also reasonable to assume that NSA knows of an attack A
but is unwilling to reveal it, and manipulated P256 to avoid A, by methods
that they do not wish to reveal.  The prudence principle, assume that worst,
means your pessimistic assumptions merits addressing more than this
alternative optimistic assumption.  

> speculation, completely divorced from rational risk management.

Agreed.  I don't think I said this.

>    = Pr[A succeeds against a user of a random curve],

Well, I thought I prefaced my claim that you quoted above with an "if"
clause, something like we assume that we can trust verifiably pseudorandom
generation.  I had in mind something like random oracle model proof.  Since
you say there will never be such a proof, I am reconsidering what I thought,
and pondering why you say that.  

Hmm.  I don't think you are talking about posterior probabilities, which are
available to the parties who know A and to which I am not claiming any kind
of proof, argument or anything.  That is, I was thinking about prior
probabilities, given the fact that we don't know A, and that we are
specifically discussing unknown A.  

If you are saying that random oracle model proofs do not apply to that real
world, then you are right that I did not present anything like a standard
model proof.  I was wrong for implying such a thing.  But, you also said
there will never be such a proof, so I am rather puzzled.  

Maybe I am missing a factor in the equality, even in a random oracle proof,
because as you noted, even the Brainpool seeds are mildly subject to
manipulation. 

Anyway, you say it's not a big issue, and introduce a fantasy world or
proving that claim.

Anyway, I am still inclined to interpret the Brainpool phrase "verifiably
random" as claiming more that non-manipulability.  It seems to suggest some
form of justifiable indistinguishabilty to a random curve.  This may only be
a heuristic argument, but at least it some kind of argument.

> more secure than small coefficients, but maybe they're _less_ secure.

Agreed.  Zero justification.  

Prudence principle: assume the worst, so choose the < inequality for
Curve25519.  I think we should continue to assume the worst, even if it is
wild speculation, and then address it as best as possible.

The Brainpool curves have some kind of justification, albeit maybe not a
full-fledged proof.  In other words, to me, the Brainpool approach presents
some kind of best-we-can-do-effort to resist attacks not yet known to us.  

I think P256 would do this too, except for the special field, and more
importantly, the unexplained seeds.  I would be quite surprised if the US
gov publicly recommended, via FIPS 186-2, that its agencies use EC curves
that could be affected an attack A.  I find it very hard to think how the US
gov could be sure that other skilled adversaries could not find the attack
A.  The only thing I can think of, is if a trapdoor key was embedded in
P256, but that seems to imply some kind of the weakness in sha1 or the
verifiable key generation process, because such a key would have require
sufficient entropy for third parties to guess, rendering the hash-generic
exhaustive search approach to manipulation infeasible.
 
Anyway, the advantage for Brainpool over Curve25519 is slight, and
hypothetical, and may be offset by Curve25519's many other benefits, e.g.
efficiency, simple and short implementation.

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 04 Oct 2013 14:18:36 +0200

> may then be inferred further.)  

The primes used by NIST curves are so special that there is less room for suspicion of a backdoor in the primes than in
the curve.

Our main concern with the special primes used by NIST curves is that their special form requires more caution to harden
your arithmetic against side-channel attacks. As a matter of fact, Sakai & Sakurai, for instance, have proposed power
analysis attacks targeting arithmetic on Pseudo-Mersenne primes. And we don't know, if the NSA has developed improved
side-channel attacks against ECC over such fields.

As I understand, the Curve25519 papers address side-channel immunity by specifying an eligible arithmetic. No objection
to that approach, but for the Brainpool curves we had a different one.

Another aspect was that we avoid many patents by not using Pseudo-Mersenne primes.

Johannes

---

From: Rene Struik <[email-masked]>
Date: Fri, 04 Oct 2013 08:57:44 -0400

[offline note]

Hi Johannes:

Thanks for your note. I presume you refer to the paper:
Side Channel Analysis - Simple Power Analysis on Fast Modular Reduction 
with ECC over Generalized Mersenne Primes (Yasuyuki Sakai, Kouichi 
Sakurai, IEICE Trans.Fund., 2006)

I am glad you refer to side channel resistance and implementation 
attacks, an often undershed aspect of security discussions (certainly in 
standardization bodies).

The paper suggests the need to weed out conditional branches, as are 
also a problem in other implementation attacks. Do you think that 
modular reductions with NISTp curves are generally hard to secure, or 
just the naive and well-documented approach? I would be curious if you 
have some data that delves on this with Brainpool curves. {As an 
example, if one uses Barrett reduction (Alg. 2.14 of Guide to ECC book), 
one has a conditional branch as well. This being said, this can be 
massaged away.}

As to patents: for basic scalar multiplication, this era should be 
nearly over, if one discards implementation attacks; if one doesn't, it 
does not seem to, though.

Best regards, Rene

On 10/4/2013 8:18 AM, Johannes Merkle wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "D. J. Bernstein" <[email-masked]>
Date: 5 Oct 2013 19:29:50 -0000

Dan Brown writes:
> it is also reasonable to assume that NSA knows of an attack A
> but is unwilling to reveal it, and manipulated P256 to avoid A

Sure. In BigBrotherLand, the eavesdropper Eve is actually a big fan of
the innocent users Alice and Bob, and is helping protect them against
hidden weaknesses in their communication system.

However, our job as _cryptographers_ is to tell Alice and Bob how to
protect themselves against the possibility of _bad_ behavior by Eve.
That's why all these ECC standards are advertising the "verifiable"
randomness of the NIST curves---they're claiming that the curves are
protected against bad behavior by NSA's Jerry Solinas. That's also why
people are unhappy to learn that the advertising is false.

When we see a protocol that turns out to have Eve as a trusted third
party with the power to compromise security, we fix the protocol. We
don't say "Well, gee, maybe Eve is actually helping our security."

> The Brainpool curves have some kind of justification, albeit maybe not
> a full-fledged proof.  In other words, to me, the Brainpool approach
> presents some kind of best-we-can-do-effort to resist attacks not yet
> known to us.

No, it doesn't. Maybe an unknown attack is _more_ likely to break
brainpoolP256r1 than to break Curve25519. You keep using words like
"best" and "prudence" and "advantage"; but you have zero justification
for any of this. You keep

   * misrepresenting brainpoolP256r1 as a random curve and
   * stating the "random is safer" myth in several different ways;

do you not realize that this myth was solidly debunked several years
ago? Section 11 of http://eprint.iacr.org/2008/390.pdf presents several
clear counterexamples; do you dispute those counterexamples?

If you think there's some reason that brainpoolP256r1 is more like the
examples where randomness helps security, rather than the examples where
randomness hurts security, then you should say what that reason is. You
can't simply pretend that the counterexamples don't exist.

By the way, I also don't see anything in the Brainpool document along
the lines that you're claiming. For example, the document never claims
that its primes are more secure than "special" primes; it clearly states
that it avoids "special" primes "to avoid patented fast arithmetic."

---D. J. Bernstein

---

From: [email-masked] (Martin Rex)
Date: Tue, 8 Oct 2013 22:51:29 +0200 (CEST)

Peter Gutmann wrote:
> Yaron Sheffer <[email-masked]> writes:
> 
> >I think we've been through all these arguments (on both sides of the issue)
> >over the last week, with the exception of "ECC brittleness". Can you please
> >clarify what you mean by that?
> 
> So with RSA-authenticated DH all you need to do is use a constant-time modexp
> on the server when you sign and pre-encode the PKCS #1 expected result and use
> a constant-time memcmp() on the client when you verify and you're OK.  If you
> did that ten years ago then you're safe against pretty much everything that's
> come along since then.
> 
> With ECDLP-based algorithms in contrast there's a whole range of issues you
> need to take into account, the worst of which is the distressing propensity of
> the DLP algorithms to leak the private key if you get even the tiniest detail
> wrong.  Not only do you have to get all of these finicky details exactly
> right, but every now and then someone points out a new issue that you then
> need to retroactively patch into your existing code base.  For example if you
> used the recommended (until not too long ago) way to generate your k for 
> (EC)DSA then you'd leak a tiny bit of your private key on each signature
> (again, that nasty propensity of DLP algorithms to leak the private key).
> That's what I meant by ECC, and DLP in general, brittleness.

Which
  "recommended (until not too long ago) way to generate your k for (EC)DSA"
are you referring to specifically?

Is or was this part of FIPS 186-x for DSA--or some X9.xx document for ECDSA
that do not have (not having coughed up the $$), and is that specific
issue sufficient to enable the attack described in this paper:

  Jean-Charles Faugere, Christopher Goyet and Guenael Renault
  "Attacking (EC)DSA Given Only an Implicit Hint"

  http://www-polsys.lip6.fr/~goyetc/doc/ImplicitECDSA_Goyet.pdf

(My own understanding of the crypto math is rather poor)

What's also irritates me is that every intentional weaknesses or bias in
a DRNG could enable this attack.  IIRC, EC_Dual_DRNG has both, a bias
and a weaknesss.  It also makes me feel uneasy about secret RNG designs
such as Intels RDRAND--on top of the Problem that RDRAND expands
1.5 GBit/s alleged real randomness into 6 GBit/s weakened output
(rather than the reverse, compressing it).

The fact that TLS requires a new and independent signature on the
(EC)DHE params in ServerKeyExchange on every full handshakes makes
it easy to obtain (EC)DSA signatures in large numbers and short time
through successful and therefore unsuspicious "full TLS handshakes".

Btw. where would one find the information necessary to implement
(EC)DSA safe with respect to the state-of-the-art?  The references
in rfc4492 (ECC for TLS) and rfc6460 (Suite B Profile for TLS)
appear somewhat static:
  http://tools.ietf.org/html/rfc6460#section-7
  http://tools.ietf.org/html/rfc4492#section-10

Wouldn't it make sense to first ensure that implementors _know_ what
known problems they have to watch out for TODAY (which is not necessarily
part of the original algorithm specs), before we ask them to prefer/migrate
to such algorithms?

-Martin

---

From: Dan Brown <[email-masked]>
Date: Wed, 9 Oct 2013 16:28:53 +0000

D. J. Bernstein writes
> Dan Brown writes:
> > it is also reasonable to assume that NSA knows of an attack A but is
> > unwilling to reveal it, and manipulated P256 to avoid A
> 

Aside, and smaller point: To me, the fact that the NIST Koblitz curves and
the curves

http://cacr.uwaterloo.ca/techreports/2001/corr2001-68.ps
 
seem just as free from manipulation as Curve25519, seems like mild evidence
against a backdoor in P256.  Publication of these alternatives would
undermine a plan to get one's adversary to use backdoors unwittingly.  I
think I already made this point on the TLS list.

> people are unhappy to learn that the advertising is false.

Good point: I did not realize most people were unaware that the seeds had no
explanation, yet still concluded verifiably random ruled out every possible
mischief.  I also agree that "verifiably random" is a misnomer, but did
consider it a minor one.  Do you have a better suggestion?  

Also, this is why I am trying to understand what you are advertising about
Curve25519.

You gave an example that, under reasonable assumptions, with 2^(-30)
probability the ECDLP in Curve25519 could be solved in 2^64 computations.  I
do not see how those assumptions are reasonable, but even so, if 2^30 people
use Curve25519, then is that a good risk?  Do you feel that the system-wide
risk for RSA, or integer DH is comparable?

> don't say "Well, gee, maybe Eve is actually helping our security."

Yes, but I think already implied this when I said should assume the worst,
etc.  

> brainpoolP256r1 than to break Curve25519. You keep using words like
 
Maybe.  Maybes will always exist in crypto.  We just try to reduce them,
whenever and however we can.

> clear counterexamples; do you dispute those counterexamples?

Thanks, I had completely forgotten about that paper, probably because I
don't see ether issue as very important.  In other words, we're splitting
hairs.

Anyway, the eprint of Koblitz, Koblitz and Menezes [KKM] lumps brainpool
into the class of random curves, similarly to me.  

Of course, the brainpool curve is a fixed curve.  (I don't think ever
misrepresented that fact.)  If the brainpool and nist seeds were kept
secret, then these pseudorandom curves would be hard to distinguish from
some class of random curves, or do you dispute that?  I don't think that
"maybe" attack against brainpool curve that you hypothesize above, is
intended to be a such distinguisher (although it could be, since we're
talking possibilities now), but rather one that, by some fluke, affects that
particular seed used in the brainpool.

The KKM paper does not say "myth", it says "conventional wisdom".  Yes, I am
just applying the conventional wisdom.  KKM do not claim to "solidly debunk"
that wisdom, and instead say we are left to make our "best guess" about
future attacks.

Their examples about prime-field curves make "plausible" assumptions about a
future attack.  Well, one could "plausibly" assume that a future attack
affects a random curves uniformly at random, and then conclude that one
fixed curve is just as good as any other.  But, this seems to me almost like
circular reasoning. In other words, I do have some trouble with their
example: their assumptions may be artificial.

I also dispute the implicit KKM contention that conventional wisdom did not
admit any possibility special curves could be safer.  Rather I see
conventional wisdom already looked at the evidence and made its "best guess"
that random curves would be safer, admitting the possibility that it could
be otherwise.

Also, I don't fully agree with the implicit KKM contention that just because
some attacks are unknown, and that various attacks will always be possible,
therefore we should totally rely on intuition.  I agree that intuition, as
in "best guess" is a good start, but a careful algorithm selection should
try to formalize this initial intuition, isolate and reduce assumptions,
prove what little can be proved and so on. 

The KKM example about isogenies between curves is very interesting, of
course.  Maybe I am mistaken, but I think that brainpool curves address that
via the c(E) thing.  Have you considered the equivalent for Curve25519?  It
would be interesting to know if the ECDLP in Curve25519 is, via isogenies,
equivalent to the ECDLP in many other curves (perhaps only of the same
size).  They we could focus our debate a little better.

> examples where randomness helps security, rather than the examples
> where randomness hurts security, then you should say what that reason
> is. You can't simply pretend that the counterexamples don't exist.

I was not pretending, but I did make a bad mistake: when I assumed that
worst for Curve25519, I forgot to assume the worst for random curves.  In
other words, I supplied the wrong reason for my position.  So, I have being
thinking a little more about why I hold this position. Here's what I have so
far, all of which is informal.  Also, I am restricting this to prime-field
elliptic curves.

1. Suppose some extremes: if an attack affects all random curves, excluding
Curve25519, then basically ECC would be no more, and Curve25519 would now
belong to the class "Special Elliptic Curve Cryptography".  How logical
would it be for SECC to inherit the previously believed security of ECC?
Maybe it SECC would be secure, but clock would have to started anew to build
up trust.  The opposite extreme is that some attack affects only a special
class of curves, as in the MOV and SASS attacks.  Then ECC goes on, with not
much worry, and we just drop those affected curves.  This has happened twice
already.

2. So far, there no are 0 (*) attacks against random curves, and 2 against
special curves: the MOV and SASS attacks.  I view this as quite good
evidence in favour of random curves, over special curves.  Of course, the
next attack could be against random curves.  Of course, with only 2 attacks,
the evidence is slim.  In addition to this evidence of these two attacks,
consider these attacks are rather old, and no new ones have been published
for many years.

Regarding this point (#2), I have a hard time reconciling some of your
views: 

"zero justification": you keep saying this phrase, and applied against
random safer than special.  Is this referring to fact that there's always a
possibility of something completely surprising and unlike past experiences? 

"overwhelming evidence": you used this phrase, I think in reference to the
MOV and SASS attacks, to support the argument that Curve25519 belong to a
different special class than the known weak special classes.  (I.e.
something about the field sizes, the curve sizes and coefficient sizes being
irrelevant, because they do not figure much in the MOV and SASS attacks).

What I am having trouble with is how the same fact set (MOV+SASS) presents
both "zero justification" for arguments that favour brainpool over
Curve25519 and "overwhelming evidence" for brainpool incomparable to
Curve25519.  Could you elaborate? 

3. This next reason is very informal, but I think it affected my thoughts.
Curve25519 is a newcomer to TLS, compared to the NIST curves and brainpool
curves, and as such, warrants scepticism.  The burden is on any new
algorithm presented to TLS is to identify its advantages, and these claims
should be scrutinized by the TLS WG.  Curve25519 may have sufficient other
advantages over alternatives for adoption in TLS: efficiency, secure
implementation, and so on.  I suggest that offering Curve25519 as a means to
provide algorithm agility, e.g. if RSA, integer DH, and random EC including
brainpool collapse, then maybe Curve25519 will be sole survivor.  Certainly
possible.

//

On the other hand, after reading Section 11 of KKM, I remembered something
else that is a slight shred of evidence that special curves are safer than
random curves (although not with respect to the ECDLP):

The Cheon-type attacks affect random curves slightly more adversely than
certain special curves.  That is, some special curves in which n-1 and n+1
are nearly prime resist Cheon-type attacks, but these curves are rare among
random curves (or sizes), so could be viewed as special.  

Although this is a very weak attack, and arguably moot if one assumes
one-way KDFs, it exists, unlike the hypothetical attack as in the KKM
examples on prime-field elliptic curves.  

I don't think that this is enough evidence to override the other evidence
favouring random curves, though.

//

If we move far away from prime-field elliptic curves, say to hash functions,
then I do not see any evidence that random is safer special.  Indeed, if one
defined a random hash function by random sequence of bit operations, perhaps
formalizing this through straight line programs, then, I would imagine the
security would be very bad.  In that case, special seems safer than random.
(Going yet farther astray, I think there's results in coding theory that
random codes can do as well as special codes.)  Anyway, to argue random over
special in the case ECC, we have to look at the evidence particular to ECC.

> that its primes are more secure than "special" primes; it clearly
> states that it avoids "special" primes "to avoid patented fast
> arithmetic."
> 
 
Yes, I already acknowledged most of that previously in this thread.
---------------------------------------------------------------------
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.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Oct 2013 00:30:58 -0000

Dan Brown writes:
> if an attack affects all random curves, excluding
> Curve25519, then basically ECC would be no more,

Here are six examples of attacks that already affect the security level
of the vast majority of elliptic curves:

   * Shanks's baby-step-giant-step attack. Drastic reduction in the
     number of arithmetic operations required to break ECDLP. There's no
     defense against this attack.

   * The Pohlig--Hellman attack. Further drastic reduction in the number
     of arithmetic operations required for _most_ curves---but not all;
     there are occasional special curves that resist the attack.

   * Twist attacks. Again applicable to _most_ curves---but, again, not
     all; again there are occasional special curves that resist the
     attack.

   * Negating rho. Okay, it's just a 1.4x attack speedup, but I can't
     see any justification for you to ignore it. There's no defense
     against this attack.

   * Pollard's rho attack. Drastic reduction in _memory_ consumption,
     making elliptic curves much easier to break (in reality, and in
     sensible cost metrics). There's no defense against this attack.

   * The van Oorschot--Wiener parallel rho attack. Drastic reduction in
     _communication_, allowing efficient parallelization, again making
     elliptic curves much easier to break. There's no defense against
     this attack.

So you're wrong in implying that there haven't already been attacks that
affect "random curves". Do we respond by discarding ECC, as you suggest?
Of course not. We respond by choosing parameters to resist the attacks:

   * Choose _extremely_ special curves (we're talking about one curve in
     a thousand here!) that defend against twist attacks and the
     Pohlig--Hellman attack.

   * Choose primes far above 200 bits to defend against the other four
     attacks.

Of course, we also take time to further investigate and build confidence
that the security story is stable. All of these attacks have been known
for more than ten years (three of them even before ECC was published),
as have the two attacks that you mentioned for extremely rare curves.
People working on attacks have found interesting improvements for
extension fields, higher genus, etc., but seem to have run out of ideas
for attacking prime-field ECC.

> So far, there no are 0 (*) attacks against random curves, and 2 against
> evidence in favour of random curves, over special curves.

That's because you're simply ignoring all the contrary evidence. For
example, if you insist on using random curves then Pohlig--Hellman will
damage your security, probably quite severely. That's why everyone is
actually using rare curves that resist the Pohlig--Hellman attack.

In other words, rather than taking the uniform distribution over all
elliptic curves of whatever size, ECC users are massively biasing the
distribution of elliptic curves. The biased distribution discards the
vast majority of elliptic curves: at least the curves vulnerable to
Pohlig--Hellman, and nowadays also the curves that aren't twist-secure.
Every sane risk analysis will conclude that this bias is a good idea.

I say that it's a good idea to narrow the distribution even more, in
fact down to a single curve, by taking the _smallest_ curve coefficient
within the usual massively biased distribution. That's what Curve25519
does. This isn't just a performance win; it also prevents the sort of
manipulation that's clearly possible for someone who claims to be
"randomly" choosing curves from the wider distribution.

Now imagine that there's no manipulation. How does this single-curve
distribution compare in security to the larger (massively biased)
distribution against some unknown attack? The correct answer is that we
have no idea---maybe it's more secure, maybe it's less secure, maybe
it's the same.

You keep trying to trivialize this question by promoting the myth that
more uniformity is safer. You present this as some sort of ill-defined
dichotomy between "random" and "special", with "random" clearly being
better. You take every break of a small curve class as support for your
position, retroactively declaring the curves in the class to be
"special", while you ignore the glaring counterexamples such as
Pohlig--Hellman.

> probability the ECDLP in Curve25519 could be solved in 2^64
> computations.

No. What I actually wrote was "Suppose NSA knows---and knew in the late
1990s---a cost-2^64 attack that breaks one P1363-compliant 256-bit curve
in a billion". I gave examples to illustrate that this "wouldn't be out
of line with the spectrum of known ECC attacks". I then explained how
this attack would have allowed NSA to _guarantee_ weakness of the NIST
P-256 curve, while for an honestly generated curve the situation is
obviously quite different.

By misstating my assumptions as being specific to Curve25519, you're
omitting the critical security impact on NIST P-256, and you're also
promoting a misconception that ECC security analysis is curve-specific.

> I do not see how those assumptions are reasonable, but even so, if
> 2^30 people use Curve25519, then is that a good risk?

I have no idea what you think you mean by "a good risk" (and I also have
no idea why you're talking about the number of people---the discussion
is about weak curves, not weak keys). In the situation that I actually
described, there's no reason to think that the risk is different for
Curve25519 and for an _honestly_ generated NIST P-256. The problem is
that we don't know whether NIST P-256 was honestly generated.

> Do you feel that the system-wide risk for RSA, or integer DH is comparable?

There are improvements in index calculus all the time. Those have been
continually dragging down the security level of RSA, which in turn has
been dragging down the performance of RSA, which is exactly why modern
RSA is so much slower than ECC.

---D. J. Bernstein

---

From: Dan Brown <[email-masked]>
Date: Wed, 16 Oct 2013 19:36:48 +0000

D. J. Bernstein writes:
> Dan Brown writes:
> > if an attack affects all random curves, excluding Curve25519, then
> > basically ECC would be no more,
> 
> So you're wrong in implying that there haven't already been attacks
> that affect "random curves". Do we respond by discarding ECC, as you

Yes, those are pretty good examples favouring special over random, but they
are not pertinent to my analysis.

The S, PH, P, and vOW attacks above affect any group over which one does
DH/DL crypto.  They are not ECC-specific.  

Resisting these attacks and doing DH/DL crypto requires ensuring the
parameters resist the attacks.

So, any DH/DL system needs to use a group whose order has a prime factor of
bit size at least twice the desired security level.

If I was an opponent of DH/DL, let's say RSA or NTRU, I might use these to
argue against DH/DL.

One reason, despite such arguments, to still use DH/DL is forward secrecy.
I don't know if NTRU provides forwards secrecy as efficiently as DH/DL.

I made a mistake in my previous email about the class of curves to which I
restricted: I forgot to specify that I meant random EC curves that meet
these generic conditions. 

When I say "curve" in the context of ECC, I assume this condition.  Maybe
you have a more mathematically correct perspective, and read random curve to
include these vulnerable to PH.  

The twist attack is just as easily addressed by checking the point before
applying one's private key to it.  (Unless I misunderstand.)  Yes,
implementation fault resistance is important, but it is secondary to
algorithm security, because an insecure algorithm cannot be fixed any kind
of implementation technique.

In this case, my personal opinion is that the most reasonable guesses at the
difference in algorithm security here are so slight, then implementation
fault resistance benefits of Curve25519 have much merit.  In other words, I
wouldn't object to that argument.

The negation attack is considerably weaker than the MOV and SASS attacks,
and in any case it seems to be the price to pay for any form of ECC. So, it
cannot be used to choose between curves.

To summarize, once one sets up the basic DH/DL requirements, and tries to
make a choice of ECC for this purpose, then the attack count is still 0
random, and 2 special (or 1 if you prefer to merge MOVFR and SASS into a
transfer attack).

Based on this score, if I had to guess what the next attack would be, then I
would guess special.  An attack on random would be a breakthrough.
Therefore, trying to choose a random curve is a best guess approach.

> suggest?
> Of course, we also take time to further investigate and build
> confidence that the security story is stable. All of these attacks have
> been known for more than ten years (three of them even before ECC was
> published), as have the two attacks that you mentioned for extremely
> rare curves.
> > So far, there no are 0 (*) attacks against random curves, and 2
> > against special curves: the MOV and SASS attacks.  I view this as
> > quite good evidence in favour of random curves, over special curves.
> 

I already answered this above, but in brief: PH must resisted by all forms
of DH/DL crypto, so is not a basis to choose between EC curves.

And yes again, I did forgot to mention in my definition of random curves the
condition that the group order be divisible by a large prime.

This is a fact that I take for granted.

> Every sane risk analysis will conclude that this bias is a good idea.

Not that it matters, but my psychiatrist let me go home.

> have no idea---maybe it's more secure, maybe it's less secure, maybe

Uncertainty, "no idea", about unknown attacks is a given, but we should
still try to resist them, even if that means making assumptions and
guessing.  Provably secure algorithm try to do this.  Previously unknown
attacks are known pop up, occasionally.   But, we also give weight to the
effort that people have exerted in trying to find attacks, to infer the
unlikelihood of new attacks being discovered.    

> "special", while you ignore the glaring counterexamples such as Pohlig-
> -Hellman.

As I said above, I take PH resistance for granted in any DH/DL, and a built
into the ECC.

> 1990s---a cost-2^64 attack that breaks one P1363-compliant 256-bit
> curve in a billion". I gave examples to illustrate that this "wouldn't
> be out of line with the spectrum of known ECC attacks". I then
> explained how this attack would have allowed NSA to _guarantee_
> weakness of the NIST

Why was I wrong? Is it because Curve25519 is not P1363-compliant?

> promoting a misconception that ECC security analysis is curve-specific.
 
Yes, your supposition applies to any fixed curve, including Brainpool and
Curve25519.  Yes, it is not curve-specific. 

> I have no idea what you think you mean by "a good risk" (and I also

Good meaning sufficiently small compared to the benefit.

> have no idea why you're talking about the number of people---the
> discussion is about weak curves, not weak keys). In the situation that

If an algorithm is weak, then all its users lose.  My heuristic is that the
ensuing loss is proportional to the number of (human) users.  Such
heuristics might be useful to define what a good risk is.  Granted for most
risks we have make a lot of guessing, but it still has merit to try.

> I actually described, there's no reason to think that the risk is
> different for
 
See all my arguments above.

> that we don't know whether NIST P-256 was honestly generated.

Agreed that is a problem.  

I am still surprised that you think it so reasonable a supposition.

I forgot now, what attacks you quoted to support that position.  Was it PH?

> RSA is so much slower than ECC.

Yes, that's well-known, but is it reasonable to suppose that, with
probability 2^(-30) some lurking adversary knows an attack a 2^64 cost
attack against each possible RSA key?  I don't see any evidence to support
that reasonability of the weakness in the whole RSA algorithm.  (Weak
low-density classes of RSA keys, maybe but that's different.)

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Oct 2013 18:05:32 -0700

> unlikelihood of new attacks being discovered.
So you agree that E(random curve falls to unknown attack)=E(Curve25519
falls to random attacks). (This is is obvious unless
cosmic conspiracy happens, and if it isn't, think about it). But now the
question is whether the author of the random curve really picked it at
random, vs specified a curve. And then the fact that DJB specified at
most 17 bits or so is very important: a new attack would have to work
on 2^{-17} of all curves to work on Curve25519.
Sincerely,
Watson Ladd

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

---

From: Dan Brown <[email-masked]>
Date: Thu, 17 Oct 2013 15:46:13 +0000

Watson Ladd wrote
> Dan Brown wrote
>
> > Based on this score, if I had to guess what the next attack would be,
> > then I would guess special.  An attack on random would be a
> breakthrough.
> ...
> > Uncertainty, "no idea", about unknown attacks is a given, but we
> > should still try to resist them, even if that means making
> assumptions
> > and guessing.  Provably secure algorithm try to do this.  Previously
> unknown
> > effort that people have exerted in trying to find attacks, to infer
> > the unlikelihood of new attacks being discovered.
> >
> falls to random attacks). (This is is obvious unless cosmic conspiracy
> happens, and if it isn't, think about it). But now the question is

Sure, but confining ourselves to "random attacks' is way too optimistic. 
Future, and unknown, attacks will not necessarily be random.

Also, that is not at all what I was talking about in the text you quoted.  In 
fact, earlier in this thread, I mentioned this random attack argument as being 
almost circular, assuming one what one aims to establish, and that this was 
similar to what Koblitz, Koblitz and Menezes argued.

Well, maybe you mean something other than "random attacks"?

> whether the author of the random curve really picked it at random, vs
> specified a curve. And then the fact that DJB specified at most 17 bits
> or so is very important: a new attack would have to work on 2^{-17} of
> all curves to work on Curve25519.

Just curious: where's the 17 from?

Why couldn't a new attack just work on one curve, namely Curve25519?  If I 
understand correctly, DJB has argued that the ECC theory and experience would 
be evidence for a claim similar, but perhaps not as strong, as your claim.

Sure, a new attack could work against just one brainpool curve too.  But for 
brainpool, there a three prongs against such a single curve attack: the ECC 
theory and experience, the use of SHA1 of in brainpool definitions, the use of 
Pi and e in the brainpool curves.  That would definitely be a "cosmic 
conspiracy".

The MOV and SASS worked on small fractions of curves.  If I recall correctly, 
in both cases there had already been proposals to use special curves (for 
efficiency and other convenience reasons) affected by these attacks, before 
the attacks were discovered.  The risk of this happening again for Curve25519 
is much smaller, because of the many intervening years of research into ECC. 
That's why I view Curve25519 as safe, but in the context of resisting unknown 
attacks, the evidence supports brainpool, or an honestly-generated P-256 as 
slightly safer.

...

The most compelling argument, at least to me, against my position is the 
Pohlig--Hellman attack, which DJB already raised a couple times.  I've exclude 
this attack from my evidence, because it is generic to DH/DL, and Curve25519, 
Brainpool and P256 all address PH attacks in the same way, with a low-pass 
filter.

Arguably, we could have boosted the group size, and resisted PH with a 
high-pass filter, resulting in DH/DL that belong to a larger class of groups. 
That would have been less efficient, but also not very compelling for security 
because is there is evidence of low-density generic DH/DL attacks, i.e. 
special groups, that need to be avoided.  Thus the decision to resist PH by 
using a low-pass filter (e.g. searching random orders until one nearly prime 
was found) does not seem to introduce a risk.  In the case of PH-protected 
ECC, the weak argument to avoid special curves is to avoid another MOV or 
SASS.

---

From: Johannes Merkle <[email-masked]>
Date: Thu, 17 Oct 2013 18:32:29 +0200

> be evidence for a claim similar, but perhaps not as strong, as your claim.

There is really no use in speculating about future attacks as long as there are not some clear indications about their
presence and potential. An example of the latter case is the anticipation (or is is merely a feeling in the guts?) by
some researchers of an attack potential for certain curves having small class group orders, and even the validity of
this educated guess is controversially disputed.

Nobody knows which curves unforeseen attacks (I mean to exclude the latter example by this term) will affect. IMO any
speculation about this (including the present discussion) is metaphysics.

BTW, my understanding of DJB posts was that he only meant to contradict your hypothesis on certain curves being more
likely being affected by future attacks than others, but as far as I understood, he never made any claim about the
impact to be expected by future attacks.
-- 
Johannes

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Oct 2013 11:38:53 -0500

> be evidence for a claim similar, but perhaps not as strong, as your claim.

Let's say that there are single-curve attacks.  We don't know how many
curves have such attacks, nor how hard it is to find such attacks for
specific curves, or specific curves with such attacks.  Perhaps DJB
does know, but either he got spectacularly lucky (if such attack/curve
pairs are rare) or such attack/curve pairs are very common.  The
latter would imply that all ECC is busted, in which case we needn't
worry about whether Curve25519 is weak because we have bigger
problems, so we must ignore this possibility when comparing curves to
one another.  That leaves the former, and now we need some estimate of
frequency of such attack/curve pairs in order to decide if any one
curve is weak.

We don't have such an estimate, but surely whatever that frequency is,
it's the same for all cryptographers.  That means that for any one
standard curve, the likelihood of it being weak this way is about the
same if the possible attacks for each curve were not known at the time
they were discovered.  Now we just need to know whether the curves in
question were selected with or without such knowledge, but we can't
know this [yet], so instead we must estimate the likelihood that the
authors selected a weak curve on purpose.  An estimate of weak curve
distribution/frequency would allow us to estimate the likelihood that
a curve was selected because it was weak.

If some curve required specifying N bits of information, then it must
have been picked from a range of 1..2^2N or so curves (the 2^2N upper
bound is an estimate), *roughly*.  The larger the N, the larger the
freedom the author has/had in selecting a weak curve.  Whatever the
frequency of weak curves, the smaller the N, the more luck an author
needs to pick a weak curve.

That, I think, is the argument for why DJB curves' selection criteria
are more rigid (i.e., less subject to manipulation) than Brainpool
curves.

Now, if one out of every 5 curves are weak, then clearly there's a
great chance that DJB curves are weak.  If, for small Ns, one out of
every 5 curves are weak, while for large Ns one out of every trillion
curves are weak, then Brainpool curves are stronger than DJB curves.
I.e., the distribution of weak curves matters.  We know nothing about
the distribution of such weak curves -- the associated attacks are not
known, they are merely conjectured for the sake of argument after all.

It seems unlikely that there's a class of attacks on curves where the
distribution of weak curves tails off as curve complexity (size of
constants) increases.  But we can't really know anything about this
conjectured class of attacks each limited to one or few curves.

I'm not sure what we should assume, but all else being equal my
conclusion is that we should prefer curves whose selection criteria
left very little freedom to those doing the selection.  This might
include Brainpool-like (i.e., with large constants) curves, but I'd
want the selection to work as follows: one small group of people
publicly select a hash function, another disjoint set of people
independently, publicly (videotaped), and concurrently select a short,
simple, and *meaningful* English language string ("hello world"), then
pick the largest constants smaller than bounds computed from that hash
applied to that string.  In the meantime DJB curves were clearly
selected with very little freedom to select for rare weak curves,
therefore I believe we can trust them.

Nico
--

---

From: Dan Brown <[email-masked]>
Date: Fri, 18 Oct 2013 14:21:43 +0000

Nico Williams wrote:
> Dan Brown  wrote:
> > Why couldn't a new attack just work on one curve, namely Curve25519?
> > If I understand correctly, DJB has argued that the ECC theory and
> > experience would be evidence for a claim similar, but perhaps not as
> strong, as your claim.
>

Well, you've assumed here, just like others, that attacks are random.  If you 
assume that attacks are random, then you are right that manipulation is the 
main threat.

I've argued a few times that assuming random attacks is too optimistic, and 
also close to circular reasoning, and not supported by the evidence.

Remember, Curve25519, though free from the potential of malicious 
manipulation, is chosen, in part, for its special efficiency properties. 
These special properties may also given an attacker special advantages.  DJB 
has already argued, based on the existing attacks  -- not random attacks --  
that this is unlikely.   And I agreed.

Consider the ECC history.  After resisting all generic attacks, we have the 
following

Miyaji proposed special trace 1 curves.  A few years later, these were broken 
by the SASS attack.

Various proposed supersingular curves.  Later, they were broken by the MOVFR 
attacks.

But ever since then, it has been fairly quiet on the prime-field side of ECC.

> pairs are rare) or such attack/curve pairs are very common.  The latter
> would imply that all ECC is busted, in which case we needn't worry
> about whether Curve25519 is weak because we have bigger problems, so we
> must ignore this possibility when comparing curves to one another.

Furthermore, if we admit this possibility, i.e. to justify that the ECDLP over 
P256, then we should not just ignore it, but consider alternatives to ECC.

As I understand it, DJB has put forward his reasonable supposition of what the 
bigger problem is.  Maybe you should review it.

> That leaves the former, and now we need some estimate of frequency of
> such attack/curve pairs in order to decide if any one curve is weak.
>

Of course, it's very hard to make such estimates.  Even so, there is merit in 
making such estimates.  They have to been based on evidence.  There two types 
of evidence here:

1.  The lack of new attacks, despite efforts and incentives.

2.  The existing attacks, e.g. MOVFR and SASS.

Intuition might entirely dismiss inferring estimates from this evidence set, 
as wild speculation.  More formally, intuition would be saying the inference 
drawn from the set have low confidence.

---

From: Nico Williams <[email-masked]>
Date: Fri, 18 Oct 2013 11:00:16 -0500

> assume that attacks are random, then you are right that manipulation is the

I assumed all of: random attacks ("[w]ed don't know how many") and
attacks where one knows how to create a curve so it will be vulnerable
("[w]e don't know ... how hard it is to find ... specific curves with
such attacks").

> also close to circular reasoning, and not supported by the evidence.

Random attacks are the reason to want rigid curve selection processes.

That leaves the other possibility, that the curve author knows how to
create curves that will be vulnerable to some class of attacks without
a random search.  Here we can use curve selection criteria that
involve parameter selections that no one person/entity can control --
verifiably.

Surely that was your point, no?  That curve25519 might be "special"
(as in specially weak) in some way that you (and I) don't know.

> But ever since then, it has been fairly quiet on the prime-field side of ECC.

We can look at things other than the constants in curve25519 (and
curve 1174, and curve3617) -- the class(es) of curve(s) that it (they)
fits.. separately from the curve selection criteria.  How do we
mitigate unknown weaknesses in each curve class?  The only thing I
know is: algorithm agility.

As for selection criteria, I think I'd prefer a verifiably random
selection process over the smallest freedom approach, but where
there's doubt about the random selection process' verifiability I
prefer the latter over the former.  The problem is that as time passes
it becomes more difficult to verify that a long-ago random selection
process was not manipulated -- we have to trust records of history in
order to believe that it wasn't.

> P256, then we should not just ignore it, but consider alternatives to ECC.

I didn't mean that we should flat out ignore that possibility.  I was
very specific: "... so we must ignore this possibility WHEN COMPARING
CURVES TO ONE ANOTHER".  I said nothing about comparing ECC to
non-ECC.  Once more, the only way I know of to mitigate against
unknown attacks is algorithm agility.

For ephemeral DH algorithm agility is relatively simple: require to
implement N different DH algorithms, make it easy to turn off any of
them if they get broken.

For other ECC uses algorithm agility is much harder: it involves
re-keying.  We could require that principals have N public keys (in
PKI cases, that all N certs have the same names and so on, issued by
the same issuer), so that it's possible to drop any one that gets
broken later.  But even this, I think, may be too much to ask for.

So at some point we have to pick something.  At some point, in spite
of uncertainty, we have to select some algorithm as the one we're
going to rely on the most for authentication.  Which would you rather
use?

> drawn from the set have low confidence.

So do nothing?  Ignore the whole field?  I'm not sure where you're
going with this.  What specific advice are you giving us?

Nico
--

---

From: Michael StJohns <[email-masked]>
Date: Fri, 18 Oct 2013 12:35:49 -0400

I've been watching the curve conspiracy discussion stuff for a bit. I 
don't actually know what the reality is.  So I decided to try and find 
the earliest mention of one of the seeds.  I half expected I was going 
to find the seed string had been pulled from the random number tables in 
the CRC handbook.

I googled for "C49D3608 86E70493 6A6678E1 139D26B7 819F7E90" - the seed 
for P256 and found:

ftp://ftp.iks-jena.de/mitarb/lutz/standards/ansi/X9/x962-11-17-97.pdf

This document has the seed for P256 and P192 (which also matches) but 
not P384 or P521. Only sample curves up to 256 bits were provided.

The existence of this document, created in 1997 would tend to suggest 
that at least a few curves were created in X9 and not by NIST given the 
document precedes the FIPS 186-2 publication by a couple of years.  Of 
course, X9 could have just gotten the curves from NIST as a submission - 
but why weren't P384 and P521 provided at that point?

  I don't have access to the X9 archives - maybe someone out there has a 
set of X9 correspondence around 1997 or so that we could take a look 
at?  I would expect the curves to be some form of specific contribution.

Mike

---

From: Dan Brown <[email-masked]>
Date: Fri, 18 Oct 2013 18:42:16 +0000

Nico Williams wrote:
> Dan Brown <[email-masked]> wrote:
> > Nico Williams wrote:
>

Yes, good point and sentence.

Special attacks are the reason to want random curve selection.

> a random search.  Here we can use curve selection criteria that involve
> parameter selections that no one person/entity can control --
> verifiably.
>

My point was not about malicious curve selection, but its pre-requisite: 
existence of a weak class of curves.

> > These special properties may also given an attacker special
> > advantages.  DJB has already argued, based on the existing attacks  -
> - not random attacks --
> > Consider the ECC history.  After resisting all generic attacks, we
> > have the following
> >
> > Miyaji proposed special trace 1 curves.  A few years later, these
> were
> > broken by the SASS attack.
> >
> > Various proposed supersingular curves.  Later, they were broken by
> the
> > MOVFR attacks.
> >
> We can look at things other than the constants in curve25519 (and curve
> 1174, and curve3617) -- the class(es) of curve(s) that it (they) fits..
> separately from the curve selection criteria.  How do we mitigate
> unknown weaknesses in each curve class?  The only thing I know is:
> algorithm agility.

In addition to algorithm agility, random curve selection mitigates unknown 
weaknesses, e.g. Brainpool or P256 (but only if you trust its creator).

Hmm, maybe, I am missing your point about "curve class".

I believe that, elsewhere in this thread, I said algorithm agility would be a 
very good reason for including Curve25519, in addition to Brainpool.

Algorithm agility, though, does not help much, in general, against untold 
attacks (mainly helping against newly announced attacks).

In particular, we don't want to TLS to become laissez-faire roll any algorithm 
you want, i.e. the ultimate in algorithm agility?  At some point, TLS 
considers the evidence and picks a few good algorithms, right?  The choice 
governing this selection of each algorithm is not primarily algorithm agility. 
For example, AES was chosen for inclusion in TLS, not because of algorithm 
agility but because of the extensive analysis it underwent.  TLS did not, and 
still does not, adopt every single newly proposed algorithm in the name of 
algorithm agility.  So, something other than algorithm agility seems to be 
protecting TLS.

Also, separately from but similary to algorithm agility, algorithm X is not 
usually adopted in TLS just on the grounds that we know of no attack, else 
each new proposal would be adopted.  So, it is inconsistent to consider only 
about known attacks.  TLS has to consider what evidence there is against 
unknown attacks.

I contend that it is on this basis, that is reasonable scrutinize crypto 
algorithms, be it P256 or Curve25519.

> selection process over the smallest freedom approach, but where there's
> doubt about the random selection process' verifiability I prefer the
> latter over the former.  The problem is that as time passes it becomes
> more difficult to verify that a long-ago random selection process was
> not manipulated -- we have to trust records of history in order to
> believe that it wasn't.
>
> >> problems, so we must ignore this possibility when comparing curves
> to one another.
> >
> > Furthermore, if we admit this possibility, i.e. to justify that the
> > ECDLP over P256, then we should not just ignore it, but consider
> alternatives to ECC.
>
> CURVES TO ONE ANOTHER".  I said nothing about comparing ECC to non-ECC.
> Once more, the only way I know of to mitigate against unknown attacks
> is algorithm agility.

Sorry for the confusion. In this thread, I've been arguing two INDEPENDENT 
points:

- random curves have slightly more assurance than special
- if the threat against P256 is serious, then we had better seriously consider 
non-ECC

The evidence set for the two points is similar, which may cause me to look 
like an arguing for one point, when I am trying to argue the other.

Put another way, what's the point in comparing curves to each other, if we 
believe there's a bigger problem of ECC being busted.

Put another way, it's as if we have something like C = max(A,B) + |A-B|, then 
C is always better than A or B, unless A and B are the same.

> For other ECC uses algorithm agility is much harder: it involves re-
> keying.  We could require that principals have N public keys (in PKI
> cases, that all N certs have the same names and so on, issued by the
> same issuer), so that it's possible to drop any one that gets broken
> later.  But even this, I think, may be too much to ask for.
>
> So at some point we have to pick something.  At some point, in spite of
> uncertainty, we have to select some algorithm as the one we're going to
> rely on the most for authentication.  Which would you rather use?

Hmm, as an end user, I might go for the safest possible that can run on my 
device.

> > Of course, it's very hard to make such estimates.  Even so, there is
> > merit in making such estimates.  They have to been based on evidence.
> > There two types of evidence here:
> >
> > Intuition might entirely dismiss inferring estimates from this
> > evidence set, as wild speculation.  More formally, intuition would be
> > saying the inference drawn from the set have low confidence.
>

Oh, sorry, I was very unclear, hinging on the word "might" to express what 
others might intuit.  I was thinking about a totally different point.

My own intuition: I think ECC is safe, and that in the very unlikely case of 
any untold attacks, they will be at most similar in impact to MOVFR and SASS.

My advice: definitely don't worry about Brainpool.  Don't worry about P256, 
unless you view its creator as an adversary and you are somehow required to 
use ECC, almost against your will, instead of some alternative like RSA or 
integer DH.  Consider Curve25519 mainly if you really want efficiency, or 
don't trust the reliability of your implementation, and maybe also have dim 
view on the security of ECC alternatives.

TLS can safely adopt all these EC choices.

At some point, though, TLS may not want to allow too many choices.

---

From: Nico Williams <[email-masked]>
Date: Fri, 18 Oct 2013 15:28:16 -0500

> Special attacks are the reason to want random curve selection.

But then you need to construct a random curve selection process that
everyone will be able to believe [years later!] was not manipulated.
That's very difficult.  Even if we eliminate the unreasonably paranoid
from "everyone".

And then what if the selected curves don't perform well?  Pick the
next closest well-performing curve?  How would such a procedure affect
the trustworthiness of the selection process?

At least with DJB's curves I only need to worry that DJB (et. al.) has
knowledge about cryptanalysis on said curves that he (they) are not
sharing, that DJB is mounting an attack on us.  You worry about
special attacks that are not known to the public nor DJB, but to me
that's the same as "random", and all I care about is that the curve
authors not have known about them a priori, because then we can reason
(with no data, granted, so it's all hand waving) about the density of
such attacks in the neighborhood of the curves in question.

> weaknesses, e.g. Brainpool or P256 (but only if you trust its creator).

But since Dual_EC, we don't trust P256's creators.  That's a key
reason for this entire discussion.

> Hmm, maybe, I am missing your point about "curve class".

s/class/family/.

> very good reason for including Curve25519, in addition to Brainpool.

OK, good.

> attacks (mainly helping against newly announced attacks).

Unless you also have enough diversity of algorithms to begin with.
That's why a number of algorithms would have to be required to
implement (quite a few, actually, considering your doubts anyways, and
assuming we can't get good consensus on just two; you might have
doubts about just two different algorithms).

> governing this selection of each algorithm is not primarily algorithm agility.

But it should be -- it should be about ability to survive
cryptanalytic advances.  We've experienced this w.r.t. chained IV CBC
cipher modes in SSHv2, for example, where having deployed counter
modes saved our collective bacon once.

> algorithm agility.  So, something other than algorithm agility seems to be

I understand this.  And given the time we've had to cryptanalyze AES
maybe we feel really good about it, so maybe we don't need so many
symmetric ciphers.  But your arguments, assuming they carry the day,
argue for having several key exchange and signature algorithms -- I
don't see how else to interpret what you're saying.

> about known attacks.  TLS has to consider what evidence there is against

There's only so much we can do about unknown attacks.  Algorithm
agility + lots of algorithms (each from a different family).

> - if the threat against P256 is serious, then we had better seriously consider

You lost me with the second point.

As to the first, the problem is that assurance for random selection is
difficult -- aside from that I'd agree.

> believe there's a bigger problem of ECC being busted.

Yes, we need non-ECC algorithms too, well, at least for as long as
they are practical (i.e., RSA with 16KB keys are not).  But anyways,
we also need ECC because of its performance benefits.  At least until
quantum computers become sufficiently powerful that we have to drop
this entire field of cryptography anyways.

> Hmm, as an end user, I might go for the safest possible that can run on my

Well, OK, but we have a large diversity of devices and device
capabilities.  If we're going to wind down this thread with a
conclusion, we should get more specific.

> any untold attacks, they will be at most similar in impact to MOVFR and SASS.

OK, thanks.  My own intuition is that DJB's curves are safe from
as-yet unknown attacks.  It's just intuition.

> view on the security of ECC alternatives.

DJB argues cogently that the NIST curves are not safe enough.  I'm OK
with Brainpool, but there are still significant advantages to DJB's
curves.

> At some point, though, TLS may not want to allow too many choices.

Well, I think we're way past that point as to non-required to
implement algorithms.  The problem there is the cartesian product
explosion of cipher suite IDs.  As for required to implement
algorithms, we're not.

Nico
--

---

From: Bill Frantz <[email-masked]>
Date: Sat, 19 Oct 2013 00:01:55 -0700

>going to rely on the most for authentication.  Which would you rather

One possible solution is to use more than one algorithm. Having 
two signatures, both of which must validate, is robust even if 
one algorithm is compromised. Using two DH key agreements and 
XORing the results protects against one of them be compromised. etc.

This approach has costs. Some applications may be willing to pay 
them and others not. But TLS has a lot of options and users can choose.

Cheers - Bill

-------------------------------------------------------------------------
Bill Frantz        | Re: Hardware Management Modes: | Periwinkle
(408)356-8506      | If there's a mode, there's a   | 16345 
Englewood Ave
www.pwpconsult.com | failure mode. - Jerry Leichter | Los Gatos, 
CA 95032

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 Oct 2013 09:47:10 -0000

Michael StJohns writes:
> that at least a few curves were created in X9 and not by NIST

If you look at

   http://csrc.nist.gov/csrc/fedstandards.html

you'll see NIST stating "These curves have been generated and reviewed
by the government." Offhand I can't think of a NIST document admitting
that the curves were created by NSA, but everyone in the community knows
Jerry Solinas as the NSA point man on this. NSA's earlier contribution
of the same curves to X9 is what led to X9 demanding seeds for curves
(and incorrectly labeling seeded curves as "verifiably random").

---D. J. Bernstein