Cracking Passwords With Amazon EC2 GPU Instances 217
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."
proper use of hashing algorithms (Score:5, Informative)
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.
Re:Yes, SHA1 security is questionable.. (Score:4, Informative)
By definition any hash function has collisions if the passwords you are storing have more bits than the hash does (more possible passwords exist than possible hash values). The problem is when it collides in fewer bits.
Re:Dictionnary attack doesn't show any weakness (Score:3, Informative)
No, it doesn't. For any other hashing algorithm of similar speed, the same results could be obtained. It's not a weakness of the algorithm, it's a weakness of only checking for passwords of 6 characters and less. That's not a very big space.
Re:Yes, SHA1 security is questionable.. (Score:4, Informative)
All hash functions producing hashes shorter than the text must necessarily have collisions.
There are applications for hashes that have nothing to do with security.
Re:Yes, SHA1 security is questionable.. (Score:4, Informative)
My understanding is that hash functions should not have collisions.
Then, you simply do not understand.
Let me explain gently. If a hash function produces and n bit digest (output) for any given input then any input that is greater than n bits in length MUST produce a digest that collides with an input of n bits or less even though the inputs are dissimilar.
Example: For each letter of this sentence choose either a 0 or 1. You are a 1 bit hashing function. How many collisions did you create after only 3 inputs?
Re:proper use of hashing algorithms (Score:1, Informative)
Where do you store the salt? In a column next to the hashed password?
Yes, the salt is stored with the password, typically in plaintext. The value of the salt is in preventing rainbow table-style lookup attacks using pre-calculated values. As such, it doesn't matter if it's right out there in the open or not--the only requirement is that the salts for different passwords are different from each other.
BTW, the OP's salt example is insanely long. A few random bytes is really plenty.
Re:Password length of 1-6 (Score:3, Informative)
had to google it: http://www.xkcd.com/327/ [xkcd.com]
Re:Yes, SHA1 security is questionable.. (Score:4, Informative)
Re:Yes, SHA1 security is questionable.. (Score:4, Informative)
Salt has absolutely nothing to do with collisions if you have the target hash you're trying to collide with. Finding collisions means they don't need to know the original input, it means they found some other input that creates the same hash. Salting only helps dictionary attacks against the password that created the hash.
Weak attempt, but still good advice (Score:4, Informative)
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.
Re:Yes, SHA1 security is questionable.. (Score:5, Informative)
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.