These are called "cache-timing attacks". In presence of caches, no memory lookup can be guaranteed to be constant time. Any memory lookups that use secret indices are thus not timing-safe, however non-secret indices are OK.

See https://cr.yp.to/antiforgery/cachetiming-20050414.pdf

Here's an implementation that doesn't use tables: https://github.com/openbsd/src/blob/master/sys/crypto/aes.c

(That implementation comes from BearSSL, whose website also has a discussion of the issue and a performance comparison[1].)

[1] https://www.bearssl.org/constanttime.html

No. At least not with modern caching (or very old page boundary crossings).

A constant time implementation has to avoid tables & compute the values directly (and slowly) or take special care to ensure that all of the table is hit/cached on each access.

> or take special care to ensure that all of the table is hit/cached on each access.

For example, by using an oblivious read: Access each row, AND it with a mask that is either all 1s or all 0s depending on if its the row you want (which you must set without branching) and OR all the results together.

Very slow.