Next Generation Password-Based Authentication Systems

Passwords, despite being the primary means for users to authenticate on the Web or to a computing device, are marred with several usability and security problems: users nowadays have too many accounts and passwords to remember; typing pass- words correctly can be cumbersome, particularly on touch screen devices. As a result, users often pick simple, easy-to-remember, and easy-to-type passwords and reuse them across different websites. Simple passwords, unfortunately, are also easy-to-guess. Reused passwords can put all of a user’s accounts at risk if any of them are compromised. In this dissertation, I show how to improve the state of passwords and password- based authentication (PBA) systems by incorporating knowledge of real-world password distributions. I identify three challenges faced by current passwords and PBA systems. Using a combination of empirical and analytical methods, I first dis- till out the details of those problems and then use that knowledge to guide building the next generation PBA systems that provide better usability and security. First, to help users deal with too many account passwords, I design NoCrack, a secure password vault system (also called password manager) that uses honey encryption to encrypt user passwords under a master password. Honey encryption provides NoCrack’s vault ciphertexts with a novel property: decryption with any incorrect master password will output decoy but plausible-looking sets of pass- words. Therefore, if an attacker tries to decrypt a NoCrack’s vault ciphertext with several guesses for the master password, the attacker does not immediately learn the correct master password even if it is included in the list of guesses. To learn which of the decrypted passwords are real, the attacker has to try them on- line, which can be relatively slow, potentially detectable by the websites for which the user has an account, and also subject to website rate-limiting for too many incorrect password submissions. Besides having too many passwords, users often make mistakes while typing passwords, and, in current settings, login is rejected if the entered password is not exactly what is used during registration. This is annoying and counter-productive for legitimate users. Via studies conducted on Amazon Mechanical Turk and with Dropbox’s production login infrastructure, I measured the extent that password typos cause a usability burden. I showed how to design PBA systems that can tolerate typos without degrading the security of passwords. Finally, due to billions of breached passwords and rampant password reuse habits, credential stuffing attacks have become a serious threat to password security: an attacker can compromise a user account by simply trying the password of that user stolen from other websites. To prevent such attacks, some third party web services have started providing APIs for checking if a user’s password is present in a leaked set of passwords. I give a framework to analyze the security requirements of such compromised credentials checking (C3) services. I go on to provide new C3 protocols that provide a better security/bandwidth trade-off