Is the encrypted password's salt simply random?

[Glenn F. Leavell]

In article <1991Feb26.201846.22584 at rigel.econ.uga.edu> I recently wrote:
>I'm using a randomly generated two-character salt from the set [a-zA-Z0-9./],
>and everything seems to be working fine.  Here's my question:  is this
>the right way to choose the salt - just a random thing?

Thanks to all who responded!  They are:

  "Ric Anderson" <ric at cs.arizona.edu>
  dkeisen at Gang-of-Four.Stanford.EDU (Dave Eisen)
  auvhess at auvsun1.tamu.edu (David K. Hess)
  chris at cs.uwa.oz.au (chris mcdonald)
  Tim Tsai <it1 at Ra.MsState.Edu>
  kimcm at diku.dk (Kim Christian Madsen)
  smb at ulysses.att.com
  Dave Turner (ptsfa!dmturne at ns.PacBell.COM)
  Chris Siebenmann <cks at hawkwind.utcs.toronto.edu>
  jfh at rpp386.Cactus.ORG (John F Haugh II)

The consensus seems to be that using a random salt is the right thing
to do.  Several people where nice enough to give me some advice on
good ways to choose random numbers or to point out how the BSD 4.3
"passwd" program does it.  More on that later.

I'd like to quote from the 9 May 1988 Sun Security Features Guide:

	The password encryption routine crypt() involves a "salt"
	used to perturb the encrypting algorithm, so that DES chips
	cannot be used to assist in cracking login passwords.

Becuase of this, and becuase the two characters of the salt are always the
first two characters of the encrypted password, I was wondering why the
choice of the salt really made any difference.   It was Chris Siebenmann
who sent me a response that cleared that up.  So, I'll highlight some of  
the respones that I received including Chris Siebenmann's.

Chris Siebenmann <cks at hawkwind.utcs.toronto.edu> writes:
 >The purpose of the salt is to increase the amount of encryption work that
 >must be done to check every password in the password file (and to move
 >it out of the realm of reasonableness to store, pre-encrypted, all the
 >words in a dictionary). Thus, you want (if possible) each password in
 >your password file to have a different salt, so a would-be cracker must
 >do
 >	# of words * # of passwords
 >encryptions to check every word against every password, instead of (at
 >worst) just the number of words. A useful reference for this is the
 >paper on password security for Unix in the V7 manual or the 1st Bell
 >Technical Journal on Unix (reprinted as something like "AT&T Readings
 >on Unix: <something>").

Ric Anderson <ric at cs.arizona.edu> writes:
 >The old BSD 4.3 "passwd" program uses 
 >    (void)time(&salt);
 >    salt = 9 * getpid();
 >    saltc[0] = salt & 077;
 >    saltc[1] = (salt>>6) & 077;
 >    for (i = 0; i < 2; i++) {
 >        c = saltc[i] + '.';
 >        if (c > '9')
 >            c += 7;
 >        if (c > 'Z')
 >            c += 6;
 >        saltc[i] = c;
 >    }
 >    return(crypt(pwbuf, saltc));
 >which is based on the time of day clock.

Kim Christian Madsen <kimcm at diku.dk> writes:
 >The salt is chosen from the indicated range, by random, that is there
 >is a minor twist.  Usually you use only the time to seed the random
 >generator, this is also done in finding the salt however the result of
 >getpid is also used in order to make it further random (two users
 >updating their passwords at the same time will not get the same
 >salt).

Finally, John F Haugh II <jfh at rpp386.Cactus.ORG> sent the following, which
describes a method for generating a random number:

 >what you are doing is correct, but i doubt that how you are doing
 >it is.  you need to get a =real= random number.  there are several
 >good sources of random numbers, and random number generators aren't
 >one of them.
 >
 >this is just an idea, but you might find it helpful if you've
 >never done anything like this and want to do it up right.
 >
 >you need to get several numbers, such as process ID, uptime in 
 >the finest resolution you can get, time of day clock in the
 >finest resolution you can get, and fold all of those bits into
 >the 12-bit resolution of the salt.  you want to do the folding in
 >a chaos-preserving fashion - that is, don't just stick all the
 >low 12 bits in the lower 12 bits of the salt, shift, repeat, etc.,
 >because if you do this carelessly with a 32 bit number you wind
 >up with more slop on the low end than the high end, and that will
 >cost you some amount of randomness lost.  try something like
 >merging the low order TOD bits with the high order uptime bits
 >and splater the PID bits in the middle, fold in half (which will
 >give you 32 bits on BSD machines because (struct timeval) is 64
 >bits wide - in which case, fold in half twice), then take that
 >16 bit mess and fold the top four bits into the other 12 bits
 >using the 12 bits to determine where they go.  something like
 >counting the one bits in the each of four three bit groups, then
 >use that to decide which bits gets twiddled.  after you are done
 >with that, split that 12 bit result into a pair of 6 bit numbers
 >that give you the [./A-Za-z0-9] alphabet characters for the salt.

Again, thanks to all who responded!
--  
Glenn F. Leavell  Systems Administrator  glenn at rigel.econ.uga.edu  404-542-3488
 University of Georgia Economics Department. 147 Brooks Hall. Athens, GA 30602