In this section, we enumerate the problems of password-based authentication, which we address with our work in section 3.
Password and PIN-based user authentication have numerous deficiencies. Unfortunately, many security systems are designed such that security relies entirely on a secret password. Cheswick and Bellovin point out that weak passwords are the most common cause for system break-ins [CB94].
The main weakness of knowledge-based authentication is that it relies on precise recall of the secret information. If the user makes a small error in entering the secret, the authentication fails. Unfortunately, precise recall is not a strong point of human cognition. People are much better at imprecise recall, particularly in recognition of previously experienced stimuli [Int80, PC69].
The human limitation of precise recall is in direct conflict with the requirements of strong passwords. Many researchers show that people pick easy to guess passwords. For example, an early study by Morris and Thompson on password security found that over 15% of users picked passwords shorter or equal to three characters [MT79]. Furthermore, they found that 85% of all passwords could be trivially broken through a simple exhaustive search to find short passwords and by using a dictionary to find longer ones. They describe an effort to counteract poor passwords, which consists of issuing random pronounceable passwords to users. Unfortunately, the random number generator only had distinct seeds, and hence the resulting space of ``random'' passwords could be searched quickly. Klein conducted a wide-reaching study of password security in 1989 and notes that 25% of all passwords can be broken with a small dictionary [Kle90].
Other notable efforts to design password crackers were conducted by Feldmeier and Karn [FK89] and Muffett [Muf92]. Because of these password cracker programs, users need to create unpredictable passwords, which are more difficult to memorize. As a result, users often write their passwords down and ``hide'' them close to their work space. Strict password policies, such as forcing users to change passwords periodically, only increase the number of users who write them down to aid memorability.
As companies try to increase the security of their IT infrastructure, the number of password protected areas is growing. Simultaneously, the number of Internet sites which require a username and password combination is also increasing. To cope with this, users employ similar or identical passwords for different purposes, which reduces the security of the password to that of the weakest link.
Another problem with passwords is that they are easy to write down and to share with others. Some users have no qualms about revealing their passwords to others; they view this as a feature and not as a risk, as we find in the user study discussed in section 4.
The majority of solutions to the problems of weak passwords fall into three main categories. The first types of solutions are proactive security measures that aim to identify weak passwords before they are broken by constantly running a password cracking programs [MT79, FK89]. The second type of solution is also technical in nature, which utilizes techniques to increase the computational overhead of cracking passwords [Man96]. The third class of solutions involves user training and education to raise security awareness and establishing security guidelines and rules for users to follow [AS99, Bel93].
Note that all three classes of solutions do not remedy the main cause of password insecurity, which is the human limitation of memory for secure passwords. In fact, most previously proposed schemes for knowledge-based user authentication rely on perfect memorization. One exception is the work of Ellsion et al. , which describes a knowledge based authentication mechanism that can tolerate user memory errors [EHMS99]. We discuss these schemes in detail in section 5.