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

From: Jon Callas <[email-masked]>
Date: Sat, 1 Feb 2014 04:57:29 -0800

On Jan 31, 2014, at 4:48 AM, Werner Koch <[email-masked]> wrote:

> 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.

Who cares? It's just a bitstring that is added into the hash to make it unique for the signature algorithm. Think of it as a form of salted hash where that is for the algorithm. The only thing that matters is uniqueness, and even if there's an OID collision, it's not the end of the world. Do it!

> 
>> 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 can think of two ways to deal with it:

1) Ignore it. It's not *really* an MPI. It's a point in MPI format, and just throw it in there.

The reason for the rule is so that a given integer doesn't have subtle problems from different encodings with leading zeroes.

But these aren't integers, they're points of a known length. Just use the length and don't worry.

2) Consider this a primitive form of compression and roll with it.

Of those two, I vote for (1). There's no real value in the compression, it's an observation. And the reason there's little value in compression is the same reason that there's little harm in just putting the point there and don't worry about leading zeroes.

Let me take the case of the curve 414-19, and let's imagine that there's two leading zeroes in a point and thus the debate is whether we code it as a 412 or 414 bit field.

Either of those is kinda meh. It would be *better* even to make the field be 416, as that's an even multiple of 32. That gives you fast unpacking. If you're not going to do 416, it seems not worth worrying about the MPI rules, as you already have to have in your library a way to slosh zero high bits around anyway.

For a curve like one of the 255-bit ones, it's easy to stress over that extra bit, and why *not* just pack it into 256 bits for efficiency? Don't stress. 

> 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.

Well, 414-19 is an Edwards curve so you can do EdDSA on it. It's 30 bits larger than 384, so you could use a 384-bit hash, or a variable-length hash function like Skein or SHA-512/z.

	Jon

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 03 Feb 2014 22:53:46 -0800

> Of those two, I vote for (1). There's no real value in the compression, it's an observation. And the reason there's little value in compression is the same reason that there's little harm in just p…

One positive side effect of using compression is that de-compression 
implies a validated point.

In some uses of OpenPGP protocol it may be necessary to validate that 
the ephemeral public key of ECDH lies on the curve and not on some 
specially selected curve with points of low order.

See "Validation of Elliptic Curve Public Keys" sec
4.2 Invalid-Curve Attack on ECIES (that applies to ECDH as well).