Abstract or Summary:
In our experience, poorly chosen passwords continue to be a major cause of security breaches. The increasing popularity of the UNIX operating system and the Kerberos authentication protocol in commercial environments accentuates this problem, as both are vulnerable to dictionary attacks which search for poor passwords. A proactive password checker is a component of a password changing program that attempts to validate the quality of a password chosen by the user, before the selection is finalized. In addition to checking for several attributes such as the size of the password and whether the password is derived from information about the user, the heart of any conventional proactive checker is a program that matches the password against a dictionary of passwords known to be bad. This dictionary of passwords can occupy tens of megabytes of space (in a distributed environment the dictionary may have to be replicated several times), and the time to search the dictionary can be high, especially if an attempt is made to filter out bad noisy passwords (which are of the form: common words plus one character noise, e.g. tiger2 or compQuter).

Bapasswd is a new proactive password checker which drastically reduces the space and time requirements of the matching program. This is achieved by applying the theory of statistical inference on Markov chains to the “bad password recognition” problem. We assume that bad passwords are a language generated by a kth order Markov process, and then estimate the transition probabilities of this process from existing dictionaries of bad passwords. This table of transition probabilities, which takes up very little space, is then used in lieu of the dictionary itself. When given a password, Bapasswd will use statistical tests to determine, with a high degree of confidence, whether that password could have been generated by the same Markov process, and if so, rejects the password. A key feature of Bapasswd is that bad noisy passwords are automatically recognized as being unsuitable and need not be present in the initial training dictionary.

We present considerable empirical evidence to show that Bapasswd successfully filters out bad passwords, while simultaneously ensuring that it does not become very burdensome for a legitimate user to choose a new password.