15
$\begingroup$

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?

$\endgroup$
4
  • 8
    $\begingroup$ That crc32 in the middle of it will make it quite easy to brute-force. Because crc32 only outputs 32 bits, and thus 1 in 2^32 passwords will match the final hash. $\endgroup$
    – user253751
    Aug 18, 2017 at 0:01
  • $\begingroup$ If you were truely concerned that a method may get broken, some sort of combination through concatenation might help. $\endgroup$ Aug 18, 2017 at 9:20
  • $\begingroup$ @DennisJaheruddin I think the . might be a concatenation-operator in whatever language the OP is using. $\endgroup$
    – Philipp
    Aug 18, 2017 at 14:42
  • $\begingroup$ @Philipp I think so too, but what I mean is that rather than combining F and G by doing something in the trend of F(G(x)) a better approach to combining functions might be in the trend of F(X1).F(X2). -- This is just conceptual, not a suggestion for implementation. $\endgroup$ Aug 19, 2017 at 8:42

2 Answers 2

26
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ CSC32 is even worse than that - Given a message you can calculate what modifications are necessary to four consecutive bytes of the message to get a desired result. $\endgroup$ Aug 17, 2017 at 14:09
  • 3
    $\begingroup$ @EugeneStyer Yes, but that doesn't help here, because it's CRC32(MD5(password)). If you need to change some bytes in the MD5 value, there's no better way than brute-forcing the password, and if you do that then there's no advantage in the ability to invert CRC32. $\endgroup$ Aug 17, 2017 at 15:09
  • $\begingroup$ @Gilles So I understand this is terribly insecure but I have trouble understanding the part about breaking it. You say the password only influences what goes into the CRC32, but what about the first round of MD5? If it's possible to create something that can crack these hashes fast, I would like to try and do it, I don't care if the result is the real pass or not. $\endgroup$
    – Luke
    Aug 17, 2017 at 20:52
  • 1
    $\begingroup$ @Luke Given Z, it's easy to find Y such that crcC32(Y)=Z. But here Y=md5(X) and, given Y, there's no better way to find X than guessing. Guessing may be fast or slow depending on how strong the password is. (cont.) $\endgroup$ Aug 17, 2017 at 21:15
  • 1
    $\begingroup$ @Luke But you can also take the problem from the other end. Run through a lot of X values, calculate Y=md5(X) and Z=crc32(Y). MD5 has no collisions unless you deliberately craft them, so every X value will give you a different Y. And different Y values will usually give you different Z, because you also have to work a little to get a crc32 collision. If you go through more X values than there are distinct Z values, you'll eventually run through all the possible Z values. Since there are only 4 billion, that's doable on a PC. $\endgroup$ Aug 17, 2017 at 21:16
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.