Subject: Re: Comments on ECC draft

From: Len Sassaman <[email-masked]>
Date: Mon, 23 Sep 2002 15:01:12 -0700 (PDT)

I'd like to bring this up again before the next revision of the draft. How
close are we to consensus on the ECC semantics?

OpenSSL now has ECC in it, and there is an ECC in TLS draft being proposed
in the IETF. It is worth nailing this down, I think.

On Wed, 5 Sep 2001 [email-masked] wrote:

>
> We have been looking at the ECC issue and have a few comments on the
> proposed draft by Dominikus Scherkl and Christoph Fausak.
>
> Broadly speaking it looks very good.  Obviously a lot of care and effort
> has gone into the work.  It seems to be timely to address the issue of
> elliptic curve support as there is interest in this technology from a
> number of areas.
>
> Our main concern is the number of variations proposed.  Experience with
> OpenPGP and other standards suggests that having a multitude of options
> does not lead to interoperability and security.  It is better to focus
> on a small number of options that will be used and tested.
>
> In looking at the various forms of elliptic curves, we can separate
> consideration of the coordinate field (the field from which the X and
> Y coordinates are taken) from the curve group.  Rather than describing
> each curve choice as a particular coordinate field and elliptic curve,
> we would rather specify a limited set of coordinate fields, and then to
> define curves using that set.
>
> Especially when implementing the binary (characteristic 2) fields,
> to get good performance it is necessary to optimize the code for the
> particular field size and basis.  Knowing the polynomial you can hard-code
> the necessary shifts, xors, and array offsets and do the arithmetic
> very fast.  Code which treats these values as variables will be much
> less efficient. As efficiency is much of the motivation for going to EC
> technology, we should try to preserve it.
>
> Therefore we recommend choosing a limited set of field sizes, and for each
> one choosing a single coordinate basis.  This will let all implementers
> optimize their code for the fields that are actually in use.
>
> As candidates for the specific fields to use, we recommend
> the selections from NIST [fips186-2], used as ECC groups in IKE
> [draft-ietf-ipsec-ike-ecc-groups-03]. These fields are being deployed
> and are in use in some environments. They provide for efficient
> implementations.
>
> ECC groups in IKE specifies two curves for each choice of coordinate
> field, a random curve which is expected to provide maximal security due
> to absence of any exploitable structure, and a Koblitz curve which has
> structure that allows for optimization and high speed.  We feel this is a
> good model to follow. It provides some flexibility while still providing a
> limited number of choices which will promote interoperability.  No special
> coding is needed to support the Koblitz curve for interoperation purposes;
> effort is only required if you want to get the potential speed advantages.
>
> The last point we would like to make is about the field representation
> format (section 4.4 in the draft), where again we would propose to reduce
> the number of options in order to improve interoperability. 16 options
> is too many.
>
> We suggest the initial draft use only prime fields, descriptor 3,
> and trinomial/pentanomial binary fields, descriptors 11 and 12. These
> three are enough to cover all the NIST curves.  They seem to provide
> the advantages which we seek from ECC without multiplying the options
> excessively.
>
> If the group does want to pursue additional field types, we would like
> to see some rationale for the use of prime extension field types 4-9. Our
> concern with the special primes 1-2 is that this area seems to be covered
> by patents.  And descriptors 14-16 are for normal bases, where we see
> two problems.  First, they cannot be efficiently implemented in software;
> and second, we do not think it is possible to convert from a normal basis
> into a polynomial basis representation without additional information
> regarding the specific normal basis chosen.  Hence using normal bases
> as an interchange format is not a good choice.  So we would like to see
> more discussion of that aspect if the group wishes to pursue it.
>
> (One organizational point: section 4.4 actually describes custom curves,
> and we would prefer to see the draft focus on predefined curves.  We have
> ideas on how to reorganize the draft to define specific coordinate
> fields and curves based on them, which we are getting into shape to
> present shortly.)
>
> Hal Finney
> Andrey Jivsov
> Network Associates, Inc.
>
> URLs:
> NIST curves: http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf
>
> ECC groups:
> http://www.ietf.org/internet-drafts/draft-ietf-ipsec-ike-ecc-groups-03.txt
>

--Len.

---

From: David Shaw <[email-masked]>
Date: Mon, 23 Sep 2002 18:57:18 -0400

> in the IETF. It is worth nailing this down, I think.

I'm not against ECC in OpenPGP, but given how close 2440bis is to last
call, perhaps the ECC specification could go in a companion RFC?

David

-- 
   David Shaw  |  [email-masked]  |  WWW http://www.jabberwocky.com/
+---------------------------------------------------------------------------+
   "There are two major products that come out of Berkeley: LSD and UNIX.
      We don't believe this to be a coincidence." - Jeremy S. Anderson