Subject: [openpgp] Catch 22 in ECC support of OpenPGP?

From: Werner Koch <[email-masked]>
Date: Fri, 31 Jan 2014 09:48:33 +0100

Hi,

[gniibe asked on the gnupg-devel list on how to support EdDSA.  We
 better continue the discussion here.]

On Fri, 31 Jan 2014 04:46, [email-masked] 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.

---

From: Jon Callas <[email-masked]>
Date: Fri, 31 Jan 2014 02:04:24 -0800

>   curve size parameter or maybe assign a single algorithm identifier

OIDs are just unique constants. It's quasi-IANA governed. Getting an OID is easy as long as you have a base OID from the IEEE. I've gotten OIDs for a number of organizations, and once you have one, you just put your own off of that.

So suppose they give you [1.2.3.4]. All you need to do is make [1.2.3.4.x.y.z...] for your own OIDs for whatever purpose.

If you look at <http://www.oid-info.com/faq.htm>, particularly question 10, there are easy ways to get one. There are suggestions that include how to get an OID from IANA, and also how to use a UUID as an OID.

>   as the signature material as octet strings and not as MPIs.

As you've noted, in RFC 6637, Andrey codes an EC point into an MPI, which I think is clever, and works fine. Why not just do it?

> format.  Such a format should be URI encoded for use in QR codes anyway.

That's a good argument for not using a UUID, because it's going to be over 16 bytes long. But you can go to IANA for an OID, or get your own OID base and then just issue one from there.

> better go in lock-step with the Ladd I-D.  Is there anyone with free

I'd say just do something that will work. Get an OID, we agree on an algorithm ID, and then Bob's your uncle and Alice is your auntie.

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

You mean this isn't?

	Jon

---

From: Werner Koch <[email-masked]>
Date: Fri, 31 Jan 2014 13:48:38 +0100

> If you look at <http://www.oid-info.com/faq.htm>, particularly question 10, there are easy ways to get one. There are suggestions that include how to get an OID from IANA, and also how to use a UUI…

Sure.  We already use one from the GNU arc in Libgcrypt:

  1.3.6.1.4.1.11591.15 ellipticCurve
    1.3.6.1.4.1.11591.15.1 Ed25519

This is a different OID than Peter Gutman's for Curve25519.

> As you've noted, in RFC 6637, Andrey codes an EC point into an MPI,
> which I think is clever, and works fine. Why not just do it?

I explained it below.  RFC-6637 requires the use of SEC encoding which
is nice because you will never have the problems with leading zeroes.
However, EdDSA uses a different compression format without any
identifier (which makes up nice 32 bytes).  A leading zero may however
happen.  RFC-4880 does not allow that and thus one would need to check
whether to left pad a read MPI before using it with Ed25519 code.  As I
said, not a real problem but it would be possible to save 2 lines of
code if we could use a raw octet string.

> I'd say just do something that will work. Get an OID, we agree on an algorithm ID, and then Bob's your uncle and Alice is your auntie.

An OID is given above.

   The following public key algorithm ID is added to expand Section
   9.1 of [RFC4880], "Public-Key Algorithms":

          ID        Description of Algorithm
          --        --------------------------
          22        EdDSA signature algorithm [EdDSA]

   [EdDSA] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja Lange,
   Peter Schwabe, Bo-Yin Yang. High-speed high-security
   signatures. Journal of Cryptographic Engineering 2 (2012),
   77–89. Document ID: a1a62a2f76d23f65d622484ddd09caf8. URL:
   http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26.

I have not yet seen the specs for Curve41417 and thus I do not know
whether it also defines EdDSA for signatures.  EdDSA according to the
paper requires the use of SHA512 but it also tells that other hash
algorithms are possible.  Hopefully Watson Ladd's I-D can eventually be
used as a reference.

Salam-Shalom,

   Werner

p.s.
>> Shouldn't we continue this discussing at the IETF OpenPGP mailing list?

I forwarded the entire message text ;-)

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 31 Jan 2014 22:31:47 -0800

> code if we could use a raw octet string.

Werner, it's an unexpected argument...

I would say that the MPI encoding is even more appropriate format when 
considering a compact representation (i.e. (x) v.s. (x,y) )

For example, with http://tools.ietf.org/html/draft-jivsov-ecc-compact 
the compact representation is exactly an element in the underlying 
field, Fp. It's exactly an integer mod p. If we use an MPI for an RSA 
key component, why shouldn't we use an MPI for the x as well?

Likewise, with Ed25519 high-bit encoding the value is (almost) an 
integer in a Fp field.

It's a good idea to ensure that when you copy the value of an MPI into a 
buffer, the highest bytes of the buffer are zeros ;-)