MD5 Brute Force Attack

origin_dev

I've just finished working on a system that requires MD5 password hashes to be sent via email (PDF forms, long story). I found this little gem; if you google an MD5 hash, you get the password.

For instance: "secret", becomes "5ebe2294ecd0e0f08eab7690d2a6ee69"

And when we Google it...

m0ffx

~$ echo "secret" | md5
dd02c7c2232759874e1c205587017bed

strange...

Sunstorm

http://md5.benramsey.com/

ajg

@m0ffx said:

~$ echo "secret" | md5
dd02c7c2232759874e1c205587017bed
strange...

Not strange at all... You're including the newline.

~$ echo -n secret | md5

5ebe2294ecd0e0f08eab7690d2a6ee69

PJH

Did you want salt or pepper with your MD5 hashes?

m0ffx

Hope that website has fun! I make there about 4 x 10^38 md5 hashes. Each is 128 bits, ie 16 bytes, and let's assume the same for a limit on password lengths. You'd need 79 billion billion billion 1 terabyte hard drives to store them all. If you stacked them up, it would reach across most of the known universe.

@m0ffx said:

Hope that website has fun! I make there about 4 x 10^38 md5 hashes. Each is 128 bits, ie 16 bytes, and let's assume the same for a limit on password lengths. You'd need 79 billion billion billion 1 terabyte hard drives to store them all. If you stacked them up, it would reach across most of the known universe.

yes nuit usually passwords are not that good...

8 letter passwords with numbers would result in up to 60^6 hashes .. about 5 * 10^10 hashes * 32 byte .. makes hmm 1.5 TiB ... no problem there?

sobani

@Quicksilver said:

yes nuit usually passwords are not that good...
8 letter passwords with numbers would result in up to 60^6 hashes .. about 5 * 10^10 hashes * 32 byte .. makes hmm 1.5 TiB ... no problem there?

I get 62^8 =~ 2,2 *10^14 hashes * 32 bytes makes 6,2 pebibytes... yikes

Rank_Amateur

Apparently, using Google can be easier and more reliable than fashioning your own dictionary attack.

http://www.lightbluetouchpaper.org/2007/11/16/google-as-a-password-cracker/

--RA

Obfuscator

www.md5oogle.com/

belgariontheking

@sobani said:

I get 62^8 =~ 2,2 *10^14 hashes * 32 bytes makes 6,2 pebibytes... yikes

But how many Gibibytes? (I love that word)

@sobani said:

@Quicksilver said:
yes nuit usually passwords are not that good...
8 letter passwords with numbers would result in up to 60^6 hashes .. about 5 * 10^10 hashes * 32 byte .. makes hmm 1.5 TiB ... no problem there?
I get 62^8 =~ 2,2 *10^14 hashes * 32 bytes makes 6,2 pebibytes... yikes

sry misttyped 6 letters..

still md5 is broken so it would probably be easier to calculate the hashcode directly then storing a rainbowtable...

asuffield

@m0ffx said:

Hope that website has fun! I make there about 4 x 10^38 md5 hashes. Each is 128 bits, ie 16 bytes, and let's assume the same for a limit on password lengths. You'd need 79 billion billion billion 1 terabyte hard drives to store them all. If you stacked them up, it would reach across most of the known universe.

Which is precisely why you use rainbow tables to compress the database down to a few terabytes.

You can no longer get away with using unsalted hashes. You should now always use a salt that is at least the same length as your hash.

asuffield

@Quicksilver said:

still md5 is broken so it would probably be easier to calculate the hashcode directly then storing a rainbowtable...

Where did you get this idea? It's nonsense. You can't do that.

What you can do is generate two strings of your own that have the same hash, where you get to pick the content of one of them (a second preimage attack). This is of very limited application. It's primarily useful in breaking signature schemes; it's useless against password hashes.

slavdude1

@PJH said:

Did you want salt or pepper with your MD5 hashes?

Personally, I like ketchup. Lots of ketchup.

jcoehoorn

"You should now always use a salt that is at least the same length as your hash."

Actually, that's not quite right. You salt the users's password such that the result is longer than 16 characters before converting it to a hash. When creating the hash, use SHA-2 or Bcrypt rather than md5. Though I suppose salting the hash afterward wouldn't really hurt anything.

http://www.codinghorror.com/blog/archives/000949.html
http://www.codinghorror.com/blog/archives/000953.html

asuffield

@jcoehoorn said:

"You should now always use a salt that is at least the same length as your hash."
Actually, that's not quite right.

Actually, it is precisely right. Nothing else results in correct salting. The whole point of the exercise is to ensure that the hash has as much entropy as it should have (since rainbow tables, and database attacks in general, are an attack on hashes that are lacking entropy).

origin_dev

Came up with a simple solution: we just append a random string to the end of a users password and hash that. ;-)

asuffield

@origin_dev said:

Came up with a simple solution: we just append a random string to the end of a users password and hash that. ;-)

We call that a 'salt'.

Carnildo

@asuffield said:

@origin_dev said:
Came up with a simple solution: we just append a random string to the end of a users password and hash that. ;-)
We call that a 'salt'.

Aren't salts usually prepended?

Quietust

@Carnildo said:

@asuffield said:
@origin_dev said:
Came up with a simple solution: we just append a random string to the end of a users password and hash that. ;-)
We call that a 'salt'.

Aren't salts usually prepended?

I've seen it both ways, so I do both - generate a random string, put half at the beginning of the password, the other half at the end, hash the whole lot (and then put both salts on the password hash).
Probably overkill, but it's better than I've seen some systems do (phpBB3 appears to do multiple passes of salt-MD5, which one would expect to [i]reduce[/i] the overall entropy after enough passes).

asuffield

@Carnildo said:

@asuffield said:
@origin_dev said:
Came up with a simple solution: we just append a random string to the end of a users password and hash that. ;-)
We call that a 'salt'.

Aren't salts usually prepended?

It doesn't make the slightest bit of difference. A salt is any amount of entropy that is used as an input to a key derivation function (usually a password digest function, but it has a handful of other applications).

asuffield

@Quietust said:

@Carnildo said:
@asuffield said:
@origin_dev said:
Came up with a simple solution: we just append a random string to the end of a users password and hash that. ;-)
We call that a 'salt'.

Aren't salts usually prepended?

I've seen it both ways, so I do both - generate a random string, put half at the beginning of the password, the other half at the end, hash the whole lot (and then put both salts on the password hash).

A futile gesture that would make me very uncomfortable about the system, since the author clearly doesn't know what they're doing.

Probably overkill, but it's better than I've seen some systems do (phpBB3 appears to do multiple passes of salt-MD5, which one would expect to [i]reduce[/i] the overall entropy after enough passes).

There is a single well-known algorithm that involves multiple (thousand) passes of the md5 transformation instead of the usual single pass. This algorithm is the one commonly used for password digests on unix systems; it is cryptographically equivalent to a normal md5 hash but takes about a thousand times longer to compute, which is necessary to block brute-force attacks against short passwords (since the basic md5 algorithm is really too fast for the job of hashing passwords). It is available on most systems, including php, via the crypt() function.

I expect that phpbb3 is not using it and is just sucking as hard as it does in every other respect. But I haven't checked.

belgariontheking

@asuffield said:

It doesn't make the slightest bit of difference. A salt is any amount of entropy that is used as an input to a key derivation function (usually a password digest function, but it has a handful of other applications).

So an algorithm which applied the same salt to each password would be a wtf? Some guy at my last company thought that would be ok.

PJH

@belgariontheking said:

@asuffield said:
It doesn't make the slightest bit of difference. A salt is any amount of entropy that is used as an input to a key derivation function (usually a password digest function, but it has a handful of other applications).
So an algorithm which applied the same salt to each password would be a wtf? Some guy at my last company thought that would be ok.

Less of a WTF than no salt at all (since it makes the default rainbow tables useless,) but still a WTF.

The purpose of a salt is to make the passwords harder to figure out. To crack them you take a possible password, salt it then hash it, then see if it matches any of the hashes in the database.

If the salt is the same for every password, they need only salt/hash once to compare against every single hash in the database.

If the salt is different for each password, they need to salt/hash each time to compare against each hash. Computationally more expensive.

asuffield

@belgariontheking said:

@asuffield said:
It doesn't make the slightest bit of difference. A salt is any amount of entropy that is used as an input to a key derivation function (usually a password digest function, but it has a handful of other applications).
So an algorithm which applied the same salt to each password would be a wtf? Some guy at my last company thought that would be ok.

Yes, that's dumb. The whole point (and definition) of a salt is that it's pure cryptographically-strong entropy. It will not perform its function if it is not.

belgariontheking

@asuffield said:

@belgariontheking said:
@asuffield said:
It doesn't make the slightest bit of difference. A salt is any amount of entropy that is used as an input to a key derivation function (usually a password digest function, but it has a handful of other applications).
So an algorithm which applied the same salt to each password would be a wtf? Some guy at my last company thought that would be ok.
Yes, that's dumb. The whole point (and definition) of a salt is that it's pure cryptographically-strong entropy. It will not perform its function if it is not.

But still not as dumb as cleartext passwords. Another of my former companies used that. I couldn't be buggered to fix it for reasons of my own.

Quietust

@asuffield said:

A futile gesture that would make me very uncomfortable about the system, since the author clearly doesn't know what they're doing.

It's a [b]web-based game[/b] which originally just MD5-hashed the password directly into the database. Get a grip. If it would really give you peace of mind (which it likely won't, so I won't bother), I'll drop it down to a single 8-character salt prepended to the password just like everybody else does, just for you.

The concept of salting password hashes is simple enough - add extra entropy to the password to thwart bruteforcing. Some people like to put the salt at the beginning, and some like to put it at the end (and some like to hash the password, append the salt, then hash it again), but the actual position of the salt is largely irrelevant.

Cap_n_Steve

@asuffield said:

A futile gesture that would make me very uncomfortable about the system, since the author clearly doesn't know what they're doing.

If that's all it takes to make you uncomfortable, I suggest you never use any website.

origin_dev

@Quietust said:

@asuffield said:
A futile gesture that would make me very uncomfortable about the system, since the author clearly doesn't know what they're doing.

It's a [b]web-based game[/b] which originally just MD5-hashed the password directly into the database. Get a grip. If it would really give you peace of mind (which it likely won't, so I won't bother), I'll drop it down to a single 8-character salt prepended to the password just like everybody else does, just for you.

The concept of salting password hashes is simple enough - add extra entropy to the password to thwart bruteforcing. Some people like to put the salt at the beginning, and some like to put it at the end (and some like to hash the password, append the salt, then hash it again), but the actual position of the salt is largely irrelevant.

Thank you. Clearly asuffield doesnt know what he's doing.

m0ffx

@belgariontheking said:

But still not as dumb as cleartext passwords. Another of my former companies used that. I couldn't be buggered to fix it for reasons of my own.

A fucking annoying number of websites do that. They then email you the password. And some even send regular 'reminders'.

MarcB

@m0ffx said:

@belgariontheking said:
But still not as dumb as cleartext passwords. Another of my former companies used that. I couldn't be buggered to fix it for reasons of my own.
A fucking annoying number of websites do that. They then email you the password. And some even send regular 'reminders'.

Just because they can make the cleartext available doesn't mean it's actually stored in cleartext. They could be storing it as an AES or DES blob in the database and crypting/decrypting it as necessary. I've done that for any number of systems that required some measure of privacy on the data, but also required that the data's original form be recoverable.

asuffield

@MarcB said:

@m0ffx said:
@belgariontheking said:
But still not as dumb as cleartext passwords. Another of my former companies used that. I couldn't be buggered to fix it for reasons of my own.
A fucking annoying number of websites do that. They then email you the password. And some even send regular 'reminders'.
Just because they can make the cleartext available doesn't mean it's actually stored in cleartext. They could be storing it as an AES or DES blob in the database and crypting/decrypting it as necessary. I've done that for any number of systems that required some measure of privacy on the data, but also required that the data's original form be recoverable.

Unless it's an asymmetric system with one key held offline, there is no cryptographic difference between this and storing passwords in cleartext. It accomplishes nothing more than buzzword compliance.

death

@asuffield said:

@MarcB said:
Just because they can make the cleartext available doesn't mean it's actually stored in cleartext. They could be storing it as an AES or DES blob in the database and crypting/decrypting it as necessary. I've done that for any number of systems that required some measure of privacy on the data, but also required that the data's original form be recoverable.
Unless it's an asymmetric system with one key held offline, there is no cryptographic difference between this and storing passwords in cleartext. It accomplishes nothing more than buzzword compliance.

Who cares about the storing if a sys-admin(you?) can reverse my password. You can take my identity within that system and leave no tracks. Anybody with access to the encrypted data can. I am just as uneasy about that as a clear-text password.

asuffield

@death said:

@asuffield said:
@MarcB said:
Just because they can make the cleartext available doesn't mean it's actually stored in cleartext. They could be storing it as an AES or DES blob in the database and crypting/decrypting it as necessary. I've done that for any number of systems that required some measure of privacy on the data, but also required that the data's original form be recoverable.
Unless it's an asymmetric system with one key held offline, there is no cryptographic difference between this and storing passwords in cleartext. It accomplishes nothing more than buzzword compliance.
Who cares about the storing if a sys-admin(you?) can reverse my password. You can take my identity within that system and leave no tracks. Anybody with access to the encrypted data can. I am just as uneasy about that as a clear-text password.

You have no clue what we are talking about.