The world of security is often quite mind-blowing, in a sense that people can exploit the most innocent looking crack in a system and use it to completely undermine its security. In this blog post we’ll look at one of the most interesting types of exploits – a timing attack.

These work by recording how long a system takes to respond to specifically crafted inputs, and over a long enough time, the internal state of the system can be revealed.

Let’s look at an example

Let’s first create some example code we can use as a starting point. The following PHP code is a very lightweight example of how many login systems look, focusing specifically on the part that determines if the incoming password is correct or not (1).

if ($inputPassword === $correctPassword) {
  allowAccess();
} else {
  forbidAccess();
}

In this snippet of code, if the input password matches the correct password, the execution continues into the allowAccess function and the user is allowed to proceed. Otherwise, the user is shown some form of error message. As a theoretical construct, this seems fine, and there doesn’t appear too much wrong with this; after all, we have to check the password somewhere.

Deep dive into string comparisons

Amazingly, there is a subtle but very serious flaw in the above code, and it’s to do with string equality. To demonstrate this, let’s ask this question: how would you check if two strings are the same? The simplest way is to just loop through the characters of one string, and check them against the other. For example, does character 1 of string 1 match character 2 of string 2? If so, repeat across the length of the string until you reach the end, and if you do reach the end, the strings are the same. And what happens if you encounter a different character? Well, you just stop as you know the strings are different, and you have no need to continue checking the remaining characters.

But wait! This means that the time it takes to compare strings depends on how similar they are! So if a string is 90% correct, but differs only in the last character, it will take longer to check than a string that differs immediately in character location 1.

You can probably see where we are going with this: the more similar the strings are, the slower the comparison will be because the computer will have to check more characters.

Now, you’re probably (and rightfully) wondering if this difference is even detectable? I mean, even if where was a substantial difference in the strings, is it possible to detect this difference in any meaningful sense and exploit it? Let’s see.

How PHP compares strings

The PHP source code is freely available online. If you go through it you can see the following call chain indicating how string comparisons are achieved:

You can immediately see that that if the strings are of different length, the comparison returns false early on. But if this check passes, a call to memcmp is called which compares, byte by byte, the strings. So how does this function work? Well, memcmp is not declared in the PHP source code and is instead a function declared in a C library. You can view one implementation here, or view the screenshot of it below

You can see the problematic line highlighted – if the characters are different, the function returns immediately.

Constant time string comparisons

In general, returning as soon as it’s evident that the two strings are different is a good thing – it makes for faster programs. But in some situations, being faster leaks some internal information about the state of the program, and in the context of security, this is a problem.

The fix is when comparing strings within a security context, one should always attempt to use constant time algorithms. These are algorithms that take the same amount of time to run regardless of the length or size of the user’s input. These can be designed by not branching or changing memory/disk access behaviour based on the input. And this doesn’t just relate to string comparisons; if you are sorting a list for example, it might be necessary to use a constant time sorting algorithm.

For the case of string comparison, the fix is to simply not return as soon as the string is determined to be different, but continue comparing anyway. PHP introduced a secure, constant time comparison function called hash_equals() to accommodate this need.

Are timing attacks even practical?

Definitely, they’ve been done. In fact, in 2017 the famous Meltdown and Spectre attacks forced CPU manufacturers (including Intel, AMD, ARM, and IBM) to redesign their CPUs entirely due to several timing attack flaws. As of early 2018, almost every computer system in the world was affected by Spectre, making it the most powerful example of a timing attack in history. What did this attack allow? You could gain root access on the system.

In terms of string comparisons specifically, it’s been shown that you can remotely detect differences in time down to about 15 nanoseconds using a sample size of about 49,000

So not only are they practical, but they are happening. As a result, it’s important that those of us in the software industry understand exactly how these attacks work so we can collectively reduce the risk of them occurring, ultimately leading to a happier, and safer, internet for us all.

 

Photo by Mitchell Hollander on Unsplash

(1) In most systems, passwords are not compared directly, but either the hashes are compared or a function that compares hashes is invoked. This is often the case with token verification, password resets, etc.