1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ So, will there be no security gain, in this scheme? :) $\endgroup$ – Vivekanand V May 16 at 15:15
  • 2
    $\begingroup$ @VivekanandV: doesn't look like it, unless you're running on non-standard hardware. Remember, if you're thinking about side channels (or performance), it is necessary to be familiar with how the hardware works (because side channels is all about what the adversary can infer from the hardware). And, in this case, the CPU hardware is designed to be quite efficient at memory reads (including reads of a single byte) $\endgroup$ – poncho May 16 at 15:21
  • $\begingroup$ Can you please suggest some methods to protect my implementation. Are there ways to add confusion to the table lookup for an attacker? $\endgroup$ – Vivekanand V May 16 at 15:23
  • $\begingroup$ I tried another method to eliminate lookup table in my implementation: #define SboxU32(x) ((0x637C777B) * (x==0) ) ^ ((0xF26B6FC5) *(x==1)) ^ .... and so on... , but it's very performance draining, since all 64 conditional statements are checked and the expression evaluated ! Can you please suggest methods to improve it ? $\endgroup$ – Vivekanand V May 16 at 17:21
  • $\begingroup$ Look up bitslicing, it's a common anti-side-channel technique. Also masking. google.com/url?q=https://eprint.iacr.org/2015/727.pdf may be of interest to you. $\endgroup$ – SAI Peregrinus May 18 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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