Subject: Comments on ECC draft

From: [email-masked]
Date: Wed, 5 Sep 2001 18:28:32 -0700

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

---

From: [email-masked] (Bodo Moeller)
Date: Mon, 10 Sep 2001 21:50:25 +0200 (CEST)

[email-masked]>:

[...]
> by patents.

[Field decriptors 1 and 2 are for pseudo-Mersenne prime fields.]

What patents?  These should be patents applied for by the NSA (the
optimizations for pseudo-Mersenne primes are due to Jerry Solinas).
I'm not sure how they'd handle licensing -- the patents for Jerry's
algorithms for Koblitz curves have already been issued earlier this
year, and presumably licensing would be similar to that, whatever this
means.  (Hopefully no restrictions, as for DSA, which is also
patented.)

(Note that the FIPS recommended curves over prime fields all are based
on pseudo-Mersenne primes.  Of course applications that want to use
optimized modular arithmetic for these primes can do so, whether or
not special field descriptors are used.)

>              And descriptors 14-16 are for normal bases, where we see

Also, this is an area where patents really appear to be a severe issue.

> fields and curves based on them, which we are getting into shape to

The draft obviously intends to provide a lot of flexibility, while in
the sake of efficiency and interoperability it would be better to
sacrifice flexibility and limit the class of allowed curves.