91

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?

  • 53
    Considering the length of the salt, this could result in a very lengthy (impractical) login operation if you have to try all possible salt values. This will result in using a smaller salt range for usability. I think that that may lead to worse security than using a valid salt value and storing it. See also stackoverflow.com/questions/184112/… for discussion on ideal salt length, suggesting between 16 and 256 bits. – oɔɯǝɹ Jul 15 '16 at 9:40
  • 213
    Just what is this guy a professor of? Dentistry? – Shadur Jul 15 '16 at 9:55
  • 36
    Note that a good cryptographic hash is slow by design, so the range of possible salt values becomes too large very soon. – oɔɯǝɹ Jul 15 '16 at 9:58
  • 59
    This is why people should learn from Stack Exchange instead of professors. :-) – Bryan Field Jul 15 '16 at 13:47
  • 109
    AFAIK storing a salt is a bad idea if your database is in a humid place-- leads to corrosion (see example of corroded table in Second Life here). – Jedi Jul 15 '16 at 14:29
177

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.

  • 4
    wouldn't it also open up the possibility of more collisions and a lot more false positives? – CaffeineAddiction Jul 15 '16 at 14:24
  • 1
    @CaffeineAddiction Maybe. For example the following might happen : hash(wrong salt + wrong password) = hash(right salt + right password). But it's not a practical route to attack as creating collision in hash function is pretty hard. – Gudradain Jul 15 '16 at 14:36
  • 2
    @CaffeineAddiction: not likely. Assuming SHA-256 and a 32-bit salt, your odds of a collision with the existing hash (aka, 2nd preimage) have gone from 2^-256 to 2^-224. Larger, but still infinitesimal in the grand scheme of things. – David Jul 15 '16 at 15:58
  • 2
    @David how? hash functions can be modelled as random oracles where any two inputs lead to independent outputs, so I don't think the probability changes at all (unless you pad your input to a fixed length) – Thomas Jul 17 '16 at 12:40
  • 2
    @Thomas You have one hash generated from <salt><password>. Every time the user enters their password, the server checks your password combined with the 2^32 possible salts. If for instance you were using a 32 bit hash, that would mean that your real password would work, but there would also be an excellent chance that the hash would match one of the 2^32 tried by the server if you entered any password. – Jason Goemaat Jul 19 '16 at 7:11
126

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.

  • 3
    wouldn't it also open up the possibility of more collisions and a lot more false positives? – CaffeineAddiction Jul 15 '16 at 14:26
  • 39
    Peppers are still stored, though (not in plain view, but stored) – WoJ Jul 15 '16 at 14:42
  • 33
    How I've always heard "pepper" defined is a salt that's stored per-application in the code, rather than per-user in the DB. – BlueRaja - Danny Pflughoeft Jul 15 '16 at 15:44
  • 21
    Worth noting that a pepper is still stored, just not necessarily in the database. The OP seems to be talking about a case where the salt is not stored at all, and the application essentially brute forces the salt every time a login is attempted... – Ajedi32 Jul 15 '16 at 18:41
  • 9
    @amccormack I'm not sure of a definitive source, but pretty much every article or post I've read about peppers seems to share this definition. security.stackexchange.com/q/3272/29865 stackoverflow.com/q/16891729/1157054 blog.filippo.io/salt-and-pepper And besides that, not storing the pepper would be pretty useless - it'd basically just be a really hacky way of increasing the work factor of your hash function. – Ajedi32 Jul 15 '16 at 18:58
21

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'.

  • "If there were no salt, the attacker could brute force the hash for all users in a single brute force Job. (saves a lot of time this way)" Or just select from the database for every user with the MD5 hash 5f4dcc3b5aa765d61d8327deb882cf99, which corresponds to the password "password". It's also a way of protecting users from themselves. – Mikkel Jul 18 '16 at 21:22
  • Never use MD5 to store passwords! Use a Slow Hash instead. But yes, I see your point. I've updated the answer to reference Rainbow Tables which you refer to. – Bryan Field Jul 19 '16 at 12:08
  • True. In the real world, you should be using a proper password hashing library in whatever language you're working with, which normally includes the salt in the hash string as well as protecting against timing attacks, rendering this whole discussion moot. But yes, MD5 is not for passwords. – Mikkel Jul 19 '16 at 13:57
16

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.

3

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.

2

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.

1

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.

  • 1
    Wouldn't you make their job a lot more easy though if they didn't have the hash and salt? Since now the server checks 4096 values if I only transmit one, thus giving a lot more false positives. This was the reasoning my prof used but it doesn't seem very useful to me, so I'd like to see someone who actually uses this approach in real-world code. – jazzpi Jul 18 '16 at 17:28
  • If they don't have the hash, there's no point, is there? Salting protects against people that have the hashes. If using a 12 bit number becomes popular, attackers might create databases with pre-computed hashes for each of those numbers and common/uncommon passwords to make their job easier. Even if you generate 4096 random salts and re-use them instead of a simple 12 bit number would let them focus on one salt value say and possibly compromise a lot of users if you have millions. – Jason Goemaat Jul 19 '16 at 2:06
  • 1
    Yes, salting protects against people that have the hashes. Normally, it doesn't make you more vulnerable against people that don't have the hashes, but it does with this variant. – jazzpi Jul 19 '16 at 6:55
  • 1
    Because if you send one password to the server, it needs to check it with all 4096 possible salts, thus giving you a lot higher potential for false positives. – jazzpi Jul 19 '16 at 7:28
  • 1
    Sounds like you're talking about a collision in the hashing algorithm with trying random passwords. If you have a 256 bit hash, those 4096 attempts are nearly meaningless when trying to produce a collision. The reason you can brute force when you have the hash is because you can run millions or billions of checks each second on your local computer(s). If your site allows people to attempt millions of passwords without locking them out, (A) you're doing it wrong and (B) they must have a hella-fast connection to your servers and (C) you should notice your server's CPUs being pegged. – Jason Goemaat Jul 19 '16 at 16:16
0

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.

  • 1
    "This "progressive salt discarding" approach could extend the useful life of hashing functions." There are hashing functions with configurable hash size (one example being Keccak), and using those as the underlying primitive of a KDF seems like a much better idea to me. You could still use this technique to extend the useful life of unupdated password hashes (with an update, the new hash would have the most recently configured hash size), but whether that's a good idea is also questionable. You'll see the user's plain password on every logon (except with e.g. SRP), so you can update the hash. – Rhymoid Jul 16 '16 at 12:14
  • @Rhymoid You need write permission to the password database entry to update the hash at authentication time (when the password is briefly known to the system). For instance, on classic Unix, everyone could read /etc/passwd and use the hashes for authentication, but only a setuid utility like /bin/passwd could update them. (In general, we can envision a system in which updating an authentication database entry is a separate privilege from using it for authentication, even though both are special privileges only granted to certain programs.) – Kaz Jul 16 '16 at 16:54
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.