Move base64 constant-time functions to the new module

[gilles-peskine-arm]

#3649 (PR: #4866) moves constant-time functions to a new module. #4814 (PR: #4835) rewrites base64 constant-time functions. To allow the two to proceed in parallel, the base64 work will happen inside base64.c and the main constant-time PR not touch the base64 functions.

The goal of this task is to move base64 constant-time functions to the new module, once both #3649 and #4814 are resolved.

[mpg]

I'd like to clarify the intention here, and perhaps more generally with library/constant_time.c. My understanding is that this module was created to avoid code duplication across modules, where various modules would end up defining copies of (mostly) the same basic utility functions (such as turning 0/1 into 0/0xff...ff, etc.) by moving said basic functions to a common place.

Currently, base64.c has 3 functions that are constant-time: mbedtls_base64_mask_of_range(), mbedtls_base64_enc_char() and mbedtls_base64_dec_value(). Of these three, only the first one looks like it's of general use (return 0x00 or 0xff depending on whether a value is in a range); the other two a quite specific to base64. Was the intention of this ticket to move all three of them to constant_time.c, or just the first one?

Actually, looking at the contents of constant_time.c now I see several functions that look pretty specific to a given module, and it's not quite clear to me why they're here rather than their own module. (For example, why wouldn't mbedtls_ct_rsaes_pkcs1_v15_unpadding() be in rsa.c, built using functions from constant_time.c?) We seem to have deviated from the original intent of moving common things to one place, and instead are now moving all constant-time things to one place, even if they're highly specific to one module? Was that a conscious decision, and if so, when did it happen? (Sorry if I'm late on this.)

[gilles-peskine-arm]

My understanding is that this module was created to avoid code duplication across modules (…) We seem to have deviated from the original intent of moving common things to one place, and instead are now moving all constant-time things to one place, even if they're highly specific to one module? Was that a conscious decision, and if so, when did it happen?

See #3649. Moving common things in one place was only one of the goals. Another goal was to make validation simpler: when reviewing/analyzing/testing, we know immediately what's expected to be constant-time.

So it was a conscious decision made last year. It's not an irrevocable decision, we can revisit it.

[mpg]

Ok, so I read 3649 again, and it seems like you cited two reasons for creating a new module:

1. "to make reviewing, testing and static analysis simpler: if a function is in this module, it's expected to be constant-trace"
2. "we currently have some code duplication because multiple modules required identical or near-identical building blocks"

I was focused on the second reason, and I think I missed some of the things you see as consequences of the first reason.

I fully agree that "if it's in this module, it's expected to be constant-trace", but I don't think we need or want the converse "if it's constant-time, it's in this module" to be true. I mean, I don't think anybody is suggesting moving the implementations of ChachaPoly, all hashes, HMAC, etc. to constant-time.c, even though they're expected to be constant-trace. What if we add a bit-sliced implementation of AES, or make (more of) bignum constant-time? Generally speaking, there will be bits of constant-time code in a lot of places in the library, that can't (and IMO shouldn't) always be cleanly isolated from the rest.

For example: mbedtls_ct_hmac() is currently in constant-time.c, which IMO is wrong as it's quite specific to TLS, but the function that uses it, mbedtls_ssl_decrypt_buf() which stayed (rightfully!) in ssl_tls.c also has a a lot of non-trivial things to make the code path that end up calling mbedtls_ct_hmac() constant-time: the way the padding is checked, the entire flow of the function (making sure we don't return early), the way lengths are managed and checked... Some of those could be abstracted to functions (for example padding checking, which would also make unit tests easier), but at the end of the day there's still going to be non-trivial points in ensuring that "decrypt check legacy-CBC TLS records" happens in constant-time, and I don't think we want a mbedtls_ct_ssl_decrypt_buf_mee_cbc() function in constant-time.c (think of the dependencies if nothing else, this function work on an ssl_context, an ssl_transform and an ssl_record). (We can also talk about the handling of RSA decryption in ssl_srv.c, where the achieving constant-time behaviour changes the flow of the handshake.)

So it was a conscious decision made last year. It's not an irrevocable decision, we can revisit it.

I didn't realize at that point we might have different understandings of the decision that was being made. I thought we were all talking about moving the generic constant-time functions for a new module, which I don't think the description explicitly contradicts, and evidently you were also thinking we were all in agreement, or we'd have discussed it then.

I'd like to have a discussion about it and see if the rules need to be revisited, or perhaps just written down to avoid future misunderstandings, but right now's probably not the best time (I already spent more time writing this message than I probably should have), considering the other more urgent things on our plates. Let's talk about this later then. (Anyway, 3649 is supposed to have follow-ups.)

[gilles-peskine-arm]

Your point of view makes sense, and I think it would be reasonable to move specific-purpose functions such as mbedtls_ct_hmac and mbedtls_ct_rsaes_pkcs1_v15_unpadding back into their natural module.

I suggest doing that after we've done a pass of rationalizing core functions though. It's easier to do that with all the functions in one place.

[mpg]

Agreed! Btw, do we already have tickets to track the rationalization pass?

[gilles-peskine-arm]

No. #3649 describes some high-level objectives for these follow-ups.