Re: [TLS] Should we require compressed points

[Rene Struik <[e-mail]>]

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" <[e-mail] 
> <mailto:[e-mail]>> 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).
> > 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.
>
> 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.
>
> 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.
> >
> > 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] <mailto:[e-mail]>
> >> https://www.ietf.org/mailman/listinfo/tls
> >
> >
> >
> > --
> > email: [e-mail] <mailto:[e-mail]> | Skype: 
> rstruik
> > cell: [phone] | US: [phone]
>


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