The Graphical Passwords Project  
Funded by the NSF CyberTrust Program

Co-PIs:  J.C. Birget (Rutgers-Camden), D. Hong (Rutgers-Camden), N. Memon (Brooklyn Polytechnic), S. Man (SW Minn. State), S. Wiedenbeck (Drexel).

Computer security depends largely on passwords in order to authenticate human users. The main drawback of passwords is what we call  the password problem, namely the fact that passwords are expected to comply with two conflicting requirements:
(1) Passwords should be easy to remember, and the user authentication protocol should be executable quickly and easily by humans.
(2) Passwords should be secure, i.e., they should look random and should be hard to guess; they should be changed frequently, and should be
different on different accounts of the same user. They should not be written down or stored in plain text.
   
Classical studies have shown that, human users tend to choose and handle alphanumeric passwords very insecurely: [R. Morris, K. Thompson, ``Password security: a case history'', Communications of the ACM 22 (1979) 594-597], [D.C. Feldmeier, P.R. Karn, ``UNIX Password security - ten years later'', Advances in Cryptology - CRYPTO'89, LNCS 435, Springer (1990) 44-63], [D. Klein, ``A survey of, and improvements to, password security'',  UNIX Security Workshop II, Berkeley, Calif., Usenix Association (1990)]; see also  [A. Menezes, P. van Oorschot, S. Vanstone, Handbook of applied cryptography, CRC Press (1997), Sections 10.2, 10.6], [R.E. Smith, Authentication: from passwords to public keys, Addison-Wesley (2002),  Chap. 2 and Notes to Chap. 2], [B. Ives, K. Walsh, H. Schneider, ``The domino effect of password reuse'', Communications of the ACM 47(4) (2004) 76-78]. 

Graphical passwords may be a solution to the password problem. The idea of graphical passwords, first described by Greg Blonder [G. Blonder, Graphical Passwords, United States Patent 5559961 (1996)], is to let the user click (with a mouse or a stylus) on a few chosen regions in an image that appears on the screen. To log in, the user has to click in the same regions again. The literature contains several papers on the subject: [I. Jermyn, A. Mayer, F. Monrose, M. Reiter, A. Rubin, ``The design and analysis of graphical passwords'',  8th Usenix Security Symposium (1998)],  [A. Perrig, D. Song, ``Hash visualization: A new technique to improve real-world security'', International Workshop on Cryptographic Techniques and E-Commerce (1998) 131-138], [``The science behind Passfaces'', Real User Corporation (Sept. 2001). http://www.realuser.com], [M. Boroditsky, ``Passlogix password schemes''. http://www.passlogix.com],  [R. Dhamija, A. Perrig, ``Deja Vu: User study using images for authentication'', 9th Usenix Security Symposium (2000)].  More recent references:  [J. Thorpe, P. van Oorschot, ``Graphical dictionaries and the memory space of graphical passwords'', 13th Usenix Security Symposium (2004) 135-150], [D. Davis, F. Monrose, M. Reiter, ``On user choice in graphical password schemes'', 13th Usenix Security Symposium (2004) 151-164], [J. Thorpe, P. van Oorschot, ``Towards Secure Design Choices for Implementing Graphical Passwords'',  20th Annual Computer Security Applications Conference (2004 ACSAC), Dec. 6-10, 2004, Tucson, Arizona], [V. Roth, K. Richter, R. Freidinger, ``A PIN-entry method resilient against shoulder surfing'',  11th ACM Conf. on Computer and Communication Security (2004) 236-245].

In Blonder-style graphical passwords, only pre-processed images can be used; the click regions can only be chosen from certain  pre-designed regions in the image. This implies that the users cannot provide images of their own for making passwords, and users cannot choose click places that are not among the preselected ones. Our design allows the use of any images (including the users own images, digital photos of landscapes, paintings, etc.).  Moreover, we let users choose any places that attract them as click regions; such places are easier to remember. However, allowing arbitrary click locations leads to a stability problem, which we had to overcome. The problem is that we cannot expect users to click always on exactly the same location (when they intend to). So we discretize the image, by using a square grid. But that leads to border problems: If the chosen click location is near the edge of a grid-square, the user will sometimes click in one square, sometimes in a neighboring square. We devised a multi-grid method, which we call  robust discretization, and which leads to a stable output for the user's clicking actions. An approximation parameter r is used; as long as the user clicks within distance r of the originally chosen click location, the output of the clicking will be the same (e.g., r = 2 mm).  It is important to have stable output, because the output of the discretized clicking will undergo a secure hash (``password encryption'');  for security reasons, we do not store the actual graphical password in the computer, just the hash value.  So, the system does not know the graphical password explicitly, and hence cannot check whether a user's clicks are ``approximately correct''. The hashing of passwords leads to the requirement that the user's clicks at login must always be in the same multi-grid squares; hence, we need a robust discretization.
More details on how robust discretization works can be found in the following paper, which gives detailed descriptions of a graphical passwords system: 

     J.C. Birget, Dawei Hong, Nasir Memon, ``Robust discretization, with an application to graphical passwords'', Aug. 2003 (Cryptology ePrint archive, http://eprint.iacr.org/2003/168 ; there is a slightly revised version, in pdf or ps ). Journal version: ``Graphical passwords based on robust discretization'', IEEE Transactions on Information Forensics and Security,  1(3) (Sept. 2006) 395-399.

We have implemented the graphical password system described in the above paper; the implemented version is called PassPoints.  For passwords, human aspects (usability of the system, learnability and long-term memorability of the passwords, avoidance of unsafe practices, and user satisfaction) are of crucial importance.  The following studies focus on human factors in the graphical passwords system PassPoints:

     S. Wiedenbeck, J. Waters, J.C. Birget, A. Brodskiy, N. Memon, ``PassPoints: Design and longitudinal evaluation of a graphical password system'',  International J. of Human-Computer Studies (Special Issue on HCI Research in Privacy and Security), 63 (2005) 102-127. ( pdf )
 
     S. Wiedenbeck, J. Waters, J.C. Birget, A. Brodskiy, N. Memon,  ``Authentication using graphical passwords: Effects of tolerance and image choice'',  Symposium on Usable Privacy and Security (SOUPS),  6-8 July 2005, at Carnegie-Mellon Univ., Pittsburgh.  (  pdf   )

     S. Wiedenbeck, J. Waters, J.C. Birget, A. Brodskiy, N. Memon,  ``Authentication using graphical passwords: Basic results'', Human-Computer Interaction International (HCII 2005), Las Vegas, July 25-27, 2005. ( pdf )

A method for a dictionary attack against the PassPoints graphical passwords system is described in

     A. E.  Dirik,  N. Memon, J.C. Birget, ``Modeling user choice in the PassPoints graphical password scheme'',  Symposium on Usable Privacy and Security (SOUPS), July 2007, at Carnegie-Mellon Univ., Pittsburgh.  (  pdf   )



Shoulder-surfing: Graphical passwords, and alphanumeric passwords as well, are vulnerable to shoulder surfing (e.g., when an attacker directly watches a user during login, or when a security camera films a user, or when an electromagnetic pulse scanner monitors the keyboard or the mouse, or when trojan login screens capture passwords, etc.). The paper below outlines some graphical password schemes that are resistant to shoulder surfing:

     Leonardo Sobrado, J.C. Birget, ``Graphical passwords'', The Rutgers Scholar, vol. 4 (2002), http://RutgersScholar.rutgers.edu/volume04 .

Human factors testing of this scheme appears in

    S. Wiedenbeck, J. Waters, L. Sobrado, J.C. Birget, ``Design and evaluation of a shoulder-surfing resistant graphical password scheme'', in Proceedings of Advanced Visual Interfaces (AVI2006), Venice, Italy, 23-26 May 2006. ( pdf )

A variety of other shoulder-surfing resistant password schemes are described in the following papers:

     S. Man, D. Hong, M. Matthews, ``A shoulder-surfing resistant graphical password scheme - WIW'', Proc. Int. Conf. on Security and Management, Las Vegas, 2003, pp. 105-111. ( pdf )

     S. Man, D. Hong, B. Hayes, M. Matthews, ``A  password scheme strongly resistant to spyware'',  Proc. Int. Conf. on Security and Management, Las Vegas, 2004, pp. 94-100. ( pdf )

     S. Man, D. Hong, M. Matthews, J.C. Birget,  ``A shoulder-surfing resistant graphical password scheme'', (March 2005).  ( pdf ).

____________________
J.C. Birget, Dec. 2007