Re: [TLS] Safe ECC usage

[Dan Brown <[e-mail]>]

Dear Professor Bernstein,

Thanks for your helpful response.

I too feel Curve25519 is safe, and in many aspects more secure than alternatives. I just want quantified claims of advantages, with formal arguments, and balanced treatment of any aspects in which it may not be more secure. Your finding this curve is ingenius and commendable.

After I sent my email, I noticed I wrote about a hypothetical "strong weakness". I should have ‎written "severe weakness". Maybe for this, or otherwise, I was unclear: to clarify myself P256 and Curve25519 are not at all in the "same situation". If we consider adversaries choosing curves, then Curve25519 fares way better than P256 (unless you are hypergenius).

Also, I think these hypotheses merit attention, but should be treated numerically, just like any other crypto.



‎Anyway... I will paraphrase your supposition below:

Density q = 2^(-30) class of weak curves.

Where weak mean logs solvable at cost 2^64.

Probability 2^(-b) that that an adversary found the weakness. Variable b is unknown, which we must infer. We could generalize it, as in b(30,64).

You responded "no" to my position that we must mildly revise our claims for any EC curve.

So, I conclude that the recent news does not suggest to you revising your estimate of b. Also, you estimate b is high (but I don't know how high), because you say the risk is low.
Inferring b is difficult, because of the lack of evidence and the many factors.

My interpretation of most ECC claims is that we have inferred b to so large‎ that the probability 2^-(64+b) yielded nothing more effective than standard generic group tradeoffs between cost and success rate. The basis for this inference was the lack of published progress on ECDLP, for all but a negligible density of curves. Maybe this was unjustified, but I feel that was the claim. As a result this risk was absorbed by the risks due to published algorithms.

Sorry for saying "threat to any EC curve". I hope that I've clarified what I meant by "mildly reduce‎" now.




I don't know if you claim(ed) something different ...‎



Sorry, by "special", I just meant not pseudorandom. Yes, P256 has a special field. I think brainpool curves don't have special fields, which may have some merit.  You are right that I have not given an argument why special might be weak. Your counter arguments is good, too, for the case of Curve25519.

What I meant... 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.  Of course, it's a logical leap to jump from small d to small curve coefficients, but if we are going to be prudent, then why not avoid small coefficients too?  More precisely, let's stick to verifiably random curves, as a matter of prudence.







Sent from my BlackBerry 10 smartphone on the Rogers network.
From: D. J. Bernstein
Sent: Saturday, September 28, 2013 6:37 PM
To: [e-mail]
Subject: Re: [TLS] Safe ECC usage


Dan Brown writes:
> Five NIST curves are Koblitz curves, which do not have seeds at all.

Agreed. There's nothing unexplained in, e.g., the K-233 curve. However,
as I wrote in the Curve25519 paper in 2005, prime fields have "the
virtue of minimizing the number of security concerns for elliptic-curve
cryptography; see, e.g., [1998 Frey] and [2003 Diem]."

Maybe Frey's Weil-descent attack strategy has reached its limits, but
maybe not; see, e.g., http://eprint.iacr.org/2012/146. The performance
benefits of Koblitz curves aren't big enough to justify having to worry
about further developments in this area. It's best to use prime fields,
eliminating this entire class of attacks.

> I must have forgotten that aspect of the Brainpool standard. If
> possible, please remind me of the issue, if only by link to the relevant
> document (and section thereof).

This is the second bullet item in the list of "major issues" stated at
the beginning of "ECC Brainpool Standard Curves and Curve Generation v.
1.0".

> a consistent treatment of ECC must mildly reduce, or at least revise,
> the claimed security of any EC curve if the treatment also posits that NIST
> curves have an undisclosed strong weakness.

No.

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. This wouldn't be
out of line with the spectrum of known ECC attacks, such as

* the Pohlig--Hellman attack breaking most curve orders (this is why
P1363 requires a large prime to divide the order),
* twist attacks breaking most of the remaining curve orders in many
protocols,
* Weil descent breaking many curves for some field sizes,
* the MOV attack on curves of order p-1 and p+1 and so on, and
* an attack on curves of order p.

Suppose that NSA can recognize immediately from the group order whether
the attack will be successful---again a reasonable assumption. NSA could
then

* have generated many billions of seeds until finding a
P1363-compliant curve vulnerable to this attack (a feasible
computation for NSA in the 1990s),

* have standardized that curve as NIST P-256 (we already know that
NIST took its curves from NSA), falsely claiming the curve to be
"verifiably random", and

* be applying the cost-2^64 attack to NIST P-256 users today.

You claim that such an attack would be a threat to "any EC curve". But
this claim is obviously not correct for curves that really are randomly
generated (and you have zero justification for making the same claim for
any particular curve). The correct comparison, under exactly the same
hypotheses, is simple:

* Honest curve: NSA has _a one-in-a-billion chance_ that we obtained
a weak curve, in which case NSA finds our keys with cost 2^64.

* NIST curve: NSA is _guaranteed_ that we're using a weak curve, so
NSA finds our keys with cost 2^64.

These are obviously not the same situation. The attack costs are the
same, but the success probabilities are on totally different scales.

I don't think there's a high risk of being in this situation---there
have been many years of intensive cryptanalysis of ECC, and for prime
fields the security story seems to have converged. But there's also no
reason for ECC users to expose themselves to risks that are so trivial
to avoid. There are also much larger risks that definitely bite people
(see http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf)
and that one can avoid by moving away from the NIST curves.

> I have argued on this list that
> Curve25519 is special in its use of small coefficients.

Well, yes, you've declared that y^2=x^3+486662x^2+x mod 2^255-19 is
"special", but you haven't actually given an argument for this---for
example, an attack strategy in which the size of the 486662 plays a
role. Index calculus sees sizes, but the whole point of ECC is to stop
index calculus. You could equally well declare that NIST P-256 is
"special" since its prime can be written as a low-degree polynomial in a
power of 2 with coefficients {-1,0,1}, or declare that brainpoolP256r1
is "special" since it contains the scary string BCCDC.

> Does Curve25519 ignore Cheon-type "attacks" (which are rather weak)?

Key derivation stops such attacks, and is easy to do securely, as
discussed in the Curve25519 paper. As far as I know, all Curve25519
deployment is using appropriate key derivation.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago
_______________________________________________
TLS mailing list
[e-mail]
https://www.ietf.org/mailman/listinfo/tls


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