Subject: Re: [TLS] Curve25519 in TLS

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 16 Oct 2013 08:36:52 +0200

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.

---

From: [email-masked] (Martin Rex)
Date: Wed, 16 Oct 2013 08:42:35 +0200 (CEST)

> 3. Public key encoding: a byte string in little-endian convention.

Make it work completely _without_ rfc4492 bloat,
and similar to DH instead, defining new KeyExchange Methods
and seperate ciphersuites for it.

-Martin

---

From: Juho Vähä-Herttua <[email-masked]>
Date: Wed, 16 Oct 2013 12:48:42 +0300

> On 16.10.2013, at 9.42, [email-masked] (Martin Rex) wrote:
> 

I think this would be the best option for Curve25519, just handle it as a special case without trying to force it into the overly complex ECC spec.

Juho

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 16 Oct 2013 15:05:00 +0200

> and seperate ciphersuites for it.
If we want to cover all existing key exchanges and ciphersuites, this would mean
defining four new key exchanges (ECDH25519-PSK,RSA,ECDSA,anon), and 52 new
ciphersuites currently. And then duplicating every ECDHE-based ciphersuite
defined in the future. And if at some point, a new Montgomery or Edwards curve
is proposed (maybe the recent curve3617), duplicating all that again.

That's quite a lot of trouble: what specific problem would it solve? What
exactly do you mean by RFC 4492 "bloat", and in which specific way defining new
key exchanges would make it lighter? As an implementer, I don't feel like adding
new key exchanges for Curve25519 would make my life any easier, as it would come
*in addition* to RFC 4492 support.

Anyway, I believe that cryptographic parameters agility is a highly desirable
property of a protocol like TLS, and RFC 4492 provide that, better than
specialised key exchanges supporting only one curve. If that solution had been
adopted in early 2006, the only one curve would probably have been a NIST curve
(curve25519 was very new at the time, while NIST curves had been around for
years), and you wouldn't be very happy now, I guess.

I hope my first post didn't give the wrong impression: I don't think the
framework from RFC 4492 is a misfit for the Curve25519 ECDH function, the only
real point of friction is the encoding of the public keys. The other remarks I
made are merely things I'd like to see clarified in the draft, and information
that seemed relevant to me to discuss the public key format.

Manuel.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Oct 2013 11:48:28 -0700

Minor nitpicks about language below.

> first byte indicating which format was chosen (and holding the possible
I don't believe this is correct: RFC4492 permits curves with cofactor
greater than one.
I don't have a copy of the IEEE standard in front of me, but I believe
in this case one has to
do a group membership check. So it depends on what the meaning of G is.
> special procedure for this curve.
What is actually happening is that exponentiation by the private key
is annihilating the small order
torsion subgroup on both the curve and the twist because the private
key is divisible by 8, and the curve and twist
have large prime-order subgroups with cofactor 8 and 4 respectively.
This is a big difference from the usual method,
in which one only sends members.
> Cons: with the basic "uncompressed" format, wastes 32 bytes of bandwidth.
Also, a dirty hack.
> advertised. Does not seem very clean to me.
The other issue is that this isn't the ansiX962 format for deep
technical reasons. You would need to use
a birational morphism to Weirstrauß form, which is a pointless PITA,
or just tell pleasing lies, which annoys those of
us trying to analyze things, and is a potential source of bugs.
> Note that A and C may be combined.
Probably the best idea, especially given that definition of addition
is completely different.
>
> Any other idea?
>
> Manuel.
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 16 Oct 2013 21:55:56 +0200

On 16/10/2013 20:48, Watson Ladd wrote:
> greater than one.  I don't have a copy of the IEEE standard in front
> of me, but I believe in this case one has to do a group membership
> check. So it depends on what the meaning of G is.
>
Yes, sure, when receiving the peer's public key, one must always check
it is actually a point on the expected curve (which is done
automatically in the process of computing y if the compressed format is
used) and, if the group generated by G has cofactor greater than one,
that the peer's public key belongs to this subgroup.

I don't really see how it contradicts my statements, but anyway.

> is annihilating the small order torsion subgroup on both the curve and
> the twist because the private key is divisible by 8, and the curve and
> twist have large prime-order subgroups with cofactor 8 and 4
> respectively.

100% agreed. I'm just not sure if this precision about the "why" is
essential in the I-D, or if we should just leave it in the paper, and
just mention in the I-D that implementers MUST be careful to generate
private keys in the mandated special way for Curve25519.

> This is a big difference from the usual method, in which one only
> sends members.

Well, to be really nitpicky, if the peer follows the procedure, she will
only send members, just as with the usual method. The difference is,
*if* the peer doesn't send members of the subgroup generated by G (ie by
9 in the Curve25519 case), with the usual method we must check and
reject invalid public keys, and with the Curve22519 we just don't care
since the choice of the private exponent takes care of that for us, as
you accurately described.

>> Cons: with the basic "uncompressed" format, wastes 32 bytes of bandwidth.

I don't deny it :)

> technical reasons.  You would need to use a birational morphism to
> Weirstrauß form, which is a pointless PITA, or just tell pleasing
> lies, which annoys those of us trying to analyze things, and is a
> potential source of bugs.

Agreed. What I was suggested was indeed to abuse this format and give it
a different meaning just for this curve. Which may be qualified as a
dirty hack too, obviously.

> Probably the best idea, especially given that definition of addition

It's certainly the less hackish way.

Thinking about it, I'm inclined to say we don't need to define a new
ECPointFormat entry, the I-D should just mandate that support for (resp.
use of) curve25519 implies support for (resp. use of) the associated
(unamed) point format. This avoids possible consistency issues like a
client advertising support for the curve but not for the associated
point format.

Similarly, the usual point formats have a leading byte indicating the
format used, that should IMO be dropped for curve25519.

So this would lead to the definition that, for this curve, instead of
containing "the byte string representation of a field element following
the conversion routine in Section 4.3.3 of ANSI X9.62", the point member
of the ECPoint structure contains an opaque[32] representing the
x-coordinate of the point.

Which would only leave the issue of the byte order of this string. Here
it has no security implications, and I'd be inclined to mandate
big-endian order (a divergence from the Curve25519 paper), with the
rationale that is it more consistent with other encodings and that
implementations already have routines for outpouting bignums in this
order. OTOH, this would mean that people using the existing/reference
implementations of the Curve25519 function would need to reverse its
output/inputs. Either way I don't have strong feelings about this.

Manuel.

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 16 Oct 2013 22:16:40 +0200

You wrote:

> ECPointFormat entry, the I-D should just mandate that support for
> (resp. use of) curve25519 implies support for (resp. use of) the
> associated (unamed) point format. This avoids possible consistency
> issues like a client advertising support for the curve but not for
> the associated point format.
> 
> containing "the byte string representation of a field element
> following the conversion routine in Section 4.3.3 of ANSI X9.62", the
> point member of the ECPoint structure contains an opaque[32]
> representing the x-coordinate of the point.

This sounds like a feasible approach to me.  Maybe we need to put this
solution in writing, and maybe put some of the other options in writing
as well, to allow people to make an informed decision of where to go.  I
think this thread has been quite informative, and I'm hoping we can
reach some early consensus and update the draft with that.

/Simon

---

From: [email-masked] (Martin Rex)
Date: Thu, 17 Oct 2013 20:30:15 +0200 (CEST)

> > representing the x-coordinate of the point.

This should probably be a variable length vector so that the
format can be reused beyond curve25519 for similar curves with
longer keys (is curve3617 such a thing?)

> reach some early consensus and update the draft with that.

Extending plus subsetting rfc4492, so that PDUs and code points
for ECDH cipher suites can be shared between curve25519 and other
ECC curves, seems appropriate and acceptable.

But I would highly appreciate if the generic bloat, brittleness and
timing-sensitive ECC math of regular rfc4492 can be avoided as much
as possible.  So a new, simplified/specialized ECPoint format that
is mandatory for use with curve25519 and relatives, would help a lot.

-Martin

---

From: Nico Williams <[email-masked]>
Date: Thu, 17 Oct 2013 15:21:17 -0500

> longer keys (is curve3617 such a thing?)

Yes (and yes, at least it exists as a curve specification in
safecurves.cr.yp.to; dunno if code exists).  (Ditto Curve1174.)

<aside>
If the choice is between

   sequence {curve ID, variable-length octet string}

   extensible choice with curve ID as discriminant and the value type
is a fixed-sized octet string of size given by the curve ID

   sequence {curve ID, octet string of size given by curve ID}

which is best?

The first two are commonplace and easy to implement; the first being
the easiest to implement.  The last is akin to ASN.1's IOS -- too
complex, no one will bother as no one has bothered.

So that's two choices, the first one being historically easier to implement.
</aside>

> ECC curves, seems appropriate and acceptable.

Yes.

> is mandatory for use with curve25519 and relatives, would help a lot.

Agreed.

Nico
--