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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Rich Salz via RT
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
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Billy Brumley
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 <[hidden email]> 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
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Rich Salz 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 <[hidden email]> 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


_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Rich Salz via RT
Hi,

Thanks! Verify attached diff.



_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

RT4284.diff (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Billy Brumley
> Thanks! Verify attached diff.

Without looking too closely at the asm, at least the output now looks OK to me:

Input point: P
ad4cfe7307736330 5a390846abdb19e5 bc92e079b12de03f 3a6b3ebcbf24755d
5ed0dbce609dcf3b 091a794357eca9ee acb4d5512ea7232f 09d787c5915c070a
d482c016856ed40a 4a9e64127c9216d7 308267a3a3c72f6c 99a4ef25b90c6499
after ecp_nistz256_point_add(A, P, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b
after ecp_nistz256_point_double(B, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b

I will say that I don't understand how ecp_nistz256_point_add_affine
does not have these conditions. Maybe that's a question for the
original authors.

BBB
_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Rich Salz via RT
> Thanks! Verify attached diff.

Without looking too closely at the asm, at least the output now looks OK to me:

Input point: P
ad4cfe7307736330 5a390846abdb19e5 bc92e079b12de03f 3a6b3ebcbf24755d
5ed0dbce609dcf3b 091a794357eca9ee acb4d5512ea7232f 09d787c5915c070a
d482c016856ed40a 4a9e64127c9216d7 308267a3a3c72f6c 99a4ef25b90c6499
after ecp_nistz256_point_add(A, P, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b
after ecp_nistz256_point_double(B, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b

I will say that I don't understand how ecp_nistz256_point_add_affine
does not have these conditions. Maybe that's a question for the
original authors.

BBB


_______________________________________________
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Jun Sun
Hi Billy,
Thank you very much for verify the bug!

The reason ecp_nistz256_point_add_affine is not affected is that this function is only used when a scalar is multiplying the generator point G. In this case, a big pre-computed table is used with a 7 bit window size for all fixed window positions (that is why the table has 37x64 entries and you do not see a point doubling function called there). So at the point when ecp_nistz256_point_add_affine is called, p.p is holding the accumulated previous window scalar data (lower bits of scalar) by G, and t.a is holding the current window scalar value by G, they will never meet each other. So inside ecp_nistz256_point_add_affine, no logic to check for doubling.


Jun Sun

________________________________________
From: Billy Brumley via RT <[hidden email]>
Sent: February 3, 2016 6:05 AM
To: Jun Sun
Cc: [hidden email]
Subject: Re: [openssl-dev] [openssl.org #4284] Bug in nistz256 assembly code.

> Thanks! Verify attached diff.

Without looking too closely at the asm, at least the output now looks OK to me:

Input point: P
ad4cfe7307736330 5a390846abdb19e5 bc92e079b12de03f 3a6b3ebcbf24755d
5ed0dbce609dcf3b 091a794357eca9ee acb4d5512ea7232f 09d787c5915c070a
d482c016856ed40a 4a9e64127c9216d7 308267a3a3c72f6c 99a4ef25b90c6499
after ecp_nistz256_point_add(A, P, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b
after ecp_nistz256_point_double(B, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b

I will say that I don't understand how ecp_nistz256_point_add_affine
does not have these conditions. Maybe that's a question for the
original authors.

BBB


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
Reply | Threaded
Open this post in threaded view
|

Re: [openssl.org #4284] Bug in nistz256 assembly code.

Rich Salz via RT
Hi Billy,
Thank you very much for verify the bug!

The reason ecp_nistz256_point_add_affine is not affected is that this function is only used when a scalar is multiplying the generator point G. In this case, a big pre-computed table is used with a 7 bit window size for all fixed window positions (that is why the table has 37x64 entries and you do not see a point doubling function called there). So at the point when ecp_nistz256_point_add_affine is called, p.p is holding the accumulated previous window scalar data (lower bits of scalar) by G, and t.a is holding the current window scalar value by G, they will never meet each other. So inside ecp_nistz256_point_add_affine, no logic to check for doubling.


Jun Sun

________________________________________
From: Billy Brumley via RT <[hidden email]>
Sent: February 3, 2016 6:05 AM
To: Jun Sun
Cc: [hidden email]
Subject: Re: [openssl-dev] [openssl.org #4284] Bug in nistz256 assembly code.

> Thanks! Verify attached diff.

Without looking too closely at the asm, at least the output now looks OK to me:

Input point: P
ad4cfe7307736330 5a390846abdb19e5 bc92e079b12de03f 3a6b3ebcbf24755d
5ed0dbce609dcf3b 091a794357eca9ee acb4d5512ea7232f 09d787c5915c070a
d482c016856ed40a 4a9e64127c9216d7 308267a3a3c72f6c 99a4ef25b90c6499
after ecp_nistz256_point_add(A, P, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b
after ecp_nistz256_point_double(B, P)
52d422c756922166 033fb71af0fd3251 b38e0f88b5a2b2a4 bd964cc28ad2bf39
61c01cf1c0a9b7f9 5acaf8aa07f449fc 62b8600cf22cec6b ab80a212e72fb53d
b4a67dfe55eb1133 ec19e9f97640f280 1a3caeebc962ab48 19a5d850b22fa55b

I will say that I don't understand how ecp_nistz256_point_add_affine
does not have these conditions. Maybe that's a question for the
original authors.

BBB


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