Bignum: Agree on an approach for scalars

[yanesca]

Context

Scalars in EC modules are both used in point operations as scalars and modular operations modulo the group order. The original approach was to represent them as an mpi_mod_residue. The representation of mpi_mod_residue is opaque and direct bit manipulation operations might not yield correct results. Alternatively bit manipulations could automatically convert, but that is prohibitively expensive. This means that the conversion would need to be done manually inside the ECP module. So far so good.

The problem is, that Montgomery keys don't fit into a mpi_mod_residue modulo the group order. They are multiplied by 2^k, where k is the cofactor of the curve (k=2 or 3). In theory these could be reduced modulo the group order and restored when needed, but that would be non-trivial, increase the attack surface and code size. Also, it would make harder to argue about the correctness of the code.

This means that we can't use mpi_mod_residue for representing scalars. (Scalars should be the same C type - at least outside of the ECP module - whether they belong to Montgomery or Weierstrass curves.)

Operations

Inside the ECP module:

• Comparison with modulus and with zero for checking validity of Weierstrass keys
• Setting bits to mask Montgomery keys
• Getting bits for scalar multiplication
• Negation for recoding of scalar (almost, it should changed 0 to p instead of leaving as 0)

Outside the ECP module:

• Modular operations (primarily multiplication) mod n
• Input/Output

Options

In either case, bit manipulation is only needed for scalars and the type would need to be aligned to the chosen one. Also, since negation is not exactly the modular negation a dedicated function would be needed whatever the type of choice is.

*Option 1 (`char`):**

• Use the keys as they are provided, without any processing, just the mandatory checks and masking
• Weierstrass and Montgomery scalars are of different byte order, the get_bit function would need to handle this
• Checking validity of Weierstrass keys would require converting to something that can do that (eg. mbedtls_mpi_uint*) and would need to allocate a temporary buffer

*Option 2 (`mbedtls_mpi_uint`):**

• Checking/validating Weierstrass keys would need a new function or breaking abstraction (calling _core functions and accessing the modulus value directly)
• need to convert for ECDSA/outside ECP (as opposed to just reading it in)
• the need for conversion is not obvious from the type
• needs to store length (number of limbs) separately
• reading Montgomery scalars needs calling _core functions or adding a new function

Option 3 (mbedtls_mpi_scalar):

• Checking/validating Weierstrass keys would need a new function or breaking abstraction (calling _core functions and accessing the modulus value directly)
• need to convert for ECDSA (as opposed to just reading it in)
• I/O would need a new function or breaking abstraction (calling _core functions and accessing the modulus value directly)
• new function would be needed for conversion to mbedtls_mpi_residue (can't think of a use case for conversion the other way)

[yanesca]

I am leaning towards Option 1:

• Montgomery and Weierstrass multiplication are handled in two separate functions anyway: in the local context the byte order will be clear and always the same.
• The temporary buffer is relatively small and could be allocated on the stack (suitable to handle the maximum curve size). The verification function doesn't have a very deep call stack (compared to the actual multiplication), this wouldn't affect the peak RAM consumption.

Can anyone think of an issue I am missing here?

[gilles-peskine-arm]

the need for conversion is not obvious from the type

This makes me dislike option 2.

The temporary buffer is relatively small and could be allocated on the stack (suitable to handle the maximum curve size)

For ECC-specific code I don't see anything wrong with allocating a bignum on the stack, or even a small number. It's only with RSA-sized numbers that a bignum on the stack is not acceptable.

Option 3 (mbedtls_mpi_scalar):

(…)
need to convert for ECDSA (as opposed to just reading it in)

Why convert? Can't mbedtls_mpi_scalar just be a struct containing a byte array (so yes, it's a conversion, but a trivial one that doesn't affect CPU or memory usage)?

[yanesca]

Why convert? Can't mbedtls_mpi_scalar just be a struct containing a byte array (so yes, it's a conversion, but a trivial one that doesn't affect CPU or memory usage)?

When I wrote Option 3, I had an mbedtls_mpi_uint* based struct in mind. But you are right, we have an Option 4 where we wrap an unsigned char*. That would make the type distinct (in the sense that passing the struct to a function taking unsigned char* wouldn't compile) and could provide static inline functions in the API for convenience and as you say wouldn't affect CPU or memory usage.

Yes, that sounds like a good idea, thanks!

[gilles-peskine-arm]

By the way, option 3/4 could potentially be a union {char[]; mpi_uint[];}, allowing modifications in place, if you have sufficient control about ownership.

[gilles-peskine-arm]

Note that there is a downside of wrapping a pointer in a struct: that tends to rule out some optimizations, like keeping the pointer in a register. So it might not be transparent to code size. In my earlier message I was thinking of wrapping an array in a struct which doesn't tend to suffer from such problems.

[yanesca]

Using a direct typedef would not rule out any optimisations, but the downside is that it would compile when a type of that variable is passed to a function expecting unsigned char*.

[yanesca]

In theory we could make it with an array, but that would mean that we are wasting some ROM with some scalars as it has to be maximum sized. So the choice seems to be an optimisation question, with what I am assuming would be relatively low impact.

[yanesca]

@gilles-peskine-arm are you happy with moving forward with Option 4 as you suggested (wrapped array variant)?

[gilles-peskine-arm]

I'm happiest with a wrapped array (option 4) if it's doable, or a wrapped pointer (option 3) if it doesn't hurt efficiency.