Constant-timeness in libtommath

[J08nY]

Hey all,
I am wondering what the constant-timeness situation is in libtommath.
Did anyone do any testing? Are there any claims?

[czurnieden]

To make libtommath run in constant time the following conditions must be met first:

• the basic integer mp_digit has to be used in full, that is e.g.: a 32-bit mp_digit needs to use all 32 bits not only 28
• compilers will optimize the basic operations on mp_digit in a way that may or may not be constant time which has to be taken care of
• all optimizations that are not always used have to be excluded
• check if the algorithms that have to be constant time (for encryption) are constant time

That will need quite some time to implement:

• using all bits in mp_digit is not a large problem but some algorithms relay on the fact that mp_digit has some top bits unused (e.g.: Comba multiplication/squaring). Operations on software implementations of mp_word may or may not be constant time so those cannot be used. Tedious but doable.
• it is known how to "persuade" compilers to use constant time operations. Tedious but doable.
• some of the optimizations are already in separate files and can be switched off per preprocessor directives. Tedious but doable.
• checking the algorithms for constant-timeness (is that even a word?) is not easy and might need a separate implementation of one of the proven constant-time algorithms instead. Doable but with some risk of f'ing up. Oh, and tedious, too!

All of the above will make libtommath slower. Only by a little bit? By a lot? I don't know but don't think it will be significant for the number ranges commonly used in encryption.

[J08nY]

• the basic integer mp_digit has to be used in full, that is e.g.: a 32-bit mp_digit needs to use all 32 bits not only 28

Is this necessary? For example BearSSL has several constant-time bigint implementations, one of which is i31 which uses only 31 bits out of a 32-bit int.

• checking the algorithms for constant-timeness (is that even a word?)

Becoming a word 😛. But in general this would not be that hard and can be done on the level of libtommath functions, which can be shown to be constant-time w.r.t. their inputs, sometimes even something basic like Valgrind can be used. However, something like Binsec/Rel will give stronger guarantees of constant-timeness, see here. We tried doing this for some libtommath functions using Valgrind, but fixing the leaks without proper knowledge of the library or a good plan was quite hard.

In one of our projects, we are using a subset of libtommath (not that large, generally just modular arithmetic) and while we don't care about security, the non-constant-timeness is a hassle, because we are using libtommath in (auto)generated implementations of cryptography that get simulated or executed to evaluate side-channels. While non-constant-timenesss is definitely a side-channel leak, we are not interested in it and it actually behaves as a sort of countermeasure for other attacks, like DPA.

I guess my question is, whether you can guess which of your suggested points above would bring the largest improvement?
My guess are the "special-cases" or conditional optimizations and making the bigints a fixed size (when they are field elements actually) and then always using them fully.

[czurnieden]

Is this [full use of all bits in a native type] necessary?

In theory: yes, but n-1 bits works too if some care is taken and it makes things definitely easier. Some of the problems and related code are already listed in the BearSSL link you gave.

n-4 (used here at LTM for e.g.: Comba) is, as far as I understood not usable.

[...]something like Binsec/Rel will give stronger guarantees of constant-timeness, see here.

Ah, that's very interesting, thanks for the paper!
Is Binsec usable now? Stumbled upon about a year or so ago, seemed promising but couldn't get it to work properly than.

[...] a subset of libtommath (not that large, generally just modular arithmetic)

Not all functions are needed for cryptographic use, of course but it is still a lot of work.

I guess my question is, whether you can guess which of your suggested points above would bring the largest improvement?
My guess are the "special-cases" or conditional optimizations and making the bigints a fixed size (when they are field elements actually) and then always using them fully.

That would indeed be a large step towards the goal! And the only new "function" in that case would be fixed-sized bigints. Nice.

So in no special order (although I would implement fixed bigints first) and quite roughly:

• Implement fixed-size bigints and adapt basic arithmetic to make proper use of them (they have to be interns only, the API should not change)
• Remove algorithmic optimizations (e.g.: early outs) in all modular arithmetic (per preprocessor to keep it simple)
• Check remaining code (helpers et al.) for constant-timeness (this can be automated to some degree) if they are needed for cryptographic use.
• Make make constant-time

If that's all done and dusted:

• Make native arithmetic constant time (e.g.: avoid compiler-optimizations).

That is a lot of work, although I am pretty sure it can be done before Christmas, just not the one in 2023.

But bad jokes aside: LTM gets used for cryptographic purposes by several projects and should have at least some of the standard precautions available. Current develop is, despite its name stable and should be a good starting point.

[J08nY]

Ah, that's very interesting, thanks for the paper!
Is Binsec usable now? Stumbled upon about a year or so ago, seemed promising but couldn't get it to work properly than.

Hopefully usable now. I will also try it out on libtommath.

That would indeed be a large step towards the goal! And the only new "function" in that case would be fixed-sized bigints. Nice.

Nice to know that I was not so far off. We might try again, using this approach, to make parts of libtommath more constant-time.

[J08nY]

openssl/openssl#6640 seems like a nice discussion on constant-time big numbers in OpenSSL that might have overlaps with what is happening in libtommath. Things certainly broke in libtommath when I experimented with breaking the mentioned invariant and having fixed-size bignums.