432 CHAPTER 7 Counting and Combinatorics
Once the number of possibilities is known for a particular license plate scheme, it can
be decided whether enough different license plates will be available for all the cars to be
licensed. The Pigeon-Hole Principle will tell which schemes cannot be used. For example,
if there are three million cars to license before the scheme is changed or new plates are
issued, only alternatives (c) and (d) in Example 6 may be used.7.3.3 Application: UNIX Logon Passwords
The UNIX operating system requires that users prove their identity before accessing system
resources. A user typically begins a session by providing a username and a secret password
to a login program. This program then verifies the password using a systemwide password
file. A program called crypt takes a user's password and turns it into an entry in the sys-
tem's password file. To crack a system by guessing a password, you must figure out what
sequence of characters gives rise to the image of the crypt operation. A fast workstation
with specially designed software can try more than 200,000 words a second to see if any
trial word gives rise to the output of crypt. The question is whether it is reasonable to try all
possible combinations of symbols that can be valid passwords to discover a legal password.
The UNIX operating system has the following requirements for the user forming a
password:
"* Each password must have at least six characters. Only the first eight characters are
significant.
"* Each password must contain at least two alphabetical characters and at least one numeric
or special character. In this case, alphabetical refers to all uppercase or lowercase letters.
"* Each password must differ from both the user's login name and any reverse or circular
shift of that login name. In the application of this rule, an uppercase letter and the cor-
responding lowercase letter are considered to be the same; for example, user johnson
could not have password hnsOnjO.
"* A new password must differ from the old one by at least three characters. In the applica-
tion of this rule, an uppercase letter and its corresponding lowercase letter are considered
to be the same.
Example 12. How many passwords can be formed in the UNIX system? How long would
it take a user to try all possible combinations with the crypt program to discover a valid
password?
Solution. We are going to simplify the problem a bit: First, assume that all passwords
are six characters long. (We shall remove this restriction in an exercise at the end of the
chapter.) Second, temporarily assume that the required letters in the password occur as the
first two symbols of the password as we solve the problem. Also, temporarily assume that
the required special character occurs as the last symbol. (In Section 7.5, we will see how
to remove these two temporary restrictions.) We will find that these two restrictions add a
factor of 60 to the count. We will just add that factor without explanation at this time. We
will also assume that all 32 special characters on a standard keyboard count as possible
special characters.(# Passwords) = 60. (# Possible at position 1) ... (# Possible at position 6)
= 60. 52 .52. 84. 84. 84. 32
= 3,077,129,502,720