Moving forward with Curve25519

[Andrey Jivsov]

On 08/06/2014 12:53 AM, Werner Koch wrote:
> On Wed,  6 Aug 2014 00:40, openpgp at brainhub.org said:
>
>> For all protocols that I know, including OpenPGP, the Y coordinate is
>> not used in the calculation of the shared secret in ECDH. This is
>
> Sure.  I mentioned 0x42 only for completeness.  We do not need it.
>
>> X has aesthetically pleasing 32 byte size. X is an integer, which fits
>> perfectly into the OpenPGP container, which is an MPI.
>
> Only 50% of those values would fit as 32 bytes into an OpenPGP MPI.  As
> soon as the high bit is set we should prefix it with a 0x00 byte to
> avoid signed/unsigned problems.  Further, OpenPGP _requires_ us to strip
> off leading zero bytes.  Thus there won't be a fixed length anyway.
>

Hello Werner.

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 
something else if needed, but OpenPGP can standardize that the high bit 
is always zero )

To show how what I proposed always works, let's say we are encoding some 
Curve256189 (a similar prime closest to 2^256). In this case the point 
representation still fits into 32 bytes and the highest bit of 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).

If the MSB of a particular point is bit 250, that's fine. There is even 
an advantage with the format I am proposing in that one can 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 an integer 
with a tag value, because the tag value will assure that the high bits 
are set.

In more details, the selection criteria that I mentioned earlier work as 
follows. If the tag is used, a 255-bit MPI cannot be encoded in fewer 
than 256 bits, while it will be fewer than 256 bits in case of the 
Curve25519.


> Using a constant prefix makes things easy.  With the prefix byte we
> always have 35 bytes (2 bytes length, 1 byte prefix, and 32 byte value)
> and the length will always be 263 (bits).  This allows to keep the code
> very small by writing or reading the constant string 0x01,0x07,0x40
> which is the followed by the 32 bytes for X.  And other implementations
> may use the regular MPI machinery for processing the data.
>
> Actually you did the same in RFC-6637 by requiring the 0x04 prefix.

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

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.
#2: Montgomery curves don't need Y, thus there is no cost of decompression.

>
>> I think that OpenPGP should adopt X as the format for the ECDH. This
>> works with Curve25519 encryption or any other ECDH scheme.
>
> I concur.
>
>> ( Besides, the value 41 or 42 is implied by the curve OID in the
>> following way. If we are talking about encryption and the OID is
>> Curve25519, you know it's 41. The value 40 v.s. {41,42} is implied by
>> the curveID and the size of the MPI. )
>
> Sure.  I actually considered to make that implicit by either the OID or
> even by looking at the size of the MPI and map that to a certain curve.
> However, this breaks with the existing ECC format and has is slightly
> annoying in that we do not known in advance what will come.

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

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.

  (We have a
> similar problem with the IV for the key protection which depends on the
> block length of the cipher algorithm; if you do not known that algorithm
> you can't properly parse the packet).

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

(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 "compressed" 
form).

>
> A more compact key representation would be useful but I do not think we
> should do that with v4 packets.  If we need a shorter key presentation
> we can do that outside of OpenPGP.  For example in a QR code we may want
> a different encoding of the key data (e.g. human readable with checksum).

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.

Thank you

>
>
>
> Shalom-Salam,
>
>     Werner
>