Constant time multiplication in GF(2^8)

Question

I am trying to implement AES in C; I would like to make it resistant to side-channel attacks but I can't implement the multiplication in constant time. My current code:

static uint8_t GF28_Mult (uint8_t Poly0, uint8_t Poly1) {
    uint8_t Result = 0;

    for (uint8_t Shift = 0; Shift < 8; Shift++) {
        if (Poly1 & 0x01)
            Result ^= Poly0;

        if (Poly0 & 0x80)
            Poly0 = (Poly0 << 1) ^ 0x1b;
        else
            Poly0 <<= 1;

        Poly1 >>= 1;
    }

    return Result;
}

Is it actually necessary to have this in constant time if GF28_Inverse is in constant time?

Answer 1

In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can be coded as one of these three functionally equivalent functions:

uint8_t mult1B_compact(uint8_t a, uint8_t b) {
    uint8_t r = 0, i = 8;
    while(i)
        r = (-(b>>--i & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    return r;
}

uint8_t mult1B_fast(uint8_t a, uint8_t b) {
    uint8_t r;
    r = (-(b>>7    ) & a);
    r = (-(b>>6 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>5 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>4 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>3 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>2 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>1 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
 return (-(b    & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
}

uint8_t mult1B_shift8(uint8_t a, uint8_t b) {
    uint16_t r,s;
        r  = (-((s = b+b)&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
        r ^= (-((s += s )&256))>>8 & a; r += r; r ^= (-(r&256))>>8 & 0x1B;
 return r ^( (-((s +  s )&256))>>8 & a);
}

Try It Online!. The first two versions extensively uses a generic technique, applicable to many other languages: it

• moves a bit of interest to the low-order bit of a byte using right-shift >>
• isolates it with & 1 if necessary,
• applies the unary operator - to change 1 to 0xFF…FF (leaving 0unchanged),
• then uses the outcome as a byte mask.

For most platforms, this generates code free from data-dependent timing variation¹. I know no exception, but still that should be checked, e.g. by inspection of the generated code, and in theory invoking/verifying considerations about what influences the execution time of an instruction on each of the target CPUs.

On many platforms, mult1B_fast (perhaps, made inline) is close to the fastest portable C code free from data-dependent timing variation. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte: the above technique is applied on the high byte 16-bit variables, hence & 1 becomes &256. Assembly language often allows further gain, including thanks to direct access to the carry bit.

Note: These techniques leave other side channels wide open, in particular power analysis.

Note: demonstrating the absence of data-dependent timing variation is very difficult in some non-compiled languages. The most minute details about the runtime environment in theory needs to be taken into account; like, what heuristic a Java JITC uses.

Note: Bogus compiler/tool warning on the tune of «unary minus operator applied to unsigned type, result still unsigned» can be silenced, perhaps by changing the occurrences of -( to 0-(. Add parenthesis to satisfy any enforced convention.

---

Is it actually necessary to have (this field multiplication code) in constant time if GF28_Inverse is in constant time?

No, because full field multiplication is not necessary (also see note¹). Except for computation of the S-box, a natural implementation of AES encryption² (including AES decryption in CTR mode) only needs field multiplication by the field element $x$, encoded 2. Using the same technique as above, that can be coded as one of:

inline uint8_t mul1B_x(uint8_t a) {
    return (-(a>>7) & 0x1B) ^ (a+a);
}

inline uint8_t mul1B_x_shift8(uint8_t a) {
    uint16_t r = a+a;
    return ((-(r & 256))>>8 & 0x1B) ^ r;
}

---

¹ For security, we do not need constant-time code, which is next to impossible to achieve on many modern computing platforms because of the various caches and background interrupt activity. It is enough that any timing variations there may be is independent of the data manipulated.

² One such natural implementation is there. It is typically free from data-dependent timing variation on CPUs without a data cache when the two 256-byte tables are aligned to a 256-byte boundary. One of these tables is replaceable by mul1B_x, the other is the S-box.

Answer 2

It's necessary to have all components in constant time for them to be side-channel-free; what's more, time isn't the only side-channel that an implementation have to be consider.

I've attempted making my implementation side-channel free, starting from finite-field multiplication:

static inline uint8_t xtime(uint16_t x)
{
    x = ((x << 1) & 0x00ff) - ((x << 1) & 0x0100);
    return (uint8_t)(x ^ ((x >> 8) & 0x1b));
}

static inline uint8_t gmul(uint8_t a, uint8_t b)
{
    register uint8_t x = 0;

    for(int i=0; i<8; a=xtime(a),i++)
        x ^= ~((1 & (b >> i)) - 1) & a;

    return x;
}

To explain what I did to make it "constant-time", I used

1. "&" bitwise-and and ">>" shift operator to obtain a single bit integer value 0 or 1.

2. Subtract the value from step 1 to obtain a all-bits-zero or all-bits-one word as mask.

3. use the mask with bitwise-and operator to conditionally apply the second operand to avoid using the ternary conditional operator.

You may also be interested in how to implement sbox in constant time.