Re: [TLS] Should we require compressed points

[Watson Ladd <[e-mail]>]

On Oct 22, 2014 10:02 AM, "Rene Struik" <[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]>
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]
>> > https://www.ietf.org/mailman/listinfo/tls
>> >
>> >
>> >
>> > _______________________________________________
>> > TLS mailing list
>> > [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]