Subject: Re: ECC curve ID

From: Werner Koch <[email-masked]>
Date: Thu, 17 Apr 2008 10:57:35 +0200

Hi,

and sorry for me taking so long to reply.  I struggled too long with
real world OpenPGP interoperability problems ;-).

On Thu, 28 Feb 2008 00:31, [email-masked] said:

> I think that support for arbitrary curves has some merits. On the
> other hand, these benefits must be compared against possibility of
> ever getting the ECC support in OpenPGP applications.

My point was to allow an implementor to use a different curve and *if*
that curve eventually make it into the specs, old messages will still
work.  We had this problem in the past where we internally agreed on an
ID (e.g. for Twofish), implemented it in PGP and GPG and then hoped it
would make it into the standard.  Given the size of the WG at that time,
we could be pretty confident that it will make it into the standard and
thus there was no need to use an ID for an experimental algorithm.

Today it is different.  In particular there are more possible curves to
use for an algorithms and thus tehre is no room left for experimental
use.  The experimental IDs don't really work.

> OpenPGP application is not required to understand ASN.1 /
> DER. Essentially, this proposal means that we are replacing one-byte
> ID by multi-byte ID. Would it be good to agree on new curve anyway and

There is no need to understand them.  In fact we are already using ASN.1
encodings and I bet that all implementations don't parse them but just
take them as a binary blob.  Thus the only change would be to specify
the curve as a DER encoded OID insted of a number and mark that as MUST
implement.

> applications will be able to interoperate using curves we disagree
> on. The freedom will be detrimental to interoperability. (Conversely,

This is not a problem.  RSA is an optional akgorithm but all smartcards
use RSA and it just works.  However if someone uses a perfectly OpenPGP
compliant 8k RSA key, you will get serious interoperability problems.  I
consider this a very similar problem to non-standard curves.

> companion proposal or in the next version of the document. For
> example, ID 254 might mean that there is an ASN.1 structure
> referencing the curve, inserted somewhere into the sequence of

Too complicated.  For the sake of backward compatibility we had to use
such kludges in the past.  For a new feature we should really avoid
using that.  

My proposal is thus:

Change section 8 to:

  The following algorithm-specific packets are added to Section 5.5.2
  Public-Key Packet Formats of [RFC4880] to support ECDH and ECDSA.

  This algorithm-specific portion is:

    Algorithm-Specific Fields for ECDH keys:
    
      * a one-octet length of the next field

      * an ECC curve OID, defined in section 10

      * a one-octet value 01, reserved for future extension

      * a one-octet hash function ID used with KDF

      * a one-octet algorithm ID for the symmetric algorithm used to
        wrap the symmetric key for message encryption, see section 7 for
        details

      * MPI of EC point representing public key

    Algorithm-Specific Fields for ECDSA keys:

      * a one-octet length of the next field

      * an ECC curve OID, defined in section 10

      * MPI of EC point representing public key

  The following algorithm-specific packets are added to section 5.5.3.
  Secret-Key Packet Formats of [RFC4880] to support ECDH and ECDSA.

    Algorithm-Specific Fields for ECDH or ECDSA secret keys:

      * MPI of an integer representing the secret key, which is a scalar
        of the EC point

Change section 10 to:

    The parameter ECC curve OID defines the curve.

    OID                  Curve description              Curve name
    ----------------------------------------------------------------   
    1.2.840.10045.3.1.7  NIST Curve P-256 [FIPS 186-2]  "NIST P-256"
    1.3.132.0.34         NIST Curve P-384 [FIPS 186-2]  "NIST P-384"  
    1.3.132.0.35         NIST Curve P-521 [FIPS 186-2]  "NIST P-521"  

    Implementations MUST implement "NIST P-256", "NIST P-384" and "NIST
    P-521".  The hexadecimal representation used in the public and
    private key encodings are:

    Curve Name   Len  Hexadecimal representation of the OID
    ----------------------------------------------------------------   
    "NIST P-256"  8   0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x03, 0x01, 0x07 
    "NIST P-384"  6   0x05, 0x2B, 0x81, 0x04, 0x00, 0x22            
    "NIST P-521"  6   0x05, 0x2B, 0x81, 0x04, 0x00, 0x23             

> with Windows Vista, Linux (openssl), etc. Which ECC standard
> *excludes* the curves specified in the proposal? I claim that the
> proposed subset of curves is the most widely supported subset of any

I don't have any  problem with these curves. 

It is not matter of whether they are exluded but on whether national
bodies require the use of certain curves.  The US requires thus but
other countries may require different ones.  Without a way to use their
curves they won't be abale to use OpenPGP and need to use X.509.  For
the very same reason we include RIPEMD-160; there is no real technical
reason to use it but it is required by some legislatives.  We can make
them all happy with a minor change to yopur porposal.  For an
implementor it is just a nit to support this chnaged format.  It might
even be easier because there might be no need for an OpenPGP-Curve-ID
mapping table.

> This is where freedom will make interoperability problematic. It is
> hard to come up with preferences that control the structure of
> self-signatures, because preferences themselves are stored in

Same goes for SHA-256 or DSA-2.  We already have interoperability
problems.

> self-signatures. The only solution to this chicken-and-egg problem is
> to establish small core set of curves, the two ones I proposed in the
> draft, and focus on supporting these curves first.

Fine with me.

>> p.s. I don't think that the notion of "Top Secret" And "Secret"
>> belongs into
>> an RFC.  I could also ask to add "VS/NfD", which is a secrecy level used
>> in Germany
>
> This seems reasonable. If any of 3 curves in the proposal satisfy

This was not my point.  It is not a matter of an Internet standard to
define what is top secret and what is secret.  This is an
oprganisational issue of the entity using appliactions based on that
standard.  Add it as an informational note at the end of spec after the
security considerations and mark is as U.S. specific.  As it stands now
it looks pretty much like a part of the standard.

Shalom-Salam,

   Werner

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

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 18 Apr 2008 11:47:53 -0700

> real world OpenPGP interoperability problems ;-).

One more reason to design this document right ;-)

>     OID                  Curve description              Curve name

I don't disagree with most of the arguments you provide, it was a close 
call for me. Let me summarize how I see the issue.

Pros for OIDs:

1) OpenPGP depends on another registry, doesn't need to maintain its 
own. The assumption is that OID registry will be up-to-date and any 
curve we will ever need will have an OID.

2) In the time window when OID is available but it is not yet in OpenPGP 
registry, standard-compliant messages can be created faster.

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.

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

3) consistency with the way OpenPGP references other algorithms.

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

I wonder if I am a lone supporter of numeric IDs, though.

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) ?

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

> it looks pretty much like a part of the standard.

I think I share your views on this. This resonates with the discussion 
we had recently regarding profiles v.s. algorithms. Some people wanted 
this spec to be Suite-B only, others -- format spec only. What we have 
now is mostly the format spec, which we need in either case, with a 
short informative section that tells what to do to get Suite-B support. 
I would look past this perceived impurity because Suite-B makes the 
document more relevant.

>    Werner

Thank you for the comments.