Does anybody not store salts?

Question

We talked about password hashing and salting in class today. Our professor had a very different understanding of the use case of salts from mine and said that you might not store the salt at all and just check every login attempt with all possible salts and authorize if one matches.

I don't really see any point whatsoever in this since now my service is much more vulnerable to brute force attacks (send one password, server checks many), but I guess it is a little more secure to pure dictionary attacks against the hashed password.

So is there any use case where people would actually do this?

Answer 1

Not storing the salt is bad advice.

The main purpose of a salt is that each user password has to be attacked individually.

If you do not store the salt then, as you said, you need to try every single salt combination in order to validate the password. If you need to check every single salt combination, this means that the salt cannot be too long (you mentioned 12 bits in a comment). If the salt is not long, it means that the salt will be repeated for many users. If it's repeated for many users, it means the attacker will be able to attack many users at the same time, which will save the attacker time.

By doing that, you nearly completely defeat the purpose of using a salt.

Answer 2

A 'secret' salt is known as a pepper.

From Wikipedia:

A pepper can be added to a password in addition to a salt value. A pepper performs a similar role to a salt, however whereas a salt is commonly stored alongside the value being hashed, for something to be defined as a pepper, it should meet one of the following criteria that define it a more carefully hidden 'secret' than the salt value:

• The pepper is held separately from the value to be hashed
• The pepper is randomly generated for each value to be hashed (within a limited set of values), and is never stored. When data is tested against a hashed value for a match, this is done by iterating through the set of values valid for the pepper, and each one in turn is added to the data to be tested (usually by suffixing it to the data), before the cryptographic hash function is run on the combined value.

The advantage of a pepper is that an attacker must now guess up to the number of possible permutations of a pepper value for each plaintext entry.

Peppers increase the length of attack for a specific hash, whereas a salt does not.

Remember that a salt is an effective mitigation for precomputed hashes and it makes an attacker spend a long time attacking a set of hashes. However, if only one hash is of concern, and no precomputed hashes are to be used, a salt does not increase the length of attack. A Pepper however, forces the attacker to use multiple guesses for each plaintext password, even for a single hash.

In this way, a pepper is similar to key stretching.

Most implementations prefer key stretching to peppers.

My personal observation is that most implementations prefer key stretching to peppers. I don't have a reference for this so readers may provide supporting or dissenting references in the comments. People tend to prefer key stretching because it has a known and expected performance cost and security benefit. In order to compute the Nth round of a hash, N hashes must be computed. With a pepper however, only the expected number of attempts can be calculated. Consider a 1 byte pepper, the attacker would need 256 guesses to guess all possible combinations, but the expected value is 128, and the attacker could (on average of 1/256 times) guess the value on the first try.

Peppers and Key Stretching can work against each other.

Key stretching is effective because you can set the number of rounds based on the length of time you want the computation of a hash to take. Say you want a single check to take half a second on current hardware, you just increase the rounds until that occurs.

With a pepper, because you need to guess multiple values for each password, the size of a pepper must be inversely related to the number of rounds in order to keep the computation time constant.

Practical advice on hash implementations

The best advice for password/hash implementations is to use well known methodologies and tested libraries. You should be using bcrypt or pbkdf2 with a unique salt and many rounds. These algorithms tend to have well known implementations in many languages and frameworks. If you happen to find a well known and tested library that includes a pepper, in addition to salts and key stretching, it may be worth your while to use it, but the additional benefit often outweighs the performance costs.

Answer 3

Background: 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), but not secret. 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)

---

Answer: If you were to 'not store' the salt ('brute force the hash at runtime' as your professor suggests)

• the possible salts would have to be very few
• the hash would have to be quite a bit faster

This would totally defeat the purpose of Salt, severely cripples the benefit of a Slow hash. That is a major design mistake on the part of your professor. Basically, he is rolling his own password storage scheme, where he should be using the well vetted bcrypt algorithm (or scrypt or PBKDF2) as it was intended to be used.

---

_{* 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

Your professor isn't correct. The point of a salt is to increase the entropy of the hashed passwords to prevent any sort of pre-computation attack on them as well as preventing the same password from different users from having the same hashed value.

Being able to try all possible salt values means that you must have a very LOW amount of entropy in the salt, which means a pre-computation via rainbow tables is possible.

Answer 5

You could use the salt in this way. It would be a sort of hash-stretching process. Typically you stretch a hash by repeating the algorithm several thousand times, which slows attackers and users by 1000fold, but users typically don't mind the slowdown. Using a salt in this way would have the effect of doing a hash stretching algorithm by having to repeat it for many unknown hashes.

However, this is an extremely unusual approach. The traditional ways of doing salting do what salts are supposed to do far better (make it so that nobody can precompute a password table). The traditional ways of doing hash stretching do what hash stretching is supposed to do far better (make it so it takes longer for attackers to compute passwords). Using a salt in this way is kind of mushing the two of them together. The result kind-of sort-of works, but the cleaner approaches do both solutions far better than the ugly mismash of techniques.

Answer 6

Rather than thinking of salt in terms of brute-forcing, I like to think of it in terms of saying that it makes it impossible to tell anything about a password, including its relationship with other passwords, by looking at it. If the system uses no salting, looking at two users' hashed passwords would indicate whether their real passwords matched. If a system salted using username only but nothing random, time-specific, or system-specific, then looking at a user's hashed passwords on two machines that use the same approach would indicate whether the user's passwords on the two machines matched. If the system salted using system ID and user name, but nothing random or time-specific, then someone with accesses to two different password hashes by the same user could tell whether the associated passwords match.

The effect of random salting is to make it so that no two hashes using the same password are likely to match, even if they involve the same user on the same system. While one could achieve a similar effect without storing the salts if log-in attempts were to brute-forcing them, such an approach would limit the practical length of salt one could use and thus increase the likelihood that passwords used in two contexts would have the same salt and thus be recognizable as matching.

Answer 7

What does salting give you? Attackers have pre-calculated databases of hash values for passwords, common and not. If they capture your database and have the hash of the passwords for every user, it's simple to check their hashes against those values without a salt.

With a random salt that is stored along with the password, this insanely quick method is no longer possible. But if the attacker has the salt as well as the hash, it is still possible to use dictionary attacks for weak passwords or brute-forcing for short ones. All the attacker has to do is use the salt and try different passwords using a dictionary or brute-force attack.

Now let's say when the password is changed, you hash it with a random 12 bit value that isn't stored along with the salt that is. Then every time you check the password, you have to try all 4096 values. On my computer this takes about 3.5ms, so 284 passwords can be checked each second. A little more cpu use on the server when someone logs in, but for someone trying dictionary or brute-force attacks, you just made their job a lot more difficult, even if they have the hash and salt.

Answer 8

There seems to be some merit in the idea of not storing some controlled number of bits of the salt, which is independently configured and is independent of the salt size.

Suppose we have 32 bit salts. We could choose to store only 22 bits, and brute-force through the remaining 10 when we authenticate. The effect of this is as if more rounds were added to the hashing function. Not so many that legitimate authentication is impacted, but enough to raise the difficulty of brute-force cracking.

Next year, machines get faster. So we sweep through the password database and knock off a bit from each salt: now we store only 21 bits, and have to brute force through 11.

It's as if we doubled the hashing strength, but without the disruption of replacing the algorithm and getting users to re-hash their passwords (which is left up to the regular password expiry policy).

This "progressive salt discarding" approach could extend the useful life of hashing functions.

However, these kinds of approaches slow down the legitimate authentication and the brute force attack by an equal factor, so at best they provide a minor security layer. Our focus should be placed into improvements which add only a constant amount of extra time to legitimate use, while multiplying the cracking difficulty. Of course, an improvement which has this property is increasing the amount of entropy in the password phrase! Each bit of entropy added to the password adds a constant cost to the legitimate users, yet doubles the brute force cracking effort. A password of length N takes O(N) to hash (and type), but O(2**N) to brute force. Adding 12 bits of entropy to a password beats concealing 12 bits of salt.

Answer 9

Out in the wild we have a users table. A users table is usually

ID   |  username | salt | encrypted_password               | horridly_insecure_reset_key
===========================================================================
1    | user1     | foo  | 09b6d39aa22fcb8698687e1af09a3af9 | NULL
2    | user2     | bar  | 6c07c60f4b02c644ea1037575eb40005 | NULL
3    | user3     | baz  | 09b6d39aa22fcb8698687e1af09a3af9 | reset

Then an authentication method will look something like

def authenticate(user, password)
    u = User.find(user: user)
    return u.encrypted_password == encrypt(password + u.salt)
end

By having a salt per user it ensures that even if the password for user1 is known you can't figure out the password for user2 or user3 without their salt.

You also ensure that you can't figure out the salt by have a set of encrypted passwords and trying a few encrypted passwords.

In essence, this way, every attack against a user has to be started from scratch.

Even if an attacker has a list of users and salts, they still need to do the cracking against each and every user to see if they have a password match. If you had a pool of salts, or one static salt, I could know that user1's password is password and then just find all the encrypted passwords that match. So this way at least slows them down just a little bit more.

Now when we look at salts, we want to reduce salt reuse. Two identical salts will make it easier to attackers. If two people share the same salt and the same password, breaking one user will break the other.

So lets say that we only use these three salts. And we have 3000 users. that means, 1000 people have the same salt. If 1% of those have a password of "password" then those people can be cracked all at the same time. 10 accounts get hacked at once. Because we know the three salts. That's a very easy stretch to get 30 people attacked at once.

Now if every salt is unique. And we know that user1's password is password, that doesn't do you any good. You still have only cracked 1 user. You still have to do "does password + salt = encrypted password" for all other 2999 users.

A really important note.

Security through obscurity is not security. That doesn't mean you should post your users table on google cause that's silly. But when measuring security, you should assume the attacker has everything. You can't say, "But they won't know the application salt cause they don't have the source code". Cause they could. Doesn't mean give away your salts, it just means it's not real security. Assume they have the user name and the salt, and then try to make it more difficult for them to get the password.

SUPER IMPORTANT NOTE

The code and table used here are about 9,000 times too simple for real use. The password are not encrypted, the salts are too short, the method is a bit to simplistic, in short doing something like this in production is not anything that should be considered secure. I chose these cause there simple for the point of demonstration, not because they are secure.

Answer 10

Well, you certainly don't have to "explicitly store" a full, globally-unique salt in the database next to each password -- you could, for example, merely just "derive" it from other fields in the database instead (which can save storage space as well).

For example -- you could just store one secret GUID anywhere outside of the database, and then, during login, simply append it to any user-specific field already there (such as userId, username, etc...) to form a globally-unique password salt for each user. (But, just don't forget to at least store some tiny little "nonce", to handle password changes, however!!)