Uninitialized memory bug found in /mpn/generic/mod_1_1.c

[Brett Kuntz]

> It does not exist, only pre[0] through pre[3] does. 

pre[4] **IS** pre[0] through pre[3] 

Go to line 248 inside mpn/generic/mod_1.c 

mp_limb_t pre[4]; 

That is NOT initialized. 

The next line: 

mpn_mod_1_1p_cps (pre, b); 

Only initializes pre[0], pre[1], and pre[3]. ***NOT*** pre[2]. 

The final line: 

return mpn_mod_1_1p (ap, n, b, pre); 

Reads from pre[2] erroneously and gives incorrect results if your stack memory has anything other than a 0 there. 

> But if you actually claim that an unedited GMP has a bug here, please 
construct a test case which uses documented interfaces, and which 
demonstrates the claimed bug. 

1) Edit line 248 mpn/generic/mp_limb_t pre[4]; into: 

mp_limb_t pre[4] = { -1, -1, -1, -1 }; 

2) Recompile GMP. 

3) Use the mpn_mod_1() function as described on the following page and you will now get incorrect results: 

https://gmplib.org/manual/Low_002dlevel-Functions 

-Brett Kuntz 




From: "Torbjörn Granlund" <tg at gmplib.org> 
To: "Brett Kuntz" <kuntz at shaw.ca> 
Cc: gmp-bugs at gmplib.org 
Sent: Thursday, August 31, 2023 3:40:47 AM 
Subject: Re: Uninitialized memory bug found in /mpn/generic/mod_1_1.c 

Brett Kuntz <kuntz at shaw.ca> writes: 

Take a look at function mpn_mod_1() in /mpn/generic/ mod_1.c on lines 248 - 250 

mp_limb_t pre[4]; 
mpn_mod_1_1p_cps (pre, b); 

mp_limb_t pre[4] is not initialized 

It does not exist, only pre[0] through pre[3] does. 

and the mpn_mod_1_1p_cps() function 
never writes to pre[2]. So if we change that to mp_limb_t pre[4] = { -1, 
-1, -1, -1 }; as a test we'll quickly see that inside mpn_mod_1_1p_cps() 
the value cps[2] (pre[2]) is never written to and if we print out pre[4] 
after running it we'll get output like: 0x21CFE6CFC938B36BU, 
0x0000000000000000U, 0xFFFFFFFFFFFFFFFFU, 0x9581CA13918612E1U (pre[2] is 
-1) 

/mpn/generic/mod_1_1.c lines 260-266: 

if (LIKELY (cnt != 0)) 
{ 
mp_limb_t B1modb = -b; 
B1modb *= ((bi >> (GMP_LIMB_BITS-cnt)) | (CNST_LIMB(1) << cnt)); 
ASSERT (B1modb <= b); /* NB: not fully reduced mod b */ 
cps[2] = B1modb >> cnt; 
} 

cnt will ALWAYS equal 0 since there will be NO leading 0's when this is 
called since /mpn/generic/mod_1_1.c checks for the high bit being SET 
before calling.. which means this function only ever gets called with NO 
leading zeros!!! 

Why are you so worked up? 

The logic seems perfectly fine. 

ALSO there are unexplained differences between MOD_1_1P_METHOD 1 and 
MOD_1_1P_METHOD 2 when it comes to the function mpn_mod_1_1p_cps(). In 
one of them pre[4] is always set and in the other (method 2) pre[2] is 
skipped! Why are these two functions different? It looks like their job 
is to calculate the inverses for the following mod functions so one 
would expect them to be the same. 

There are lots of "unexplained" things in the GMP internal functions. 
But trust me, the GMP developers understand the sources. 

ALSO the x64 assembly versions of these codes also does not always set 
all 4 values of pre[4] and this has lead to incorrect results when using 
the exported function mpn_mod_1(). 

You hypothesise things here. And you're wrong. 

I benevolent reading of your claims here is that things will be bad if 
you use one variant of the internal _cps function with another variant 
of the corresponding internal mod function. If that's what you're 
trying to say, then you're right. GMP is not edit proof, local user 
edits might break it in all sorts of ways, 

But if you actually claim that an unedited GMP has a bug here, please 
construct a test case which uses documented interfaces, and which 
demonstrates the claimed bug. 

I do not understand these functions enough 

Shouting from the top of your lungs about a bug which is just the result 
of reading the sources, without allowing yourself time to understand the 
logic fully, is somewhat unfair. 

-- 
Torbjörn 
Please encrypt, key id 0xC8601622