Why don't table lookups run in constant time?

Question

The Wikipedia article on big O notation says that performing a lookup is a constant time operation. So why are lookup tables susceptible to timing attacks?

Answer 1

It mostly has to do with the real world influence of memory caches.

A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster).

Hence, if you read a location that you've read before, it goes much faster than if you read a location which you haven't; hence, you're not constant time.

Modern CPUs can process data much faster than memory can respond (perhaps by a factor of 100), hence caches are pretty much ubiquitous. Some lower end microcontrollers might not have them; but they're an exception...

Answer 2

I just wanted to extend poncho's answer as aspects of this question keep coming up. Generally speaking, you can write constant-time portions of software if you have privileged OS access, but it's not very practical. I also think it's impossible from userspace. Here's the crux of the problem:

Everyone wants their computer to be "faster"; however, it doesn't really matter how much "faster" I make things in hardware, there will always be more software to put on it. The easiest way to make something faster is to bypass the bottleneck in the system, and this has been (and will most likely always be) memory that is not on-die (for a parity process). Back in the days for the 8086 and the 68000, the CPU and the memory bus ran at the same speed. Obviously, today this is not the case. Let's say that you have a CPU that can complete an instruction in 1ns (1GHz, and this is not true due to pipelines) and your external memory latency is 4ns (250Mhz, assuming no DDR tricks, so a 1:1 mapping). In this case, you need to wait 4 cycles unless you have some buffer memory in between: enter the cache.

The cache let's you skip the access if you already happen to have that data in the cache. There are many forms of cache from direct mapped (1-way) to fully associative caches. ( used to spend 2 weeks on this topic alone due to practical hardware issues, so this is the short-short version) In the simplest form, you have something that looks like this:

The "tag" is the upper address, and the index in the row in the array. I use the last few bits for the output control. The "valid" column is a counter of some modulo. When I access the memory, I reset the counter. I did not include bits to do further control in the image. These bits can set all sort of other cache behaviors.

This is the origin of the cache timing attack. It takes me more time to go out to memory. The last time that data was constant time from memory was 30 years ago. The 80286 and 68010 both had caches, and "Big O" notation sort of went out the window with that in a practical sense.

If I want to speed up memory IO, I put a small subset of memory on die for fast, local memory; however, the issue is that I can fill it and then I run out of it. CPU's offer all sorts of cache locking, etc, but you need to have supervisor access. This means that I can put an array in cache and keep it there. When I crunch numbers, I generally cache lock the program. I then can just hammer data sets that are restricted to the speed of the bus without worrying out the IO cost of running the actual program.

The issue that this doesn't solve is the fact that interrupts can happen at any time, and even if you do not go out to memory for a cache miss, you still cannot guarantee that you will not have a hiccup in the throughput. This is why the AES-NI instructions have value; their timing is fixed cycle.

What can you actually do? Almost nothing; however, I've never seen anyone try filling the cache in userspace an then attacking it (keep in mind, I'm not a cryptographer, so I might have missed a reference). In the context of AES, you have the following code in C:

#include <stdint.h>
uint8_t s[256] = 
{
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
};

int main(void)
{
    uint32_t i;  // the counter
    uint8_t data;// a value to assign the data to
    for(i=0;i<sizeof(s);i++)  
    {
        s[i];  
    }
    data=s[6];
    return(0);
 }

If you have debugging tools (JTAG to stop the clock and peek), you will see that s[6] is pulled from the cache and not memory because I filled memory by accessing the complete array before I did the lookup. Again, this does not solve the issue of an interrupt happening, even if the cache is still filled. If you have supervisor access on the CPU, you could just disable interrupts for the time of some critical section.

It's worth noting that hardware designers do not really care about constant time execution in general. My work is generally asynchronous architectures that do not have a clock so I do nothing in constant time.

A further note on the x86 architecture: The RISC core (microcode) that is wrapped with the legacy CISC ISA makes things very complicated from a timing perspective. A useful summary in the crypto context is here: https://eprint.iacr.org/2016/086.pdf

Answer 3

Big O notation addresses the asymptotic behavior of a function. Specifically, it's an upper bound.

If $f(n)$ is $O(g(n))$ then that means there exists some coefficient $k$ such that for $n$ greater than some sufficiently large number $k \cdot g(n) \geq f(n)$.

For "constant time" it means $g(n)$ is a constant. (Not necessarily one. It doesn't matter as long as it's not zero.) $O(1)$ means that the run time has a maximum independent of $n$. Having a maximum does not mean the run time is not variable.

There also exists Big Omega, which is used to instead describe $k \cdot g(n)$ as a lower bound. Big Theta means that there exist two $k$ coefficients such that $f(n)$ is bounded below by $k_1 \cdot g(n)$ and above by $k_2 \cdot g(n)$. (Again for large values of $n$.) None of these three notations, even Big Theta, tells you whether or not $f(n)$ is strictly constant.

 

And that is just the theoretical run time of an operation. A real world implementation can run slower or faster based on various conditions^*. When a implementation of a cryptographic algorithm is said to be "constant time" it means that the run time of a function does not depend on secret data.

An implementation which is not constant time is vulnerable to timing based side channel attacks. Random-access-memory (RAM) table-based implementations are not constant time for any hardware that uses a CPU cache. The cache keeps track of memory access patterns so that it can bypass slow uncached RAM lookups. As a result, any implementation that performs memory accesses based on secret data runs the risk of that data being revealed.

Similarly, secret-dependent if statements are not constant time because of branch prediction. Loops are not necessarily constant time because their run time obviously varies if the number of iterations they make varies. And individual CPU instructions, like multiplication, may not be constant time.

However, an implementation is not automatically variable-time just because it uses one of these operations. A constant time implementation can still use these operations if they depend only on non-secret information.

For example, a table look up for round specific constants is safe. Table-based implementations of S-boxes (like in AES), however, are not constant time because the lookup index depends on secret data (keys and plaintext).

_{* Some of these variations in run time can be normal and benign. Context switching could slow down your cryptography program, but its timing probably doesn't leak secret information. Your CPU might adjust its clock speed to avoid overheating. These things probably have nothing to do with plaintext or keys, and so the variability they cause likely isn't harmful, but side channel attacks can get really creative.}