Computer Science Department
School of Computer Science, Carnegie Mellon University


Usable Human Authentication:
A Quantitative Treatment

Jeremiah Blocki

June 2014

Ph.D. Thesis


Keywords: Human Authentication, Passwords, Password Management Scheme, Usability Model, Security Model, Password Composition Policy, GOTCHA

A typical computer user today manages passwords for many different online accounts. Users struggle with this task–often forgetting their passwords or adopting insecure practices, such as using the same passwords for multiple accounts and selecting weak passwords. While there are many books, articles, papers and even comics about selecting strong individual passwords, there is very little work on password management schemes–systematic strategies to help users create and remember multiple passwords. Before we can design good password management schemes it is necessary to address a fundamental question: How can we quantify the usability or security of a password management scheme. One way to quantify the usability of a password management scheme would be to conduct user studies evaluating each user's success at remembering multiple passwords over an extended period of time. However, these user studies would necessarily be slow and expensive and would need to be repeated for each new password management scheme. Our thesis is that user models and security models can guide the development of password management schemes with analyzable usability and security properties.

We present several results in support of this thesis. First, we introduce Naturally Rehearsing Password schemes. Notably, our user model, which is based on research on human memory about spaced rehearsal, allows us to analyze the usability of this family of schemes while experimentally validating only the common user model underlying all of them. Second, we introduce Human Computable Password schemes, which leverage human capabilities for simple arithmetic operations. We provide constructions that make modest demands on users and we prove that these constructions provide strong security: an adversary who has seen about 100 10-digit passwords of a user cannot compute any other passwords except with very low probability. Our password management schemes are precisely specified and publishable: the security proofs hold even if the adversary knows the scheme and has extensive background knowledge about the user (hobbies, birthdate, etc.). They do not require any significant server-side changes. In further support of our thesis, we show that user models and security models can also be used to develop server-side defenses against online and offline attacks.

262 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by