next up previous
Next: Improvements Up: User-Authentication Previous: User-Authentication

Passwords

The most widely used form of authentication is to require the user to type a password. Unix uses this approach. There are several ways to support passwords. We shall study some of these by studying the different schemes that have been used in Unix. We first study how Unix establishes contact with a user.

The system starts up executing the init process, whose process

On each terminal port available for interactive use, init forks a copy of itself, which attempts to open the port for reading and writing. (This new process has its own process identifier) The open succeeds when a directly connected terminal is turned on or a telephone call is accepted by a dial-up modem. Then the init process execs a program called getty.

Getty initializes terminal line parameters and prompts the user to type a login name, which getty collects. It then executes a program called login, passing the login name as an argument. The login process prompts a user for a password, and checks the input against an entry in the password file (/etc/passwd). If the password is valid, login sets the user identifier ( uid) of the process to that of the user logging in and executes the shell specified in `/etc/passwd'.

We now study the different schemes used in Unix to check passwords.

The First Approach

Unix was first implemented with a password file that contained the actual passwords of all the users, and for that reason this file had to be heavily protected agains being read or written. This approach caused several problems:

There was no way to prevent the making of copies by privileged users.

Errors could cause the contents of the file to be accessed. In one case, one system administrator was editing the password file while another was simultaneously editing the daily message that is printed on everyone's terminal. Due to a software design error, the temporary editor files of the two users were interchanged and thus, for a time, the password file was displayed to every user when he logged on.

The contents of the file saved on magnetic tape were available to anyone with physical access to these tapes.

The contents of the file, which also contained other informations such as user name, had to be duplicated on other files so that non-privileged processes could access them. These files had to be updated whenever a user was added to or dropped from the system.

The Second Approach

An obvious solution was to encrypt each user's password P with some key K and store the encrypted version: E (P, K)

in the password file. Now when the user tries to logs on to the system, the password he types is encrypted and compared with the encrypted version in the password file. If the two match, the login attempt succeeds. If the function E is hard to invert without a key, the password file could be read by everyone. If the function E is hard to invert even with a key, then the password and login programs could also be read by everyone. (Encryption functions that are hard to invert are called trap-door encryption algorithms)

A convenient and rather good encryption program available at that time was the M-209 program, which simulated the M-209 cipher machine used by the US Army during World War II. Unfortunately, the cyphertext produced by it was easily invertible, given the key. However, given the plaintext and the cyphertext, it was very hard to guess the key. Thus the new version of Unix used the password, not as the plaintext, but as the key, and a constant was encrypted using this key. The encrypted result was entered in the password file.

Attacks on the Second Approach

One approach to penetrating this scheme is to keep guessing the key until one succeeds. This method can work well since most people will use short passwords composed entirely of ASCII characters. In a collection of 3,289 passwords gathered from many users over a long period of time: 15 were a single ASCII character, 72 were strings of two ASCII characters, 464 were strings of three ASCII characters, 477 were strings of four alphanumerics, 706 were five letters, all upper-case or lower-case, 605 were six letters, all lower case.

On a PDP-11/70 the the amount of time needed to encrypt a potential password was 1.25 milliseconds. The time required to try all combinations of 5 lower case letters ((26) was 4 hours, of 6 lower case letters was 107 hours, of 4 ASCII characters was 93 hours, of 5 ASCII characters was 500 days, of 6 ASCII characters was 174 years. The search could be improved by trying first:
The app. 250,000 words in a dictionary spelled forwards and backwards
A list of first names, last names, street names, and city names (best obtained from some mailing list).
All valid license plates in the state.
Room numbers, social security numbers, telephone numbers etc.

Morris and Thompson, authors of the Unix password scheme, compiled a list of likely passwords using the above heuristics, encrypted each of these using the known password encryption algorithm, and checked to see if any of the encrypted password matched entries in their list. Over 86


next up previous
Next: Improvements Up: User-Authentication Previous: User-Authentication



Prasun Dewan
Mon Nov 4 12:08:34 EST 1996