Subject: [saag] Time now for ECC?

From: Robert Moskowitz <[email-masked]>
Date: Fri, 23 Aug 2013 08:43:54 -0400

The popular technical press has picked up Blackhat talks on the 
approaching end of RSA and DH and thus the need to move to ECC:

http://www.technewsdaily.com/18662-internet-security-cryptopalypse.html

Cryptopalypse ???

Like Metcalf predicting the death of the Internet in the mid 90s?

We (the IETF) have been doing well positioning for ECC.  Or so it seems 
to me.  But is there a sense of urgency as I seem to recall with MD5 and 
SHA1.

Or is it that we have done everything we reasonably can to 'lead the 
horse to the water'?

Curious to get a reading on this from an IETF prospective.

---

From: Yoav Nir <[email-masked]>
Date: Fri, 23 Aug 2013 19:10:31 +0000

On Aug 23, 2013, at 3:43 PM, Robert Moskowitz <[email-masked]> wrote:

> The popular technical press has picked up Blackhat talks on the approaching end of RSA and DH and thus the need to move to ECC:
> 

"Such academic work, the presenters pointed out, quickly rendered useless the MD5 one-way encryption algorithm a few years ago". "Quickly" is a weird word to use there. The academic work exposing flaws in MD5 dates back to 1994, so that RFC 2459 from January 1999 recommended not to use it. Colliding buffers happened in 2004, and a fake certificate was generated in late 2008. Do 14-15 years count as "quickly" on the Internet?

> We (the IETF) have been doing well positioning for ECC.  Or so it seems to me.  But is there a sense of urgency as I seem to recall with MD5 and SHA1.

The urgency is so great that most certificates are still signed with RSA+SHA-1. The certificate for https://www.ietf.org is like that, as is the certificate for Paypal. MD5 does seem to have disappeared.

> Or is it that we have done everything we reasonably can to 'lead the horse to the water'?
> 

We can write draft-ietf-water-horse. We can publish it and give it an RFC number. We have no control as to who decides to implement it.

Yoav

---

From: Nico Williams <[email-masked]>
Date: Fri, 23 Aug 2013 14:49:36 -0500

If we want ECC take-up I think we should standardize Curve25519 ECCDH
and Ed25519 ECC signatures, as their authors make strong (at least
plausible) arguments for patent non-encumberment of those algorithms
and their various implementations.  Plus those algorithms happen to
have some useful advantages over competitors, primarily speed.

I'm curious as to why there's been so little adoption of
Curve25519/Ed25519 here at the IETF (and, for that matter, NIST and
similar agencies of national governments other than the U.S.).  I've
not done much research as to this point, but whenever I've asked I've
received no responses.

Nico
--

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 23 Aug 2013 16:27:08 -0400

> have some useful advantages over competitors, primarily speed.

Where are these documented?

---

From: Nico Williams <[email-masked]>
Date: Fri, 23 Aug 2013 16:14:00 -0500

> Where are these documented?

http://cr.yp.to/ecdh.html
http://ed25519.cr.yp.to/

A number of implementations are floating about.

The ease of estimating patent [non-]encumbrance certainty
(alternatively: low cost of and availability of patent licensing on
reasonable terms) is often the most important factor for many
implementors after "good enough security and performance".  If we want
ECC adoption to pick up steam then we should want to standardize ECC
curves that make this easy; IMO curve25519 does that.  (But IANAL.)

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 23 Aug 2013 15:11:31 -0700

> curves that make this easy; IMO curve25519 does that.  (But IANAL.)

There's RFC 6090, and then there's
http://www.certicom.com/index.php/ip-contributions. Various interoperable
implementations supporting the widely standardized curves do exist
(open-source and otherwise): TLS connections to www.google.com, for
example, normally do use ECDH (with curve NIST P-256) these days. Offering
more specifications to choose from could make a broad migration harder
because it's a detriment to interoperability.

That said, Curve25519 *is* nice (although for new specs you'd probably pick
the Ed25519 curve representation even for ECDH instead). Based on its
merits, this newer work certainly seems worthy of standardization.

(*That* said, the recent claims that the end of RSA and DH is approaching
are horribly overblown -- at increasing key sizes, they are becoming
increasingly inconvenient to use compared to elliptic curves, but that has
been known for a long time.  The recent results for certain discrete
logarithms are a useful reminder that the known cryptanalytic algorithms
can indeed improve, but they don't apply to DH using MODP groups or to RSA.)

Bodo

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 24 Aug 2013 00:13:26 +0200

On Aug 23, 2013, at 21:49, Nico Williams <[email-masked]> wrote:

> If we want ECC take-up I think we should standardize

For CoAP, we just zoomed in rather heavily on secp256r1, a.k.a. NIST P-256.
All the (D)TLS moving parts needed for this are in place*).

Implementers are advised that the techniques documented in RFC 6090 are available for implementation.

The WG feels pretty good about that.

And there certainly would be synergies if the not-so-constrained parts of the Internet used the same curve that light switches and thermostats are going to use.

Grüße, Carsten

*) Well, we are waiting for two more SEC area specs to be finished because we don't always use full certs and our chips like AES-CCM.  But that shouldn't stop anyone else.

---

From: Nico Williams <[email-masked]>
Date: Fri, 23 Aug 2013 17:16:12 -0500

On Fri, Aug 23, 2013 at 5:11 PM, Bodo Moeller <[email-masked]> wrote:
> (open-source and otherwise): TLS connections to www.google.com, for example,
> normally do use ECDH (with curve NIST P-256) these days. Offering more
> specifications to choose from could make a broad migration harder because
> it's a detriment to interoperability.

That's particularly true for TLS for reasons very specific to TLS.  In
general adding more DH groups is not a big deal for any protocol that
supports DH for key exchange.

> merits, this newer work certainly seems worthy of standardization.

Agreed.  I think these are compelling.

> logarithms are a useful reminder that the known cryptanalytic algorithms can
> indeed improve, but they don't apply to DH using MODP groups or to RSA.)

I agree that the warnings of RSA's and DH's impending deaths are
overblown, but we should make sure we have ECC equivalents in place.

Nico
--

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 23 Aug 2013 15:56:50 -0700

> supports DH for key exchange.

I don't agree that the reasons are specific to TLS.  Whereas for MODP DH
adding more groups is not a big deal, in the case of ECC you're essentially
looking at independent implementations for different groups -- if you
support NIST P-256, you'll have to add very different code to also support
Ed25519.  [You can create more general code for families of curves, e.g.
NIST P-###, but it will cost you dearly in performance.]  So sticking to a
small set of curves makes it more likely that different implementations
will actually be able to interoperate with each other [efficiently] without
falling back to good ol' MODP DH or RSA.

The best strategy to prevent more widespread deployment of elliptic-curve
cryptography is to create standards that cover every curve that's out there
:-)

> overblown, but we should make sure we have ECC equivalents in place.

Certainly!  For various protocols, ECC with NIST curves is already getting
traction.  {Curve,Ed}25519 allows for performance improvements significant
enough that, *despite* the general interoperability concerns, it would be a
shame not to support this also; and hopefully this will eventually become a
government-vetted curve too.

Bodo

---

From: Nico Williams <[email-masked]>
Date: Fri, 23 Aug 2013 18:08:32 -0500

On Fri, Aug 23, 2013 at 5:56 PM, Bodo Moeller <[email-masked]> wrote:
> small set of curves makes it more likely that different implementations will
> actually be able to interoperate with each other [efficiently] without

The point is that for protocols other than TLS (which don't have
"handshake message too large, proxy went catatonic" problems adding DH
groups and curves is not difficult.  Yes, for ECC DH adding curves
requires deploying code, which is not correspondingly true of modular
DH, but that's not a real problem.

Now, more code is more code and generally that's not a good thing, but
sometimes the benefits are compelling, and I believe that in this case
they are.

> cryptography is to create standards that cover every curve that's out there

There have to be REQUIRED to implement curves, no doubt, and there
must be very few of those (maybe two).  Beyond that, and ignoring
TLS-specific issues (see above), having 100 possible curves or just 3
makes little difference, at least to me -- it's easy to ignore all the
non-REQUIRED ones, after all.

> government-vetted curve too.

I can agree with this.  I would very much like for NIST to review
{Curve,Ed}25519 and -assuming it stands up to cryptanalysts-
standardize it.  I would only add that the IETF does not have to wait
for NIST, and that I'd like to see more analysis of {Curve,Ed}25519.

Nico
--

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 23 Aug 2013 16:46:04 -0700

> must be very few of those (maybe two).
>

Right, if you *require* certain curves and implementations actually obey
the requirement, then adding further optional curves is not as much of an
issue -- at least in theory, because as long as it remains possible to
simply stick to RSA or to MODP DH, implementors might decide to skip the
"required" part of ECC support.

For what it's worth, I think if you are going to require any single curve,
the most suitable candidate right now would be NIST P-256 (taking into
account aspects such as *current* deployment with IETF protocols and
existing non-IETF standards). It's sort of ancient, but this also means
it's been around for analysis for a long while.  (As appealing as Ed25519
is, requiring a second curve seems counterproductive. It would be perfect
as an optional curve.)

Bodo

---

From: Nico Williams <[email-masked]>
Date: Fri, 23 Aug 2013 20:20:30 -0500

I'm not proposing {Curve, Ed}25519 as a required one.  I don't object
to -and do recommend- having two required to implement algorithms for
certain types of operations, first to exercise algorithm agility, and
second because that has saved our bacon on occasion (I'm thinking of
the SSHv2 IV chaining issues from years ago).

Nico
--

---

From: Stephen Kent <[email-masked]>
Date: Sat, 24 Aug 2013 08:38:49 -0400

Another issue to consider is hardware support. While SW support may not 
be terribly
hard to generalize, HW support may be more curve (family)-specific. 
Folks operating
servers, who make use of hardware acceleration, would be adversely 
affected if we
encourage use of curve families that are not supported.  I suggest we 
try to get
input from folks to gauge the availability of HW support for ECDH.

Steve

---

From: Michael Richardson <[email-masked]>
Date: Sun, 25 Aug 2013 21:31:30 -0400

> overblown, but we should make sure we have ECC equivalents in place.

I wonder if widespread and ubiquitous use of RSA did not occur until
after Sept. 2000, when the patent expired, and everyone was "sure"

-- 
Michael Richardson
-at the cottage-

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 26 Aug 2013 14:52:56 -0700

On 08/23/2013 04:46 PM, Bodo Moeller wrote:
> the requirement, then adding further optional curves is not as much of
> an issue -- at least in theory, because as long as it remains possible
> to simply stick to RSA or to MODP DH, implementors might decide to skip
> the "required" part of ECC support.
>
> For what it's worth, I think if you are going to require any single
> curve, the most suitable candidate right now would be NIST P-256 (taking
> into account aspects such as *current* deployment with IETF protocols
> and existing non-IETF standards). It's sort of ancient, but this also
> means it's been around for analysis for a long while.  (As appealing as
> Ed25519 is, requiring a second curve seems counterproductive. It would
> be perfect as an optional curve.)

I will second the benefit of the limited choice for the benefit of 
adoption of ECC. P-256 seems to be the best choice to bootstrap the 
ecosystem into the ECC world. The availability of too many "best" 
choices could be a negative thing, sending a confusing message for what 
to implement and focus on first.

One issue that was not mentioned here is the needs of off-line 
protocols, where, unlike as in TLS, you don't know anything about the 
recipients. Typically, these are signing protocols where the potential 
recipients are the whole World.

For example, consider SMIME application. Typically the security is 
bootstrapped by signing a message, after which the recipient will learn 
some facts about sender's capabilities through SMIMECapabilities. But 
this doesn't answer the question of what to do in the first signed 
message (sent to a large group).

Or, which ECDSA a CA should use to sign X.509 certificates? Which 
OpenPGP personal key should I generate?

Unlike the choice between RSA 2048 and 2096, ECC P-256 and P-384 are 
quite different and are probably viewed as separate algorithms by most 
implementations (knowing that a peer supports P-256 doesn't give you 
certainty that P-384 is supported). If Edwards curves are added, this is 
yet another set of essentially different algorithms. They are fine as 
optional choices, but given the SuiteB, the clear lowest common 
denominator is P-256.