Subject: Re: [TLS] draft-sheffer-tls-bcp: DH recommendations

From: Peter Gutmann <[email-masked]>
Date: Sat, 21 Sep 2013 08:42:09 +0000

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.

Peter.

---

From: Yaron Sheffer <[email-masked]>
Date: Sun, 22 Sep 2013 01:02:23 +0300

Hi Peter,

Thanks for the clarification. Two questions:

- Does any of this brittleness still apply when talking about ECDH (as 
opposed to ECDSA), with fixed parameters?

- Further supporting the brittleness argument... We recently specified 
recipient tests in IKEv2, that apply (and are actually 
security-critical) when either side reuses its DH private key [1]. The 
recipient needs to test that the received point is actually on the 
relevant curve. Are these mandated for ECDHE in TLS? I would have 
expected to see this requirement in [2] (reuse of DH keys is allowed in 
this RFC), but it ain't.

Thanks,
	Yaron

[1] http://tools.ietf.org/html/rfc6989#section-2.3
[2] http://tools.ietf.org/html/rfc4492#section-5.4

On 09/21/2013 11:42 AM, Peter Gutmann wrote:
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: "D. J. Bernstein" <[email-masked]>
Date: 26 Sep 2013 15:27:57 -0000

Modern elliptic-curve cryptography solidly takes care of all of the
"brittleness" mentioned in this thread, and is much easier than RSA to
implement securely. Compare https://twitter.com/tweetnacl to the amount
of code required to implement similar functionality in OpenSSL.

Peter Gutmann writes:
> potentially NSA-influenced values like P256

There is indisputably an unexplained seed c49d3608 86e70493 6a6678e1
139d26b7 819f7e90 for the NIST P-256 curve mod 2^256-2^224+2^192+2^96-1,
and similarly for the other NIST curves. This was identified by the 2005
Brainpool standard as a major issue for the NIST curves; it has also
been highlighted recently by Bruce Schneier.

Fortunately, one can design high-security elliptic curves that don't
have any unexplained constants. That's what I did with Curve25519.
Curve25519 is the curve y^2=x^3+486662x^2+x mod 2^255-19; every number
here is completely explained in the Curve25519 paper.

> even without NSA skullduggery make a nice single target for attack.

There have already been several detailed studies of the cost of finding
multiple discrete logs on the same curve (authors: Escott, Sager,
Selkirk, Tsapakidis, Kuhn, Struik, Hitchcock, Montague, Carter, Dawson,
Lee, Cheon, Hong, Bernstein, Lange). Basically, if finding one ECC key
costs 2^128, then finding 1000000 keys costs 1000*2^128, and the first
key found will still cost 2^128. For comparison, finding 1000000 AES
keys costs the same 2^128 as finding a single key, and the first AES key
will be found with cost only 2^128/1000000.

Yaron Sheffer writes:
> The recipient needs to test that the received point is actually on
> the relevant curve.

This is certainly an issue for the NIST curves. Fortunately, this test
is completely unnecessary for x-coordinate ECC using twist-secure curves
such as Curve25519. I introduced this approach at ECC 2001, using the
smaller curve y^2=x^3+7530x^2+x mod 2^226-5 as an illustration.

Peter Gutmann writes:
> 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).

Ed25519 has three levels of defense against this type of problem.

First, k is chosen as a random 512-bit string, many bits larger than the
group order l (around 2^252). This is overkill (compare to the 64 bits
in Algorithm 2 in Section 4.1.1 of BSI Technical Guideline TR-03111) but
also an inexpensive and comprehensive defense.

Second, the group order l is very close to a power of 2, specifically
within 2^125 of 2^252, so the bias would be unnoticeable even if k were
as small as 256 bits.

Third, k is actually produced in a deterministic way as a secret hash,
so the k-generation mechanism is fully testable---there's no need to
worry about the implementor accidentally choosing a biased RNG.

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

---

From: Dan Brown <[email-masked]>
Date: Thu, 26 Sep 2013 16:46:39 +0000

> D. J. Bernstein writes
> 139d26b7 819f7e90 for the NIST P-256 curve mod 2^256-2^224+2^192+2^96-
> 1, and similarly for the other NIST curves. This was identified by the

[DB] Five NIST curves are Koblitz curves, which do not have seeds at all.
They also use small curve coefficients, which is similar to Curve25519.

> 2005 Brainpool standard as a major issue for the NIST curves; it has
> also been highlighted recently by Bruce Schneier.

[DB] 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).  In particular, I already tried to summarize
on this list (in response to a message from Douglas Stebila) an argument
that 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.  I may have missed an something
important.  To further elaborate my argument: it is possible to formulate
one's suspicion in such that way that one needs only to boost one's curve
size accordingly.  For example, if one suspects an undisclosed class of
curves whose density is say n^(1/8) where n is the curve size, then, to
resist falling into this class, one can choose n large enough, so that the
risk is small enough.  Such risk should be somehow calibrated with claimed
security levels: e.g. if we want the adversary to incur computational cost
of 2^128 at success rate near 1, we may be satisfied with success rate
2^(-48) at cost near 1.  With these settings might choose a 384-bit curve
instead of 256-bit curve.  This doesn't protect against constant density
classes, but is at least worth something.  Of course, I made up the n^(1/8).
One might look at the densities of the current weak classes: one has n^(1/2)
and the other (MOV) has, hmm, I have to study it some more, I just remember
a result that says it's low.  

If I recall correctly, the Brainpool documents recommended against, or at
least avoided, special classes of curves.  I have argued on this list that
Curve25519 is special in its use of small coefficients.  What's your thought
on the risk of this?  So far, the main two weak classes of prime-field
curves are negligible density.  If the future reveals such classes, then it
seems that attempting to select curves verifiably at random is a more solid
way to avoid falling into such a class than choosing a special curve.  If I
recall correctly, the MNT curves were special curves chosen for desirable
characteristics, that later fell into one of these classes.  

> have any unexplained constants. That's what I did with Curve25519.

[DB] Wasn't this well-known already for Koblitz curves, or are they broken?
I may have lost track, since there has been recent improvements in (EC)DLP
over extension fields.  I had thought that maybe Koblitz curves remained
unaffected.  (Also, some standards, e.g. ANSI X9.63 have long prohibited
such extension-field curves, which might be a good case of anticipation, or
perhaps just promotion of interoperability).

> here is completely explained in the Curve25519 paper.

[DB] Does Curve25519 ignore Cheon-type "attacks" (which are rather weak)?
If so, that's probably fine for TLS, because the attacks do not affect TLS,
unless the TLS-PRF is much weaker than we think, and DH private keys are
very heavily re-used.  So, I mainly ask for completeness.  Also, the NIST
curves and the Brainpool curves do not incorporate any countermeasures to
these attacks (the Brainpool deliberately so).

> keys costs the same 2^128 as finding a single key, and the first AES
> key will be found with cost only 2^128/1000000.
> 

[DB] Good point. 

I had interpreted the comment differently to refer to attacking the curve
itsel (which would support using a random curve for each TLS handshake, for
example).  A typical response to the comment (under my interpretation) is
that AES and SHA2 are also nice single targets, and well maybe, that's a
good thing, with incentives, publicity, and so on.
---------------------------------------------------------------------
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: 28 Sep 2013 22:36:48 -0000

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

---

From: Kyle Hamilton <[email-masked]>
Date: Sun, 29 Sep 2013 00:33:06 -0700

Dr Bernstein,

That's all well and good, but perhaps should you try to figure out how your
functions can in fact be used in such standards as TLS without having to
resort to pulling hens' teeth?

Or perhaps apply your (admittedly much better than mine) intellect to
figure out how to create a single public key from a single private key
which can be used for both signing and key derivation, thus permitting
consolidation of both into a single X.509 Certificate structure?  The lack
of this is in fact a major impediment to using self-signed certificates as
containers for curve25519 public keys.

Granted, I've been severely out of touch for quite a while, and it's
possible that (e.g.) Ed25519 permits the use of the same public key in this
manner (even though Ed25519 has a peculiar recordkeeping requirement which
makes it less than ideal).  If it does, please accept my humble apology.
If it does not, however, I'd like to ask you to design a function which can
be used for both signature and derivation from the same public key, so as
to create a clear path forward for at least one (if not more)
externally-developed elliptical function for ease of integration into the
preexisting TLS (and perhaps more importantly PKI) infrastructure.

BULLRUN's first major visible success was in inducing everyone to think
about "how do you know it's who you think you're talking to?", completely
ignoring SSLv1's opportunistic encryption.  Netscape carried this further
by simply refusing to speak with SSL sites that didn't authenticate
themselves.  I don't know if there is any webserver out there that will do
TLS without an identity certificate, and even if there is I doubt there is
a client that will communicate in those conditions.  So, we need at the
very least a self-signed certificate to carry the public key used to derive
the shared key.

(Also, while I've hopefully got your attention, have you any plan to create
an x64 ABI for Curve25519?  I'm currently having to use it via a COM
wrapper I hacked up in C#, 64-bit processes calling via COM to a 32-bit
process which exports only one function that COM doesn't mandate:
curve25519(). This is insecure to COM-debug capable processes at the very
least, as it requires that the caller provide the caller's private key over
a public data bus.)

I have the utmost respect for your knowledge and intellect, but without
having a plan to fit your function into a common framework, there is simply
no way to use the function you keep trying to promote.

-Kyle H

(Note: I would -love- to find out that I'm wrong, on any or all of this.)

---

From: Johannes Merkle <[email-masked]>
Date: Mon, 30 Sep 2013 13:59:49 +0200

> the beginning of "ECC Brainpool Standard Curves and Curve Generation v.

This aspect is also addressed in RFC 5639 as first bullet point in Section 1 and as security requirement 5 in section 2.1.

Johannes

---

From: Adam Langley <[email-masked]>
Date: Mon, 30 Sep 2013 11:03:20 -0400

On Sun, Sep 29, 2013 at 3:33 AM, Kyle Hamilton <[email-masked]> wrote:
> Or perhaps apply your (admittedly much better than mine) intellect to figure
> out how to create a single public key from a single private key which can be
> used for both signing and key derivation, thus permitting consolidation of
> both into a single X.509 Certificate structure?  The lack of this is in fact
> a major impediment to using self-signed certificates as containers for
> curve25519 public keys.

Current ECDSA deployments involve an ECDSA key in an X.509 certificate
and ephemeral, ECDHE keys being generated by the server as needed.
These ephemeral keys are signed by the ECDSA key.

A similar design would have an Ed25519 key in the X.509 certificate
and curve25519 used for ECDHE. I don't believe there's anything needed
to get that working save for switching out the algorithms.

(It is the case that some ECDSA certificates have both the signature
and key derivation bits set in the key usage. This means that OpenSSL,
at least, will allow it to be used for both ECDSA and fixed-ECDH. I'm
not aware of anyone who actually wants that however. As far as I've
seen, it's just the result of copying an RSA certificate template and
forgetting to update the KeyUsage.)

> makes it less than ideal).

Ed25519 and curve25519 are the same curve so it is technically
possible to use an Ed25519 public key, with a bit of thought, as a
curve25519 key. However, I wouldn't recommend it. TLS certainly
doesn't need that.

> an x64 ABI for Curve25519?  I'm currently having to use it via a COM wrapper
> I hacked up in C#, 64-bit processes calling via COM to a 32-bit process
> which exports only one function that COM doesn't mandate: curve25519(). This
> is insecure to COM-debug capable processes at the very least, as it requires
> that the caller provide the caller's private key over a public data bus.)

There are several implementations of curve25519 in SUPERCOP, including
amd64, asm versions (amd64-51); 64-bit, C code (donna_c64) and
portable C code (ref10). It would be pretty simple to convert the
ref10 code to C# if you wished.

Cheers

AGL

---

From: Santosh Chokhani <[email-masked]>
Date: Mon, 30 Sep 2013 19:27:31 +0000

Adam,

Simply copying RSA template and thus the key usage bits should not yield the behavior you mention.  RSA certificates should set the key encipherment bit.  EC type certificates should not set that bit; the appropriate bit is key agreement.

So, either someone or software is doing that mental translation.

Products should not use a certificate for ECDH or DH key agreement if the key encipherment bit is set.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Adam Langley
Sent: Monday, September 30, 2013 11:03 AM
To: Kyle Hamilton
Cc: [email-masked]
Subject: Re: [TLS] Safe ECC usage

On Sun, Sep 29, 2013 at 3:33 AM, Kyle Hamilton <[email-masked]> wrote:
> consolidation of both into a single X.509 Certificate structure?  The 
> lack of this is in fact a major impediment to using self-signed 
> certificates as containers for
> curve25519 public keys.

Current ECDSA deployments involve an ECDSA key in an X.509 certificate and ephemeral, ECDHE keys being generated by the server as needed.
These ephemeral keys are signed by the ECDSA key.

A similar design would have an Ed25519 key in the X.509 certificate and curve25519 used for ECDHE. I don't believe there's anything needed to get that working save for switching out the algorithms.

(It is the case that some ECDSA certificates have both the signature and key derivation bits set in the key usage. This means that OpenSSL, at least, will allow it to be used for both ECDSA and fixed-ECDH. I'm not aware of anyone who actually wants that however. As far as I've seen, it's just the result of copying an RSA certificate template and forgetting to update the KeyUsage.)

> possible that (e.g.) Ed25519 permits the use of the same public key in 
> this manner (even though Ed25519 has a peculiar recordkeeping 
> requirement which makes it less than ideal).

Ed25519 and curve25519 are the same curve so it is technically possible to use an Ed25519 public key, with a bit of thought, as a
curve25519 key. However, I wouldn't recommend it. TLS certainly doesn't need that.

> (Also, while I've hopefully got your attention, have you any plan to 
> create an x64 ABI for Curve25519?  I'm currently having to use it via 
> a COM wrapper I hacked up in C#, 64-bit processes calling via COM to a 
> 32-bit process which exports only one function that COM doesn't 
> mandate: curve25519(). This is insecure to COM-debug capable processes 
> at the very least, as it requires that the caller provide the caller's 
> private key over a public data bus.)

There are several implementations of curve25519 in SUPERCOP, including amd64, asm versions (amd64-51); 64-bit, C code (donna_c64) and portable C code (ref10). It would be pretty simple to convert the
ref10 code to C# if you wished.

Cheers

AGL

---

From: [email-masked] (Martin Rex)
Date: Tue, 1 Oct 2013 00:50:26 +0200 (CEST)

> containers for curve25519 public keys.

I currently do not see any benefit from using EC for digital signatures,
but instead a huge amount of code, complexity and IPR issues (did you
look at the CertiCom idea how to charge?).

What I believe would be more attractive is an alternative to rfc4492
for ECDHE_RSA based on curve25519 (and _just_ curve25519), i.e.
a small number of new cipher suites and an additional ClientKeyExchange
and ServerKeyExchange variant specifically tailord for curve25519, so
that there are real benefits to a full-blown and generic rfc4492 TLS EC
crypto.

-Martin

---

From: Kyle Hamilton <[email-masked]>
Date: Mon, 30 Sep 2013 20:36:54 -0700

Martin,

When is the last time a purely mathematical algorithm was in fact
patentable and defensible?

Not to mention, Ed25519 is in fact a nonpatented EC signature capability,
but it is more a one-time authenticator than anything resembling a flat
signature.

Please stop being a shill for BULLRUN.

-Kyle H

On Mon, Sep 30, 2013 at 3:50 PM, Martin Rex <[email-masked]> wrote:

> lack

---

From: Yoav Nir <[email-masked]>
Date: Tue, 1 Oct 2013 05:14:09 +0000

> I currently do not see any benefit from using EC for digital signatures,

Other than certificate size and the speed of making those calculations?  Really, try "openssl speed rsa2048 ecdsap256" on any Linux or Mac machine.

> look at the CertiCom idea how to charge?).

Yes, I have: "If the standard is adopted, Patent Holder will not assert any claims of any patents owned or controlled by the Patent Holder against any party for making, using, selling importing or offering for sale a product that implements the Standard…" (weird capitalization theirs, not mine)

Also, there's RFC 6090 on how you can do all the ECC operations with 1994 technology.

Also, public CAs, a notoriously careful bunch, have started issuing ECC certs, all browsers have ECC ciphersuites as does OpenSSL and others. Clearly the market is not afraid of the IPR issue.

> for ECDHE_RSA based on curve25519 (and _just_ curve25519),

IANAL and neither are you. What makes you think that the IPR issues apply to P-256 more than they do to Curve25519?

> i.e.

ECDHE_RSA is slower than plain RSA. ECDHE_ECDSA is faster. Once you've dipped your toe in the ECC pool, there's no reason not to have it in the signature as well.

Yoav