[openssl-dev] [openssl.org #4284] Bug in nistz256 assembly code.

[Billy Brumley via RT]

I verified this bug. At least, I think so.

Input point: P
88c38b77f62c7646 8761482ed66be7ec e29c7ff650f1ad3d a075da5d50ae8d0f
7aecc07d9b4b9a78 11c14dd2ab2cc516 e11dc6d90097e6b6 0ccfcffded344d8c
5723476edeccc439 0ad224b227c5b4e8 c2f7280137f60ac6 c97c65b4fe0fa310
after ecp_nistz256_point_add(A, P, P)
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
after ecp_nistz256_point_double(B, P)
5dc647edcf585e47 8a1234279b722778 d1fe20832426c68a 8854b03358f4812f
fe8c5c9008a694e5 5187b8b82213bc83 0c1da0ab8aced06c cc08ba7a7c7c7474
88cc2b97e5151f2f fe3275dcd154755a e98898ead6ffac57 282dd53b1eea1cf2

Basically the asm degenerates to

 337     if (is_equal(U1, U2) && !in1infty && !in2infty) {
 342             memset(r, 0, sizeof(*r));
 343             return;
 345     }

Since the subsequent (after jz branch taken) point_add arithmetic
causes everything to zero out, so you're left with the point at
infinity.

Note that ecp_nistz256_point_add adds two projective points, so it
doesn't get called for all EC_POINT_mul code paths.

BBB

On Mon, Feb 1, 2016 at 9:59 PM, Jun Sun via RT <rt at openssl.org> wrote:
> Hi openssl team,
>
> In function ecp_nistz256_point_add (in ecp_nistz256.c), in the case when U1 == U2 and S1 == S2, in C reference code, the logic is call ecp_nistz256_point_double (line 339) to do a point double operation:
>
>
>  337     if (is_equal(U1, U2) && !in1infty && !in2infty) {
>
>  338         if (is_equal(S1, S2)) {
>
>  339             ecp_nistz256_point_double(r, a);
>
>  340             return;
>
>  341         } else {
>
>  342             memset(r, 0, sizeof(*r));
>
>  343             return;
>
>  344         }
>
>  345     }
>
>
>
>
> This is correct and follow what is described in S.Gueron and V.Krasnov's paper. But in x86_64 assembly code (ecp_nistz256-x86_64.pl), this logic is not implemented, it fall back to point adding code again:
>
>
> 2385         .byte   0x3e                            # predict taken
>
> 2386         jnz     .Ladd_proceed$x                 # is_equal(U1,U2)?
>
> 2387         movq    %xmm2, $acc0
>
> 2388         movq    %xmm3, $acc1
>
> 2389         test    $acc0, $acc0
>
> 2390         jnz     .Ladd_proceed$x                 # (in1infty || in2infty)?
>
> 2391         test    $acc1, $acc1
>
> 2392         jz      .Ladd_proceed$x                 # is_equal(S1,S2)?
>
>
>
>
> The difference be seen in the latest ectest.c for the group order tests, even though both C code and assembly code does not generate any error, but they generate different values:
>
>
>  201         scalars[0] = n1;
>
>  202         points[0] = Q;          /* => infinity */
>
>  203         scalars[1] = n2;
>
>  204         points[1] = P;          /* => -P */
>
>  205         scalars[2] = n1;
>
>  206         points[2] = Q;          /* => infinity */
>
>  207         scalars[3] = n2;
>
>  208         points[3] = Q;          /* => infinity */
>
>  209         scalars[4] = n1;
>
>  210         points[4] = P;          /* => P */
>
>  211         scalars[5] = n2;
>
>  212         points[5] = Q;          /* => infinity */
>
>  213         if (!EC_POINTs_mul(group, P, NULL, 6, points, scalars, ctx))
>
>  214             ABORT;
>
>  215         if (!EC_POINT_is_at_infinity(group, P))
>
>  216             ABORT;
>
>
> P is holding different values between C reference C code and assembly code. This should not happen if the point doubling function is called in assembly code as well.
>
>
>
> Jun Sun
>
> This email and any attachments are for the sole use of the intended recipients and may be privileged or confidential. Any distribution, printing or other use by anyone else is prohibited. If you are not an intended recipient, please contact the sender immediately, and permanently delete this email and attachments.
>
> _______________________________________________
> openssl-dev mailing list
> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev