root labs rdist

July 19, 2010

Exploiting remote timing attacks

Filed under: Crypto,Hacking,Network,Protocols,Security — Nate Lawson @ 12:19 pm

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!

9 Comments

  1. Will you be publishing any papers, slides or videos? If so, when can we expect them? :)
    I’m very interested in what you might have to say about optimized but non-constant time comparison functions.

    Comment by newsham — July 21, 2010 @ 9:31 pm

    • We’ll be publishing the slides shortly after the talk, yes. Blackhat typically posts videos also. We can’t pre-publish because we are still optimizing things up to the last minute, and it would spoil the fun.

      Comment by Nate Lawson — July 22, 2010 @ 5:10 pm

      • The slides or whitepaper haven’t made it to the Blackhat archives yet. Do you have any idea when they will appear? I’m really interested to have a read over your WP :)

        Comment by Sam — August 2, 2010 @ 5:49 pm

      • The slides will be posted soon. We’re updating them with some additional results that weren’t available at the time of the talk and adding better background material that makes more sense in print than in presentation.

        Comment by Nate Lawson — August 3, 2010 @ 1:33 pm

  2. There are even more basic versions of this attack. I’ve seen web sites where you can tell user state (invalid user name, valid but locked, and valid but incorrect password) based on timing. The code path differences, I assume are related to the number of SQL/LDAP queries run (e.g. lookup the user, if valid, look to see if they’re locked, if not locked, check the password), because the time differences often are measurable without any instrumentation.

    Comment by Jeremiah Blatz — July 24, 2010 @ 1:53 pm

    • Yes, definitely. Our talk will include lots of general information about timing attacks. HMAC comparison is only one potential timing leak, and not even the best one.

      Comment by Nate Lawson — July 26, 2010 @ 10:28 am

  3. Hello, I haven’t been able to find your paper/slides either on the BLACKHAT CD, website, or here. Will they be posted? Thank you.

    Comment by Jim — August 10, 2010 @ 4:49 pm

    • They will be posted (see above). We are adding material to make sure they read well in print since you won’t have the context of our talk.

      Comment by Nate Lawson — August 10, 2010 @ 8:06 pm

      • Hello, checking in again – any updates? I enjoyed the briefing and am looking forward to your full paper also! Thanks!

        Comment by Jim — August 31, 2010 @ 4:40 pm


RSS feed for comments on this post.

The Rubric Theme Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 81 other followers