Using Node.js event loop for timing attacks

A little over 3 years ago, a few friends and I started a group called pasten to participate in the Chaos Computer Club’s Capture The Flag (CTF) competition. It is a jeopardy style CTF, where the participating teams need to solve security related challenges in various categories such as exploitation, reverse engineering, web, forensic & crypto. CTF is fun and educational, and I definitely recommend participating in it. It’s even more fun when you win, like we did this year!

This year’s competition included, amongst other challenges, a Node.js application which was susceptible to an interesting timing attack, leveraging the Node.js-specific event loop. This post walks through the challenge, explaining the risk while demonstrating how an attacker may unravel and exploit such a vulnerability. Hopefully it will also help you avoid similar vulnerabilities in your own code.

Timing attacks

Before we dig into the challenge, let’s explain what a timing attack is.

Imagine a service where, when you provide the wrong password to an existing email, the service would respond with “The fifth letter of your password is wrong, please try again”. Seems absurd, right? Giving such information lets an attacker brute-force the password one character at a time, making it trivial to break in. However, this is exactly what happens when we use naive string comparison when verifying passwords or authentication tokens.

Native string comparison, including JavaScript’s == operator, typically works by iterating the two (equal length) strings, comparing one character at a time, and stopping when a character differs. So, if I compared foo to bar, the loop would iterate once, while comparing foo to fox would compare 3 chars, taking longer to complete.

Sample vulnerable authentication function:

function isAuthenticated(user, token) {
  var correctToken = FetchUserTokenFromDB(user);
  return token === correctToken;
}

A single character comparison is pretty fast to do, but it’s slow enough. Research shows an attacker can measure events with 15-100µs accuracy across the internet, and a 100ns accuracy over a local network. Attackers can use these techniques, making these small delays quite similar to telling the user which character was wrong.

This type of attack is called a timing attack, and it can be performed each time input impacts processing time. To prevent it, we need to make the string comparison take the same amount of time regardless of the entered password, for instance by xoring the two passwords, and seeing if the result was zero.

Not vulnerable to timing attacks:

var mismatch = 0;
for (var i = 0; i < a.length; ++i) {
  mismatch |= (a.charCodeAt(i) ^ b.charCodeAt(i));
}
return mismatch;

The challenge: Sequence Hunt

Armed with this information, let’s dig into the challenge. It started with a link to a page holding the following:

Sequence HuntWelcome to my integer sequence hunt. You have to compute five numbers between 0 and 100 implementingthe algorithms below. When you think you have a correct solution, send them as GET parameters here.You can also get some info about you here.I expect a lot of load, so I built this around async IOLoops.Have Fun!

[EDIT]Someone sent me this. Since each check takes considerable time, the server now waits untilthree seconds have passed since the request came in to prevent these attacks.[/EDIT]

AlgorithmsTODO publish algorithms

The text here points to /check, where we need to send the correct parameters to get the flag, and IOLoops links to /info, which shows the following:

you are 37.120.106.140request count on your IOLoop: 1

What do we know so far?

1. There’s an unknown algorithm that takes in 5 numbers, ranging from 0 to 100

2. To get the flag we need to provide the correct numbers.

3. The algorithm’s execution time probably depends on the input, potentially allowing a timing attack.

4. The server always waits for at least 3 seconds before sending back the response, to hinder timing attacks.

Now we need to figure out how to capture the flag. Since the challenge was titled Sequence Hunt, I’ll use sequencehunt.com as a placeholder domain name in my examples, but do not send any attacks to this (unrelated) domain! You can run the vulnerable sample application I wrote. It should behave similarly to the CTF one.

Exploring

A quick confirmation shows it indeed takes about 3 seconds for a check request to return, regardless of the values we provide. This means brute-forcing all the combinations is not an option. It will require trying 100^5 (10 billion) combinations, which will take thousands of years to complete…

$ curl "https://sequencehunt.com/check?val0=1&val1=1&val2=1&val3=1&val4=1"
you are 37.120.106.140
At least one value is wrong!

$ time curl "https://sequencehunt.com/check?val0=1&val1=1&val2=1&val3=1&val4=1"
you are 37.120.106.140
At least one value is wrong!
0.00s user
0.01s system
0% cpu
3.174 total

Playing with the /info page we notice that each /check request increases the IOLoop count, and so does the /info request itself.

$ curl "https://sequencehunt.com/info"
you are 37.120.106.140<br>request count on your IOLoop: 1

$ curl "https://sequencehunt.com/info"
you are 37.120.106.140<br>request count on your IOLoop: 2

$ curl "https://sequencehunt.com/info"
you are 37.120.106.140<br>request count on your IOLoop: 3

$ curl "https://sequencehunt.com/check?val0=1&val1=1&val2=1&val3=1&val4=1"
you are 37.120.106.140<br>At least one value is wrong!

$ curl "https://sequencehunt.com/info"
you are 37.120.106.140<br>request count on your IOLoop: 5

Sending /check requests with various random numbers does not give us any statistically significant differences in timing. The algorithm apparently takes less than 3 seconds to run, and so all requests simply return in the specified minimum of 3 seconds.

However, we noticed that sending a request to /info while there’s an outstanding /check request takes considerably longer to respond - giving us a timing related hook to explore. To understand the next step, let’s take a moment to talk about Node’s event loop.

Node.js event loop

Designed with scalability in mind, Node.js (and JavaScript in general) is an asynchronous event driven framework. When a piece of code wants to call a potentially blocking action, such as opening a file or writing to the network, it registers a callback function, triggers the relevant action, and terminates. When the action completes (e.g. the file was opened), the callback event is called by the event loop.

The event-driven model is extremely scalable, as threads never sit and “wait”, but it introduces a problem when a function takes a long time to complete. Since the Node.js server runs only one thread per core (by default), such a long running function would take up the entire core, while others wait in the queue for their turn. In the browser, this is the reason for the “script taking too long to run” error message you may have encountered. On the server, it will simply make requests hang.

To better understand Node JS event loop, see the excellent talk Philip Roberts gave at JSConf, or read one of these articles.

Breaking the puzzle

In our case, the event loop provided us with the timing information we needed. As long as /check was running, the event loop didn’t regain control, making the /info request hang. In contract, the setTimeout function simply registers a scheduled event and yields control, letting /info requests to be processed quickly. I put the code for a simple server showing this effect on GitHub if you want to see the effect locally.

Now that we had a way to get timing info (also known as having a side-channel), all we needed to do is to send a /check request and, without waiting for the response, send a /info request, measuring the time it takes for it to return.

To automate the search process, and cancel out network jitter, the next step was to write a python script that, given a set of inputs:

• Opens n threads

• Sends a check request and measures the time it takes for a parallel /info request to return

• Averages the times and returns the result

I used n=5, and it proved to be enough. It might be higher depending on the quality of the internet connection and the algorithm’s timing properties. Here are the results from the first run - note the significant difference with the value 4

[0, 0, 0, 0, 0]: 0.4933500289916992
[1, 1, 1, 1, 1]: 0.3603970050811768
[2, 2, 2, 2, 2]: 0.4297104358673095
[3, 3, 3, 3, 3]: 0.4705570697784423
[4, 4, 4, 4, 4]: 0.9154952526092529 <<<<<<<<
[5, 5, 5, 5, 5]: 0.4637355804443359
[6, 6, 6, 6, 6]: 0.3557830333709716
[7, 7, 7, 7, 7]: 0.4418128013610840
[8, 8, 8, 8, 8]: 0.4297045707702637

Since the difference in timing appeared only when 4 was in the first position, the next step was to enumerate over the rest of the parameters. Second digit was found to be 12

[4, 10, 10, 10, 10]: 0.840841388702392
[4, 11, 11, 11, 11]: 0.859339499473571
[4, 12, 12, 12, 12]: 1.228700304031372 <<<<<<<<
[4, 13, 13, 13, 13]: 0.907831811904907

And so on, until we got to all the correct parameters [4, 12, 77, 98, 35]

$ curl 'https://sequencehunt.com/check?val0=4&val1=12&val2=77&val3=98&val4=35'
you are 37.120.106.140
Congratulations, here is your prize:
32C3_round_and_round_and_round_IT_goes

Flag captured.

Summary

Timing attacks are a real threat, and affect both small and big players (like Google). Even small differences in execution time can be gleaned with a fairly small sample set (in internet scale), and used by attackers to glean information and refine brute-forcing. In Node.js specifically, the event loop can be used as another signal for timing attacks.

A few tips to protect your own application from such flaws:

• When implementing authentication checks, keep the authentication process running in a constant amount of time. You can use secure-compare or other packages to achieve such constant time comparisons.

• Be sure to check they don’t have known vulnerabilities

• Test for timing vulnerabilities with tools.

Lastly, if you want to show case your own skills and take on these challenges, try participating in CCC’s Capture The Flag yourself next year!