Password crack [affecting OAuth and OpenID] could affect millions | Hacker News Reader

Password crack [affecting OAuth and OpenID] could affect millions

computerworld.com

74 pointschaostheory53 comments

Everyone who reads HN is smart enough to simply read the primary source for this:

http://lists.openid.net/pipermail/openid-security/2010-July/...

Follow the thread. Nate is Root Labs, Taylor works for him. This is the same vulnerability as Nate found in Google Keyczar last year, and that Coda Hale found in Rails several months ago.

Until people start handling crypto flaws the same way we handle buffer overflows, sweeping whole codebases to find and eliminate them, you can safely expect a major news story every year about some horrible pattern of abuse. Just a few months ago, Thai and Juliano at Netifera broke a bunch of Java web stacks with CBC padding oracles, another "old-news" crypto attack that was discovered in the '90s and promptly forgotten.

Wow, there are some fantastically stubborn, yet civil minds in that thread. I like Nate's reference to writing a blog post "to help people skip the standard progression of awareness to timing attacks."

"Standard progression of awareness" is a wonderful term.

The reply in question: http://lists.openid.net/pipermail/openid-security/2010-July/...

Seriously. Kudos to Nate Lawson for being so patient in explaining the vulnerability he found in the developer's code to the developers themselves.

Able to read it easily yes. Finding it during work hours - not me personally =) Good find.

Another example you can cite is people using strcmp to compare digests. I believe this was found an fixed in Netscape and then later shows up again in other SSL libraries and even the Wii's signing a decade later.

Thanks for the link. There's nothing quite as educational as watching experts discuss a topic.

Thank you very much for that link. I've been looking for more information than what the lame article gives and the link is just awesome.

Thanks.

Hi, we're the ones who were interviewed for this article. First, the article has been updated (including headline, which now reads "Authentication crack..."). The author mistakenly focused on the fact that OAuth and OpenID are used for authentication, and thus substituted "password" for "token" in his head when we explained things. I'll have to work on speaking more clearly. :-)

The attack is not new. But it's still everywhere. That's why we're giving a talk at Blackhat. We are hoping this will finally be the year people take timing attacks seriously and fix them.

The point of our talk is to give concrete numbers to let people make their own decisions about exploitability. One result is a matrix of language (C, Java, Ruby, Python, PHP) versus attacker vantage point (Internet, LAN, VM-to-VM on same host). We'll show the minimum timing delta we were able to distinguish at each point, given a certain number of samples.

The previous best results in this area were 20 microseconds Internet, 100 nanoseconds LAN with about 1000 measurements (Crosby et al). We have improved a bit on this (too soon to give exact numbers, wait for the talk).

http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf

Nearly every OAuth and OpenID library we found was vulnerable. No one has fixed these kinds of things. That's sad because they are exploitable in some configurations and as a software developer, you never fully know your customer's threat model. They could be running on Slicehost and have attackers literally on the same machine or a single server on a WAN link locked in a vault. (Usually the former more than latter.)

We hope our talk helps developers take this kind of attack more seriously but also dispel some of the FUD that these are easy. I think a good conclusion to make is "timing attacks are easier than I expected (but not easy) so it's worth fixing them."

You guys are out of control over there. Wish I could be there personally at your presentation.

You are awesome

We have improved a bit on this (too soon to give exact numbers, wait for the talk).

Can you, at this point, give us any idea whether the lower bound of 'a bit' is, say, single digit percent or a factor of two or whatever the case might be?

"On some login systems, the computer will check password characters one at a time, and kick back a "login failed" message as soon as it spots a bad character in the password. This means a computer returns a completely bad login attempt a tiny bit faster than a login where the first character in the password is correct."

This doesn't sound right to me. Aren't passwords usually checked by hashing the entire password and comparing against a hash? I don't see how software would be checking passwords one character at a time.

Yes, systems that hash passwords aren't timeable, because attackers can't "propose" a hash that is correct to the first N bytes in order to find byte N + 1.

If you are comparing literal passwords, you may have something more to be concerned about.

"Not timeable" isn't entirely accurate. There are still ways to make use of timing information; they are just not this particular textbook example.

Be more specific about the attack you're thinking of?

I may be wrong on this, but if you know the mechanism by which it's hashed, then there should be nothing stopping you from doing the hashing on your side as well, and timing the hash comparison. So if 'foo' hashes to 'abcdef' and 'bar' hashes to 'ab0012', and it takes longer for 'bar' to be checked than 'foo', that tells you something about the hash it's comparing against. Obviously in the real world this is significantly more difficult as it's tough to generate data that hashes to what you want it to, but I don't see why such an attack wouldn't be possible.

(Of course, this could be completely different than what the parent was thinking about.)

Timing leaks about a password hash can eliminate potential guesses from your dictionary, making a combined online/offline attack marginally more powerful. However, it does not directly reveal the password as it would if they were plaintext.

This was the one I had in mind.

For websites yes, but often you want to transmit the hashed value over the network. In that case it might be easier to implement the constant-time comparison.

Python:

  def is_equal(a, b):
      if len(a) != len(b):
          return False
    
      result = 0
      for x, y in zip(a, b):
          result |= x ^ y
      return result == 0

Java:

  public static boolean isEqual(byte[] a, byte[] b) {
      if (a.length != b.length) {
          return false;
      }
    
      int result = 0;
      for (int i = 0; i < a.length; i++) {
        result |= a[i] ^ b[i]
      }
      return result == 0;
  }

Code from http://codahale.com/a-lesson-in-timing-attacks/

It is a bad idea to send hashed passwords over a network. If you need a level of security beyond "passwords on the wire", use TLS.

Yes I fully agree. But sometimes you can't always use SSL/TLS (eg. for performance reasons within games). For certain requests you might want to add a hash for integrity protection and in that case absolutely use constant-time comparisons.

I might be missing something, but wouldn't that code allow to guess the password length because it returns more quickly if the length doesn't match? As far as I can see, the following would give away less information:

  def is_equal(actual, submitted):
      result = 0
      for i in range(0, len(submitted)):
          result |= ord(actual[i % len(actual)]) ^ ord(submitted[i])
      return result == 0 and len(actual) == len(submitted)

It's amusing that timing attacks work essentially like those often-mocked Hollywood movies where the computer/hacker cracks the password one character at a time.

This timing attack is really old news, but subtle enough to persist in many a project, e.g. Rails patched it in v2.3.4 Sept 09 (briefly re-introduced it this month on edge).

Will be interesting to see which of the big players were shown to be vulnerable.

This is an extremely dangerous attitude towards a vulnerability class. Rails did not fix the timing comparison of an OpenID HMAC verification; they fixed a timing bug in the HMAC comparison function of the Rails message verifier, which is used by session cookies and cannot be used for OpenID.

This misconception is dangerous because old vulnerability classes are extremely pernicious and have a terrible habit of reappearing even in code where they've been eliminated in the past. They're like weeds, or cockroaches, and require a concerted and decisive effort to eliminate.

It is simply not "old news" that most OpenID implementations made this mistake, just like it wouldn't be old news if IIS had an exploitable stack overflow in its HTTP header parsing.

"if IIS had an exploitable stack overflow in its HTTP header parsing"

Where'd that come from? That's a very interesting example to pull out of your hat.

I agree it's old news that these things are exploitable. But nobody fixed them. So either developers don't care about exploitable flaws or they aren't aware they're exploitable. The latter is the reason for the talk.

Can someone summarize if (and how) this is different from the timing attack on OAuth from last year that prompted OAuth 1.0a?

Does anyone know how feasible this kind of attack is with real world network latency and server load fluctuations? In the end it comes down to statistics, but i could imagine forging a token this way might take a very high number of failed attempts, which might then trigger other security mechanisms?

From my understanding, actually surprisingly so. Stats allow you to cope with latency and uncertainty - just ask the NTP gurus. There's a reference somewhere, but effectively these attacks are possible over surprisingly long distances/dodgy connections.

And even more so, with people potentially sitting right next to each other on services like AWS, RackSpace, etc.

See "Get off my cloud" for an example how you can exploit the allocation algorithms to intentionally locate yourself on the same machine as your target.

http://cseweb.ucsd.edu/~hovav/dist/cloudsec.pdf [pdf]

"We have shown that, even though the Internet induces significant timing jitter, we can reliably distinguish remote timing differences as low as 20µs. A LAN environment has lower timing jitter, allowing us to reliably distinguish remote timing differences as small as 100ns (possibly even smaller). These precise timing differences can be distinguished with only hundreds or possibly thousands of measurements."

http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf

Inside Amazon datacenters you also have lan-like performance.

Why should this affect OAuth? The authentication mechanism is not part of the protocol. OpenID is for authentication and OAuth for authorization.

The original post to the mailing list mentions the ruby open-id library (along with Java and Python libraries) as being vulnerable.

Checking out the code, it looks like the string comparison at the end of the check_message_signature method will leak timing info (uses rb_str_cmp internally?).

Link: http://github.com/openid/ruby-openid/blob/master/lib/openid/...

Edit: Was wrong about what could leak.

if timing is so critical to these attacks, it seems adding a tiny variable (on the order of a millisecond) in response times would completely prevent this

  "For every problem there is always a solution
   that is simple, obvious, and wrong." -- Mark Twain

I'm not an expert, but I know several people who are. Apparently the literature explains clearly why this most obvious of fixes is, as Twain predicts, wrong. The simple jitter that you can add is dealt with by statistical techniques.

As I say, I'm not an expert, but if you google this it should give you references to papers that discuss the issues.

On the second page of the article:

>Program the system to take the same amount of time to return both correct and incorrect passwords. This can be done in about six lines of code, Lawson said.

Only by introducing a delay where is none is needed.

This makes things slower for the rest of us. 1 extra millisecond per user * 8 billion users * times 10 logins a day == Lots Of Lost Man Hours, probably enough to rebuild the great pyramids of Egypt by hand every year.

Security researchers are the reason we can't have nice things. :)

The funniest part about these discussions is that we're discussing an optimization that exclusively helps attackers. Virtually all HMAC candidate hashes are correct all the way through the final byte, meaning that even in a classic short-circuited compare, you still have to read everything. In virtually all traffic, you never get to take that short circuit. The only time short-circuited comparisons ever make things faster is when an attacker is waiting for a rejection.

However, in many high-level languages == is written in C, and reimplementing it in the high-level language can be quite slow in comparison.

You know, it'd be handy if such high-level languages implemented a separate =$= operator that worked just like ==, but was timing-independent.

No. Adding noise to a signal increases the amount of filtering and the number of measurements you need to take. It doesn't eliminate the signals. The vulnerability is the signal; the fix --- a constant-time HMAC comparison function --- is to eliminate the signal.

So then is the fix as simple as removing the early "break;" statement from a strcmp?

Perhaps the fix is to comment it out and explain why. ;)

Depends on the rest of the strcmp implementation. You might still leak information such as the number of correct characters if responding to a correct character takes a different amount of time than responding to an incorrect character. Ever played Mastermind? Same theory here.

Your best bet is to generate a huge body of inputs (including the relevant special cases), and tweak the code until it takes the same amount of time for all of them.

Number of chars would matter for plaintext passwords but not HMAC. You gain no more practical advantage knowing I used SHA1 or SHA256 HMAC. Yet another reason not to use plaintext passwords.

That effectively already exists. The internet isn't instant or consistent, and this is about remote timing attacks.

The internet is Statistically consistent, which is all the attack needs.

Even if you added a random up to one second pause, that's still "Statistically consistent", it just requires far more samples to detect millisecond variations.

(delayed, but) whups, my mistake. Read that wrong.

Nate Lawson debunked this and other arguments in a blog entry linked in the thread:

http://rdist.root.org/2010/01/07/timing-independent-array-co...

Reply on news.ycombinator.com