Latest commit introduces undefined behavior in hgcd2.c
My bignum fuzzer running at OSS-Fuzz came up with this: hgcd2.c:223:42: runtime error: shift exponent 64 is too large for 64-bit type 'mp_limb_t' (aka 'unsigned long') #0 0x76a4db in div2 /src/libgmp/mpn/hgcd2.c:223:42 #1 0x769684 in __gmpn_hgcd2 /src/libgmp/mpn/hgcd2.c:372:18 #2 0x74ac55 in __gmpn_gcd /src/libgmp/mpn/gcd.c:200:11 #3 0x73c209 in __gmpz_gcd /src/libgmp/mpz/gcd.c Introduced in commit https://gmplib.org/repo/gmp/rev/f044264e2fe9 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: Latest commit introduces undefined behavior in hgcd2.c
I don't mind if you don't fix it, but technically undefined behavior can have consequences beyond the value of the involved variable. On Wed, Sep 18, 2019 at 9:20 PM Torbjörn Granlund wrote: > > Guido Vranken writes: > > My bignum fuzzer running at OSS-Fuzz came up with this: > > hgcd2.c:223:42: runtime error: shift exponent 64 is too large for > 64-bit type 'mp_limb_t' (aka 'unsigned long') > #0 0x76a4db in div2 /src/libgmp/mpn/hgcd2.c:223:42 > #1 0x769684 in __gmpn_hgcd2 /src/libgmp/mpn/hgcd2.c:372:18 > #2 0x74ac55 in __gmpn_gcd /src/libgmp/mpn/gcd.c:200:11 > #3 0x73c209 in __gmpz_gcd /src/libgmp/mpz/gcd.c > > Introduced in commit https://gmplib.org/repo/gmp/rev/f044264e2fe9 > > I think it is a false positive. The result of the shifted value is > masked when the shift count is not in range. > > (We got the same false positive from our nightly testing using gcc's > sanitized-something command-line option.) > > -- > Torbjörn > Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
Thank you, I have confirmed that your patch resolves the issue.
On Mon, Aug 29, 2022 at 10:29 AM Paul Zimmermann
wrote:
> thank you, I confirm the bug, here is a potential fix:
>
> $ diff -u mini-gmp.c.orig mini-gmp.c
> --- mini-gmp.c.orig 2022-08-29 10:28:20.700995412 +0200
> +++ mini-gmp.c 2022-08-29 10:27:36.112191428 +0200
> @@ -3060,6 +3060,7 @@
>if (en == 0)
> {
>mpz_set_ui (r, 1);
> + mpz_tdiv_r (r, r, m);
>return;
> }
>
> Paul
>
> > From: Guido Vranken
> > Date: Sun, 28 Aug 2022 16:22:40 +0200
> >
> > The following program computes 1^0 % 1:
> >
> > //#include
> > #include "mini-gmp.c"
> > #include
> >
> > #define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
> >
> > int main(void)
> > {
> > mpz_t a, b, c, res;
> > char* s = NULL;
> > /* noret */ mpz_init(a);
> > /* noret */ mpz_init(b);
> > /* noret */ mpz_init(c);
> > /* noret */ mpz_init(res);
> >
> > CF_CHECK_EQ(mpz_set_str(a, "1", 10), 0);
> > CF_CHECK_EQ(mpz_set_str(b, "0", 10), 0);
> > CF_CHECK_EQ(mpz_set_str(c, "1", 10), 0);
> > CF_CHECK_EQ(mpz_set_str(res, "0", 10), 0);
> >
> > /* noret */ mpz_powm(res, a, b, c);
> >
> > printf("%s\n", mpz_get_str(NULL, 10, res));
> > end:
> > return 0;
> > }
> >
> > The result should be 0, which is the case with regular libgmp, but with
> > mini-gmp the result is 1, and this is incorrect.
> >
> > Tested on version 6.2.1 and the latest repository checkout, with recent
> > clang and gcc, on x64 Linux.
> > ___
> > gmp-bugs mailing list
> > gmp-bugs@gmplib.org
> > https://gmplib.org/mailman/listinfo/gmp-bugs
>
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
mini-gmp mpz_powm incorrect result
The following program computes 1^0 % 1:
//#include
#include "mini-gmp.c"
#include
#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
int main(void)
{
mpz_t a, b, c, res;
char* s = NULL;
/* noret */ mpz_init(a);
/* noret */ mpz_init(b);
/* noret */ mpz_init(c);
/* noret */ mpz_init(res);
CF_CHECK_EQ(mpz_set_str(a, "1", 10), 0);
CF_CHECK_EQ(mpz_set_str(b, "0", 10), 0);
CF_CHECK_EQ(mpz_set_str(c, "1", 10), 0);
CF_CHECK_EQ(mpz_set_str(res, "0", 10), 0);
/* noret */ mpz_powm(res, a, b, c);
printf("%s\n", mpz_get_str(NULL, 10, res));
end:
return 0;
}
The result should be 0, which is the case with regular libgmp, but with
mini-gmp the result is 1, and this is incorrect.
Tested on version 6.2.1 and the latest repository checkout, with recent
clang and gcc, on x64 Linux.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_gcdext Bézout coefficients do not match documentation
I've confirmed with my fuzzer that the committed patch resolves the issues. Thanks. On Sun, Feb 18, 2024 at 8:27 PM Niels Möller wrote: > marco.bodr...@tutanota.com writes: > > > The only reason why I prefer my solution is: when cmp<0, there is no > need to compute > > mpz_sub (t1, t0, t1); > > That's certainly a micro optimization, but let's keep things simple. > > I've pushed this fix now, I think there were only comment and ChangeLog > changes since the previous version of the patch. > > Thanks for the review, > /Niels > > -- > Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. > Internet email is subject to wholesale government surveillance. > ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
mini-gmp mpz_gcdext Bézout coefficients do not match documentation
Computing extended gcd using mpz_gcdext where a = 1, b = 2:
libgmp: g: 1, s: 1, t: 0
mini-gmp: g: 1, s: -1, t: 1
This violates the docs: "s = sgn(a) if abs(b) = 2", e.g. s must be 1
Computing extended gcd using mpz_gcdext where a = 6, b = 4:
libgmp: g: 2, s: 1, t: -1
mini-libgmp: g: 2, s: -1, t: 2
The docs state: "abs(s) < abs(b) / (2 g) and abs(t) < abs(a) / (2 g)"
I think that should be: "abs(s) <= abs(b) / (2 g) and abs(t) <= abs(a) / (2
g)"
(< should be <=)
Then, for libgmp this is true: s: 1 <= 4 / 4, t: 1 <= 6 / 4
For mini-gmp this is false for t: s: 1 <= 4 / 4, t: 2 <= 6 / 4
Reproducer:
//#include
#include "mini-gmp.c"
#include
static void test(
const unsigned long int a_ui,
const unsigned long int b_ui)
{
mpz_t a, b, g, s, t;
mpz_init(a);
mpz_init(b);
mpz_init(g);
mpz_init(s);
mpz_init(t);
mpz_set_ui(a, a_ui);
mpz_set_ui(b, b_ui);
mpz_gcdext(g, s, t, a, b);
printf("g: %s, s: %s, t: %s\n",
mpz_get_str(NULL, 10, g),
mpz_get_str(NULL, 10, s),
mpz_get_str(NULL, 10, t));
}
int main()
{
test(1, 2);
test(6, 4);
}
Tested on Linux x64 using the latest repository code.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
