Another Question About Salting Passwords

I know there are tons of blogs, articles, and questions on SO about salting passwords, but one thing I haven't been able to find an answer to is this:

If I am generating a password hash like t开发者_运维知识库his:

$salt = randomString
$password = $_POST['password'] 
hashedPassword = sha1($password.$salt)

And I have a table like this:

Users
user_id | hashedPassword | salt

Why is it so difficult for an attacker to figure this password out? Can't they just use a rainbow table, or brute force to figure out the salt, and then append the salt to every word in a dictionary attack?

Can't they just use a rainbow table, or brute force to figure out the salt,

How would that work? But it's a non-issue anyway - assume that the attacker knows the salt. Its purpose is not to be secret, that's why you store it right next to the hash.

and then append the salt to every word in a dictionary attack?

Sure they can do that, but they have to do it for that particular user. They cannot amortize the effort over all users in the DB, or use a precomputed table of hash->password mappings.

That, and only that is the point of a salt.

They can do that. The power is that they would therefore need to generate a new rainbow table for each password (or iterate through each dictionary entry for each password).

So the total compute time for a single password is still the same as for a common salt. But the total compute time for multiple passwords goes up exponentially...

Oh, and it's typically considered good practice to have two salts. One stored in the database that's unique per password hash, and one stored on the filesystem that's unique for the whole site. That way if the database is compromised, there's no significant worry as they only have 1/2 the salts used. Sure, if the filesystem's compromised they could get it all, but if the filesystem's compromised, they can install password sniffers and other nasties...

I hope that helps...

Well, for one they cannot use a precomputed rainbow table to find a collision - an attacker would have to generate their own rainbow table using the salt. Also, assuming every user has a different salt, that rainbow table would only work for a single user - making their job that much more difficult.

The point of the salt is not to make a single password stronger. It is about preventing the attacker from scaling up, when attacking several passwords. With the salt, the attacker cannot reuse his efforts into attacking another password; he must rehash his dictionary.

Rainbow tables are nothing magical; they are just a special case of a precomputed table, which is akin to a simple dictionary attack with slightly distinct space-time modalities. Building the rainbow table implies more or less going through the complete dictionary. Precomputed tables are a gain for the attacker if he can use them to attack several passwords. If passwords are salted, then precomputed tables, rainbow or not, will not gain him anything.

That being said, a single password is often weak and can be brute-forced, because the average password will fit in the average user brain, and, as such, cannot be very complex. To mitigate that risk, one should use repeated or iterated hashing. A salt does not help here (but it does not harm either). See this answer for details.

Let's use a simple example: we have two databases, Alpha and Beta:

Alpha just hashes the password and stores the result:

row: {
    passwordHash = Hash(password)
}

Beta creates a random value for each user and uses it as part of the input to the hash function:

row: {
    salt = RandomString(),
    passwordHash = Hash(password + salt)
}

Now say your adversary has prior knowledge that some of your users are using the password: "password"

To find all users in Alpha whose password is "password", you only have to calculate the hash of "password" once. Here's an example from SQL:

DECLARE @Hash INT; SET @Hash = Hash("password");
SELECT UserID FROM Users WHERE passwordHash = @Hash

Since it just involves integer equality, it's about as efficient as a query can be. Even if Alpha had hundreds of thousands of users, it would return very quickly.

The fact that Beta's hashes include a row-specific random value in every password hash, you cannot write a similarly efficient query for it. The closest you could get would be to re-evaluate the (intentionally expensive to compute) hash function for every row's salt:

SELECT u.UserID FROM Users u WHERE u.passwordHash = Hash("password" + u.salt)

The fact that searching for a known password is so expensive should indicate how expensive it is to perform a brute force attack, even if that attack is guided by dictionaries of common passwords, or algorithms that attempt to mix words and numbers together to create passwords the way humans do.

You already know that salt is a measure to defend against "rainbow table" attacks, so your question is... how?

"Rainbow table" has become a flowery term for any attack that computes the hashes for common and likely potential passwords ahead of time and stores them in an efficient lookup table. Once you have that table built (which can take several hours), you then iterate through every User and see if their password hash is in the lookup table. If it is, you'll have guessed that user's password.

The users within Alpha are indeed vulnerable to this kind of attack. Alpha will have equivalent hashes for equivalent passwords, so a hash table or rainbow table could be used to reverse the hashes. But Beta cleverly sidesteps this vulnerability by making the result of the hash function unique to the user by virtue of the salt.

I hope this helps some reader, someday!