Salted password + hash - is it really useful?

Question

I am new to the topic and wanted to know the concept of having salted hashes before going down to the technical details.

From what I have understand

• password - plaintext
• hash password - plaintext password being encrypted by a hashing algorithm that is irreversible (one way)
• salted hash password - random text + plain text password being hashed / hash (salt+plaintext)
• a rainbow table is list of pre-calculated hash results from a list of dictionary words, comparing the hashed passwords against the list in the rainbow table for a match will reveal the actual password being used by the user.

Hence, 2 of the same plaintext passwords will not have the same hash value due to the random value of the salt.

The salt is sometimes stored with hash password.

---

From the above,

1. I am assuming that there is no max password attempts - How does having a salt prevent a malicious user from attempting to to brute-force the password into the system by just trying random password (e.g over a dictionary list)? They are using the same legit login mechanism as compared to the actual-user by just attempting/inputting different password per login.
2. If the salt prevents a rainbow attack by having random data appended to the plaintext before the MD5 hash, the very 1st criteria is that the rainbow attack has a list of hashed (salt+password) to compared with. Now, isn't the system already compromised when the malicious user has that list of hashed passwords?
3. If the salt and hashed password are stored together, wouldn't that malicious user (instead of using a rainbow table) just recompute his list of dictionary text + the salt retrieved to derive the hash results, and compare them against the hashed password in the retrieved list?

It is just that now the rainbow table is built based on a single salt value for a particular hashed password entry. For another password entry, another precomputed rainbow table based on that associated salt will have to be use.

Is my understanding wrong? So what does salt really help?

Answer 1

From your initial understandings:

• A rainbow table is, for a given hash algorithm, an exhaustive map from hash outputs to inputs. Given that the table must cover the entire output range, and that a good hash algorithm makes it difficult to predict input from desired output, and expensive to compute the output, it should be very expensive to generate.

As to your questions:

1. Salting your hashes does nothing to prevent brute-force attacks against your login page. It instead protects against your (or someone else's, if they're using the same hash algorithm as you) DB being compromised and the attacker knowing the hashes. Once they have the hash, they look it up in the rainbow table to find the input that will generate that hash, and enter that in your login page. It doesn't even matter if the input is not the same as the user's password, as they will both hash to the same value.
2. As noted above, rainbow tables are expensive to generate.
   • If you use no salt and a common hash algorithm, the table already exists and all accounts are compromised. This is cheap to do.
   • If you use 1 salt for all your users or a unique hash algorithm, the attacker will have to generate 1 rainbow table and all accounts are compromised. This is a expensive, but perhaps the payoff of getting all accounts is worth it.
   • If you use a unique salt for each user, the attacker will have to generate 1 rainbow table for each user, regardless of what algorithm you use. This is expensive, and the payoff is 1 account. Hopefully this is not worthwhile.
3. Salting does not protect against dictionary attacks

The aim is to make the attacker do as much work as possible, enough that it'll be easier to just find the user (or if the attacker is a very clear thinker, your sysadmin) and beat them with a rubber hose rather than commit non-trivial resources to computing rainbow tables.

As an aside, MD5 is not a good hash algorithm in this context, it is far to quick to compute.

Answer 2

Simple version : Salts don't stop brute force attacks against a single user's password. What they stop is is you being able to do a brute force attack against all of the users' passwords at the same time.

Answer 3

Salt don't help against brute force attacks, as the attacker is firing all passwords known to men, he will eventually get lucky and guess it right.

Salts become helpful when the stored passwords have been stolen, to find the password that belongs to the hash (I wouldn't use MD5) you can take a random password, hash it, and check it against the hash you found in the stolen passwords. Rainbow tables make this go a lot faster.

However, when using salts, he wont find the password but the password+salt, meaning he will have to subtract the salt to find the actual password. The point of using a salt is that you use a different one for each password, so if the attacker cracks one password, he will do only that, crack that one password, even if someone else is using the same password, that hash will be completely different.

Using salts is not about making it impossible to crack a password, it's about making it take long to crack all the passwords, as you will have to check each and every password as a unique hash, even if the same password is used again.

It's all about making it time consuming to crack all the hashes.

Answer 4

Here is the answer to related question which should resolve all of your confusion: How to securely hash passwords?

EDIT:

To question 1.

As was said by other answerers, you can't prevent brute force by salting your passwords. Other techniques exists for this task, usually it's throttling of some kind and limiting number of attempts. Gradual throttling with each next failed attempt works best from the UX standpoint.

To question 2.

Here is the excerpt from the above linked answer:

Since the overall contents of a server that can validate passwords are necessarily sufficient to indeed validate passwords, an attacker who obtained a read-only snapshot of the server is in position to make an offline dictionary attack: he tries potential passwords until a match is found. This is unavoidable. So we want to make that kind of attack as hard as possible. Our tools are the following:

<...>

Salts: among the advantages of the attacker over the defender is parallelism. The attacker usually grabs a whole list of hashed passwords, and is interested in breaking as many of them as possible. He may try to attack several in parallels. For instance, the attacker may consider one potential password, hash it, and then compare the value with 100 hashed passwords; this means that the attacker shares the cost of hashing over several attacked passwords. A similar optimisation is precomputed tables, including rainbow tables; this is still parallelism, with a space-time change of coordinates.

The common characteristic of all attacks which use parallelism is that they work over several passwords which were processed with the exact same hash function. Salting is about using not one hash function, but a lot of distinct hash functions; ideally, each instance of password hashing should use its own hash function. A salt is a way to select a specific hash function among a big family of hash functions. Properly applied salts will completely thwart parallel attacks (including rainbow tables).

To question 3.

To put it short, relation between rainbow table and salt is that you have one rainbow table per salt value. To calculate a rainbow table is the same as bruteforce the password which uses single salt or does not use any at all. It costs time, and usually a lot of it. If all of your passwords in the database are salted using different salt value, attacker's job in case your database gets stolen, in layman's terms, just have increased by order of magnitude. For each password the specific precomputed rainbow table should exist.

It's not a question of protection per se, it's a question of making attacker's life harder.

Answer 5

Your first point is easily answer. There is nothing that prevents that. Salt are not a mean to avoid brute-force attacks anyway.

Your second and third point are more relevant. Salts are here to avoid having one rainbow table to rule them all. That is to say, for each user, you have a different salt. This means that if you want to attack multiple users, you have to make the work of computing the rainbow tables for this particular salt. Rainbow tables computations are not free, especially when the salt value is large enough. It takes time and money.

Of course, salts are not the solution that will solve all password problems. However, security is about trade-off. You have a simple method to verify the user authentication, but you make it difficult (time-consuming, money consuming) for the attacker. One of the thing to know about security is that "with the right means, you can break anything". Not all attackers has access to all necessary means.