Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Salt -- Something I've Never Understood

by Cody Pendant (Prior)
on Feb 05, 2004 at 04:48 UTC ( #326684=perlquestion: print w/replies, xml ) Need Help??

Cody Pendant has asked for the wisdom of the Perl Monks concerning the following question:

I've asked this in the CB and felt stupid.

What's the point of the "salt" in "crypt"?

Please don't point out that crypt isn't professional-level encryption, I'm not using it, I've just never got the point of the salt part.

It makes the encrypted thing more random (because you choose the two characters), and therefore more secure? But then it saves the two characters, so if someone was trying to crack it, that would help, not hinder them, right?



($_='kkvvttuubbooppuuiiffssqqffssmmiibbddllffss')
=~y~b-v~a-z~s; print
  • Comment on Salt -- Something I've Never Understood

Replies are listed 'Best First'.
Re: Salt -- Something I've Never Understood
by saintmike (Vicar) on Feb 05, 2004 at 05:16 UTC
    The salt might seem useless at first to prevent cracking a password if the algorithm (crypt) is known and the salt (two characters, openly available in /etc/passwd) is known and the way the salt and the algorithm are combined is known.

    However, it serves a purpose: It complicates the attacker's task to come with a pre-encrypted dictionary (a huge list of common passwords, already encrypted with the crypt), go to the target computer and do quick lookups of the encrypted passwords in /etc/passwd in the dictionary.

    It complicates this task by multiplying the number of entries in the pre-crypted dictionary by the number of possible salt values. Or by having the attacker run crypt() based on the actual salt values at attack time.
Re: Salt -- Something I've Never Understood
by blokhead (Monsignor) on Feb 05, 2004 at 05:19 UTC
    If there were no salt, then someone could spend a few CPU years running every plausible password string through crypt() and make/distribute a reverse-mapping database. With a random salt, the size of such a database becomes much more infeasible to try to produce (you have to try each possible password with each possible salt string). But I doubt this is much of an issue these days, thanks to Moore's law and distributed computing.

    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.

    blokhead

      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 232 possible salt values, so it takes 160 * 232 = 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

Re: Salt -- Something I've Never Understood
by atcroft (Abbot) on Feb 05, 2004 at 15:37 UTC

    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 [azAZ09./]. 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

Re: Salt -- Something I've Never Understood
by allolex (Curate) on Feb 05, 2004 at 08:27 UTC

    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.

    --
    Allolex

      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$/
Re: Salt -- Something I've Never Understood
by Cody Pendant (Prior) on Feb 06, 2004 at 03:43 UTC
    Thank you all for your comments. I understand it now and I appreciate the interesting discussions.


    ($_='kkvvttuubbooppuuiiffssqqffssmmiibbddllffss')
    =~y~b-v~a-z~s; print
A reply falls below the community's threshold of quality. You may see it by logging in.
A reply falls below the community's threshold of quality. You may see it by logging in.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://326684]
Approved by jweed
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (3)
As of 2023-09-26 01:31 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?