tPAKE: Typo-Tolerant Password-Authenticated Key Exchange

摘要

Password-authenticated key exchange (PAKE) enables a user to authenticate to a server by proving the knowledge of the password without actually revealing their password to the server. PAKE protects user passwords from being revealed to an adversary who compromises the server (or a disgruntled employee). Existing PAKE protocols, however, do not allow even a small typographical mistake in the submitted password, such as accidentally adding a character at the beginning or at the end of the password. Logins are rejected for such password submissions; the user has to retype their password and reengage in the PAKE protocol with the server. Prior works have shown that users often make typographical mistakes while typing their passwords. Allowing users to log in with small typographical mistakes would improve the usability of passwords and help users log in faster. Towards this, we introduce tPAKE: a typo-tolerant PAKE, that allows users to authenticate (or exchange high-entropy keys) using a password while tolerating small typographical mistakes. tPAKEallows edit-distance-based errors, but only those that are frequently made by users. This benefits security, while still improving usability. We discuss the security considerations and challenges in designing tPAKE. We implement tPAKE and show that it is computationally feasible to be used in place of traditional PAKEs while providing improved usability. We also provide an extension to tPAKE, called adaptive-tPAKE, that will enable the server to allow a user to log in with their frequent mistakes (without ever learning those mistakes).