Make mbedtls_aes_context be shallow-copyable

[jethrogb]

Issue originally raised with title: Arbitrary stack read in AES code

Originally reported to support.mbedtls@arm.com on February 12 2018, but never got a response.

mbedtls_aes_setkey_enc stores a pointer to somewhere inside the (then-current) location of mbedtls_aes_context in the same mbedtls_aes_context. When changing the address of the mbedtls_aes_context, for example by returning it from a function, the address is no longer valid. As a result, the encryption/decryption functions read arbitrary memory instead of the intended round key, ultimately returning bogus output. The sample C program below demonstrates the problem, at least on my platform. You might need to replace gethostbyname by another function that uses the stack to see the issue.

The same applies to mbedtls_ctr_drbg_context since it stores an mbedtls_aes_context inline.

I have not found any documentation that states contexts should not be moved in memory, and I've also not encountered any other types that behave badly when that's done (such moving is very common in my codebase).

The pointer in question is rk, which is required only when MBEDTLS_PADLOCK_ALIGN16 is defined. Aligned memory can't be guaranteed when moving the context. My recommended solution would be to specifically allocate aligned memory only when MBEDTLS_PADLOCK_ALIGN16 is defined and store that pointer, and in other cases just use an inline array directly.

I think the potential for actual information leakage resulting from the invalid memory reads is low, since the memory is mixed in as part of the AES algorithm.

// Compile with: gcc -Wall aestest.c -lmbedcrypto -o aestest
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <netdb.h>
#include <mbedtls/config.h>
#include <mbedtls/aes.h>

void print_block(const char* name, const unsigned char c[16]) {
    printf("%s = %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n",
        name, c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7], c[8], c[9], c[10], c[11], c[12], c[13], c[14], c[15]);
}

mbedtls_aes_context get_context() {
    unsigned char k[16] = {};
    mbedtls_aes_context ctx;

    mbedtls_aes_init( &ctx );

    assert( mbedtls_aes_setkey_enc( &ctx, k, 128 ) == 0 );
    
    return ctx;
}

void free_context(mbedtls_aes_context ctx) {
    mbedtls_aes_free( &ctx );
}

int main() {
    unsigned char p[16] = {};
    unsigned char c[16] = {};

    // inline
    unsigned char k[16] = {};
    mbedtls_aes_context ctx;

    mbedtls_aes_init( &ctx );

    assert( mbedtls_aes_setkey_enc( &ctx, k, 128 ) == 0 );
    assert( mbedtls_aes_crypt_ecb( &ctx, MBEDTLS_AES_ENCRYPT, p, c ) == 0 );
    mbedtls_aes_free( &ctx );
    print_block("ciphertext", c);

    // moving (1)
    ctx = get_context();

    assert( mbedtls_aes_crypt_ecb( &ctx, MBEDTLS_AES_ENCRYPT, p, c ) == 0 );
    free_context( ctx );
    print_block("ciphertext", c);

    // moving (2)
    ctx = get_context();

    // use the stack a little bit
    gethostbyname("localhost");

    assert( mbedtls_aes_crypt_ecb( &ctx, MBEDTLS_AES_ENCRYPT, p, c ) == 0 );
    free_context( ctx );
    print_block("ciphertext", c);

    return 0;
}

[hanno-becker]

Hi @jethrogb,

thank you for your detailed and comprehensible report, which shows that shallow copies of mbedtls_aes_context are not supported.

I am not aware of any use of shallow-copying in the library, but neither of any documentation that would explicitly forbid it. So we should either (a) add documentation stating that they are forbidden, (b) add a dedicated copy function, or (c) rewrite the context to support shallow copies.

In general I think that shallow-copying of structures containing references is a dangerous thing to do; one should really use dedicated move- or copy-routines.

Ping @gilles-peskine-arm.

Kind regards,
Hanno

[ciarmcom]

ARM Internal Ref: IOTSSL-2608

[gilles-peskine-arm]

We don't require alternative implementations to make their contexts copyable. Therefore the library doesn't guarantee in general that you can take a copy of a context and use it. This is mostly relevant in that you can't reliably make a copy of a context and use the copy independently of the original. But it also means that you can't reliably move a context in memory.

If you know that you aren't using an alternative implementation, then you can inspect the context type and figure out that most contexts are movable and copyable. The AES context, however, is not movable due to the embedded pointer.

We can't change the context type without breaking compatibility with code that makes assumptions on the context, which by our compatibility policy means waiting for a new major release of Mbed TLS. So our options are limited.

I'd like to make the library more robust, even if we don't officially say that it's ok to move a context — as you say we don't officially say that it isn't ok either. But your proposal is problematic because it breaks compatibility with the semantics of the context type. The library code uses ctx->rk on all platforms, even though it's equal to ctx->buf on most. We could change ctx->rk to be null when MBEDTLS_PADLOCK_ALIGN16 is not defined, at a tiny increase in code size, but what if there's code out there that assumes that ctx->rk points to the round keys on all platforms? If we keep ctx->rk as it is then moving wouldn't be supported on any platform unless the code that does the moving also updates ctx->rk. Providing a function mbedtls_aes_move wouldn't work for the use case of returning a structure on the stack.

[jethrogb]

Thanks for your input. Let me try to provide some more context.

In general I think that shallow-copying of structures containing references is a dangerous thing to do; one should really use dedicated move- or copy-routines.

This type of moving/copying is pretty common when using MbedTLS with another language such as C++ or Rust. C++ has the ability to run arbitrary code on move, but Rust does not.

In general moving/inline allocation is preferred since you're avoiding extraneous heap allocations.

you can inspect the context type and figure out that most contexts are movable and copyable.

NB. A lot of contexts are not copyable because they contain pointers to allocated memory that will be freed on mbedtls_*_free, which of course can only be done once.

I just remembered that a mbedtls_rsa_context contains a mbedtls_threading_mutex_t so on some platforms it may also not be moveable.

We can't change the context type without breaking compatibility with code that makes assumptions on the context, which by our compatibility policy means waiting for a new major release of Mbed TLS. So our options are limited.

Is this policy spelled out somewhere? It's never clear to me if there are any parts that are considered "internal" vs. "Public API".

Is it within the policy to make things break when adding a (default-undefined) #define? For example, MBEDTLS_MOVABLE_AES_CONTEXT? You wouldn't be able to specify both that and MBEDTLS_PADLOCK_ALIGN16.

[gilles-peskine-arm]

Regarding compatibility: our compatibility policy only applies to the default config.h. We're more relaxed with non-default options, but we still try to avoid breaking people's code. We don't have a formal definition of what this means. So we can be more flexible for a change that only affects MBEDTLS_PADLOCK_ALIGN16, but we'd still be careful, especially since it would be unexpected that enabling a hardware-related optimization would affect the high-level behavior of data structures. Which admittedly it does right now due to the alignment constraint.

For the default configuration, we're pretty conservative about what we consider to be internal. For types, we don't change the layout of a type unless it's declared in an *_internal.h header. (Our plan for Mbed TLS 3.0 is to document a lot more structures as “internal”, and so we'd only consider changing them to be an ABI change, not an API change. We don't have a date in mind for Mbed TLS 3.0.)

We can make a new compile-time option, but we tend not to like that because it adds to our testing burden. Option combinations grow exponentially with the number of options, and it's difficult to ensure that we're testing all “interesting” combinations.

[gilles-peskine-arm]

Revisiting this now that we have a firm plan for Mbed TLS 3.0 — releasing in June 2021. One of the things we're changing in Mbed TLS 3.0 is that the layout of data structures such as mbedtls_aes_context will now considered an implementation detail, so we can remove rk at any time in the 3.x series. Hence we can remove the field rk either in 3.0 or at any time in the 3.x series; this will be an ABI change but not an API change.

Additionally we need to establish the requirement on alternative implementations to not have the same problem, namely: it must be possible to move a data structure which is the context of an alternative implementation. This additional requirement is purely documentation and testing. At least the documentation part should be done in 3.0. This applies to all alt contexts, not just AES.

Thus, here is the definition of done for this task:

• Either remove rk from mbedtls_aes_context (and adapt the code that uses it accordingly), or file a new issue to do it in 3.x.
• Document that all alt contexts must be movable in memory.
• Either test that all alt-able contexts must be movable in memory, or file an issue to do it in 3.x.

[mpg]

Labeling as "size:S" based on the minimal amount of work we need to do for 3.0 (add documentation, one small code change + one issue for later, or create two issues for later). Obviously systematic testing of all alt-able contexts would be a larger size.