# Why do crypto libs use table lookups when they're vulnerable to timing attacks?

AESEngine.java, from BouncyCastle, uses table lookups as does aes_x86core.c, in OpenSSL. But per Cache-timing attacks on AES table lookups like what OpenSSL and BouncyCastle are doing are vulnerable to timing attacks. So why would they use them?

• Note that Bouncy contains 3 different AES implementations. Aug 3 '15 at 15:35
• As far as I know this is only a problem if the adversary can push parts of the table out of cache. If the table stays in cache then table lookups are more robust against side-channel attacks than alternatives involving conditional branches. Aug 4 '15 at 11:44

I believe that it is for two reasons:

• Nontable based implementations of AES are possible, but (assuming you don't have AES-NI or something similar) are significantly slower than table based implementations (perhaps $10\times$ to $20\times$ slower)

• For a lot of uses, timing attacks aren't particularly relevant (as either the attacker can't get the start/stop times, or can't get them to the precision needed to actually perform such an attack against AES)

Remember, when we deal with side channel attacks, there are a number of attack models possible:

• At the simplest level, the attacker gets no information about the encryption process; he can (possibly) submit chosen plaintexts and ciphertexts, but the encryption operation looks like an abstract Oracle

• The attacker might get some information (to some precision) about how long the encryption process takes

• The attacker might also get some information about the memory accesses that the encryption process tables (cache-based side channel attacks)

• The attacker might get some information about the state of the electronic gates of the device during the encryption process (DPA, EM-based side channel attacks)

• The attacker might be able to cause a miscomputation during the encryption process (Fault Cryptanalysis)

• The attacker might get unfettered access to the entire encryption process (White Box Cryptography)

The countermeasures needed as you go down the stack become increasingly expensive; it sounds reasonable that an implementation will say "we'll go down this far and no farther"

• I'd only add to this very good answer that even if implemented with tables, it's possible to mitigate the ill effects. On Linux one can mlock() pages of data to memory (preventing their paging-out), and on at least some ARM processors it's possible to lock cachelines into cache. Aug 4 '15 at 1:04
• This paper presents an AES implementation that doesn't use lookup tables, but is still almost as fast as traditional implementations. It's nowhere near 10x to 20x as slow. Aug 4 '15 at 1:22
• @user54609 bitslicing is only efficient for parallelizable modes. Aug 4 '15 at 8:36
• @IwillnotexistIdonotexist Unfortunately mlock does not help here because mlock just prevents the page from being swapped to disk, it does not prevent an attacker from forcing it out of L2 cache either with explicit instruction (clflush) or by introducing cache contention. An instruction to lock cachelines into cache would do the trick however. Feb 6 '19 at 21:29