[Discuss] salt question

[blu at nedharvey.com (Edward Ned Harvey (blu))]

> From: discuss-bounces+blu=nedharvey.com at blu.org [mailto:discuss-
> bounces+blu=nedharvey.com at blu.org] On Behalf Of Eric Chadbourne
> 
> I have a basic question about salt.
> 
> I was reading this:
> http://www.openwall.com/articles/PHP-Users-Passwords
> 
> And don't quite understand this line:
> "Salts are normally stored along with the hashes. They are not secret."
> 
> So if they are not secret what is the advantage if your site is
> exploited?  Such as if the salt is stored in a config file couldn't the
> attacker utilize this with his rainbow tables?  Also I see in PHP
> crypt() you don't have to supply a salt.  How does that work?  Is there
> a distinct salt per hash, and if yes, where is this stored?
> 
> I have a log in system I wrote myself with sha1 but from everything I've
> been reading this seems inadequate.

This is crypto 101.  You should take the crypto course at coursera - free, and I can testify - very good.  Or just read "Cryptography Engineering" or similar.

Anyway, in the old days, systems stored passwords unencrypted on disk, with permission bits to protect it.  But it was too frequent that something is able to circumvent the permission bits somehow.  So then they started doing crypto hashes.  Instead of storing the password, store the hash.  Should be irreversible, right?  Well as you said, attackers started generating rainbow tables, so they could just find a way to bypass the permission bits, and easily lookup passwords based on precomputed hashes.  So then people started defending with salts.  A random number, or other random data, which is stored along side the hashes.  The user's password is first mixed with the salt, which essentially randomizes the rainbow tables.  So attackers first bypass the permission bits, find some way of getting the salt, and then they throw a bunch of CPU's at the problem and generate new rainbow tables.  So the defender then adds a "stretch."  Instead of just mixing the salt with the password and hashing...  You mix the salt, hash, mix with salt, hash, mix with salt, hash...  The specified number of stretch times.  The selection of stretch number should be somewhat randomized - If all you want to defend against is rainbow attacks, then a proper number might be somewhere between 16,000 and 32,000...  (It will force the attacker to need 16,000 to 32,000 times as much CPU horsepower for the same number of guesses).  But if you want to defend against brute force targeted attack, it should be somewhere between 10m and 20m.  (A 1-2 second calculation time.)

But the whole point is to reduce vulnerability of weak passwords.  No matter how much you salt and stretch, you'll still get hacked if your password is super weak.  "Password" or "Pa$$word" and so forth.  Even with a super salted, super stretched password, these are going to be among the first any attacker tries to guess.