There are several known methods for implementing AES in constant time using SIMD operations, mostly based around fast byte shuffling (for instance Hamburg and Kasper/Schwabe). Are there any similar approaches that allow a constant-time AES to be implemented using only standard C operations? The closest thing I've seen is this byte oriented AES implementation, but it uses input-dependent loops to compute logarithms and exponents for the sbox.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Generally speaking, a lookup-table can be implemented in constant time by doing it as if it was a hardware circuit.
Consider a multiplexer: this is a circuit which accepts three inputs $a$, $b$ and $c$, and yields one output $d$ which is equal to $a$ if $c = 0$, to $b$ otherwise (I am talking about single-bit values here). A multiplexer can be used to implement a $1\rightarrow1$ lookup table: set $a$ to the value of the table for a "0" input, $b$ to the value for a "1" input, and set $c$ to the actual input you want to transform.
If you store single bit values in variables, the corresponding C code looks like:
which has a constant execution time.
If you know how to implement $n\rightarrow1$ lookup tables with constant-time code, a $n+1\rightarrow1$ lookup table is obtained by isolating the last bit: you consider the two $n\rightarrow1$ sub-tables, the first one being the table you get by setting the last bit to 0 or 1, respectively. Then you use the outputs of those two sub-tables as $a$ and $b$ inputs for an extra multiplexer controlled by the last input bit. This means that a $n+1\rightarrow1$ table is just a pair of $n\rightarrow1$ tables and extra bit which decides which of the two tables we were actually talking about.
With this construction, a $8\rightarrow1$ table is implementable as a tree of 255 multiplexers like the one above. The AES S-box is an $8\rightarrow8$ table, and is applied to 16 values in parallel at each round, so you end up to having to evaluate $128\times255$ multiplexers per round.
However, with the C code above, you are actually computing several multiplexers in parallel. If the C variables are 64-bit values, then you are doing 64 multiplexers simultaneously: bits of index 0 talk to other bits of index 0, bits on index 1 with bits of index 1, and so on, up to bits of index 63. This is known as bit slicing. Due to the similarity of structure in AES, you can use that to reduce the number of multiplexer evaluations to $4\times 255$ per round: a mere thousand...
With such techniques, you can end up with a constant-time, plain C implementation of AES which should evaluate a block in, say, 20000 clock cycles. Which is awfully slow, but still doable. However, this is only the beginning. There are many optimizations which can be applied to such a structure (e.g. you can replace multiplexers with a not-exactly-a-multiplexer construction "
A google search on "bitslice implementation AES" links to a few research papers, but apparently none being publicly downloadable.
Just to complement Thomas's reply, here are a couple of papers that do not rely on SIMD registers to implement bitsliced AES:
Adding to Thomas's answer: in A depth-16 circuit for the AES S-box, Joan Boyar and Rene Peralta give a compact representation of AES tables as boolean operations, that are useful for a bitslice/SIMD implementation.