Re: [TLS] Should we require compressed points

[Rene Struik <[e-mail]>]

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 
> <[e-mail] <mailto:[e-mail]>> wrote:
> > On 10/21/2014 10:52 AM, Eric Rescorla wrote:
> >
> > 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
> >
> >
> > 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?).
>
> 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.
> >
> > Just my $.02
> >
> > Mike
> >
> >
> >
> > 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
> >
> >
> >
> >
> >
> >
> >
> > _______________________________________________
> > TLS mailing list
> > [e-mail] <mailto:[e-mail]>
> > https://www.ietf.org/mailman/listinfo/tls
> >
> >
> >
> > _______________________________________________
> > TLS mailing list
> > [e-mail] <mailto:[e-mail]>
> > 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
>
>
>
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]