possible C bugs in ecp_nistp521

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

possible C bugs in ecp_nistp521

Bo-Yin Yang
Dear all,

we found some counter-examples (examples where wrong answers were
returned) for field element computations in the C routines for P-521
(that is, modulo 2^521-1).   The counterexamples, a C test file, a
Makefile, and a short README are attached.

The routines in question are: felem_square, felem_mul, felem_diff_128_64.

Can someone inform us whether these are in fact a couple of bugs that we
found, or did we miss something.

Best wishes,
Bo-Yin Yang


P.S.

The counterexamples are:

- for felem_square and felem_mul:
   felem in = {
     0x3fd9049d07fdc0ad, 0x3ece5f4000000000, 0x39c5349d6a623811,
     0x3bf48f8409415499, 0x3ffdac80c8300000, 0x3ff3f3de63be6baf,
     0x3fa3eff5c6db1743, 0x3dde8d0ddc21079f, 0x3e068b5ec961f8fc
   };

- for felem_diff_128_64:
   largefelem out = {
     0,0,0,
     0,0,0,
     0,0,0
   };
   felem in = {
     0x4000000000012270, 0x1000000000000000, 0x0010000000000000,
     0x0400000000000000, 0x0800000000000000, 0x0020000000000000,
     0x0000000040000000, 0x0002000000000000, 0x0000000400000000
   };

-- B.Y.


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

Makefile (352 bytes) Download Attachment
check.c (14K) Download Attachment
README (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: possible C bugs in ecp_nistp521

Patrick Steuer
Dear Bo-Yin Yang,

I looked into your felem_square counterexample:

There is an overflow in the result's least significant 128-bit limb such
that the computed result is 2^128 smaller than the actual result.

The general problem is the following..

The function's comment says:
/*-
  * felem_square sets |out| = |in|^2
  * On entry:
  *   in[i] < 2^62
  * On exit:
  *   out[i] < 17 * max(in[i]) * max(in[i])
  */

If you look at the function's code youll notice that given the entry
assumption, the exit assertion's "less than" should actually be a
"less than or equal to" for in the case of all in[i]s being equal to say
x, max(in[i])=x and out[0]=17*x^2.

So out[0] is stored in 128-bits, but for e.g. x=2^62-1, out[0]>2^128.

If its a bug depends on the contexts from which felem_square is called.
If for some reason its inputs are guaranteed to satisfy some stricter
entry condition than stated in the above comment (such that there is no
overflow) things might be alright.

I didnt look at your other examples but id expect something similar.

Best Regards,

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

Re: possible C bugs in ecp_nistp521

Kyle Hamilton
I would expect that correct results would be provided for all valid
inputs (including those inputs that are not otherwise constrained).
As such, I would class this as a bug in OpenSSL.

-Kyle H

On Mon, Jan 7, 2019 at 7:44 PM Patrick Steuer <[hidden email]> wrote:

>
> Dear Bo-Yin Yang,
>
> I looked into your felem_square counterexample:
>
> There is an overflow in the result's least significant 128-bit limb such
> that the computed result is 2^128 smaller than the actual result.
>
> The general problem is the following..
>
> The function's comment says:
> /*-
>   * felem_square sets |out| = |in|^2
>   * On entry:
>   *   in[i] < 2^62
>   * On exit:
>   *   out[i] < 17 * max(in[i]) * max(in[i])
>   */
>
> If you look at the function's code youll notice that given the entry
> assumption, the exit assertion's "less than" should actually be a
> "less than or equal to" for in the case of all in[i]s being equal to say
> x, max(in[i])=x and out[0]=17*x^2.
>
> So out[0] is stored in 128-bits, but for e.g. x=2^62-1, out[0]>2^128.
>
> If its a bug depends on the contexts from which felem_square is called.
> If for some reason its inputs are guaranteed to satisfy some stricter
> entry condition than stated in the above comment (such that there is no
> overflow) things might be alright.
>
> I didnt look at your other examples but id expect something similar.
>
> Best Regards,
>
> Patrick Steuer
> --
> openssl-users mailing list
> To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users
Reply | Threaded
Open this post in threaded view
|

Re: possible C bugs in ecp_nistp521

Billy Brumley
> I would expect that correct results would be provided for all valid
> inputs (including those inputs that are not otherwise constrained).
> As such, I would class this as a bug in OpenSSL.

These functions are not part of the public OpenSSL API so that's just
not how it works. There is a ton of internal code across the library
that makes assumptions about the inputs, e.g. in this case the
internal caller using some non-trivial representation that somehow
bounds limbs.

In this instance, I suspect Patrick's statement is valid -- hopefully
it's just a documentation typo and the bounds are tighter.

In any case, this (and any other might-be arithmetic bug) is
potentially a security issue so it shouldn't be discussed on a public
mailing list.

BBB
--
openssl-users mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-users