Merge pull request #6618 from gilles-peskine-arm/mpi_sint-min-ub-2.28
Backport 2.28: Fix undefined behavior in bignum: NULL+0 and -most-negative-sint
diff --git a/ChangeLog.d/mpi-add-0-ub.txt b/ChangeLog.d/mpi-add-0-ub.txt
new file mode 100644
index 0000000..9f131a4
--- /dev/null
+++ b/ChangeLog.d/mpi-add-0-ub.txt
@@ -0,0 +1,4 @@
+Bugfix
+ * Fix undefined behavior (typically harmless in practice) of
+ mbedtls_mpi_add_mpi(), mbedtls_mpi_add_abs() and mbedtls_mpi_add_int()
+ when both operands are 0 and the left operand is represented with 0 limbs.
diff --git a/ChangeLog.d/mpi-most-negative-sint.txt b/ChangeLog.d/mpi-most-negative-sint.txt
new file mode 100644
index 0000000..5e775c4
--- /dev/null
+++ b/ChangeLog.d/mpi-most-negative-sint.txt
@@ -0,0 +1,4 @@
+Bugfix
+ * Fix undefined behavior (typically harmless in practice) when some bignum
+ functions receive the most negative value of mbedtls_mpi_sint. Credit
+ to OSS-Fuzz. Fixes #6597.
diff --git a/include/mbedtls/bignum.h b/include/mbedtls/bignum.h
index cede923..0f3aa00 100644
--- a/include/mbedtls/bignum.h
+++ b/include/mbedtls/bignum.h
@@ -182,6 +182,20 @@
#endif /* !MBEDTLS_NO_UDBL_DIVISION */
#endif /* !MBEDTLS_HAVE_INT64 */
+/** \typedef mbedtls_mpi_uint
+ * \brief The type of machine digits in a bignum, called _limbs_.
+ *
+ * This is always an unsigned integer type with no padding bits. The size
+ * is platform-dependent.
+ */
+
+/** \typedef mbedtls_mpi_sint
+ * \brief The signed type corresponding to #mbedtls_mpi_uint.
+ *
+ * This is always an signed integer type with no padding bits. The size
+ * is platform-dependent.
+ */
+
#ifdef __cplusplus
extern "C" {
#endif
diff --git a/library/bignum.c b/library/bignum.c
index 0e9ff19..7b851ca 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -262,6 +262,17 @@
memcpy( Y, &T, sizeof( mbedtls_mpi ) );
}
+static inline mbedtls_mpi_uint mpi_sint_abs( mbedtls_mpi_sint z )
+{
+ if( z >= 0 )
+ return( z );
+ /* Take care to handle the most negative value (-2^(biL-1)) correctly.
+ * A naive -z would have undefined behavior.
+ * Write this in a way that makes popular compilers happy (GCC, Clang,
+ * MSVC). */
+ return( (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z );
+}
+
/*
* Set value from integer
*/
@@ -273,7 +284,7 @@
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
memset( X->p, 0, X->n * ciL );
- X->p[0] = ( z < 0 ) ? -z : z;
+ X->p[0] = mpi_sint_abs( z );
X->s = ( z < 0 ) ? -1 : 1;
cleanup:
@@ -1093,7 +1104,7 @@
mbedtls_mpi_uint p[1];
MPI_VALIDATE_RET( X != NULL );
- *p = ( z < 0 ) ? -z : z;
+ *p = mpi_sint_abs( z );
Y.s = ( z < 0 ) ? -1 : 1;
Y.n = 1;
Y.p = p;
@@ -1130,6 +1141,11 @@
if( B->p[j - 1] != 0 )
break;
+ /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
+ * and B is 0 (of any size). */
+ if( j == 0 )
+ return( 0 );
+
MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
o = B->p; p = X->p; c = 0;
@@ -1317,7 +1333,7 @@
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( A != NULL );
- p[0] = ( b < 0 ) ? -b : b;
+ p[0] = mpi_sint_abs( b );
B.s = ( b < 0 ) ? -1 : 1;
B.n = 1;
B.p = p;
@@ -1335,7 +1351,7 @@
MPI_VALIDATE_RET( X != NULL );
MPI_VALIDATE_RET( A != NULL );
- p[0] = ( b < 0 ) ? -b : b;
+ p[0] = mpi_sint_abs( b );
B.s = ( b < 0 ) ? -1 : 1;
B.n = 1;
B.p = p;
@@ -1756,7 +1772,7 @@
mbedtls_mpi_uint p[1];
MPI_VALIDATE_RET( A != NULL );
- p[0] = ( b < 0 ) ? -b : b;
+ p[0] = mpi_sint_abs( b );
B.s = ( b < 0 ) ? -1 : 1;
B.n = 1;
B.p = p;
diff --git a/tests/suites/test_suite_bignum.function b/tests/suites/test_suite_bignum.function
index f159967..35952f0 100644
--- a/tests/suites/test_suite_bignum.function
+++ b/tests/suites/test_suite_bignum.function
@@ -1671,6 +1671,150 @@
}
/* END_CASE */
+/* BEGIN_CASE */
+void most_negative_mpi_sint( )
+{
+ /* Ad hoc tests for n = -p = -2^(biL-1) as a mbedtls_mpi_sint. We
+ * guarantee that mbedtls_mpi_sint is a two's complement type, so this
+ * is a valid value. However, negating it (`-n`) has undefined behavior
+ * (although in practice `-n` evaluates to the value n).
+ *
+ * This function has ad hoc tests for this value. It's separated from other
+ * functions because the test framework makes it hard to pass this value
+ * into test cases.
+ *
+ * In the comments here:
+ * - biL = number of bits in limbs
+ * - p = 2^(biL-1) (smallest positive value not in mbedtls_mpi_sint range)
+ * - n = -2^(biL-1) (largest negative value in mbedtls_mpi_sint range)
+ */
+
+ mbedtls_mpi A, R, X;
+ mbedtls_mpi_init( &A );
+ mbedtls_mpi_init( &R );
+ mbedtls_mpi_init( &X );
+
+ const size_t biL = 8 * sizeof( mbedtls_mpi_sint );
+ mbedtls_mpi_uint most_positive_plus_1 = (mbedtls_mpi_uint) 1 << ( biL - 1 );
+ const mbedtls_mpi_sint most_positive = most_positive_plus_1 - 1;
+ const mbedtls_mpi_sint most_negative = - most_positive - 1;
+ TEST_EQUAL( (mbedtls_mpi_uint) most_negative,
+ (mbedtls_mpi_uint) 1 << ( biL - 1 ) );
+ TEST_EQUAL( (mbedtls_mpi_uint) most_negative << 1, 0 );
+
+ /* Test mbedtls_mpi_lset() */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_negative ), 0 );
+ TEST_EQUAL( A.s, -1 );
+ TEST_EQUAL( A.n, 1 );
+ TEST_EQUAL( A.p[0], most_positive_plus_1 );
+
+ /* Test mbedtls_mpi_cmp_int(): -p == -p */
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &A, most_negative ), 0 );
+
+ /* Test mbedtls_mpi_cmp_int(): -(p+1) < -p */
+ A.p[0] = most_positive_plus_1 + 1;
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &A, most_negative ), -1 );
+
+ /* Test mbedtls_mpi_cmp_int(): -(p-1) > -p */
+ A.p[0] = most_positive_plus_1 - 1;
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &A, most_negative ), 1 );
+
+ /* Test mbedtls_mpi_add_int(): (p-1) + (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_positive ), 0 );
+ TEST_EQUAL( mbedtls_mpi_add_int( &X, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, -1 ), 0 );
+
+ /* Test mbedtls_mpi_add_int(): (0) + (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, 0 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_add_int( &X, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, most_negative ), 0 );
+
+ /* Test mbedtls_mpi_add_int(): (-p) + (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_add_int( &X, &A, most_negative ), 0 );
+ TEST_EQUAL( X.s, -1 );
+ TEST_EQUAL( X.n, 2 );
+ TEST_EQUAL( X.p[0], 0 );
+ TEST_EQUAL( X.p[1], 1 );
+
+ /* Test mbedtls_mpi_sub_int(): (p) - (-p) */
+ mbedtls_mpi_free( &X );
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_positive ), 0 );
+ TEST_EQUAL( mbedtls_mpi_sub_int( &X, &A, most_negative ), 0 );
+ TEST_EQUAL( X.s, 1 );
+ TEST_EQUAL( X.n, 1 );
+ TEST_EQUAL( X.p[0], ~(mbedtls_mpi_uint)0 );
+
+ /* Test mbedtls_mpi_sub_int(): (0) - (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, 0 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_sub_int( &X, &A, most_negative ), 0 );
+ TEST_EQUAL( X.s, 1 );
+ TEST_EQUAL( X.n, 1 );
+ TEST_EQUAL( X.p[0], most_positive_plus_1 );
+
+ /* Test mbedtls_mpi_sub_int(): (-p) - (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_sub_int( &X, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, 0 ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (-p+1) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, -most_positive ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, 0 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, -most_positive ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (-p) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, 1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, 0 ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (-2*p) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_shift_l( &A, 1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, 2 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, 0 ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (-2*p+1) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_add_int( &A, &A, 1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, 1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, -most_positive ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (p-1) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_lset( &A, most_positive ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, 0 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, most_positive ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (p) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_add_int( &A, &A, 1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, -1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, 0 ), 0 );
+
+ /* Test mbedtls_mpi_div_int(): (2*p) / (-p) */
+ TEST_EQUAL( mbedtls_mpi_shift_l( &A, 1 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_div_int( &X, &R, &A, most_negative ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &X, -2 ), 0 );
+ TEST_EQUAL( mbedtls_mpi_cmp_int( &R, 0 ), 0 );
+
+ /* Test mbedtls_mpi_mod_int(): never valid */
+ TEST_EQUAL( mbedtls_mpi_mod_int( X.p, &A, most_negative ),
+ MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
+
+ /* Test mbedtls_mpi_random(): never valid */
+ TEST_EQUAL( mbedtls_mpi_random( &X, most_negative, &A,
+ mbedtls_test_rnd_std_rand, NULL ),
+ MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
+
+exit:
+ mbedtls_mpi_free( &A );
+ mbedtls_mpi_free( &R );
+ mbedtls_mpi_free( &X );
+}
+/* END_CASE */
+
/* BEGIN_CASE depends_on:MBEDTLS_SELF_TEST */
void mpi_selftest( )
{
diff --git a/tests/suites/test_suite_bignum.misc.data b/tests/suites/test_suite_bignum.misc.data
index 937e290..9da54ff 100644
--- a/tests/suites/test_suite_bignum.misc.data
+++ b/tests/suites/test_suite_bignum.misc.data
@@ -1955,6 +1955,9 @@
MPI random bad arguments: min > N = 1, 0 limb in upper bound
mpi_random_fail:2:"000000000000000001":MBEDTLS_ERR_MPI_BAD_INPUT_DATA
+Most negative mbedtls_mpi_sint
+most_negative_mpi_sint:
+
MPI Selftest
depends_on:MBEDTLS_SELF_TEST
mpi_selftest: