4
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ I don't get the question's "a constant-time implementation requires a barrel shifter", or why the lack of multiplier is a problem. On CPUs with neither a constant-time multiplier nor barrel shifter, it's easier to implement constant-time multiplication and addition, if we bear the unavoidable performance penalty. Whatever risk of timing dependency there remains tends to be elsewhere (in modular reduction, and exponentiation), and AFAIK these two problems are essentially the same as for architectures with a constant time multiplier and barrel shifter. $\endgroup$ – fgrieu Feb 8 at 7:17
  • $\begingroup$ @fgrieu Most multiplication algorithms in embedded systems have timing variations due to performance considerations. I'm simply asking for information on constant-time alternatives and their performance characteristics and comparisons. $\endgroup$ – 比尔盖子 Feb 8 at 7:30
  • 1
    $\begingroup$ The Handbook of Applied Cryptography Chapter 14 might be useful for you. The chapter doesn't claim the algorithms are constant-time, but most of them are "obviously" constant time (although some appear not to be --- I have not looked through them all, but the subtraction algorithm 14.9 $x - y$ appears to leak the bit of information $x\geq y$). The book is quite old (from 1996), but I haven't found more recent sources. $\endgroup$ – Mark Feb 8 at 21:18
8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I'm no expert, however, the CPUs consist of barrel shift seems rare $\endgroup$ – kelalaka Feb 8 at 11:12
  • 2
    $\begingroup$ @kelalaka: In my experience, 8-bit CPUs and their derivatives do not have barrel shifters. However some (8051, PIC18..) have constant-time hardware multiplication (8x8->16); that can help for e.g. RC5. In modern 32-bit CPUs, anything at least a Cortex M3, and some Cortex M0, have barrel shifter and some level of hardware multiplication; but the non-constant timeness of multiplication is often an issue, and at the very least it complicates things. $\endgroup$ – fgrieu Feb 8 at 11:30
  • 2
    $\begingroup$ @kelalaka: I would expect the area cost of a barrel shiifter to depend on the number of metal layers available. It's possible to implement a 32-bit barrel shifter either as 32 one-of-32 multiplexers which can be laid out with a minimal number of wire crossings, or as five one-of-two multiplexers interconnected by shuffle-permutation networks. The latter approach will use many fewer transistors, but unless one has enough metal-interconnect layers the shuffle permutation networks will use up a lot of chip area without any transistors. $\endgroup$ – supercat Feb 8 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.