Re: [Cfrg] invalid compressed point attack ...

[David Jacobson <[e-mail]>]

On 11/27/14, 7:38 PM, David Jacobson wrote:
> On 11/27/14, 10:33 AM, Dan Brown wrote:
>> 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.
> You seem to be saying that using y = z^((p+1)/4) where z is computed 
> from x using the curve equation, i.e. for short Weierstrass z = x^2 + 
> a * x + b, is not a valid way of computing a valid (x,y) on the 
> curve.  Well, of course, it is possible that z is not a quadratic 
> residue.  But if you check that y^2 == z, is it still unsafe?
>
> Thank you,
>
>     --David
That was supposed to be z = y^3  + a * x + b.  Sorry for the typo. One 
always sees the mistake 3 seconds after clicking "send".

    --David