Why don't table lookups run in constant time?

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?

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...

• So lookup tables are not inherently vulnerable to timing attacks? – Melab Nov 29 '17 at 19:25
• @Melab: as above, on most modern CPUs, lookup tables are inherently vulnerable, unless you take extra precautions (e.g. always do constant access, possibly scanning the entire lookup table on any access) – poncho Nov 29 '17 at 19:30
• @SAIPeregrinus: Big O notation doesn't assume that all operations take the same amount of time; it assumes that the time variation is bounded by a constant factor (as the O eats constant factors). In this case, this is true (and the fact that the bound is a factor of 100 is not relevant to the theory - however, it is quite relevant to the practice) – poncho Nov 29 '17 at 23:03
• @Melab lookup tables are a rather abstract concept. The actual action on a modern computer is to add an offset to an address, check if that data is in a fast memory (cache) and if not, load the data (thus, not constant time). You seem to believe that the algorithmic complexity is tied to an algorithm being constant time - they are distinct concepts and it is best to divorce them in your mind. – Thomas M. DuBuisson Dec 3 '17 at 1:18
• @Melab Right. You could have secret-dependent lookup tables on a Z80 CPU and not worry about timing attacks, since that processor has no cache and every memory access takes the same amount of time. – forest Mar 3 '19 at 8:13

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

• Is there any sensible compiler except with -O0 that will actually generate code for the loop that does nothing? What you can usually do is load every entry of the table and perform arithmetic with the entry value and the index to end up selecting only the entry you want. – Squeamish Ossifrage Dec 3 '17 at 1:12
• @SqueamishOssifrage I have no idea. I checked the code first with cc -S . I didn't remove the loop. my cc is LLVM – b degnan Dec 3 '17 at 1:28
• Lemme amplify that a little bit: The technique you used in your code fragment does not work, in part because any sane compiler will optimize away the useless loop, and in part because even if it didn't there's nothing to prevent the CPU cache from having some parts of the array evicted and other parts retained, exposing exactly the same cache-timing side channel. – Squeamish Ossifrage Dec 3 '17 at 1:34
• @SqueamishOssifrage I was trying to make the simplest example possible. If you do not optimize the loop off, it will not be a problem. If you are worried, write it in assembly. If you notice, I say that you most like cannot do this successfully in the userspace. I then gave the best example I could think of for userspace. You are correct on the fact that other processes could kick out code. It would just depend on how the supervisor mode configured system. – b degnan Dec 3 '17 at 1:53
• @SqueamishOssifrage, you might get there by declaring the accesses volatile so the compiler has to generate reads every time the code says to read. Of course that still says nothing about how the processor itself interprets the instructions. – ilkkachu Dec 3 '17 at 15:08

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.

• Depending on how the if statements are structured, it might use a jump table instead of a bunch of independent comparisons and branches. Of course, not every list of if statements is compatible with being optimized as a jump table, but enough are that saying that secret-dependent if statements are always not constant time is not necessarily correct. – forest Oct 30 '18 at 0:09
• @forest Jump tables are realized as indirect branches by either loading the target address from an address table and jumping to that address, or jumping to an entry (instruction) in an instruction table. Either way, indirect branches are predicted in modern CPUs and can therefore be susceptible to timing attacks just like conditional branches. Regardless of branch prediction, a jump depending on secret data can always potentially reveal that data to a timing attack on the instruction fetch as well. – Lukas Apr 7 '20 at 2:21