Password crack [affecting OAuth and OpenID] could affect millions

http://www.computerworld.com/s/article/9179224/Researchers_Password_crack_could_affect_millions

by chaostheory • 16 years ago

74 53 16 years ago

thrill• 16 years ago

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

RiderOfGiraffes• 16 years ago

  "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.

ronnier• 16 years ago

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.

steveitis• 16 years ago

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. :)

tptacek7• 16 years ago

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.

snprbob86• 16 years ago

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

Groxx3• 16 years ago

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

JoeAltmaier• 16 years ago

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

shajith2• 16 years ago

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...

LiveTheDream• 16 years ago

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.

tptacek7• 16 years ago

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.

euroclydon• 16 years ago

"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.

NateLawson5• 16 years ago

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.

edanm• 16 years ago

"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.

tptacek7• 16 years ago

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.

amalcon3• 16 years ago

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

metachris3• 16 years ago

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/

tptacek7• 16 years ago

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.

callahad• 16 years ago

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.

blasdel• 16 years ago

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

brown9-2• 16 years ago

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

chaostheory• 16 years ago

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

mukyu• 16 years ago

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.

michaeltwofish• 16 years ago

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

hysterix2• 16 years ago

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.

phreeza• 16 years ago

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?

twp• 16 years ago

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.

SoftwareMaven• 16 years ago

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

metachris3• 16 years ago

"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.

meeee• 16 years ago

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

shajith2• 16 years ago

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.

xinsight• 16 years ago

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.

arihant• 16 years ago

sh1mmer• 16 years ago

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

NateLawson5• 16 years ago

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."

hysterix2• 16 years ago

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

You are awesome

pvg• 16 years ago

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?

Password crack [affecting OAuth and OpenID] could affect millions

Related Stories