[ACCEPTED]-Salt Generation and open source software-rainbowtable

Since questions about salting hashes come along on a quite regular basis and there seems to be quite some confusion about the subject, I extended this answer.

What is a salt?

A salt is a random set of bytes of a fixed length 84 that is added to the input of a hash algorithm.

Why is salting (or seeding) a hash useful?

Adding 83 a random salt to a hash ensures that the 82 same password will produce many different 81 hashes. The salt is usually stored in the 80 database, together with the result of the 79 hash function. Salting a hash is good for 78 a number of reasons:

1. Salting greatly increases the difficulty/cost of precomputated attacks (including rainbow tables)
2. Salting makes sure that the same password does not result in the same hash. This makes sure you cannot determine if two users have the same password. And, even more important, you cannot determine if the same person uses the same password across different systems.
3. Salting increases the complexity of passwords, thereby greatly decreasing the effectiveness of both Dictionary- and Birthday attacks. (This is only true if the salt is stored separate from the hash).
4. Proper salting greatly increases the storage need for precomputation attacks, up to the point where they are no longer practical. (8 character case-sensitive alpha-numeric passwords with 16 bit salt, hashed to a 128 bit value, would take up just under 200 exabytes without rainbow reduction).

There is no need for the salt to be secret.

A salt is not a secret 77 key, instead a salt 'works' by making the 76 hash function specific to each instance. With 75 salted hash, there is not one hash function, but 74 one for every possible salt value. This 73 prevent the attacker from attacking N hashed 72 passwords for less than N times the cost 71 of attacking one password. This is the point 70 of the salt.
A "secret salt" is 69 not a salt, it is called a "key", and 68 it means that you are no longer computing 67 a hash, but a Message Authentication Code (MAC). Computing MAC is tricky 66 business (much trickier than simply slapping 65 together a key and a value into a hash function) and 64 it is a very different subject altogether.

The 63 salt must be random for every instance in which it is 62 used. This ensures that an attacker has 61 to attack every salted hash separately.
If 60 you rely on your salt (or salting algorithm) being 59 secret, you enter the realms of Security Through Obscurity (won't 58 work). Most probably, you do not get additional 57 security from the salt secrecy; you just 56 get the warm fuzzy feeling of security. So 55 instead of making your system more secure, it 54 just distracts you from reality.

So, why does the salt have to be random?

Technically, the 53 salt should be unique. The point of the salt is 52 to be distinct for each hashed password. This 51 is meant worldwide. Since there is no central organization 50 which distributes unique salts on demand, we 49 have to rely on the next best thing, which 48 is random selection with an unpredictable 47 random generator, preferably within a salt 46 space large enough to make collisions improbable 45 (two instances using the same salt value).

It 44 is tempting to try to derive a salt from 43 some data which is "presumably unique", such 42 as the user ID, but such schemes often fail 41 due to some nasty details:

1. If you use for example the user ID, some 40 bad guys, attacking distinct systems, may 39 just pool their resources and create precomputed 38 tables for user IDs 1 to 50. A user ID is 37 unique system-wide but not worldwide.

2. The same applies to the 36 username: there is one "root" per Unix 35 system, but there are many roots in the 34 world. A rainbow table for "root" would 33 be worth the effort, since it could be applied 32 to millions of systems. Worse yet, there 31 are also many "bob" out there, and 30 many do not have sysadmin training: their 29 passwords could be quite weak.

3. Uniqueness 28 is also temporal. Sometimes, users change 27 their password. For each new password, a new salt must be selected. Otherwise, an 26 attacker obtained the hash of the old password 25 and the hash of the new could try to attack 24 both simultaneously.

Using a random salt 23 obtained from a cryptographically secure, unpredictable 22 PRNG may be some kind of overkill, but at 21 least it provably protects you against all those 20 hazards. It's not about preventing the attacker 19 from knowing what an individual salt is, it's about 18 not giving them the big, fat target that 17 will be used on a substantial number of 16 potential targets. Random selection makes 15 the targets as thin as is practical.

In conclusion:

Use 14 a random, evenly distributed, high entropy 13 salt. Use a new salt whenever you create 12 a new password or change a password. Store 11 the salt along with the hashed password. Favor 10 big salts (at least 10 bytes, preferably 9 16 or more).

A salt does not turn a bad password 8 into a good password. It just makes sure 7 that the attacker will at least pay the 6 dictionary attack price for each bad password 5 he breaks.

Usefull sources:
stackoverflow.com: Non-random salt for password hashes
Bruce Schneier: Practical Cryptography (book)
Matasano Security: Enough with the Rainbow Tables
usenix.org: Unix crypt used salt since 1976
owasp.org: Why add salt
openwall.com: Salts

Disclaimer:
I'm not a 4 security expert. (Although this answer was 3 reviewed by Thomas Pornin)
If any of the security professionals 2 out there find something wrong, please do 1 comment or edit this wiki answer.

Really salts just need to be unique for 8 each entry. Even if the attacker can calculate 7 what the salt is, it makes the rainbow table 6 extremely difficult to create. This is 5 because the salt is added to the password 4 before it is hashed, so it effectively adds 3 to the total number of entries the rainbow 2 table must contain to have a list of all 1 possible values for a password field.

Since Unix became popular, the right way 40 to store a password has been to append a 39 random value (the salt) and hash it. Save 38 the salt away where you can get to it later, but 37 where you hope the bad guys won't get it.

This 36 has some good effects. First, the bad guys 35 can't just make a list of expected passwords 34 like "Password1", hash them into a rainbow 33 table, and go through your password file 32 looking for matches. If you've got a good 31 two-byte salt, they have to generate 65,536 30 values for each expected password, and that 29 makes the rainbow table a lot less practical. Second, if 28 you can keep the salt from the bad guys 27 who are looking at your password file, you've 26 made it much harder to calculate possible 25 values. Third, you've made it impossible 24 for the bad guys to determine if a given 23 person uses the same password on different 22 sites.

In order to do this, you generate 21 a random salt. This should generate every 20 number in the desired range with uniform 19 probability. This isn't difficult; a simple 18 linear congruential random number generator 17 will do nicely.

If you've got complicated 16 calculations to make the salt, you're doing 15 it wrong. If you calculate it based on 14 the password, you're doing it WAY wrong. In 13 that case, all you're doing is complicating 12 the hash, and not functionally adding any 11 salt.

Nobody good at security would rely 10 on concealing an algorithm. Modern cryptography 9 is based on algorithms that have been extensively 8 tested, and in order to be extensively tested 7 they have to be well known. Generally, it's 6 been found to be safer to use standard algorithms 5 rather than rolling one's own and hoping 4 it's good. It doesn't matter if the code 3 is open source or not, it's still often 2 possible for the bad guys to analyze what 1 a program does.

You can just generate a random salt for 19 each record at runtime. For example, say 18 you're storing hashed user passwords in 17 a database. You can generate an 8-character 16 random string of lower- and uppercase alphanumeric 15 characters at runtime, prepend that to the 14 password, hash that string, and store it in 13 the database. Since there are 62⁸ possible 12 salts, generating rainbow tables (for every 11 possible salt) will be prohibitively expensive; and 10 since you're using a unique salt for each 9 password record, even if an attacker has 8 generated a couple matching rainbow tables, he 7 still won't be able to crack every password.

You 6 can change the parameters of your salt generation 5 based on your security needs; for example, you 4 could use a longer salt, or you could generate 3 a random string that also contains punctuation 2 marks, to increase the number of possible 1 salts.

Use a random function generator to generate 9 the salt, and store it in the database, make 8 salt one per row, and store it in the database.

I 7 like how salt is generated in django-registration. Reference: http://bitbucket.org/ubernostrum/django-registration/src/tip/registration/models.py#cl-85

salt = sha_constructor(str(random.random())).hexdigest()[:5]
activation_key = sha_constructor(salt+user.username).hexdigest()
return self.create(user=user,
           activation_key=activation_key)

He 6 uses a combination of sha generated by a 5 random number and the username to generate 4 a hash.

Sha itself is well known for being 3 strong and unbreakable. Add multiple dimensions 2 to generate the salt itself, with random 1 number, sha and the user specific component, you have unbreakable security!

In the case of a desktop application that 14 encrypts data and send it on a remote server, how 13 do you consider using a different salt each 12 time?

Using PKCS#5 with the user's password, it 11 needs a salt to generate an encryption key, to 10 encrypt the data. I know that keep the salt 9 hardcoded (obfuscated) in the desktop application 8 is not a good idea.

If the remote server 7 must NEVER know the user's password, is 6 it possible to user different salt each 5 time? If the user use the desktop application 4 on another computer, how will it be able 3 to decrypt the data on the remote server 2 if he does not have the key (it is not hardcoded 1 in the software) ?