Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
If you are interested in an efficient constant time implementation of AES, you can take a look at NaCl. –  j.p. Dec 2 '11 at 10:06
add comment

3 Answers

up vote 13 down vote accepted

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→1 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→1 lookup tables with constant-time code, a n+1→1 lookup table is obtained by isolating the last bit: you consider the two n→1 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->1 table is just a pair of n→1 tables and extra bit which decides which of the two tables we were actually talking about.

With this construction, a 8→1 table is implementable as a tree of 255 multiplexers like the one above. The AES S-box is an 8→8 table, and is applied to 16 values in parallel at each round, so you end up to having to evaluate 128*255 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*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 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→4 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.

A google search on "bitslice implementation AES" links to a few research papers, but apparently none being publicly downloadable.

share|improve this answer
add comment

Just to complement Thomas's reply, here are a couple of papers that do not rely on SIMD registers to implement bitsliced AES:

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.