Subject: [TLS] Should we require compressed points

From: Eric Rescorla <[email-masked]>
Date: Tue, 21 Oct 2014 16:52:29 +0200

https://github.com/tlswg/tls13-spec/issues/80

Today we discussed the possibility of requiring support for compressed
points
in TLS 1.3 now that the IPR has expired.

Specifically, I propose that for TLS 1.3, we:

- Use only compressed points for the existing curves (and presumably
  whatever superior format is defined for the CFRG-recommended
  curves, as appropriate).

- Deprecate the Supported Point Formats extension for TLS 1.3

For RFC 4492-bis, we might also consider requiring support for compressed
points as well as uncompressed (already required) but this seems like a
separable issue, since it's mostly in service of optimization rather than
simplicity.

What do people think?
-Ekr

---

From: Hubert Kario <[email-masked]>
Date: Tue, 21 Oct 2014 11:01:11 -0400 (EDT)

----- Original Message -----

> From: "Eric Rescorla" <[email-masked]>
> To: [email-masked]
> Sent: Tuesday, 21 October, 2014 4:52:29 PM
> Subject: [TLS] Should we require compressed points

> Today we discussed the possibility of requiring support for compressed points

> separable issue, since it's mostly in service of optimization rather than

How does that impact possibility of adding more "exotic" curves like curve25519/Ed25519 
in some later point in time? 
-- 
Regards, 
Hubert Kario

---

From: Martin Thomson <[email-masked]>
Date: Tue, 21 Oct 2014 08:03:22 -0700

> in some later point in time?

I'd have thought that this only applies to the existing registrations.
New registrations can define a proprietary format.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 21 Oct 2014 17:03:27 +0200

On Tue, Oct 21, 2014 at 5:01 PM, Hubert Kario <[email-masked]> wrote:

> ------------------------------
>
> *From: *"Eric Rescorla" <[email-masked]>
> *To: [email-masked]
> *Sent: *Tuesday, 21 October, 2014 4:52:29 PM
> *Subject: *[TLS] Should we require compressed points
>
>

Hubert, thanks for your email.

I don't think it should impact it at all because you still have to
advertise the curves you
support. My assumption is that advertising curve X would be the same as
advertising
that you could support its defined point format(s).

-Ekr

---

From: Michael StJohns <[email-masked]>
Date: Tue, 21 Oct 2014 11:11:42 -0400

> - Deprecate the Supported Point Formats extension for TLS 1.3

I'm pretty much opposed to the former and I guess by extension the latter.

There's a very large body of code that doesn't support anything except 
type 0x04(uncompressed) X9.63 point encodings.   If you want to add 
support for compressed points (or hybrid compressed), I don't think 
that's necessarily a bad idea, but not at the expense of removing 
support for uncompressed points.   If you wanted to remove the supported 
point format extension, I guess you could mandate support for both 
compressed and uncompressed (and hybrid?).

As a second item, I would estimate the  chance we're going to see 
compressed points in X509 certificates as a regular thing prior to about 
10 years from now as very small, meaning that any general transition to 
EC based suites is going to require uncompressed point support.

Lastly, while the base IPR for point compression seems to be no longer 
of concern, I've still been told to avoid it for a few more years due to 
implementation patents related to compression.  I'm not sure how 
worrisome that is, but its one of the reasons that binary curves aren't 
in broader use still.

Just my $.02

Mike

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Michael StJohns <[email-masked]>
Date: Tue, 21 Oct 2014 11:16:56 -0400

On 10/21/2014 11:01 AM, Hubert Kario wrote:
> ------------------------------------------------------------------------
>

My personal opinion is that there needs to be a complete separation in 
encodings and code points between X9.63 compliant EC data and anything 
else.

In the specific case of the curves you mention, unlike X9.63 curves, 
signing curves/keys and key agreement curves/keys are not 
interchangeable or compatible.  They are actually two different crypto 
systems and will probably require different code points  and maybe 
encodings.

The other classes of curves that don't have an X9.63 (Montgomery?) 
representation will need similar treatment.

Mike

---

From: Yoav Nir <[email-masked]>
Date: Tue, 21 Oct 2014 18:26:27 +0300

> On Oct 21, 2014, at 6:03 PM, Eric Rescorla <[email-masked]> wrote:
> 
> 
> On Tue, Oct 21, 2014 at 5:01 PM, Hubert Kario <[email-masked] <mailto:[email-masked]>> wrote:
> From: "Eric Rescorla" <[email-masked] <mailto:[email-masked]>>
> To: [email-masked] <mailto:[email-masked]>
> https://github.com/tlswg/tls13-spec/issues/80 <https://github.com/tlswg/tls13-spec/issues/80>
> 
> I don't think it should impact it at all because you still have to advertise the curves you
> support. My assumption is that advertising curve X would be the same as advertising

It does say that unless we re-introduce the extension, each curve with come with one single point format. I think that’s a fine idea that simplifies the code.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 21 Oct 2014 19:01:48 +0300

> that you could support its defined point format(s).

I would just lock the point format per curve for non-X9.63-compatible
stuff, at least for DH. That is, use curve-defined wire encoding,
regardless of what point formats extension says.

Also, there is another issue with non-X9.63-compatible stuff:
Encoding of the premaster secret. Proposal: Use usual wire encoding.

Disadvantage of this is that TLS 1.2- compatiblity would require
contradicting RFC 4492 (but specs contradicting base specs is not
unheard of) in order to ignore point formats and pms encoding.

Now with this, one could just stuff raw 32-byte curve25519 public
key into *KeyShare packet (with no prefix) and use the raw shared
secret as premaster secret (also 32 bytes).

And similarly for some XYZ curve that is twice the speed of
curve25519, but has really odd 48-byte point format.

-Ilari

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 21 Oct 2014 11:56:57 -0700 (PDT)

Hi Eric,

  I agree with your proposal.

  Dan.

---

From: Michael StJohns <[email-masked]>
Date: Wed, 22 Oct 2014 12:03:45 -0400

> - Deprecate the Supported Point Formats extension for TLS 1.3

After thinking about this longer - how actually would this work 
negotiation wise?  Specifically "us[ing] only compressed points"?

AFAICT, all you're going to do is make the negotiation even more 
complex.  The TLS1.3 clients and servers will still need to implement 
uncompressed points to talk to TLS1.2 and before clients and servers.  A 
TLS1.3 server will still need to understand an offered Supported Point 
Format extension from a TLS1.2 client to figure out if it can send a 
compressed point public key.  (I think) A TLS1.3 client will still need 
to offer the Supported Point Format extension in case it's talking to a 
1.2 server if the client wants to offer a compressed public key.

Is there any benefit you get besides  the savings of 1/2 of a public key 
on the wire from the server to the client?  Call it 32 octets for a 256 
bit X9.63 key.

The only way you get away from this is if you have prior knowledge of 
the server implementation or you put TLS1.3 on a new port (which to be 
clear I'm not suggesting).

And you still need support for the uncompressed form for certificates 
for quite a very long time (RFC5480).

So what's the argument for doing this besides "we can"?

Mike

---

From: Watson Ladd <[email-masked]>
Date: Wed, 22 Oct 2014 09:11:10 -0700

> There's a very large body of code that doesn't support anything except
type
> 0x04(uncompressed) X9.63 point encodings. If you want to add support for
> compressed points (or hybrid compressed), I don't think that's
necessarily a
> bad idea, but not at the expense of removing support for uncompressed
> points. If you wanted to remove the supported point format extension, I
> guess you could mandate support for both compressed and uncompressed (and
> hybrid?).

There is a large body of code that doesn't support TLS 1.3 as well.
> As a second item, I would estimate the chance we're going to see
compressed
> points in X509 certificates as a regular thing prior to about 10 years
from
> now as very small, meaning that any general transition to EC based suites
is
> going to require uncompressed point support.

Yes, but uncompressed points are not a security concern in X509, but they
are in ECDH. Furthermore, the cost of adding compression support is very
small: it's a square root, a check, and potentially flipping the sign. The
benefit is that invalid point attacks are much harder to carry out.

>
> Lastly, while the base IPR for point compression seems to be no longer of
> concern, I've still been told to avoid it for a few more years due to
> implementation patents related to compression. I'm not sure how worrisome
> that is, but its one of the reasons that binary curves aren't in broader
use
> still.

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

---

From: Rene Struik <[email-masked]>
Date: Wed, 22 Oct 2014 13:01:59 -0400

Hi Watson:

I do not understand your statement below: the cost of "decompressing" 
points may be not that insignificant and, depending on application, one 
might rather send uncompressed points instead.

For simplicity, let us assume a short-Weierstrass curve E with defining 
equation y^2 = x^3 + a x + b (mod p). (A similar argument holds for 
other curves, of course.)

If one receives an uncompressed alleged point R:=(x,y), one has to check 
whether this is indeed on the curve E. This comes roughly at cost 2S+1M 
(where S=squaring; M=multiply).
If one receives a compressed point R':=(x,y') and requires the 
corresponding uncompressed point R, one has to compute a solution y to 
the equation y^2=alpha, where alpha:=x^3+ax+b (mod p) and (if there is a 
solution) pick y or p-y, depending on the binary value y'. This comes at 
roughly cost 1S + 1M+1SQRT (where SQRT=square root).

The trade-off here is that point compression slightly saves on 
communication bandwidth, whereas it does increase computational cost of 
scalar multiplies.
{Rough ballpark for 256-bit curve: 64 octet uncompressed point vs. 32 
octet compressed point; curve check uncompressed point roughly <0.2% 
cost scalar multiply vs. ~10% cost scalar multiply (based on figures I 
have seen floating around on the cfrg mailing list).}

Your suggested "security concern" seems to be that implementers will 
somehow not perform the curve check (why?) and that, by using point 
compression, you simply enforce it indirectly (since recomputing the 
uncompressed point from the compressed one includes checking whether the 
x-value is indeed the x-coordinate of a possible curve point). For 
implementers that *do* perform the curve check and do care more about 
performance than about the 32-octet communication savings, this would 
present a disadvantage.

The only case where the latter does not incur such a large performance 
hit seems to be in cases where scalar multiplication does not use the 
y-coordinate at all (since then one does not care about y' and simply 
sees whether alpha is a quadratic residue). This does however restrict 
implementation freedom.

If one were to be concerned about implementation attacks, why not have 
people compute a compressed point R':=(x,y') from a received 
uncompressed point R:=(x,y) {this simply requires taking y':=y (mod 2), 
i.e., determining the parity of y} and then do as you suggested.

Using uncompressed points gives people two mechanisms for preventing 
invalid point attacks (via curve check or point decompression), at 
slightly higher communication cost (32 octets) that seems easy to accept 
in most TLS applications. Allowing freedom to choose either format gives 
people choice, also on communication cost side, at trivial cost of 
having a single octet indicator.

This leads us back to the representation formats we currently have.

Best regards, Rene

==
Yes, but uncompressed points are not a security concern in X509, but 
they are in ECDH. Furthermore, the cost of adding compression support is 
very small: it's a square root, a check, and potentially flipping the 
sign. The benefit is that invalid point attacks are much harder to carry 
out.

On 10/22/2014 12:11 PM, Watson Ladd wrote:
>
> On Tue, Oct 21, 2014 at 8:11 AM, Michael StJohns 
> <[email-masked] <mailto:[email-masked]>> wrote:
> > There's a very large body of code that doesn't support anything 
> except type
> > points in X509 certificates as a regular thing prior to about 10 
> years from
> > now as very small, meaning that any general transition to EC based 
> suites is
> Yes, but uncompressed points are not a security concern in X509, but 
> they are in ECDH. Furthermore, the cost of adding compression support 
> is very small: it's a square root, a check, and potentially flipping 
> the sign. The benefit is that invalid point attacks are much harder to 
> carry out.
>
> >
> worrisome
> > that is, but its one of the reasons that binary curves aren't in 
> broader use
> > still.
> >
> > Just my $.02
> >
> > Mike
> >
> >
> >
> > [email-masked] <mailto:[email-masked]>
> > [email-masked] <mailto:[email-masked]>
> "Those who would give up Essential Liberty to purchase a little 
> Temporary Safety deserve neither Liberty nor Safety."
> -- Benjamin Franklin
>
>
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Andrei Popov <[email-masked]>
Date: Wed, 22 Oct 2014 18:15:11 +0000

A few considerations:

-          The “IPR has expired” statement will require legal validation before an implementer can bake point compression into products;

-          Fewer bytes on the wire/more CPU is a good tradeoff in some scenarios, but probably not in every scenario;

-          Requiring support for point compression imposes additional (even if relatively minor, in the scale of things) cost for TLS1.3 implementers.

What are the reasons for getting rid of uncompressed points?

Cheers,

Andrei

From: TLS [mailto:[email-masked]] On Behalf Of Eric Rescorla
Sent: Tuesday, October 21, 2014 7:52 AM
To: [email-masked]
Subject: [TLS] Should we require compressed points

What do people think?
-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 22 Oct 2014 20:26:15 +0200

On Wed, Oct 22, 2014 at 8:15 PM, Andrei Popov <[email-masked]>
wrote:

>  A few considerations:
>
> -          The “IPR has expired” statement will require legal validation
> before an implementer can bake point compression into products;
>
> -          Fewer bytes on the wire/more CPU is a good tradeoff in some
> scenarios, but probably not in every scenario;
>
> -          Requiring support for point compression imposes additional
> (even if relatively minor, in the scale of things) cost for TLS1.3
> implementers.
>
>
>
Really what I want is to get rid of point negotiation, because it's yet
another
point of complexity and it's not universally implemented anyway. Given that
people seem to think that compressed points are better, I figured that was
the way to go. If people prefer to just require uncompressed points (at
least for the existing X9.63 curves) I could certainly live with that.

-Ekr

 Cheers,
>
>
>
> Andrei
>
>
>
> *From:* TLS [mailto:[email-masked]] *On Behalf Of *Eric Rescorla
> *Sent:* Tuesday, October 21, 2014 7:52 AM
> *To:* [email-masked]
> *Subject:* [TLS] Should we require compressed points
>
>
>

---

From: Martin Thomson <[email-masked]>
Date: Wed, 22 Oct 2014 11:47:08 -0700

> least for the existing X9.63 curves) I could certainly live with that.

Yep, and I'll note that 32 octets isn't a trivial amount of space in a
handshake.  We're particularly space constrained here.  If that's 32
octets more of application data I'd have available, I suspect that
another compressed HTTP/2 request - or a good proportion of one -
could fit in that space (for a 0 RTT mode in particular).

---

From: Watson Ladd <[email-masked]>
Date: Wed, 22 Oct 2014 11:52:48 -0700

> For simplicity, let us assume a short-Weierstrass curve E with defining
equation y^2 = x^3 + a x + b (mod p). (A similar argument holds for other
curves, of course.)
> If one receives a compressed point R':=(x,y') and requires the
corresponding uncompressed point R, one has to compute a solution y to the
equation y^2=alpha, where alpha:=x^3+ax+b (mod p) and (if there is a
solution) pick y or p-y, depending on the binary value y'. This comes at
roughly cost 1S + 1M+1SQRT (where SQRT=square root).
> {Rough ballpark for 256-bit curve: 64 octet uncompressed point vs. 32
octet compressed point; curve check uncompressed point roughly <0.2% cost
scalar multiply vs. ~10% cost scalar multiply (based on figures I have seen
floating around on the cfrg mailing list).}

Ask Bouncycastle, Apple, and Go why they don't do this check. (Bouncycastle
fixed it). The fact is implementations are exploitable as a result of
taking shortcuts not revealed in ordinary testing.

Furthermore, x coordinate only is adequate for ECDH and was suggested in
the original ECC paper.

hit seems to be in cases where scalar multiplication does not use the
y-coordinate at all (since then one does not care about y' and simply sees
whether alpha is a quadratic residue). This does however restrict
implementation freedom.

Brier - Joyce is also slower then table based fixed window methods.
Furthermore,  not all curves in TLS are twist secure.
> If one were to be concerned about implementation attacks, why not have
people compute a compressed point R':=(x,y') from a received uncompressed
point R:=(x,y) {this simply requires taking y':=y (mod 2), i.e.,
determining the parity of y} and then do as you suggested.

They could validate the received point instead. Why decompress when you
don't have to?
> Using uncompressed points gives people two mechanisms for preventing
invalid point attacks (via curve check or point decompression), at slightly
higher communication cost (32 octets) that seems easy to accept in most TLS
applications. Allowing freedom to choose either format gives people choice,
also on communication cost side, at trivial cost of having a single octet
indicator.
type
necessarily a
compressed
from
suites is
they are in ECDH. Furthermore, the cost of adding compression support is
very small: it's a square root, a check, and potentially flipping the sign.
The benefit is that invalid point attacks are much harder to carry out.
>> > Lastly, while the base IPR for point compression seems to be no longer
of
worrisome
broader use

---

From: Andrei Popov <[email-masked]>
Date: Wed, 22 Oct 2014 19:39:25 +0000

I'm not convinced that a requirement to support multiple point compression algorithms helps eliminate complexity:).

Point compression does help save a bit of space, so that we can carry more of those lovely human-readable ALPN IDs. I agree that point compression may be a valuable feature.

While I would prefer to keep uncompressed points, this would not be a deal-breaker for me. Losing support for renegotiation concerns me much more.

Cheers,

Andrei

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Wednesday, October 22, 2014 11:47 AM
To: Eric Rescorla
Cc: Andrei Popov; [email-masked]
Subject: Re: [TLS] Should we require compressed points

On 22 October 2014 11:26, Eric Rescorla <[email-masked]> wrote:
> Really what I want is to get rid of point negotiation, because it's 
> yet another point of complexity and it's not universally implemented 
> anyway. Given that people seem to think that compressed points are 
> better, I figured that was the way to go. If people prefer to just 
> require uncompressed points (at least for the existing X9.63 curves) I 
> could certainly live with that.

Yep, and I'll note that 32 octets isn't a trivial amount of space in a handshake.  We're particularly space constrained here.  If that's 32 octets more of application data I'd have available, I suspect that another compressed HTTP/2 request - or a good proportion of one - could fit in that space (for a 0 RTT mode in particular).

---

From: Rene Struik <[email-masked]>
Date: Wed, 22 Oct 2014 16:24:20 -0400

Hi Watson:

Your argument seems to be biased towards x-coordinate only calculations. 
There may very well be good reasons for implementations using the 
y-coordinate of a received point in their implementation as well, in 
which case forcing those to incur a ~10% of scalar multiply performance 
hit by offering only compressed objects seems to be somewhat brutal.

Best regards, Rene

On 10/22/2014 2:52 PM, Watson Ladd wrote:
>
>
> On Oct 22, 2014 10:02 AM, "Rene Struik" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> > Hi Watson:
> >
> > I do not understand your statement below: the cost of 
> "decompressing" points may be not that insignificant and, depending on 
> application, one might rather send uncompressed points instead.
> >
> > For simplicity, let us assume a short-Weierstrass curve E with 
> defining equation y^2 = x^3 + a x + b (mod p). (A similar argument 
> holds for other curves, of course.)
> >
> > If one receives an uncompressed alleged point R:=(x,y), one has to 
> check whether this is indeed on the curve E. This comes roughly at 
> cost 2S+1M (where S=squaring; M=multiply).
> the equation y^2=alpha, where alpha:=x^3+ax+b (mod p) and (if there is 
> a solution) pick y or p-y, depending on the binary value y'. This 
> comes at roughly cost 1S + 1M+1SQRT (where SQRT=square root).
> >
> communication bandwidth, whereas it does increase computational cost 
> of scalar multiplies.
> > {Rough ballpark for 256-bit curve: 64 octet uncompressed point vs. 
> 32 octet compressed point; curve check uncompressed point roughly 
> <0.2% cost scalar multiply vs. ~10% cost scalar multiply (based on 
> figures I have seen floating around on the cfrg mailing list).}
> >
> uncompressed point from the compressed one includes checking whether 
> the x-value is indeed the x-coordinate of a possible curve point). For 
> Ask Bouncycastle, Apple, and Go why they don't do this check. 
> (Bouncycastle fixed it). The fact is implementations are exploitable 
> as a result of taking shortcuts not revealed in ordinary testing.
>
> Furthermore, x coordinate only is adequate for ECDH and was suggested 
> in the original ECC paper.
>
> >
> > The only case where the latter does not incur such a large 
> performance hit seems to be in cases where scalar multiplication does 
> not use the y-coordinate at all (since then one does not care about y' 
> and simply sees whether alpha is a quadratic residue). This does 
> however restrict implementation freedom.
>
> > If one were to be concerned about implementation attacks, why not 
> have people compute a compressed point R':=(x,y') from a received 
> uncompressed point R:=(x,y) {this simply requires taking y':=y (mod 
> 2), i.e., determining the parity of y} and then do as you suggested.
>
> They could validate the received point instead. Why decompress when 
> you don't have to?
> >
> slightly higher communication cost (32 octets) that seems easy to 
> accept in most TLS applications. Allowing freedom to choose either 
> format gives people choice, also on communication cost side, at 
> trivial cost of having a single octet indicator.
> >
> >> > now as very small, meaning that any general transition to EC 
> based suites is
> >> Yes, but uncompressed points are not a security concern in X509, 
> but they are in ECDH. Furthermore, the cost of adding compression 
> support is very small: it's a square root, a check, and potentially 
> flipping the sign. The benefit is that invalid point attacks are much 
> harder to carry out.
> >>
> >> >
> > email: [email-masked] <mailto:[email-masked]> | Skype: 
> rstruik

---

From: Jeffrey Walton <[email-masked]>
Date: Wed, 22 Oct 2014 16:33:38 -0400

> before an implementer can bake point compression into products;
Possible related: http://cr.yp.to/patents/us/6141420.html. The 420
patent expired in July 2014.

On Wed, Oct 22, 2014 at 2:15 PM, Andrei Popov
<[email-masked]> wrote:
> -          Requiring support for point compression imposes additional (even
> if relatively minor, in the scale of things) cost for TLS1.3 implementers.
>
>

---

From: Bodo Moeller <[email-masked]>
Date: Tue, 28 Oct 2014 11:49:16 +0100

Eric Rescorla <[email-masked]>:

> least for the existing X9.63 curves) I could certainly live with that.

RFC 4492 requires support for uncompressed format (and uncompressed format
is assumed if the supported point formats extension is omitted), so
switching to compressed format for the existing curves in the next protocol
version appears to be asking for trouble.

Deprecating the supported point formats extension isn't a bad idea, but
then if we want to support compressed format for some of the current
curves, the right way to do that would be to define new NamedCurve values
for these.

Bodo