OAuth, OpenID Password Crack Could Affect Millions

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

Comments

Every password can be broken

[Some.Net(Guy)]

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

Re:OpenID

[Reason58]

Wait, doesn't slashdot use OpenID?

hahahah

DISREGARD THAT I SUCK COCKS

Who doesn't hash/encrypt passwords?

[MankyD]

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

[betterunixthanunix]

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?

[roman_mir]

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.

Or do not have variable delays at all

[betterunixthanunix]

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

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

Re:Or do not have variable delays at all

[natehoy]

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

[Trepidity]

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.

Re:Or do not have variable delays at all

[Anonymous Coward]

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

[betterunixthanunix]

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:Or do not have variable delays at all

[kyrio]

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

[kyrio]

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

Re:Or do not have variable delays at all

[An Onerous Coward]

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 guesses you're sending to the service.

Re:Or do not have variable delays at all

[doublebackslash]

Sure thing.
# openssl speed sha1
Doing sha1 for 3s on 16 size blocks: 4925162 sha1's in 3.00s
Doing sha1 for 3s on 64 size blocks: 3460802 sha1's in 2.99s
Doing sha1 for 3s on 256 size blocks: 1972423 sha1's in 3.00s
Doing sha1 for 3s on 1024 size blocks: 722903 sha1's in 3.00s
Doing sha1 for 3s on 8192 size blocks: 104552 sha1's in 2.99s
OpenSSL 0.9.8g 19 Oct 2007
built on: Mon Jun 7 19:28:26 UTC 2010
options:bn(64,64) md2(int) rc4(ptr,char) des(idx,cisc,16,int) aes(partial) blowfish(ptr2)
compiler: gcc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -O3 -Wa,--noexecstack -g -Wall -DMD32_REG_T=int -DMD5_ASM
available timing options: TIMES TIMEB HZ=100 [sysconf value]
timing function used: times
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
sha1 26267.53k 74077.37k 168313.43k 246750.89k 286451.50k

26 MB/sec on small blocks in sha1sum. String compares I don't have a command handy to time, but I know that they will be in the hundreds of megabytes / sec range. Now this does not cover security concerns at all. I think that, since we are talking about a security system, we should talk about them.

Passwords are salted and hashed because storing a plaintext password is a grave security mistake. Anyone working with the database could grab a single table and know what everyone's passwords were. That is exceptionally bad, even if they only used the password in that one place. Someone could use that knowledge to legitimately log in as a user. Extrapolate from there. Worse still, many people use the same passwords in a few places, perhaps with a few variants.

Without just telling you to Read More Schneier (which would be rude) , I'd like to make you aware that hashing is one of the most amazingly cheap non-arbitrary things one can do on a modern processor, and that all other operations in a useful system take vastly longer (database lookups, disk access, network access, public key cryptography to establish an SSL session which you better hope your password travels over).

Cryptographic hashes are one of the best building blocks for secure systems, and you may find their application interesting. Give it a look-see. I do recommend Schneier, but some free links follow:
http://unixwiz.net/techtips/iguide-crypto-hashes.html (decent primer, little long winded)
http://mathworld.wolfram.com/BirthdayAttack.html (simple explanation of the birthday attack)
http://en.wikipedia.org/wiki/Salt_(cryptography) (I know a wiki link, but this ties in VERY closely with password security)
http://en.wikipedia.org/wiki/Message_authentication_code (another, I know. But it has a lot of titillating links in it that should be followed)

Also for further reading: Package transforms and Schneier's book Applied Cryptography.

Security is important, and I'd think that if you have such strong opinions you could put them to good use. Happy reading!

PS: None of the links I provided talk about timing attacks. That is very important, but once you've got your head around cryptographic hashes you will know that a well salted and properly implemented hash library will not be vulnerable to many timing attacks. Figured I'd warn you.

Re:Or do not have variable delays at all

[rgviza]

Since passwords are usually stored hashed, you need to hash the plaintext input. You can either do it in the database or the front end code, but you still need to do it.

Generally you do a select password, username where username = inputusername and password = password(inputpassword);

where password() is the hashing algorithm. If you get a row, it's a successful login.

The database usually does an indexed lookup against the first 4 (lets assume the index is on 4 characters) characters of the hash so the fails are going to usually be pretty consistent in time unless you get one of the first 4 characters right after hashing. Even then it won't have the timing you'd think it would. You could get the first 4 characters of the password right when inputting it, and it's possible that once hashed, none of the first 4 will match when comparing the hashes against what's in the table.

As well the entire hash result changes when you change just one character on the input if you use a good algorithm (sha2 or rijndael aka AES) so it's difficult, if not impossible to predict what change will happen in the hash by changing the input, if you don't know the secret and initialization vector. Much less how it will affect the timing of the query result.

Maybe I don't understand the problem.

Is this an issue with unhashed passwords? If so it's a non issue for most because anyone with half a brain will be using strong-cryptographically hashed passwords in a production system. The actual article says "some" libraries are vulnerable. I'm betting it's the ones that are set up to use text file databases with unhashed passwords. There are options in some of the servers to use a database like this.

This type of attack is one of the reasons we cryptographically hash passwords and use a good algorithm instead of something like md5.

lolswordfish

[crow_t_robot]

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

That movie makes me cringe.

Re:Add a random delay

[Enleth]

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

[crow]

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.

Doesn't MD5 make this hard?

[tthomas48]

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

[betterunixthanunix]

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:Why the fuzz?

[maxume]

The sarcastic answer is development.

Re:OpenID

[something_wicked_thi]

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.

Seriously?

[FranTaylor]

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?

[disambiguated]

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

[XanC]

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

[Eternauta3k]

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.

For the uninitiated...

[ThoughtMonster]

http://bash.org/?5775

Would you ike to play a game?

[damonlab]

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.

So a secure comparison algorithm would be..

[droidix55]

Say you have two hashes

1. break each into an array of integers, create a result array with the same size
2. XOR the two arrays containing the hashes into the result array
3. OR all of the ints in the result array together
4. if the result is 0 then the authentication is successful

Would that work?

Re:Add a random delay

[clone53421]

GODDAMN. You really ARE that stupid.

We are NOT fucking talking about a SINGLE measurement of time.

We are talking about hundreds - possibly thousands - of "value", plus your random number. Guess what. Your stupid random number averages out to its median over about 1000 attempts. Meanwhile the CONSTANT value remains CONSTANT and as only the RELATIVE position of the values was important, we can compare it to OTHER attempts and determine which was faster REGARDLESS of your stupid random number.

You average it out.

No, I do not expect you to understand that any more than you understood the more helpful (and less insulting) version. You are an idiot.

Re:Answer to brute force attacks

[Ant P.]

So in your system, I could lock you out of the site simply by doing a bad login on your username three times? Nice.