in reply to Salt -- Something I've Never Understood

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...

  • Comment on Re: Salt -- Something I've Never Understood

Replies are listed 'Best First'.
Re: Re: Salt -- Something I've Never Understood
by MidLifeXis (Monsignor) on Feb 05, 2004 at 20:04 UTC

    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