Consider using different bignum library for constant-time execution

[J08nY]

fiat-crypto could be used to generate known constant-time and correct finite-field arithmetic for selected primes which could the be used in the codegen subpackage. Using fiat-crypto instead of the current libtommath would help for analysis of the generated implementations as libtommath is not constant-time, leading to misalignment in the traces, whereas fiat-crypto is constant-time.

Doing this would mean some changes to the codegen process, as generated implementations were assumed to be curve-generic (a curve is set at runtime), while fiat-crypto needs the prime to generate the implementation. Also, fiat-crypto only implements finite-field
arithmetic and not generic big-numbers, so implementing ECDH/ECDSA/the current codegen target would need to be investigated.

[J08nY]

I looked at some more variants here. Specifically I considered BearSSL and its bignumber implementations that seem to be quite portable and offer a lot of the functionality necessary.

The issue with using BearSSL (or for that matter any constant-time bignumber implementation, or other implementations instead of libtommath) is that the bignumber API required by pyecsca is very extensive and not directly present in BearSSL. pyecsca wants to be able to choose the bignumber multiplication and squaring implementations, modular reduction technique (Montgomery/Barrett/Basic) as well as the modular inversion technique. BearSSL obviously does not implement all of those, as some are inherently not constant-time. I think no matter what single implementation is chosen there is going to only be support for a part of the bignum implementations that pyecsca requires.

There are some ways of getting around this:

1. Pick just one bignum library (e.g. libtommath) and patch/extend it to make it constant-time and cover as many implementation possibilities as possible.
2. Add support for more bignum libraries and let them support only a part of the implementation choices/bignum functions. There would also need to be some functionality to be able to tell whether the implementation choices in a given configuration are satisfiable by a given library and whether the functions are enough to implement keygen/scalarmult/ECDH/ECDSA.

Option 1 sounds like a lot of work, especially the constant-time part (as libtommath currently implements quite a lot of the implementation choices in some way the functionality part would be somewhat ok). Option 2 adds complexity to the tool and the need to support multiple libraries, but also adds some flexibility. A combination of options 1 and 2 is the strongest, but also the most work. A slightly different option is to merge options 1 and 2 into one bignum library that has it all, but that is also a huge amount of work.

All-in-all the current choice of libtommath (provided that the montgomery reduction used in it is fixed) is probably the best bang for the buck for some time. Maybe its non-constant-timeness can be investigated and improved with just a patch or two (or some specific alignment technique can be devised).

[J08nY]

Important note:

• Montgomery multiplication is much faster than base and also introduces much less variability into the runtime.
• -DBN_NON_CONST might help.