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