Path: utzoo!attcan!uunet!husc6!bloom-beacon!mit-eddie!killer!texbell!sneaky!gordon
From: gordon@sneaky.TANDY.COM (Gordon Burditt)
Newsgroups: comp.unix.wizards
Subject: Password security
Keywords: pass phrases
Message-ID: <4449@sneaky.TANDY.COM>
Date: 21 Nov 88 07:36:16 GMT
Distribution: na
Organization: Gordon Burditt
Lines: 89

The DES algorithm used in password encryption takes 56 bits of key information 
from the user's typed in password, and uses this key to encrypt a constant 
some number of times.  (What constant and how many times aren't relevant
here.)  The 56 bits are taken as the 7 low-order bits of each of 8 characters 
of the password.  A brute-force exhaustive search would seemingly require up 
to 2**56 encryptions.  However, the number of likely 56-bit keys is reduced 
considerably for various reasons:

- Certain characters are untypable in passwords:  nul, newline, backspace, 
  and line-kill characters, and possibly ^S, ^Q, and ^M.
- Users tend not to like to type control characters and shifted characters.
- Users tend to choose passwords that make sense and are easy to remember.

Assuming for the moment that DES is kept, security would be increased if more 
of the 2**56 bit combinations were generated by "obvious" passwords that users 
can easily remember.  So, I propose the following change to the password 
algorithm.  It can be implemented by someone having the source to login (see 
alt.sources for a recently posted one), passwd, su, and related programs,
and the object code to crypt(3).

- Change the length of the password to 28 characters minimum, 512 characters 
  maximum.
- Map this password into an old-style 8-character password that crypt(3) takes.
- Call crypt(3) to get an encrypted password.

The mapping algorithm works like this:

First, shorten the password to 28 characters.  Break the entered password into 
28-character blocks, with the last one padded out to 28 characters with 
nulls.  Combine the 28-character blocks by adding the corresponding characters 
in each block to generate a sum 28-character block.  This isn't supposed to be 
hard to crack, but it does mean that whether the user finishes the word that 
ran over 28 characters or not DOES make a difference.

Next, derive TWO BITS from each of the 28 characters.  I suggest using the
low-order bit and the parity.  Map the 56 bits into the 7 low-order bits of 8 
characters of a conventional password.  Since crypt(3) ignores the high-order 
bits (8-bit-character chauvenism here), set all of them, so if one character 
happens to be all zeros, it won't terminate the string.  Add a null as the 9th 
character to terminate the string.

I can hear the arguments now:  "But...But...But...there are millions of ways 
to type the user's password, and one of them might be easy to guess!" Yep.  
Each password has a "canonical representation" consisting of a 28-character 
string containing only the characters "0", "1", "2", and "3".  There are 
millions of times more ways to type a given correct password than there are 
canonical wrong passwords.  There is even a 25% chance that if you type your 
password in with one character wrong, you will get in anyway.  This mapping 
scheme should be explained to users so they don't lose confidence in the 
system (at least not for the wrong reason).  

Now, what about attacks?  Dictionary attacks are greatly complicated.  Let's 
suppose that all passwords are 4 words from /usr/dict/words. The number of
combinations went from 24,000 (single word) to 24,000**4, or about 
3.3 * 10**17.  This is about 4 times the number of canonical passwords, or
worse than brute force.  

How about pre-computed encryption dictionaries?  Well, it's no longer safe to 
assume that only printable characters appear in the 8-character password fed 
to crypt(3), so the size goes up by a factor of about 10.  If the assumption
was being made that passwords are lower-case alphanumeric, the size goes
up by a factor of about 25,000.

You know the guy and he's in love with his car?  Well, his license plate 
number, pet name for his car, make, and model are all under 28 characters, so 
they can't be the whole password.  Even if you think he used 3 of these 
together, that's 24 orders, times lots of combinations of with and 
without spaces, capital letters, etc.  And who says his dealer's phone
number isn't in there?  Things like license plate numbers, phone numbers, 
social security numbers, first names, etc. can no longer be a whole password.

Well, what does anyone think?  Does having multiple correct passwords
scare anyone off?

Some other suggestions:  if possible, use shadow password files.  In spite
of arguments that they aren't totally secure (theft of backup tapes, for
instance), they do provide some protection.  The recent Internet Worm
COULD HAVE sent back copies of password files for every system it
infected.  It couldn't have gotten at shadow password files.  There is
also no risk from a badly-configured or buggy uucp allowing a uucp neighbor
to grab the encrypted passwords, since uucp doesn't have access to them.

If you have the expertise to fool with crypt(3) and be sure you aren't
weakening the encryption, make the salt bigger.  4096 combinations isn't
enough.


					Gordon L. Burditt
					...!texbell!sneaky!gordon