Branchless AES Implementation

Question

Imagine a branchless implementation of the AES-128 cipher. Are there any benefits over the implementation that contains branches, other than possible prevention of timing attacks?

Is it even true, that a branchless code can mitigate a timing attack? Are there any other side-channel attacks that are prevented in this way?

Answer 1

What makes crypto code vulnerable to timing attacks is data dependent timing variations. Branching according to a round counter, or to the key size, does not create a vulnerability. Most implementations of AES make no branch according to key or data value, and supressing other branches won't help.

The main source of data-dependent timing variations in AES is in the table lookups for the S-boxes: according to if the entry is in cache, or not, the table fetch will take different time. See for example Daniel J. Bernstein, Cache-timing attacks on AES (2004) [direct link to pdf] for more info.

Among ways to make AES code free of any timing dependencies are:

• using AES-NI or other hardware support;
• using a CPU without data cache (and being careful about alignment of the table);
• changing the S-table to a logical expression, possibly using bitslicing to regain at least some of the lost speed; unfortunately the AES S-table is rather hard to express in this way (this has been studied by Joan Boyar and René Peralta, A new combinational logic minimization technique with applications to cryptology and A depth-16 circuit for the AES S-box; here are some of their equations).