# Constant time multiplication in GF(2^8)

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?

• If you are implementing this on a device that can spare a few hundred bytes of memory, I think you can achieve constant time using a discrete logarithm table. In my simple-minded implementations zero would be a special case as a factor, but I think Dilip Sarwate's suggestion does away with that potential problem. I'm too ignorant to tell whether that opens up other side channel attacks. – Jyrki Lahtonen Jul 26 '20 at 11:09
• @JyrkiLahtonen Why do you think a discrete logarithm table would help in Galois field multiplication? – DannyNiu Jul 26 '20 at 11:21
• @DannyNiu It replaces a multiplication with addition of the logarithms, and unless I'm wrong integer addition is constant time. You need the doubled log table to avoid the need to test whether the result of the addition exceeds 255. May be the need for the ninth bit ruins the idea? – Jyrki Lahtonen Jul 26 '20 at 11:23
• Be aware that side-channel leaks are not part of the state that C compilers are required to consider, so optimization attempts by the compiler may turn any implementation into side-channel sieves. If you don't want to inspect every release to ensure the binary is secure, generate assembly from the C code once, inspect it, and build using the assembly code from then on. – Extrarius Jul 26 '20 at 14:28
• @JyrkiLahtonen: With tables you can have always problems with "cache attacks", which might be the reason for not directly using a table for the s-box. – j.p. Jul 28 '20 at 6:14

## 2 Answers

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 bitof 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.

• In Linux/GCC this function has 118 disassembly lines. Run the command objdump -Mintel -d a.out on the compiled output a.out. – kelalaka Jul 26 '20 at 17:21
• Is there any source of this code? If you wish I can extend this answer with disassembly. It clearly shows that there is no optimization around. – kelalaka Jul 26 '20 at 17:23
• @kelalaka: this source code is out of my head at time of writing. I checked that it gives the same result as other code. I use the same technique in lots of my code. – fgrieu Jul 26 '20 at 17:32

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.

• In the chat, It was mentioned that constant time cannot be achieved with C. It is one the way to achieve, and rather one has to be careful about the output by checking the assembly. – kelalaka Jul 26 '20 at 10:23