Password security
Gordon Burditt
gordon at sneaky.TANDY.COM
Mon Nov 21 17:36:16 AEST 1988
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
More information about the Comp.unix.wizards
mailing list