The Graphical Passwords Project
Funded by the NSF CyberTrust Program
J. C. B i r g e t
D. H o n g
N. M e m o n (Brooklyn
S. M a n (SW Minn. State), and
W i e d e n b e c k (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'', NIX Security Workshop II,
Berkeley, Calif., Usenix Association (1990)]; see also [A.
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
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
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
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.
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
S. Wiedenbeck, J. Waters, J.C. Birget, A.
Memon, ``PassPoints: Design and longitudinal evaluation of a graphical
J. of Human-Computer Studies (Special Issue on HCI Research in
Privacy and Security), 63 (2005) 102-127. ( pdf
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
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),
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
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 ).
[2012-13: There is a Romanian translation of this page, by
a Polish translation by V. Aleksandrova
and a Czech translation by D. Milton
http://www.autoteilexxl.de/edu/?p=138 . ]
J.C. Birget, Dec. 2007