RSA public operation results in panic, with particular odd modulus size (IDFGH-10615)

[Emill]

Answers checklist.

• I have read the documentation ESP-IDF Programming Guide and the issue is not addressed there.
• I have updated my IDF branch (master or release) to the latest version and checked that the issue is present there.
• I have searched the issue tracker for a similar issue and not found a similar issue.

IDF version.

v5.1

Operating System used.

Windows

How did you build your project?

Eclipse IDE

If you are using Windows, please specify command line type.

None

Development Kit.

ESP32-S3

Power Supply used.

USB

What is the expected behavior?

The RSA library should not panic when running a public operation. Instead it should finish execution and return a status code.

What is the actual behavior?

Panic

Steps to reproduce.

#include <mbedtls/rsa.h>
#include <mbedtls/sha256.h>

void rsa_bug(void) {
    int res;
    mbedtls_rsa_context rsa_ctx;
    uint8_t N[384] = {0};
    uint8_t E[3] = {1, 0, 1}; // 65537

    for (int i = 0; i < 384; i++) N[i] = 0x45;

    mbedtls_rsa_init(&rsa_ctx);
    res = mbedtls_rsa_import_raw(&rsa_ctx, N, 384, NULL, 0, NULL, 0, NULL, 0, E, 3);
    if (res != 0) {
        printf("res: %d\n", res);
        abort();
    }
    res = mbedtls_rsa_complete(&rsa_ctx);
    if (res != 0) {
        printf("res: %d\n", res);
        abort();
    }

    uint8_t hash[32], signature[384] = {0};
    if (mbedtls_sha256(NULL, 0, hash, 0) != 0) { // hash of empty message
        abort();
    }
    res = mbedtls_rsa_pkcs1_verify(&rsa_ctx, MBEDTLS_MD_SHA256, 32, hash, signature);
    printf("verify res: %d\n", res);
}

The actual contents of the message hash and signature are irrelevant, it is when deriving "rinv" for the modulus that the bug is triggered.

Debug Logs.

assert failed: mpi_mult_mpi_failover_mod_mult esp_bignum.c:651 (mpi_words(Z) == z_words)


Backtrace: 0x403757aa:0x3fca3820 0x40379b25:0x3fca3840 0x4037f3c5:0x3fca3860 0x4201231a:0x3fca3980 0x420123f5:0x3fca39a0 0x420124cd:0x3fca39d0 0x4201340d:0x3fca3a00 0x4201352f:0x3fca3a90 0x420120ef:0x3fca3ab0 0x42012229:0x3fca3ae0 0x42012331:0x3fca3b20 0x42010f68:0x3fca3b40 0x42011700:0x3fca3b70 0x42011769:0x3fca3ba0 0x4200d9e8:0x3fca3bc0 0x420080f1:0x3fca3fd0 0x420239cb:0x3fca3ff0 0x4037bfcd:0x3fca4020
0x403757aa: panic_abort at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/esp_system/panic.c:452

0x40379b25: esp_system_abort at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/esp_system/port/esp_system_chip.c:84

0x4037f3c5: __assert_func at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/newlib/assert.c:81

0x4201231a: mpi_mult_mpi_failover_mod_mult at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/port/esp_bignum.c:651 (discriminator 1)

0x420123f5: mbedtls_mpi_mul_mpi at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/port/esp_bignum.c:522

0x420124cd: mbedtls_mpi_mul_int at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/port/esp_bignum.c:557

0x4201340d: mbedtls_mpi_div_mpi at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/mbedtls/library/bignum.c:1430

0x4201352f: mbedtls_mpi_mod_mpi at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/mbedtls/library/bignum.c:1499

0x420120ef: calculate_rinv at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/port/esp_bignum.c:200 (discriminator 2)

0x42012229: esp_mpi_exp_mod at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/port/esp_bignum.c:388

0x42012331: mbedtls_mpi_exp_mod at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/port/esp_bignum.c:460

0x42010f68: mbedtls_rsa_public at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/mbedtls/library/rsa.c:752

0x42011700: mbedtls_rsa_rsassa_pkcs1_v15_verify at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/mbedtls/library/rsa.c:2221

0x42011769: mbedtls_rsa_pkcs1_verify at C:/Users/Emil/Documents/Espressif/frameworks/esp-idf-v5.1/components/mbedtls/mbedtls/library/rsa.c:2268

0x4200d9e8: rsa_bug at C:/Users/Emil/Documents/eclipse-workspace/hello_world/main/rsa_bug.c:28

More Information.

It seems the bug got introduced by this commit: dc34d49, which was made to catch errors on ESP32 (#8710).

Other relevant issues:
#10403
#11366

My conclusion is that the assertion is incorrect, and only works in some cases. The added assertion is:

assert(mpi_words(Z) == z_words);

A proposed solution is instead:

assert(z_words - mpi_words(Z) <= (size_t)1);

Description of proposed solution:

The mbedtls_mpi_mul_mpi function, which is the only function that calls mpi_mult_mpi_failover_mod_mult, calculates:

size_t x_bits = mbedtls_mpi_bitlen(X);
size_t y_bits = mbedtls_mpi_bitlen(Y);
size_t x_words = bits_to_words(x_bits);
size_t y_words = bits_to_words(y_bits);
size_t z_words = bits_to_words(x_bits + y_bits);

It determines that the result will fit in x_bits + y_bits bits. But this is only the worst case. In some cases, the result fits in x_bits + y_bits - 1 bits. Take for example 0b1111 * 0b1111 = 0b11100001 which fits in 8 bits, but 0b1000 * 0b1000 = 0b01000000 which fits in 7 bits. The code rounds up to the nearest word size, so the bug will only be triggered when the worst case number of bits is 1 modulo 32 and at the same time the actual number of bits is 0 modulo 32, for the result.

In my sample code, the modulus is 0x45454545... and at some point during calculate_rinv, the modulus times 3 is being calculated, which is 0xcfcfcfcf..., which only requires 1 extra bit, not 2, and hence fits in one word less than the worst case.

[mahavirj]

@Emill Thanks for sharing detailed report and a probable fix. In-fact, we have been running into similar failure internally and were trying to narrow it down. We will do further analysis and create a fix for this.

[Emill]

@laukik-hase thanks for the fix!
However, the expression

assert((z_words >= mpi_words(Z)) && (z_words - mpi_words(Z) <= (size_t)1));

is a bit redundant. The left hand side of && can be removed due to unsigned arithmetic. If you still want to make it explicit and more clear, you should keep the result of mpi_words(Z) in a local variable and compare to that variable, to avoid the recomputation of mpi_words(Z).