Subject: Re: [TLS] Straw poll on draft-ietf-tls-ecc-*

From: Hovav Shacham <[email-masked]>
Date: 05 Oct 2004 12:12:32 -0700

Bodo Moeller <[email-masked]> writes:

> I vote for option A ("Advance draft-ietf-tls-ecc-* to Proposed
> Standard").

I vote B, informational.

> we know that attacks against RSA and DH have subexponential
> complexity, while attacking ECC requires exponential time (around
> 2^k steps for ECC over (2k)-bit fields).

Except when it doesn't; consider the talks by Pierrick Gaudry and
Claus Diem at ECC a few weeks ago.

> Increasing keylengths to improve security has a more noticeable
> effect on performance for RSA and DH than for ECC (with its
> exponential complexity of known attacks).

Yes; but, barring significant advances in factoring or discrete log,
the ECC ciphersuites provide only moderate throughput improvement, at
the cost of protocol complexity.  This seems to me to be an unwise bet
against Moore's Law.

-- 
Hovav Shacham                                  [email-masked]
"Rightly looked at there is no laughable thing under the sun."

_______________________________________________
TLS mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tls

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 05 Oct 2004 13:11:24 -0700

> Claus Diem at ECC a few weeks ago.

Yes, obviously.  This was an oversimplification (sort of like "factoring
integers is hard").  More precisely, as long as you don't try to cut
corners by using composite fields or other special curves, then if you
choose elliptic curves with the usual cryptographic properties described
in the standards (notably, existence of a large prime-order subgroup),
you can very reasonably hope to achieve attack resistance as claimed
above.

> the cost of protocol complexity.

This depends on the hardware (and use of the protocol) that you are
considering.  For example, with unauthenticated clients, there's
ephemeral DH with RSA signatures (which is in pretty wide use for
TLS-protected SMTP) vs. ephemeral ECDH with RSA signatures.  For weak
hardware, this can make a great deal of a difference.  If you see TLS
as a general security protocol for data streams, then this matters.

---

From: Tim Dierks <[email-masked]>
Date: Tue, 5 Oct 2004 17:25:19 -0400

On Tue, 28 Sep 2004 15:55:39 -0700, Eric Rescorla <[email-masked]> wrote:
> This is a Straw Poll in the fate of draft-ietf-tls-ecc-*.
> 
> A. Advance draft-ietf-tls-ecc-* to Proposed Standard.
> B. Advance draft-ietf-tls-ecc-* as Informational and remove
>    the extensions.
> C. Advance draft-ietf-tls-ecc-* as Informational with the
>    extensions. Amend RFC 3456 to allow extensions without
>    a Standards Action.

I vote option B. I don't think curve negotiation is of substantial
practical value.

 - Tim

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 05 Oct 2004 15:22:33 -0700

Tim Dierks wrote:

>                  I don't think curve negotiation is of substantial
> practical value.

The ECC TLS draft uses two extensions: "supported elliptic curves",
and "supported point formats".  The latter arguably would be easy to
get rid of if necessary (make the uncompressed point format not
only the default and a "MUST support", but also a "MUST use").
But "supported elliptic curves" serves an important practical purpose
beyond merely providing an optimization like "supported point formats"
does: Without curve negotiation, clients and servers would have to
support both prime field curves and binary curves to be able to use ECC
ciphersuites without risking non-interoperability.  The way the
handshake works, the server has to decide about the type of curve to use
for ECDH when sending the ServerKeyExchange message; the client has
to follow this lead (i.e. use the same group) in the ClientKeyExchange.

The concern is mostly about small clients with limited capabilities:
With the "supported elliptic curves" extension, clients that support,
say, only prime fields or even just a specific one of the well-known
curves will be able to finish the handshake for ECC ciphersuites
without problems (under the usually reasonable assumption that the
servers are less limited).  Without this extension, such clients
could only hope that the server will pick a curve that works for them.

A general solution to this and similar problems might be to define
ciphersuite-specific extensions: By RFC 3546, we have

       struct {
           ExtensionType extension_type;
           opaque extension_data<0..2^16-1>;
       } Extension;

       enum {
           server_name(0), max_fragment_length(1),
           client_certificate_url(2), trusted_ca_keys(3),
           truncated_hmac(4), status_request(5), (65535)
       } ExtensionType;

What about using

       struct {
           ExtensionType extension_type;
           select (MSB(extension_type)) {
               case 0:
                   opaque extension_data<0..2^16-1>;
               case 1:
                   CipherSuite cipher_suites<2..2^16-1>;
                   opaque extension_data<0..2^16-1>;
       } Extension;

instead where all extension types with the MSB set are valid only for
the ciphersuites listed for them and thus don't require a single
global specification?

---

From: Tim Dierks <[email-masked]>
Date: Tue, 5 Oct 2004 17:12:10 -0700

> >                  I don't think curve negotiation is of substantial

I based this entirely on my experience with ECC TLS, which is
substantial (I'm a former CTO of Certicom). In my experience, 100% of
the use of ECC TLS has been in closed-interoperability environments:
everyone participating in the network already knows with whom they're
going to need to speak, and the algorithm space is reduced to a
sub-specification of the TLS spec. In reality, this generally means
everyone uses a single curve, to say nothing of field or point format.
I don't see any reason this is going to change any time soon, so I
don't think it's worth standardizing the extension portion of the
draft.

 - Tim

---

From: "Anton Stiglic" <[email-masked]>
Date: Tue, 5 Oct 2004 20:50:13 -0400

For those who have not seen it yet:

http://csrc.nist.gov/publications/drafts.html#sp800-52

--Anton

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 05 Oct 2004 17:54:22 -0700

> I don't see any reason this is going to change any time soon, [...]

The old draft-ietf-tls-ecc-01.txt specification, which you co-authored
while you were with Certicom, only had ciphersuites that required ECDH
in the *certificates* (apart from anonymous ECDH, which does not have
any ceritificates in the first place).  This naturally only lends itself
to closed environments as you describe them.

The ECC TLS drafts now, since draft-ietf-tls-ecc-02.txt (August 2002),
have a ECDHE_RSA key exchange algorithm, which lets ECC TLS work outside
such closed worlds: Everyone can continue to use their RSA certificates
(which makes signature verification faster anyway); ECDH is used just
in the key exchange messages.  Obviously there are still ciphersuites
requiring ECC-enabled certificates, which would only be used in
closed-interoperability environments at first (and may catch on later).
But there are now ciphersuites that ensure unhindered interoperability
without requiring closed networks -- all that is needed is curve
negotiation.