Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

OAuth, OpenID Password Crack Could Affect Millions

Soulskill posted more than 4 years ago | from the letmein-123456 dept.

Security 304

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

cancel ×

304 comments

Sorry! There are no comments related to the filter you selected.

Add a random delay (1)

clone53421 (1310749) | more than 4 years ago | (#32930180)

n/t

Or do not have variable delays at all (3, Insightful)

betterunixthanunix (980855) | more than 4 years ago | (#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:Or do not have variable delays at all (2, Insightful)

Anonymous Coward | more than 4 years ago | (#32930372)

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.

Re:Or do not have variable delays at all (1)

betterunixthanunix (980855) | more than 4 years ago | (#32930528)

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 (4, Insightful)

Anonymous Coward | more than 4 years ago | (#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.

Re:Or do not have variable delays at all (-1, Flamebait)

betterunixthanunix (980855) | more than 4 years ago | (#32930970)

Nevermind that hashing will take a hell of a lot longer than check the entire plaintext password. Nevermind that checking the entire plaintext password is valuable if security matters (and presumably, security is the value of hashing, unless you want to build a reverse lookup table of passwords).

You are beginning to sounds like a troll.

Re:Or do not have variable delays at all (3, Insightful)

kyrio (1091003) | more than 4 years ago | (#32931028)

It's you who is sounding like a troll. The AC is correct, you are not.

Re:Or do not have variable delays at all (-1, Troll)

betterunixthanunix (980855) | more than 4 years ago | (#32931130)

The AC is correct about what? The the cost of checking an entire submitted password is somehow unacceptable, but that the cost of hashing every submitted password is acceptable? Really? You can go and try this experiment yourself: time how long it takes to hash a 50 character string, and then time how long it takes to check equality between corresponding characters of two 50 character strings. I am being generous here: 50 characters is pretty long for a password.

We are not talking about a busy wait, we are talking about a method of checking passwords that does not have an obvious and easily exploited side channel.

Re:Or do not have variable delays at all (3, Interesting)

kyrio (1091003) | more than 4 years ago | (#32931186)

He is correct about everything. You are just a troll.

Re:Or do not have variable delays at all (1)

something_wicked_thi (918168) | more than 4 years ago | (#32930542)

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.

Re:Or do not have variable delays at all (3, Informative)

Trepidity (597) | more than 4 years ago | (#32930770)

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? (3, Insightful)

FranTaylor (164577) | more than 4 years ago | (#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?

Re:Seriously? (1)

Galestar (1473827) | more than 4 years ago | (#32931170)

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

Re:Seriously? (4, Insightful)

disambiguated (1147551) | more than 4 years ago | (#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.

Re:Or do not have variable delays at all (1)

Galestar (1473827) | more than 4 years ago | (#32931144)

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:Or do not have variable delays at all (3, Interesting)

natehoy (1608657) | more than 4 years ago | (#32930582)

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 delay, a time-checking algorithm would interpret that delay as meaning it got part of the answer correct, where in reality it might have gotten another part of the answer correct (or none of it). A few thousand random-delay hits would have the cracking algorithm thinking that it was simultaneously getting the same bits of the key right and wrong, but still convinced that it was dealing with a time-attack-sensitive system. The attacker might even interpret it as some form of rotating key and give up.

In other words, you are fooling the decryption algorithm down a blind alley of inquiry, and wasting its time. That's far more secure than telling it that you are not subject to time-based attacks right up front. You want to waste as much of your attacker's time and effort as you possibly can.

And, sure, the attacker is probably using multiple simultaneous attacks, but the more obviously impossible attacks you can convince them to try, the more likely it is they'll trip some form of DOS detection.

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.

Re:Or do not have variable delays at all (2, Interesting)

betterunixthanunix (980855) | more than 4 years ago | (#32930930)

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.

Re:Add a random delay (4, Insightful)

Enleth (947766) | more than 4 years ago | (#32930320)

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.

Re:Add a random delay (1)

Mr. Spontaneous (784926) | more than 4 years ago | (#32930540)

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.

Re:Add a random delay (1)

maxume (22995) | more than 4 years ago | (#32930708)

That still leaks information about the characters used in the password.

Re:Add a random delay (1)

wall0159 (881759) | more than 4 years ago | (#32930560)

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:Add a random delay (1)

Michael Kristopeit (1751814) | more than 4 years ago | (#32930842)

uh, the "signal" IS the amount of delay. adding "random delay" is not "merely adding noise"... it IS removing the signal altogether. the amount of delay caused by the password check and the amount of delay randomly added can NOT be differentiated.

i agree that for login, a consistent delay coupled with a delay status screen is the most usable solution.

Re:Add a random delay (2, Informative)

XanC (644172) | more than 4 years ago | (#32930926)

No, the signal is the amount of time it takes to do the password comparison, and the noise is the random amount of time on top of it.

To circumvent: try each password 100 times. It'll become clear what the actual time to compare the password is.

Re:Add a random delay (0)

Anonymous Coward | more than 4 years ago | (#32931080)

what if the delay is a function of the password? though fixed time seems to be a better solution

Re:Add a random delay (3, Informative)

Eternauta3k (680157) | more than 4 years ago | (#32931034)

the amount of delay caused by the password check and the amount of delay randomly added can NOT be differentiated.

Take a bunch of samples, average them.

Re:Add a random delay (2, Informative)

betterunixthanunix (980855) | more than 4 years ago | (#32930734)

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 samples should tend towards the expected value -- effectively, the noise will be removed (or more precisely, the average value of the noise will be added to both the 0 measurement and the 1 measurement, which is no different than just having a slower computer on the other end).

Now, for this to work properly, you need a large enough number of samples. The larger the range of random delays, the larger the number of samples will have to be. This creates a fairly typical security trade-off: too large of a range, and your users will be angry because they have to wait too long to log in, and too small of a range means that attackers have an easy time cracking passwords.

A better solution is to have a constant delay for every password check, regardless of whether the password is correct.

Re:Add a random delay (1)

something_wicked_thi (918168) | more than 4 years ago | (#32930784)

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. Then you force all operations to take exactly X time.

Re:Add a random delay (1)

clone53421 (1310749) | more than 4 years ago | (#32930976)

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 simply added 0-1000us and the routine took 50us, it now takes 50-1050us. However, if you repeat the same input a few hundred times, the average time will converge to about 550us, whereas a call that took 500us will converge to 1000us. You only made the attack take longer.

If you pad to a random value between 1000-2000us, no matter how many times the same input is repeated it will just converge to 1500us, giving the attacker no knowledge of the time taken to check the password.

The easiest way to do this would probably be to use two separate threads: one thread delays a random amount of time then return the result, the other thread checks the password and stores the result in a shared memory location. Just ensure that the password-checking thread will always finish before the delay-then-return thread does. This way the amount of time you actually delay will not depend at all on the amount of time taken to check the password. However you would need a fairly good understanding of the architecture so as to make sure that the two threads would not be able to interfere with each other in a way that would contaminate the randomness of the delay length.

Explaining all of that took a while, though, and I needed to hurry to get my first post. ;)

Re:Add a random delay (1)

minor_deity (1176695) | more than 4 years ago | (#32931266)

In that case you are doing significantly more work then you need to, just to spoof timings so that your attacker will think you are vulnerable to a timing attack. Better just to take constant time and be done with it.

Re:Add a random delay (1)

clone53421 (1310749) | more than 4 years ago | (#32931348)

Taking a constant amount of time is likely just as hard as taking a random amount of time as I described. The only difference is that you are padding to a fixed number instead of a random one.

Re:Add a random delay (2, Informative)

crow (16139) | more than 4 years ago | (#32930362)

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 cover more complicated situations.

Re:Add a random delay (1)

clone53421 (1310749) | more than 4 years ago | (#32931160)

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 enough times. You’ve contaminated your randomness by biasing it with a fixed number that depended on the input.

but correct, and more easily expressed in a multi-threaded sense,

    Thread 0: Verify
    Thread 1: .....Random..... + Copy result from finished Verify = Result

Result does not depend on Verify. Random just has to be long enough to ensure that Verify will always complete.

Re:Add a random delay (0)

Anonymous Coward | more than 4 years ago | (#32930400)

will "random delay" improve things much? you'd have to have a small upper bound for the delay (pausing for a year
is not likely to carry much favour) - and on most machines, the granulative of 'delays' is limited to 1/100s or 1/1000s.
Surely, given enough iterations, you could quickly average out the delay factor?
Would it not be better to just return results after a fixed elapsed time from the moment the login attempt began? Then
no information seeps out.

OpenID (1)

Reason58 (775044) | more than 4 years ago | (#32930188)

Wait, doesn't slashdot use OpenID?

Re:OpenID (5, Funny)

Reason58 (775044) | more than 4 years ago | (#32930204)

Wait, doesn't slashdot use OpenID?

hahahah

DISREGARD THAT I SUCK COCKS

Re:OpenID (1)

DocSavage64109 (799754) | more than 4 years ago | (#32930238)

Wow. Guess it's no longer theoretical...

Re:OpenID (1)

roman_mir (125474) | more than 4 years ago | (#32930622)

No no, it's all good, good thing /. is not US army though, otherwise Reason58 would be 'honorably separated' from this place in a short while.

Re:OpenID (2)

something_wicked_thi (918168) | more than 4 years ago | (#32930796)

I suddenly wish I hadn't posted in this thread so I could mod up you to offset that troll mod someone lacking a sense of humor gave you.

Every password can be broken (2, Funny)

Some.Net(Guy) (1733146) | more than 4 years ago | (#32930200)

It's just a matter of time. Anyone seen Swordfish?

Re:Every password can be broken (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#32930250)

Can't say I did. Got blinded by the ugly tits.

lolswordfish (4, Funny)

crow_t_robot (528562) | more than 4 years ago | (#32930308)

Just drop a logic bomb through the trap door, right?

That movie makes me cringe.

Re:lolswordfish (0)

Anonymous Coward | more than 4 years ago | (#32930602)

not nearly as bad as The Net. Glad Sandra is hot...

Re:lolswordfish (1, Insightful)

AnonymousClown (1788472) | more than 4 years ago | (#32930724)

The movie makes me hard....Halle Berry topless and the thought of some hot blond giving a bj while working at the computer.....

Suspension of disbelief, dude.

Re:Every password can be broken (1)

Kepesk (1093871) | more than 4 years ago | (#32930354)

Agreed. I've never completely trusted the various efforts to create online identification systems, though I'll admit that it wasn't because of this possibility. I guess I'll just continue not using them.

yikes! (1)

Irick (1842362) | more than 4 years ago | (#32930228)

hope a preventative measure gets added soon, OpenID is a great idea, i really like only having one login, but still, tightening up the corners is important ^^

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

MankyD (567984) | more than 4 years ago | (#32930244)

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

Re:Who doesn't hash/encrypt passwords? (1)

TubeSteak (669689) | more than 4 years ago | (#32930376)

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?

Re:Who doesn't hash/encrypt passwords? (1)

betterunixthanunix (980855) | more than 4 years ago | (#32930472)

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

Re:Who doesn't hash/encrypt passwords? (1)

Abcd1234 (188840) | more than 4 years ago | (#32930720)

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.

Re:Who doesn't hash/encrypt passwords? (1)

betterunixthanunix (980855) | more than 4 years ago | (#32930854)

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 computing a collision), but should not be an easy thing to do

Of course, a simpler solution that does not even require those two conditions is to have the delay from a password check be constant (for a given password). Hashing and salting should be a second line of defense, for when a user manages to download the password database.

Re:Who doesn't hash/encrypt passwords? (1)

crow_t_robot (528562) | more than 4 years ago | (#32930564)

IDWSLFOID (I don't write security libraries for Open ID) but I would guess that it's because they use a stream cipher instead of a block cipher.

Re:Who doesn't hash/encrypt passwords? (1)

Shimbo (100005) | more than 4 years ago | (#32930620)

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:Who doesn't hash/encrypt passwords? (2, Interesting)

roman_mir (125474) | more than 4 years ago | (#32930684)

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 encrypted with the same algorithm Encryption.encryptString(...) the hash values are compared instead of the clear text passwords.

This serves 2 purposes:
1. The password is never actually stored in the system, only its one-way hash.
2. It prevents this particular attack from working.

Re:Who doesn't hash/encrypt passwords? (1)

adonoman (624929) | more than 4 years ago | (#32931380)

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, and store the salt alongside the hashed password. Now if two users have the same password, the hashes will still be different, and the attacker will have to run his attack against each user individually instead of against the whole DB. See wikipedia [wikipedia.org]

String encryptedPassword = Encryption.encryptString(password + user.GetSalt(), AppConstants.AUTH_KEY);

Secondly, if your String.equals() function is returning immediately on compare failure, the attacker can still use the timing method to reconstruct the hash of the password without gaining access to your database. Not the worst of attacks, but it does give the attacker more information to work with.

Even better than trying to fix your solution, though, would be to use an authentication library where someone else is handling the crypto and the protocols. It's brutally tough to get right - as evidenced by the fact that libraries built by experts are still having issues.

Re:Who doesn't hash/encrypt passwords? (1)

Stewie241 (1035724) | more than 4 years ago | (#32930836)

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:Who doesn't hash/encrypt passwords? (2, Insightful)

betterunixthanunix (980855) | more than 4 years ago | (#32930428)

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:Who doesn't hash/encrypt passwords? (1)

Bert64 (520050) | more than 4 years ago | (#32931102)

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.

Re:Who doesn't hash/encrypt passwords? (1)

betterunixthanunix (980855) | more than 4 years ago | (#32931200)

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:Who doesn't hash/encrypt passwords? (1)

mattventura (1408229) | more than 4 years ago | (#32930446)

It could be extended to hashes, to a lesser degree. If you know the hashing algorithm used, you could use it to figure out where the hash does not match and ultimately use it to determine the hash, which can then be cracked easily if the password is weak.

Re:Who doesn't hash/encrypt passwords? (1)

MankyD (567984) | more than 4 years ago | (#32930558)

I don't think a reasonable password hashing algorithm works like that. If I change one character in the password (any single character) the entire hash could/should change. You can't look at it and say "well, 90% of the hash matches, let's tweak it a bit more."

Re:Who doesn't hash/encrypt passwords? (1)

EsbenMoseHansen (731150) | more than 4 years ago | (#32930710)

No, since A) the hash will be salted and B) changing one character gives a completely different hash result (just try running md5sum on some strings). E.g:
password 286755fad04869ca523320acce0dc6a4
passwore 530bbcd6551386c86cbc0ebc6b007cc4

Re:Who doesn't hash/encrypt passwords? (1)

mattventura (1408229) | more than 4 years ago | (#32930878)

changing one character gives a completely different hash result

That's the point. You could theoretically get find out the MD5 assuming it wasn't salted by computing md5's yourself and finding one with the characters you need. For example, I would test md5's with all the possible first characters and find the one that is fastest, then generate a list of password and hash pairs with every possible second character and the first character we found earlier, and repeat for every character thereon. It would be a stretch, and the original password would not be revealed, just a hash, but in theory such an attack could work.

Re:Who doesn't hash/encrypt passwords? (1)

Qzukk (229616) | more than 4 years ago | (#32930838)

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 find a password from my rainbow table that hashes to the same thing your account did.

If you have a basic (A-Za-z0-9) plaintext password that's at least 9 letters long, it's "stronger" (62*9=558 attempts), and that's without punctuation.

It's true that bytewise comparison of a 128bit hash would take 4096 attempts (256*16) but if you're not going to block me after 100 failed logins, it's unlikely that you're going to stop me after 4000, either.

The answer is either random delay or not short-circuiting test logic anywhere in a login routine. Blocking login attempts after N failures is another good idea.

Or... (1)

hypergreatthing (254983) | more than 4 years ago | (#32930246)

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

OMG so very hard!

No. (1)

roguegramma (982660) | more than 4 years ago | (#32930834)

Adding a random delay doesn't help. Just send in the request 100 times and take the average time.

Re:Or... (1)

Stewie241 (1035724) | more than 4 years ago | (#32930862)

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.

Re:Or... (1)

Carnildo (712617) | more than 4 years ago | (#32930972)

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()

Re:Or... (0)

Anonymous Coward | more than 4 years ago | (#32931258)


start = time.time()
authenticate = passwordCheck(password)
wait_until(time.time() > start+timeDelay)

Slashdot (1)

ceraphis (1611217) | more than 4 years ago | (#32930260)

that are used to check passwords and user names when people log into websites such as Twitter and Digg.

You forgot slashdot.

This happened back with WinNT (1, Informative)

Anonymous Coward | more than 4 years ago | (#32930276)

There used to be a similar timing problem in the days of WinNT with account lockouts. An attacker would throw guesses at a target, which would delay its responses slightly while the account wasn't locked out. Once the lockout threshold was reached, the response time dropped significantly. It was obvious, too; a human could easily distinguish between accounts that were and were not locked out.

Welcome back to 1997!

Re:This happened back with WinNT (1)

betterunixthanunix (980855) | more than 4 years ago | (#32931040)

TENEX was found to be vulnerable to this sort of attack; you could guess a password one character, by literally measuring the delay in the password comparison (identical to TFA's attack, really).

Welcome back to the 1960s!

Re:This happened back with WinNT (1)

Bert64 (520050) | more than 4 years ago | (#32931326)

Only NT already has RPC functions available remotely by default which let you see the password policy, see accounts that are locked, see what usernames exist, see what groups the accounts are in etc...

Time for a secure strcmp()? (1)

Qzukk (229616) | more than 4 years ago | (#32930286)

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:Time for a secure strcmp()? (1)

mmkkbb (816035) | more than 4 years ago | (#32930366)

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.

Does no-one else put a 10-second delay in? (1)

Xugumad (39311) | more than 4 years ago | (#32930298)

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:Does no-one else put a 10-second delay in? (1, Informative)

Anonymous Coward | more than 4 years ago | (#32930424)

This isn't about 'try until you succeed', it's about 'measure exactly how long it takes to fail'. So your system, while commended, would not prevent against this unless you put in some sort of padding on the message that returned failure.

For example, if your password is 'password', then if I guess passwoe, it would take longer to fail than if I guessed qassword.

Re:Does no-one else put a 10-second delay in? (0)

Anonymous Coward | more than 4 years ago | (#32931014)

If it's always sleep(10) seconds, you're only secure by accident (the difference in password comparison timing is probably less than the sleep() clock granularity, which probably wakes it up at the nearest ten microsecond or so mark. For now, anyway. Then someone whines that their video is 0.8% out of sync and the kernel is modified to accommodate a finer-grain clock). If it slept exactly 10 seconds each time, you'd still be leaking "how long did it take to discover the password didn't match", though you'd be slowing down the overall process.

Re:Does no-one else put a 10-second delay in? (1)

Bert64 (520050) | more than 4 years ago | (#32931360)

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.

Hashed Passwords?? (1)

neiko (846668) | more than 4 years ago | (#32930326)

I thought most of the time just a hash of the password was transmitted, which would not allow this as the hash changes in multiples places when you change a specific location of the original password...

Re:Hashed Passwords?? (1)

Captain Spam (66120) | more than 4 years ago | (#32930828)

I thought most of the time just a hash of the password was transmitted, which would not allow this as the hash changes in multiples places when you change a specific location of the original password...

Almost, but using a straight, in-seuqence, string comparison, stop-at-first-difference method, you could work out the hash and check for a collision from there.

Okay, yes, that might be absurdly slow with today's computational power, but it's not quite foolproof.

Re:Hashed Passwords?? (1)

SQLGuru (980662) | more than 4 years ago | (#32930984)

If you just transmit the hash, then all I need to do is generate hashes; I don't actually need your password at all. This would be more or less the same as sending the password in clear-text.....it's just that the password is some fixed length string that can't be pronounced.

The server needs to do the hash, not the client.

Doesn't MD5 make this hard? (2, Insightful)

tthomas48 (180798) | more than 4 years ago | (#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?

Re:Doesn't MD5 make this hard? (1)

mandelbr0t (1015855) | more than 4 years ago | (#32930908)

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 must be very low, but it is possible.

Re:Doesn't MD5 make this hard? (1)

tthomas48 (180798) | more than 4 years ago | (#32931112)

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

Why the fuzz? (1)

sandertje (1748324) | more than 4 years ago | (#32930532)

As said, it takes only a few lines of code to fix this "bug". Not really hard. Just set a fixed amount of time for the response. Besides:

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.

Is there any situation where interpreted languages are actually faster than said other languages? ;-)

Re:Why the fuzz? (5, Funny)

maxume (22995) | more than 4 years ago | (#32930778)

The sarcastic answer is development.

FUD (0)

Anonymous Coward | more than 4 years ago | (#32930576)

Move along people there's nothing to see here...

Not like xbox 360 (0)

Anonymous Coward | more than 4 years ago | (#32930624)

There is a difference between this type of timing attack and the timing attack used on the xbox 360/smart cards. In both cases, the attacker is submitting a key, and waiting to see how long it takes to process that key. The xbox 360 is a closed system, and the attacker has control over every aspect of the system (in the sense of a controlled scientific experiment). He can easily do the attack over and over, and be able to make it so that only the key changes. Something like OpenID is on the internet, though, and the attacker can't control every single aspect of the system he's attacking. There are numerous reasons why one key will take a different amount of time, with the server load and network load constantly changing. It is impractical to measure the difference of a couple of cpu cycles when there is so much noise.

The only way this will succeed is if these people have come up with a different technique to do the timing attack, but you still shouldn't compare them to people that are attacking a device sitting on their bench. The only thing that I can think of is submitting the same password hundreds or thousands of times, and averaging the amount of time. I'd think that this would appear to be a denial-of-service attack.

Re:Not like xbox 360 (1)

crow_t_robot (528562) | more than 4 years ago | (#32930752)

The only thing that I can think of is submitting the same password hundreds or thousands of times, and averaging the amount of time. I'd think that this would appear to be a denial-of-service attack.

This would be the way to do it. Just spread the attempts out over a week to not DoS and get a good cross-section of different network congestion times. Considering that OpenID is a "single point of failure" spending a week cracking a password is definitely worth it to get access to a ton of sites for one user ID.

Oldest technique? (1)

solidex (246903) | more than 4 years ago | (#32930668)

Wow, I remember reading something about a similar technique once. In an old text file written by some 80s hacker group. Or maybe it was that awful "Secrets of a Super Hacker" book. Either way, this HAS to be one of the oldest techniques known to anyone.

The researchers plan to discuss their attacks (1)

countertrolling (1585477) | more than 4 years ago | (#32930800)

Do they have "permission"? Or will somebody come along and tell them they can't discuss it?

OpenID, OAuth, and all the rest (0)

Anonymous Coward | more than 4 years ago | (#32930910)

How secure can any homogenous security system really be? I want to use a different login, password, and backend security mechanism on every single site that I have an account on.

Account lookup attempts? (0)

Anonymous Coward | more than 4 years ago | (#32930918)

Wouldn't locking out the account after X invalid attempts just block this anyway?

first side channel attack I learned (1)

owlstead (636356) | more than 4 years ago | (#32931012)

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 independent way), use a hash and always test the all the bytes in the hash.

Adding delays is costly and unnecessary, outside the fact that you might still detect something since the average random delay is probably a constant. Don't forget that these attacks already rely strongly on statistics. One thing that you can easily do with an online system is to add a delay after a bad attempt. If you add enough delay, a statistical attack may take simply too long a time (make sure sure you don't aggravate your users until they get a heart attack). Obviously, on an online system, you cannot *just* set a maximum amount of retries without handing a DoS attack to attackers.

Preventing side channels attacks is hard, and don't get illusions that they can be easily discarded because they are impossible to implement. They can be implemented and with the current state of cryptography, they are the one of the weakest points in many security protocols and algorithms. Within the SHA-3 competition it is definitely one area that is getting attention.

... so? (0)

Anonymous Coward | more than 4 years ago | (#32931020)

post a news story when an authentication scheme which /doesn't/ invite users to type their usernames and passwords into dozens of random websites is broken.

Otherland FTW (1)

Gothmolly (148874) | more than 4 years ago | (#32931242)

Even Dread's killer gear was vulnerable to timing attacks. Of course he had a two-factor text&speech combination that the (arguable) heroine managed to get just by accident, but still - vulnerable to a timing attack.

Facebook (1)

Sergeant Pepper (1098225) | more than 4 years ago | (#32931292)

In addition to the listed sites, I believe Facebook's Connect API uses OAuth for authentication... that's a LOT of users...

Xbox 360? A better example! (1)

VGPowerlord (621254) | more than 4 years ago | (#32931366)

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.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>