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

[Brian Smith]

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 have built a testing framework for exploring things like this in
*ring*. I will attach the input file for my tests which show that
ecp_nistz256_point_add seems to fail to recognize the point at
infinity correctly. However, it is also possible that I just don't
understand how ecp_nistz256 intends to work. My questions are:

1. With respect to additions of the form (a + infinity == a) and
(infinity + b == b), is the code in ecp_nistz256_point_add and
ecp_nistz256_point_add_affine correct?

2. if it is correct, could we add more explanation as to why it is correct?

3. Given the specifics of the implementation of the ecp_nistz256
implementation, is it even possible for us to encounter the point at
infinity as one of the parameters to ecp_nistz256_point_add, other
than in the very final addition that adds g_scalar*G + p_scalar*P? See
Section 4.1 of [1].

Background: For based point (G) multiplication, the code has a large
table of multiples of G, in affine (not Jacobian) coordinates. The
point at infinity cannot be encoded in affine coordinates. 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. Regardless, if you represent the point at infinity as (0, 0)
then it makes sense to check (x, y) == (0, 0).

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

Note that this is confusing because `EC_POINT_new` followed by
`EC_POINT_to_infinity` initializes (X, Y, Z) = (0, 0, 0). Thus, the
check of (x, y) == (0, 0) "works" as well as the check z == 0. But, it
doesn't work in real-life cases where the point is infinity is
encountered during calculations, because we'll have (X, Y) != (0, 0)
but Z == 0.

The assembly language code that does this check is hard to understand
unless one is familiar with SIMD. However, the C reference
implementation that the assembly language code used as a model is easy
to understand. This code can be found in the ecp_nistz256.c file.

Note the parameters of ecp_nistz256_point_add are P256_POINT, not
P256_POINT_AFFINE, so "representation of the point at infinity as (0,
0)" doesn't make sense to me. But, that's exactly what it checks.

In ecp_nistz256_point_add_affine, it makes more sense to me, because
parameter |b| is in fact a |P256_POINT_AFFINE|. However, |a| is not a
|P256_POINT_AFFINE|, so the (x, y) == (0, 0) check doesn't make sense
to me. The x86-64 and x86 assembly language code seems to emulate this
exactly. I didn't test the ARM code, but I'd guess it is similar.

[1] https://eprint.iacr.org/2014/130.pdf (Section 4.1)

Here's the specific logic I'm talking about (which is also present in
the asm code):

```
static void ecp_nistz256_point_add(P256_POINT *r,
                                   const P256_POINT *a, const P256_POINT *b) {
    [...]

    const BN_ULONG *in1_x = a->X;
    const BN_ULONG *in1_y = a->Y;
    const BN_ULONG *in1_z = a->Z;

    const BN_ULONG *in2_x = b->X;
    const BN_ULONG *in2_y = b->Y;
    const BN_ULONG *in2_z = b->Z;

    /* We encode infinity as (0,0), which is not on the curve,
     * so it is OK. */
    in1infty = (in1_x[0] | in1_x[1] | in1_x[2] | in1_x[3] |
                in1_y[0] | in1_y[1] | in1_y[2] | in1_y[3]);
    if (P256_LIMBS == 8)
        in1infty |= (in1_x[4] | in1_x[5] | in1_x[6] | in1_x[7] |
                     in1_y[4] | in1_y[5] | in1_y[6] | in1_y[7]);

    in2infty = (in2_x[0] | in2_x[1] | in2_x[2] | in2_x[3] |
                in2_y[0] | in2_y[1] | in2_y[2] | in2_y[3]);
    if (P256_LIMBS == 8)
        in2infty |= (in2_x[4] | in2_x[5] | in2_x[6] | in2_x[7] |
                     in2_y[4] | in2_y[5] | in2_y[6] | in2_y[7]);

    [...]
}

static void ecp_nistz256_point_add_affine(P256_POINT *r,
                                          const P256_POINT *a,
                                          const P256_POINT_AFFINE *b) {
    [...]

    const BN_ULONG *in1_x = a->X;
    const BN_ULONG *in1_y = a->Y;
    const BN_ULONG *in1_z = a->Z;

    const BN_ULONG *in2_x = b->X;
    const BN_ULONG *in2_y = b->Y;

    /*
     * In affine representation we encode infty as (0,0), which is not on the
     * curve, so it is OK
     */
    in1infty = (in1_x[0] | in1_x[1] | in1_x[2] | in1_x[3] |
                in1_y[0] | in1_y[1] | in1_y[2] | in1_y[3]);
    if (P256_LIMBS == 8)
        in1infty |= (in1_x[4] | in1_x[5] | in1_x[6] | in1_x[7] |
                     in1_y[4] | in1_y[5] | in1_y[6] | in1_y[7]);

    in2infty = (in2_x[0] | in2_x[1] | in2_x[2] | in2_x[3] |
                in2_y[0] | in2_y[1] | in2_y[2] | in2_y[3]);
    if (P256_LIMBS == 8)
        in2infty |= (in2_x[4] | in2_x[5] | in2_x[6] | in2_x[7] |
                     in2_y[4] | in2_y[5] | in2_y[6] | in2_y[7]);

    in1infty = is_zero(in1infty);
    in2infty = is_zero(in2infty);

    [...]
}
```

Cheers,
Brian
-- 
https://briansmith.org/