Introduction

 

For the vast majority of computer systems, passwords are the method of choice for authenticating users. It is well-known, however, that passwords are susceptible to attack: users tend to choose passwords that are easy to remember, and often this means that they are also easy for an attacker to obtain by searching for candidate passwords. In one case study of 14,000 Unix passwords, almost 25% of the passwords were found by searching for words from a carefully formed ``dictionary'' of only $3 \times 10^6$ words [12]. This relatively high success rate is not unusual despite the fact that there are roughly $2 \times 10^{14}$ 8-character passwords consisting of digits and upper and lower case letters alone.

In this paper we explore an approach to user authentication that generalizes the notion of a textual password and that, in many cases, improves the security of user authentication over that provided by textual passwords. We design and analyze graphical passwords, which can be input by the user to any device with a graphical input interface. A graphical password serves the same purpose as a textual password, but can consist, for example, of handwritten designs (drawings), possibly in addition to text. The devices by which we are primarily motivated are ``personal digital assistants'' (PDAs) such as the Palm Pilot$^{\rm TM}$, Apple Newton$^{\rm TM}$, Casio Cassiopeia E-10$^{\rm TM}$, and others, which allow users to provide graphics input to the device via a stylus. More generally, graphical passwords can be used whenever a graphical input device, such as a mouse, is available.

To the best of our knowledge, the notion of a ``graphical password'' is due to Blonder [4]. That work proposed a password scheme in which the user is presented with a predetermined image on a visual display and required to select one or more predetermined positions (``tap regions'') on the displayed image in a particular order to indicate his or her authorization to access the resource. Beyond this proposal, however, [4] did not further explore the power of graphical passwords or argue security for its particular proposal.

In this paper we considerably advance the theory and practice of graphical passwords. We take as a main criterion the need to evaluate graphical passwords' security relative to that of textual passwords. We design two graphical password schemes that we believe to be more secure than textual passwords (and more secure than the scheme of [4]), and we employ novel analysis techniques to make this argument. Moreover, we describe our implementation of one of our graphical password schemes on the Palm Pilot.

The graphical password schemes that we propose derive their strength from the following observation: a graphical interface for providing input enables the user to decouple the positions of the inputs from their temporal order. This is in contrast to textual passwords input via a keyboard: here, the temporal order in which the user types characters uniquely determines their position in the password. However, in a graphical password, e.g., consisting of several drawn lines, the final position of each line can be determined independently of the temporal order in which the lines are drawn. We show that this independence between input position and order can be used to build interesting new password schemes, and in some cases obtain authentication that is convincingly stronger than textual passwords but not significantly harder to remember.

The first graphical password scheme builds directly on textual password schemes, by enhancing the input of textual passwords using graphical techniques. In this case, if we assume the same underlying distribution on the choice of the password, the graphical password is at least as strong as the textual password that underlies it, and even a conservative estimate of the variations introduced by the graphical input yields a substantial improvement in strength over the purely textual version. We propose and implement a second scheme, called ``draw a secret'' (DAS), which is purely graphical; the user draws a secret design (the password) on a grid. Here, to argue an improvement over textual passwords, we define a class of DAS passwords that, we believe, captures a small subset of the memorable ones. This class consists of those passwords that can be generated by a short program in a simple grid-based language. We do not argue that every memorable password has a short program to describe it, but that passwords describable by short programs are memorable. We show that even this subset of memorable DAS passwords is larger than the dictionaries of textual passwords to which a high percentage of passwords typically belong.

Throughout this paper we focus on graphical passwords that are exactly repeatable by the user. This distinguishes our work from all works on graphical pattern recognition of which we are aware (see Section 4), where it suffices for the device to recognize an input as being ``sufficiently similar'' to--but not necessarily the same as--a previously stored input. Because pattern recognition schemes require the storage of (some representation of) the plaintext password on the device, the password is vulnerable to an attacker who captures and probes the device. In contrast, because graphical passwords are repeatable, our schemes can derive a secret key, e.g., to encrypt and decrypt files, without need to store the password on the device. This protects both the password and the encrypted content from the attacker if the device falls into the attacker's hands.

The rest of this paper is outlined as follows: In Section 2, we present textual passwords with graphical assistance. In Section 3, we proceed to purely graphical passwords with a scheme called ``draw-a-secret'' (DAS). Section 3.2 shows our design and implementation of a memo pad encryption scheme based on DAS. Section 3.3 proposes novel ways to analyze and estimate the security of DAS and graphical passwords in general. In Section 4 we overview other password schemes, unrelated to graphical passwords, but putting our work in a larger context. Finally, Section 5 concludes.