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

[Rakshasa Taisab]

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

[windcask]

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

[SuricouRaven]

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

[intellitech]

Solid, but not practical.

Re:Yes, SHA1 security is questionable..

[windcask]

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

[intellitech]

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

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

[windcask]

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

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

[VortexCortex]

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

[Antisyzygy]

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

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

[Teun]

Truecrypt disagrees.

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

[Anonymous Coward]

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

[vlm]

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

Re:Yes, SHA1 security is questionable..

[SteveAyre]

Not true... with salted encrypted passwords you're trying to find a password that the application will think is the correct one. It concatenates the salt with the password and checks whether the hashes match (simplified explanation, but that is what many implementations such as crypt do). That means you're trying to find a collision where the salt is at the start of the input that causes the collision. That's a small subset of the inputs that generate the same hash so it does make finding collisions harder.

Re:Yes, SHA1 security is questionable..

[vlm]

Because it has become easy to create 2 plaintexts that both hash out to the same SHA-1 value.

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.

Your use of the word "easy" is a little peculiar in that you don't get to chose the matching plaintext, except in the most limited fashion.

Most of the time you're signing a hash of a document instead of signing the document itself.
Example "My hundred page mortgage packet", hashed down, sign the hash to prove its mine or basically stick a virtual notary stamp on it.

It is a math breakthru to be able to generate "a file" that hashes to the same, signed value faster than random guess -n- check. The problem is "a file" instead of being "My hundred page mortgage packet" is going to be superficially similar to the output of /dev/random. Its unlikely a judge could find anything worth enforcing in a big /dev/random file.

Generating a matching plaintext that is 99.999% provided with just a couple word switched around is still best done totally randomly or in other words its impossible.

Also "easy" implies an air of "solving ROT-13" which is a slight exaggeration. Breaking a 160 bit hash in less than 2 to the 160th is cool, but its still hovering around 2 to the 50-something ops. So its not as if your key size has dropped to 3 bits or something, its more like its dropped to 50-something bits. Which for many/most apps, is frankly more than necessary, although for a small subset it is not secure enough.

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

[0123456]

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.

Not using a salt means you can check a complete file of passwords in the same run, since you just hash the password and check whether it matches any entry in the file. Using a salt means you can only check one password at a time, since the password will hash to a completely different value when used with a different salt (absent blind luck finding a collision).

If you want to crack 50,000 passwords, then you'll have to buy 50,000 times more power to do that if they're salted than if they're not.

Re:Yes, SHA1 security is questionable..

[Omnifarious]

0) What algorithms do you propose as replacements?

That is tricky. Currently SHA2-256,384,512 are the only viable replacements, but I would say that's only provisional and should wait for the results of the NIST hash algorithm competition.

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!

This is a completely different issue than say "Oh, it's still perfectly good for some things, you don't have to stop using it!". If someone else is using it that you need to interoperate with you don't have any choices besides not interoperating, or implementing the algorithm.

But you still don't have to say "It's just fine, for some things!" and you don't have to make it easy for people to use for new things. For example, you shouldn't be providing an option for people to create an MD2, or MD5 signature anymore, and your UI should strongly discourage the use of an SHA-1 based signature of anything.

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.

Re:Yes, SHA1 security is questionable..

[nabsltd]

As far as I can tell, salting only helps against rainbow table attacks.

Adding a salt also helps to increase the original keyspace, which increases the time to brute force.

As an example, in TFA the source input of the hashes were all 6 bytes. If the hash had been created by adding a 2-byte salt, that means the original user-generated password was only 4 bytes...definitely not very secure.

Note that TFA did not exhaustively compute all SHA1 hashes in 49 minutes, but it appears to have exhaustively searched the 6-byte keyspace in 49 minutes. If you use 8-byte passwords with a 4-byte salt, that increases the keyspace by a factor of 281,474,976,710,656, which means that you'd have to pay around $400 trillion to Amazon to exhaust that keyspace. Also note that unless you have absolute knowledge of how the salt is added (front, back, etc.), the keyspace jumps a lot just by adding a one-byte salt, since that character can be any value, not just restricted to easily typed characters.

So, the article is cute, but doesn't show that password cracking is now available to all for the price of a latte.

Re:Yes, SHA1 security is questionable..

[plexluthor]

Correct me if I'm wrong, but I thought salting still helps in this case. If I use a 6-character password and the hash falls into the hands of the attacker, the attacker will be able to find a collision in at most 256^6 attempts. But if my password is salted first (and the attacker doesn't know the salt), the search space increases dramatically, does it not? Or is it assumed that if they have the hash they have the salt, too?

Re:Yes, SHA1 security is questionable..

[clone53421]

The salt is typically added at the end, and for the MD5 hashing algorithm, two colliding passwords will still collide no matter how much salt is added.

In other words,
if MD5(password) == MD5(password),
then MD5(password+salt) == MD5(collisionValue+salt).

Re:Yes, SHA1 security is questionable..

[robosmurf]

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.

Um, the very article you link to lists no found collisions, only theoretical attacks (where an algorithm could be used to find one faster than a brute force search).

Given that I've yet to see an actual SHA-1 collision published, it's hardly "easy" to do...

Re:Yes, SHA1 security is questionable..

[emt377]

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.

Collisions aren't a problem per se, the problem is if they're predictable. A cryptographic hash that never produces collisions is like a random number generator that never produces the same output twice in a cycle. I.e., not very random and if not random it's predictable. This is different from other types of hash functions, like those used for data structures, where you ideally want to random shuffle the input space into the output space.

Re:Yes, SHA1 security is questionable..

[Deltronica]

Exactly. As understanding of the framework under which the input is generated increases, computations decrease. The input we're talking about is anything but random.

Re:Yes, SHA1 security is questionable..

[clone53421]

Collisions are a problem if they occur frequently, or early in a brute-force. If any relatively short password can collide with another password, collisions are a problem in your cryptographic hash. In a good hash function, no password of <n bits should collide with any other password of <n bits. The higher n is, the better the hash function is.

Predictability is a separate problem entirely.

Re:Yes, SHA1 security is questionable..

[VortexCortex]

The salt is typically added at the end ...

Citation needed. I've never salted anywhere but at the beginning.

... and for the MD5 hashing algorithm, two colliding passwords will still collide no matter how much salt is added.

A true, but very contrived example. A simple fix is to include the salt first (or just use HMAC for cryin out loud!).

For an example of the former:

#!/usr/bin/perl -w
use strict;
use Digest;

my $one = pack "H*",
("d131dd02c5e6eec4693d9a0698aff95c"
."2fcab58712467eab4004583eb8fb7f89"
."55ad340609f4b30283e488832571415a"
."085125e8f7cdc99fd91dbdf280373c5b"
."d8823e3156348f5bae6dacd436c919c6"
."dd53e2b487da03fd02396306d248cda0"
."e99f33420f577ee8ce54b67080a80d1e"
."c69821bcb6a8839396f9652b6ff72a70");

my $two = pack "H*",
("d131dd02c5e6eec4693d9a0698aff95c"
."2fcab50712467eab4004583eb8fb7f89"
."55ad340609f4b30283e4888325f1415a"
."085125e8f7cdc99fd91dbd7280373c5b"
."d8823e3156348f5bae6dacd436c919c6"
."dd53e23487da03fd02396306d248cda0"
."e99f33420f577ee8ce54b67080280d1e"
."c69821bcb6a8839396f965ab6ff72a70");

my $MD5 = new Digest( "MD5" );

$MD5->add( $one );
print "MD5 one: " . $MD5->hexdigest() . "\n";
$MD5->add( $two );
print "MD5 two: " . $MD5->hexdigest() . "\n";

$MD5->add( "salt" . $two );
print "MD5 salt + one: " . $MD5->hexdigest() . "\n";
$MD5->add( "salt" . $one );
print "MD5 salt + two: " . $MD5->hexdigest() . "\n";
# -- end --

Output:

MD5 one: 79054025255fb1a26e4bc422aef54eb4
MD5 two: 79054025255fb1a26e4bc422aef54eb4
MD5 salt + one: 34ca1a8952c4217bc8d8613710116712
MD5 salt + two: 9fb0c0eb1aa52fbb6466987c079815c4

A "typical" (among my peers) way to salt is using HMAC:

HMAC(K,m) = H((K XOR opad) + H((K XOR ipad) + m)).

Select either K or m as your salt and passphrase... I prefer K as the salt because my salt has a fixed length, and typically has more entropy than my users' passphases.

Re:Yes, SHA1 security is questionable..

[windcask]

First off, I just said that the character value is what matters, not how the character displays. It doesn't matter what unicode's replacement for it is because that same ASCII value is going to be taken as the character, regardless of whether your program/system/whatever is able to display it correctly. All you'll see is a dot or a star in the password field, anyway...

In short, yes I'm sure. ASCII 01 in DOS will still be ASCII 01 in Apple, as long as the corresponding character is entered. Getting it to enter correctly is another story...

http://www.jimprice.com/jim-asc.shtml

http://en.wikipedia.org/wiki/ASCII#Variants

http://ascii-table.com/ascii-extended-mac-table.php

By the way, that's the wrong smiley. The white-on-black smiley is Windows Alt+Numpad 1, not the black-on-white.

Re:Yes, SHA1 security is questionable..

[cbiltcliffe]

The problem is "a file" instead of being "My hundred page mortgage packet" is going to be superficially similar to the output of /dev/random. Its unlikely a judge could find anything worth enforcing in a big /dev/random file.

I don't agree.
"A file" could be whatever you wanted it to be. "I'll sign all my possessions over to cbiltcliffe if he provides me with a single 1997 US nickel."
Then, you add a serial number to the end of the document. The length of the serial number will depend on the hash being used:

MD5: 128 bit.
SHA1: 160 bit.

By the time you've gone through all these serial numbers, you'll have your collision.
If "a file" is in the format of a Word document, or some other such non-text format, you'll even be able to keep the serial number hidden, so the judge doesn't see it. Makes for less awkward questions that way.

Now, is it feasible to brute force through all these serial numbers to find your collision? Depends on the processing power you have at your disposal, and what hash you use. If you happen to run a significant botnet, the calculations would be somewhat trivial. If you're trying to do it on a single netbook, you're probably out of luck.

Re:Yes, SHA1 security is questionable..

[RichiH]

0) What algorithms do you propose as replacements?

For secret input: SHA2 512 _or_ Whirlpool
For public input: SHA2 512 _and_ Whirlpool
That should hold water for the next few years. After that, we will talk again.

My main point is that by using hash functions from two different families, you lower the chance of finding collisions. But you may increase the chance of finding the input in case it was unknown.

Re:Yes, SHA1 security is questionable..

[JoelKatz]

There is no evidence that using hash functions from two different families has any effect on the chance of finding collisions. Theoretically, n-bit collisions should be no harder or easier to find if all n bits come from the same algorithm than if some of them come from one algorithm and some come from another.

Re:Yes, SHA1 security is questionable..

[JoelKatz]

There is no conceivable scenario in which the attacker would search for the salt.

Re:Yes, SHA1 security is questionable..

[RichiH]

That theory assumes that both algorithms have the same level of security.

With cryptanalysis, this is not the case. And once one hash is broken, the other will, hopefully, resist the same attack.

Also, please note that I can not trivially create SHA2 756 or something while hashing with different algorithms is trivial. If you want, you can start using ten different salts for ten different runs of the hashing function.

None of this is bulletproof but given public input, it will not lessen your security and have arguably no meaningful overhead (embedded, battery, etc ignored, here) while giving you a very decent chance of better security.

Re:Yes, SHA1 security is questionable..

[deAtog]

You and the author of the article both seem to be missing one important aspect of password hashing. You're never supposed to apply a particular hashing algorithm directly to a password. Instead the user's password should be combined with some salt(random data) and then hashed. The resulting hash can still be brute forced, but any resulting hashes can't be used as collisions for other stored hashes as they require a different known salt to be used. In other words, while it took the author 49 minutes he only had to compute 6^n number of hashes where n is the number of possible characters per position (lowercase, uppercase, numeric?). If each hashed password had a different known salt appended, he would have had to compute 14 * 6^n number of hashes. This is an order of magnitude larger than the original time. Of course, this only applies if the salt is known. If the salt is unknown during the brute-force it's practically impossible to discover the original password.

Re:Yes, SHA1 security is questionable..

[clone53421]

Ok. I must have misremembered something related to cryptographic signing and thought it applied to password hashing.

Re:Yes, SHA1 security is questionable..

[clone53421]

By the way, that's the wrong smiley. The white-on-black smiley is Windows Alt+Numpad 1, not the black-on-white.

No, it isn’t. That’s the smiley you get by the following. Try it yourself:

javascript:var c; try { alert("HTML escape sequence:\n" + eval("'&#' + String(0x" + escape(c = prompt("Enter char:", "")).split("%u").join("%").split("%")[1] + ") + ';'" + (c === null ? "error" : "")) ); } catch(e) { (c > "" && c !== null ? alert("The character " + c + " is not a special character.") : void(0)); }

(Alt+Numpad 1, Ok) => &#9786;

You get the same thing if you enter the character in an <input type=password/> field and escape its contents.

Somehow your sureness doesn’t convince me.

In fact it will be a Unicode character (and completely dependent on the OS and software on the user side – if Unicode is even supported in the text entry field) and completely dependent on how it is handled on the server side, so it may work on some websites and not others (is there a 256-entry table of Unicode -> 8-bit ASCII conversions? or does some weird 2-byte sequence get stored like Slashdot used to do? or does it get stripped out and ignored completely?).

There are way too many variable factors for you to just wave it away with a dismissive “oh, it’ll work”.

Re:Yes, SHA1 security is questionable..

[sjames]

Because there is already a good replacement for it. Where security matters, use SHA256. Where it doesn't but performance does, use MD5.

Re:Yes, SHA1 security is questionable..

[sjames]

In a password system, the primary value of finding a hash collision when you already have the shadow file is to try the same password on other systems so you can exploit those as well. If they use salt, that's not going to work. There are other potential uses, such as when you have root access but anticipate losing it soon, and salt won't prevent that other than making the hashed string slightly longer.

Of course, if you have the shadow file from two systems you can determine which of the brute force matches is the actual password.

Re:Yes, SHA1 security is questionable..

[Littleman_TAMU]

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.

Okay, so salt is more useful than I thought. For some reason I was thinking collision == access, but you're right that no one allows you to provide just the hash as that would be stupid (and pretty much defeat the purpose of hashing the password) and, as you state, if the stored hash is generated (and therefore authenticated) with salt, then your collision value won't give you access.

A well written explanation, thank you.

Password length of 1-6

[snowraver1]

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

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

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

[Ecuador]

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

[fmobus]

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

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

Re:Password length of 1-6

[snowraver1]

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

[memco]

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.

Re:Password length of 1-6

[segur]

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

[drcheap]

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

[Dishevel]

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

[WhiteDragon]

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

[StikyPad]

The best security advancements don't come from new theoretical math theory, they come from making security easy and convenient for average people.

Too bad, then, that security is inversely proportional to convenience.

Re:Password length of 1-6

[vlm]

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?

Well the point is SHA-1 outputs a 160 bit hash, so superficially you can find "A" collision in about ( (2 to the 160) divided by 2 ) guess and checks. But it's been broken so you can find a collision in only about 2 to the 50-something ops.

So guessing 20 characters times about 7 bits/char (unless you're going all UTF-8 on us) is 140 bits in for a hash that could be "worth" 160 bits, but now is only worth 140 bits. What you don't know is SHA-1 is only "worth" about 50 bits, lets round up to about 7 ASCII characters.

Extra characters at the input will just get the hashy thing squashed down to about 50 bits worth of security. Which, lets face it, is probably enough. My ATM pin code is a bit less than 10 bits. My analog/mechanical car door lock could only dream of 50 bits of security.

But don't delude yourself into thinking you're getting "20 characters" of security by feeding a hash that actually tops out around 7.

Re:Password length of 1-6

[MtHuurne]

The kind of hashes used in password databases are a lot longer than 4 characters (~24 bits) though. The total number of hashes produced by 4-character passwords is so much less than the total number of possible hashes that the chances of a hash collision like you describe are negligible.

Since the salt and the hash are typically stored in the same place, someone running this kind of attack most likely knows the salt too. If it's possible to try all 6-character passwords in less than an hour, that will still be the case with a known salt attached to it. The only difference is that since a different salt is used for every user account, the brute force attack must be repeated for each user. If the attacker's goal is to gain entry to a specific account is does not make a difference, but if the goal is to gain access to any account it can make a huge difference.

Re:Password length of 1-6

[falldeaf]

You seem like a people person, I bet you're fun at parties.

Re:Password length of 1-6

[falldeaf]

Good thing then that the goal for most people is not the absolute most secure setup possible. It's about finding a good balance between usability and security. If you're *only* worried about security then unplug it, fill it with cement and bury it in your back yard. (And don't tell anyone that you did it.)

Re:Password length of 1-6

[lakeland]

Instead of someone breaking your 20 character password, all they have to do is find a password that hashes to the same as your SHA1 hash. Because of weaknesses in the SHA1 algorithm, any password contains only approximately 8 bytes (8 characters) of data. Put another way, until we improve off SHA1 it is not particularly useful to have a password over 8 characters because it's cheaper to crack the hash than the password anyway.

Re:Password length of 1-6

[Entrope]

That attack breaks down -- badly -- when random salts are used. You have to compute the hash for each salt+plaintext combination that you want to attack. If a random 32-bit salt is used, you need about 77,000 passwords before you would expect to find two that use the same salt (see http://en.wikipedia.org/wiki/Birthday_attack for the statistics).

Re:Password length of 1-6

[Moses48]

Now you're down to maybe a single month for a wealthy individual to be able to crack a significant, real-world password.

Checking their stickie notes on their monitor because they can't remember hard passwords is easier. Or just brute-force dictionary attack + mined dates/family names from the oh so secure facebook. This is all currently available and much EASIER than any hack that takes large computational power.

Disclaimer: Dictionary attacks can take a while, but given all the meta-data from facebook, we're still talking under a month on a personal computer in most cases.

Re:Password length of 1-6

[Dishevel]

I am.

Re:Password length of 1-6

[nabsltd]

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.

Since an exhaustive keyspace search increases the time by 256 for each extra character (and the TFA shows about 100x increase, probably because he didn't use every character), then even if performance doubled every year (unlikely), you'd still be at about a 10 CPU-days to crack an 8-character password, and over 1000 CPU-days to crack a 10-character password. So, yeah, if computers increase in speed by more than double their current increase, and Amazon (or some other company) has enough of them to rent to you, you could break a 10-character password for $50K or so in a week.

Of course, 10 years from now, we'll be using a hash function that takes 1000 times a long to compute, because it doesn't affect real password-checking speed (which is lightning fast compared to typing speed) on the 200GHz-equivalent processor.

Re:Password length of 1-6

[segur]

Of course, and this is why such salt is used in /etc/passwd (or /etc/shadow or equivalent, respectively) on all moder UNIXes, but it does not seem to be the case in the file form TFA (apart from containing only a few passwords). Thus the 49 minutes should roughly apply (id est, the difference not beeing in the order of magnitude) even for single password.

Re:Password length of 1-6

[yuhong]

So guessing 20 characters times about 7 bits/char (unless you're going all UTF-8 on us)

AFAIK, the NT password hash is up to 255 UTF-16 characters hashed using MD4.

Re:Password length of 1-6

[yuhong]

AFAIK, the NT password hash is up to 255 UTF-16 characters (two bytes per character) hashed using MD4, which is even weaker than SHA1 or MD5. Not that you necessarily need to crack the hash, because many Windows networking protocols lets you pass it directly.

Re:Password length of 1-6

[Kosi]

remember little Bobby tables?

And how I do! Just two days ago I told a friend about xkcd and browsed to exactly that "exploits of a mum" strip later that day because of it. It always makes me laughing so hard, that's the kind of girl to marry!

Re:Password length of 1-6

[ecuador_gr]

Hmm, I wonder why firefox corrected my "flyer" to "flier". It seems I had it right and flyer is valid...

Re:Password length of 1-6

[vlm]

AFAIK, the NT password hash is up to 255 UTF-16 characters hashed using MD4.

Hmm. So 16 bits/UTF-16 char times 255 chars is 4080 bits. But that is not "4000 byte encryption!" or whatever. MD4 only squirts out 128 bits. So a strange design decision indeed to let the user think a long password is more secure. Anything more than 8 UTF-16 chars is wasted effort, or is purely a convenience factor for 9 character long names of dog, or first street address or whatever.

Re:Password length of 1-6

[emt377]

Instead of someone breaking your 20 character password, all they have to do is find a password that hashes to the same as your SHA1 hash. Because of weaknesses in the SHA1 algorithm, any password contains only approximately 8 bytes (8 characters) of data. Put another way, until we improve off SHA1 it is not particularly useful to have a password over 8 characters because it's cheaper to crack the hash than the password anyway.

This is probably not true for password input that rejects non-ASCII. If you find a collision for H(P*V[S]) with password P, where S is a salt identifying a vector from V[], and you have S but not V[], then I suspect that collision is not so useful. First of all even if you could use the collision straight as-is if V[] didn't exist, it would likely contain the 200/256 chars or so that aren't accepted in a password. So you'd have to search for up to 1/((1-200/256)^8)/2 or 95364 collisions on the mean before finding one acceptable. And I bet many of those would still be too long or too short. In practice this means it's not enough to find a collision, but you need to find all collisions - basically you're back to brute force. But V[] would be an obstacle since you need to factor out V[S] before you can feed it into a password field. (I used '*' above loosely as a transform operator to indicate a change of P beyond merely appending a string.)

Now, if you know in advance that you will be able to get a copy of the account data then what you'd do is create one of your own and assign it a password. Now when you get the file you have the hash, P, and S and can attack V[]. Once you have at least one vector you can attack the other passwords using your own V[S] and hope for a solution that's in an acceptable format.

Re:Password length of 1-6

[emt377]

Of course, 10 years from now, we'll be using a hash function that takes 1000 times a long to compute, because it doesn't affect real password-checking speed (which is lightning fast compared to typing speed) on the 200GHz-equivalent processor.

If you want it to take 1000 times as long to check a password, then all you need to do is store H(P+R) where P is the password, R a random number between 0 and 2000, and + some sort of transform operator that's not necessarily addition. After storing the hash you discard the random number. This means each password will need on average 1000 runs through the hash function to validate. This is no different from using a computationally more expensive hash function. Fundamentally though, the problem is the small search space, and at some point - no matter what hash function is used - we will need more bits worth of password than we can remember or want to type. At that time we'll have to switch to some physical means, like a card that is unlocked with a short password and then used for authentication. (Think SDIO card or RFID, or even SIM, though presumably once actually a basic necessity we'll have to come up with a standard specifically for it.)

Re:Password length of 1-6

[StikyPad]

Pfft, that would just preserve it. Better to memorize the contents while under hypnosis such that nobody -- not even you -- can access your memory without the appropriate.. aw shit!

Re:Password length of 1-6

[falldeaf]

Ok, snap, it just got 'real'.

Pfft, that would just preserve it. Better to memorize the contents while under hypnosis such that nobody -- not even you -- can access your memory without the appropriate.. aw shit!

That's seriously bush league. If you can't be bothered to build a doomsday device and destroy the entire planet while at the same time inventing the technology to become immortal so that you can patiently wait from a small space station observing the once known as earth rubble to make sure any alien race surveying the ruins is obliterated with your high powered space lasers then you're just begging for your data to be stolen.

Re:Password length of 1-6

[yuhong]

Or passphrases.
But the reason I mention it in the first place is because MD4 is even weaker than MD5.

Re:Password length of 1-6

[JoelKatz]

That assumes that an 8-character password will contain 8 characters each equally likely to be any of 128 characters. If so, that would be an incredibly strong 8-character password, suitable for almost any application where SHA-1 would be used to hash a password.

In addition, this attack cannot (yet) be used where the original input to the hash function is unknown, so it wouldn't affect the use of SHA-1 for this purpose. (It does affect digital signature applications.) And the current status of this attack is that it has defects that may or may not be fixable -- so the attack may not even exist.

http://eprint.iacr.org/2009/259
(See the last paragraph)

Re:Password length of 1-6

[JoelKatz]

Sure, *IF* you manage to find a 4-char string. But that's like saying there's no point in having a combination to a safe because *if* a burglar manages to guess the combination on his first try ...

Re:Password length of 1-6

[fmobus]

Granted. In a quick back-of-the-napkin calculation, I got that log256 16^32 is 16, meaning that, in theory, all 16-char passwords *could* map to all possible hashes. So, passwords longer than 16 chars, when stored under md5, collide with 16-char passwords, making the former somewhat useless.

Maybe a good idea for picking a password is to somehow ensure no shorter password would yield the same md5. A daunting task by any metric.

Re:Password length of 1-6

[JoelKatz]

An attacker has two mechanisms by which he could break the scheme. He could find the password, or he could find some other password that hashes to the same value. In most real world cases, the former will be much simpler than the latter. So increasing the difficulty of the former has significant value.

If your password is going to be something like
"hTudv9-TvlINqz;i" then I agree, there's no point in making it more than about 16 characters. There's about 92 bits in there, and it's not going to be brute forced no matter what.

In practice, most passwords of 16 character length will be more like 'firefly-absta1ns' if we're lucky (40-50 bits or so) and so will not have nearly that strength.

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

[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

[ByOhTek]

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

[Omnifarious]

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.

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

[kiwix]

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

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

[markatto]

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

[Bill Dog]

One of the commenters on that blog 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

[VortexCortex]

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

[mu22le]

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

[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

[blueg3]

If only there was some sort of Password-Based Key Derivation Function that could use salted, fast-to-compute hashes and apply them many times to increase the cost of computation so that dictionary attacks are proportionally more difficult.

Re:Dictionnary attack doesn't show any weakness

[amicusNYCL]

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

Maybe that would be seen as a weakness. But what this guy demonstrated was not "thousands of password in an hour", it was "14 passwords with a maximum length of 6 in 49 minutes". Can you scale up, and crack thousands in an hour? Sure. But at the rate he did it, one password every 3.5 minutes, to get 1000 passwords in 60 minutes you would need a nearly 60-fold increase in power. He paid $2.10 for his 49 minutes, which means you're going to need to pay $126 per hour if you want the power to crack that many passwords. So, it comes down to economics, what's it worth to you? Are you willing to pay $3,000 per day to crack 24k passwords?

Re:Dictionnary attack doesn't show any weakness

[PhrostyMcByte]

You laugh, but PBKDF2 is the most common way to derive an encryption key from a password and it calls for looping a hash function 1000+ times, for the specific reason of making brute-force attacks take longer to do.

Re:Dictionnary attack doesn't show any weakness

[Bill Dog]

And unfortunately as more computing power becomes cheaper, so will more consumption of it that had previously been unneeded. If organized crime can affordably rent half a data center, an organization might need several dedicated servers just to offset that. The escalation of this silly war includes increasing demands on the electrical grid.

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

[rockNme2349]

If the cracker HAS the hashed password file then your security has already been breached. There's about three things on any system that need access to that file: the login system, the password change system and possibly the admin.

The general idea of hashing passwords is that even if an adversary gains access to the password file it can still be secure. This accounts for things that you might not have foreseen, such as intercepted communications. They don't have to access it in storage necessarily. Now you can always say that your users should be using encrypted connections to your server, but the point of the hash is to have a second line of defense, since a password is a very unique type of information where the data doesn't need to be accessed, simply matched. Even if you encrypt your communications, are you sure it is secure? Will it always be secure?

Re:Dictionnary attack doesn't show any weakness

[cortana]

And that is exactly what you do in the real world.

e.g., pam_unix allows you to set the 'rounds' parameter to slow the calculations, in case the increased default is not paranoid enough for you.

The original article simply gives us a bunch of SHA1 hashes, unmodified, unsalted. Far too weak for real-world use, yes.

Oh my.

[Deanalator]

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

Re:Oh my.

[jeffmeden]

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

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

Re:Oh my.

[clone53421]

That’s the combination to my luggage!

Re:Oh my.

[smithmc]

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

Pfft. You fool; everyone knows that 6-character passwords are no good. You should use a 7-character password, like me!

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.

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

[Evo]

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

[Anonymous Coward]

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

[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

[orange47]

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

[bk2204]

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

[Anonymous Coward]

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

[ByOhTek]

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

[kiwix]

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

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

[mrnobo1024]

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

[jlebar]

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.

Re:proper use of hashing algorithms

[drcheap]

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.

Yes, it would, but there is a slight problem when the actual values of "sufficiently large" is something along the lines of "...big. Really big. You just won't believe how vastly, hugely, mindbogglingly big it is. I mean, you may think it's a long way down the road to the chemist's, but that's just peanuts..."

Re:proper use of hashing algorithms

[Inda]

Bless that post size limit or you may have broken cryptography, time, space, ...

But I think he meant ONLY contains the MD5, and I wouldn't know.

If it does exists, could it possibly be the worst password ever? ...or the best?

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:proper use of hashing algorithms

[emt377]

but would having MD5 and filesize make it harder to produce collision?

Not appreciably - size matters more for passwords since they're (typically) shorter than the hash. This makes it likely impossible to find a collision between two plaintext strings of equal length. Files are different, even BT chunks, in that they're orders of magnitude larger than the hash. Hence, collisions exist and the strength of the hash is dependent on how difficult they are to produce at will.

Re:proper use of hashing algorithms

[antifoidulus]

No, it increases the complexity of finding AT LEAST ONE valid password on your system. As long as I can get access to an account I can cause all sorts of trouble, not the least is executing one of the myriad of privilege escalation exploits and getting root. If they are after a single password then yeah, it doesn't help. But how do they know ahead of time who has the weakest password. I guess if their real name was Stupid McPicksbadpassword.....

Re:proper use of hashing algorithms

[ByOhTek]

No, because traditionally a salt is kept with the passwords. Salts are useful against Rainbow Tables, yes, but they are not useful towards brute force attacks, WHICH IS WHAT THE DISCUSSION HERE IS ABOUT. you can just grab the salt and add it into the password, the time is increased by a small linear factor.

Re:proper use of hashing algorithms

[JoelKatz]

Now everyone is staring at me and I'm going to have to explain why I'm laughing so hard to a bunch of people who don't even know what hashing is.

Ban Amazon

[OzPeter]

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

[alta]

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?

[Yvan256]

Obligatory.

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.

Re:No, it shows that WEAK PASSWORDS are bad

[sootman]

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

[StikyPad]

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

Re:No, it shows that WEAK PASSWORDS are bad

[drcheap]

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.

That's all great and wonderful, but the reality is that the set of people (a very large set I might add) who use passwords that are <= 6 characters tend to stick with [A-Za-z0-9] as their character-space.

Re:No, it shows that WEAK PASSWORDS are bad

[Timmmm]

Yeah but salt.

Re:No, it shows that WEAK PASSWORDS are bad

[trjonescp]

So someone with $9k and six months time would have access to your password?

Re:No, it shows that WEAK PASSWORDS are bad

[Timmmm]

True but he was only using a single node, and it cost him $2 or something. He could easily use a few hundred nodes and get that "SIX MONTHS" down to a few hours.

Re:No, it shows that WEAK PASSWORDS are bad

[BitZtream]

[a-z] + [A-Z ]+ [0-9] = 62

62*62*49 = 3139 = 130 days = roughly 4 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:Why not a LAM/MPI - CUDA cloud cluster??

[jefe7777]

I hope we roast some corn this weekend.
~eom

CUDA EC2 cluster

[wlad]

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

Re:CUDA EC2 cluster

[delinear]

Cracking things like hashed passwords or encrypted data is computationally difficult. It's natural that, given this type of computational power (i.e. distributed in "the cloud" rather than in one system), it's one of the first things people try.

Re:CUDA EC2 cluster

[wlad]

Sure, computationally difficult, but my point was that it's also conceptually very simple and terribly, terribly uncreative. Hardly worth of a slashdot article. Let's wait for some real applications, it has enormous potential in areas such as real time raytracing, neural networks, real time video stream analysis, and so on.

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.

Re:Weak attempt, but still good advice

[Just Brew It!]

Amusingly, I think one of the passwords he didn't manage to crack was the empty string.

Indeed. The last line in the input file is the hash of the null string!

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

[delinear]

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.

Re:GPU is better than CPU at computation?

[pwilli]

GPUs are very specialized processors, therefore they will always outperform the general purpose CPUs in their domain of computational problems (graphics, physics, other massively parallel/pipelineable problems like password cracking). However they would really suck at doing "normal" tasks like running the OS and other applications. GPUs having their own memory and other components directly wired to and optimized for them on graphics cards gives them additional advantages. Finally most gamers forget that they paid up to $ 500 for their graphics card and only $ 200 or less for their CPU.

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

[ChefInnocent]

All those were cause by Slashdot? Wow! I am impressed at the power of Slashdot and its ability to travel backwards through time. Now, that is what we should be calling the Slashdot effect. I could have sworn problems with "loose" and "opps" existed before Slashdot (likely the others as well).

Are you sure you are not just blaming Slashdot for all the language woes like the sitting President is at fault for all the country's woes? Personally, I think the problem is with the written language and the inconsistency of the rules.

Go ahead and blame Slashdot; I'm going to blame the nature of language itself. Your Anglo ancestors, Germanic Ancestors, Indo-European Ancestors, and the like would all assure you, that you are a demonstration of the continued degradation of the language. Most of them couldn't understand a word you are saying anymore than they could a "hood-rat".

Are these just simple SHA-1 hashes?

[geniusj]

Those password hashes are just SHA-1 hashes. Hashes coming from something like unix's crypt()-like functions use many rounds of hashing and therefore take that much longer to crack.

The re-rise of the FPU

[toygeek]

Sure, CPU's include a FPU these days, but in the early days between the 8086/8 you had the 8087 FPU, 286's had the 287, 386's the 387, and even 486SX's could have a 487 added (DX's had it built in). The Pentium class CPU's were the first to have all models include a FPU. Since then, all CPU's have included one.

But now, for more intensive items, we have "physics" cards, GPU cards (which at first glance appear to be FPU's?) etc. So, is the FPU as an addon on its way back? Perhaps.

Re:GPU is better than CPU at computation?

[lakeland]

In general computations yes, but not in anything that is most naturally expressed as vector computations.

ADVERTISEMENT

[IRWolfie-]

This reads like an advertisement, it even includes the cost of the service.

Should have used Elastic Map/Reduce

[BitZtream]

I'm pretty sure it could be done cheaper and faster using Elastic Map/Reduce which password brute forcing would fit very nicely into.

Re:SHA-1 for signing software packages.

[vlm]

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

But is it possible to alter the plaintext in a way that creates, say, a security backdoor and have the hash predictably remain the same? ... But maybe there is something I don't understand - maybe an attacker could add a "comment" that returns the hash to the same value after coding in an exploit.

If read literally, the first statement about "SHA-1 and MD5 are not suitable" is in fact completely wrong, which might be causing some confusion. If you use both, the comment that you add to the security damaged source to "patch up" the SHA-1 to the same hash, will almost certainly throw off the MD5 hash. Breaking both MD5 and SHA-1 simultaneously to the same extraordinary level such that you can change plaintext without altering BOTH a md5 and a sha1 is likely impossible and way off the radar. MD5 and SHA-1 seem weaker than originally claimed, but they aren't that weak especially not in a team.

Re:SHA-1 for signing software packages.

[JoelKatz]

This is a myth. Actually, MD5 and SHA-1 together are a very inefficient use of both your CPU cycles and your bits. If you needed a 288-bit hash, taking the first 288 bits of a SHA-512 hash is believed to be significantly stronger than a 128-bit MD5 followed by a 160-bit SHA-1 hash, and it would take less time to generate.