# Known methods for constant time (table-free) AES implementation using 'standard' operations?

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.

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:

d = (a & ~c) | (b & c);

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 ^ (b & c)", which selects between $a$ and $a \oplus b$ ($a$ xor $b$), and is enough to implement a lookup table; also, the first row of multiplexers in a tree can often be collapsed since its inputs are known values of 0 or 1). For the DES S-boxes (eight distinct $6\rightarrow4$ tables), very optimized bitsliced implementations were designed by Matthew Kwan back in 1998. Moreover, the AES S-box has an internal algebraic structure which can probably be further exploited.