Timing attacks
Introduction
Basics FAQ
Overclocking FAQ
Programming FAQ

I'm writing software. What can I do to protect against timing attacks?

First of all, you need a clear idea of which variables are secret. Secrets are more than just cryptographic keys: they include plaintexts, passwords, credit-card numbers, etc. If data is or could be from the user, and you're not sure that the user wants it to be public, it's best to label it as secret.

Your objective is now to cut off all data flow from secrets to timings. At a low level, you want every instruction that the CPU executes in running your program to meet the following two goals:

In normal programming, you might sometimes think about some large-scale aspects of timing such as caches, but you probably don't think about small-scale aspects of timing such as store-to-load forwarding or cache-bank conflicts.

Obviously if (secret) do_lots_of_stuff() will take more time if secret is set than if it isn't. Less obviously, if (secret) do_x() else do_y() will take variable time, and cause other operations to take variable time, even if do_x and do_y have the same number of operations. Instead of worrying about the details, you should simply assume that the instruction pointer is public: never use secret data to control a branch, a loop condition, a function pointer, etc.

Obviously x[i] takes less time if x[i] is in cache than if it isn't. Less obviously, x[i] takes variable amounts of time for data in cache, even within the same cache line. Instead of worrying about the details, you should simply assume that all memory addresses are public: never use secret data as an array index. (You can think of this as also capturing the instruction-pointer assumption: at a low level, the instruction pointer is just another memory address.)

An easy way to catch data flow to the instruction pointer and to (other) memory addresses is to run valgrind on your compiled code, after marking all secret data as uninitialized. There are various tools to automate this, such as TIMECOP inside SUPERCOP. However, if there are code paths or data paths that weren't covered by this valgrind run, then timing variations along those paths won't be caught. There are various static-analysis tools that make more thorough guarantees; for the moment these tools are hard to use, but there are efforts to build languages and compilers with explicit secret variables, such as FaCT.

Branches and array indices are not the complete list of timing variations. For example, division instructions take variable time on typical processors, and multiplication instructions take variable time on some processors. A big step forward here is that some CPU manufacturers have recently begun promising that certain instructions will run in constant time. This information has not yet been integrated into easy-to-use tools.

What do I do if I really need to branch based on secret data?

Compute both sides of the branch, and use logical instructions (or arithmetic instructions) to select the correct results based on the secret data. For a loop with a secret iteration count, compute the loop for its maximum possible number of iterations, and use logical instructions to select the correct results based on the secret data.

Similarly, if you need to select an array entry based on secret data, read all of the array entries, using logical instructions to select the correct entry.

There are also techniques to convert divisions into simpler operations, and to convert multiplications into simpler operations. If you're persistent enough then you can build everything from logical bit operations; that's how everything is ultimately computed in hardware anyway.

Isn't that a big slowdown?

For some algorithms, yes, but there are many techniques to make it faster, and some algorithms don't suffer at all. For example, some of the fastest available software for sorting integer arrays avoids all secret branches and all secret indices.

Even the extreme case of decomposing everything into bit operations is more efficient than it might sound, since one logical CPU instruction carries out bit operations on many parallel inputs. This is called "bitslicing" and has set speed records for many useful computations.

Are there any automated tools to do these software conversions for me?

Yes. The latest work on this topic is Constantine. This won't handle algorithmic speedups, divisions, etc., but it will handle branches and indices. You should still use valgrind as a double-check.

There is also ongoing work on tools to add masking and defenses against speculative-execution attacks. These tools are currently limited in the types of software that they support, and the results are difficult to evaluate for security, but maybe these tools will stop some attacks.

The HertzBleed paper says that overclocking attacks "fundamentally undermine constant-time programming". Is that true?

No.

The constant-time discipline prohibits, systematically identifies, and systematically eliminates all data flow from secrets to timings. Configuring the CPU to vary clock frequency depending on power is a violation of this central prohibition, so whatever security problems are caused by this violation come from not following the constant-time discipline.

The constant-time discipline is the only auditable methodology available for addressing timing attacks. Part of this is software modifications to avoid having secret data leak into cycle counts, and another part is configuration changes for constant CPU frequency to avoid having secret data leak into CPU frequency (cycles per second).

Using a failure in the second part to try to excuse abandoning the first part is as counterproductive and misguided as using buffer overflows in browsers to try to excuse weak cryptography. Having secret data leak into cycle counts would add to whatever damage is caused by having secret data leak into CPU frequency.

Are there more resources on what I should do as a programmer?

Yes, many. Here are some online guides:

There are also more and more people with experience making constant-time software run fast. If you run into speed problems, ask for help!

Version: This is version 2022.06.19 of the "Programming FAQ" web page.