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

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?

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

[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

[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

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

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

[maxume]

The sarcastic answer is development.

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

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