59

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?

Kevin DiTraglia
  • 771
  • 1
  • 6
  • 8

2 Answers2

47

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.

F.P
  • 878
  • 8
  • 14
  • 10
    Oh, that makes sense. It just makes it so the hacker would have to compute an entire rainbow table *for each password*, I hadn't thought of it like that, makes perfect sense now. Thanks for the answer. – Kevin DiTraglia Sep 08 '14 at 14:48
  • No problem, I stumbled over this too in the beginning, but once you grab the concept it's very easy to see :) – F.P Sep 08 '14 at 14:49
  • So the answer is, you compute the random salt, and store it right along with the hashed password in say a users table? For some reason I feel like I've seen random salts used, but not stored, but I could be mistaken. – Kevin DiTraglia Sep 08 '14 at 14:49
  • That's basically what should happen, yes. I am not entirely sure if there are better approaches, so maybe someone with more experience can comment on this. Example of a mapping file for a User Provider in Symfony: [FOSUserBundle/User](https://github.com/FriendsOfSymfony/FOSUserBundle/blob/master/Resources/config/doctrine/model/User.orm.xml) - You can clearly see `password` and `salt` right next to each other. – F.P Sep 08 '14 at 14:51
  • Good answer but you forgot to mention the fact that salt are also used to protect against birthday attacks (as long as salt values are unique in a given DB) – Stephane Sep 08 '14 at 15:47
  • @Stephane I don't know about birthday attacks - feel free to include it in my answer if you think it fits. – F.P Sep 08 '14 at 17:42
  • I just learned that a [rainbow table](http://security.stackexchange.com/questions/379/what-are-rainbow-tables-and-how-are-they-used) is a more complex thing. You're talking about a hash table. – Christian Strempfer Sep 08 '14 at 18:48
  • I stumbled over this also: storing the salt alongside of the password? But I was thinking in terms of a brute force attack, in which case, if the attacker has the salt right there to add to their attempts, it would not add any extra security, though no less either. However with a rainbow attack, which is _much_ faster and more likely to be used, the attacker is using a table of hashes to compare to the hashes in the database (ie, reverse). These tables are made from computing hashes of likely passwords, but they would need to have included the salt as well if the resulting hash is to match. – KevinHJ Jul 29 '21 at 13:55
  • (continuing) One could say if the rainbow attacker has the salt, they could generate the rainbow table using the known salt, but then in essence, they would be doing the same thing to generate the new table as they would do using a brute force attack. The reason rainbow attacks are so much faster is all of that heavy work has already been done, and now it is just a matter of looking up the user's pw hash in the rainbow table. You could think of a rainbow table as all of the hashes that got generated while doing a brute force attack. – KevinHJ Jul 29 '21 at 14:02
26

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.

ThoriumBR
  • 51,983
  • 13
  • 131
  • 149
  • 1
    In the third example (with a unique salt), you've accidentally included the same hash twice. – Chris Murray Sep 08 '14 at 16:05
  • 9
    Please, please, please, please use a better hashing algorithm than `MD5`. Or at least add a note saying not to use md*/sha* for password hashing. – Tyzoid Sep 08 '14 at 17:38
  • Oh... finally it made more sense. Thank you, loved your examples. – Christian Feb 24 '16 at 13:07
  • @Tyzoid What should be used instead of `MD5`? – Kellen Stuart Jan 09 '18 at 21:04
  • @KolobCanyon Use something like `bCrypt`. It's a hashing function designed to be slow, making effective bruteforcing difficult. The cost is also tunable, so you can adjust the difficulty of each hash attempt. Most implementations will automatically salt for you too, making it easy to use. – Tyzoid Jan 23 '18 at 03:21
  • @ThoriumBR thanks! So using the same salt for all records basically means not to use a salt at all right? Because when the attacker bruteforces passwords he does so by appending the salt to each entry in the dictionary, therefore the time needed to find a password with or without salt is the same. Is this reasoning correct? – Aaron Ullal Jan 16 '19 at 16:09
  • @AaronUllal not quite. If, for example, the salt is _abc123_ for every password, and at least two users have _password123_ as his password, the attacker cracks the first occurrence and immediately knows every single user with _password123_ as password. A random salt for every entry means that even if every single user have the same password, the attacker have to bruteforce one by one. – ThoriumBR Jan 16 '19 at 17:05
  • @ThoriumBR yeah that part was very clear, thanks! I was referring to no salt vs same salt for every record... if you use the same salt for every record in the table you pretty much have no additional benefit, right? – Aaron Ullal Jan 16 '19 at 21:55
  • @AaronUllal you have one small benefit: instead of using any already available lookup table for passwords, the attacker must create his own. Depending on the attacker, it will extend the attack time for a couple days, or less. But if you are saving passwords, do the right thing and use long, unique, random salts. – ThoriumBR Jan 17 '19 at 11:03
  • It says "As the salt is part of the hash, you store the salt on the database and the password on the user.", then again says.. " someone steals your database, it can see something like this:" So if someone stole your database, couldn't they use the salt stored in the database to crack the password? – Don Dilanga Oct 10 '20 at 10:11
  • 1
    Yes, they can. With the salt, they need to bruteforce the passwords one by one. Without the salt, they can tell from the start all people with the same password (and there will be a lot) and bruteforce them all at once. – ThoriumBR Oct 11 '20 at 03:13