Section 9.1. Introduction

9.1. Introduction

The ubiquity of graphical user interfaces and input devices, such as the mouse, stylus, and touch screen, that permit other than typed input, has enabled the emergence of graphical passwords. Graphical passwords are particularly useful for systems that do not have keyboards. In addition, they offer the possibility of addressing known weaknesses in text passwords. History has shown that the distribution of text passwords chosen by human users has entropy far lower than possible,^{[1], [2], [3], [4]} and this has remained a significant weakness of user authentication for over 30 years. Given the fact that pictures are generally more easily remembered than words,^{[5], [6]} it is conceivable that humans would select and remember graphical passwords that are stronger than the text passwords they typically select.

^[1] R. Morris and K. Thompson, "Password Security: A Case History," Communications of the ACM 22:11 (Nov. 1979), 594597.

^[2] D. Feldmeier and P. Karn, "UNIX Password SecurityTen Years Later," Advances in CryptologyCRYPTO '89 (Lecture Notes in Computer Science 435), 1990.

^[3] D. Klein, "Foiling the Cracker: A Survey of, and Improvements to, Password Security," Proceedings of the 2nd USENIX Security Workshop (Aug. 1990), 514.

^[4] T. Wu, "A Real-World Analysis of Kerberos Password Security," Proceedings of the 1999 ISOC Symposium on Network and Distributed System Security (Feb. 1999).

^[5] D. L. Nelson, U. S. Reed, and J. R. Walling, "Picture Superiority Effect," Journal of Experimental Psychology: Human Learning and Memory 3 (1977), 485497.

^[6] S. Madigan, "Picture Memory," Imagery, Memory, and Cognition (Hillsdale, NJ: Erlbaum, 1983), 6586.

The goal of this chapter is to review some proposed graphical password schemes and the analyses that have been performed to evaluate their security and/or usability. Where appropriate, we explain these schemes in the context of results from the psychological literature. In surveying this information, we also hope to elucidate those topics in graphical passwords that are candidates for future research.

Today, text passwords have many uses, but these uses can be grouped into two types:

• Authentication. The first and most common is as a method of user authenticationthat is, to confirm the claimed identity of a human user. The output of this process is one bit: "1" means that the user is as claimed, "0" indicates that he is not.

• Key generation. The second is as a method of key generation by the human user, for the purpose of using the resulting key in a cryptographic algorithm. A common example of this type is file or disk encryption using a password: the user inputs her password, and this password is used to encrypt or decrypt certain stored contents of the device. Unlike authentication, key generation requires an output of many more bits (e.g., 80), and each bit should be unpredictable to an adversary who does not know the password.

In both cases, the output should be repeatable by a user who knows the password.

In order to stand in for text passwords, graphical passwords supporting both types of use are needed. While arguably the two types of use can be supported via a common mechanismthe only difference being whether the entered password is compared against a stored template (as in the authentication case) or output directlymost proposed graphical password systems have a password space that could be searched exhaustively by an automated program in a short time. Because this is exactly the attack that user-based key generation is intended to address, such schemes may not be useful for key generation; nevertheless, they may still be useful for user authentication. We thus find it useful to separate the two notions.

As with text passwords, most graphical password schemes can be configured to permit the user to choose the password, or to have the password generated by the system and given to the user. In the latter case, the security of the graphical password is presumably high, whereas the usability might suffer. In the former case, usability might be better, but as we will show, the security of the graphical passwords might be weakened.