Re: [TLS] Curve25519 in TLS

[Manuel Pégourié-Gonnard <[e-mail]>]

Hi,

On 24/09/2013 17:32, Simon Josefsson wrote:
> http://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
> 
I think a few points should be clarified in the draft. As the
introduction correctly states, Curve25519 is a new ECDH function, not
just a new curve for use with the usual ECDH construction. Let me sum up
the constructions of ECDH in TLS and in Curve25519.

TLS ECDH:
1. Private keys: random integer in the range [1, q-1] with q the order of G.
2. Public keys: a point on the curve (defined over F_p).
3. Public key encoding: either
    (a) the x and y coordinates of the point, or
    (b) the x coordinate and a bit for determination of the y coordinate,
with integers represented as big-endian bytes strings, preceded by a
first byte indicating which format was chosen (and holding the possible
additional bit).

Curve25519 ECDH:
1. Private keys: random 254-bit positive integer with the high-order bit
set and the three lowest-order bits cleared.
2. Public keys: any number in the range [0, 2^{256}-1].
3. Public key encoding: a byte string in little-endian convention.

Now I'll discuss the differences and possible issues in more detail.

1. Concerning the private key, I think keeping the paper's definition
does not raise any issue. Implementors should just be careful to use a
special procedure for this curve.

2. Concerning the public key, the 256-bit integer in the paper
represents (modulo p) the x coordinate of a point on the curve E, but
this point may not be defined over F_p, but over F_{p^2}. An alternative
way of seeing things is that the public key may be either the x
coordinate of a point in E(F_p) or of a point in E'(F_p) where E' is the
twist curve y^2 = x^3 + 2Ax^2 + 4x.

By construction of E, this is not a security issue at all, and rather a
fact that simplifies implementations of the Curve25519-ECDH protocol,
since there is no need to check the validity of public keys and they are
shorter, but it introduces a real difference (in the type of objects,
not just their representation) with the usual TLS ECDH function.

3. So, if we want to preserve the nice property than any 32-byte string
(ie, any 256-bit integer x) is a valid key (and I think we do), we don't
have a y coordinate at our disposal for the normal encoding procedure.
Some ideas around this issue:

A. Just use the convention y = 0 and one of the existing formats.
Pros: simple, just works.
Cons: with the basic "uncompressed" format, wastes 32 bytes of bandwidth.

B. Always use the "ansiX962_compressed_prime" format.
Pros: doesn't waste bandwidth.
Cons: forces applications to advertise support this format, which is a
problem if they can't support it for other prime curves, unless we
introduce an exception to the effect that support for this format with
this particular curve is implied as soon as support for the curve is
advertised. Does not seem very clean to me.

C. Introduce a new point format "compressed_prime_montgomery".
Pros: doesn't waste bandwidth, doesn't look hacky.
Cons: a new point format only for one curve? OTOH, it is indeed a
particular class of curve, since the recommended formulas work only with
the x coordinate, and other curves in this class may be added later.

Note that A and C may be combined.

Any other idea?

Manuel.