Cracking Passwords With Amazon EC2 GPU Instances

suraj.sun writes "As of Nov. 15, 2010, Amazon EC2 is providing what they call 'Cluster GPU Instances': An instance in the Amazon cloud that provides you with the power of two NVIDIA Tesla 'Fermi' M2050 GPUs... Using the CUDA-Multiforce, I was able to crack all hashes from this file with a password length from 1-6 in only 49 Minutes (1 hour costs $2.10 by the way.). This is just another demonstration of the weakness of SHA1 — you really don't want to use it anymore."

Comments

Yes, SHA1 security is questionable..

[intellitech]

But, regardless of the hash method, 6-character passwords are ultimately worthless.

Re:Yes, SHA1 security is questionable..

[jandrese]

It's impossible for a hash algorithm not to have collisions. You're mapping an arbitrarily large problem space down into just a handful of bits. There are infinitely more possible inputs to the algorithm than there are outputs. That said, it's supposed to be computationally prohibitive to find those collisions, and that's where MD5 and SHA1 are failing.

Re:Yes, SHA1 security is questionable..

[WuphonsReach]

Why is SHA1 deprecated?...

Because it has become easy to create 2 plaintexts that both hash out to the same SHA-1 value. See the section titled "SHA-1" which talks about attacks on the hash function.

This means that SHA-1 and MD5 are not suitable for "signing" usage where you have a plaintext where you want to prove that the original has not been changed. It's too easy for an attacker to alter the plaintext in a easily hidden manner so that the hash stays the same.

Is it still useful for the storage of passwords? Yes, but the writing has been on the wall for SHA-1 and MD5 for close to a decade now. When one weakness is discovered in an algorithm, it's the safe bet to assume that future weaknesses will be discovered and those make make the hash algorithm unsuitable for storing passwords. Better to move to one of the newer, more complex, algorithms while you have time to plan over the course of a few years rather then have to switch suddenly in the space of a month or three after an attack is discovered.

Re:Yes, SHA1 security is questionable..

[XaXXon]

3 :(

I'm not a good hashing function!

Re:Yes, SHA1 security is questionable..

[blueg3]

This isn't finding collisions, it's a dictionary attack to find the original inputs.

A collision is where you find two different inputs, A and B, such that hash(A) = hash(B). A collision attack is where you are able to control both A and B, and you manage to compute an A and B such that hash(A) = hash(B). A collision attack is now possible in MD5, but, as far as I know, not SHA1. A preimage attack is where you have a fixed A or a fixed hash(A) and you try to compute a B such that hash(A) = hash(B). That is, the difference is that you can't modify A. There is no known preimage attack for MD5 or SHA1 that is more efficient than brute force. The effectiveness of a brute-force attack is mitigated by having a larger hash output size, as that dramatically reduces the probability of finding a collision. So, moving from SHA1 to SHA2 would decrease the effectiveness of a brute-force attack. However, it's still computationally unreasonably to perform a preimage attack on MD5, much less SHA1.

However, this is talking about a dictionary attack to find the original input. That's where you have hash(A) and you try various possibilities A' and compute hash(A) until you find an A' where hash(A') = hash(A). This looks pretty similar to a preimage attack, but in a preimage attack, you don't care about the nature of A. You just want to find some B, any B, that hashes to the same value. Brute-force preimage attacks take far, far too long. In a dictionary attack, you're trying to use your knowledge of the likely properties of A to recreate likely values for A and compute their hashes. The properties of the hash function are largely irrelevant for this attack. It can be any function, they all work equally will. The important thing is the properties of A. If A is no more than 6 alphanumeric characters, that's a very small space to search through.

So, to summarize. In a brute-force collision attack, the properties of the hash function matter. In a dictionary attack, the properties of the possible inputs (passwords) matter.

Imagine they used only MD5 for hashing. If you tried to perform a collision attack, you'd need to compute on the order of 2^128 MD5 hashes. If you tried to perform a dictionary attack on passwords of 1-6 alphanumeric characters, you'd need to compute on the order of 72^6 ~= 2^37 MD5 hashes.

You need passwords of at least 20 alphanumeric characters (high-entropy ones, at that) before the strength of MD5 is a security weakness. You need 26-character passwords for SHA1 to be weaker than your password.

Dictionnary attack doesn't show any weakness

[kiwix]

This just shows one more time that SHA1 is deprecated — You really don't want to use it anymore.

No it doesn't show anything. Your "attack" would only have been marginally slower with SHA-2, because SHA-2 is a bit slower of SHA-1. You didn't exploit any weakness of SHA-1 in this brute-force attack.

Re:Dictionnary attack doesn't show any weakness

[Anonymous Coward]

No it doesn't show anything. Your "attack" would only have been marginally slower with SHA-2, because SHA-2 is a bit slower of SHA-1. You didn't exploit any weakness of SHA-1 in this brute-force attack.

He exploited the "is fast to calculate" weakness.

Clearly, we need hash functions which take long amounts of time to compute.

Re:Dictionnary attack doesn't show any weakness

[daveewart]

I think "able to brute-force thousands of passwords in an hour" qualifies as a weakness in SHA-1.

Not really. It just shows that 6-character passwords aren't very strong. The hash itself is not the weak point.

Re:Dictionnary attack doesn't show any weakness

[vadim_t]

No, it qualifies as weakness of the passwords.

If your password is "password", no hash is going to save you from that. The cracker takes "password", feeds it to the hash, then compares the result to every line in the hashed password file, to check if it matches anybody's.

Hashing itself has to be fast, since not only passwords get hashed. Sometimes you need to hash a DVD .iso, would you want that to take a week?

Now, you can do things like making the encoding be hash(hash(hash...(password))) with such a depth that it takes a second for a single check. You can't make it much longer than that because then the users will get tired of waiting. But even then it won't save you if you're dumb enough to have "password" or your username for the password. If the attacker has 10000 accounts, it takes about 3 hours worst case (with salting) to check if any of them use "password". And with that many, chances are pretty good that at least one is. So it's still not a license to use a crappy password. That's if they're not determined enough to get a botnet to work on it.

Re:Password length of 1-6

[falldeaf]

Are you kidding? Everyone that isn't a 'computer person' is still using their daughter's name or the favorite type of sports car brand, one word all lower case passwords for all sites and always will. The best security advancements don't come from new theoretical math theory, they come from making security easy and convenient for average people.

large cloud, small brain

[epine]

I agree the story could have been framed better. There is in any case some story here. For certain computational tasks, the linear performance scaling that vanished in a puff of Prescott has returned from the grave.

And not only that, instead of spending $20,000 to buy a Fermi class workstation and getting your result in a year, you can throw the same $20,000 at the cloud and have 10,000 machines deliver your result in an hour, for large instances of cloud.

This applies to a class of computational tasks denominated in CPU cycles where you can cut a wide swath.

Moore's law still exists, it's just not evenly distributed.

proper use of hashing algorithms

[MyDixieWrecked]

So this also proves that, ultimately, this list of passwords was not properly hashed.

People jump up and down and scream that SHA1 and MD5 are broken, but if properly used, they still offer significant password security. One trick is to use salts when storing passwords in the database.

password: 'foo'
salt: '2010-11-16T08:39:05Z - some_random_string$#@!'
password-hash (md5): 14e80778512f578a5fe263abe4b58e9c

that increased the amount of time required to brute-force the password significantly. Also, the use of a database of hashes is largely worthless since each password in the list would have a completely unique hash. for the sake of brute-forcing the data, short passwords don't matter (on the other hand, brute-forcing login to the application is not affected). Having a different salt for each password makes the time spent on each other password completely worthless once the cracker gets to the next item in the list.

to improve that, we can say... hash the result 1000 times in a row. For someone trying to brute force the hash, they would spend 1000x the CPU resources creating the hash. It's mostly not a big deal to run that hash 1000 times when creating the information for the database or authenticating the user.

of course, SHA1 and MD5 are still broken when it comes to file integrity checking (when it comes to tampering) since there are documented collisions. For this case, cryptographic signatures are where it's at. You can guarantee that not only was the file not tampered with, but also that the person who supplied the signature was who they say they were. Gotta love public key encryption.

No, it shows that WEAK PASSWORDS are bad

[sootman]

"Using the CUDA-Multiforce, I was able to crack all hashes from this file with a password length from 1-6 in only 49 Minutes..." [emphasis mine]

Sounds like someone missed the day they taught exponents in school.

Pretend he only tested 72 characters: a-z, A-Z, 0-9. Going from 6 to 8 characters would make this take 5,184x longer. (72x72). 49 minutes x 5184 = about SIX MONTHS.

Weak attempt, but still good advice

[FlameWise]

He's got 14 hashes and cracked 10 of them with passwords of length 1 through 6, some of which contain proper symbols like "P4s$" and "G0o|)".

Length 1 through 4 take less than a second.
Length 5 takes 31 seconds.
Length 6 takes 2950 seconds.
I can see why he probably didn't want to cough up for Length 7 or above.

Amongst the passwords he didn't find was, according to Google Search: "password". Amusingly, I think one of the passwords he didn't manage to crack was the empty string.

I figure you'd have to polish that package a bit for a real attack, but undoubtedly people already have done that somewhere and hence it's a good idea to follow his advice anyway.