gmp_pow(64, 11) throws overflow exception

[pbroekhof]

Description

The following code:

<?php
echo gmp_pow(64, 11);

Resulted in this output:

Fatal error: Uncaught ValueError: base and exponent overflow in Command line code:1
Stack trace:
#0 Command line code(1): gmp_pow(64, 11)
#1 {main}
  thrown in Command line code on line 1

But I expected this output instead:

73786976294838206464

https://3v4l.org/eY5kA

Not sure why the overflow triggered here, the resulting output is not particularly large (for GMP). Performing the same calculation by using gmp_mul() repeatedly does not cause an overflow exception.

PHP Version

PHP 8.3.14

Operating System

Arch Linux 6.11.6

[cmb69]

This has been introduced via #16384. The threshold seems to be way too restrictive.

[cmb69]

php-src/ext/gmp/gmp.c

Lines 1363 to 1370 in 3aa4973

	double powmax = log((double)ZEND_LONG_MAX);
	if (Z_TYPE_P(base_arg) == IS_LONG && Z_LVAL_P(base_arg) >= 0) {
	INIT_GMP_RETVAL(gmpnum_result);
	if ((log(Z_LVAL_P(base_arg)) * exp) > powmax) {
	zend_value_error("base and exponent overflow");
	RETURN_THROWS();
	}

The condition on line 1367 is basically checking whether base_arg ** exp > ZEND_LONG_MAX, in which case a ValueError is thrown; it seems to me that powmax should rather be something like UINT_MAX (probably a bit less), and log should rather be log2 or log10 depending on the libgmp representation). The code in the else branch does the same check, but also assumes the GMP base fits into an libgmp ui, which is is an additional restriction (and may cause overflow/wrap-around; not sure how that's implemented in libgmp/mpir).

[cmb69]

php-src/ext/gmp/gmp.c

Lines 1363 to 1370 in 3aa4973

	double powmax = log((double)ZEND_LONG_MAX);
	if (Z_TYPE_P(base_arg) == IS_LONG && Z_LVAL_P(base_arg) >= 0) {
	INIT_GMP_RETVAL(gmpnum_result);
	if ((log(Z_LVAL_P(base_arg)) * exp) > powmax) {
	zend_value_error("base and exponent overflow");
	RETURN_THROWS();
	}

The condition on line 1367 is basically checking whether base_arg ** exp > ZEND_LONG_MAX, in which case a ValueError is thrown; it seems to me that powmax should rather be something like UINT_MAX (probably a bit less), and log should rather be log2 or log10 depending on the libgmp representation). The code in the else branch does the same check, but also assumes the GMP base fits into an libgmp ui, which is is an additional restriction (and may cause overflow/wrap-around; not sure how that's implemented in libgmp/mpir).

PS: there is GMP_UI_MAX which may be helpful. However, with current mpir (3.0.0) on Windows, mpz_get_ui() happily returns values which are way larger than GMP_UI_MAX (which is 0xFFFFFFFF on x64). Ah, because sizeof(mpir_ui)==8. ¯\(ツ)/¯ (seems completely b0rked on LLP64; need to check Brian Gladman's fork).

PPS: mpz_get_ui() overflows (mpir 3.0.0, Brian Gladman's fork HEAD) for large values. However, at least GMP_UI_MAX suits mpir_ui there (64bit unsigned int).

PPPS: instead of log(mpz_get_ui(gmpnum_base)) we can likely employ mpz_sizeinbase().

[cmb69]

So I guess something like the following would do (where 2000 is some arbitrary value, which might be large enough, and is unlikely to trigger OOM, or FPEs; this is assuming that numbers are stored in base 256):

 ext/gmp/gmp.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/ext/gmp/gmp.c b/ext/gmp/gmp.c
index 177d0c7f7c..abbffe2485 100644
--- a/ext/gmp/gmp.c
+++ b/ext/gmp/gmp.c
@@ -1360,11 +1360,11 @@ ZEND_FUNCTION(gmp_pow)
 		RETURN_THROWS();
 	}
 
-    double powmax = log((double)ZEND_LONG_MAX);
+	double powmax = 2000;
 
 	if (Z_TYPE_P(base_arg) == IS_LONG && Z_LVAL_P(base_arg) >= 0) {
 		INIT_GMP_RETVAL(gmpnum_result);
-		if ((log(Z_LVAL_P(base_arg)) * exp) > powmax) {
+		if ((log(Z_LVAL_P(base_arg)) / log(256) * exp) > powmax) {
 			zend_value_error("base and exponent overflow");
 			RETURN_THROWS();
 		}
@@ -1374,8 +1374,7 @@ ZEND_FUNCTION(gmp_pow)
 		zend_ulong gmpnum;
 		FETCH_GMP_ZVAL(gmpnum_base, base_arg, temp_base, 1);
 		INIT_GMP_RETVAL(gmpnum_result);
-		gmpnum = mpz_get_ui(gmpnum_base);
-		if ((log(gmpnum) * exp) > powmax) {
+		if ((mpz_sizeinbase(gmpnum_base, 16) / 2.0 * exp) > powmax) {
 			FREE_GMP_TEMP(temp_base);
 			zend_value_error("base and exponent overflow");
 			RETURN_THROWS();

That passes the ext/gmp test suite.

[devnexen]

Thanks @cmb69, please open a PR :)

[Girgias]

Should this same approach be used for #16880 ?

[cmb69]

@Girgias, possibly. There are two unrelated issues: (a) find the proper threshold which doesn't trigger allocation overflow (regardless of whether checked by libgmp or not), and (b) do not prematurely convert to (unsigned) integers (which in itself might cause overflow). (b) may or not may already affect some functions, (a) is likely something we should unify throughout (though not necessarily for stable releases). And (a) may or not may take into account actual OOM conditions (we want to avoid libgmp/mpir aborts, but it's obviously not possible to predict OOM conditions). I think we should reconsider #16609.

But especially the approach I'm suggesting here and the PR should be checked by people with a stronger math background than I have, and ideally by people who know more about libgmp/mir than I do.

[GaryAllan]

Isn't the whole point of gmp to work with large numbers? Why were these warnings added?

Using gmp to manipulate IPv6 (128bit) addresses. Now app is borked with PHP Fatal Errors.

Works fine in 8.3.13.

# php -v
PHP 8.3.14 (cli) (built: Nov 21 2024 05:32:50) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.3.14, Copyright (c) Zend Technologies
    with Xdebug v3.3.2, Copyright (c) 2002-2024, by Derick Rethans
    
# php -a
Interactive shell

php > $a = gmp_pow(2,128);
PHP Warning:  Uncaught ValueError: base and exponent overflow in php shell code:1
Stack trace:
#0 php shell code(1): gmp_pow()
#1 {main}
  thrown in php shell code on line 1

php > $a = gmp_pow(2,64);
PHP Warning:  Uncaught ValueError: base and exponent overflow in php shell code:1
Stack trace:
#0 php shell code(1): gmp_pow()
#1 {main}
  thrown in php shell code on line 1
  
php > $a = gmp_pow(2,63);
php >

[brainpower]

Here gmp gets used to do pubkey crypto, and fails with the reported error in Line 125:
https://github.com/web-token/jwt-util-ecc/blob/v2.1/Curve.php#L121

I'm not sure about the key size it uses, but it might be either 256, 384 or 521?

Anyway that issue brought me here and I can report that the testcase I threw together works again when applying the patch from #16884 :

print "\n521bit random number:\n";
#$big = gmp_random_bits(521);
$big = gmp_init("4251217229032923292930005432624928043281508404012751772104304003082554171429833539451625576338397719972103098793555878613020934461497631132347722033178373655", 10);
print gmp_strval($big);
print "\nsquared:\n";
print gmp_strval(gmp_pow($big, 2));
print "\ncubed:\n";
print gmp_strval(gmp_pow($big, 3));

No idea if its correct, but given the same number, .25 and .26-pathed give the same result.
And since the crypto worked with .25, I'd guess, the calculation of .25 was correct and worked fine.

$ php-8.2.25/sapi/cli/php gmp.php

521bit random number:
4251217229032923292930005432624928043281508404012751772104304003082554171429833539451625576338397719972103098793555878613020934461497631132347722033178373655
squared:
18072847928426366581279989915694740530671916218102377191424132023600136047861156669615104969436794199495181765333056780055816218023379471025928901238862791468101621646705488089388006447463679143858905946586705082207061183645048871047124837688431517702933005990405140682440783810752751802070956908932298390798059025
cubed:
76831602491018146134634345126442958915477938546234602862191417202949958534079235121536007064385456418446864474203451342701569341778306506439541356249308333142051417716010195018032238613622721344353239896478098745620543823585174360460492277345173948753232020183168581348902727027062576340141057533620617249233140104213169388056803516021682723724305838712648291962679567686459967874143733768903580124157697624354599273726138868476180996981744830018252088144265980194986375                                                                                   


$ php-8.2.26/sapi/cli/php gmp.php

521bit random number:
4251217229032923292930005432624928043281508404012751772104304003082554171429833539451625576338397719972103098793555878613020934461497631132347722033178373655
squared:

Fatal error: Uncaught ValueError: base and exponent overflow in /home/XXXX/dev/php/gmp.php:30
Stack trace:
#0 /home/XXXX/dev/php/gmp.php(30): gmp_pow(Object(GMP), 2)
#1 {main}
  thrown in /home/XXXX/dev/php/gmp.php on line 30
  

$ php-8.2.26-patched/sapi/cli/php gmp.php

521bit random number:
4251217229032923292930005432624928043281508404012751772104304003082554171429833539451625576338397719972103098793555878613020934461497631132347722033178373655
squared:
18072847928426366581279989915694740530671916218102377191424132023600136047861156669615104969436794199495181765333056780055816218023379471025928901238862791468101621646705488089388006447463679143858905946586705082207061183645048871047124837688431517702933005990405140682440783810752751802070956908932298390798059025
cubed:
76831602491018146134634345126442958915477938546234602862191417202949958534079235121536007064385456418446864474203451342701569341778306506439541356249308333142051417716010195018032238613622721344353239896478098745620543823585174360460492277345173948753232020183168581348902727027062576340141057533620617249233140104213169388056803516021682723724305838712648291962679567686459967874143733768903580124157697624354599273726138868476180996981744830018252088144265980194986375                                                                                                  

EDIT: noticed I had a 512 bit number instead of a 521 bit number and redid the tests.

Maybe the testcase in PHP should also test for number sizes typically found in cryptography?

[cmb69]

Isn't the whole point of gmp to work with large numbers? Why were these warnings added?

Very large number can cause overflow handling in libgmp, which then leads to abort of the whole process (very bad for ZTS environments, but also not nice for NTS). Thus, restricting the range of supported inputs is reasonable. However, the fix was too restrictive. Sorry!

Maybe the testcase in PHP should also test for number sizes typically found in cryptography?

That is a good idea. Maybe you want to contribute a PR?

[brainpower]

That is a good idea. Maybe you want to contribute a PR?

Well, I'm no crypto-guy, and I don't really know much about the inner workings of those algos...
So, sadly I have almost no idea which cases should actually be tested for... other than what I found while troubleshooting this issue.

So, I could contribute the testcase above, maybe not just 521 bit, but also for 384 and 256, maybe 128 bit numbers, but not really anything more than that.
If I should, which branch/commit/tag should a PR be based on? Especially when it basically depends on at least your fix?

[cmb69]

Well, I'm no crypto-guy, and I don't really know much about the inner workings of those algos...

Me neither.

So, I could contribute the testcase above, maybe not just 521 bit, but also for 384 and 256, maybe 128 bit numbers, but not really anything more than that.

Yes, that sounds reasonable. I think it's best to target master; could still be changed later.

[Girgias]

@GaryAllan the issue is that the underlying GMP library actually doesn't allow to use a "GMP object" for certain parameters, but wants an unsigned long (or just long) which is why the warning got introduced.

Now why the underlying GMP doesn't allow this I don't understand.

[Girgias]

@cmb69 I was out and about today, but I will try to review this considering I do have a Bsc in maths... but I don't know that much about libgmp but I did read through the docs for it for #16685

[GaryAllan]

Hello,

I've written a test case for ext/gmp/tests and would like to raise a PR.

What's the bug ID for this issue? The IDs don't appear to match GitHub issue IDs.

e.g bug74670.phpt 74670 isn't a GitHub Issue #.

Where did bug ID 74670 come from and what's the equivalent for this bug?

Thanks

[brainpower]

bug* prefix seems for Bugs reported at the old bugtracker: https://bugs.php.net/
gh* prefix is used for github issues.

[cmb69]

@Girgias, thanks! I think we should focus on #16880 first. If we go with counting bits, #16884 should be adapted to do this, too.

[Girgias]

I had an offline discussion with @nielsdos and he think (which I agree) the best course of action is to revert all the overflow checks for stable releases and fix them in master. They were found by fuzzing and not a human, and clearly we did the fixes haphazardly.

I have an idea for mpz_pow_ui looking at https://github.com/SWI-Prolog/swipl/blob/38ce02c748a9603d31e0ff87543840070f543770/src/pl-arith.c which boils down to

"number of bits of base num" times exponent is always less or equals the number of bits required to hold the result

Knowing that GMP can handle numbers up to 2^37 bits (see: https://gmplib.org/list-archives/gmp-discuss/2012-April/005020.html) this gives us an easy way to determine the "safe" limit.

For mpz_fac_ui I am running a script to determine at which value it "breaks" which is going to take a while, but at least we are not doing some random guess.

The final function where such an issue can arise is mpz_bin_ui for which I haven't had time to look into yet.

[GaryAllan]

Alpine 3.20 has picked up the broken PHP builds

This may start impacting a wider audience.

/ # cat /etc/issue 
Welcome to Alpine Linux 3.20
Kernel \r on an \m (\l)

/ # php -v
PHP 8.3.14 (cli) (built: Nov 21 2024 08:27:36) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.3.14, Copyright (c) Zend Technologies

/ # php -a
Interactive shell

php > print gmp_strval(gmp_pow(2, 64));
PHP Warning:  Uncaught ValueError: base and exponent overflow in php shell code:1
Stack trace:
#0 php shell code(1): gmp_pow()
#1 {main}
  thrown in php shell code on line 1
php > 

[cmb69]

I had an offline discussion with @nielsdos and he think (which I agree) the best course of action is to revert all the overflow checks for stable releases and fix them in master.

Works for me (although the gmp_pow() overflow check might be the only one which is completely off).

"number of bits of base num" times exponent is always less or equals the number of bits required to hold the result

So https://github.com/php/php-src/pull/16884/files#diff-0bdc127cb9fb7a558418fb24dcd2d7249c5031680db06010d9caa4663d945264R1357 is basically correct. :)

Knowing that GMP can handle numbers up to 2^37 bits

On 32bit systems, at most 2^31 bits, I think. And even that is quite something for 64bit systems. But I'm fine with applying the max limit. (Albeit, "640K ought to be enough for everyone" ;)

Anyhow, thanks for looking into this, @Girgias!

@GaryAllan, we're always shipping RCs; if these are not tested …