-
Notifications
You must be signed in to change notification settings - Fork 2.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
mbedtls_mpi_mod_int() produces incorrect results #6540
Comments
I'm interested in this issue and have some findings here. Please correct me if I'm wrong. The problem is the algorithm for general case: Lines 1476 to 1490 in faefe62
From my limited math knowledge, the algorithm is correct but we might have overflow when doing y << biH . Because we couldn't ensure that y < (1 << biH) , when b >= (1 << biH) . y is only guaranteed to be less than b .So the possible solution would be, if it is acceptable, only do calculation when b is less than 1 << biH and return error otherwise.
|
Unfortunately this is not acceptable: this is a public function, we can't remove functionality from it. Can you confirm experimentally (with a debugger or by adding an assert or a printf) that the failing test case causes an overflow at this point? |
library patch: diff --git a/library/bignum.c b/library/bignum.c
index d33f07cc4..b2b09049f 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -1479,10 +1479,18 @@ int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_
for( i = A->n, y = 0; i > 0; i-- )
{
x = A->p[i - 1];
+ if ( y >> biH )
+ mbedtls_printf(
+ "[bignum.c:%d] y << biH would overflow, y = %08x\n",
+ __LINE__, y);
y = ( y << biH ) | ( x >> biH );
z = y / b;
y -= z * b;
+ if ( y >> biH )
+ mbedtls_printf(
+ "[bignum.c:%d] y << biH would overflow, y = %08x\n",
+ __LINE__, y);
x <<= biH;
y = ( y << biH ) | ( x >> biH );
z = y / b;
Test code: #define MBEDTLS_ALLOW_PRIVATE_ACCESS
#include <mbedtls/bignum.h>
#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
char* A[] = {
"562954248388609",
"562954248388610",
"2417870085973332058963968",
"230772460340063000000100500000300000010",
"562954248388609",
"562954248388610",
"2417870085973332058963968",
"230772460340063000000100500000300000010",
};
mbedtls_mpi_sint B[] = {
65537,
65537,
65537,
1205652040,
65535,
65535,
65535,
65535,
};
#define TEST_NUM ( sizeof(A) / sizeof(A[0]) )
int main(void)
{
int i;
mbedtls_mpi a,b;
mbedtls_mpi r;
mbedtls_mpi_uint ret;
mbedtls_mpi_uint p[1];
for ( i = 0; i < TEST_NUM; i++ )
{
printf("\n===== test %d =====\n", i);
printf("Calculate A mod B\n");
printf("A = %s\n", A[i]);
printf("B = %d\n", B[i]);
mbedtls_mpi_init(&a);
mbedtls_mpi_init(&b);
mbedtls_mpi_init(&r);
CF_CHECK_EQ(mbedtls_mpi_read_string(&a, 10, A[i]), 0);
p[0] = ( B[i] < 0 ) ? -B[i] : B[i];
b.s = ( B[i] < 0 ) ? -1 : 1;
b.n = 1;
b.p = p;
CF_CHECK_EQ(mbedtls_mpi_mod_int(&ret, &a, B[i]), 0);
CF_CHECK_EQ(mbedtls_mpi_mod_mpi(&r, &a, &b), 0);
printf("mbedtls_mpi_mod_int: %u\n", ret);
printf("mbedtls_mpi_mod_mpi: %u\n", r.p[0]);
}
end:
mbedtls_mpi_free(&a);
return 0;
} Output:
|
Since the algorithm is incorrect, we would expect there to be values for which it fails on 64-bit systems, and indeed The following test cases include both 32-bit and 64-bit trigger values, and also use the (However, there is a gotcha here: since the test interface gives
|
My fuzzer missed the 64 bit case because it was always using int32 instead of mbedtls_mpi_sint. Fixed it and now it finds it immediately. |
Summary
mbedtls_mpi_mod_int
produces the wrong result for certain inputs (initially found on 32-bit x86)System information
Mbed TLS version (number or commit id): 49e9fbd
Operating system and version: Linux x64
Configuration (if not default, please attach
mbedtls_config.h
):Compiler and options (if you used a pre-built binary, please indicate how you obtained it): gcc and clang with -m32
Additional environment information:
Expected behavior
Print
3644370
Actual behavior
Print
650989178
Steps to reproduce
Then compile and run:
Additional information
The text was updated successfully, but these errors were encountered: