# How to make an AES implementation using lookup tables immune to cache timing attacks?

I recently made a very naive implementation of AES using lookup tables, but it's totally unsafe because of timing attacks. I am not interested in using the processor specific instructions for AES, which is used practically, since I wanted to make a cool project with AES ! Is there any way to prevent my AES implementation from being insecure ?

• The easiest solution is reading all the cache lines where the keys are stored. – kelalaka Jan 12 '20 at 14:14
• @kelalaka Can you please be more clear? – Vivekanand V Jan 12 '20 at 14:40
• This was mitigation in OpenSSL or when I heard this attack I simply said this before knowing this mitigation. Cache attack uses the knowledge that you access some cache lines for the round and uses this to determine the key bit(s). Therefore if you access all your cache lines related to your lookup tables, you will be safe. – kelalaka Jan 12 '20 at 14:43
• not pertinent to how, but hardware information is here: crypto.stackexchange.com/questions/53528/… – b degnan Jan 14 '20 at 13:48

When it's possible, a solution is to ensure that table lookups at data-dependent addresses are constant-time and without action on the cache, by

• Disabling cache (use and loading/invalidation) during such table lookups. That's heavily system dependent, though. Some CPU architecture have special instructions, addressing modes, or mode bits allowing this, or allow to control which addresses can be cached.
• And ensuring that there is no other condition causing timing variations in table lookup; I'm in particular thinking of an extra cycle due to internal carry in the addition of base address and index on some CPUs. On many 8-bit CPUs, that means starting the 256-byte table at an address multiple of 256.

It is not quite as safe to:

• Flush cache before table lookup, because in some attack scenarios an adversary could examine the cache state.
• Fill cache with the full table before use, because in some attack scenarios an adversary or a coincidence could partially flush the cache.

Other techniques aim at making it impossible to measure timing dependencies. For example, we may start a timer before encryption, set to a larger value than the worst-case encryption duration, then wait precisely until expiry of the timer after encryption. With a cycle-accurate timer, and if an adversary can not induce interrupts that make the duration of the encryption vary beyond the maximum forecast, and a host of other conditions, it is conceivable that timing variations in encryption are fully hidden. Beware that this could worsen leaks by other side channels (power, electromagnetic emissions).

None of this is general and portable. Other solutions have no such drawback: they just use no table lookups at data-dependent indexes, replacing them by constant-time expressions or table tookups at data-independent adresses. That can be made portable and reasonably fast when using bitslicing; see answers to this related question.

If speed is not an issue, a slow but simple and quite portable technique goes:

uint8_t lookup(const uint8_t table[256], uint8_t index) {
unsigned j, r;
j = r = 255;
do
r ^= ((-(index ^ j)) >> 8) | table[j];
while(j--);
return (uint8_t)r;
}


This works because -(index ^ j) has bits 8 to 15 each 0 or 1 depending on if index==j or not, and the indexes in table[j] are not data-dependent.
It might be necessary to inhibit a spurious compiler warning or/by inserting 0 before -.

It is also possible to use that (c >> j) & 1 does a lookup at index j in a $$k$$-entries 1-bit table defined by $$k$$-bit constant c, in a constant-time manner on CPUs with an at-least-$$k$$-bit barrel shifter and a compiler that uses it. That combines with the above: we can select among 32 constants each 64-bit according to 5 bits of the index (perhaps unrolling the loop), then use a 64-bit barrel-shifter to extract the 8-bit result according to the remaining 3 bits of the index.

• The theoretical keyword here is probably "oblivious ram"? – SEJPM Jan 12 '20 at 14:57
• @SEJPM: I confess that I have always stared blankly at oblivious RAM papers, not understanding the connection to the physical devices (RAM, CPUs) that I use. – fgrieu Jan 12 '20 at 15:30