gmp_pow(64, 11) throws overflow exception

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

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

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).

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().

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.

@cmb69

Thanks @cmb69, please open a PR :)

Should this same approach be used for #16880 ?

@Girgias

@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.

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 >

@Girgias

Good catch @Girgias - I'm testing that change on my library, and it seems to be ok. For some reason, I thought that was a much newer language feature.

It does raise the question of why the operator overloads aren't validated as the same was as the functions. I would have (wrongly) assumed that the former is mere syntactic sugar for the latter; this leads me to think that if the original change was in response to a security concern, there could be application vulnerabilities that remain after patching depending on how the code was written.

The GMP codebase is a "bit" jank atm, I got a big clean-up PR in #16685 that I need to land, but that is only for master.

The memory overflow was found via fuzzing, and it only detected something on gmp_pow() and we didn't think of applying it to the operator overloading hook. AFAIK there is no security issue, the fix is just to prevent a segfault.

@Firehed

@Firehed :

Not sure if you all need additional test vectors here (e.g. https://3v4l.org/lnhXp), but I'm happy to extract my new test failures into whatever format would be beneficial. @brainpower @GaryAllan et al, sounds like we're working on similar spaces - do you all want to collaborate on this?

Well, your example should be covered by the tests in #16896 . If you have any other feel free to share as a comment on my PR or maybe open a PR to the branch of my PR and I'll add them to my PR, if reasonable.
cmb69 wanted to wait for a proper fix for gmp_pow though, before concentrating on the tests.

revert php commit which broke some use-cases of gmp (overzealous chec…

[BUGFIX] Disable GMP for certain php versions due to a bug in php

I tested this also in the 8.4.1 release and I get the same fatal error here too. It happens in these three releases from November 21:

8.2.26
8.3.14
8.4.1

Yes, this is normal, because it was a bug fixes that has been applied to all supported versions.

This is going to be fixed in the next release after the revert of the broken fix.

You can use the ** operator instead of gmp_pow() which is not affected by the broken fix.

BigInteger: fix for PHP 8.4.0 - 8.4.1 regression

The overflow checks have been reverted, so this ticket can be closed.

Disallow PHP 8.3.14 and 8.2.26

Use gmp operator overload instead of gmp_pow

Navigation Menu

Repository navigation

gmp_pow(64, 11) throws overflow exception #16870

Description

PHP Version

Operating System

30 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	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();
	}

gmp_pow(64, 11) throws overflow exception #16870

Description

Description

PHP Version

Operating System

Activity

cmb69 commented on Nov 20, 2024

cmb69 commented on Nov 20, 2024

cmb69 commented on Nov 20, 2024

cmb69 commented on Nov 20, 2024

devnexen commented on Nov 20, 2024

Girgias commented on Nov 21, 2024

cmb69 commented on Nov 21, 2024

GaryAllan commented on Nov 21, 2024

30 remaining items

Firehed commented on Nov 26, 2024

Girgias commented on Nov 26, 2024

brainpower commented on Nov 26, 2024

Olsm commented on Nov 28, 2024

Girgias commented on Nov 28, 2024

cmb69 commented on Dec 9, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions