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

[Brian Smith via RT]

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



-- 
https://briansmith.org/


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