# How can bit slicing be constant time, when Mix Columns is in the cipher

The strength with bit sliced implementations are (apart from that they are fast) that they are running in constant time. This outrules side-channel attacks based on timings.

Now, my question is: How can ciphers such as AES run in constant time, when bitsliced? The MixColumns operations works in $GF(2^8)$, so whenever an eight bit from the matrix multiplication is $1$ before the multiplication, the result has to be reduced modulo the polynomial of the Galois Field to not overflow. To me that seems like, the running time of the cipher depends on the input then? (I can understand why SubBytes, ShiftRows and constant additions are constant time).

Is the solution for bit slicing to reduce (XOR) with the polynomial after every operation, or is there a smarter trick? It seems like a slowdown, since bit slicing is often done for speed. (I'm not an expert on Galois Fields either, so I'm not sure if it's okay to XOR with the polynomial after each operation, as that would be like adding a value to the result everytime)

Thanks for enlightening in advance! There is not THAT much documentation on bit slicing. It seems like everyone knows that its fast and knows it exists, but very few implementations has actually tried using it.

EDIT: It does not seem like, it would be okay to reduce with the irreducable polynomial after every multiplication. If I XOR the polynomial to a result, which 9th bit is $0$ (i.e. result does not overflow), then it will overflow since the irreducable polynomial in AES is $100011011$ (in bitform).

You can (and should) do the reduction in constant time using masking. That is, instead of using the following (non-bitsliced) pseudo-C code to do the reduction:

if ((result >> 8) & 1) {
/* bit 8 is set: clear it and flip bits 0, 1, 3 and 4 */
result ^= 0x11b;
}


you can simply do:

result ^= 0x11b * ((result >> 8) & 1);


(where your compiler may optimize the multiplication by a constant into a series of bit operations, if it's more efficient on your CPU architecture).

This can then be trivially bitsliced, e.g. like this:

/* bit0 .. bit7 store the 8 bits of the result(s), bit8 is the overflow bit */
bit0 ^= bit8;
bit1 ^= bit8;
bit3 ^= bit8;
bit4 ^= bit8;

• Thanks a lot for your answer! It was actually really trivial - just as you stated... I guess though, sometimes its about being in the right mindset first, before those things become obvious. It helped me. I have a few other questions about bit-sliced mix columns, but those are for another question. Thanks a lot! Apologies for the late answer too by the way. Started out implementing right away, when I saw your answer... So forgot to actually revert to here and say thanks for the progress it provided me! – oPolo May 10 '16 at 10:24