Catch 22 in ECC support of OpenPGP?

[Werner Koch]

On Fri, 31 Jan 2014 04:46, gniibe at fsij.org said:

> I think that adding new signature scheme requires its algorithm ID.

Right, for EdDSA we should have a new id.  Yesterday I changed the GnuPG
code and replaced the EdDSA hacks with new experimental algorithm id.
The code is not finished and actually the whole ECC stuff is currently
broken.  I'll fix that soon.

For EdDSA we need a new RFC to have the IANA assign a new algorithm id.
While doing that we should also address two questions:

1. Shall we keep the OID field or shall we replace it with either a
   curve size parameter or maybe assign a single algorithm identifier
   for Ed25519/EdDSA?

2. Does the use of MPIs make sense?  Bernstein defines the key as well
   as the signature material as octet strings and not as MPIs.

A reason to drop the OID field would be smaller key material which may
help with key backup or direct use of the key.  However, it complicates
parsing because we would need two methods.  I am fine with the OIDs
(after all I suggested them) because for key backup we can use our own
format.  Such a format should be URI encoded for use in QR codes anyway.

The problem with fitting an EdDSA key or signature material into an MPI
is the usual leading zero problem.  Thus for processing the red MPIs
needs to be left-padded with zeroes up to the size indirecty specified
by the OID.  Note that we do not have the compression flag byte in plain
EdDsA (but see below).  For GnuPG/Libgcrypt this is not a big problem
because we already have code in place to do that.  New OpenPGP
implementations may benefit from a simpler scheme.  Related to question
1, a length byte could also be used to distinguish between different
curves (i.e. Ed25519 and Curve41417).

RFC-4880 describes the key material as a series of MPIs, which would
rule out the above idea.  However, RFC-6637 already uses non-MPIs for
the OID and the KDF params.

> (1) Possible algorithm ID 22 for ECDH+ECDSA:
> http://www.ietf.org/mail-archive/web/openpgp/current/msg07163.html

I am not in favor of mixing them.  Encryption, and in particular DH, is
different from signing.  Having different algorithms ids also helps to
avoid mixing encryption and signing keys due to implicit capabilities.

> (2) Possible algorithm ID 22 for EdDSA:
> http://www.ietf.org/mail-archive/web/openpgp/current/msg07194.html

Before we can request the assignment of a new algo id, we need to write
the specs.  This is why I am currently using 105 for EdDSA.  Some of you
may have noticed that the CFRG (the IRTF crypto research group) is
currently discussing standardization of non-Weierstrass curves
(e.g. Curve25519 an its variants).  Watson Ladd is working on an I-D[1].
The TLS WG is also discussing these curves.

There are many ideas floating around and it would be useful to wait
until we have a clear picture.  This will help to solve the problem of
missing standard documents for the Bernstein (aka Chicago) curves.  The
available papers are not suitable for normative use in an RFC (maybe
with the exception of the Ed25519 paper).

Of course we could informally agree on an algorithm id for EdDSA, as we
always did in the OpenPGP WG.  However, a new algorithm id is not
sufficient as long as we do not have answers to the above questions.  We
better go in lock-step with the Ladd I-D.  Is there anyone with free
time to write an I-D?

Shouldn't we continue this discussing at the IETF OpenPGP mailing list?


Salam-Shalom,

   Werner


[1] http://www.ietf.org/id/draft-ladd-safecurves-03.txt

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.