Constant Time Multiplication for Cryptography in Pure Software without Hardware Multiplier or Barrel Shifter

Question

To prevent various forms of timing side-channel attacks, it's strongly advisable to implementing public-key cryptography in constant time. Or at least, without secret-dependent timing variations. However, as far as I'm aware, such implementations rely on a constant-cycle hardware multiplier. Sometimes it's also possible to replace some multiplications with shifts and adds, still, a constant-time implementation requires a barrel shifter.

Hypothetically, if I want to implement public-key cryptography (either elliptic curve or discrete log) on the cheapest microcontrollers without either a hardware multiplier or barrel shifter, what are my options for a constant-time multiplication algorithm in pure software? Constant-time multiplication in pure software sounds like a basic enough problem and many researchers must already have investigated it, but I don't know where to look. What algorithms are available, and how do they perform comparing to their non-constant time counterpart? 10x slower? 100x slower?

An obvious solution I can imagine is using a 16-bit lookup table for 8x8 multiplication, then pretending that we have a 8-bit multiplier and proceeding from here. On an embedded system without cache, on ROM, there will be no timing variation. But are there any alternative approaches (or a variation of the LUT approach that performs better in time/space)?

To clarify my motivation, I know this is impractical in real applications (even if one is stubborn enough to do it, a crypto coprocessor would be the solution), I ask it mostly due to theoretical interests.

Answer 1

Constant-time multiplication in software without constant-time multiplier is easy. In C, this working code to compute $x\cdot y$ for 8-bit inputs is typically¹ constant-time:

unsigned mul(unsigned char x, unsigned char y) {
  unsigned r = x, s = x&-(y&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  s += (r += r)&-((y >>= 1)&1);
  return ((r+r)&-(y>>1))+s;
}

On a $b$-bit CPU, it is required $O(b)$ instructions, compared to $O(1)$ with a constant-time $b$-bit multiplier. Assembly often makes it possible to do considerably better than the obvious translation of the above code, especially on architectures without built-in 16-bit addition.

It's possible to compute $(x\,y)+z$ where $0\le z<2^b-1$ by the same method. This can be used to perform multiplication of arbitrarily large fixed-size quantities in constant time using the schoolbook algorithm, or others such a Karatsuba, translated to base $2^b$ rather than base $10$, with essentially the same $O(b)$ performance penalty compared to implementation with a constant-time multiplier.

The most serious difficulty is the same as on architectures with a constant-time multiplier: constant-time modular reduction.

I don't get how the lack of barrel shifter is an issue: in the arithmetic used in ECC cryptography, there's typically no computed shift involved, thus no opportunity that the lack of barrel shifter degenerates into a timing dependency. And the natural form of most algorithms uses shifts by one, thus a barrel shifter would not help much anyway.

---

One thing worth investigation on CPUs without hardware multiplier is Elliptic Curves over $GF(2^m)$, e.g. sect239k1. I know no reason this would be much less secure than secp224k1, and scalar multiplication no longer uses any integer multiplication, so the lack of hardware multiplier has low penalty.

---

¹ Except if the compiler introduces branches or if some of the instructions involved are not constant-time, but I've ever experienced that.