Moving forward with Curve25519

[Werner Koch]

On Wed,  6 Aug 2014 19:29, openpgp at brainhub.org said:

> Curve25519 always has the high bit set to zero because it fits into
> 255 bits. ( For ECDH anyway; one may in theory reuse the high bit for

Right.

> the 32 byte can be 1. In OpenPGP these 32 bytes are encoded as an
> MPI. MPI in OpenPGP encodes the size in bits, counting from the most
> significant bit (MSB).

I mentioned that OpenPGP allows that; but experience has shown that an
MPI with the MSBit set is easily messed up due to the common 2-compl
encoding of integers.  Thus to represent an arbitrary octet string it is
better to make sure the MSBit is cleared.  Also the fixed size due to
the prefix byte has advantages over the small saving in 1 of 128 cases.

Actually the code in GnuPG and Libgcrypt does not care about it because
ECC points are considered opaque values but the fixed size makes it
easier for simpler implementations to pass a fixed string to the NaCL
library.

> realize even greater space savings by trial-generating public EC keys
> so that they have high bits as zeros. This will allow the MPI encoding
> to fit into smaller number of octets. We cannot do this when we prefix

Limiting the search space is not considered good style.

After all we do not save much compared to the overhead the OpenPGP
encoding introduces anyway (right, I suggested the longer OID approach).

> This was for two reasons that don't apply to Curve25519:

I know.

> 1. patents
> 2. there is a ~5% cost to decompress a point on short Weierstrass
> curves (NIST Suite-B curves, Brainpool curves).
>
> #1: never applied to ECDH, definitely doesn't apply in 2014.

And the compression patent expired last week.  I am not sure whether the
X-only format was also covered by this patent but recent discussion
pointed out that the last  harming patent was this one.

> #2: Montgomery curves don't need Y, thus there is no cost of decompression.

Agreed.

> One has to switch either by the tag or by the size of MPI. I think the
> logic based on MPI size is clear enough (if MPI size in bits <= 255
> ==> only X is used).

After all this is a different key due to the different fingerprint (but
note that the creation date may also be used to create a different
fingerprint).

> Support for multiple formats causes complexity. Given what we know now
> about modern curves, I think the default should be an uncompressed
> point. This is the case we should optimize for.

This contradicts with your dislike for the prefix byte due to space
reasons.  A compressed format with prefix byte is shorter than the
uncompressed format.  I guess we have some kind of misunderstanding
here.

> It makes little sense to talk about "uncompressed" Montgomery
> point. We should have a single blessed format, and it's clearly a
> "compressed" one.

Okay, we agree on X only, right?

There are two open questions:

- Native format as used by the reference implementation and the common
  use of a certain curve (i.e. little endian for Curve25519).  Or the
  usual network byte order.

  I favor the native format.
  
- Use of a prefix byte.

  I prefer a 0x41 prefix byte for two reasons:
  - Fixed length operations.
  - It is compatible with the proposed format of TLS.


> (There is some argument to say that the format should be an Edwards
> representation so that keys can be used for both DH and
> signatures. However, in all cases the standard should probably be some

If someone wants to use such a questionable design the NIST or Brainpool
curves may be used for that.  I do not plan to explicitly allow that in
GnuPG.

> True, there are applications where short keys are important. 32 byte
> keys are short enough that humans can handle them (i.e. type them
> encoded in base32 format, read them, and it's easier to scan them
> too). The abovementioned method to reduce the size of a public key
> makes this a bit easier for humans.

Not really, there is still some overhead.  For a base32 format (or
zbase32) a dedicated format can be used: Just the 4 byte timestamp, a 1
byte non-IETF identifier for the curve, and the plain key (leaving out
the prefix byte).  [With base32 we need to have a multiple of 5 bytes
and thus the above (4 + 1 + 32) leaves us with 3 spare bytes which could
be used to keep the prefix and length bytes.]

Reading Simon's draft again, he actually defines 0x41 as
"montgomery_x_le" (Montgomery X coordinate, little endian).  Which is
the definition we should of course also use.


Shalom-Salam,

   Werner


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