Performance Regression in RSA Test Suite (v3.6.4 → v3.6.5)

[Ashish285]

Summary

Hey all,

I am testing mbedtls 3.6.5 and encountered a significant performance regression between v3.6.4 and v3.6.5 with RSA test suite, with approximately 35% increase in execution time (1.37s → 1.85s) for identical test coverage (250/250 tests passed).

I noticed the v3.6.5 release notes mention a fix for the SSBleed/M-Step timing side-channel vulnerability. I assume this performance change is the intentional cost of the mitigation, but I wanted to confirm if this is expected and understand if any optimizations are possible.

System information

Mbed TLS version (number or commit id): v3.6.4 (baseline) vs v3.6.5 (regression)
Operating system and version: macOS (Apple Silicon M3)
Configuration (if not default, please attach mbedtls_config.h): Default configuration
Compiler and options (if you used a pre-built binary, please indicate how you obtained it): Default compiler (clang on macOS)

Expected behavior

I was expecting a minor release to not have a significant performance penalty.

Actual behavior

Metric	v3.6.4	v3.6.5	% Change
Elapsed Time	1.37s	1.85s	+35.0%
User CPU Time	1.36s	1.84s	+35.3%
System Time	0.01s	0.01s	0%

Steps to reproduce

# v3.6.4
git clone https://github.com/Mbed-TLS/mbedtls.git && cd mbedtls
git checkout v3.6.4 && make clean && make
gtime -f "\nElapsed: %e seconds\nUser: %U\nSys: %S" ./tests/test_suite_rsa

# v3.6.5  
git checkout v3.6.5 && make clean && make
gtime -f "\nElapsed: %e seconds\nUser: %U\nSys: %S" ./tests/test_suite_rsa

Result: v3.6.5 takes ~35% longer than v3.6.4

Additional information

Questions:

1. Is this the expected cost of the SSBleed/M-Step mitigation?
2. Are there optimization opportunities to reduce the impact while maintaining security?
3. Could there be configuration options for different threat models (e.g., MBEDTLS_ALLOW_VARIABLE_TIME_FOR_PERFORMANCE for systems not vulnerable to SSBleed/M-Step)?
4. Should the release notes explicitly mention this performance impact for capacity planning?

We appreciate the security fix! We're looking for confirmation this is expected, guidance on threat model applicability, and possible configuration options for controlled environments where the additional overhead may be unnecessary.

[gilles-peskine-arm]

The SSBleed/M-Step mitigation does have a performance cost, for both RSA key generation and private-key operations. Performance varies a lot depending on platform details, even runtime details (something as minor as loading a function or data structure on a cache line boundary vs in the middle of a cache line can have a measureable impact), so it's impossible to give generic numbers. But +35% seems within reasonable expectations to me, considering the nature of the patch.

I'm not aware of improvements. As far as I know, we followed the state of the art in constant-time GCD and modular inverse. @mpg may have ideas though.

We have occasionally considered different threat models (not specifically for this particular patch), but we came to the conclusion that it's really hard. It would require some upfront work to set up different pieces of code with different properties, and then significant added maintenance to make sure that the less secure alternatives don't accidentally contaminate the more secure alternatives. So it's not something we intend to do in the foreseeable future except in egregious cases. (One case we do have is that the public-key RSA operation is not constant-time, which is a considerable performance improvement for an operation that's supposed to be fast, and even that makes the code more complex than we'd like.)

These days, we tend to think that the performance of RSA private-key operations is not critical: people who care about the performance of private-key operations tend to have moved to ECC. May I ask what your use case is that uses Mbed TLS where RSA private-key operations make up a significant amount of CPU power?

I take your point regarding mentioning this in release notes. In our defense, it's really hard to estimate the performance impact, since it's so variable. Unfortunately, almost all patches for side channel leakage have a performance cost, and the impact of that cost tends to be mainly about how often the affected function runs.

[Ashish285]

Hi @gilles-peskine-arm , thanks for the response.

But +35% seems within reasonable expectations to me, considering the nature of the patch.

I am also trying the same on ESP32 as well and there I see ~70% impact. I understand that other things might be impacting this and it is very hard to get any approximate impact numbers.

May I ask what your use case is that uses Mbed TLS where RSA private-key operations make up a significant amount of CPU power?

I do not have an immediate use case for RSA private-key operations but from ESP-IDF we do have some performance targets for different chips. If this performance impact is expected and there are no optimisations available at this stage then we will have to modify the performance numbers for our users.

In our defense, it's really hard to estimate the performance impact, since it's so variable.

I agree with you on this, maybe just one side note can be added that this change might include a performance penalty (although it is expected for a side channel attack fix)

[mpg]

Hi @Ashish285 and thanks for your report! I basically agree with everything Gilles said, just a few things to add.

I'm not aware of improvements. As far as I know, we followed the state of the art in constant-time GCD and modular inverse. @mpg may have ideas though.

Indeed I can't think of a way for making constant-time GCD/modinv itself faster, as you say we followed the state of the art.

However we might try changing the way we use it in RSA keygen: instead of computing d = e^-1 mod LCM(P-1, Q-1), we could use the generalized CRT: compute e^-1 mod P-1 and e^-1 mod Q-1 and then reconstruct d from that. For this to be efficient we'd need to imposed that both P-1 and Q-1 are 2 mod 4, which is allowed by the latest NIST standards.

As usual for performance, it's hard to predict it it would be better without trying it out. It would have an advantage for security too, by avoiding the use of long division (present in our current code). The main drawback is this approach only works for key generation, not for loading of incomplete RSA keys, a feature that 3.6.5 offers. So, we'd need separate code paths for key generation and key completion, which would make the code a bit larger.

May I ask what your use case is that uses Mbed TLS where RSA private-key operations make up a significant amount of CPU power?

I'll also point out that in builds with MBEDTLS_RSA_NO_CRT disabled (which it is by default), only RSA key generation and completion of incomplete keys should be affected. Once the key is generated/loaded, normal private key operations (signing, decrypting) should perform worse in 3.6.5 than they did in 3.6.4. (See the advisory - we expect only the operations that were vulnerable in a given build to become slower in the same build in 3.6.5).

The distribution between affected and unaffected operations in the test suite is probably not representative of real workloads - though I understand how it makes sense of course to use the test suite as a convenient way to measure performance.

I'll see if I can some numbers by type of operation.

I agree with you on this, maybe just one side note can be added that this change might include a performance penalty (although it is expected for a side channel attack fix)

Agreed. While including specific numbers is probably too hard, we could still include a note mentioning which operations are expected to become slower.

Also, we should remember to pay attention to this when designing fixes - here I favoured simplicity and code size by handling all cases (generation and completion) in the same way, but we should have considered whether this was a good trade-off for performance.

[mpg]

I do not have an immediate use case for RSA private-key operations but from ESP-IDF we do have some performance targets for different chips. If this performance impact is expected and there are no optimisations available at this stage then we will have to modify the performance numbers for our users.

Looking at the link, it seems your performance targets are only for public and private operations, which should not be affected in the default configuration (with MBEDTLS_RSA_NO_CRT unset).

Can you check using make -C programs test/benchmark && programs/test/benchmark rsa?

Key generation should be affected in all configurations, but I'm not observing a noticeable difference with the following silly test program:

#include <psa/crypto.h>
#include <stdio.h>

int main(void) {
    psa_crypto_init();

    psa_key_id_t key = 0;

    psa_key_attributes_t attrs = PSA_KEY_ATTRIBUTES_INIT;
    psa_set_key_type(&attrs, PSA_KEY_TYPE_RSA_KEY_PAIR);
    psa_set_key_bits(&attrs, 2048);
    psa_set_key_usage_flags(&attrs, PSA_KEY_USAGE_EXPORT);

    for (unsigned i = 0; i < 100; i++) {
        psa_status_t status = psa_generate_key(&attrs, &key);
        if (status == PSA_SUCCESS) {
            psa_destroy_key(key);
        } else {
            puts("FAILURE");
            return 1;
        }
    }
}

make library/libmbedcrypto.a && gcc -Wall -Wextra -Iinclude rsakeygen.c library/libmbedcrypto.a -o rsakeygen && time ./rsakeygen

(change the number of iterations if necessary to get a running time that makes sense to observe this way).

So, I'm starting to think the only thing that might be noticeably affected would be loading of incomplete key with rsa_complete(), which to be frank would not be our top priority (we actually removed support for that in 1.0).

Could you confirm which operation(s) are affected?

[mpg]

Note: on my laptop (6th gen i7) I can't see any difference in running time of test_suite_rsa between 3.6.4 and 3.6.5 (around 3.6 - 3.7s in both cases).

I also gave it a try on a Raspberry Pi 2 (Cortex-A7) for a change. Here I can see a difference:

• v3.6.4: test_suite_rsa runs in 28.7s (+- 0.1)
• v3.6.5: test_suite_rsa runs in 32.2s (+- 0.1) so that's about 12% slower

[Ashish285]

Hi @mpg , apologies for being late to reply here.

I also did some more tests on my end. I did the tests using this sample code.

Sample Code

#include <string.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "mbedtls/rsa.h"
#include "mbedtls/pk.h"
#include "mbedtls/entropy.h"
#include <mbedtls/ctr_drbg.h>
#include "entropy_poll.h"
#include "freertos/FreeRTOS.h"

static const char privkey_4096_buf[] = "-----BEGIN RSA PRIVATE KEY-----\n"
                                  "MIIJKAIBAAKCAgEA1blr9wfIzTylroJHxcoq+YFA765gF5vj9b6tfaPG0XQExSkjndHv5sra4ar7T+k2sBB4OcKKeGHkNk6wk8tGmOS79r2L74XZs1eB0UruG+huV7Sd+YiWzwN8y9jGImA9hIkf1qxIvkco5WTmT7cVwUnCQ7qiiVadD/LgyeGD04yKZpzv9UJzfjXz5ITTn/ejcn7423M9qz41nhRWwK4zw1jv7IB57d1dWOCbN3RO4dvfVndCz8DOmLzJrZAkLsz39vppbIwbMqTXKFxWqzZY2xrYmnMx9p3v4hLeju7ls3fsekESonoP0C76u50wJfZWO2XcIUo4pue/jHi2o9KouhLXW/vyasplXvE6FFrBjSpsm1Nar4KQMUolEkUbO9baGcQvH9G5WOH0kwPt7AOSqM2EUPvBd7Jv0tbMI/BRZVVltC/t6WhannCM/I6nZrlNe5tie/qYlFu474jp5/tpa8RykkDxwl9whejIqd4iQbvDiP/GXgBYtDJ9VU/S2KqHJhQFLDi+F3+ewOcF391fgt1e1J2vNYLKZOfxTOl/1vJbU/2IjRWTRQ7cXnmpR/GNCRfgH2as6Z/0oknBSVephguDnO5QlveP4Cx2EOVY/A/KgDpu8PumSrlIk+YQgLxdKsXaVI6eDY4rY7q2uCJH3yIAfZJXEeD+ResUuSZltvECAwEAAQKCAgBwR89+oipOGHR6b5tBP+q/1bXFtXhqLs3eBuSiQu5qj2cKJYi+mtJMD3paYDdTThQa/ywKPDf+8n6wQTrnCj32iQRupjnkBg/O9kQPLixVoRCHJy5vL+D6tLxVY3cEDEeFX3zIjQ5SWJQVn6KXcnoNZ7CVYHGPcV9mR5TsuntFImp7aituUBDY14NgJKABRFosBqS6tZpKYo5MlCbXZy1ujUTOnNhxrIAj9yvUQFhIs/hrNpB1ELf46gWSF03LAIesyvWjvx9yxcL7QzeNDyozQbFVwvsWsvaZcIxXzw4B8RjdSV5+2V2BY4z6D6SB7R50ahjxrEqC9PFe3PQmsL9OvFjV9idYwFOhxiWXGjIm3wwFFLOj3e0TShscj2Iw+Ghd3wApvSdBZxzdjap1NHC+Q6yYU+BnivxUHcopVPPM3rsLndyRC6zfrQw/OkOlAP3bNL1hRedPRmRDOz0V1ihEpgC1VfXx6XOu4eg8xWiJgWX+BGvT5GWjfQg2hB1Jm344r3l0eLhr25dO80GIac2QGT2+WmYkXcsQ3AiqAn2VF8UB5mU+Iyh96jmSFVVltGZgfp98yFYN63/7wB++lhVQmJZwbglutng1qjQBFslIULddIHiYvF+AVvkrO3Hc2zg8rT91tbE13k06A1zlNGcQuQKLax8e+2/BNjsZU2E4uQKCAQEA7L4obKWYRHgG6j1VEDRrQU8Vkm4L11B+ZD/rsEh3q7LbzViOPv+1dZ40jX2qYScWyaefI46bukJlk/mlNv4Dh3EnSFvHPCInDM3oImCYImwUx0hkbSRyRNwlwRwx81LJzIR84cCqpNWrXXcplomUSM62ea1E1vtNSZs9Bg2OLoWvFOTPgk/xDi6ezdb6JFiId6cARup/bmZ363mg8jCq0wpTLVdUGrezfMj4GpB1uQET5xqXleumQu/04cHPOfXwpV0ikIOId/ldY/PetiRd86B32aB2Xd4fHUpxHMY+63MFmL6SsqMQJMPubv+eIrOId4HhT+nXNFBZXolT5XG5NwKCAQEA5xvvccHNyCTL0AebxD6EihWnp0/Dd0DwXWxZw0Yhhc9xa/W/QtygB6kPb35oKGvCKdm4dWCIGln03dU5D6CMNkJlbkxpo8gybz34SJ/6OvU836rBLHZXE3Xiqbe5XkdMdarA7kTEhEUqekDXPxhws9dWh0YjtAnBPpm1GQppiykI2edkiIhRgju5ghe+/UjAjxrEgCKZeAODh46hwZHERRKQN2MFUOFcOVDq+2wTJem9r3h1uBQAiZn8PDyx0rlRkwH2dZSSauVW+I713N0JGucOV7FeMO0ebioqqckh0i91ZJNH//Io8Sp8WuBsU/vcP9jT+5BDkCbc71BRO/AFFwKCAQBj4a6oeA0QBhvUw9+ZoKQHv9f4GZnBU+KfZSCJFWn39NQrhMsu5S+n2gGOGJDDwHwqxB+uHsKxCMZWciM0WmMex6ytKJucUURscIsZxespyrPRiEdmjNPxHXiISt8AK9OcB+GwVVsphERygI35Rz5aoWv3VhUPJqNrBKXwYdO06Q3/ILIz5oprU1wIuER9BSU+ZiUFxnXRHEZIAN7Yj5Piyh5hqNCBHTQK17dlbcFdNokxHdUKmYth/l8wyFYnvA21lt+4XOY8x+aQ/xjde+ZvnSozlTGbVNWHxBqI61MsfzDDStQVrhpniIqWJh6PwXM4CIII9z2mgqfR7NqKmTptAoIBAQDTYQOigmZbFvyrayoXVi8XtTLAnv3jByxR5pY7OtvSbagJ3J1w5CYim4iYq39M6TKP4KkMApy5rWl/tFQabPeRcS0gsxc0TBmFEaMTme7fGgrxcFZ6+koubHZCUN5k0sWmIeWQiKlNaY2uf7vf49TBSMXFuGtTclCjlybCnnlmZMPJuhCDqFsUyNelm15+f5pPyWXM5NiFooEc7WIZj996Zb4uSo1EKruVWONzzqe814s9AOp60SCkuoiv97uVRxbLZNItPRSmXNktQmSx/CEl0AuYPYwvJ9HbZQncfTBH9ExlDyidernjyr4uyHGMZyJN614ICy0gncsZv9ZtAd1FAoIBAA4toGPU/VcKFmK92zgO05jsg5vJzw5xeoxRWKrLg7iby6Su6BuNgaVwfYWeZuOhnXakid7FvFXKH6x44o9gyFm5bKqFhaXDzAnxzqcLeM5V+gititOsstpZCbVOoKQOhgTHyxpFNVX3E/nB8EunydWyhQMxKme//NsRroFm1vWljQKyL3zER82AzyseEpEYZoB/6g0n5uF2lR7KllxeBlINsceQ8g3JkmJTdS1hoXcyUSsZ+EgrRbCykNB5aVC5G3/W1OSZsFHbbMrYHCMnaYKwMqLmOkb11o6nOrJJ4pgHj8CVcp2TNjfy3y0Ru6RZ42b0Q+3LktJBGu9r5d04FgI=\n"
                                  "-----END RSA PRIVATE KEY-----";

static int myrand(void *rng_state, unsigned char *output, size_t len)
{
    size_t olen;
    return mbedtls_hardware_poll(rng_state, output, len, &olen);
}

int app_main()
{
    mbedtls_rsa_context *rsa = NULL;
    mbedtls_pk_context clientkey;
    struct timespec start_time, end_time;

    unsigned char orig_buf[4096 / 8];
    unsigned char encrypted_buf[4096 / 8];
    unsigned char decrypted_buf[4096 / 8];
    memset(orig_buf, 0xAA, sizeof(orig_buf));
    orig_buf[0] = 0;

    printf("Built with Mbed TLS version: %s\n", MBEDTLS_VERSION_STRING);

    mbedtls_pk_init(&clientkey);
    int res = mbedtls_pk_parse_key(&clientkey, (const uint8_t *)privkey_4096_buf, sizeof(privkey_4096_buf), NULL, 0, myrand, NULL);
    if (res != 0) {
        printf("Failed to parse private key\n");
        return -1;
    }
    rsa = mbedtls_pk_rsa(clientkey);
    if (rsa == NULL) {
        printf("Key is not an RSA key\n");
        return -1;
    }

    clock_gettime(CLOCK_MONOTONIC, &start_time);
    for (int i = 0; i < 10; i++) {
        res = mbedtls_rsa_public(rsa, orig_buf, encrypted_buf);
    }
    clock_gettime(CLOCK_MONOTONIC, &end_time);

    uint64_t elapsed_ns = (end_time.tv_sec - start_time.tv_sec) * 1000000000ULL + 
                          (end_time.tv_nsec - start_time.tv_nsec);
    double elapsed_ms = elapsed_ns / 1000000.0;

    uint64_t avg_elapsed_ns = elapsed_ns / 10;
    double avg_elapsed_ms = avg_elapsed_ns / 1000000.0;

    printf("RSA 4096 encryption time: %.3f ms (%llu ns)\n", avg_elapsed_ms, avg_elapsed_ns);
    vTaskDelay(1000 / portTICK_PERIOD_MS);
    clock_gettime(CLOCK_MONOTONIC, &start_time);
    for (int i = 0; i < 1; i++) {
        res =  mbedtls_rsa_private(rsa, myrand, NULL, encrypted_buf, decrypted_buf);
    }
    clock_gettime(CLOCK_MONOTONIC, &end_time);
    
    // Calculate elapsed time in nanoseconds
    elapsed_ns = (end_time.tv_sec - start_time.tv_sec) * 1000000000ULL + 
                          (end_time.tv_nsec - start_time.tv_nsec);
    elapsed_ms = elapsed_ns / 1000000.0;

    avg_elapsed_ns = elapsed_ns / 1;
    avg_elapsed_ms = avg_elapsed_ns / 1000000.0;

    printf("RSA 4096 decryption time: %.3f ms (%llu ns)\n", avg_elapsed_ms, avg_elapsed_ns);

    return 0;
}

Running this on my Mac also doesn't seem to have much of a difference between mbedTLS 3.6.4 and 3.6.5 but running the same on ESP32 and ESP32S3, I do see a difference

Running on ESP32S3:

Built with Mbed TLS version: 3.6.4
RSA 4096 encryption time: 4.945 ms (4944630 ns)
RSA 4096 decryption time: 185.620 ms (185620100 ns)

Built with Mbed TLS version: 3.6.5
RSA 4096 encryption time: 4.945 ms (4945190 ns)
RSA 4096 decryption time: 198.156 ms (198155920 ns)

Running on ESP32:

Built with Mbed TLS version: 3.6.4
RSA 4096 encryption time: 11.343 ms (11343300 ns)
RSA 4096 decryption time: 2562.334 ms (2562334000 ns)

Built with Mbed TLS version: 3.6.5
RSA 4096 encryption time: 11.326 ms (11326300 ns)
RSA 4096 decryption time: 4022.277 ms (4022277000 ns)

As you can see running this on ESP32 is substantially slower with mbedTLS 3.6.5. Let me know if I can share any more details or help with anything else for you to debug the issue.

Thanks!

[mpg]

@Ashish285 Thank you very much for the new data! This comes as a surprise to me, I really didn't expect rsa_private() to become slower in 3.6.5. And the slowdown if indeed quite substantial on ESP32 (+57%).

I'm re-labeling this as a bug and a regression until we understand what's going on, because the performance drop is substantial (on some platforms) and unexpected in that part of the code. Perhaps I'll change the classification again once it's understood, but I don't like such a mismatch between my expectations and the data.

Just to be sure, can you confirm that you're using the same configuration (mbedtls_config.h) with both versions?

[Ashish285]

Hi @mpg , yes, the only change was to update the mbedtls pointer to shift between mbedTLS 3.6.4 and mbedTLS 3.6.5.

Also to add in, I was able to revert the performance penalty by switching back few functions back to the 3.6.4 variant. Here is a relevant patch for it

esp_rsa_private_operation_performance.patch

Ignore the additional included sdkconfig.h, that was added to include the definition of CONFIG_MBEDTLS_RSA_COUNTERMEASURES_SSBLEED_MSTEP