# How does a cache timing attack work on AES with lookup tables?

I was trying to make a software only implementation of AES (Rijndael). At first I was able to implement it using table lookups for the Galois field multiplication and also for the SBox, but, I really wanted to remove all table lookups as they are prone to cache timing attacks. But implementing the Galois field Multiplication opened new avenues of side channel attacks, and also reduced the performance drastically...

This is a sample code I use for Galois field multiplication:

uint8_t GFm(uint8_t a, uint8_t b)
{
uint8_t p = 0;
while(a&&b)
{
if(b&1)
{
p^= a;   // I realized this
branching is
vulnerable to power analysis
attacks...
}
if(a&0x80)
{
a = ((uint16_t)a<<1)^0x11b; //
We reduce by using the Rijndael
polynomial.
}else{
a <<=1;
}
b >>= 1;
}
return p;
}

• Does replacing if(b&1){p^= a;} with p = p^ (b&1)*a; offer any protection against power analysis attacks?
• Should I replace the while() with for(int i = 0; i<8; i++), to prevent the leakage of bit length of b ? (The for loop makes my implementation more slower as it has to run 8 times always.)

• Is there a way to hide the traces of table lookups... ?

• Is there an even faster method to do $$GF(2^{8})$$ multiplications? This function is crucial since I use it in calculating the multiplicative inverse of elements in $$GF(2^{8})$$ by modular exponentiation. Those multiplicative inverses will go through the affine transformation to calculate the S-box.

Every help will be greatly appreciated!!! :)

• Did you look at BearSSL? first ok, 2. not clear. 3. read all the cache lines. – kelalaka Apr 30 '20 at 12:48
• @kelalaka I will definitely look at BearSSL, Please see my edits. Can you please tell me how to read all cache lines? I mentioned the for loop as it always runs 8 times, which is exactly the size of unit8_t in bits. My guess is that if an attacker can track how many times a loop runs, he should not be able to know the position of the most significant bit on b . Is that of any use, or is while() sufficient? – Vivekanand V Apr 30 '20 at 13:00
• In the cache attack, the attacker check which cache lines are not changed. So if you read all the cache lines you don't give the attacker information. Reading all is low level programming, Pleased read Flush-and reload and similar articles. – kelalaka Apr 30 '20 at 13:05
• Also, protecting against Power Analysis Attacks is a real pain; ultimately, you need to ensure that every intermediate bit you process is uncorrelated to anything that the attacker can use. Because the attacker can query the same plaintext/ciphertext multiple times, adding this protection involves splitting up every non-public bit randomly into several bits (thresholding); this is slow (because fresh randomness needs to be applied often); that's not something you want to do unless you have to. – poncho Apr 30 '20 at 13:57
• – b degnan Apr 30 '20 at 14:20