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

[Omnifarious]

While this article really has nothing to do with the security of SHA-1, SHA-1 does have weaknesses that should make anybody think twice before using it.

And I really hate it when people say "Oh, well, it isn't good for this, but how about this?! I mean, we can't toss out a perfectly good algorithm!". What possesses people to hang onto algorithms that are broken for which there are essentially drop in replacements for that aren't.

Hash algorithms are really tricky to use correctly, and know when you can and can't use them when they have a specific weakness is not a trivial determination to make. And replacing the stupid thing is pretty simple. So just get over it already and drop the bad algorithm. How hard can it be?

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

[clone53421]

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:Yes, SHA1 security is questionable..

[John Hasler]

My understanding is that hash functions should not have collisions.

All hash functions producing hashes shorter than the text must necessarily have collisions.

Of course the level of security you want is tied to how securely you want to protect your data.

There are applications for hashes that have nothing to do with security.

Re:Yes, SHA1 security is questionable..

[VortexCortex]

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:Yes, SHA1 security is questionable..

[TheLink]

So just get over it already and drop the bad algorithm. How hard can it be?

0) What algorithms do you propose as replacements?
1) How hard can it be? Maybe you can "walk the talk" by deleting/disabling all the CA certs in your browser that use bad algorithms- e.g. algorithms that you did not propose in 0). Same goes for not using browsers, ssh servers and clients that do not support algorithms in 0).

Don't be surprised if you find that some CAs are still using MD2!

Re:Yes, SHA1 security is questionable..

[clone53421]

Are you so sure of that?

(it is actually replaced by a unicode character – ☺ to be exact.)

Re:Yes, SHA1 security is questionable..

[bluefoxlucid]

Yes that seems to be the case here. If he used SHA-256 it would still break like that; but with 7 character passwords he'd be doing 4-5 bits more just for lower case letters, 5-6 for lower/upper and numbers, almost 7 bits for upper/lower/number/hash. At 4 bits that's 16 hours.. just adding one lower case letter. With complex passwords with 8 characters, 16384 hours or about 2 years. The average case is half that of course. Good luck spending a year to break 8 characters.

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

[AndrewNeo]

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.

Re:Yes, SHA1 security is questionable..

[Littleman_TAMU]

I think you misunderstand what AndrewNeo was saying. When you have the hash itself, you can then try to find some input that also produces that hash (a collision). You don't have to know anything about the original password or the salt.

As far as I can tell, salting only helps against rainbow table attacks. OP wasn't using those, he was computing the hashes (and thus finding collisions) using only the EC2 GPU instance. He was generating the tables themselves. Salt won't help you in that case. It just requires more compute power which has now become available thanks to the EC2 GPU instances that Amazon is offering.

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.

Re:Yes, SHA1 security is questionable..

[sgtwilko]

Correct me if I'm wrong but, Yes, what you are saying is true for hashes without salt or systems that allow you to provide an already hashed password (why would you do such a thing?), but for these you do not need the collision the hash itself will do.

In a system that correctly applies the salt, your new input will not generate the same hash.
i.e.,
User sets Password, Password is hashed with the salt (e.g., passwordHash = hash(salt+password) )
You discover the resultant hash,
You find a collision that produces the same hash ( hash(collisionValue) == passwordHash )
You then try to use this collisionValue to gain access to the system, but because of the use of a salt the system will take your collisionValue and add the salt, this will produce a completely different resultant hash and will not match the stored password hash.

hash(salt+collisionValue) != passwordHash.

Unless you know of a side-channel attack, or have access to enough hashes where you already know the password in order to determine the salt (or format of the salt for a roaming salt) then your collision is not effective.

Yes you are correct the OP didn't use rainbow tables where salting helps to prevent attacks, but the tables produced were for 1-6 character passwords, without salt. Had he used a 16 character salt (128 extra bits as per bcrypt) then he would not have found a single one of these passwords in that amount of time.

Unless you know the salt and how it is being applied to the password (hash(salt+password), hash(password+salt), hash(hash(password)+salt), etc) you will find it very, very difficult to produce input, not to the hash, but to the authentication system, that can match the resultant password hash.

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

[ZouPrime]

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: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:Dictionnary attack doesn't show any weakness

[Cow Jones]

He exploited the "is fast to calculate" weakness.

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

You're being facetious, but this is basically what the apr1 algorithm used in the Apache webserver does. It's a modified variant of MD5, where the hashing step is repeated 1000 times in order to slow down the creation of dictionary hashes:

/*
  * And now, just to make sure things don't run too fast..
  * On a 60 Mhz Pentium this takes 34 msec, so you would
  * need 30 seconds to build a 1000 entry dictionary...
  */
for (i = 0; i < 1000; i++) {
        apr_md5_init(&ctx1); ....

from apr_md5.c, line 608

I don't know whose bright idea that was... the comment about the speed of this routine on a 60 MHz CPU speaks for itself. But regardless of how effective such "improvements" are, we're now stuck with this algorithm if we want to support the password hashes used in conjunction with .htaccess files, for example.

CJ

Re:Dictionnary attack doesn't show any weakness

[Eil]

Parent was modded funny, but that's actually a valid security measure and it does wonders against your garden-variety dictionary attack.

SHA1 deprecated?

[Anonymous Coward]

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

Or you could, you know, use a salt (like any competent password system). And require eight-character passwords (like any competent password system). That will stave off obsolescence for maybe another decade.

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.

Re:Password length of 1-6

[hedwards]

Indeed. Pretty much everybody that cares about password security is stuck using a password manager anyways. So you may as well use a 20 char password when allowed to. I mean that would only take what like a millennium to break at that rate?

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.

Re:proper use of hashing algorithms

[fmobus]

While I concurred with your point somewhere else in this discussion (regarding the usage of salt), I wonder if there is any possibility that an attacker, having a sufficiently large corpus of your stored hashes, would be able to extrapolate what salt your application is using.

Re:proper use of hashing algorithms

[randallman]

Salts protect against rainbow tables, not necessarily short passwords. In most situations, the salt needs to be known by both parties and is sent in the transmission so that the salt is not a secret. Don't count on the salt being a secret. You still need to choose a good password. Using a salt just means an attacker won't be able to look up the hash in a rainbow table.

Re:Password length of 1-6

[MozeeToby]

Maybe he wanted a proof of concept without having to spend lots of money doing it? So he can crack a bunch of 6 character passwords in an hour or so, extrapolating up, and estimating a 100 fold increase in the search space for each extra character, you might end up spending several hundred years cracking a 10 character password. Now, what's handy is that you're just renting the equipment, I don't know how many GPU setups that Amazon has available, but it doesn't seem unlikely that you could rent several hundred, possibly even several thousand, of them at a time, cutting the time to crack a significant password down to under a year, which still seems pretty secure, especially given the cost of renting that many platforms.

But what happens in 5-10 years, after the performance per price ratio has doubled a few more times? Now you're down to maybe a single month for a wealthy individual to be able to crack a significant, real-world password. Give it another few generations of hardware and you're not even talking about a wealthy individual any more. Good luck convincing the average Joe that he needs to start remembering 15+ character passwords, especially if you're going to enforce truly random ones that aren't susceptible to more direct attacks.

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.

Why not a LAM/MPI - CUDA cloud cluster??

[mrnick]

As part of my graduate studies, in Computer Science at Texas A&M University, I built out a LAM/MPI - CUDA cluster. With this configuration we had access to all the CPU/GPU on all the systems in the lab. Although it requires knowledge of both API it can be extremely powerful. I'd love to see a cloud based system based upon this configuration. Now that would be worth paying by the hour to use!!!

896 CUDA Cores (2 x NVIDIA Tesla C2050 (Fermi) cGPU) is nice but imagine the power of a data center filled with these!!!

Re:Password length of 1-6

[Chyeld]

Clarification from the story summary:

It's not one password, it's a file full of password hashes.

If it takes 49 minutes to crack a single password of six characters length, you need to upgrade from the ZX81 you must be using.

Re:Password length of 1-6

[jank1887]

had to google it: http://www.xkcd.com/327/

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.