[openssl-dev] Are the point-at-infinity checks in ecp_nistz256 correct?

[Brian Smith]

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/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20160708/35e38df9/attachment.html>