How come hash salt doesn't make a hash ineffective?

Question

I am not a cryptography expert. I watched this video regarding hashing and salting as part of the course User Authentication With Express and Mongo in teamtreehouse.com.

• I understand from the video that a hash is a representation of a password stored in the DB, used to prevent say company workers from copying password (the hash will be suited to a password given in authentication) and first created by passing the password in a hash function (simple hash function in this case).

• I also understand that salting a hash is randomizing the hash.

What I didn't understand from the video is how would an hash keep being evaluated properly if we change it (salting it), each authentication anew. In other words, how could it still match the password.

Edit: Maybe I should have ask: What is the mechanism that creates the salt, juxtaposing it to the hash, and make sure the password will comply to the hash+salt combination.

Answer 1

Direct Answers

What is the mechanism that creates the salt, juxtaposing it to the hash, and make[s] sure the password will comply to the hash+salt combination?

• What creates the salt? - A random number generator, used when a user's password is being generated or changed.

• What juxtaposes that salt beside the hash? - How exactly to store the results of that random number generation is an implementation decision; it makes no difference to the algorithm. All that's important is that the salt is concatenated to both the value that's stored, and (again, separately) to the value that's hashed.

• What makes sure the password will comply with the hash+salt combination? - There are two stages to consider here: Password generation, and password checking.

  During password generation, a new, random salt is created. The hash to be stored is then generated from this salt and the user's password, and both the newly-generated salt (as plaintext) and the hash (generated from both pieces) are stored in the password database.

  When checking a password, both these fields are retrieved from the password database. The retrieved salt is combined with the newly-entered password, and the result of that combination is hashed. If the combined hash matches the hash which was previously stored, the operation is a success. Thus, the user needs to remember only their password; the plaintext salt was retrieved from the password database. Because the hash was generated from the combination of these two things in the first place, combining them again generates that same value again.

  The fact that the same salt value is used when a password is generated and when that password is later checked ensures that the password+salt combination will have the same hash when generated, and when later checked.

---

Longer-Form Explanation

Initial State: No Salt

Let's say you have a password:

123

...and a cryptographic hash function which hashes that password to a string:

GBIQ

such that checkPassword 123 GBIQ (as implemented below) emits GOOD.

It's critical to understand (for the rest of this to make sense) that cryptographic hash functions are designed to be impossible reverse with any means short of a brute-force search (that is, just trying all possible inputs and comparing their outputs against whatever you're trying to find).

What's Wrong With This

...now, someone who hasn't stolen your password database can work out ahead-of-time that GBIQ is the hash of password 123, so they can just make a big database with millions of common passwords with their hashes and compare that to any password database they steal. (Also, they can look at which users have the same hash, and immediately know that those users have the same password).

Consequently, if and when they do steal your password database, they can just check the hashes it contains against their big list of hashes whose plaintext passwords they've already figured out -- any matches they find is an account they can break into!

Adding Salt

Let's say you want to stop those attacks -- so, what you do is you generate a random value to use as a "salt" whenever a user changes their password. So, when the user is setting their password to 123, let's say that you randomly generate the salt 111. Then, you take the hash of 111|123, and get a result of P2C/. You would then store the salt and the hash (of the salt and the password together) as something like:

111|P2C/

(P2C/ is different from 5a3H because the salt is part of the hash value, even though the password didn't change). When the user enters their password of 123, you retrieve that 111| prefix from storage, prepend it to the front, and hash 111|123. If the result is P2C/, then you know that the password entered by the user was correct.

Thus, when you generate a new hash for the password 123 without specifying a salt, each one is different:

$ hashPassword 123
3sm|BVve
$ hashPassword 123
gwu|00Eq
$ hashPassword 123
84c|akWi

...but any one of these passes the check:

$ checkPassword 123 '3sm|BVve'
GOOD
$ checkPassword 123 'gwu|00Eq'
GOOD
$ checkPassword 123 '84c|akWi'
GOOD

...and changing any part (the salt or the actual password) will break it:

$ checkPassword 123 'ABC|BVve'
BAD
$ checkPassword 123 '3sm|NOOP'
BAD

Why does this work? The salt isn't just a database prefix, but is also a prefix to the input to the hash function itself. Consequently, every hash is different depending on the salt.

Advantages/Effects

Rainbow Table Attacks Defeated

Now, someone can't just figure out ahead of time that GBIQ is the hash to 123 -- instead, if they want to work out possible hashes ahead-of-time, they need to calculate and store that hash with every possible salt. Even with small amounts of salt, this gets hard very quickly (because salt is much more random than human-generated passwords): 8 bits of salt multiplies the effort (and storage required) by 256; 16 bits by 65,536; 32 bits by 4,294,967,296.

So instead, someone who steals the password database and sees an entry of ABC|BVve needs to figure out what strings can be appended to ABC| and fed into the hash function to get BVve as output. Because 123 is a really simple password (and four bytes is not remotely a long enough hash), they'll probably find something quickly -- but they had to attack just that one password, rather than just doing a big database merge between the database they stole and the one they precalculated; and with strong passwords and suitably long hashes, such attacks can take a long time.

Even Identical Passwords Have Different Hashes

Moreover, if you have a second user set their password to 123, they'll (if your salts are long enough and random enough) almost certainly have a different salt. So let's say this second user gets the salt 222. Since 222|123 has a completely different hash from 111|123 (whereas 111|123 hashes to 5a3H, perhaps 222|123 hashes to CJq3, and so this entry is stored in the database as 222|CJq3), there's no way for someone looking at the password database to know that these two users' passwords are identical (and thus that if they want to find out the CEO's password all they need to do is bribe the janitor, or whomever else is using the same one).

---

Sample Implementations

Unsalted

The above actually performs the 123 -> GBIQ transform used in earlier examples:

hashPassword() {
  local password=$1
  openssl dgst -sha256 -binary <<<"$password" \
    | openssl enc -base64 \
    | head -c 4 \
    && printf '\n'
}

Consequently, checking a password against a database entry is just a direct comparison:

checkPassword() {
  local userPassword=$1 databaseEntry=$2
  if [[ $(hashPassword "$userPassword") = "$databaseEntry" ]]; then
    echo "GOOD"
  else
    echo "BAD"
  fi
}

Salted

With salt, the process of hashing a password changes: It now accepts a salt to use in the check, and -- to generate the same hash used in a prior run -- must be given the same salt again.

It also has the ability to generate a new random salt (though we could potentially put this responsibility on the caller instead):

hashPassword() {
  local password=$1 salt=$2
  if ! [[ $salt ]]; then
    # generate new random bytes for salt
    salt=$(openssl rand -base64 4 | head -c 3)
  fi
  # put salt at the front of our output
  printf '%s|' "$salt"
  # then also generate the hash WITH THE SALT AS PART OF THE HASHED VALUE
  openssl dgst -sha256 -binary <<<"${salt}|${password}" \
    | openssl enc -base64 \
    | head -c 4 \
    && printf '\n'
}

checkPassword() {
  local userPassword=$1 databaseEntry=$2 salt hash
  # split the database entry into the salt and the hash
  IFS='|' read -r salt hash <<<"$databaseEntry"
  # use that salt with the user's plaintext password to generate a hash
  if [[ $(hashPassword "$userPassword" "$salt") = "$databaseEntry" ]]; then
    echo GOOD
  else
    echo BAD
  fi
}

Answer 2

The salt is stored in plaintext next to the hash and the same salt is used when checking a password.

Its purpose is to slow down attackers who obtained a copy of the database:

• They must attack each password on its own (they need to try each input for each hash instead of trying each input and comparing the output to all hashes at once).
• They can't make use of huge precomputed lookup tables ("rainbow tables") since salting is essentially equivalent to giving each user their own hash function.

There is no need to keep the salt secret or store it more safely than the corresponding hash.

_{(This is as opposed to pepper, which is mixed into the hash in the same way but is fixed per application and not stored in the database. This tries to defend against attackers who obtained database access, but not the application's program code or configuration files.)}

Answer 3

It is important to keep a few things in mind about these topics: salt, pepper, MAC, PBE hashes (ie: intentionally slow hashes).

• Hashes are NOT more random than their input. They simply obscure obvious patterns; such that equality checks are the only operation available on them.
• You MUST know how much entropy is in the hash input, where it comes from, and entropy relative to authorized versus unauthorized users. Think of a bit of entropy is a doubling of the search space to verify the hash.

If you include a salt, all that you are doing is invalidating any pre-computed dictionaries. You are effectively picking a random hash function derived from the standard one. ie: Think of sha256_salt[412](x) vs sha256_salt[53215](x) as different functions. When you use a salted hash, it is critical that x is actually "random" in some sense. It needs enough entropy (relative to somebody that is not supposed to be able to verify the password) to be considered the right "type" of input to the function.

But keep in mind: salt is useless if the hashed value has so little entropy that a pre-computed dictionary isn't even necessary. For example: "What 3-letter Agency do you work for?" is an answer with no more than a few bits of entropy.

Just try:

threeLetterAgencies = ["CIA", "FBI", "NSA", "NRO", ...]
for r in database.Records:
  for a in threeLetterAgencies:
    if r.hashed == hashfn(r.salt, a):
      print("You work for %s" % a)

In this situation, a salt is basically useless. The problem is that a salted hash of a password REQUIRES a highly random input. This is why you are told to not use your dog name, kid name, or dictionary word as a password. In this case, we are talking about an especially small dictionary.

If a user chooses a truly random dictionary word, then there are only a few hundred thousand choices. But users choose random dictionary words from a much less random set, and try to make up for it with a small number of tweaks like turning E into 3, etc. A bad password is only a dozen bits of entropy or so. This is WHY it is common to use intentionally "slow" hashes to deal with passwords, to make up for them not having quite as much entropy as we would like.

On the other hand, a simple MAC, is basically a hash(encryptedInput + secretKey) such that even if you guess that the input must be encryptedInput, you cannot verify it unless you also guess secretKey. This is effectively a one-way encryption such that you can verify your guess (ie: for use in encrypted database indices). If you used a 32bit random key, then there are at least 32-bits of randomness with respect to an attacker that does not have the key.

And the point of a Pepper is to artificially slow down a hash, by just literally adding entropy bits hash(password+pepper). This slows down the check for everyone, legitimate or illegitimate; by the number of entropy bits in pepper. If the pepper is not large enough (say it's only 4 bits); it will only cause brute-force against individual password tries take 16x longer. It will also cause a legitimate password check to take 16x longer than just doing one hash to verify.

Answer 4

Note: This is an extremely over-simplified explanation, but it communicates the concepts across effectively and so one is able to extrapolate to actual, real-world, implementations.

I'll have a crack at this. I understand your confusion from when I was studying this concept, and so I might be well placed to address it.

Hash Functions

First, what is a hash function? It's really just something that turns an input into an output. It also doesn't let you change the output back into the input, so the only real way to find the input corresponding to a certain output is to try a bunch of inputs and see which one matches.

The notable point, in this case, though is that for some input, it will always produce the same output. So if you "hash" the word "dog", you will always get the same output, say "qwerty".

Weaknesses without Salting

Say someone hashes all the words in the English language and stores the output for each of them. This means that if they see "qwerty", they don't have to go through the effort of hashing everything and checking to see if the output is "qwerty". They can just look it up in their database and see that the word "dog" hashes to "qwerty", and so they've cracked it easily.

Or what if multiple people in a leaked database have used the password "dog"? In the outputs, "qwerty" will appear multiple times, and so an attacker just has to break it once and he will have broken them all.

Solution: Salting!

The solution, of course, is a salt. A salt is really just a value, any value. The only real requirement is that the value is unique for every user, and so the easiest way to accommodate that requirement is to randomly generate the salts for each user.

So this time, say there are two users, Alice and Bob, with the password "dog", but they each have a unique salt. For simplicity, let's say their salts are their names.

For Alice, we hash "alice+dog" instead of just "dog", and for Bob, we hash "bob+dog". This time, Alice's output is "ytrewq" and Bob's is "poiuy". We store both this output and the salt that we used, in our database.

Now, if the attacker comes along and has an attempt at cracking Alice's password, he has to attempt to hash "alice+apple" and then "alice+banana", et al, each time comparing the output to the one stored. If he finally cracks it, he must do the same amount of work for Bob, since the input will be different ("bob+apple" et al).

And he cannot just look up everything in his database because he will have to create a separate one for each user, which defeats the point of it.

So that's the point of using a salt, put simply. In practical terms, the salts are usually randomly generated and around 128 bits, however, to mitigate against accidental re-usage, and to ensure that no attacker already has a lookup table of that particular salt.

Answer 5

It appears you misunderstood the function and purpose of the salt. There are two parts to the answer:

Hashing Passwords

Passwords are stored in databases as one-way-hashes. As the name implies, a one-way-hash, contrary to encryption, cannot be reversed. However, the same input will always lead to the same hash. So to find out if a user typed the correct password, hash whatever he typed and compare it with the stored hash value.

The hash functions used for this specific purpose also have a secondary feature: They are intentionally slow (i.e. computation expensive).

The purpose for both of these is to slow down attackers who compromised the database and thus have the password hashes in their hands. The hashes themselves don't tell you the password and there is no way to get the password from the hash. Brute-forcing the password database by hashing every possible password until you get a match is a slow process.

Salting Password Hashes

This process has two weaknesses:

1. Two users who use the same password will have the same password hash.
2. With computers becoming more powerful and GPU processing available, brute-forcing at least common passwords and their variations (dictionary attacks) is quite feasable. Most importantly, you can prepare the, say, most common one million passwords beforehand, by hashing them all and making a database of their hashes, then use a reverse-lookup to figure out the password. This is called a rainbow table.

Salting simply adds a random string to the password before it is hashed. Since you need to know this string in order to repeat the hashing and compare the user input to the stored hash, the salt is also stored in the database in plain text.

The salt defeats both of the mentioned weaknesses. Two users can have the same password, but as their salts are different, the hashes are different as well. Cryptographic hashsums have the effect that even a one-byte change in the input will result in a completely different hash. Rainbow tables also become impractical, as you would have to store not just the hash of every password, but of every password hashed with every possible salt. If the salt is just 2 bytes, the 1 mio. words database now exploded to about 65 billion. And it is easy and cheap to use larger salts, making rainbow tables entirely impractical (with an 8-byte salt, even pre-computing the most common 1,000 password would require storing on the order of 10^22 pairs).

Remaining Weaknesses

One weakness remains. Even if I cannot pre-compute a rainbow table, I can brute-force the most common passwords in a password database. The time required is on the order of hours to try the most common 100 or so passwords by simply hashing them all for all user salts and comparing to the stored hash. That is the reason why users should be strongly discouraged from using "password" or "12345678" or such as their password. Even with the strongest protections, extremely weak passwords can still be brute-forced. In the real world, trying the top 100 or so passwords is almost guaranteed to yield me a couple successful hits.