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

Question

I'm reading about bit-slicing techniques, and one thing about it caught my mind.

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

Answer 1

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;