There's also the fact that if two people have the same password, with (random) salt, that fact is not obvious by looking at their encrypted passwords. This is probably the most important reasoning: more information can be protected by using salt.

But I doubt this is much of an issue these days, thanks to Moore's law and distributed computing.

This is true for crypt() because it doesn't use a long enough salt value. However, a properly-sized salt can make all dictionary attacks impractical unless there are some fundamental changes in understanding computers (Moore's "law" is more like an observation, and will stop working someday).

With a 32-bit salt, and a 160-bit hashing algorithm (like SHA1), the minimum size of the password database (not the attacker's dictionary) is 32 + 160 = 192 bits / user (ignoring the space to store the username and whatever overhead is needed by the database itself). To generate a dictionary, an attacker must create a hash value for every possible password and all salt values for each password. There are 2³² possible salt values, so it takes 160 * 2³² = 640 GB to store all possibilities for one password. That doesn't even include storage overhead, or the additional information you'll probably want in the stored datastructure to make searching untold terrabytes of data take a reasonable time. Consider, too, that some implementations put even more data into the hash (the username is common), which screws dictionary attackers even more. Compressing this data will probably be minimally effective, since compression algorithms work to remove patterns, which the hash algorithms have already removed.

----
I wanted to explore how Perl's closures can be
manipulated, and ended up creating an object
system by accident. -- Schemer

: () { :|:& };:

Note: All code is untested, unless otherwise stated

A number of people have already answered this question very well, but I'll add one or two more points, if I may, for completeness.

First of all, crypt is not an encryption algorithm, but a one-way hashing algorithm, based originally on DES (the Data Encryption Standard algorithm). When you enter a password attempt, your entry is hashed with the same salt value, and the results compared.

Secondly, according to the crypt(3) manpage,

salt is a two-character string chosen from the set [a–zA–Z0–9./]. This string is used to perturb the algorithm in one of 4096 different ways.

Let's illustrate this with an example. If you decided to try to brute-force attempt all of the lower-case 6 character passwords on the box by computing them in various places, then putting them together into a single file, and doing a search against them, you would be dealing with (26**6), or approximately 3.09e8 (309 million), possibilities. You decide to store them as the hashed key followed by a comma followed by the unhashed key followed by a carriage return. Because the crypt(3) function returns a 13 character string, these lines would be approximately 21 characters each. Figuring that, you realize this could conceivably be stored as a file of approximately 6.5GB, which is within the range of most drives these days. Enter the salt. By adding the two-character salt, which perturbs it in one of 4096 ways, your search space has just been increased from 309 million to 1.2 trillion possibilities, and your storage space from 6.5GB to approximately 26.5TB (yes, terabytes).

Admittedly, that was a very, very contrived example, but the idea is reasonably solid. Obtain password file, do a search against a sorted file, and *bam* you have it. The salt makes it very difficult to have such files prebuilt and stored around somewhere.

Hope that helped...

In addition, without the salt, if two users had the same password (not that this would ever happen :), the crypted hashes would be identical. With the salt present, cracking one common password will (hopefully) not result in cracking additional passwords without additional work.

--MidLifeXis

You've got it right. It makes the encryption key* more random. As far as I know, there is no real random number generation on computers, so you need something that goes beyond whatever the algorithm/processor combination can create. The salt is that something. GPG, like PGP, uses "entropy" during key creation---moving the mouse, hitting keys, anything that increases makes the state of the computer unique.

Update: Added "key" above, which is what I meant. Thanks to Abigail-II for pointing out my wording mistake. saintmike's post is very much to the point.

It doesn't make the encryption more random. That doesn't make any sense. You don't want any randomness in your encryption - if there were any randomness, how would you ever be able to determine your password was correct?

The salt serves two points, both already explained higher up in the thread: it increases the size of a pre-computed dictionary with a factor of 4096, and it reduces the chance that two users using the same password have identical encrypted passwords. Points that were important a couple of decades ago, but less so nowadays. Pre-computed dictionaries are now much more feasible (although the factor 4096 still hinders), and most modern Unix systems use a non-user readable /etc/shadow to store the encrypted passwords. Of course, if you use NIS, anyone being able to snoop the network can see the encrypted passwords.

Abigail

It doesn't make the encryption more random. That doesn't make any sense.

I suspect he meant the encryption key, not the encryption process. Indeed, making the process random wouldn't make any sense.

---

$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}}
split//,".rekcah lreP rehtona tsuJ";$\=$ ;->();print$/
[download]