11.2. Passwords

Definition 112. A password is information associated with an entity that confirms the entity's identity.

The simplest password is some sequence of characters. In this case, the password space is the set of all sequences of characters that can be passwords.

EXAMPLE: One installation requires each user to choose a sequence of 10 digits as a password. Then A has 1010 elements (from "0000000000" to "9999999999").

The set of complementary information may contain more, or fewer, elements than A, depending on the nature of the complementation function. Originally, most systems stored passwords in protected files. However, the contents of such files might be accidentally exposed. Morris and Thompson [651] recount an amusing example in which a Multics system editor swapped pointers to the temporary files being used to edit the password file and the message of the day file (printed whenever a user logged in); the result was that whenever a user logged in, the cleartext password file was printed.

The solution is to use a one-way hash function to hash the password into a complement [943].

EXAMPLE: The original UNIX password mechanism does not store the passwords online in the clear. Instead, one of 4,096 functions hashes the password into an 11-character string, and two characters identifying the function used are prepended [651]. The 13-character string is then stored in a file. A UNIX password is composed of up to eight ASCII characters; for implementation reasons, the ASCII NUL (0) character is disallowed. Hence, A is the set of strings of up to eight characters, each chosen from a set of 127 possible characters.[1] A contains approximately 6.9 x 1016 passwords. However, the set C contains strings of exactly 13 characters chosen from an alphabet of 64 characters. C contains approximately 3.0 x 1023 strings. The subset of C corresponding to selected passwords may or may not be readable. Many UNIX systems store these strings in the file /etc/passwd, which all users can read. Many other versions of the UNIX system, however, store these strings in shadow password files that only the superuser can read [347, 406]. The UNIX hashing functions f F are based upon a permutation of the Data Encryption Standard. F consists of 4,096 such functions fi, 0 i < 4,096. The UNIX authentication functions are login, su, and other programs that confirm a user's password during execution. This system supplies the proper element of C; that information may not be available to the user. Some of these functions may be accessible over a networkfor example, through the telnet or FTP protocols. Finally, the selection functions are programs such as passwd and nispasswd, which change the password associated with an entity.

^[1] In practice, some characters (such as the erase character) have special meanings and are rarely used.

The goal of an authentication system is to ensure that entities are correctly identified. If one entity can guess another's password, then the guesser can impersonate the other. The authentication model provides a systematic way to analyze this problem. The goal is to find an a A such that, for f F, f(a) = c C and c is associated with a particular entity (or any entity). Because one can determine whether a is associated with an entity only by computing f(a) or by authenticating via l(a), we have two approaches for protecting the passwords, used simultaneously.

EXAMPLE: One site does not allow the root user to log in from a network. The login functions exist but always fail. Hence, one cannot test authentication of root with access to these functions over a network.

Each of these approaches leads to different types of attacks and defenses.

11.2.1. Attacking a Password System

The simplest attack against a password-based system is to guess passwords.

Definition 113. A dictionary attack is the guessing of a password by repeated trial and error.

The name of this attack comes from the list of words (a "dictionary") used for guesses. The dictionary may be a set of strings in random order or (more usually) a set of strings in decreasing order of probability of selection.

If the complementary information and complementation functions are available, the dictionary attack takes each guess g and computes f(g) for each f F. If f(g) corresponds to the complementary information for entity E, then g authenticates E under f. This is a dictionary attack type 1. If either the complementary information or the complementation functions are unavailable, the authentication functions l L may be used. If the guess g results in l returning true, g is the correct password. This is a dictionary attack type 2.

EXAMPLE: Attackers often obtain a UNIX system's password file and use the (known) complementation function to test guesses. (Many programs such as crack automate this process.) This is a type 1 attack. But the attackers need access to the system to obtain the complementation data in the password file. To gain access, they may try to guess a password using the authentication function. They use a known account name (such as root) and guess possible passwords by trying to log in. This is a type 2 attack.

The issue of efficiency controls how well an authentication system withstands dictionary attacks.

11.2.2. Countering Password Guessing

Password guessing requires either the set of complementation functions and complementary information or access to the authentication functions. In both approaches, the goal of the defenders is to maximize the time needed to guess the password. A generalization of Anderson's Formula [24] provides the fundamental basis.

Let P be the probability that an attacker guesses a password in a specified period of time. Let G be the number of guesses that can be tested in one time unit. Let T be the number of time units during which guessing occurs. Let N be the number of possible passwords. Then .

EXAMPLE: Let R be the number of bytes per minute that can be sent over a communication line, let E be the number of characters exchanged when logging in, let S be the length of the password, and let A be the number of characters in the alphabet from which the characters of the password are drawn. The number of possible passwords is N = AS, and the number of guesses per minute is G = R/E. If the period of guessing extends M months, this time in minutes is T = 4.32 x 104 M. Then , the original statement of Anderson's Formula.

EXAMPLE: Let passwords be composed of characters drawn from an alphabet of 96 characters. Assume that 104 guesses can be tested each second. We wish the probability of a successful guess to be 0.5 over a 365-day period. What is the minimum password length that will give us this probability? From the formulas above, we want = . Thus, we must choose an integer S such that . This holds when S 6. So, to meet the desired conditions, passwords of at least length 6 must be required.

Several assumptions underlie these examples. First, the time required to test a password is constant. Second, all passwords are equally likely to be selected. The first assumption is reasonable, because the algorithms used to validate passwords are fixed, and either the algorithms are independent of the password's length or the variation is negligible. The second assumption is a function of the password selection mechanism. We will now elaborate on these mechanisms.

11.2.2.1 Random Selection of Passwords

The following theorem from probability theory states a maximum on the expected time to guess a password.

Theorem 111. Let the expected time required to guess a password be T. Then T is a maximum when the selection of any of a set of possible passwords is equiprobable.

Proof See Exercise 1.

Theorem 111 guides selection of passwords in the abstract. In practice, several other factors mediate the result. For example, passwords selected at random include very short passwords. Attackers try short passwords as initial guesses (because there are few enough of them so that all can be tried). This suggests that certain classes of passwords should be eliminated from the space of legal passwords P. The danger, of course, is that by eliminating those classes, the size of P becomes small enough for an exhaustive search.

Complicating these considerations is the quality of the random (or pseudorandom) number generator. If the period of the password generator is too small, the size of P allows every potential password to be tested. This situation can be obvious, although more often it is not.

EXAMPLE: Morris and Thompson [651] tell about a PDP-11 system that randomly generated passwords composed of eight capital letters and digits, so to all appearances, |P| = (26 + 10)8 = 368. Taking 0.00156 second per encryption meant that trying all possible passwords would require 140 years. The attacker noticed that the pseudorandom number generator was run on the PDP-11, and it had a period of 216 1 (because the PDP-11 is a 16-bit machine). This meant that there were 216 1, or 65,535, possible passwords, requiring 102 seconds to try them all. It actually took less than 41 seconds to find all the passwords.

Human factors also play a role in this problem. Psychological studies have shown that humans can repeat with perfect accuracy about eight meaningful items, such as digits, letters, or words [206]. If random passwords are eight characters long, humans can remember one such password. So a person who is assigned two random passwords must write them down. Although most authorities consider this to be poor practice, the vulnerabilities of written passwords depend on where a written password is kept. If it is kept in a visible or easily accessed place (such as taped to a terminal or a keyboard or pinned to a bulletin board), writing down the password indeed compromises system security. However, if wallets and purses are rarely stolen by thieves with access to the computer systems, writing a password down and keeping it in a wallet or purse is often acceptable.

Michele Crabb describes a clever method of obscuring the written password [218]. Let X be the set of all strings over some alphabet. A site chooses some simple transformation algorithm t: X A. Elements of X are distributed on pieces of paper. Before being used as passwords, they must be transformed by applying t. Typically, t is very simple; it must be memorized, and it must be changed periodically.

EXAMPLE: The transformation algorithm is: "Capitalize the third letter in the word, and append the digit 2." The word on the paper is "Swqgle3". The password will be "SwQgle32".

This scheme is most often used when system administrators need to remember many different passwords to access many different systems. Then, even if the paper is lost, the systems will not be compromised.

11.2.2.2 Pronounceable and Other Computer-Generated Passwords

A compromise between using random, unmemorizable passwords and writing passwords down is to use pronounceable passwords. Gasser [350] did a detailed study of such passwords for the Multics system and concluded that they were viable on that system.

Pronounceable passwords are based on the unit of sound called a phoneme. In English, phonemes for constructing passwords are represented by the character sequences cv, vc, cvc, or vcv, where v is a vowel and c a consonant.

EXAMPLE: The passwords "helgoret" and "juttelon" are pronounceable passwords; "przbqxdf " and "zxrptglfn" are not.

The advantage of pronounceable passwords is that fewer phonemes need to be used to reach some limit, so that the user must memorize "chunks" of characters rather than the individual characters themselves. In effect, each phoneme is mapped into a distinct character, and the number of such characters is the number of legal phonemes. In general, this means that the number of pronounceable passwords of length n is considerably lower than the number of random passwords of length n. Hence, a type 1 dictionary attack is expected to take less time for pronounceable passwords than for random passwords.

Assume that passwords are to be at most eight characters long. Were these passwords generated at random from a set of 96 printable characters, there would be 7.3 x 10¹⁵ possible passwords. But if there are 440 possible phonemes, generating passwords with up to six phonemes produces approximately the same number of possible passwords. One can easily generalize this from phonemes to words, with similar results.

One way to alleviate this problem is through key crunching [373].

Definition 114. Let n and k be two integers, with n k. Key crunching is the hashing of a string of length n or less to another string of length k or less.

Conventional hash functions, such as MD5 and SHA-1, are used for key crunching.

11.2.2.3 User Selection of Passwords

Rather than selecting passwords for users, one can constrain what passwords users are allowed to select. This technique, called proactive password selection [107], enables users to propose passwords they can remember, but rejects any that are deemed too easy to guess.

The set of passwords that are easy to guess is derived from experience coupled with specific site information and prior studies [423, 651, 656, 859]. Klein's study [512] is very comprehensive. He took 15,000 password hashes and used a set of dictionaries to guess passwords. Figure 11-1 summarizes his results. Some categories of passwords that researchers have found easy to guess are as follows.

EXAMPLE: The strings "hello" and "mycomputer" are poor passwords because they violate criteria 4 and 18, respectively. The strings "1PLK107" and "311t3$p32k" are also poor (the first is a California licence plate number and violates criterion 15, and the second is the word "elitespeak" modified as in criterion 9).

Good passwords can be constructed in several ways. A password containing at least one digit, one letter, one punctuation symbol, and one control character is usually quite strong. A second technique is to pick a verse from an obscure poem (or an obscure verse from a well-known poem) and pick the characters for the string from its letters.

EXAMPLE: The string "LlMm*2^Ap" (where ^A represents control-a) is a good password. The letters are chosen from the names of various members of two families, and the combination of characters is unlikely to be guessed even by those who know the families. As a more complex example, few people can recite the third verse of "The Star-Spangled Banner" (the national anthem of the United States of America): And where is that band who so vauntingly swore That the havoc of war and the battle's confusion A home and a country should leave us no more? Their blood has wiped out their foul footsteps' pollution. No refuge could save the hireling and slave From the terror of flight, or the gloom of the grave: And the star-spangled banner in triumph doth wave O'er the land of the free and the home of the brave Choose the second letter of each word of length 4 or greater in the third line, alternating case, and add a "/" followed by the initials of the author of the poem: "OoHeO/FSK." This is also a password that is hard to guess. But see Exercise 5.

Definition 115. A proactive password checker is software that enforces specific restrictions on the selection of new passwords.

Proactive password checkers must meet several criteria [111]:

EXAMPLE: The proactive password checker OPUS [860] addresses the sizes of dictionaries. Its goal is to find a compact representation for very large dictionaries. Bloom filters provide the mechanism. Each word in the dictionary is run through a hash function that produces an integer hi of size less than some parameter n. This is repeated for k different hash functions, producing k integers h1, ..., hk. The OPUS dictionary is represented as a bit vector of length n. To put the word into the OPUS dictionary, bits h1, ..., hk are set. When a user proposes a new password, that word is run through the same hash functions. Call the output h1', ..., hk'. If any of the bits h1', ..., hk' are not set in the OPUS dictionary, the word is not in the OPUS dictionary and is accepted. If all are set, then to some degree of probability the word is in a dictionary fed to OPUS and should be rejected.

EXAMPLE: Ganesan and Davies [345] propose a similar approach. They generate a Markov model of the dictionary, extract information about trigrams, and normalize the results. Given a proposed password, they test to see if the word was generated by the Markov model extracted from the dictionary. If so, it is deemed too easy to guess and is rejected.

Both these methods are excellent techniques for reducing the space required to represent a dictionary. However, they do not meet all the requirements of a proactive password checker and should be seen as part of such a program rather than as sufficient on their own.

Example: A "little language" designed for proactive password checking [108] was based on these requirements. The language includes functions for checking whether or not words are in a dictionary (a task that could easily use the techniques of OPUS or Ganesan and Davies). It also included pattern matching and the ability to run subprograms, as well as the ability to compare passwords against previously chosen passwords. The keyword set sets the values of variables. For example, set gecos "Matt Bishop, 3085 EU-II" assigns the variable gecos to the value Matt Bishop, 3085 EU-II. Pattern assignment is available through setpat: setpat "$gecos" "^\([^,]\), \(.*\)$" name office This matches the pattern with the value of gecos (obtained by prefixing a "$" to the variable name). The strings matched by the subpatterns in "\(" and "\)" are assigned to the variables name and office (so name is Matt Bishop and office is 3085 EU-II). Equality and inequality operators work as string operators. All integers are translated to strings before any operations take place. Other functions are available; see Figure 11-2 for some examples. Figure 11-2. Examples of functions. [View full size image] The basic component of the little language is the password test block: test length("$p") < 6 true "Your password contains fewer than 6 characters." endtest This block says to compare the length of the proposed password, stored in the variable p earlier, and compare it with 6 (the test). If the test is true (that is, if the password is less than six characters long), the message in the second line is printed and the password is rejected. As another example, the test infile("/usr/dict/words", "$p") is true if the value of p is a string in the file "/usr/dict/words." The test !inprog("spell", "$p", "$p") is true if the output of the program spell, given the value of p as input, produces that same value as output. Because spell prints all misspelled input words, if the input and output match, then the value of p is not a correctly spelled word. The language contains many other functions, including one for testing for catenated words and another for hashing passwords using the UNIX password hashing function.

11.2.2.4 Reusable Passwords and Dictionary Attacks

As discussed earlier, reusable passwords are quite susceptible to dictionary attacks of type 1. The goal of random passwords, pronounceable passwords, and proactive password checking is to maximize the time needed to guess passwords.

If a type 1 dictionary attack is aimed at finding any user's password (as opposed to a particular user's password), a technique known as salting increases the amount of work required [651]. Salting makes the choice of complementation function a function of randomly selected data. Ideally, the random data is different for each user. Then, to determine if the string s is the password for any of a set of n users, the attacker must perform n complementations, each of which generates a different complement. Thus, salting increases the work by the order of the number of users.

EXAMPLE: Most versions of the UNIX system use salts. The salt is chosen randomly, when the password is set, and is an integer from 0 to 4,095, inclusive. The specific complementation function depends on the salt. Specifically, the E table in the DES is perturbed in one of 4,096 possible ways,[2] and the message of all 0 bits is enciphered using the password as a key. The resulting 64 bits are mapped into 11 characters chosen from a set of 64 characters. The salt is split into two sets of six bits, and those sets are mapped to printable characters using the same alphabet. The 11-character representation of output is appended to the two-character representation of the salt. The authentication function is chosen on the basis of the salt also; hence, the salt must be available to all programs that need to verify passwords.

^[2] Specifically, if bit i in the salt is set, table entries i and i + 24 are exchanged [651].

11.2.2.5 Guessing Through Authentication Functions

If the actual complements, or the complementation functions, are not publicly available, the only way to try to guess a password is to use the authentication function systems provide for authorized users to log in. Although this sounds difficult, the patience of some attackers is amazing. One group of attackers guessed passwords in this manner for more than two weeks before gaining access to one target system.

Unlike a type 1 dictionary attack, this attack cannot be prevented, because the authentication functions must be available to enable legitimate users to access the system. The computer has no way of distinguishing between authorized and unauthorized users except by knowledge of the password.

Defending against such attacks requires that the authentication functions be made difficult for attackers to use, or that the authentication functions be made to react in unusual ways. Four types of techniques are common.

Techniques of the first type are collectively called backoff techniques. The most common, exponential backoff, begins when a user attempts to authenticate and fails. Let x be a parameter selected by the system administrator. The system waits x⁰ = 1 second before reprompting for the name and authentication data. If the user fails again, the system reprompts after x¹ = x seconds. After n failures, the system waits xⁿ¹ seconds. Other backoff techniques use arithmetic series rather than geometric series (reprompting immediately, then waiting x seconds, then waiting 2x seconds, and so forth).

Techniques of the second type involve disconnection. After some number of failed authentication attempts, the connection is broken and the user must reestablish it. This technique is most effective when connection setup requires a substantial amount of time, such as redialing a telephone number. It is less effective when connections are quick, such as over a network.

EXAMPLE: If a user fails to supply a valid name and the corresponding password in three tries, FreeBSD (a variant of the UNIX operating system) breaks the connection.

Techniques of the third type use disabling. If n consecutive attempts to log in to an account fail, the account is disabled until a security manager can reenable it. This prevents an attacker from trying too many passwords. It also alerts security personnel to an attempted attack. They can take appropriate action to counter the threat.

One should consider carefully whether to disable accounts and which accounts to disable. A (possibly apocryphal) story concerns one of the first UNIX vendors to implement account disabling. No accounts were exempt. An attacker broke into a user account, and then attempted to log in as root three times. The system disabled that account. The system administrators had to reboot the system to regain root access.

EXAMPLE: Both UNIX systems and Windows NT systems have the ability to disable accounts after failed logins. Typically, the UNIX root account cannot be disabled. The Windows administrator account can be locked out (the equivalent of "disabled" in this context) from network logins, but not from local logins.

The final, fourth type of technique is called jailing. The unauthenticated user is given access to a limited part of the system and is gulled into believing that he or she has full access. The jail then records the attacker's actions. This technique is used to determine what the attacker wants or simply to waste the attacker's time.

EXAMPLE: An attacker was breaking into the computers of AT&T Bell Laboratories. Bill Cheswick detected the attack and simulated a slow computer system. He fed the attacker bogus files and watched what the attacker did. He concluded that keeping the jail was not an effective way to discover the attacker's goals [171].

One form of the jailing technique is to plant bogus data on a running system, so that after breaking in the attacker will grab the data. (This technique, called honeypots, is often used in intrusion detection. See Section 22.6.2.1, "Containment Phase.") Clifford Stoll used this technique to help trap an attacker who penetrated computers at the Lawrence Berkeley Laboratory. The time required to download the bogus file was sufficient to allow an international team to trace the attacker through the international telephone system [878, 880].

11.2.3. Password Aging

Guessing of passwords requires that access to the complement, the complementation functions, and the authentication functions be obtained. If none of these have changed by the time the password is guessed, then the attacker can use the password to access the system.

Consider the last sentence's conditional clause. The techniques discussed in Section 11.2 attempt to negate the part saying "the password is guessed" by making that task difficult. The other part of the conditional clause, "if none of these have changed," provides a different approach: ensure that, by the time a password is guessed, it is no longer valid.

Definition 116. Password aging is the requirement that a password be changed after some period of time has passed or after some event has occurred.

Assume that the expected time to guess a password is 180 days. Then changing the password more frequently than every 180 days will, in theory, reduce the probability that an attacker can guess a password that is still being used. In practice, aging by itself ensures little, because the estimated time to guess a password is an average; it balances those passwords that can be easily guessed against those that cannot. If users can choose passwords that are easy to guess, the estimation of the expected time must look for a minimum, not an average. Hence, password aging works best in conjunction with other mechanisms such as the ones discussed in this chapter.

There are problems involved in implementing password aging. The first is forcing users to change to a different password. The second is providing notice of the need to change and a user-friendly method of changing passwords.

Password aging is useless if a user can simply change the current password to the same thing. One technique to prevent this is to record the n previous passwords. When a user changes a password, the proposed password is compared with these n previous ones. If there is a match, the proposed password is rejected. The problem with this mechanism is that users can change passwords n times very quickly, and then change them back to the original passwords. This defeats the goal of password aging.

An alternative approach is based on time. In this implementation, the user must change the password to one other than the current password. The password cannot be changed for a minimum period of time. This prevents the rapid cycling of passwords. However, it also prevents the user from changing the password should it be compromised within that time period.

EXAMPLE: UNIX systems use the time period method to age passwords (when password aging is turned on). They record the time of the last change, the minimum time before which the password can be changed again, and the time by which the password must be changed. Different systems use different formats. System V UNIX systems record the information in terms of weeks since January 1, 1970; HP/UX systems running in trusted mode record it in terms of seconds since midnight of that epoch.

If passwords are selected by users, the manner in which users are reminded to change their passwords is crucial. Users must be given time to think of good passwords or must have their password choices checked. Grampp and Morris [371] point out that, although there is no formal statistical evidence to support it, they have found that the easiest passwords to guess are on systems that do not give adequate notice of upcoming password expirations.

EXAMPLE: Most System Vbased UNIX systems give no warnings or reminders before passwords expire. Instead, when users try to log in, they are told that their passwords have expired. Before they can complete the logins, they must change their passwords as part of the login process. Trusted HP/UX, on the other hand, gives warning messages every time a user logs in within some period of time before the password expires. The specific period of time is set by the system administrator.