8 ms·
Password crack [affecting OAuth and OpenID] could affect millions
- LiveTheDream 16y agoThis 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.
- tptacek 16y agoThis 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 16y 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.
- NateLawson 16y agoI 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.
- thrill 16y agoif 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
- tptacek 16y agoNo. 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 16y agoSo then is the fix as simple as removing the early "break;" statement from a strcmp?
- Super_Jambo 16y agoPerhaps the fix is to comment it out and explain why. ;)
- amalcon 16y agoDepends 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.
- NateLawson 16y agoNumber 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.
- 16y ago
- edanm 16y 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.
- tptacek 16y agoYes, 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.
- amalcon 16y 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.
- tptacek 16y agoBe more specific about the attack you're thinking of?
- daeken 16y agoI 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.)
- tptacek 16y agoEveryone who reads HN is smart enough to simply read the primary source for this: http://lists.openid.net/pipermail/openid-security/2010-July/001156.html 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 16y agoWow, 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 16y agoThe reply in question: http://lists.openid.net/pipermail/openid-security/2010-July/001186.html http://lists.openid.net/pipermail/openid-security/2010-July/...
- brown9-2 16y agoSeriously. Kudos to Nate Lawson for being so patient in explaining the vulnerability he found in the developer's code to the developers themselves.
- chaostheory 16y agoAble to read it easily yes. Finding it during work hours - not me personally =) Good find.
- hysterix 16y agoThank 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 16y agoDoes 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?
- metachris 16y 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 http://www.cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf Inside Amazon datacenters you also have lan-like performance.
- twp 16y agoFrom 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 16y agoAnd even more so, with people potentially sitting right next to each other on services like AWS, RackSpace, etc.
- NateLawson 16y agoSee "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 http://cseweb.ucsd.edu/~hovav/dist/cloudsec.pdf [pdf]
- meeee 16y agoWhy should this affect OAuth? The authentication mechanism is not part of the protocol. OpenID is for authentication and OAuth for authorization.
- shajith 16y agoThe 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/association.rb#L122 http://github.com/openid/ruby-openid/blob/master/lib/openid/... Edit: Was wrong about what could leak.
- xinsight 16y agoIt'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 16y ago:D
- sh1mmer 16y agoCan someone summarize if (and how) this is different from the timing attack on OAuth from last year that prompted OAuth 1.0a?
- deleted 16y ago[deleted]
- NateLawson 16y agoHi, 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 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."
- hysterix 16y agoYou guys are out of control over there. Wish I could be there personally at your presentation. You are awesome
- pvg 16y agoWe 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?