[openssl-dev] [openssl.org #4636] Re: [openssl.org #4625] Re: Are the point-at-infinity checks in ecp_nistz256 correct?

[Andy Polyakov via RT]

Consider attached diff.

> The issue is particularly clear when we multiply the generator by
> zero. Note that in general, an application shouldn't multiply the
> generator by zero since there's no useful cryptographic purpose for
> doing so. But, this is a convenient example.
> 
> In the code we have,
> 
>     ecp_nistz256_gather_w7(&p.a, preComputedTable[0], wvalue >> 1);
>     ecp_nistz256_neg(p.p.Z, p.p.Y);
>     copy_conditional(p.p.Y, p.p.Z, wvalue & 1);
>     memcpy(p.p.Z, ONE, sizeof(ONE));
> 
> The generator is all zeros, so we'll start off with the point (0, 0,
> 1). Then we add the point at infinity over and over again, leaving
> that point unchanged each time. Thus, we'll end with (0, 0, 1). Then:
> 
>     r->Z_is_one = is_one(p.p.Z) & 1;
> 
> Thus, the resulting point will be (0, 0, 1).
> 
> After the memcpy quoted above, we need to do a copy_conditional(p.p.Z,
> is_infinity, ZERO) or equivalent, where ZERO is all-zeros and where
> is_infinity is the result of checking if (x, y) == (0, 0).
> 
> This is just one example of an edge case that is handled in a
> surprising way. I think there are more, as described in the quoted
> message below.
> 
> Cheers,
> Brian
> 
> 
> Brian Smith <brian at briansmith.org> wrote:
>>
>> Brian Smith <brian at briansmith.org> wrote:
>>>
>>> When doing math on short Weierstrass curves like P-256, we have to
>>> special case points at infinity. In Jacobian coordinates (X, Y, Z),
>>> points at infinity have Z == 0. However, instead of checking for Z ==
>>> 0, p256-x86-64 instead checks for (X, Y) == (0, 0). In other words, it
>>> does, in some sense, the opposite of what I expect it to do.
>>
>>
>> I exchanged email with both of the original authors of the code, Shay and Vlad. He that the ecp_nistz256_point_* functions indeed intend to represent the point at infinity as (0, 0) and it is expected (but I did not verify) that those functions should work when the point at infinity is encoded as (0, 0, _).
>>
>>> The authors
>>> instead decided to encode the point at infinity as (0, 0), since the
>>> affine point (0, 0) isn't on the P-256 curve. It isn't clear why the
>>> authors chose to do that though, since the point at infinity doesn't
>>> (can't, logically) appear in the table of precomputed multiples of G
>>> anyway.
>>
>>
>> Actually, as the code says, the point at infinity implicitly occurs in the table implicitly. Obviously the accumulator point will be at infinity until at least a one bit is found in the scalar.
>>
>>>
>>> But, it seems like the functions that do the computations, like
>>>
>>> ecp_nistz256_point_add and ecp_nistz256_point_add_affine, output the
>>> point at infinity as (_, _, 0), not necessarily (0, 0, _). Also,
>>> ecp_nistz256's EC_METHOD uses ec_GFp_simple_is_at_infinity and
>>> ec_GFp_simple_point_set_to_infinity, which represent the point at
>>> infinity with z == 0, not (x, y) == 0. Further ecp_nistz256_get_affine
>>> uses EC_POINT_is_at_infinity, which checks z == 0, not (x, y) == 0.
>>> This inconsistency is confusing, if not wrong. Given this, it seems
>>> like the point-at-infinity checks in the ecp_nistz256_point_add and
>>> ecp_nistz256_point_add_affine code should also be checking that z == 0
>>> instead of (x, y) == (0, 0).
>>
>>
>> Instead, when we convert a point from EC_POINT to P256_POINT or P256_POINT_AFFINE, we should translate the (_, _, 0) form into the (0, 0, 0) form. And/or reject points at infinity as inputs to the function. Similarly, when we convert the resultant P256_POINT to an EC_POINT, we chould translate the (0, 0) encoding of the point at infinity to the (0, 0, 0) form or at least the (_, _, 0) form.
>>
>> In particular, consider the case where you have an EC_POINT that isn't at infinity, e.g. (x, y, 1). Then you call EC_POINT_set_to_infinity on it. Then it is (x, y, 0). Then you pass it to EC_POINT_mul/EC_POINTs_mul even though you shouldn't.
>>
>> Maybe the precondition of EC_POINT_mul/EC_POINTs_mul is that none of the input points are at infinity, in which case it doesn't matter. (But if so, maybe these functions should do a point-at-infinity check.) But if it is allowed to pass in the point at infinity, then the ecp_nistz256 code should translate the input point from (_, _, 0) form to (0, 0, _) form before doing the computation. It can use is_zero and copy_conditional and friends to do this.
>>
>> Similarly, after the computation, it should translate the (0, 0, _) form to (_, _, 0) form. In particular, it should do such a translation before the code sets Z_is_one, AFAICT. Note that the nistz256 code might be using the form (0, 0, 0) instead of (0, 0, _) in which case this translation might not be necessary.
>>
>> Regardless, it would be useful to write tests for these cases:
>> 1. Verify that the result is correct when any of the input points are (0, 0, 0)
>> 2. Verify that the result is correct when any of the input points are (_, _, 0).
>> 3. Verify that the result is correct, and in particular that Z_is_one is set correctly on the result, when the final result is at infinity, especially for the cases where neither the input points are at infinity, e.g. when adding (n-1)G to 1G.
>>
>> Note that all of the above cases have interesting sub-cases: the G scalar is NULL, the G scalar is non-NULL and zero-valued, G scalar is a multiple of G, G scalar is larger than G. And same for the P scalars.
>>
>> Cheers,
>> Brian
>> --
>> https://briansmith.org/
>>
> 
> 
> 


-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4636
Please log in as guest with password guest if prompted

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-ec-ecp_nistz256-harmonize-is_infinity-with-ec_GFp_si.patch
Type: text/x-patch
Size: 6393 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20160821/1e04b8d6/attachment.bin>