mbedtls_mpi_shift_r doesn't handling the sign

[ZaixingLaw]

Summary

see the code blocks below, didn't it miss to update the sign of the X when count is equal or bigger than mbedtls_mpi_bitlen(X).

int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
{
    MPI_VALIDATE_RET(X != NULL);
    if (X->n != 0) {
        mbedtls_mpi_core_shift_r(X->p, X->n, count);
    }
    return 0;
}

comparing to mbedtls_mpi_resize_clear

static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
{
    if (limbs == 0) {
        mbedtls_mpi_free(X);
        return 0;
    } else if (X->n == limbs) {
        memset(X->p, 0, limbs * ciL);
        X->s = 1;
        return 0;
    } else {
        mbedtls_mpi_free(X);
        return mbedtls_mpi_grow(X, limbs);
    }
}

mbedtls_mpi_mul_mpi

int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
{
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
    size_t i, j;
    mbedtls_mpi TA, TB;
    int result_is_zero = 0;
    MPI_VALIDATE_RET(X != NULL);
    MPI_VALIDATE_RET(A != NULL);
    MPI_VALIDATE_RET(B != NULL);

    mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);

    if (X == A) {
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
    }
    if (X == B) {
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
    }

    for (i = A->n; i > 0; i--) {
        if (A->p[i - 1] != 0) {
            break;
        }
    }
    if (i == 0) {
        result_is_zero = 1;
    }

    for (j = B->n; j > 0; j--) {
        if (B->p[j - 1] != 0) {
            break;
        }
    }
    if (j == 0) {
        result_is_zero = 1;
    }

    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));

    for (size_t k = 0; k < j; k++) {
        /* We know that there cannot be any carry-out since we're
         * iterating from bottom to top. */
        (void) mbedtls_mpi_core_mla(X->p + k, i + 1,
                                    A->p, i,
                                    B->p[k]);
    }

    /* If the result is 0, we don't shortcut the operation, which reduces
     * but does not eliminate side channels leaking the zero-ness. We do
     * need to take care to set the sign bit properly since the library does
     * not fully support an MPI object with a value of 0 and s == -1. */
    if (result_is_zero) {
        X->s = 1;
    } else {
        X->s = A->s * B->s;
    }

cleanup:

    mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);

    return ret;
}

when the mpi X is zero the sign will be set to 1(positive).

Let's look back to the MbedTLS-2.16.0

int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
{
    size_t i, v0, v1;
    mbedtls_mpi_uint r0 = 0, r1;
    MPI_VALIDATE_RET( X != NULL );

    v0 = count /  biL;
    v1 = count & (biL - 1);

    if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
        return mbedtls_mpi_lset( X, 0 );

    /*
     * shift by count / limb_size
     */
    if( v0 > 0 )
    {
        for( i = 0; i < X->n - v0; i++ )
            X->p[i] = X->p[i + v0];

        for( ; i < X->n; i++ )
            X->p[i] = 0;
    }

    /*
     * shift by count % limb_size
     */
    if( v1 > 0 )
    {
        for( i = X->n; i > 0; i-- )
        {
            r1 = X->p[i - 1] << (biL - v1);
            X->p[i - 1] >>= v1;
            X->p[i - 1] |= r0;
            r0 = r1;
        }
    }

    return( 0 );
}

as we can see from the previous code blocks, if count is bigger than mbedtls_mpi_bitlen(X).
will set 0 to X. let's see mbedtls_mpi_lset below:

int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
{
    int ret;
    MPI_VALIDATE_RET( X != NULL );

    MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
    memset( X->p, 0, X->n * ciL );

    X->p[0] = ( z < 0 ) ? -z : z;
    X->s    = ( z < 0 ) ? -1 : 1;

cleanup:

    return( ret );
}

as a result the X->s will be 1 when using MbedTLS-2.16

System information

Mbed TLS version (v3.4.0):
Operating system and version:
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):
Additional environment information:

Expected behavior

X->s equal to 1

Actual behavior

X->s remaind the same.

Steps to reproduce

mbedtls_mpi_int(&X);
mbedtls_mpi_lset(&X, -8192);
mbedtls_mpi_shift_r(&X, 128);
mbedtls_printf("X.s: %zd\n", X.s);

Additional information

[gilles-peskine-arm]

This isn't the first bug where one function in the library creates a “negative zero” in some conditions, and other functions don't treat this “negative zero” as a representation of 0. We've decided that “negative zero” is not a valid representation, so that functions don't need to support it as an input.

test_suite_bignum asserts sign_is_valid(&X) in many places, including the unit test function for mbedtls_mpi_shift_r, but unfortunately there's no test case with a negative input.