Exploiting remote timing attacks

We’ll be giving a Blackhat talk on exploiting remote timing attacks. Our goal is to convince developers that this class of attack is exploitable and worth fixing. This article in Computer World gives a decent background.

The attack is very simple. You repeatedly send guesses about a secret value to the server, which rejects them as incorrect. However, if your first byte of the guess is correct, it takes a very slightly longer time to return the error. With many measurements and some filtering, you can distinguish this difference.

While any comparison against a secret is a potential target, we chose HMAC comparison for a few reasons. An HMAC is a message authenticator, similar to a digital signature. The primary difference is that the the verifying party must keep the true HMAC secret since it gives the attacker the correct authenticator for their forged message. HMACs are used in many protocols, including most web authentication frameworks such as OAuth and OpenID and HTTP session cookies.

Guessing the correct HMAC for an arbitrary message is game over for these authentication frameworks. The token grants access to resources or allows the attacker to assume a user’s identity on various websites.

This is not a new attack. Remote timing attacks on OpenSSL were shown to be practical in 2003. Further research in 2007 showed that differences as small as 20 microseconds over the Internet and 100 nanoseconds over the LAN could be distinguished with about 1000 samples.

We (and others) have been reporting these flaws for over a year and raising developer awareness. In 2009, we found a timing leak in Google Keyczar‘s HMAC verification that was quickly fixed. Coda Hale found a similar flaw in Java’s MessageDigest implementation. The OAuth group discussed his bug back then and some maintainers decided to fix it in their code too. But many didn’t.

A quick review of OAuth and OpenID implementations showed many had timing leaks that were potentially exploitable. Either developers knew about the bug and gave it a low priority or they weren’t aware of it. Either way, we thought some concrete research was needed to show exactly how easy or hard it was to exploit these flaws in various environments.

Exploiting timing attacks depends on extracting a timing difference from many samples by filtering out the effect of noise. If there is too much noise (the difference is too small), this attack may take too long to be practical. But an attacker who can control the environment to decrease noise (say, by blocking competing users of the server), accurately model the noise and thus filter it better, or just wait longer because their target is so valuable might be successful.

Our talk builds most closely on the Crosby 2007 paper mentioned above. We have tested many configurations to find how different variables influence an attacker. The most obvious analysis is how small a time delta can be distinguished for a given number of samples. This was performed from various vantage points (guest-to-guest VM, LAN, Internet) and for various languages (C, Python, Ruby, Java, etc.)

We applied various filtering methods to the samples to see how much unfiltered jitter remained. This would determine how small a difference could be distinguished. We added in other variables such as competing load, power management, and other factors.

The talk will have the full results. Both the proponents and skeptics should be surprised in some way. We have found some configurations that are almost certainly not exploitable and others that certainly are. If you’re the maintainer of a software package, don’t count on your users being safe from timing attacks because of your assumptions. Cryptographic software, especially open-source, is deployed in everything from slow embedded servers on up to multi-Ghz clusters.

Likewise, attackers often have a better vantage point than you’d first assume. With shared hosting providers and cloud computing, you have to assume attackers can locate themselves on the same host as their target. Even in a shared datacenter, you may assume the attacker has a LAN-equivalent vantage point.

Given that it is difficult to rule out timing attacks and the fix is so simple, we think it’s best to fix them proactively. The approach that is easiest to gain assurance is to use a constant-time compare function. (That post also gives reasons why other approaches don’t work or are too complicated to verify).

We hope our talk will give some concrete results so that more developers will take this flaw seriously. See you in Vegas!