Comments on ECC draft

[[e-mail]]

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