Move constant-time functions into a separate module

[gilles-peskine-arm]

There is a growing set of functions that are written to be protected against side channels that observe code and data paths. These functions are intended to be constant-time in the sense that not only does the total time taken by the function is independent of sensitive inputs, but also events such as branches and memory accesses are independent of sensitive inputs. This could also be called constant-trace.

The goal of this task is to create a new library module for these functions. The reason to have a separate module is to make reviewing, testing and static analysis simpler: if a function is in this module, it's expected to be constant-trace. Another reason to have a separate module is that we currently have some code duplication because multiple modules required identical or near-identical building blocks.

Existing constant-trace functions include (this may not be an exhaustive list!):

• mbedtls_ssl_safer_memcmp and its copies: mbedtls_nist_kw_safer_memcmp, and safer_memcmp in psa_crypto.c.
• In rsa.c: mbedtls_rsa_rsaes_pkcs1_v15_decrypt and its building blocks, apart from the call to mbedtls_rsa_private (or mbedtls_rsa_public).
• In ssl_msg.c: mbedtls_ssl_cf_hmac and its building blocks.
• In base64.c: mbedtls_base64_table_lookup and its building blocks.
• In bignum.c: mbedtls_mpi_safe_xxx and their building blocks; mbedtls_mpi_lt_mpi_ct()

Goals (to be done in the order described here, so as to facilitate review):

• Create a new library source file and add it to the build.
  For the sake of Mbed OS, the name of the new file must be sufficiently distinctive: Mbed OS's build system does not support two .c files with the same name in different subprojects.
  Do not expose any of the new functions publicly for now. Declare them only in a header file inside library.
• Rename existing functions to have a suitable name (mbedtls_<modulename>_xxx). The names should be unique except for functions that have exactly the same prototype and interface.
• Move existing constant-time code to the new file.

Follow-ups (some to be filed):

• Merge functions that have the same (or nearly the same) semantics but different interfaces.
• Unify the interfaces. For example: decide whether to output 0/1 or 0/~1, to mask uint8_t or size_t.
• Move base64 constant-time functions to the new module #4926 once Huge certificate parsing speed regression between mbedtls 2.16.9 and 2.16.10 (constant time base64). #4814 is done.

This change should not be backported to long-time support branches because we don't want to disrupt the build of long-time support versions by creating a new library source file. So we'll do it in 2.2x before it becomes an LTS, but we won't do it on 2.16.

[mpg]

I wanted to add this to the "tech debt" EPIC, but we can't put an issue in more that one EPIC. Let's leave it in "2.x pre-LTS" as I think that's accurate and conveys that we want to do it sooner rather than later, but keep it in mind when we plan work on paying out tech debt.

[mpg]

Unify the interfaces. For example: decide [...] to mask uint8_t or size_t.

I suspect this will be the hard part. Ideally we want to have masks of many types, including uint8_t, size_t and mbedtls_mpi_uint.

• We could generate the mask with the widest type and then truncate it to the desired type, but I'm not sure it's clear what the widest type is, for example between size_t and mbedtls_mpi_uint (also, we don't want to depend on a type defined in bignum.h). We could use uint64_t as the widest type, but on 32-bit platforms that's overkill and may incur an undesirable penalty in terms of code size (and perhaps less importantly, performance).
• We could use a macro, so that it can take the type as a parameter, but that doesn't work as we can't include the #pragma directives that MSVC needs inside a macro definition
• If we had C11, perhaps generics would come to the rescue, but we don't
• We could decide to to everything byte by byte, even for conditional assignments of wider types, but that's less efficient
• We could just have a family of functions, one for each type: mbedtls_cf_mpi_uint_mask(), mbedtls_cf_uint8_mask(), mbedtls_cf_size_mask(), etc.

I'm sure we'll come up with something, I just want to share my thoughts so far and point out where I think non-trivial design work with be needed.

Also, as the description says, we may also want to split and do the harder parts in a follow-up. Centralizing things and doing the trivial/easy deduplications would already be a huge win.