Introduction

1 Introduction

In ubiquitous textual password schemes, users tend to choose passwords that are easy to remember - this often means passwords which have ``meaning" to the user. Unfortunately, these (likely chosen) passwords make up only an insignificant part of the full password space. Furthermore, an attacker may build an attack dictionary of ``likely passwords" (roughly equated with those easily remembered) from which to draw candidate guesses. In Klein's 1990 case study [13], 25% of 14 000 user passwords were found in a dictionary of only 3 × 10⁶ words. This suggests that a password scheme's security is linked more closely to the size of its memorable password space (for a reasonable definition of ``memorable"), than that of the full password space (e.g. for 8-character passwords of digits and mixed-case letters, about 2 × 10¹⁴).

Various psychological studies show that people have significantly better recall for concrete words than abstract words [12, 4]. We expect that passwords from the full password space -- such as ``x*t1K$h9" -- which have no meaning whatsoever, are even less likely to be recalled than abstract words; in general we would not expect users to choose such passwords. Given the success of dictionary attacks, it appears that the security of a text-based password scheme is related to the size of its memorable password space, much of which consists of character strings representing, or derived from, concrete words. Passphrases (passwords based on mnemonic phrases) are one credible solution; however, given the success of dictionary attacks, it seems they are seldom used.

Graphical password schemes (e.g. [11, 2, 6]) have been proposed as an alternative to text-based schemes. One motivation for graphical schemes is that humans have a remarkable capability to remember pictures. Psychological studies support that people recall pictures with higher probability than words, including concrete nouns [14]. This motivates password schemes requiring recall of a picture in lieu of a word. If the number of possible pictures is sufficiently large, and the diversity of picture-based passwords can be captured, it seems reasonable to believe the memorable password space of a graphical password scheme will exceed that of text-based schemes -- thus presumably offering better resistance to dictionary attacks. What remains to be shown is what sort of pictures people are likely to select as graphical passwords -- corresponding to what we call the memorable password space. We begin to explore this issue in the present paper.

We analyze the memorable password space (defined in §3), motivated by the questions: (1) How might an attacker build a graphical dictionary? (i.e. an attack dictionary against a graphical password scheme); and (2) How successful would a brute-force attack using such a dictionary be? As mentioned, the high success rate of brute-force dictionary attacks against textual passwords is believed to be strongly related to the recall capabilities of humans and how this affects password selection: meaningful and thus more easily remembered strings are frequently chosen as passwords. We suggest that a clever attacker would narrow down the password space, and prioritize guesses, to pictures that people are likely to choose as passwords, based on the images they are most likely to recall.

To search for techniques that an attacker might use in building a graphical dictionary, we consult psychological studies on visual memory. We review cognitive studies indicating the types of images people are most likely to recall (and presumably choose as passwords). A collection of studies [1, 7] supports the idea that people recall symmetric images better than asymmetric images. A particularly interesting observation is that mirror symmetry carries a special status in human perception [27]. This motivates us to focus on mirror symmetric graphical passwords. An attacker exploiting this property of mirror symmetry (most probably about a vertical or horizontal axis -- see §3) might build a graphical dictionary of the encoded representations of graphical passwords, such that each entry represents at least one mirror symmetric image. If such a dictionary, containing some fraction of all possible graphical passwords, allows successful attacks, then the security of graphical password schemes may be significantly less than e.g. if all passwords in the entire space were equi-probable.

We define a class of memorable graphical passwords in general, and specifically how this class would map to a graphical password scheme proposed in 1999 by Jermyn et al. called Draw-A-Secret (DAS) [11]. We chose to analyze the memorable password space of DAS to determine whether these passwords constitute a sufficiently large password space for adequate security. For clarity, we will refer to the length of a textual password as the t-length, and the length of a DAS graphical password as length (see §4.1). We wish to determine a password-length parameter for DAS such that dictionary attacks are more costly than for text-based schemes, given a fixed t-length. This gives the former a chance to be a more secure alternative. We consider the required graphical password length (see §4.1), so that the mirror symmetric graphical password space outsizes the corresponding space of memorable textual passwords.

We define three subsets of our class of memorable passwords (graphical dictionaries) that we believe would form a basic probability-based ordering of a DAS graphical dictionary. In our analysis of the memorable password space, we found that for DAS passwords of length less than or equal to 8 on a 5 × 5 grid, even our smallest graphical dictionary (§4.4), which is a subset of what we call memorable graphical passwords, is larger in size than the larger textual password dictionaries of 40 million entries [19] (intended for use with password crackers such as John the Ripper [18]). This implies that DAS passwords of length 8 or larger on a 5 × 5 grid may be less susceptible to dictionary attack than textual passwords.¹

Under reasonable assumptions and parameter choices, we show the time to exhaustively try all passwords in the full DAS space is approximately 540 years, in comparison to 6 days for one of our proposed symmetric graphical dictionaries. Thus, if as conjectured, a significant fraction of users choose mirror symmetric passwords, the security of the DAS scheme may be substantially lower than originally believed. However, this reduction in size can be compensated for by longer passwords: the size of the space of mirror symmetric passwords of length about L+5 exceeds that of the full password space for corresponding length L ≤ 14 on a 5 × 5 grid.

Our contributions include the definition of a class of memorable graphical passwords, the introduction of graphical dictionaries, an analysis of the memorable password space of the DAS scheme of Jermyn et al. [11], and progress towards understanding the subtleties of DAS. Although we focus our analysis on the DAS scheme, our work has general implications for all graphical passwords. This work could be used to help in formulating password rules for graphical password users and in creating proactive graphical password checkers.

The sequel is organized as follows. §2 briefly discusses related work. §3 presents a proposed class of memorable graphical passwords. §4 analyzes this class for the DAS scheme. §5 discusses additional observations and possible extensions to this work, including further concerns about the size of the DAS password space that might be used in practice. Concluding remarks are made in §6.