Timeless timing attacks

By Jamie Kawahara, senior software engineer at Ontra

One of the great benefits of working at Ontra is our annual continuing education stipend, which we can use towards educational material and activities such as books, classes, and attending conferences. I’ve always wanted to learn more about information security, so I decided to attend Defcon — the world’s largest hacker conference.

Although I attended the conference virtually rather than in-person in Las Vegas, I was still a bit wary about what I was in for. All I had heard before  were things like “anything that can be hacked will be hacked, so trust no one,” or “the safest thing to do is not bring any electronic devices at all.”  

It turned out to be a relatively normal conference (at least virtually). Defcon featured presentations from top information security professionals and ethical hackers (called “White Hats”) on the latest security exploits they researched and developed that year. I found Tom Van Goethem and Mathy Vanhoef’s presentation titled “Timeless Timing Attacks” particularly interesting. That’s what I’d like to talk about today (you can watch their entire talk here).

What is a timing attack?

Let’s say we built an application that asks users to enter a password when they log in. The app checks that the password they entered matches the password we have saved for that user. Now, presume that the algorithm we use to check if the two passwords match goes as follows:

1. First, check if the lengths of the two passwords are the same. If not, deny access.
2. Check if the first characters respectively are the same. If not, deny access.
3. Check if the second characters respectively are the same. If not, deny access.
4. Continue checking all the characters. If you can reach the end without a mismatch, the passwords match, and the user is logged in.

This algorithm is vulnerable to a timing attack, which would go like this:

1. The hacker first needs to determine the length of the password. They start by trying one character (“a,” for example) and measure the time it took for our app to deny access.  
2. Then they try two characters (“aa,” for example) and notice it took the same amount of time for denial.
3. They repeat this until they’ve tried, for example, ten characters and notice that it took slightly longer for access denial.

Because it took slightly longer to receive a denial of access when trying ten characters, they can deduce that the password must be ten characters long. This is because when they enter the correct number of characters, it satisfies Step 1 in our app’s logical flow. Then, our app proceeds to perform Step 2, which checks if the first characters match. Since our app now needs to perform this second step, it takes slightly longer for it to respond with a denial of access. This time increase is the clue that the hacker uses to determine that they have made a correct guess.

The hacker would then determine the password’s characters in the same fashion. To determine the first character, they would start by trying all characters allowed for a password one at a time. So, for example, they could start with a ten-character string that begins with “a,” then one that begins with “b,” and so on down the alphabet. Whatever character takes the longest to return a denial of access is the correct first character.  This is because when the first characters match, it satisfies Step 2 in our app’s logical flow, and our app proceeds to execute Step 3, checking the second characters and thereby taking longer to respond. The process would repeat like this to determine the rest of the characters.

The way to modify our password checking algorithm so it is immune to timing attacks is to make it continue to check the entire string of characters, regardless of whether it found a mismatch. That way, there is no time difference between checking a correct password and checking a wrong password.

Spectre — more than just a Bond villain

The most powerful timing attack in history was the Spectre vulnerability. Spectre was discovered independently in 2018 by Jann Horn from Google’s Project Zero and Paul Kocher in collaboration with Daniel Genkin, Mike Hamburg, Moritz Lipp, and Yuval Yarom. They discovered and proved that all modern CPUs could be tricked into caching secret information, which could be deciphered with a timing attack.  

Spectre was remarkable because it exploited a fundamental feature of how all modern CPUs work; therefore, it affected every computer made since 1995. Mitigating the vulnerabilities required months of secretive work by all major CPU, operating system, and cloud vendors. Experts continue to discover variants of Spectre to this day; its Wiki site says, “As it is not easy to fix, it will haunt us for quite some time.”

One significant limitation of timing attacks is that they are difficult to perform over the internet. Network jitter can cause responses to come back at delayed times and drown out any timing differences from the victim’s computer. That brings us to Tom Van Goethem and Mathy Vanhoef’s “Timeless” version of timing attacks, which is unaffected by network jitter and is therefore capable of being performed effectively over the internet.  

If you are confused as to why security professionals would spend their time figuring out how to make attacks more effective, remember that they are called “ethical hackers”.  Their job is to research and develop all vulnerabilities that could be possible and make them public so that the industry can be alerted and make security patches proactively.

Below is a figure from their presentation that illustrates the number of requests an attacker needs to make to a victim’s computer (located in the EU) to measure a statistically significant time difference in a traditional timing attack. The top row indicates the location of the attacker’s computer. The first column shows the timing difference in the victim’s computer that the attacker hopes to measure.  

Notice how the number of requests the attacker needs to make increases with the distance between the victim and the attacker. It also increases as the timing difference in the victim’s computer gets smaller. So, you can see that even if the attacker and victim are in the same region, timing differences of 5µs or smaller cannot be reliably detected over the internet in traditional timing attacks.

Van Goethem and Vanhoef’s solution to this problem is remarkable in its simplicity. Instead of sending each request separately and measuring the time difference, they send two requests simultaneously and observe the order in which the responses come back. This eliminates the need to measure absolute time, hence the term “Timeless.”

Attached here is a figure from their presentation which illustrates how the number of requests the attacker needs to make in a “timeless” attack gets reduced significantly. Also, the smallest reliably measurable difference is 100 nanoseconds — an order of magnitude smaller than differences measured with traditional timing attacks. Timeless attacks are also unaffected by network jitter and can be executed anywhere in the world.

Some caveats of note:

1. The attacker must ensure requests are sent simultaneously via multiplexing or encapsulation.
2. The victim’s computer needs to process requests in parallel.
3. The victim’s computer needs to immediately send the response after finishing the request.

Takeaways to remember

Timing attacks use differences in the time it takes a victim’s computer to finish requests to reveal secret information. “Timeless” timing attacks developed by Van Goethem and Vanhoef eliminate the need for measuring absolute time differences by comparing the order in which simultaneous requests get returned. Since “timeless” attacks are unaffected by network jitter, they can be executed anywhere globally and can reliably detect much smaller time differences than traditional timing attacks.