Salts, how does the script know what the salt is?

I am new to PHP programming and trying to grasp the idea of hashing and encryption for protecting passwords, credit card details and such. I've done a lot of reading about MD5 which I think I understand the basics of now. I've seen places recommending that I use SHA2, which I don't understand how to implement.

Back to my question. I can understand how a script can tell if a password is correct or not by hashing the password and comparing the value against the hashed one in the database. My problem occurs when trying to understand salts. If I have a dynamic salt such as the date (yes, I have heard its a bad one to use), how does the script know that a password is correct because the salt will be different for the entered password and the one stored in the database.

For example: Say the original password was created on the 21/02/2011:

• unhashed with salt:

mypassword210211

• hashed with salt:

cbc0a790b2f28fc72ca43eb749028b9f


Then if I check my password today:

• unhashed with salt:

mypassword30012012

• hashed with salt:

e4af7ca7e263750a15be642d903c9ac9


They're completely different, so how does the script know that they are the same? Do I have to store the salt used on the specified password in the database so it knows what to use next time?

I'm rather confused and its highly likely that I am not understanding the whole hashing process properly. I've done my research, but whether I have done correctly or not I don't know.

-
You normally wouldn't implement MD5 or SHA-2 yourself, but use a function given by your library. (And SHA-2 is actually a family of functions with different output sizes, the important ones being SHA-256 and SHA-512.) –  Paŭlo Ebermann Jan 30 '12 at 8:37
Remember that using password+salt and using some FAST hash (such as MD5 or any has in SHA family) is not the right way to store passwords. Use bcrypt or preferably scrypt instead. –  Mikko Rantalainen Apr 19 '13 at 10:27

Do I have to store the salt used on the specified password in the database so it knows what to use next time?

Yes that is exactly correct.

Salts are not secret values but they do need to be randomly selected (without bias) distinct. This is why using dates may require some care: they have low entropy.

Dynamic salt doesn't mean the salt is changing each time a user logs in. It just means you are using a different salt for each user.

-
Thanks, awesome answer. I'll just see if anyone has something to say. –  Sam Jan 30 '12 at 4:11
Actually, they don't need to be without any bias, just the remaining entropy should be high enough. A (non-biased) random selection is just the easiest way to achieve this. –  Paŭlo Ebermann Jan 30 '12 at 8:32
Actually, for most password-related salt usages, what we need is just that salt values are distinct from each other. Unbiased selection in a big enough space is sufficient to achieve uniqueness. Dates are not bad as themselves -- as long as you never choose two salts during the same second, and you take care never to repeat dates, even when the system administrator resets the clock. –  Thomas Pornin Jan 30 '12 at 12:33
Thanks @Paulo and @Thomas; good points. I fixed my answer. –  PulpSpy Jan 30 '12 at 15:18
@ThomasPornin: It is very true that for most password-related salt uses distinct values are sufficient. However, small amount of entropy risks rainbow tables attacks, and is non-standard. Both RFC 2898 and NIST SP 800-132 have some recommendation of having random part in salt (64 bit or 128 bit) [for instance due to rainbow tables]. Maybe in this light, I would recommend editing the response back to match, for instance, Paulo's comment, or original. –  user4982 Dec 28 '13 at 19:31

The salt has two main purposes as I understand it.

(1) To ensure that two users who choose the same password, get different password hashes.

Say the CEO, and the janitor, choose the same password. Without a salt, they'd both get the same hash. This means that an attacker who managed to download the password file, could instantly see that the CEO, and the janitor, have the same password (whatever that is). So instead of putting a keylogger on the CEOs laptop, he'd just beat the password out of the janitor! Or if the janitor was the attacker, he'd instantly see that his own password, was also the CEO's - so he could log in as the CEO, without having to try multiple passwords and risk a system alert.

With a salt, the two hashes are completely different, and no attacker can possibly know that several users have the same password. Salting the passwords also ensures that users who choose the same password on different systems, get different hashes on each of those systems.

For (1), the only actual requirement, as far as I can see, is that the salt is different for different users - because even the slightest change in salt+password, will cause an enormous change in the hash thereof. So you could just use an increasing number 1, 2, 3 etc. It needn't be large, random, or secret - just different for different users.

However, in practice, when you're storing the password for a new user, you don't necessarily want to scan the other users' salts, to check you pick a different value; and you sure don't know what salts were used on other systems! So a common approach is to "take a chance", and just pick a big random number, hoping that the resultant number hasn't been picked before. The bigger the number, the less chance it has been picked before.

(2) To reduce the chance of password cracking using rainbow tables.

Say an attacker pre-computes the hashes of a million common passwords, and stores those in a table. So the table has a million (password, hash) entries. (These are commonly called rainbow tables.) Then, when he downloads a password file, he just looks-up each of the hashes, from that file, in that table. If hash value 1234567890 matches table entry ("letmein", 1234567890), he now knows that password "letmein" will produce that hash - voila! The table takes time to generate, and space to store. But once done, it will instantly crack those million passwords - if they are unsalted.

But say each password is salted with one of (say) 1000 different values - perhaps just a number from 1 to 1000. Now the attacker has to pre-compute each password 1000 times - once for each possible salt. So the table is now a thousand times larger. Clearly, if the salt is large enough, this makes the table infeasible - it takes too long to generate, and is too large to store.

For (2), the requirement is, as I understand it, that the salt has many different potential values, and is unpredictable. If the salt doesn't have many different potential values, the table is still feasible. And if the salt is predictable, the attacker just generate a rainbow table for the predictable values, and hopes for the best!

So to meet both (1) and (2), you just pick a large random number for the salt. As I understand it, 32 BYTE salts are coinsidered the go these days.

Using the DATE as a salt is a very very bad idea. That wouldn't even achieve benefit (1) - let alone benefit (2). If I saw code that used the date for a salt, I'd not trust that code for any security related functions of any description - the author has no idea what he's doing.

This is my understanding of salts (in regard to password hashing). I guess I'll soon find out if I'm right or not :-)

TC

-

Usually the salt is stored with the hash.

Let's say we have a table users with the field password. The hash is generally written concatenated with the salt (divided by a separator like :)

So the final field value will be something like

cbc0a790b2f28fc72ca43eb749028b9f:21022011

Note that the salt should always be in cleartext (or being reachable in some way) because it will be used then to match the hash.

-
Yes, and often the name of the hash algorithm is also concatenated to the salt and the hash, in Modular Crypt Format or LDAP / RFC2307 format. –  David Cary Dec 29 '13 at 4:43