Why can salts be public?

Question

From what I understand, salts are called "salts" rather than "keys" because they are allowed to be public. I understand that applying a random salt makes it difficult for rainbow table attacks because the hashed and salted password will be different for each user, even if they have the same password.

However, isn't going from salted password to hashed password trivial if the salt is public? Even if an attacker has to recalculate the hash for every user, that is still only one calculation for each user. And if applying a salt is O(1), shouldn't undoing every user cost O(n)?

I feel as if I am missing something. To me, it seems like undoing the salt is only one additional step that can be easily automated, and in the end leaves hashed just as susceptible to rainbow table attacks.

Answer 1

The point of a unique salt is this: the work that the attacker does to crack one user's salted password cannot be reused against another user. So it addresses this point of your question:

Even if you had to recalculate the hash for every user, that is still only one calculation for each user. And if applying a salt is O(1), shouldn't undoing every user cost O(n)?

Think of it this way. Suppose you have n users, and the attacker is going to perform m password guesses. If you don't have salts, then the attacker can check each of their m password guesses against all n users—which means that they get to perform m × n user/password pair guesses.

With unique salts, on the other hand, each of the attacker's m password guesses is only applicable to one user. So they can only perform m user/password pair guesses. This is a big win for the defender.

And this analysis assumes that the attacker knows all of the salts. So the answer to your question, strictly speaking, is that salts can be public because they offer a big security improvement even if the attacker knows them. (In contrast with keys—e.g., ciphers offer no security against an attacker who knows the key.)

We can tweak your question a bit and ask: why not keep salts secret? Well, that's actually a thing; the popular name for "secret salts" is pepper, and there are people who use them—they offer further security beyond what public salts do. But many folks just don't think that the extra security is worth the time and hassle of keeping additional secrets. Others are actually skeptical that it adds more security in practice:

• http://blog.ircmaxell.com/2012/04/properly-salting-passwords-case-against.html
• https://stackoverflow.com/questions/16891729/best-practices-salting-peppering-passwords

Others however are more positive about peppers. Notably, the Password Hashing Competition's call for submissions specifically allowed for algorithms to accept a "secret key" (pepper) in addition to a salt.

But one thing is for sure—using peppers is much more complex than using public salts, because of the extra measures needed to make sure that a compromise of the password database doesn't also compromise the peppers.

Answer 2

Let's solve a simpler problem. Pretend the attacker has a list of all unique passwords used in the database, but doesn't know whom they belong to. This list contains p passwords. There are n users. p can be no greater than n but in practice it will always be strictly less than n.

With a non-unique salt, the attacker must calculate every password hash with the salt applied. That's O(p) hash calculations.

Without any salt, if a rainbow table for the hash algorithm already exists, the attacker just looks up the hash values for each password from the lookup table, requiring exactly zero hash calculations.

With a unique salt, the attacker must calculate roughly half of all password hashes for each user, thus requiring O(n×p) hash calculations.

In this very simplified example, with p≅n, it's the difference between O(1), O(n), and O(n²). In reality, the attacker should NOT have a list of all unique passwords in your database and must waste a lot of hash calculations trying passwords that are not even in the database; in other words p≫n. So in real-life scenarios the impact is even more extreme, especially for the unique-hash case.

I'm talking about the number of hash calculations for the size of the computation here, because if your system is well-designed with a slow hash, then that will be the most expensive part of the attack. If your most expensive part is enumerating and comparing a calculated hash to each user, then you have a more severe problem.

Answer 3

From what I understand, salts are called "salts" rather than "keys" because they are allowed to be public.

That's only part of the story. Keys are used in a reversable encryption operation. A hash is designed to be irreversible. A Salt in a Hash is more like what encryption routines call an Initialization Vector. The intent is to make it unique.

However, isn't going from salted password to hashed password trivial if the salt is public?

The salt is not public. It is stored alongside the hash. A database of stolen hashes is harder to crack if each has a unique salt, even if all the salts are known.

---

from my other answer to a related question:

You should be using a Slow Password Hash. (i.e. bcrypt) By 'slow' I mean computationally expensive, taking more than 100ms (on your hardware) ^{with DoS protection *} to test a single password. This is to increase the processing power needed (on attacker hardware) to find the password by brute force, should the hash be stolen.

Per-user unique salt is highly recommended. (in the case of bcrypt it is automatically generated) Salt should be highly unique (i.e. long & random). Using unique salt means an attacker would have to run a separate brute force Job for each user.

If there were 'no salt', the attacker could instantly use a Rainbow Table and no brute force at all.

If you use a 'shared salt' only, then an attacker could crack passwords for all users with a single brute force Job. (not as quick as a rainbow table but still much easier than a separate brute force Job for each one)

---

_{* As @Navin commented, this would be a potential DoS attack vector. One solution is to limit the number of hourly attempts per IP, and per username. It is also possible that you should reduce the 'slowness' of your hash to only take 10ms. This is not nearly as good as 100ms from a 'stolen hash' perspective, but still way better than 'microseconds'.}

Answer 4

I felt like you didn't quite understand how the rainbow table worked or how it was used but I couldn't quite place what about it felt off so I went to dig a bit more and reread the wikipedia article and I think I've clarified things for my self and can answer your question.

The short answer is that the rainbow table works because it happens to make a match for your password someplace in the chain and the salt makes the password much longer which means that to still get matches your rainbow table grows to the point of being impractical/impossible or your odds of generating a match for the password goes way down.

A basic hash chain uses a reduction function to turn a hash back into a possible password and then hashes that and repeats the process. The hash table then stores the starting password that generated the first hash and the last "possible" password generated by the reduction function. To crack a password you run it through the reduction function and check the table to see if you have that as one of your results recorded. If you don't then you hash it and reduce it again and check again. Repeat that process until you've found a match or gone the full length of your chains. If you find a match you basically follow the chain backwards until you find your original result of the reduction function and the look at the previous "possible" password that was was hashed and then reduced to give you your match and you have your password. If you didn't find a match then your rainbow table didn't cover their password.

That process has collision problems but can't detect them if they aren't at the same step in the chain so the rainbow table uses a unique reduction function for each reduction step done in the chain so it is only a collision if it happens on the same step and they can detect that because both chains will have the same final result and build a new chain that isn't a collision. The passwords that the rainbow table can crack is determined by the possible passwords generated in the chain so the total number of passwords covered is the number of steps in the chain times the number of chains stored. Making your reduction functions generate much longer possible passwords so that it covers password + salt or the hashed result of the password + salt makes the rainbow table less effective. You end up covering a lot less of the possible passwords or your chains get longer taking longer to compute to make your table and check the password and your table gets bigger and harder to store/search.

https://en.wikipedia.org/wiki/Rainbow_table

Answer 5

Remember that a rainbow table is essentially a pre-computed table that can be applied to any unsalted set of passwords. That means not just simply YOUR password table, but everyone else's as well. Creating the rainbow table is hard and computing intensive. But once it's created, it can be re-used against and again, and distributed to others like any other tool.

Imagine the scenario where you didn't salt the passwords. Someone can (and has) created sets pre-computed tables that can essentially instantly crack passwords from 1-7 or 1-9 or even 1-10 characters if you used several common hashes.

Applying a large enough salt to the passwords makes this pre-computation attack impossible since pre-computation is generally much, much harder than just computing only the salts in the password file.