There is a considerable amount of prior work on authenticating users via graphical inputs to a device, particularly handwritten signatures (see, e.g., [14,13,21]). None of these works strive for exact repeatability by the user, and therefore, a model of the user's graphical input is stored on the device and used to ascertain whether a new input is sufficiently similar to the previously-stored one to grant access. This renders it essential to protect the device's (PDA's) storage from probes by an attacker. In contrast, repeatability is achieved in our schemes, thereby enabling designs in which the device, if captured, is of little help to the attacker (see Section 1).
The security of textual passwords has been examined by numerous researchers, notably [19,12,9,29,34]. Without exception, these studies reiterate the fact that people choose passwords that are easy to find by automated search. In order to improve the security of passwords, it is common practice for system administrators to invoke reactive password checkers to identify weak passwords [26,20], or to use proactive checkers to filter out certain classes of weak passwords when the user inputs her password for the first time [3,28].
A technique to improve the security of even a poorly chosen password is to salt the password by prepending it with a random number, R, before hashing [19,16]. The effect is that the search space of the attacker is increased by a factor of 2|R| if the attacker does not have access to the salts.
The techniques in this paper can be combined in natural ways with the techniques discussed above for strengthening textual passwords--i.e., proactive and reactive password checking, and salting--to improve the security of graphical passwords, as well.
More distantly related is work on one-time passwords (e.g., [11]). One-time password schemes are relevant primarily for network settings, to defend against the threat of a network eavesdropper capturing password information in transit between the user and a secure authentication server. To render such eavesdropping harmless, a one-time password scheme varies the user's password from each login to the next in a way that only the user and the server can predict, based on state shared between the server and user. In the main setting we consider, however, there is no network communication that is vulnerable to eavesdropping, and consequently the attacks with which we are concerned is the capture and analysis of all stored state relevant to authentication (the PDA in our setting, or equivalently the server's and client's states in the one-time password setting). One-time password schemes of which we are aware offer no benefit against this attacker over traditional password schemes.