Passwords, Salts, And Security Concepts

Question

Introduction

I have done a lot of research, today, and have learned a lot about hashes and encryption (and the important difference between the two). One thing I have learned is this: people disagree on the efficacy of salting.

In the responses to this question (and particularly in the comments to the accepted answer), people conclude - it seems - that storing a randomly generated salt next to the hashed password in a database is the best way to secure passwords. There are several resources that state this and this will be the basis for my question.

In this question, the accepted answer states that with access to the all the possible hashed data values, the salt doesn't do much - conecptually - to make things anymore secure (though, that would be an unfeasibly large amount of stored data). Salts and hashing algorithms serve the purpose of increasing the number of possibilities for a single password entry, making the use of a dictionary-based attack against a database exponentially less efficient (here, I use the term "dictionary-based" more liberally, refering - really - to a table, whether that be a rainbow table, a table utilized for brute-force attacks (re-computing each time), or a simple lookup table).

The Bits and Pieces

From my understanding, a well encrypted password needs three (3) things:

1. To be hashed.
2. To be hashed in conjunction with a salt.
3. To be hashed in conjunction with a random salt (one salt for each password entry)

In order for a cracker to understand the resulting stored hash, he or she needs four (4) things:

1. Knowledge of the hashing algorithm
2. Knowledge of the salt
3. The correct plaintext password value (perhaps supplied as input from a dictionary-based attack (running a dictionary through the algorithm in conjunction with the salt)).

The Security Bit

The disagreement seems to surround what to do with the salt, i.e. where to store the salt. The phrase I keep seeing passes around Stack Overflow is "security by obscurity" - which appears to be the premise of a salt ("let's make this bit of information less 'seeable'"); however, from my reading, I have come to understand that security by obscurity doesn't really work. The premise of which seems to be: if the attacker has access to the algorithm and - if provided - the salt, he or she can figure it out.

The premise, then, of security is not solely the mixing around and changing of the values, but the means the database, transactions, or server use of stopping the types of attacks that would:

1. Yield the salt to the attacker
2. Allow the attacker to brute-force the database

Another user commented that it shouldn't matter if the code is exposed to the attacker as good code - or a good security algorithm - would prevent the attack from succeeding.

So, security then is a combination of three (3) things:

1. Preventing access to the server where everything is stored
2. Creating an algorithm that prevents brute-force entry to the database
3. Encrypting transactional information
4. Hashing (obscuring) sensitive data

The concern over the efficacy salts seems to stem from the assumption that the attacker has access to the database, itself.

Scenario: I've got a dictionary, your salt, and your hashing algorithm. Grabbing your password should be of no real trouble (this is why we work to stop brute-force attacks).

So, my question as a result of these conclusions (which are now on the Stack Overflow chopping block) are:

Questions

1. Does security also involve the protection of the location of the code, e.g. access to the hashing algorithm?
2. Why does generating a random salt for each password matter, particularly if the database has been exposed, i.e. does salt randomness really add anything to the security of information? Is this simply a matter of the exponential increase in time for an attack as a result of the random salt (e.g. making an attack less appealing)?

The security of the salt seems to lie in the attacker not having it, not strictly its randomness

3. Why store the salt in a database, at all?

Essentially, is all of this security 'stuff' (about the efficacy of hashes, etc.) just myth? Maybe I am just responding to the idea that nothing really will ever be entirely hacker proof (we just do everything we can)?

Why I Am Motivated To Ask

It seems to me that if your database is exposed, the salt - random or not - doesn't matter, especially if the database stores the salt.

Best practice, then, would be twofold (salts only adding a bit more security): (1) the hashing of sensitive information; (2) the protection - in the context of this question - of the database from brute-force attacks. There seems to be a lot of misinformation floating around SO (some of it probably resides in my derived understandings, above).

Here, I am assuming guards against Cross-site Scripting, etc. are already in place.

Answer 1

The purpose of the salt is to provide additional protection if the database is compromised. If you assume the database cannot be compromised, you can just store everything in plaintext and a password-based authentication system will work fine. The problem is that password databases are compromised all the time.

John Wu and Michael Burr have already covered why you want a salt to prevent passwords that are the same from appearing as the same hash in the database.

If you use a salt, it must be stored in the database. Otherwise a legitimate user cannot be authenticated without hashing the given password with all possible salts. So if the attacker gets access to a database entry, the attacker gets access to the salt too.

If an attacker gets access to database entries, we want to maximize the amount of work and time it takes for the attacker to discover the password by brute force. If there is no salt, the attacker can precompute (before getting access to the database) and store a rainbow table, which is basically a list of potential passwords that are run through the hash function. Looking up a database entry in the rainbow table is very fast, so if the attacker can store one and has access to the database, passwords are discovered immediately. When using a salt, the size of the required rainbow table increases exponentially with the salt length, so using a sufficiently large salt will effectively preclude the use of the rainbow table.

The attacker can still brute force the database entry. With the known salt and hash algorithm the attacker will check a dictionary. This is slow because the attacker cannot precompute anything; the attacker must use the salt discovered in the database. If the password is not in the dictionary, the attacker must resort to guessing passwords. Eventually, they will discover the password. This is also why password expiration is useful. If the expected time to brute force the hash is greater than the password expiration period, you will have changed the password before the attacker brute forces it.

Answer 2

Is security more about the protection of the location of the code than it is hashing the stored information?

Security is about building mitigations for attack vectors. There are many types of attacks and many types of mitigations. You've stumbled across a few of them.

Salt (a random string stored along with the hash) protects against a specific attack vector-- a rainbow attack launched by a malicious user with access to the entire table.

Pepper (a cryptographically random, secret salt value stored in a different location) protects against something else-- a dictionary or brute force attack launched by a malicious user with access to the hashed value and salt for a particular user, but without access to other systems (especially the system that stores the pepper).

If you are reading up on this you will find that a lot of experts think that pepper is more or less useless and amounts to "security by obscurity." The reason they feel this way is they believe, at least in principle, that if a cracker has access to your DB then he almost certainly has access to the storage location holding the pepper.

Why does generating a random salt for each (in this case) password matter, particularly if the database has been exposed, i.e. does salt randomness really add anything to the security of information?

In order to understand why this is important, you must understand how a rainbow table can be used to speed up an attack. With a rainbow table, a cracker can compute all the known hash values for common passwords and scan your entire database table to find them. This is much faster than a brute force attack on each individual entry. If a salt is combined with the passwords, it renders the rainbow table useless. In the end it is all about slowing the cracker down by making the problem computationally infeasible.

The security of the salt seems to lie in the attacker not having it, not its randomness

This is absolutely incorrect. It is all about changing the input of the hash from something predictable (e.g. a word from a dictionary) to something unpredictable (a word combined with a random string), which again is to thwart a rainbow table.

Why store the salt in a database, at all?

When the user signs on, he provides his password and not the salt (he doesn't even know the salt). The entered value must then be combined with the salt and then hashed. The system compares this hash to the hash stored in the database. If there is an exact match, the system can infer that the hashed value was created with the same password entered by the user, and therefore validate the authentication attempt.

Since the user doesn't know the salt, the database has to store it.

Answer 3

Salting a password is a counter measure against rainbow table attacks.

Consider a database with the following entries

User   |  Password
Jim    |  x7291s
Jane   |  m09var
Jill   |  x7291s
Jack   |  983d2w

and consider the following rainbow table that stores common passwords which a hacker may use to try and find password hashes in a db:

Hash    | Password
x7291s  | password1
983d2w  | puppies
34980f  | 12345
302jf0  | opensesame

A hacker can easily find commonly used passwords without having to compute or crack any hashes themselves. Jim Jack and Jill have been compromised while jane who uses a more obscure password has been saved from compromise.

without a salt, the hashing function always looks like:

hash_me("password1") -> x7291s

however with a salt:

hash_me("password1 208ejd209kj4ed02" ) -> mt2d89 // using Jack's salt
hash_me("password1 3094kf04390f0s9k" ) -> 3409fk // using Jill's salt
hash_me("password1 saf890af9k3049kf" ) -> f7g6s7 // using Jim's salt

you can see that the rainbow table looses its efficacy and is no longer usable. none of mt2d89 3409fk or f7g6s7 will match x7291s of password1