Does clustering the AES Sbox look up table to 32 bit entry per index, help reduce vulnerability to cache timing attacks?

Question

I've been searching for some, easy methods to help mitigate, a cache timing attack on software AES implementations.

Currently, my implementation uses, a usual 256 byte S-box

uint8_t sbox[256] = {0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30... /* and so on*/} 

My goal as a developer, is to prevent/increase difficulty for an attacker to know the substitutions or the result of substitutions as a result of the AES SubBytes() operation.

This is a solution that I devised: Rather than using a 256 entry Sbox table, I decided to cluster the Sbox table into a 32 bit per entry table, where four bytes are grouped to form an unsigned integer, like this:

uint32_t sboxu32[64] = {0x637C777B, 0xF26B6FC5,  /* and so on */} 

Now if I want to get the S-box substitution, for a byte x : I do ExtractByte(sboxu32[x>>2], x&3) where, ExtractByte is :

#define ExtractByte(x, n) (uint8_t)(((x) >> (24 - 8 * (n))) & 0xff)

Now, this is my reason for doing this, hoping that the above modifications will help protect my implementation from cache timing attack, without impacting my performance.

For every access to the entry of sboxu32, I'm accessing the index x>>2 which is the truncated division of x by 4, Assuming that the attacker does not have any knowledge of x&3 , can the above modifications increase the difficulty for the attacker ? If the attacker knows x >> 2 , then there are 4 possibilities for the exact x and hence x&3 , Since AES operates on 16 byte blocks, I'm guessing the attacker would have to guess $4^{16}$ for the correct sequence of bytes.

• I realize that it is trivially brute forceable, but are there other methods, to, use this as a starting point, to build further camouflage my access to the actual sbox substitutions, without impacting performance?
  • Are there better performance friendly methods to mitigate side channel attacks on my AES implementation ?

Every help will be greatly appreciated!

Answer 1

The answer to this sort of question would depend greatly on your hardware (both your CPU and cache architecture).

On the other hand, I don't see this adding any protection on common hardware. When a program on (say) an Intel chip does a byte access, the CPU generally issues a read for a larger segment (often the cache line), and then extracts the desired byte from it. From the CPU's and memory's viewpoint, reading the entire line is no more expensive than reading a single byte (the memory bus is designed to pull in an entire line at once), so it might as well access it all (and so fill in the entire cache line, just in case you access other parts of that same line in the future).

So, you're doing manually (via explicit instructions) what the CPU is likely able to do automatically (and cheaper; it already has the hardware in place, and so it doesn't spend extra cycles to do so); I would expect that this is a waste of time.