hash(hash()) vs salted hash

Question

Since the introduction of Rainbow tables, and using only hashed passwords (e.x: MD5) to stored passwords in database is not the best secured way.

When people talk about salted hashes, the always use it in this way hash(password . salt) or even hash(hash(password) . salt).

I don't know why to use salt, and add extra entry for each password to store the salt? Why don't we just use hash(hash(password)), or even hash(hash(hash(password)))?

Is it more secure to put salt? or just the sense of being more complex?

Answer 1

You can build a rainbow table based on a dictionary for hash(hash(pwd)) in just twice the time as for hash(pwd) (even less because performance is mainly about disc writes) and it wouldn't even be larger. Using salt greatly expands the size needed for the table up to the amount where it becomes impractical.

Also (even more important), users often have the same password. Without an individual salt per user, if you've broken one users password, you've broken all other users that have the same password.

Answer 2

To keep things simple, let's imagine everyone uses digits as their passwords.

If everyone uses 8 digits as their password, that's 100,000,000 possibilities. If you're trying to break the system, you need to hash all those possibilities. If you have a "hash of hash of hash", you still just need to hash those 100,000,000 possibilities - just in a slightly more complicated way.

Now let's pretend we have a 4 digit salt as well. Now, instead of 100,000,000 possibilities there are 1,000,000,000,000... we've given a potential attacker 10,000 times the work to do, instead of just 3 times as much work to do.

Basically, think of a salt as a way of artificially making everyone's password longer, and thus extending the space that a dictionary attack has to work on.

EDIT: Just to be clear, given that the salt is provided in plain-text as well, you would still only have 100,000,000 possibilities to try to attack any one hash. However, it means that after trying those possibilities for one password, the attacker wouldn't have any useful information for attacking another password. Without a salt, an attacker could create a dictionary of 100,000,000 possibilities and then know all the passwords in a database, given only their hashes. In other words, salts help to prevent bulk attacks. They also mean that you can't pregenerate the dictionary: in order to attack a single password effectively, you have to know the salt beforehand. Without a salt, you could compute the hash of every possible password before you get access to the hashes themselves.

Answer 3

If you don't use a salt then an attacker can build a single rainbow table can be used to attack every password in your database. Hashing multiple times does not protect you without a salt, because rainbow tables work by chaining hashes together in exactly the way you describe: hash(hash(password)).

If you add a random salt for each user then the attacker cannot re-use the same table to crack two passwords so their work becomes much harder. As an added benefit, two users with the same password will hash to different values if a salt is used.

Your idea of iterating the hash is still good, but you need the salt too. If you do this:

function hashPassword(password, salt) {
    result = hash(salt . password)
    for (i = 0; i < 1000; i++) {
        result = hash(salt . result)
    }
    return result
}

then you make the attacker's work 1000 times harder with a negligible effect on legitimate users. Note that attackers can test millions of candidate passwords each second on a single, low-end computer - hash functions are designed to be fast. This 1000 iteration loop can change a feasible attack into one that will take 100 years or more. When computers speed up in 18 months time just change the number of iterations to 2000.

The salt, hashing algorithm and iteration count do not need to be secret and can be stored in your database alongside the computed hash. You can choose a fixed iteration count and hash algorithm, but the salt must be randomly generated for each user.

Answer 4

Both iterating the hash and using a salt increase the security of password hashing. But they protect against completely different attacks.

Iterating the hash increases the work required for brute-force attacks. But you shouldn't use a naive iteration as you suggest, but an algorithm designed for it, such as PBKDF2

A salt protects against pre-calculated tables, so it should be different for every website and user.

Answer 5

The point of the salt is to make dictionary attacks moot. Now no matter how much you rehash a hash, the same input is always going to yield the same output hash, and therefore one can build a dictionary for that. So while multiple hashing may make it more difficult for brute-force attacks, it doesn't do anything for dictionary attacks.

Answer 6

Nothing stops anyone for building a Rainbow table for doubly hashed passwords.

Answer 7

I use a comparible method to hash passwords for users that login. A salt (random value) is generated in the session and is sent to the client. The user enters their password, which is then hashed with the salt and sent back. This makes sure that the value sent from the server is different each time, making it harder to break in using a man in the middle attack.

Answer 8

The salt is a site- or user-specific value. That means that in order to retrieve the passwords, an attacker must have both access to the database AND know the salt.

In addition, the attacker could additionally generate a table once and then use it against multiple sites. However, with salts, attackers must generate one table per site or even once per user(making the attacks slower).

Site-specific salts add very little to the security of a website. As said in comments, having a combination of site-specific and user-specific salts can significantly improve security over just a site-specific salt.

A few years ago I asked here on stackoverflow a question about password storage which might be helpful to you. See Secure hash and salt for PHP passwords.