Slashdot is powered by your submissions, so send in your scoop

 


Forgot your password?
Close
typodupeerror
×
Security Open Source News

OAuth, OpenID Password Crack Could Affect Millions 304

Posted by Soulskill from the letmein-123456 dept.
CWmike writes "Researchers Nate Lawson and Taylor Nelson say they've discovered a basic security flaw that affects dozens of open-source software libraries — including those used by software that implements the OAuth and OpenID standards — that are used to check passwords and user names when people log into websites such as Twitter and Digg. By trying to log in again and again, cycling through characters and measuring the time it takes for the computer to respond, hackers can ultimately figure out the correct passwords. This may all sound very theoretical, but timing attacks can actually succeed in the real world. Three years ago, one was used to hack Microsoft's Xbox 360 gaming system, and people who build smart cards have added timing attack protection for years. The researchers plan to discuss their attacks at the Black Hat conference later this month in Las Vegas."
This discussion has been archived. No new comments can be posted.

OAuth, OpenID Password Crack Could Affect Millions More

OAuth, OpenID Password Crack Could Affect Millions

Comments Filter:

    • Or do not have variable delays at all (Score:4, Insightful)

      by betterunixthanunix ( 980855 ) on Friday July 16, 2010 @02:13PM (#32930256)
      This is neither a new problem nor an unsolved problem. This problem stems from using functions like strcmp, which return as soon as a difference is detected, and are thus unsuitable for password checks. Solution? Set a flag when the first difference is found, and continue checking subsequent characters.

      • Re: (Score:2, Insightful)

        by Anonymous Coward

        Which is just a waste of CPU resources. It's better to use the function that returns immediately, and sleep briefly instead. At least then you're freeing up the CPU for other processes that may have real work to do.

        I know, I know, you'll say it's "not a big deal", but you probably just don't deal with real servers that experience heavy load.

        • I presume this is the same sort of logic that lead to the decision to use plaintext passwords, rather than salted and hashed passwords.

          • Re:Or do not have variable delays at all (Score:4, Insightful)

            by Anonymous Coward on Friday July 16, 2010 @02:40PM (#32930786)

            Absolutely not. There is valuable computation done when hashing passwords. There isn't when you continue comparing passwords well after you know they don't match, when you could just as easily yield the CPU to other processes.

            You've been proved wrong. Try to argue the point next time, rather than throwing up strawmen.

        • But if you sleep, you may not wake up for a long time. Processes that relinquish the cpu could take a while to schedule again on machines with heavy load. When you're talking just a few dozen instructions for the additional compares, since most strings ought to be short, it's far better to finish the comparison.

          I know, I know, you'll say it's "not a big deal", but you probably just don't deal with real users that expect to have low latency responses to their requests.

        • It's really hard to get that perfect, though. If you're actually doing the same work, it's harder to accidentally leak information than if you're doing less work but trying to fake the equivalent amount. In the case of using a sleep, you're vulnerable to the particular scheduling implementation; it's pretty hard to make it so there's no visible timing differences between the sleep-using and non-sleep-using code paths.

          There are cases where it's worth the effort, but I don't think strcmp() is one of them. When an attacker can gain information by detecting that you took different code paths, it's worth being somewhat conservative in unnecessarily introducing branching paths.

        • Seriously? (Score:4, Insightful)

          by FranTaylor ( 164577 ) on Friday July 16, 2010 @02:44PM (#32930850)

          Are you serious?

          In the course of an entire web session's worth of CPU consumption, you are worried about the time taken to compare password characters? Any modern optimized processor should require one clock cycle per character.

          Do you actually profile your code or do you just make funny noises? Or maybe you're running your web server on a Commodore 64?

          • ditto parent. talking about "wasting" 6 cycles on a one off event (non-loop) is ludicrous.

          • Re:Seriously? (Score:4, Insightful)

            by disambiguated ( 1147551 ) on Friday July 16, 2010 @03:09PM (#32931260)
            Compiler-optimized code on a 64 bit machine compares 8-bit characters 8 at a time. This guy is trying to force a context switch (upwards of thousands of instructions) to save 4 or 5 instructions. It doesn't save CPU (because of the context switch), it increases the latency, it's harder to code, and may be still vulnerable! sweet.
        • Considering that passwords are generally 8-12 characters long, I'd think yielding the CPU would take more resources then just checked the remaining x characters.

      • Re: (Score:3, Interesting)

        by natehoy ( 1608657 )

        Excellent idea, but if you institute a random delay you might actually make your system more secure (and you use less CPU doing it because you're not walking through the entire checking algorithm, thereby making yourself less susceptible to CPU overload DOS attacks).

        A fixed-time-to-answer would quickly tell the time-based algorithm that it was not dealing with something that is susceptible to it, and the attacker would immediately move on to a dictionary attack or some other method.

        If you institute a random

        • Re: (Score:3, Interesting)

          by betterunixthanunix ( 980855 )

          but if you institute a random delay you might actually make your system more secure

          Random delays are easy to filter out. In fact, given that the authors performed this attack over a network (which will add random delays anyway), you should already know that they are capable of doing that.

        • Actually, the ideal would be to tune the timing to infer to the attacker something utterly unlike the actual password, and if someone sends in the password you are inferring by your timing you are now aware that a time-based attack is underway, and you can stop trying to check passwords sent by that connection entirely - just keep replying "access denied" with the delay continuing to infer the same key. Puts a lot less load on your system, and keeps the attacker busy and armed with lots of incorrect information.

          Now that's just spiteful! Remind me never to piss you off...

      • Re: (Score:2)

        by JackDW ( 904211 )

        That's interesting. For the benefit of other readers, it should be clarified that this attack is still possible even if the password is hashed, because a given hash value must be compared to the known correct value (as you stated below).

        However the situation may be even worse than you suggest. The behaviour of the CPU may change as a result of setting that flag, perhaps causing its timing to change. For instance a cache miss may (or may not) occur, or memory accesses may be reordered, or a branch might be

        • The behaviour of the CPU may change as a result of setting that flag, perhaps causing its timing to change. For instance a cache miss may (or may not) occur, or memory accesses may be reordered, or a branch might be mispredicted.

          We can actually prevent cache timing attacks somewhat by aligning the flag to a cache line boundary, and writing the password exactly one byte ahead of the flag. Thus, to compare the password at all, the flag will have to be cached, and so setting/checking the flag should not create a cache miss. This assumes that the password will not be too huge (i.e. a long enough password could "wrap around" and evict the line with the flag on it), but I think that it is fairly safe to assume that passwords are not

        • Re: (Score:3, Informative)

          by An Onerous Coward ( 222037 )

          Hashing should make a huge difference, though. If you're comparing the passwords themselves, it's pretty straightforward. To crack the hash, you have to find an acceptable-length string that hashes to each subset of the target hash (a..., a0..., a0f..., a0f4..., a0f49..., etc.) I don't know if there is a way to do that other than brute force, and toward the end the search space is prohibitive.

          I think the best you could to would be to get the first several digits of the hash, then use it to prefilter the

      • A better solution is to use a pre-defined salt, and md5 hash the input with it. Then generate an appropriate random hash, and re-hash using sha1 both the input and a pre-salt-hashed stored password with it, then compare both with strcmp.

        Good luck trying to reverse that. It's not impossible, but it's the best I can come up with, and likely to withstand any (reasonable) attack in the next 50 years on conventional hardware.

    • Re:Add a random delay (Score:5, Insightful)

      by Enleth ( 947766 ) <enleth@enleth.com> on Friday July 16, 2010 @02:16PM (#32930320) Homepage

      No, a random delay just makes it harder for an attacker to determine the nect correct character. The exact theory behind eliminating the random factor eludes me, but several smart people found a way and it's supposedly correct.

      I think the proper way is to "pad" the time so that it's constant. Say, if the password checking algorithm can take from 50us up to 600us, pad it to 1500us (safety margin!) with as much precision as posiible. There might be other code paths to pad, too, such as the one that fires when there's not even such a user, but you still want to display the "wrong password" message, as some systems do.

      • What about having a strcmp that compares strings using a randomized series of indexes?

        E.g.

        compare position 4, then 1, then 3, then 10, etc.

      • exactly. A random delay is merely adding noise to the signal, not removing the signal altogether (in the way that using a consistent delay does)

      • Re: (Score:3, Informative)

        by betterunixthanunix ( 980855 )

        The exact theory behind eliminating the random factor eludes me, but several smart people found a way and it's supposedly correct.

        It is fairly basic and necessary to pull off the attack (i.e. because this is being done over a network). Let's simplify things and suppose that the comparison is performed bit-by-bit rather than byte-by-byte; we want to determine if a particular bit is a 0 or a 1. We'll take 1000 measurements when the bit is a 0, and 1000 when it is a 1, and then take the average of the delays in each case. Invoking the law of large numbers, we can conclude that despite random noise, the average of a large number of s

      • That makes sense. If you have a 300us processing time for a particular incorrect password and you pad by 1000us +- 500us in all cases, with a uniform distribution, then it's relatively easy to guess, with known confidence, how long the real processing took, since the average of multiple attempts will come out to 1300us. moe generally, adding a random sleep with any known distribution is doomed to failure.

        The easiest way to do this is to define a time, X, that is longer than all expected processing times. Th

        • Yeah, that was basically my thought, but instead of a constant X you use a random number that’s guaranteed to be longer than all expected processing times.

          In my haste to get first post I couldn’t think of any way to express that quickly, but yeah.

      • My idea of a “random delay” isn’t quite a random delay but rather more of a “pad to a random length”. I.e. if the operation takes between 50-600us, pick a random length between 1000-2000us, start the timer at the beginning, call the routine, and when all is said and done just go to sleep until the total elapsed time reaches the random value you initially picked.

        You are correct in that simply delaying for a random amount of time merely blurs the window for detection.

        I.e. if you

    • Re: (Score:3, Informative)

      by crow ( 16139 )

      Not good enough. A random delay will add noise, increasing the number of attempts required, but will not break the attack vector.

      What is needed is to insure that the algorithm will respond in the same time when a match fails, regardless of how close the match is. If this were a simple string comparison, you would need a function that compares every character in the input to a padded version of the password, not one that stops at the first mismatch. In most cases, that same approach can be extended to cov

      • Not just a random delay, per se. You are absolutely right.

        To avoid contaminating the random delay with a fixed bias (which can easily be determined by running the same query enough times), the timer has to start at the very beginning, delay for longer than the password-checking algorithm will ever take, then return the result after the preset random length of time has elapsed.

        I.e. wrong:

        Verify + Random = Result

        Result depends on Verify. You just have to average out Random by repeating it enoug

  • Wait, doesn't slashdot use OpenID?
  • It's just a matter of time. Anyone seen Swordfish?

  • Who doesn't hash/encrypt passwords? (Score:5, Insightful)

    by MankyD ( 567984 ) on Friday July 16, 2010 @02:12PM (#32930244) Homepage

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

    If you do almost any sort of reasonable hashing or encryption algorthm on a password, this becomes a moot point, since the place that fails to match in the string will change. Are there still sites out there that don't do this? Really?

    • If you do almost any sort of reasonable hashing or encryption algorthm on a password, this becomes a moot point, since the place that fails to match in the string will change.

      This might be a stupid question, but how do they check a password one character at a time unless they're saving the password in plaintext or some other reversible method?

      • They check the hash one character (or word, quadword, whatever) at a time.

        • If that's true, a timing attack is useless, as the place where the comparison would fail is random, and certainly doesn't provide information about how to tune the input to get closer to the "correct" answer.

          • However, it could allow an attacker to determine some part of the hashed password, which the attacker might then be able to crack using his own computers (which can just sit there trying to crack the password without dealing with any other work). This depends on the attacker's ability to do two things:
            1. Compute the salt; this is not trivial, and a long enough salt should make this infeasible
            2. Compute hashes that begin with a particular sequence; this is not necessarily difficult (certainly not as difficult as

      • Re: (Score:2)

        by Shimbo ( 100005 )

        This might be a stupid question, but how do they check a password one character at a time unless they're saving the password in plaintext or some other reversible method?

        I think that's just a slightly sloppy writeup. You probably get to know individual bytes of the hashed password. It's likely that you can vastly reduce the key space for an attack by this method, with carefully chosen plaintext. No, you probably don't get individual plain text characters, one at a time, like in a bad movie.

      • Re: (Score:3, Interesting)

        by roman_mir ( 125474 )

        here is a solution I implemented a little while ago:

        public boolean isUserAuthenticated(User user, String password) throws TCAppException {
        String encryptedPassword = Encryption.encryptString(password, AppConstants.AUTH_KEY);
        if (user.getPassword().equals(encryptedPassword)) {
        return true;
        }
        return false;
        }

        User object contains password that is encrypted, the password that is passed as 'password' from the login page is also e

        • Good job not storing the plain text. But there are still problems with your code.

          First, if two users have the same password, they will have the same hash stored in the db. If an attacker gets a hold of the list of hashes, it's trivial to generate hashes of a few million common passwords and compare them to the list. In any moderately sized user list, you'll get hundreds of matches. The trick is to also generate a random string of "salt" for each user. Append the salt to the password before hashing, a

          • Salt, you are looking right at it.

            AppConstants.AUTH_KEY

            Somebody getting a copy of my DB and getting the hash keys? That means they have access to my production server and I have bigger issues than some silly thing like them signing in as some user.

        • That is a terrible auth function. Where is the randomly-generated salt? Where is the expensive hash function, like bcrypt?

          • As I replied, the AUTH_KEY is actually salt, if you care you can check my reply above to some other doubter.

      • http://www.computerworld.com/comments/node/9179224#comment-588733 [computerworld.com]

        That comment there is insightful. This has nothing to do with passwords, it has to do with SSO keys. I was confused originally because OpenID says nothing about how systems store or verify passwords, so it wouldn't make sense to check in that manner.

    • Re: (Score:3, Insightful)

      by betterunixthanunix ( 980855 )
      You'd be surprised. Salting and hashing passwords seems like common practice, but most programmers have minimal security training (yes, even those programmers who implement password based authentication systems) and may fail to realize the significance of not hashing.

      Now, the fact that open source projects have this problem is a bit disturbing...

      • Re: (Score:2)

        by Bert64 ( 520050 )

        Windows doesn't bother to salt its hashes either...

        What open source systems don't do hashing? Must be pretty niche applications or someone would have contributed a patch by now.

        • It seems that the systems described in TFA were open source, and that they checked plaintext passwords. Maybe I misread something (the article is full of inaccuracies anyway; timing attacks go back much further than 25 years, and reducing the noise added by a computer network is not ground breaking at all).

    • Re: (Score:2)

      by Qzukk ( 229616 )

      If you do almost any sort of reasonable hashing or encryption algorthm on a password, this becomes a moot point,

      You risk making the problem WORSE, especially if you compare the ASCII (hexadecimal) representation of your hashes. If I know what hash algorithm you use, I can produce a rainbow table, and attempt to log in 16 times to determine the first hexadecimal character of the hash, 16 more times to determine the second and so on. For md5 (128 bits, 32 nibbles) it would take 512 (16*32) login attempts to

    • I'm pretty sure this is easily fixed... Any authentication system I write queries the database for both the username and password at the same time(all passwords stored as MD5 hashes) and only checks to see if a row was returned. If it is, the credentials are correct. If nothing is returned, the credentials are wrong. I never tell the user which was wrong, thats up to them to figure out.

      $query = "SELECT uid from users where username='" . $_POST['username'] . "' AND password=MD5('" . $_POST['password'] . "

  • they could just impliment a simple
    if passwordcheck(password)=false then
    wait random(15)
    end if

    OMG so very hard!

    • The point isn't that it is hard to do... the point is that it isn't being done. The other point is that it wasn't being done because of the contention that the exploit was so unfeasible it wasn't worth it. The research demonstrates that the exploit is more feasible than people thought.

    • This doesn't fix the problem, it just slows down the attacker. Statistical analysis of the delay will still tell the attacker exactly how long it took to check the password.

      The correct fix is:

      if passwordcheck(password)=false then
      run_a_delay_loop_until_it_takes_as_long_as_a_success()

    • Congratulations. You've just implemented a system that is exactly no more secure. See posts above for why.

  • One that will always loop through the longest string (would need to figure out something to compare it to once past the end of the short string), even after it has decided they're not equal.

    • Re: (Score:2)

      by mmkkbb ( 816035 )

      Go back to the beginning of the short string. You know the comparison will fail, so it doesn't really matter as long as you don't follow some random pointer.

    • One that will always loop through the longest string (would need to figure out something to compare it to once past the end of the short string), even after it has decided they're not equal.

      That seems like a silly idea to me. Why would you implement it in strcmp() when most of the time you want to maximize performance. The proper place to do this is not in strcmp but in the password verification routine. As noted above also, sleeping is a more efficient use of processor resources than performing non-important calculations.

  • Last time I coded a web based auth system, if you failed to log in it would refuse to check your next attempt until 10 seconds after the previous one (blocked by IP and by username). I, apparently foolishly, assumed most people would do the same...

    • Re: (Score:2)

      by Bert64 ( 520050 )

      Do you block the combination of IP and user? If so, couldnt an attacker simply cycle through a block of usernames such that each user wasnt tried more than once every 10 seconds?

      I like systems which block the user after failed attempts, but leave your IP alone... Makes it absolutely trivial to DoS the system by simply sending invalid auth requests for all the users.

  • Doesn't MD5 make this hard? (Score:3, Insightful)

    by tthomas48 ( 180798 ) on Friday July 16, 2010 @02:26PM (#32930510)

    I hate this kind of announcement because it usually ends up that they found a hack in a revesion Bozo's poorly constructed library from 5 years ago, but I like this kind of announcement because it makes me consider my security.

    I'm using a PHP OpenID library that's using md5 for comparison in the database. I don't really see how that would be feasible, since even if you were cycling through characters you need all characters to make the hash which mysql is making its string comparison based on.

    Or am I missing something?

    • This reminds me of a similar flaw in Apache HTTPS a while back. It takes considerable timing resolution (i.e. not remote) to accomplish, but the problematic construct looks something like this:

      if (!md5match) { return FAIL; } else { // do something long and complicated return SUCCESS; }

      Basically, by using enough attacks and cycling through the bits of the calculated hash, you can determine which bits are and aren't in the private key. It takes some time to accomplish, and the network latency mu

      • But in that case the user is supplying the hash, right?

        • True, but the basis of the vulnerability is the same: do not provide timing indications of success/failure if its possible to cycle and record to deduce the password. I'm not saying it's not possible to invent a login mechanism that doesn't have this particular vulnerability, just that it's not something even security-concious people immediately think of.

          • But the problem isn't success/failure. It's differences of timing in failure, that tell how successful you were. It's basically like that old game of mastermind, but rather than colored pegs you're getting different times for your failure message.

    • If the library is not using a salt, you can still retrieve the value of the hash using the exact same method. Furthermore, if the hash is intercepted they can use it for looking up the password in a rainbow table or similar. Just hashing is not enough.

  • This was the first time-based side channel attack I learned. Within Minix you initially could place a password right at a page boundary and try and login. If there was a page fault before the password was rejected, you knew you had the right character right before the page bound. Of course, the solution is very simple: check all the characters for correctness, simply setting a boolean to false each time you find an incorrect character. Probably even better is to pad the input to a maximum length (in a time

    • That's what you get from using an outdated college lecture as starting point. Of course, as already mentioned in the responses, the correct way is to have a full length random salt, XOR the password in it (in case the RNG is broken, possibly use an additional counter or something), hash it and then send the salt & hash to the other side. Sending the password in plain or relying just on SSL is a stupid idea for an online system.

    • This was the first time-based side channel attack I learned. Within Minix you initially could place a password right at a page boundary and try and login. If there was a page fault before the password was rejected, you knew you had the right character right before the page bound.

      That dates back before Minix - Butler Lampson's Hints for Computer System Design [microsoft.com] speaks of a similar issue in Tenex. (Look for "Tenex" in that paper for the example.)

  • A better example from the past of this same sort of attack was back in OpenSSH Portable. Specifically, OpenSSH/PAM timing attack allows remote users identification [marc.info]

    Note that this didn't apply to finding passwords, just that invalid users would immediately return an error after the password was entered, while a valid user and incorrect password would have a delay.

  • Would you ike to play a game? (Score:3, Interesting)

    by damonlab ( 931917 ) on Friday July 16, 2010 @03:19PM (#32931438)
    I always thought a big flaw in the movie War Games was that the launch code was figured out one character at a time. Now this happens and flips my world upside down.

  • The researchers also found that queries made to programs written in interpreted languages such as Python or Ruby -- both very popular on the Web -- generated responses much more slowly than other types of languages such as C or assembly language, making timing attacks more feasible. "For languages that are interpreted, you end up with a much greater timing difference than people thought," Lawson said.

    Sure, scripts are slower than C. They're slower in general, but when you compare two binary strings, it's still mostly the same C memcmp call that's being called. You also have semi-random events like mark and swipe garbage collection, dynamic optimizations, I/O delays.

    This means scripts may be slower and more random, while the password check call still isn't, how the heck would that make is easier to hack scripted sites?

    I'm not even mentioning the fact most web apps don't have passwords hardcoded, but actu

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

    Why the hell are they checking against the password in plaintext, and not some kind of hash?

Slashdot Top Deals

Every nonzero finite dimensional inner product space has an orthonormal basis. It makes sense, when you don't think about it.

Close