mbedtls_mpi_cmp_int undefined behavior if parameter is LLONG_MIN

[guidovranken]

Summary

mbedtls_mpi_cmp_int negates the input value. If the input value if the lowest possible value for mbedtls_mpi_sint, then negating that value is undefined behavior, because the negation LLONG_MIN (which is -9223372036854775808) is 9223372036854775808, but that value cannot be expressed in an mbedtls_mpi_sint.

System information

Mbed TLS version (number or commit id):
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): git clone --depth 1 -b development https://github.com/ARMmbed/mbedtls.git
Additional environment information:

Expected behavior

No undefined behavior

Actual behavior

Undefined behavior:

/home/jhg/oss-fuzz-53367/mbedtls/library/bignum.c:856:23: runtime error: negation of -9223372036854775808 cannot be represented in type 'mbedtls_mpi_sint' (aka 'long'); cast to an unsigned type to negate this value to itself
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /home/jhg/oss-fuzz-53367/mbedtls/library/bignum.c:856:23 in 

Steps to reproduce

#include <mbedtls/bignum.h>

#define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }

int main(void)
{
    mbedtls_mpi a;
    mbedtls_mpi_init(&a);
    const mbedtls_mpi_sint b = -9223372036854775808ULL;
    CF_CHECK_EQ(mbedtls_mpi_read_string(&a, 10, "0"), 0);
    mbedtls_mpi_cmp_int(&a, b);
end:
    mbedtls_mpi_free(&a);
    return 0;
}

Additional information

OSS-Fuzz #53367 https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=53367

[gilles-peskine-arm]

I thought this had been raised in the past, but it might have been a private discussion only.

Several other mbedtls_mpi_xxx_int functions have a similar issue.

The mpi_xxx_int functions were mostly intended for constants appearing in code. Since they don't allow the full range of a bignum limb, they're of limited use with variables. It's unfortunate that this was not documented.

Expecting a cryptographic library to cope with negative integers is dubious in the first place; Mbed TLS currently uses them internally, but we're currently rewriting the bignum module to separate out these uses of negative integers, and it's likely that the next major version of Mbed TLS (if not, the one after that) will not support negative bignums anymore.

So we're likely to keep this as a documented bug, and add a note to the documentation that -2^(biL-1) is not an acceptable input to these functions.

[guidovranken]

OK, I've worked around the issue in my fuzzer, so it won't be detected on OSS-Fuzz anymore.

[gilles-peskine-arm]

Actually, looking closely, a cast is enough to make the behavior well-defined. So here's a proper fix.

[gilles-peskine-arm]

Fixed by #6609 and backport.