[Cfrg] invalid compressed point attack ...

[Dan Brown <[e-mail]>]

I don't know if the compressed version of the invalid-point attack is common 
knowledge - or whether people would think it is unrealistic - or even whether 
there is some drastic error in it.  If so, then sorry for stating the obvious, 
and just skip reading the rest of this message.

>From: Watson Ladd
>Sent: Wednesday, October 22, 2014 12:11 PM
>Cc: [e-mail]
>Subject: Re: [TLS] Should we require compressed points

>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.

Minor clarification on the "much harder" part: there is a technical attack 
when invalid compressed points are "used" (as defined below).

I assume short Weierstrass form, but some of this may extend to other curve 
forms.

Review: An uncompressed point (x,y) is invalid if it fails a simple check.
In an invalid point attack, a user applies the secret key to an invalid point 
using certain addition laws, and scalar multiplication algorithms, that have 
an action on uncompressed points that corresponds to the equivalent action on 
another curve in which the invalid point has low order.

Definitions: A compressed point (x,z) is invalid if it is not the compression 
of a valid uncompressed point.
We can technically define an invalid point attack for compression by 
specifying an invalid decompression rule for invalid compressed points.
For example, in prime fields of size p = 3 mod 4, the function z |-> 
z^((p+1)/4) can be used to decompress invalid compressed points, in the place 
where actual square root algorithm is used to decompress a valid compressed 
point.

To me, this invalid decompression rule seems as plausible an implementation 
fault as the fault of not checking for curve membership of an uncompressed 
point.
In fact, a user might reason that an attacker's only approach with compressed 
points is to try random compressed points (x,z) until they have low order.
Under the heuristic that random compressed (x,z) usually have random large 
orders upon invalid decompression, the user might then think it is infeasible 
to find such points, and therefore it is safe to use invalid decompression 
(e.g. saving the error-handling etc.)

Well, here is an invalid compressed point, which on curve NIST P192 
decompresses to invalid uncompressed point of order 11:

02 2f 8c 8c 8a 7c b1 1c 06 aa a3 4b 23 4f 7d 88 cd b9 9f d7 66 4a 00 a4 d7

I presented this point and a method (using division polynomials) to find such 
points in the slides at PKC 2003 (which I almost completely forgot about!).
This method certainly has an additional pre-computation cost, compared to the 
uncompressed invalid-point attack, but I don't think it's too costly.
After that initial cost, the attack is pretty much the same as the one on 
uncompressed points.

Best regards,

Dan