Password hashing and blowfish

Question

What I'm about to say is probably going to make me look like an idiot but it's better to be wrong and learn than have unanswered questions.

Ever since I started dealing with passwords I wondered what the big fuss about hashing passwords is anyway, since if somebody got a hold of your database they could find out any password no matter what hashing technique is used.

So basically the big flaw of old hashing functions were rainbow tables, something that the currently modern algorithm used by PHP in their password hashing API, blowfish, deals with. Of course it is pretty complex and undoubtedly it's built by people way smarter than me, but still I just couldn't help but wonder, if I built my own hashing function that wasn't vulnerable to rainbow tables and didn't store the salt in obvious places such as extra columns in the database or use user information like name or email as salt, would that be any good?

I just spent like 5 minutes to prepare this example for you, which uses, of course, md5, as I know it is the most hated around PHP developer critics :D

function my_password_hash($password){
    $salt = substr(md5(str_shuffle('0123456789abcdef')), 0, 5);

    $hash = substr(md5($password . $salt), 0, -5) . $salt;

    return $hash;
}

function my_password_check($password, $hash){

    $salt = substr($hash, -5);

    return substr(md5($password . $salt), 0, -5) . $salt === $hash;
}

$hash = my_password_hash('qwerty');

var_dump(my_password_check('qwerty', $hash)); // TRUE
var_dump(my_password_check('qwertY', $hash)); // FALSE

It will produce different hashes for the same input every time and the salt is blended in the final output hash, if you don't explicitly know where it is, I don't think it can be found, but that's why I'm posting here, to find out if I'm wrong.

Answer 1

Your first assumption, that an attacker who gained access to the database can find all the passwords, is invalid. Even a single invocation of MD5 with no salt and no iterations will keep the strongest passwords secured.

But only a very small percentage of users use a password, which is strong enough to remain secure under such a simple hashing.

Calling rainbow tables a weakness is not exactly correct. Rainbow tables is a method for attacking a very specific weakness in some password hashes. But there are other ways to attack the same weakness, even some methods that consume less memory and CPU time than using rainbow tables.

This weakness is easily addressed by using a salt. A salted hash will defeat both rainbow tables and most other brute force attacks. State of the art password hashes have been using salt for multiple decades. Even the old (and by now obsolete) DES based password hash used a salt.

Your approach to salting does share a weakness with the salts used in the DES based passwords, and that is the length of the salt. The salt is supposed to be long enough that it never repeats, not even by coincidence if every computer system in the world used the same password hashing algorithm for all passwords stored for centuries.

Using a salt which is long enough is practically free, so there is really no reason for using a salt with only 20 bits of entropy.

Appending salt and hash is common practice. In that respect your approach is practically identical to standard methods. Standard methods however include a format specification, in order to preserve compatibility in case the algorithm need to be changed. They also usually put an explicit separator between salt and hash.

Leaving out the separator and pretending that will slow down an attacker is security through obscurity. It doesn't work.

Obscurity is more likely to confuse the developer and cause a security flaw to be left in the code during development, than it is to actually prevent an attack.

The way you are generating randomness looks fishy, but I don't know enough about the specific platform you are developing for to say if it is a sensible approach.

There are other aspects about password hashes that may impact your security, but there isn't entirely consensus on those points.

There is agreement that it is better to use newer hashes with no known weaknesses, rather than using MD5. However none of the known weaknesses in MD5 could actually be used to attack the password hashing in your question. An attack against it would surely focus on weak passwords as well as the short salt.

Then there is the question about whether password hashing should use iterations or do all kinds of other expensive computations. Such approaches will slow down legitimate usage and brute force attacks by the same factor. As such they are not very effective. Increasing the length of a password from 10 to 11 characters would only slow down legitimate usage by 10%, but it could slow down brute force attacks by an order of magnitude. This is why longer passwords is a better way to slow down attacks.

That's not to say that iterated hashes are useless, they do slow down attacks. But they also slow down legitimate usage on your own server, which makes it an easier target for DoS attacks.

Answer 2

If someone gets access to the database with passwords in, they might well have enough access on the system to read the code implementing the hashing as well. If they do, then they know the structure of the hashed passwords.

It is also common for the attacker to know at least one password on the system (their own), so if they get the hash for their own password then they may be able to work out the structure by comparing their own password and salted password.

The good news is that salting works even if the attacker knows how the salt is constructed and stored. For very little cost when setting & checking passwords, you make it enormously more expensive/slow to crack passwords in bulk. So there is no need to worry about hiding the structure (Unix/Linux shadow password files do not, for instance) - instead just worry about generating salts with enough entropy that they make the attacker's job much slower.

While a hash can always be reversed with enough time, the goal is only to make it slow/expensive for the attacker, so a) the attacker gives up and move on to an easier target, b) you can notice that you have been hacked and tell users to change their passwords before many passwords have been compromised.

If I understand your PHP right, it cuts off some of the md5 hash to replace it with the salt - directly reducing the security of your hash. Trading off the strength of the hash for a little obscurity is a poor tradeoff, since salting works even if the attacker knows how it is done. Ideally use an existing implementation like crypt(), since its implementation (on modern systems at least) should reflect best practices.