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. 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); [...] } ``` -- Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4636 Please log in as guest with password guest if prompted -- openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
