Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Cracking Passwords With Amazon EC2 GPU Instances

CmdrTaco posted more than 3 years ago | from the sekrit-p4ssw0rd dept.

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

cancel ×

217 comments

Sorry! There are no comments related to the filter you selected.

first (-1, Offtopic)

Anonymous Coward | more than 3 years ago | (#34243270)

i rules

Yes, SHA1 security is questionable.. (4, Insightful)

intellitech (1912116) | more than 3 years ago | (#34243298)

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

Re:Yes, SHA1 security is questionable.. (1)

Rakshasa Taisab (244699) | more than 3 years ago | (#34243366)

Why is SHA1 deprecated?...

Just cause it's stupid to rely on it for obfuscating stored passwords doesn't mean it's still useful for tasks it is more suitable for.

Re:Yes, SHA1 security is questionable.. (-1)

UnknowingFool (672806) | more than 3 years ago | (#34243520)

My understanding is that hash functions should not have collisions. Both SHA-1 (2^51) and MD5 (2^24.1) both were found to have collisions and therefore not suitable anymore. Of course the level of security you want is tied to how securely you want to protect your data. Protecting your banking information demands more security than your collection of midget porn, I would hope.

Re:Yes, SHA1 security is questionable.. (5, Insightful)

jandrese (485) | more than 3 years ago | (#34243620)

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.. (3, Informative)

clone53421 (1310749) | more than 3 years ago | (#34243622)

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.. (3, Informative)

John Hasler (414242) | more than 3 years ago | (#34243674)

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.. (3, Informative)

VortexCortex (1117377) | more than 3 years ago | (#34243688)

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.. (1)

Antisyzygy (1495469) | more than 3 years ago | (#34243922)

Similar to having a function that maps from N dimensions to M dimensions where M is strictly less than N. You end up with a family of solutions for particular outputs.

Re:Yes, SHA1 security is questionable.. (1, Interesting)

Anonymous Coward | more than 3 years ago | (#34244170)

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

No, indeed. Unless there is a sufficiently narrow definition of "hash function", there is nothing preventing an input of <= n bits from having a collision with another input of <= n bits; which leaves open room for larger inputs.

Example: f(x) = (x^2) only responds with positive numbers in the output space and every output will have two possible inputs (collisions predictable), negative numbers could be used for larger inputs (obviously the overall algorithm cannot be defined by that one function alone...)

Re:Yes, SHA1 security is questionable.. (0)

Anonymous Coward | more than 3 years ago | (#34243700)

My understanding is that hash functions should not have collisions. Both SHA-1 (2^51) and MD5 (2^24.1) both were found to have collisions and therefore not suitable anymore. Of course the level of security you want is tied to how securely you want to protect your data. Protecting your banking information demands more security than your collection of midget porn, I would hope.

*Any* hash function (message digest), given a sufficiently large message compared to the resulting hash. The problem is how to make the colliding message useful to you. For instance if "Please wire $120,000,000 to account 394839487362889 Acme Bank Zurich" collides with "kjs99$ksjskj-3k a;s (....) jfkjd999p- fkjkfjijfn9449" then there isn't much of a problem.

For passwords it's different, that's why those Office/Excel password crackers always give out something like KSFH39AKSKJFK -- definitely not the original password, but it will unlock it nonetheless.

Re:Yes, SHA1 security is questionable.. (2, Interesting)

Omnifarious (11933) | more than 3 years ago | (#34243536)

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.. (2, Insightful)

TheLink (130905) | more than 3 years ago | (#34243720)

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.. (1)

VortexCortex (1117377) | more than 3 years ago | (#34243908)

And replacing the stupid thing is pretty simple. So just get over it already and drop the bad algorithm. How hard can it be?

It's not simple to replace anything that is "written" in hardware.

It's not simple to replace an algorithm with one that is more complex (more computation cycles) when performance (or battery life) is the key issue.

It's not simple to replace one hashing algorithm with another when you have thousands of users that must then update their passwords (and password hashes).

It's not a convincing argument to say "replace a hashing algorithm with another algorithm" if there is no complete break in the wild for the in-use algorithm. The common wisdom when it comes down to the dollars and cents of production is: If it's not broke, don't fix it.

I still use MD5 where I can because it is not broken (salted, of course). Mapping all hash collisions for 1-6 length inputs is no break in my book... I could do that in less than a day with any popular hashing algorithm.

The answer is simple: When hashing passwords, always use a salt. Crypt3 did it, why the hell people are still NOT salting password hashes is beyond me.

Re:Yes, SHA1 security is questionable.. (3, Informative)

AndrewNeo (979708) | more than 3 years ago | (#34244106)

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.. (1)

vlm (69642) | more than 3 years ago | (#34244288)

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?

Not to get too specific, but I use SHA-1 to generate a globally sorta-unique ID for a datapoint in multiple locations using multiple implementations by basically concatenating the relevant parts of the datapoint together and then figuring the SHA-1 hash. How is SHA-1 "broken" for this application, other than being faster and available on more systems and languages that my data importers are run on than other hash functions? I really couldn't care less if it can be reversed, but I am very interested in how "smooth" the output is, given, say, 256 million datapoints, can I reliably expect if I bucket them up based on the first byte of the hash, that I'll have 256 one million datapoint files, which can then be further processed? Also, if importer #2 on system #12 finds the same hash as importer #3 on system #7, I have code to handle it (mostly lots making certain the inputs from 2-12 and 3-7 have not been accidentally crossed), but it really slows the overall system down and generates false alarms, so again I'm very interested in "smoothness of output".

Since its working fine for me, and is not even remotely a security related issue, and is not a CPU hog, and SHA-1 has performed well at ever increasing workloads for years, I'll need another justification to find implementations on all the different systems of a new hash, back convert all the stored data to the new hash, and simultaneously (or something more complicated) modify everything that touches the globally sorta-unique ID hash field. Or, maybe it would be a waste of time...

large cloud, small brain (5, Insightful)

epine (68316) | more than 3 years ago | (#34243564)

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.

Weak attempt, but still good advice (4, Informative)

FlameWise (84536) | more than 3 years ago | (#34244164)

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.. (4, Insightful)

WuphonsReach (684551) | more than 3 years ago | (#34244062)

Why is SHA1 deprecated?...

Because it has become easy to create 2 plaintexts that both hash out to the same SHA-1 value [wikipedia.org] . 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.. (1)

windcask (1795642) | more than 3 years ago | (#34243424)

I'd argue with that. Ever use non-keyboard ascii characters in passwords? Throw one of those in with the usual rules (lower & uppercase, number, top-row symbol) and I'd say you've got a solid six-character password.

Re:Yes, SHA1 security is questionable.. (1)

intellitech (1912116) | more than 3 years ago | (#34243454)

Solid, but not practical.

Re:Yes, SHA1 security is questionable.. (1)

windcask (1795642) | more than 3 years ago | (#34243488)

How so? Alt+Numpad 1 is a smiley face. Using that wouldn't be impractical at all, except on a mobile device.

Re:Yes, SHA1 security is questionable.. (1)

intellitech (1912116) | more than 3 years ago | (#34243530)

Hah, yeah. I like passwords I can use easily and reliably across devices. To each his own, I suppose.

Re:Yes, SHA1 security is questionable.. (0)

Anonymous Coward | more than 3 years ago | (#34243610)

It's only a smiley face on MS-DOS and Windows systems.

Re:Yes, SHA1 security is questionable.. (1)

windcask (1795642) | more than 3 years ago | (#34243652)

That's beside the point. Even on some windows applications, it's a square box, but the ASCII character code is still the same. How it's displayed doesn't matter.

Re:Yes, SHA1 security is questionable.. (2, Interesting)

clone53421 (1310749) | more than 3 years ago | (#34243744)

Are you so sure of that?

(it is actually replaced by a unicode character – &#9786; to be exact.)

Re:Yes, SHA1 security is questionable.. (1)

Teun (17872) | more than 3 years ago | (#34244094)

Truecrypt disagrees.

Re:Yes, SHA1 security is questionable.. (1)

SuricouRaven (1897204) | more than 3 years ago | (#34243436)

Not quite true. They can still work providing two precautions are used: Salting to prevent precomputed tables, and a form of key strengthening (Iterated is easiest).

Re:Yes, SHA1 security is questionable.. (0)

Anonymous Coward | more than 3 years ago | (#34243490)

Worth less, but not worthless. Just now unsuitable for this particular task.

Re:Yes, SHA1 security is questionable.. (3, Informative)

bluefoxlucid (723572) | more than 3 years ago | (#34244010)

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.

Password length of 1-6 (1)

snowraver1 (1052510) | more than 3 years ago | (#34243310)

What is this 1995? Does anyone use passwords that short for anything they care about any more? I'd be interested if they could break 6-12 char passwords with lower, upper, and special characters.

I bet loftcrack could do this same job faster. What is the news here?

Re:Password length of 1-6 (0)

Anonymous Coward | more than 3 years ago | (#34243470)

Heh, no kidding. I don't think the author realizes how much longer it will take to crack even an 8-character password, let alone 12+ characters like most things let you use.

If it takes 49 minutes to crack a 6-character text password that means a 7-character password will take about 60 hours. An 8-character password will take 6 months. 9-character password will take 35 years!

Re:Password length of 1-6 (3, Funny)

Chyeld (713439) | more than 3 years ago | (#34243890)

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 (1)

segur (1066520) | more than 3 years ago | (#34244274)

Not, really. Once you computed the hash, it does not make that big difference whether you check it againts set of tens or set of tens of thousands hashed passwords. (In fact, asymptotically, it can be done in linear time in the length of single hash, regardless of the number of hashes in the set).

Re:Password length of 1-6 (1)

drcheap (1897540) | more than 3 years ago | (#34244324)

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

So a file is "full" once it contains 14 hashes?

Damn, I need to get ready for a second password file, because mine is already at 12 entries!

Re:Password length of 1-6 (4, Insightful)

falldeaf (968657) | more than 3 years ago | (#34243518)

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 (1)

Ecuador (740021) | more than 3 years ago | (#34243642)

Are you kidding? Everyone that isn't a 'computer person' is still using their daughter's name...

Still, "Random Frequent Flier" is not crackable with this brute force method... Not to mention that other child first names can hurt the attacker - remember little Bobby tables?

Re:Password length of 1-6 (2, Informative)

jank1887 (815982) | more than 3 years ago | (#34243936)

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

Re:Password length of 1-6 (1)

WhiteDragon (4556) | more than 3 years ago | (#34244396)

Are you kidding? Everyone that isn't a 'computer person' is still using their daughter's name...

Still, "Random Frequent Flier" is not crackable with this brute force method... Not to mention that other child first names can hurt the attacker - remember little Bobby tables?

nice, a Hitch Hiker's Guide ref and an xkcd ref :-)

Re:Password length of 1-6 (1)

Dishevel (1105119) | more than 3 years ago | (#34244366)

I do not like average people. I protect my stuff from them. I am perfectly ok with those people having their money taken out of their bank accounts and having their email account pwnd.

Re:Password length of 1-6 (2, Insightful)

hedwards (940851) | more than 3 years ago | (#34243544)

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?

Re:Password length of 1-6 (3, Insightful)

MozeeToby (1163751) | more than 3 years ago | (#34243600)

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:Password length of 1-6 (0)

Anonymous Coward | more than 3 years ago | (#34243962)

100x increase for each additional character is hopeful, but probably not realistic.

If the passwords are based on English words, you might only get a 16x-32x increase for each additional character. And maybe 64x-80x if you're using entirely random gibberish of letters (uppercase and lowercase), numbers and symbols.

There's two way to calculate password strength where passwords are based on real words. One is to simply assume 26x or 52x for each additional letter. The other way looks at how many words the average person knows. That number is a lot lower, in the 5k-10k word range. A more educated and well-read person might know 20k-50k, but 10k is a more accepted value. (Dictionaries tend to be in the 200-350k word range, depending on whether proper names are included.)

That means even a 12-char password using a regular word is not 64^12 but only about 2^18, maybe as low as 2^17 due to the birthday paradox. And possibly a lot worse if it's one of the 10,000 more common words (2^12 to 2^13).

Re:Password length of 1-6 (1)

fmobus (831767) | more than 3 years ago | (#34243810)

I don't see how password length makes any difference here. Most applications naïvely store hash_function(password) in the database. If you manage to find a 4-char string whose hash is the same as the one stored in the database, it doesn't matter if the original password has 300 characters. The best course of action for any application is to store hash_function(password + secret_salt) in the database.

Re:Password length of 1-6 (1)

snowraver1 (1052510) | more than 3 years ago | (#34244026)

They are brute forcing the hashes. Sure the output hash length is always the same, but the number of possible inputs are signinicantly reduced by limiting password length of 6.

Think 26^6 vs 2^160 or 308,915,776 vs 1.46E48. Quite a large difference.

Re:Password length of 1-6 (1)

memco (721915) | more than 3 years ago | (#34244074)

Which still results in someone simply needing to find a hash = hash(password+salt). No matter how many characters you throw at it, as long as you're relying on some form of hash, only the output has to be the same and that is all.

SHA-1? (0)

Anonymous Coward | more than 3 years ago | (#34243342)

Ah, thanks. But no worries, we still use MD4 over here! And most people still use MD5.

Dictionnary attack doesn't show any weakness (5, Insightful)

kiwix (1810960) | more than 3 years ago | (#34243412)

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 (1, Insightful)

gman003 (1693318) | more than 3 years ago | (#34243528)

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 (3, Informative)

ZouPrime (460611) | more than 3 years ago | (#34243646)

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 (4, Insightful)

daveewart (66895) | more than 3 years ago | (#34243654)

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 (1)

kiwix (1810960) | more than 3 years ago | (#34243724)

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

No it's a strength of SHA-1 to be fast.

If you want to design a system that resists stupid users with weak password, you can iterate the hash function a high number of times in you password system, but please keep the hash fucntion fast for other purposes. The best part is, that's actually what is done for the Linux /etc/passwd file. The MD5 scheme uses a thousand iteration of MD5 according to Wikipedia [wikipedia.org]

Re:Dictionnary attack doesn't show any weakness (4, Insightful)

vadim_t (324782) | more than 3 years ago | (#34243750)

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 (0)

Anonymous Coward | more than 3 years ago | (#34243900)

No, because even the most perfect algorithm that can be calculated in finite time, will eventually fail, by that logic, all you need is a faster processor/cluster.

The issue is with the passwords being short. So long as the sum is greater in complexity than the password, the blame for brute force breakage is on the password.

Re:Dictionnary attack doesn't show any weakness (1)

markatto (1893394) | more than 3 years ago | (#34243946)

Not necessarily. There are many use cases where there is no disadvantage to a fast hashing algorithm. For example, secure hashes are commonly used to guarantee that data has not been modified. (I believe that PHP uses a hash for this purpose, as it is much faster than running rsa on the entire message.) What this REALLY tells us is something that we have known for a long time: fast hash functions are suboptimal for password "storage"/verification. We need to use something slower for dealing with passwords, such as bcrypt, which can be made arbitrarily expensive.

Re:Dictionnary attack doesn't show any weakness (1)

VortexCortex (1117377) | more than 3 years ago | (#34244018)

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

Then you must also think that this weakness applies to all hashing algorithms, and thus is not a weakness in SHA-1 but in hashing algorithms in general.

  "able to brute force thousands of passwords in an hour" means nothing. The ability to brute force something given less computational steps than intended means something. Throw enough CPU at any algorithm and you'll see the same brute force time-frame results from any hashing algorithm.

I would fully explain, but I'm certain you wouldn't understand.

Re:Dictionnary attack doesn't show any weakness (5, Funny)

Anonymous Coward | more than 3 years ago | (#34243532)

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 (1)

Bill Dog (726542) | more than 3 years ago | (#34244000)

One of the commenters on that blog [stacksmashing.net] proposed just that, and in all seriousness. It seems like that's what it may come to -- make your password hashing function require enough cost that it doesn't put you out of business, but for the multiple of that cost required to crack them to be way too much for hackers to afford.

Re:Dictionnary attack doesn't show any weakness (1)

mu22le (766735) | more than 3 years ago | (#34244194)

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

A no brainer: just add a sleep() here and a do_nothing() loop there...

Re:Dictionnary attack doesn't show any weakness (3, Insightful)

Cow Jones (615566) | more than 3 years ago | (#34244386)

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 [apache.org] , 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 (1)

ByOhTek (1181381) | more than 3 years ago | (#34243580)

Agreed - the only thing brute force shows is the importance of good passwords.

Aren't most hashing algorithms linear in time based on the input? In that case, all such algorithms would only vary by a constant factor, not really a difference in terms of security worthiness anyway.

Correct me if I'm wrong, but isn't the main point of a hashing algorithm to make it unlikely that two different messages would have the same hash (in particular to make it difficult to coerce this effect and have the second message with a matching hash also be in some way intelligible)?

Re:Dictionnary attack doesn't show any weakness (1)

Omnifarious (11933) | more than 3 years ago | (#34243602)

That's exactly what I thought. SHA-1 has been demonstrated to have weaknesses, not trivially exploitable ones right now, but weaknesses all the same. But what this person is doing doesn't exploit any of them. They don't get to blame the ease with which they cracked passwords on SHA-1.

Though, as I understand it, there are algorithms that involve multiple rounds of hashing with a bit of salt added each time. Those would be good because there is no clear way to compute them faster and you can have a few hundred or a few thousand rounds and force a password guess to take at least a few milliseconds to evaluate even on fantastic hardware.

Oh my. (1)

Deanalator (806515) | more than 3 years ago | (#34243458)

Does this mean I can no longer rely on my 6 character passwords?

Re:Oh my. (1)

jeffmeden (135043) | more than 3 years ago | (#34244176)

Does this mean I can no longer rely on my 6 character passwords?

You still can, if your six character password is "FrodoSamwiseGandalfGimliAragornLegolas"...

SHA1 deprecated? (2, Interesting)

Anonymous Coward | more than 3 years ago | (#34243468)

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.

Password Length 1 - 6 (0)

Anonymous Coward | more than 3 years ago | (#34243498)

Good job.

Too bad that any half-competent sysadmin requires user passwords to be at least 8 characters, and has done so for the last 10 years now.

proper use of hashing algorithms (5, Informative)

MyDixieWrecked (548719) | more than 3 years ago | (#34243584)

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 (0)

Anonymous Coward | more than 3 years ago | (#34243708)

Where do you store the salt? In a column next to the hashed password?

Re:proper use of hashing algorithms (0)

Anonymous Coward | more than 3 years ago | (#34243796)

Indeed. You need to know the salt in order to re-calculate the hash to determine if the entered password is the same as the stored hash...

Re:proper use of hashing algorithms (1, Informative)

Anonymous Coward | more than 3 years ago | (#34243816)

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:proper use of hashing algorithms (1, Funny)

Anonymous Coward | more than 3 years ago | (#34243920)

Where do you store the salt? In a column next to the hashed password?

I normally keep it in a shaker.

Re:proper use of hashing algorithms (0)

Anonymous Coward | more than 3 years ago | (#34243738)

Huh? There are no documented colissions in SHA-1, nobody has ever managed to produce one. There are theoretical attacks that are believed to be in the order of 2^60, but nobody has ever implemented them to be certain.

Various people have produced collissions on weakened variants (reducing the number of rounds from 80 to 70, for example), but not on the full 80 round version.

You're thinking of SHA-0.

Re:proper use of hashing algorithms (1)

Evo (37507) | more than 3 years ago | (#34243806)

Salts don't protect against brute-forcing of hashes; they protect against rainbow tables. You still need to store that hash somewhere!

Re:proper use of hashing algorithms (1)

bk2204 (310841) | more than 3 years ago | (#34243910)

That's true. But iteration does. For example, WPA requires 4096 iterations of PBKDF to make it prohibitively expensive to attack the passphrase. OpenPGP does something similar to generate a key from a passphrase.

Re:proper use of hashing algorithms (0)

Anonymous Coward | more than 3 years ago | (#34244238)

2^12 ? You could do more operations. Modern servers can do PBKDF up to 2^18 without problems.... Desktop apps you could go for 2^22.

At that rate, even small passwords are not easily crackable. At least for the next few years.

Re:proper use of hashing algorithms (3, Interesting)

fmobus (831767) | more than 3 years ago | (#34243854)

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 (0)

Anonymous Coward | more than 3 years ago | (#34244196)

You shouldn't use "a salt" for your application. You should "N salts for N passwords": use a separate randomly generated salt for every password instance that is stored, as in the above example. This prevents rainbow tables as the attacker must then repeat the entire attack procedure for each individual hash+salt instance. The assumption going into this is that the application secrecy has been breached and the attacker has access to a copy of the database, code, and deployment parameters.

There is no fool-proof protection for short passwords, because any reasonable brute-force attacker will search in shortest password first order, since they are quicker to attack and humans are more likely to use them. You can slow down the attacker by using more costly hashing algorithms, but this is a balancing act.

Re:proper use of hashing algorithms (1)

orange47 (1519059) | more than 3 years ago | (#34243860)

but would having MD5 and filesize make it harder to produce collision? iirc, torrents for eg. use chunks of known size. also, I always wondered: is it possible to make a (let say textual) file that contains correct md5sum of itself! (kinda recursive)

Re:proper use of hashing algorithms (1)

mrnobo1024 (464702) | more than 3 years ago | (#34244226)

is it possible to make a (let say textual) file that contains correct md5sum of itself! (kinda recursive)

It sure is. Here's the file:

00000000000000000000000000000000
00000000000000000000000000000001
(a few lines trimmed to fit within Slashdot's post size limit)
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

Re:proper use of hashing algorithms (1)

ByOhTek (1181381) | more than 3 years ago | (#34244076)

All of your suggestions only increase the brute-force cracking time by a linear factor.

They are useless. Adding another character or two to the minimum password length, requiring more distinct character or requiring more character classes will all have a significantly higher affect on brute force attacks, with much less effort, and less CPU time for legitimate password entries.

Re:proper use of hashing algorithms (0)

Anonymous Coward | more than 3 years ago | (#34244108)

"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 don't usually encrypt files with public-key cryptography. You encrypt a hash of the file, and maybe also a block cipher key if you want privacy. Encrypting a 1 MB file with RSA would take too long to be practical in real world applications. Consider that you're treating the file as an 8-million-bit number, and then exponentiating it (modulo another 8-million-bit number, but still).

Re:proper use of hashing algorithms (1)

kiwix (1810960) | more than 3 years ago | (#34244206)

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.

Even, if you use a stupid password system by only hashing the password once without salt, you won't be affected by current attacks on MD5 or SHA-1.

The attack we have so far are only collision attack, and preimage attacks are still quite a long way (well, there is a 2^123 preimage attack on MD5 instead of the expected 2^128). And even preimage attacks wouldn't help you much, because they will most likely give you a random preimage, and there is a lot of them. You can use the random preimage to access the system, but it's not as valuable as the original password (if you have acces to the password file, the machine is probably compromised already, but the original password is probably used also in other system [xkcd.com] ).

That being said, you should not use MD5 or SHA-1 because they are broken, and the weakness used in the collision attack might be usable for stronger attacks. So far they have a limited impact, but just don't use MD5 ans SHA-1 anymore, it's not worth it.

Re:proper use of hashing algorithms (1)

jlebar (1904578) | more than 3 years ago | (#34244370)

You don't want a salt -- you want a pepper!

Hash with a small-ish random salt (say 10 bits) and then forget the salt. Then decrypting requires trying all possible salts until you get a hash match.

Ban Amazon (1)

OzPeter (195038) | more than 3 years ago | (#34243604)

Obviously this service will be used by pirates (and not the "arrgh matey" kind), hackers and terrorists and anyone else that gets labelled as a bad person (tm), so we better pre-emptively ban Amazon as they are the ones offering it up.

try using one for your server (1)

alta (1263) | more than 3 years ago | (#34243628)

you apparently need to throw some of that horsepower into your webserver. Amazon has some solutions there for you.

Who still uses 1 to 6 characters passwords? (1)

Yvan256 (722131) | more than 3 years ago | (#34243664)

Obligatory [megaleecher.net] .

No, it shows that WEAK PASSWORDS are bad (4, Interesting)

sootman (158191) | more than 3 years ago | (#34243762)

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

Re:No, it shows that WEAK PASSWORDS are bad (1)

sootman (158191) | more than 3 years ago | (#34243948)

Oops, typo. The number '72' came from A-Z, a-z, 0-9, and the punctuation above 0-9. If you count the other punctuation on a standard keyboard the number goes up to 94, and depending on the app you might be able to use things like é and ñ which would really raise the character count.

Re:No, it shows that WEAK PASSWORDS are bad (1)

StikyPad (445176) | more than 3 years ago | (#34244318)

Not to mention an exhaustive rainbow table search would've taken about 5 minutes on an average desktop, and as a bonus you'd likely get all passwords up to 8 chars (depending on your particular table).

Why not a LAM/MPI - CUDA cloud cluster?? (2, Interesting)

mrnick (108356) | more than 3 years ago | (#34243824)

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

slashdotted.. (0)

Anonymous Coward | more than 3 years ago | (#34243826)

...and no google cache or coral cache. Is it mirrored anywhere?

or... (1)

ILuvRamen (1026668) | more than 3 years ago | (#34243878)

Or you could use passwords longer than 6 letters

Why? (0)

Anonymous Coward | more than 3 years ago | (#34243894)

OK, nice job hashing passwords that aren't allowed on the network. At that rate, with 8 character passwords, it'd take you 300 days to compute the rainbow table. And I'm assuming that you didn't compute every possible salt value, so even then you have a useless table.

How does stuff like this make it on to Slashdot in the first place?

Slashdotted!! (0)

Anonymous Coward | more than 3 years ago | (#34243904)

the guy forgot to set up another amazon cluster for his website...

is it geek chic to appear semi-literate? (0)

Anonymous Coward | more than 3 years ago | (#34243980)

"1 hour costs 2.10$ " No, it costs $2.10. Slashdot is killing the language. You won with "loose". You won with "noone." And "pitty". And "opps". And "guage". And the random insertion of apostrophes. And the language corruption campaign rolls on like Sherman's march into Atlanta, burning and laying waste to everything in its path. The Morlocks have won.

Re:is it geek chic to appear semi-literate? (0)

Anonymous Coward | more than 3 years ago | (#34244208)

Heh, you missed the "Dictionnary attack doesn't show any weakness" thread above....

Re:is it geek chic to appear semi-literate? (1)

delinear (991444) | more than 3 years ago | (#34244378)

Placing the dollar sign after the value isn't necessarily a mistake; it's valid usage in some parts of the world. This might also indicate that the author's first language isn't English, which might excuse some of the other mistakes.

GPU is better than CPU at computation? (0)

Anonymous Coward | more than 3 years ago | (#34244096)

Is this supposed to show that GPU is better than CPU at computations? I've always thought that CPU, being the core unit, is better than GPU at general computations.

CUDA EC2 cluster (1)

wlad (1171323) | more than 3 years ago | (#34244102)

Man, all that computation power, and the first thing people think of is cracking passwords... It's a bit sad.

All Crypto "strength" = time to brute force (0)

Anonymous Coward | more than 3 years ago | (#34244146)

The "strength" of any crypto is based upon the time that the current technology will take to brute force it. A while back 56bit was considered "secure" because it would take the resources of a government to amass enough computing power to brute force it within your lifetime.

Each advance in computing power chips away at the "strength" of all forms of crypto. I am sure that we will see a flurry of sensational articles in the next few days about how the sky is falling. Readily available, cheap, computing power will shift the balance of power a bit, but it is just one more step in a long journey not the end of the world as we know it.

Governments and organizations that rely on crypto know that all crypto has a shelf life and plan accordingly by specifying longer keys and new algorithms years before they are required.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>