Fixed password schemes: attacks

(i) Replay of fixed passwords

A weakness of schemes using fixed, reusable passwords (i.e., the basic scheme of §10.2), is the possibility that an adversary learns a user’s password by observing it as it is typed in (or from where it may be written down). A second security concern is that user-entered passwords (or one-way hashes thereof) are transmitted hi cleartext over the communications line between the user and the system, and are also available in cleartext temporarily during system verification. An eavesdropping adversary may record this data, allowing subsequent impersonation.

Fixed password schemes are thus of use when the password is transmitted over trusted communications lines safe from monitoring, but are not suitable in the case that passwords are transmitted over open communications networks. For example, in Figure 10.1, the claimant A may be a user logging in from home over a telephone modem, to a remote office site В two (or two thousand) miles away; the cleartext password might then travel over an unsecured telephone network (including possibly a wireless link), subject to eavesdropping.

In the case that remote identity verification is used for access to a local resource, e.g., an automated cash dispenser with on-line identity verification, the system response (ac- cept/reject) must be protected in addition to the submitted password, and must include variability to prevent trivial replay of a time-invariant accept response.

(ii) Exhaustive password search

A very naive attack involves an adversary simply (randomly or systematically) trying passwords, one at a time, on the actual verifier, in hope that the correct password is found. This may be countered by ensuring passwords are chosen from a sufficiently large space, limiting the number of invalid (on-line) attempts allowed within fixed tune periods, and slowing down the password mapping or login-process itself as in §10.2.l(iv). Off-line attacks, involving a (typically large) computation which does not require interacting with the actual verifier until a final stage, are of greater concern; these are now considered.

Given a password file containing one-way hashes of user passwords, an adversary may attempt to defeat the system by testing passwords one at a time, and comparing the one-way hash of each to passwords in the encrypted password file (see § 10.2. l(ii)). This is theoretically possible since both the one-way mapping and the (guessed) plaintext are known. (This could be precluded by keeping any or all of the details of the one-way mapping or the password file itself secret, but it is not considered prudent to base the security of the system on the assumption that such details remain secret forever.) The feasibility of the attack depends on the number of passwords that need be checked before a match is expected (which itself depends on the number of possible passwords), and the time required to test each (see Example 10.4, Table 10.1, and Table 10.2). The latter depends on the password mapping used, its implementation, the instruction execution time of the host processor, and the number of processors available (note exhaustive search is parallelizable). The time required to actually compare the image of each trial password to all passwords hi a password file is typically negligible.

10.4 Example (password entropy) Suppose passwords consist of strings of 7-bit ASCII characters. Each has a numeric value in the range 0-127. (When 8-bit characters are used, values 128-255 compose the extended character set, generally inaccessible from standard keyboards.) ASCII codes 0-31 are reserved for control characters; 32 is a space character; 33- 126 are keyboard-accessible printable characters; and 127 is a special character. Table 10.1 gives the number of distinct «-character passwords composed of typical combinations of characters, indicating an upper bound on the security of such password spaces. □ [1]

—» c l n

  • 20
  • (lowercase)

30 (lowercase alphanumeric)

02 (mixed case alphanumeric)

95 (keyboard characters)































Table 10.1: Birsize of password space for various character combinations. The number of n- cliaracter passwords, given c choices per character, is c". The table gives the base-2 logarithm of this number of possible passwords.

—» c l n

  • 20
  • (lowercase)

30 (lowercase alphanumeric)

02 (mixed case alphanumeric)

95 (keyboard characters)


0.07 hr

3.4 hr

51 hr

430 In


17 hr

120 In

130 dy

4.7 yr


19 dy

180 dy

22 yr

440 yr


1.3 yr

18 yr

1400 yr

42000 yr


34 yr

040 yr

80000 yr

4.0 x 10® yr


890 yr

23000 yr

5.3 x 106 yr

3.8 x 10s yr

Table 10.2: Time required to search entire password space. The table gives the time T (in hours, days, or years) required to search or pre-compute over the entire specified spaces using a single processor (cf. Table 10.1). T = cn ■ t ■ y, where t is the number of times the password mapping is iterated, and у the time per iteration, for t = 25, у = 1/(125 000) sec. (This approximates the UNIX ciypt command on a high-end PC pet forming DES at 1.0 Mbytes/s - see §10.2.3.)

on specialized topics such as music, film, etc. are available. For efficiency in repeated use by an adversaiy, an “encrypted” (hashed) list of dictionary or high-probability passwords may be created and stored on disk or tape; password images from system password files may then be collected, ordered (using a sorting algorithm or conventional hashing), and then compared to entries in the encrypted dictionary. Dictionary-style attacks are not generally successful at finding a particular user’s password, but find many passwords in most systems.

  • [1] Password-guessing and dictionary attacks To improve upon the expected probability of success of an exhaustive search, rather thansearching through the space of all possible passwords, an adversary may search the space inorder of decreasing (expected) probability. While ideally arbitrary strings of n characterswould be equiprobable as user-selected passwords, most (unrestricted) users select passwords from a small subset of the full password space (e.g., short passwords; dictionarywords; proper names; lowercase strings). Such weak passwords with low entropy are easilyguessed; indeed, studies indicate that a large fraction of user-selected passwords are foundin typical (intermediate) dictionaries of only 150 000 words, while even a large dictionaryof 250 000 words represents only a tiny fraction of all possible «-character passwords (seeTable 10.1). Passwords found in any on-line or available list of words may be uncovered by an adversary who tries all words in this list, using a so-called dictionary attack. Aside from traditional dictionaries as noted above, on-line dictionaries of words from foreign languages, or
< Prev   CONTENTS   Source   Next >