Mixing algorithms for password hashing good or bad?

Question

So I've come across the following algorithm for hashing passwords

function hashpassword($str, $salt)
{
$hashed_password = md5($str);
$hash = md5('more_salt');
$hash = sha1($hash.$salt);
$hashed_password = crc32($hashed_password.$hash);
$hashed_password = sha1($hashed_password.$hash);
$hashed_password = md5($hashed_password.$salt);
return $hashed_password;
}

Does mixing hash-algorithms like this increase or reduce the chances of collisions? Doesn't it end up being a case of find the weakest link? The use of crc32 looks like a terrible idea to me since it isn't even meant for this, but I don't understand the maths behind so I can't tell if it is or not.

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution?

What I'm basically asking is, is this strong or weak? Is there an obvious problem with it?

Answer 1

Does this look like it's done by someone who knows what they're doing or is it just a case of someone throwing all the algorithms they find together and hoping it's a good solution?

This is obviously someone who threw something together without knowing what they were doing. If they knew what they were doing, they wouldn't roll their own algorithm (“Dave, you are not a cryptographer. Stop it.”), they'd use one of the standard algorithms such as PBDKF2, bcrypt or scrypt.

PBKDF2 has been in the standard library in PHP since 5.5.0, and there are plenty of open source implementations that are slightly slower but work in earlier versions. It can be debated whether PBKDF2 is the best choice, but it's a reasonable one. There is no excuse to rolling your own.

The use of crc32 looks like a terrible idea to me

Indeed, the way crc32 is used makes it really terrible. If you replace crc32 by md5, the algorithm is merely bad, because it isn't slow. A password hashing algorithm must be slow to resist brute force guessing attempts. PBKDF2 achieves this by doing something similar to the algorithm you're looking at — repeated hashing — but 1. the hashes are assembled together sensibly and 2. it typically runs for hundreds of thousands of iterations, not a just a couple.

The way the algorithm uses CRC32 is a devastating flaw. It makes it easy to find a password by brute force. There's no guessing involved: a working password can be found in just a few minutes of computer time. This may not be the password that the user chose, but it would be a password that produces the same hash.

The critical issue is that CRC32 only has $2^{32}$ possible values, which is about 4 billion. A CPU performs that many operations in just a few seconds. If you look at the structure of the hash, it's F(CRC32(G(password)), salt). The exact structure of F and G doesn't matter, the issue is that the password only influences what goes into the CRC32 function. It only takes a few minutes to calculate G(P) for a few billion values of P. Some of them will result in CRC32 collisions, but so it'll take more than $2^{32}$ values of P to reach all $2^{32}$ possible values of CRC32(G(P)), but not a lot more. So if you calculate F(CRC32(G(P)), salt) for a little more than 4 billion values of P, one of them will be the target hash.

This doesn't necessarily give you the original password, just one that works on the system that uses this hashing algorithm. If you wanted to find the original password (because users often reuse their passwords, and other sites probably don't use such a broken hashing algorithm), you'd have to work a little harder. But not much harder. When you enumerated all the CRC32 values, you found G(password). The value CRC32(G(P)) that makes the hash pass is equal to CRC32(G(password)) where password is the original password, because the function F doesn't have any “random” collision (in fact, it has no known collision, although MD5 and SHA-1 individually do, and even for those hashes individually, collisions require crafting the two source values, not just one and then looking for a collision). Take a table of MD5 values of common passwords and filter the ones that have the target CRC32; unless the password is too rare to be in the table (and there are techniques to make huge tables), you'll find the original password.

Using multiple hash functions in case a weakness is found in one of them is not a bad idea, but it needs to be done right. PBKDF2 uses the password at each iteration. If the algorithm in this question was modified to use the password in the final SHA-1 and MD5 steps, it would drop back from being extremely bad to merely bad. And although using multiple hash functions is not a bad idea, it is by no means required; in fact, it's probably not worth the added complexity (i.e. the added risk of getting it wrong).

Answer 2

Mathematically the question is:

Is F(G(H(x))) more secure than F(x)?

For once: if F(x) is secure, then F(G(x)) or even F(F(x)) is not more secure. If you can't get in, then you cannot can't get in more.

On the other hand if in F(G(x)) the G is insecure, it is likely that F(G(x)) will become insecure as well.

Taking the example of CRC32: simply speaking that algorithm will essentially reduce any password down to approximately 5 characters (see detailed explanation by Gilles). As a 5 character password is much easier to crack with brute force, the security has been reduced. With luck F is secure enough to hide that issue, but without G the whole thing would have been more secure.

That leaves 3 scenarios when concatenating functions:

1. If all functions are secure, it won't get any better.

2. If some functions are insecure, security will get worse.

3. If - out of sheer luck or incredible skill - you happen to find a combination of semi-secure functions that increases security, you have invented new algorithm.

In almost all cases option 3 is not whats going to happen.