OAuth, OpenID Password Crack Could Affect Millions 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."
This happened back with WinNT (Score:1, Informative)
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:Add a random delay (Score:3, Informative)
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:Does no-one else put a 10-second delay in? (Score:1, Informative)
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:Add a random delay (Score:3, Informative)
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:Or do not have variable delays at all (Score:4, Informative)
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:Add a random delay (Score:3, Informative)
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 (Score:4, Informative)
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... (Score:5, Informative)
http://bash.org/?5775 [bash.org]
Re:Or do not have variable delays at all (Score:3, Informative)
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 (Score:3, Informative)
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.