How long should a salt be to make it infeasible to attempt dictionary attacks?

Question

I'm designing an authentication system that works like the following:

1. User enters password
2. Salt is generated.
3. Password is hashed with whirlpool
4. Whirlpool hashed password concatenated with the plain salt
5. The concatenated version is hashed with sha1 and stored in the database.
6. I check the password is correct by hashing the password on the application layer, and then doing this (in MySQL):

MySQL

WHERE `Password` = SHA1(CONCAT('$hashedPassword',`Salt`)) AND [..]

At the moment my salt is 64 bytes. Will that be enough to make it infeasible to dictionary attack?

I'm sure sha1 has known vulnerabilities, but it's the only function available on my version of MySQL (5.1) that I can use on the database layer, rather than selecting the plain salt over a connection between the app and the database layer.

Answer 1

I think you are misunderstanding the concept of a salt. Salts do not prevent or slow down dictionary and brute-force attacks significantly.

The whole point of using salts is to avoid the possibility that someone has already precomputed a dictionary/brute force attack for your password hashes (for example using rainbow tables). Thus, it only needs to be long enough to exclude the possibility that such a table already exists for a specific salt.

Considering the typical size of such a rainbow table, it is extremely unlikely that somebody already has precomputed such tables for salts of even small size like 8 bytes or so (consider the number of possible salts: 256^8 = 18446744073709551616). The premise is of course that the salts are randomly generated and that you don't use the same salt value multiple times. 64 bytes can't hurt, of course, there's nothing wrong with that.

However, if you want to make brute-force or dictionary attacks infeasible, it won't help you to use a longer salt. Instead, make your users to choose strong passwords and consider using key stretching.

Answer 2

My copy of Practical Cryptography (Ferguson, Schneier) with a copyright date of 2003, suggests using 256 bits (32 bytes) for salt length. It says that 128 bits is "probably" okay, but, as it points out, bits are cheap. Given that, the relatively minimal cost of storing 64 bytes for a salt on disk for each password seems reasonable. It is probably overkill but it would not hurt.

You may also want to consider password stretching (repeat the hash function many times) to increase the computational complexity of attacking a password via brute force. Adding a few hundred milliseconds to the cost of checking the password can greatly increase the cost of a brute force attack.