Subject: Re: ECC curve ID

From: Werner Koch <[email-masked]>
Date: Mon, 05 May 2008 12:06:15 +0200

On Fri, 18 Apr 2008 20:47, [email-masked] said:

> Pros for OpenPGP IDs.
>
> 1) Vote of confidence for a particular curve. If it is included,
> potential implementers have agreed on it. It will be more likely
> widely supported. For example this is useful for hardware folks who
> plan far ahead, plays in the decisions about which curve to use in key
> self-signatures, and gives priorities to performance optimizations.

The same can be said of OIDs.

> 2) Shorter public keys, faster, smaller code (switch() v.s. memcmp()).

Well, okay.

> 3) consistency with the way OpenPGP references other algorithms.

Only if we agree that a curveID describes an OpenPGP algorithm.  In my
view this is a parameter of the algorithm, much like p, q and g in DSA
or even the key size of all aglgorithms.

For sure I do not want to convey all ECC curve parameters, thus using a
way to describe the curve is important.

> 4) Named curves can be introduced as an extension. The core set of
> curves will be encoded as integers, others as named curves.

I thought of that and was about to propose a format using an ID of 0 to
identify a named curve.  However the specification as well as the code
will be more complicated - even in the case that named curves are not
supported by the implementation.  

> Do you see any value in having some approval process for new curves?
> Does it bother you that I can use some questionable curve and it will
> carry equal status per the spec to the three curves we discussed so
> far (will we have a method to distinguish "next good" curve past P-521
> from an experimental curve) ?

No.  We also don't approve implementations and have no real limits on
key sizes.  It is easy to get things wrong.  Using a good curve is as
important as to use sound parameters for RSA.

> Can we reach an agreement if the document also defined a method to
> list named curves, along the lines of Werner's proposal?

If there is no other way to allow for arbitrary curves, I would agree to
it. However, I still believe that an OID with a memcmp in the code is
easier to implement than a numeric ID with a switch and a mechnism to
cope withe the optional OID named curve.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Auschnahme regelt ein Bundeschgesetz.

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 15 May 2008 23:59:16 -0700

I see three aspects of the issue.

1. The desire to control curves. What degree of freedom is appropriate?

Currently the document says:

"Future allocations in the registry will be done by IETF Expert Review 
process after general consensus between implementors of the standard is 
reached."

It doesn't allow other curves without general agreement (exact body that 
makes approval is not critical). The following item explains the reasons.

2. Different curve is not the same as different RSA key size.

The following argument will rely on implementation specifics that are 
unique to ECC.

Currently
http://www.ietf.org/internet-drafts/draft-jivsov-openpgp-ecc-00.txt only 
allows curves over prime underlying field. The primes selected for these 
fields are, forgive my exaggeration, weak primes. That is, they are 
primes very close to 2^m. The purpose of these primes is to construct 
finite fields with fastest operations for the given field size. This 
field is called underlying field of EC. The cryptography of ECC doesn't 
depend on the strength of operations in the underlying field, so the use 
of such special primes is justified. While it is possible to use 
general-purpose large-integer library to implement operations in the 
underlying field, this is not practical for performance reasons. 
Implementations will achieve better performance by tuning the code for 
each underlying field at compile time, or, in case of hardware, this may 
be done by the manufacturing time.

Conversely, even when RSA is implemented in hardware, a parameter to RSA 
key size is almost certainly a variable in software. There is nothing to 
gain by separately implementing RSA 2048 and RSA 4096 operations.

3. Finally, there is a question of how to reference a curve. Currently 
the draft uses numeric IDs, consistent with other IDs in RFC 4880.

With the exception of using less space to encode more RFC4880-aligned ID 
v.s. DER OID and slightly better lookup time, I see two approaches as 
similar. Some of pros and cons were mentioned earlier.

Given my opinion on 1., 3., and statement 2., and that the use of OID 
will need substantial rewrite of the draft, I prefer to use one byte 
curve ID. I see the difficulty of obtaining curve ID as a feature. I 
don't see the ease of introduction of new curve ID as a way to improve 
interoperability. If an implementation publicly stated that it 
implements IDs 1, 2, and 3, it's a loosing bet to expect that it will 
support any other curve. Compare this with RSA support. To put this 
differently, as an implementor I would like to hear in advance that 
another curve ID is going to be introduced into OpenPGP installation 
base, while my RSA implementation is capable of handling any key size 
within a reasonable range.

This issue is lingering unresolved between a few of us who expressed 
their opinions. I would appreciate opinion of the list on the following 
items. Please read the introduction above and mark your vote.

==================================================================
A: Keep current text regarding the procedure to approve new curves
    (for/against)
==================================================================
B: Keep current method to encode curve IDs as numeric IDs
    (for/against)
==================================================================
C: Need extension mechanism specified in the draft to add other
    curves
    (for/against)
==================================================================

Andrey:
	A: for
	B: for
	C: against

Thank you.

---

From: Werner Koch <[email-masked]>
Date: Wed, 21 May 2008 18:27:09 +0200

> 2. Different curve is not the same as different RSA key size.

What I want to express withn that comparision is that we already have a
wide range of parameters in addtion to the algorithm ID.  The curve ID
is just another parameter, or well a short-name for the curve
parameters.

> performance reasons. Implementations will achieve better performance
> by tuning the code for each underlying field at compile time, or, in
> case of hardware, this may be done by the manufacturing time.

They may still do this. I can't see that as an argument pro or con a
fixed list of curves.

> Conversely, even when RSA is implemented in hardware, a parameter to
> RSA key size is almost certainly a variable in software. There is
> nothing to gain by separately implementing RSA 2048 and RSA 4096
> operations.

I disagree.  Even pure software implementations are often tuned for
certain key sizes (e.g. to use the Karatsuba algorithm only for certain
sizes).  With hardware you even need to decide whether the hardware of
software implementation is faster for a certain size.

> support any other curve. Compare this with RSA support. To put this

Or compare that with DSA support.  How that we have DSA-2 many
implemtations fail because they can't cope with >1k DSA keys. That is a
similar interoperability issue as with new curve IDs.

> within a reasonable range.

And what about DSA implementations?

==============================================================
D: Use an OIDs instead of an algorithm ID and define the NIST curves as MUST.
   (for/against)
==================

Werner:
        A: for (as long as that does not forbit other curves)
        B: against
        C: for (as second best choice)
        D: for

Shalom-Salam,

   Werner