On predictive models and user-drawn graphical passwords

ABSTRACT

In commonplace text-based password schemes, users typically choose passwords that are easy to recall, exhibit patterns, and are thus vulnerable to brute-force dictionary attacks. This leads us to ask whether other types of passwords (e.g., graphical) are also vulnerable to dictionary attack because of users tending to choose memorable passwords. We suggest a method to predict and model a number of such classes for systems where passwords are created solely from a user's memory. We hypothesize that these classes define weak password subspaces suitable for an attack dictionary. For user-drawn graphical passwords, we apply this method with cognitive studies on visual recall. These cognitive studies motivate us to define a set of password complexity factors (e.g., reflective symmetry and stroke count), which define a set of classes. To better understand the size of these classes and, thus, how weak the password subspaces they define might be, we use the “Draw-A-Secret” (DAS) graphical password scheme of Jermyn et al. [1999] as an example. We analyze the size of these classes for DAS under convenient parameter choices and show that they can be combined to define apparently popular subspaces that have bit sizes ranging from 31 to 41—a surprisingly small proportion of the full password space (58 bits). Our results quantitatively support suggestions that user-drawn graphical password systems employ measures, such as graphical password rules or guidelines and proactive password checking.

REFERENCES

• 1: Attneave, F. 1955. Symmetry, information and memory for patterns. American Journal of Psychology 68, 209--222.
• 2: Attneave, F. 1957. Physical determinants of the judged complexity of shapes. Journal of Experimental Psychology 53, 4, 221--227.
• 3: Birget, J. C., Hong, D., and Memon, N. 2003. Graphical passwords based on robust discretization. IEEE Transactions on Information Forensics and Security 1, 3 (Sept.), 395--399. Cryptology ePrint Archive, Report 2003/168. http://eprint.iacr.org/, site accessed Jan. 12, 2004.
• 4: Blonder, G. 1996. Graphical passwords. United States Patent 5559961.
• 5: Bower, G. H., Karlin, M. B., and Dueck, A. 1975. Comprehension and memory for pictures. Memory and Cognition 3, 216--220.
• 6: Calkins, M. 1898. Short studies in memory and association from the wellesley college laboratory. Psychological Review 5, 451--462.
• 7: Joan Daemen , René Govaerts , Joos Vandewalle, Weak keys for IDEA, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.224-231, January 1994, Santa Barbara, California, United States
• 8: Darren Davis , Fabian Monrose , Michael K. Reiter, On user choice in graphical password schemes, Proceedings of the 13th conference on USENIX Security Symposium, p.11-11, August 09-13, 2004, San Diego, CA
• 9: Rachna Dhamija , Adrian Perrig, Déjà Vu: a user study using images for authentication, Proceedings of the 9th conference on USENIX Security Symposium, p.4-4, August 14-17, 2000, Denver, Colorado
• 10: French, R.-S. 1954. Identification of dot patterns from memory as a function of complexity. Journal of Experimental Psychology 47, 22--26.
• 11: Joseph Goldberg , Jennifer Hagman , Vibha Sazawal, Doodling our way to better authentication, CHI '02 extended abstracts on Human factors in computing systems, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/506443.506639]
• 12: J. Alex Halderman , Brent Waters , Edward W. Felten, A convenient method for securely managing passwords, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060815]
• 13: Ichikawa, S.-I. 1982. Measurement of visual memory span by means of the recall of dot-in-matrix patterns. Behavior Research Methods and Instrumentation 14, 3, 309--313.
• 14: Jansen, W., Gavrilla, S., Korolev, V., Ayers, R., and R., S. 2003. Picture password: A visual login technique for mobile devices. NIST Report - NISTIR7030.
• 15: Ian Jermyn , Alain Mayer , Fabian Monrose , Michael K. Reiter , Aviel D. Rubin, The design and analysis of graphical passwords, Proceedings of the 8th conference on USENIX Security Symposium, p.1-1, August 23-26, 1999, Washington, D.C.
• 16: Kirkpatrick, E. A. 1894. An experimental study of memory. Psychological Review 1, 602--609.
• 17: Klein, D. 1990. Foiling the cracker: A survey of, and improvements to, password security. In The 2nd USENIX Security Workshop. 5--14.
• 18: Cynthia Kuo , Sasha Romanosky , Lorrie Faith Cranor, Human selection of mnemonic phrase-based passwords, Proceedings of the second symposium on Usable privacy and security, July 12-14, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143120.1143129]
• 19: Madigan, S. 1983. Picture Memory. In Imagery, Memory and Cognition, J. C. Yuille, Ed. Lawrence Erlbaum, Mahwah, NJ. 65--89.
• 20: Madigan, S. and Lawrence, V. 1980. Factors affecting item recovery and hypermnesia in free recall. American Journal of Psychology 93, 489--504.
• 21: Massey, J. 1994. Guessing and entropy. In ISIT: Proceedings IEEE International Symposium on Information Theory. 204.
• 22: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 23: Newman Fabian Monrose , Zvi M. Kedem, Towards stronger user authentication, New York University, New York, NY, 1999
• 24: Monrose, F. and Reiter, M. K. 2005. Graphical passwords. In Security and Usability, L. Cranor and S. Garfinkel, Eds. O'Reilly Media Inc., Sebastopol, CA, Chapter 9, 147--164.
• 25: Muffett, A. 2004. Crack password cracker. http://ciac.llnl.gov/ciac/ToolsUnixAuth.html, site accessed Jan. 12, 2004.
• 26: Junko Nakajima , Mitsuru Matsui, Performance Analysis and Parallel Implementation of Dedicated Hash Functions, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.165-180, May 02, 2002
• 27: Nali, D. and Thorpe, J. 2004. Analyzing User Choice in Graphical Passwords. Tech. Report TR-04-01, School of Computer Science, Carleton University, Canada, http://www.scs.carleton.ca/research/tech_reports/2004/TR-04-01.pdf.
• 28: Openwall Project. 2004a. John the Ripper password cracker. http://www.openwall.com/john/, site accessed Jan.7, 2004.
• 29: Openwall Project. 2004b. Wordlists. http://www.openwall.com/passwords/wordlists/, site accessed Jan.7 2004.
• 30: Perkins, F. 1932. Symmetry in visual recall. American Journal of Psychology 44, 473--490.
• 31: Perrig, A. and Song, D. 1999. Hash visualization: A new technique to improve real-world security. In International Workshop on Cryptographic Techniques and E-Commerce. 131--138.
• 32: Benny Pinkas , Tomas Sander, Securing passwords against dictionary attacks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586133]
• 33: Niels Provos , David Mazières, A future-adaptive password scheme, Proceedings of the annual conference on USENIX Annual Technical Conference, p.32-32, June 06-11, 1999, Monterey, California
• 34: Real User Corporation. 2004. About passfaces. http://www.realuser.com/cgi-bin/ru.exe/_/ homepages/technology/passface.htm, site accessed May 25, 2004.
• 35: Shannon, C. 1948. A mathematical theory of communication. The Bell System Technical Journal 27, 379--423.
• 36: E. H. Spafford, Crisis and aftermath, Communications of the ACM, v.32 n.6, p.678-687, June 1989 [doi>10.1145/63526.63527]
• 37: Eugene H. Spafford, OPUS: preventing weak password choices, Computers and Security, v.11 n.3, p.273-278, May 1992 [doi>10.1016/0167-4048(92)90207-8]
• 38: Xiaoyuan Suo , Ying Zhu , G. Scott. Owen, Graphical Passwords: A Survey, Proceedings of the 21st Annual Computer Security Applications Conference, p.463-472, December 05-09, 2005 [doi>10.1109/CSAC.2005.27]
• 39: Tao, H. 2006. Pass-Go, a New Graphical Password Scheme. M.S. thesis, School of Information Technology and Engineering, University of Ottawa, Canada.
• 40: Julie Thorpe , P. C. van Oorschot, Graphical dictionaries and the memorable space of graphical passwords, Proceedings of the 13th conference on USENIX Security Symposium, p.10-10, August 09-13, 2004, San Diego, CA
• 41: Julie Thorpe , P. C. van Oorschot, Towards Secure Design Choices for Implementing Graphical Passwords, Proceedings of the 20th Annual Computer Security Applications Conference, p.50-60, December 06-10, 2004 [doi>10.1109/CSAC.2004.44]
• 42: Thorpe, J. and van Oorschot, P. 2005. On the Security of Graphical Password Schemes (Extended Version). Tech. Report TR-05-11, School of Computer Science, Carleton University, Canada, http://www.scs.carleton.ca/research/tech_reports/2005/download/TR-05-11.pdf.
• 43: Tyler, C. 1996. Human symmetry perception. In Human Symmetry Perception and Its Computational Analysis, C. Tyler, Ed. VSP, The Netherlands. 3--22.
• 44: Paul C. Van Oorschot , Stuart Stubblebine, On countering online dictionary attacks with login histories and humans-in-the-loop, ACM Transactions on Information and System Security (TISSEC), v.9 n.3, p.235-258, August 2006 [doi>10.1145/1178618.1178619]
• 45: Vogel, E. K. and Machizawa, M. G. 2004. Neural activity predicts individual differences in visual working memory capacity. Nature (London) 428, 748--751.
• 46: Wagemans, J. 1996. Detection of Visual Symmetries. In Human Symmetry Perception and its Computational Analysis, C. Tyler, Ed. VSP, The Netherlands, 25--48.
• 47: Susan Wiedenbeck , Jim Waters , Jean-Camille Birget , Alex Brodskiy , Nasir Memon, PassPoints: design and longitudinal evaluation of a graphical password system, International Journal of Human-Computer Studies, v.63 n.1-2, p.102-127, July 2005 [doi>10.1016/j.ijhcs.2005.04.010]
• 48: Jianxin Jeff Yan, A note on proactive password checking, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico [doi>10.1145/508171.508194]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems

General Terms:
Human Factors, Security

Keywords:
Draw-a-Secret, Graphical passwords, dictionary attack, graphical dictionary, memorable passwords, modeling user choice, password complexity factors