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

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

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

[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

[gman003]

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

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.

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.

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.

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.