Timing attacks

What's a simple example of a timing attack?

A secret cryptographic key inside your computer is a series of bits: 0s and 1s. Sometimes a 1 takes longer to process than a 0. This slightly slows down your computer's next transmission of data through the network. The timing of this transmission is visible to remote attackers watching the network. Attackers who pay close attention to timings can figure out the number of 1s in your secret key.

Wait, is that really a problem?

If this example were the whole story then it would be hard to see any reason for concern. For example, say it turns out that your latest 256-bit secret key has exactly 139 bits equal to 1; where are those 1s positioned within the 256 bits? The attacker who knows this number 139 has narrowed down the key to about 2% of the original 2256 possibilities, but that's still an extremely large number, far too many for the attacker to search through.

A closer look shows, however, that timings are much more complicated than this example suggests, revealing not just the number of 1 bits but many other interesting functions of various secret bits and other variables, often including variables that attackers can influence. Complete timing attacks work backwards from these functions to the complete secrets.

It's very easy to underestimate how complicated timings are, and how much useful information is leaked through timings. Statements along the lines of "This is a small timing leak, don't worry" are again and again followed by "Oops, that leak turns out to reveal your complete secret" after further study.

What's an example of timings revealing a complete secret?

Let's say you have an account on a server, and the server checks your login password against the correct password in the obvious way: it checks whether the first letter matches; if the first letter matches, it checks whether the second letter matches; and so on.

An attacker tries passwords EE, TT, AA, OO, II, NN, etc., and notices that TT takes slightly longer for the server to check. Aha, the first letter of the correct password must be T!

The attacker then tries passwords THH, TAA, TEE, etc., and notices that TAA takes slightly longer for the server to check. Aha, the second letter of the correct password must be A!

The attacker then tries passwords TARR, TANN, TAPP, etc. And so on. Even if your password has 20 letters in it, this attack succeeds quickly. There are only minor speed bumps from numbers and special characters.

I'm protected if the server locks my account after 3 invalid passwords, right?

Maybe. If the attacker tries 2 passwords and then you log in, is the counter reset? Also, how much money is your company willing to pay as ransom to stop an attacker from repeatedly locking all your accounts?

Computer systems have many different mechanisms that handle secrets. Most of these mechanisms operate on much higher data volumes than servers checking passwords. There have been demonstrations of correspondingly fast timing attacks, such as the 2005 Osvik–Shamir–Tromer hyperthreading attack extracting an AES disk-encryption password in 65 milliseconds. If timing attacks trigger server-visible failures (as in the password-checking example), can servers recognize those failures and deny service quickly enough, and do the denials last long enough, to stop the attack? Is it acceptable to give attackers so much power to deny service?

For many timing attacks, it isn't clear how the server could recognize that it is under attack. Some timing attacks are purely passive, simply an attacker watching the network. Proposals that try to recognize and then slow down timing attacks probably have some benefit in some corner cases but don't address the heart of the problem.

Aren't timings too noisy for the attacker to see small differences in processing time?

There are many tricks to collect extremely precise measurements, as illustrated by the 2016 Yarom–Genkin–Heninger CacheBleed attack successfully extracting a 4096-bit RSA key from single-cycle differences in processing time. There are also many tricks to influence systems so that small differences turn into large differences.

Not everything has been shown to be broken, and in general it sounds plausible that smaller differences are harder to attack, but this is very difficult to quantify and audit.

Can't the server just delay every password-checking response for exactly 1 millisecond, independently of how long the password checking took?

It's normal for computers to have many operations that they're trying to get done simultaneously. Often operations interrupt other operations, and interruptions can last for many seconds when computers run out of RAM. Building a fixed-response-time mechanism that robustly accounts for this is an open problem.

More fundamentally, when the password check finishes and switches to idling until the response time, the computer normally switches to other operations, speeding up those operations. This is often visible through the timing of those operations even if the timing of the password-checking response is controlled.

How about delaying every password-checking response for a random duration, to hide how long the password checking took?

This type of "blinding" can slow down attacks but is typically broken by statistical attacks.

The attack above exploits the fact that there is a measurable time difference between a correct guess and an incorrect guess. Over several iterations, the random duration in blinding has an average. When the attacker repeats measurements, this random average gets added to both the averages of correct guesses and incorrect guesses. Subtracting these two averages of guesses cancels out the random average, resulting in the same time difference from the original implementation.

Furthermore, this approach often fails in similar ways to the fixed-duration approach. The CPU normally behaves in a very different way when this code is in "compute mode" compared to "random delay mode".

Can't the server change how it checks passwords, always checking the same number of symbols independently of how close the passwords are, so that the computer doesn't switch to other operations?

Yes. This is an example of what's called constant-time programming. But beware that there are many details to get right: remember that it's very easy to underestimate how complicated timings are.

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