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

Sat Jul 30 10:25:25 UTC 2016

Ticket submitted by 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.

[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);

    [...]
}
```

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