Webapp password storage: Salting a hash vs multiple hashes?

Question

For security's sake, of course it's blasphemous to store passwords in plain-text; using a hash function and then doing a re-hash and comparison is considered much better.

But, if bad guys steal your database, they still could brute-force against the hash and conceivably retrieve many passwords.

The question I have is: Is salting a hash as effective for the effort as say, combining multiple encryption methods with a signifier?

For the sake of example, let's say MD5 = 1, DES = 2, and AES = 3. During the first time the password is stored, why not generate a random sequence of these numbers (i.e. "231"). Then, hash the password in that order (e.g. for "231", DES, then AES, then MD5) and add the digits to the front of the hash. Then, comparison does all three hashes in a random way, by taking the first three digits to see how it should be compared.

I know this is more computationally expensive than adding a salt before hashing, but given the random algorithm assignments plus the task of brute forcing (and taking into account that the attacker would have to have source-code access to see your enum of what numbers are what, etc.), would it be more effective?

Answer 1

Short summary: Don't do it, use an established password hash function like bcrypt, scrypt or PBKDF2.

---

Long form:

What you are doing here in effect is this:

1. Create a combined hash algorithm out of several different hash algorithms (or block ciphers made into hash functions).
2. Use a salt input to the combined algorithm to decide which of these algorithms to call in which order.
3. Store the salt and the resulting hash.

There are three ideas hidden here: A salt, repeated hashing, and use of different hash functions.

The reason to use a salt for password storage (or any usage of a password, really) is to avoid that the attacker can simply use a rainbow table - or, in fact, to make the needed rainbow table that many times bigger. As an example, if you have tree algorithms which will all be used, in a random order, you in effect have 6 possibilities (123, 132, 213, 231, 312, 321), which means a rainbow table has to be six times bigger.

At the same time, the hash execution time will be three times longer, so generating the rainbow table takes in effect 18 times the original time.

To make a rainbow table attack totally ineffective, you use a salt that big that it is not practical anymore to use a rainbow table (since it would need to long to generate and too much space to store). The Bcrypt algorithm, for example, takes an 128 bit salt input. A rainbow table for just a single password and all possible salts would take $2^{128}$ entries.

A salt alone still does not help against a brute force attack - you can check all realistic passwords in a dictionary for MD5(salt | password) == hash just as fast as MD5(password) == hash.

Here your second idea comes in: Repeated hashing. In your example, you use three hash invocations for each password - this means brute-forcing a single password takes three times the time as brute-forcing it with a single hash function. Three times is not much.

Instead, use a lot larger number of hashes. There are specialized slow hash functions around (like bcrypt), which have a configurable work factor build in - e.g. they take beside the hash and password input a work factor parameter, which says how often is should loop. You then can simply scale this with the hardware progress so your user does not have to wait too long for login, but an attacker still needs very long to crack the password.

Other schemes (like PBKDF2) use a fast hash function (like MD5, SHA-1, SHA-2) a large number of times (something like Hash(password, hash(password, hash(password, ...(password, hash(password, salt))...)))).

Your third idea is using a different hash algorithm depending on the salt. Using a different salt as input to a hash function has a similar effect to using a different hash function, but is much simpler to implement. Using different algorithms makes your combined algorithm harder to analyze (i.e. harder to guess about its security), and also harder to implement. Also, you are depending on the security of multiple algorithms.

I could think about using different algorithms to secure against cryptanalytic breakthroughs in any of them, but then you should always use all of them, and there is no reason to randomize which algorithm to use.

So, don't do this, use instead an established password hash function like bcrypt, scrypt or PBKDF with an appropriate work factor. (These all include the use of salt.)

Answer 2

I don't see salting a plain hash as sufficient, given the speed with which modern processors (and especially special-purpose chips) can do a brute-force search. Without commenting on your alternative, you should just use pbkdf2, bcrypt, or scrypt. They're all designed for what you're trying to do, and have (to varying degrees) been publicly reviewed.

Answer 3

1st, you know that AES, etc, are for encryption, right? Don't consider using "encrypt the password" because if someone gets your key, it can discover all your secrets.

2nd, the problem with hashes is the speed. That's why the best approach is to use slower hashing algorithms. While it'll make your login take longer (let's say, 100ms), it also slows down the brute-force attack. So it's good for you. That's where Bcryp, pbkdf2 and scrypt comes to help you.

3rd, don't do the hash just one time. You should do a hash(hash(hash( ... ))) a lot of times.

4th: use salt to make it harder. That way you'll add more entropy to the user password, avoiding the "common password" problem. A good salt is a very random one, one salt for each user.

And, in the end: don't forget other security points of your application. For example, if you add the "secret answer" scheme to your site, and them forget to secure the answer the user provides, all your effort might be gone as well.

Answer 4

AES and DES are encryption, not hashing. You cannot do comparisons on encrypted values with these algorithms because they would change on each encryption call.

Assuming you meant all hash algorithms...

It would be possible to compare values to others in the table. So if I see in a hash '1234567890abcdef' I could conceivably find that value in other records, and if there is a match and its on the boundry for the hash (e.g. MD5 hash is always n bytes) I could then find other users with the same password.

You would have to go one step further and hash the combined value.

You would also have to store the position of the hashes (123, 231, 321, etc), and as a result you really lose a lot of randomness if you only have 3 positions. If you have thousands of users then the possibility of some using the same passwords, and the possibility that their hash sequences are the same as other users starts to increase. After a certain number of users it seems pretty well guaranteed that you will have collisions.

The other thing is that you've just added a whole lot of complexity that will probably come back to bite you later on because its not an industry accepted design.