Return to Revisions

In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can go (three functionally equivalent versions):

#include <stdint.h> // bring type uint8_t used for a field element

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 (uint8_t)(
    r ^( (-((s +  s )&256))>>8 & a )
    );
}

This code (Try It Online!) extensively uses a generic technique, applicable to many other languages: it moves a desired bit 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 is constant time. 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 next to the fastest portable constant-time code. However, on at-least-16-bit CPUs without a barrel shifter, it may be worth trying mult1B_shift8 which only shifts by a whole byte.

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

Note: demonstrating the absence of data-dependent timing 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: Silence any bogus compiler/tool warning on the tune of unary minus operator applied to unsigned type, result still unsigned, perhaps by changing the occurrences of -( to 0-(. Add parenthesis to satisfy any required convention.

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

Only if it is used. Some natural implementation of AES uses no field multiplication. See e.g. this code (which in general is NOT constant-time on CPUs with data cache, unless table reads are made constant time, which can't be done portably).