Difference between revisions of "Constant-time algorithms"

Revision as of 23:01, 17 October 2016

Writing crypto code was never easy. Unfortunately, nowadays you don't just have to implement the algorithms so that they give the right answers, and make sure that the random numbers are actually random: you also have to make sure that all of your secrets don't leak out the side of your program through instruction timing, an exciting menagerie of cache effects, branch-predictor state, execution unit utilization, or other side channels.

The best approach we have at the moment for avoiding this kind of leakage is 'constant-time programming'. This discipline involves ensuring that no secrets are ever used to control conditional execution (for example, branches, but also other kinds of predicated instructions are suspect and should be avoided) or used to calculate memory addresses.

There doesn't seem to be a proper place anywhere else to collect constant-time programming lore; so these pages are, for the moment, it. This is not intended to be a gentle introduction: see, for example, Peter Schwabe's excellent talk at ShmooCon 2015 (slides, video) for that.

Masking fundamentals

Making do without conditional execution just isn't going to cut it. In place of conditional assignments, we often use mask variables, which we can arrange to be either zero or all-bits-set -- i.e., two's complement −1. Then we can replace

if (cond) z = x;
else z = y;

by

/* set m_cond somehow */
z = (x&m_cond) | (y&~mcond);

The remaining trick is to set up the mask. The best way I know to do this is to start by arranging for the top bit in some variable to be set or clear according to the desired condition and then performing an arithmetic right shift; the other bits don't matter and can be anything. An arithmetic shift is often free in ARM code, and cheap in x86; unfortunately, C doesn't admit the existence of such a thing.

I'm assuming throughout that we're working with unsigned integers of some known bit width, say NBITS. Then

static inline unsigned signprop(unsigned x)
  { x >>= NBITS - 1; x ^= 1; x--; return (x); }

calculates the desired result, and will be recognized as an arithmetic right shift by both GCC and Clang. It isn't recognized by armcc, and I don't know how to write a portable arithmetic right shift which armcc will compile efficiently.

Boolean canonification

Suppose that you have a variable x you know to be zero or nonzero according to some desired condition, and you want to turn it into a mask. If we can get the nonzeroness to the topmost bit then we can use signprop above and we're done.

The following is the best I've come up but it's not very nice.

static inline unsigned nonzerop(unsigned x)
  { x |= x << 1; x >>= 1; x--; return (~signprop(x)); }

Here's how it works.

• The OR arranges for x to be not equal to 1. If x was zero to begin with, it stays zero; otherwise it has some bit set other than the bottom bit.

• The shift makes sure that the top bit is clear while preserving x's zero-ness. If the original x was zero, then it's still zero; otherwise it's some nonzero value -- but it's top bit is definitely clear.

• The decrement sets x's top bit if and only if it was zero to begin with.

• Now x is ready to be passed to signprop to turn it into a mask; only the sense is wrong, so we must invert it.

This compiles down to four (sequential) instructions, which isn't brilliantly efficient, but I don't know of a better way. Fortunately, many useful cases don't need full-on boolean canonification.