How Does A Random Salt Work? [duplicate]

Question

I don't understand how using a random salt for hashing passwords can work. Perhaps random salt refers to something other than hashing passwords? Here is my thought process:

1. The salt is used to add extra junk to the end of a password prior to hashing it, to fight against the likelihood of being cracked by a rainbow table

2. However to ensure you can still verify a password is correct, you must use the same salt for each password prior to encrypting it to see if it matches the hash saved for a certain user

3. If a random salt is used, how can that password ever be verified again? Is the random salt saved somewhere to be used for each encryption? Seems less secure to me if the salt is saved right alongside the hashed password, rather than using some kind of computed salt an attacker would not inherently know if they got a hold of your data.

I'm not sure if I'm missing something here, or if random salting has to do with a different scenario in encryption, and doesn't make sense in this particular case. How can a random salt work in the above case of hashing passwords prior to encrypting?

Answer 1

Is the random salt saved somewhere to be used for each encryption?

Yes

Seems less secure to me if the salt is saved right alongside the hashed password, rather than using some kind of computed salt an attacker would not inherently know if they got a hold of your data.

It's not, because the only thing a salt does and was invented to do is, as you said:

to fight against the likelyhood of being cracked by a rainbow table

and nothing more. It adds complexity to a single password - and for every password in a database, it is unique. To verify the password, you need to store it alongside it. This doesn't compromise the security of that single password in the least bit - the hash algorithm is still as secure as without a salt.

But, looking at the whole database, every password is better protected against rainbow attacks, because the attacker must calculate very single hash with the respective salt separately and cannot do bulk operations on them.

Answer 2

To verify the hashed password without salt, you compute MD5(privided_password) and compares with the data stored on the database. It makes a trivial search on a hash table to decode lots of your passwords. (I know MD5 is weak for password storage, I'm using it just because the hashes are shorter than SHA-512, for example.)

If you use salt, you must compute MD5(provided_password + salt) and compare with the database. As the salt is part of the hash, you store the salt on the database and the password on the user.

If 3 of your users have passw0rd as its password, and you use MD5 without salt to hash your passwords, and someone steals your database, it can see something like this:

|username    | password                         |
|user1       | 71d00b760d017b2999eb54e32f41f592 |
|user7       | 71d00b760d017b2999eb54e32f41f592 |
|user13      | 71d00b760d017b2999eb54e32f41f592 |

So, as soon as the hacker locates one password in a hash table (there's plenty of them online), he knows all the others.

The first step is to use a salt. Every password will have extra data before hashing, but the same salt is used:

|username    | salt | password                         |
|user1       | SALT | a66a96b36d78e452202c12d36b6d198c |
|user7       | SALT | a66a96b36d78e452202c12d36b6d198c |
|user13      | SALT | a66a96b36d78e452202c12d36b6d198c |

Using this scheme, the hacker will have to bruteforce the hashes to get the passwords. It will take some time, but as soon as one password is cracked, all the others will be revealed too.

The next step is the random salt. Every password will have a different random salt:

|username    | salt | password                         |
|user1       | SALT | a66a96b36d78e452202c12d36b6d198c |
|user7       | ASDF | 8062279f0ba04fa6ee41d0a9e04f4c93 |
|user13      | ABCD | 5743092bfb79214247c50c4102af0b99 |

In this case, even if all your users have the same password, the hacker cannot know without bruteforce every password. In this example the salt is very short, just 4 bytes, but you can use larger salts (128 bytes or more) and increase the difficulty to bruteforce the passwords.