Cryptology ePrint Archive: Report 2017/810

The TypTop System: Personalized Typo-Tolerant Password Checking

Rahul Chatterjee and Joanne Woodage and Yuval Pnueli and Anusha Chowdhury and Thomas Ristenpart

Abstract: Password checking systems traditionally allow login only if the correct password is submitted. Recent work on typo-tolerant password checking suggests that usability can be improved, with negligible security loss, by allowing a small number of typographical errors. Existing systems, however, can only correct a handful of errors, such as accidentally leaving caps lock on or incorrect capitalization of the first letter in a password. This leaves out numerous kinds of typos made by users, such as transposition errors, substitutions, or capitalization errors elsewhere in a password. Some users therefore receive no benefit from existing typo-tolerance mechanisms.

We introduce personalized typo-tolerant password checking. In our approach, the authentication system learns over time the typos made by a specific user. In experiments using Mechanical Turk, we show that 45% of users would benefit from personalization. We therefore design a system, called TypTop, that securely implements personalized typo-tolerance. Underlying TypTop is a new stateful password-based encryption scheme that can be used to store recent failed login attempts. Our formal analysis shows that security in the face of an attacker that obtains the state of the system reduces to the difficulty of a brute-force dictionary attack against the real password. We implement TypTop for Linux and Mac OS login and report on a proof-of-concept deployment.

Category / Keywords: applications / Password, typo-tolerant password

Original Publication (with minor differences): ACM Conference on Computer and Communications Security (CCS)
DOI:
10.1145/3133956.3134000

Date: received 29 Aug 2017, last revised 23 Oct 2017

Contact author: rahul at cs cornell edu

Available format(s): PDF | BibTeX Citation

Note: This is the full version of the paper going to appear in ACM CCS 2017.

There was a bug in the analysis of the previous version in Appendix A.5: Online security which also affects our claims in the conclusion. In this version, we fixed the bug, updated the version with new results, and an appropriate conclusion.

Version: 20171023:162639 (All versions of this report)

Short URL: ia.cr/2017/810

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]