Why do people think that this is bad way to hash passwords?

Question

What's wrong with this code?

$password = "hello";
$password = md5($password);
for ($i = 1; $i < 20; $i++) {
  $password = md5($password);
}

I don't think an attacker with access to the hashes storage would be able to decrypt any password using more than 2 characters.

The attacker would have to decrypt this list of hashes to be able to gain the plaintext password.

69a329523ce1ec88bf63061863d9cb14
0dcd649d4ef5f787e39ddf48d8e625a5
5d6aaee903365197ede6f325eb3716c5
cbe8d0c48ab0ed8d23eacb1621f6c5c3
8fa852c5f5b1d0d6b1cb0fad32596c71
91a84cf929b73800d2ff81da28834c64
45b7d5e4d3fca6a4868d46a941076b72
e5b7d9d10fef132829731255ef644319
b3af6ff5f5c7ae757ca816a6cb62f092
150f3682b2e58d1d0e1f789f9ba06982
3f76626950bf31dbc815c667ca4b2b43
44f4c75517671e12946aab3c8c293f98
442256b098b2d88e93428b08b5155308
7fd8ebc5bdff94f24a10decaa1ab64e8
d04bbc863839b720d932a697f0bf443b
de737c934db23c2d1d1026863e7583a8
d745f6394700c4ab1e9ded0924ea35d2
ce9428b51d3a63431c57a435423877b6
7017f40bdb4f1be1f5fae7dd0fc7b907

With brute force, an attacher should try 36³² (*19) combinations, which is pretty unachievable. Isn't that true?

Answer 1

The wrong things on your method are:

• You use way too few iterations (20 is too low, it should be 20000 or more): password processing is still too fast, an attacker with a basic PC will still be able to "try" dozens of millions of passwords per second.
• There is no salt: an attacker may attack several passwords with very low per-password cost, e.g. with precomputed tables of hashed passwords (in particular rainbow tables).
• You are in the process of inventing your own cryptography. There is nothing wrong with being inquisitive and trying to understand things, but since there is no sure test for knowing whether a given algorithm is secure or not, inventing your own cryptography is often a recipe for disaster. Don't do it.

What you should do is to use bcrypt; there is a PHP implementation in the Portable PHP password hashing framework.

Answer 2

Others have described the limitations of this hashing method; I'd like to point out a conceptual mistake in the question:

I don't think that attacker with my DB would be able to decrypt any password with lenght > 2

Attacker would have to decrypt this list of md5 hashes to be able to gain plain-password:

[list of intermediate results]

The mistake here is thinking that the complexity of the intermediate results provides any protection at all against a brute-force dictionary attack. I think the asker is thinking the attack must work backward, starting from the stored hash, and brute-force each intermediate result in turn.

This isn't true at all; reasonable dictionary attacks will start with possible passwords, and attack the whole 20-hash stack at once. Here's the algorithm sketch:

for each candidate password:
    hash 20 times
    compare with stored hash

Using this to check all possible 3-character passwords (assuming printable ASCII) would require only 20 * 95^3 = 17147500 hashes, which is basically trivial. Using SHA-512 instead of MD5, despite having much larger intermediate values, would be more secure only because each hash takes a little longer to compute.

tl;dr a complex hash function can't save you if the password itself doesn't have enough entropy.

Answer 3

20x MD5 is a fast hashing algorithm, meaning it can generate passwords at an astonishing rate.

Please stop using fast hashing algorithms to store passwords. Even with individual salts; if someone has direct (read: offline) access to your database they can be computed very easily.

This article explains why much better than I can:

http://codahale.com/how-to-safely-store-a-password/

The article heavily mentions BCrypt (with a link to a PHP library), but bear in mind there are other slow hashing algorithms that may suit you.

Answer 4

The problem is that this is a pretty obvious "algorithm", and pretty fast to boot.
It's very likely that there's a precomputed rainbow table available for this "algorithm", and even if there isn't, md5 is fast enough to be able to precompute one in a realistic amount of time.

You should always use an individual salt for each password to avoid this kind of attack.

Answer 5

There are four problems with just iterating md5 over and over, no matter how many times you do it.

Computing Power over Time

The first big problem here is that as written it doesn't scale over time to remain secure as computers get faster. What is secure today will be cracked in moments on tomorrow's computers.

Modern secure algorithms like bcrypt and scrypt have built in tuning so that the algorithm can be automatically adjusted to be slower as attacking computers get faster. Since bcrypt is also free and it's still just a simple function call for you, there's no good reason not to use it.

Now, you do have the start of a scaling structure built in to your code. It would be easy to refactor that to run the md5 hash an arbitrary number of times, such that you can tune it to be slower over time. But that's not good enough.

Designed for Failure

The second problem is that md5 is a fundamentally poor choice for a cryptographic hash because it was specifically designed to be fast. The purpose of md5 is for quickly verifying or comparing large files. To accomplish this, the hash needs to be able to be computed quickly and efficiently. This means the implementation and design goals of the algorithm are completely at odds with storing passwords. The chances that at some point we will figure out a way to compute an md5 hash that is orders of magnitude faster than what we can do currently is orders of magnitude higher than we will be able to do the same for sha1 or bcrypt.

Degeneration

The third problem is that hashing algorithms in general tend to degenerate as you iterate them. To understand this, take the original text supplied by the user. The conceptual size of this text is unbounded. There are an infinite number of possible values here. After we hash the text once with md5, we're down to 2¹²⁸ number of possible values... still very large, but no longer unbounded. But let's cycle this again. md5 is good, but it's not perfect. Those 340 undecillion potential inputs will have some collisions, and yield a number of results that is close, but still somewhat less than, 2¹²⁸. As you continue to iterate you'll find more collisions, until you eventually end up with a number that, while still large, is significantly less than the conceptual space you thought you were working with.

Cycles

Finally, the fourth problem is some of your original potential inputs will results in cycles: value number 12345 hashes to 98743, which hashes to 67321, which hashes back to 12345, and so on. In other words, some inputs will cycle through the same small set of hash values, and iterating them further won't help. In fact, the more times you run the hash, the more likely a given original input will end up in a cycle.

This goes back to the design of md5. A cryptographic hash could be designed to minimize (not entirely eliminate, but at least minimize) the degeneration and cycle phenomenons, but it wasn't a concern at all for md5.

Conclusion

Any one of these reasons alone is enough to not use md5. There are other perfectly good options available, and they generally use the same interface, so choosing a different one isn't hard. In some platforms, it's as easy as changing an enum value you pass to some "createhash" function. Put all three reasons together, and continuing to use md5 is absolutely insane.

Answer 6

Aside from what has already been pointed out in the other answers so far, it seems to me like you have a fundamental misunderstanding sitting there right in your question. The output space of a 128-bit hash function such as MD5 is not 36^32 (about 6.3e49), but 2^128 (about 3.4e38). That's 11 orders of magnitude!

Cryptography is hard. If you don't know precisely what you are doing (and in many cases even if you do), you are much, much better off not trying to design something yourself but rather using a ready-made, tried-and-true solution. For a real life example of how terribly wrong things can go when you don't know exactly what you are doing, look up the Debian OpenSSL key debacle. The early version Netscape PRNG is another example. I'm sure there are plenty of others, too, more or less widely publicized.

Answer 7

You have a simple one-way hashing function for passwords, seems secure right? You'd have to run through a lot of guesses to brute force such a system. However, consider a bad case (not even a worst case) scenario. You use this level of security with a very high importance site, or even a site with a lot of users.

Then, one day there's a small security snafu or your site has some previously unknown vulnerability that gets exploited and all of your user account data including hashed passwords is now in the hands of "bad guys". The bad guys go to their low-cost PC with a decent GPU in it and modify a previously existing program to generate hashes so that it does 19-levels of md5 hashing. Then they feed it a well-honed dictionary of common and likely passwords as well as random alphanumeric strings of increasing length. Over time the GPU cranks through generating hashes creating a look up table. At any given time the bad guys can check their generated hash lookup table to the list of hashed passwords and, because you didn't use a per-password salt, easily find matches. Over time as the GPU continues to work away more and more passwords are revealed, until only the highest strength passwords remain.

Answer 8

MD5 is not the best hash to use nowadays for security nowadays; hashes can be computed too quickly (though the biggest flaw with md5 is the ease in generating collisions). Its only 128 bits (16^32 = 2^128 ~ 10^38); try sha-256 (2^256 ~ 10^77; its 2^128 times more keys) or sha-512. Key strengthening is a good practice (e.g., it takes 20 times longer to generate a rainbow table); but still 20 times longer isn't that long (e.g., use 20 machines and it takes just as long), but is done best with a random salt. Would be much better to key strengthen say 100000 times.

$password = "hello";
$salt = random_str(); // generate some relatively short random str
$password = sha256($password);
for($i=1;$i<100000;$i++){
    $password = sha256($salt + $password);
}
$sep = "|";
$password_scheme = "SHA256x100k";
$password = $salt + $sep + $password_scheme + $sep + $password;

Using a pseudo-code language where + concatenates strings and random_str() is a function that generates a short random string. The purpose of the random salt is that if an attacker sees your source code, sees your password-hashes, they need to do a generate a separate rainbow table for each different salt (or one for each password). So now, instead of just having to generate one rainbow table to get all the users passwords, they have to generate a rainbow table to get just one password. Also its a good idea to document the password scheme in the hash, so you may update it as necessary e.g., migrate from SHA256x100k to SHA256x1k if you need to be less CPU intensive or decide to move to a different hash later.

Granted its not the best idea to come up with your own custom crypto-method if you aren't a crypto expert. You definitely leave the opportunity for subtle security holes like timing attacks even with seemingly secure algorithms. bcrypt is probably your best bet.

Note: MD5 is particularly vulnerable to collision attacks, but you don't really have to worry about collisions in preimage attacks (which is the method of attack against password hashes). An attacker got a list of password hashes (h) somehow, and learned the hash routine (md5 x 20 or salted sha256 x 100k), and is trying to get any message m, such that hash_routine(m) = h, to let them into your system.

What collision vulnerability makes you worry about is that if you have a hash(m1) = hash(m2) when m1 != m2; so if you download something where people have checked that file m1 is safe and want to make sure that you actually downloaded m1 you compare hash(m1) to the public md5 hash. If there's a malicious version m2 with the same md5 hash then you cannot be sure m1 is safe by checking its md5 sum.

Answer 9

Rainbow tables function because multiple systems use the similar schemes for handling data. While it is well-regarded that adding a salt should be a universal feature of password hashing, adding a number of rounds also assists in defeating rainbow tables. To wit: a rainbow table for any subset of characters in MD5 cannot result in a match for any password in your system except by accidental collision. The reduction function of the rainbow table will convert each hash generated to a string that matches the letter, number, and symbol pattern that the table is designed for. The moment a hash is generated by your method that incudes a symbol outside that range (a virtual certainty as the input to your hash function is the out put of a hash), it will prevent the table from working.

That fact that your system is simple or even publicly known doesn't matter so much as that defeating a rainbow table only requires that your hashes cannot have been created in great number by the method used to generate that table.

Wikipedia has considered the issue of hash strength over time as their user database is well-known, very old, and used various hashing methods that are now insecure. The solution discussed was key stretching across the several methods. To calculate a password there, the hash method version is looked up, and the password calculated according to that. Upon login with an old version hash, it would be updated to the newer version.

Thomas mentioned that you should use more rounds for your hashing. What hasn't been talked about is how you determine how many rounds to use. The answer to this is fuzzy, but it basically boils down to, "How many iterations can I perform for the login load on my system?" If you have 10,000 users logging in every minute, you might be willing to devote a 25% cpu load to that. For that, pick a number of iterations that allows you to do roughly 700 calculations per second.

Answer 10

No, you're wrong. The problem with md5 hashes is that there is a relatively big chance on collisions: there are many strings that output the same hash. And since there are just 36^32 possibilities, which can all be tried in about 35 hours I believe (and it will get a result way sooner because there is a big chance for collisions), it is not considered a good hash anymore. Not to mention that there probably exists a rainbow table for 20 md5 hashes. Also, there is people that say md5 is actually reversible, but I'm not sure about that.

There are two ways to make your passwords harder to hack:

1. Use a static salt. This basically makes rainbow tables ineffective, because the hacker can no longer use just English words, since your salt (which the hacker hopefully doesn't know) is making up a large part of the string. Try long salts consisting of a lot of special characters;
2. Use a better, longer hashing algorithm like whirlpool or sha512. This obviously greatly increases the amount of possibilities;
3. Hash your string multiple (x) times. This is one of the things you've done right: if the hacker knows your salt and the amount of times you hash (so basically has access to your source code and database), this makes sure it takes him x times longer to get results;
4. Create a string-dependant salt. This is a salt randomly generated for every string you save in the database and stored along with it. This makes sure the hacker has to loop every possibility of the hash for every password, instead of being able to do it once for every passwords you have stored. If you have 500 passwords stored in the database, this way it takes the hacker 500 times longer to hack all passwords.

Hope this helped. :)

Answer 11

Generally, there is nothing wrong with hashing a value multiple times to make it more robust against brute force attacks. In fact, this is an already applied technique known as key stretching.

The only objections to your example is that you should use a cryptographically strong hashing algorithm as well as hashing scheme that includes a salt for more entropy and resistance to rainbow table attacks. At best an already proven password storage scheme like crypt that was specifically designed for passwords.

Answer 12

I don't think that attacker ... would be able to

You are assuming you know how attackers work.

You are assuming you know all the tricks attackers use, and that you have successfully defended against each and every one of them.

You are assuming there's nothing in the published research, knowledge that is available to anyone who cares to learn, that could help even a moderately skilled attacker break your security.

You are assuming that the attacker is unwilling even to perform a brute-force attack with stolen compute. (Have you considered the scenario where an attacker is patient and spins up a background job on someone else's server, a server that the attacker cracked into and isn't paying for, for the purpose of cracking your password file over a month-long period?)

This usually is a very bad assumption.

Answer 13

I understand this question has already been here for a little while and it has some excellent answers. How ever I think there is one problem that haven't been addressed. Using a strong algorithm (from a library) is the way to go, since those methods have been tested. But here is what i see:

I don't think that attacker with my DB would be able to decrypt any password with lenght > 2

The problem is not creating the most impossible algorithm to de-crypt. The problem is securing your database. For example if the attacker has a hold of your database, i don't think he/she will care much about the passwords in it.

Answer 14

Related links:

• Reference implementation of C# password hashing and verification

• NIST says PBKDF2 is suitable for Password Hashing

• How does PBKDF2 compare to BCrypt and other techniques?

Answer 15

Trouble with your method is that with each call on md5 you are enlarging the collision space of your passwords (no math proof about it, only naive understanding). As cool as this may look, don't try to make your security more complicated than it need.Chaining hashing algo is as sound as using multiple pseudo random to try generate a secure random. You could get simple security that is secure enough if you apply common sense practice.

Anyway usual advice occurs, use salt use an hashing algo that have a large enough collision space. If you want more security you should consider them at other levels, like server security, Managing staff security.

Anyway if you want to apply other advices of using bcrypt ( which is as bad as it requires to get the key to decipher the entire password list [O(n) once you get the password] , against looking up to a rainbow table against each entry [O(n*m)] ), I would at least advise you to use a public key cipher as the key to decrypt your data would not be needed in your input verification (use the key to encrypt the same way as you hash your data).