Jeremiah Blocki successfully defended his PhD thesis today at Carnegie Mellon University. Jeremiah’s thesis is titled “Usable Human Authentication: A Quantitative Treatment”. Jeremiah is co-advised by Manuel Blum and I. His thesis committee also included Luis von Ahn (CMU) and Ron Rivest (MIT).
Here is a slightly expanded version of the abstract of this exciting thesis. I am including pointers to the research publications that report on these results as well as popular press articles written for a broader audience.
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 and 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. 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.).
First, we introduce Naturally Rehearsing Passwords 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. The constructions and security analysis are based on new techniques for combinatorial design (see also Beidemen and Blocki and, for comparison, Nisan and Wigderson).
Second, we introduce Human Computable Passwords 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 100 10-digit passwords of a user cannot compute any other passwords except with very low probability. The security analysis is based on new statistical dimension lower bounds (building on recent results of Feldman et al).
Third, we also show that user models and security models can be used to develop server-side defenses that a company could adopt to protect the passwords of its users against online (see Optimizing Password Composition Policies paper) and offline attacks (see the GOTCHA paper).
In the news:
Naturally Rehearsing Passwords:
- Carnegie Mellon Scheme Uses Shared Visual Cues To Help People Remember Multiple Passwords, CMU News Release, December 2013.
- Memory Trick Increases Password Security, Scientific American, December 2013.
- Story time: Researchers picture way better password memory scheme, Network World, December 2013.
- “Naturally rehearsing passwords” touted as better system for secure access, Slashdot, December 2013.
- Bill Gates swallowing a bicycle is the key to a novel password system, ZDnet, December 2013.
GOTCHA Password Hackers:
- First there were CAPTCHAs, now there are GOTCHAs, Ars Technica, February 2014.
- Carnegie Mellon Researchers Use Inkblots To Improve Security of Online Passwords, CMU News Release, November 2013.
- Researchers dare AI experts to crack new GOTCHA password scheme, Network World, November 2013.
- Researchers dare AI experts to crack new GOTCHA password scheme, Slashdot, November 2013.
- Inkblot, the new fool-proof password system, The Times of India, November 2013.
- Now, ‘inkblot’ passwords for unbreakable security, The Economic Times, November 2013.
- Researchers use inkblots to make safer passwords, The Tartan, November 2013.
- Will GOTCHAs Replace CAPTCHAs?, MIT Technology Review, October 2013.