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

Jon Callas <> Sat, 01 February 2014 21:05 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 898401A1F7A for <>; Sat, 1 Feb 2014 13:05:40 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.358
X-Spam-Status: No, score=-0.358 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DATE_IN_PAST_06_12=1.543, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id qbxb5mBLIln2 for <>; Sat, 1 Feb 2014 13:05:39 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id F18F81A1F76 for <>; Sat, 1 Feb 2014 13:05:38 -0800 (PST)
Received: from localhost (localhost []) by (Postfix) with ESMTP id B32FA4C53C22; Sat, 1 Feb 2014 13:05:34 -0800 (PST)
X-Virus-Scanned: amavisd-new at
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id GBASkhkHalMo; Sat, 1 Feb 2014 13:05:33 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTPSA id 57EC04C53BFF; Sat, 1 Feb 2014 13:05:31 -0800 (PST)
Received: from [] ([]) by (PGP Universal service); Sat, 01 Feb 2014 13:05:33 -0800
X-PGP-Universal: processed; by on Sat, 01 Feb 2014 13:05:33 -0800
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Jon Callas <>
In-Reply-To: <>
Date: Sat, 01 Feb 2014 04:57:29 -0800
Message-Id: <>
References: <> <> <>
To: Werner Koch <>
X-Mailer: Apple Mail (2.1827)
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Cc: " OpenPGP" <>, Jon Callas <>
Subject: Re: [openpgp] Catch 22 in ECC support of OpenPGP?
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 01 Feb 2014 21:05:40 -0000

On Jan 31, 2014, at 4:48 AM, Werner Koch <> wrote:

> Sure.  We already use one from the GNU arc in Libgcrypt:
> ellipticCurve
> 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.