pASSWORD tYPOS and How to Correct Them Securely

We provide the first treatment of typo-tolerant password authentication for arbitrary user-selected passwords. Such a system, rather than simply rejecting a login attempt with an incorrect password, tries to correct common typographical errors on behalf of the user. Limited forms of typo-tolerance have been used in some industry settings, but to date there has been no analysis of the utility and security of such schemes.

What typos to correct?
We conducted password transcription experiment in Amazon Mechanical Turk to find out what typos users frequently make while typing passwords? Some of the frequent typos are easy to correct. E.g.,

capitalization errors (Password → password),
caps lock errors, (Password → pASSWORD),
adding an extraneous character at the end (Password → Password`).

Effect of typos on usability.
We measure the effect of correcting these typos in Dropbox production login infrastructure. The instrumentation at Dropbox did not record user passwords or otherwise change authentication policy, but recorded only the frequency of observed typos. Our experiments reveal that almost 10% of failed login attempts fail due to a handful of simple, easily correctable typos, such as capitalization errors. We show that correcting just a few of these typos would reduce login delays for a significant fraction of users as well as enable an additional 3% of users to achieve successful login.

Effect of auto-correcting typos on security.
Finally, we introduce a framework for reasoning about typo-tolerance, and investigate the seemingly inherent tension here between security and usability of passwords. We use our framework to show that there exist typo-tolerant authentication schemes that can get corrections for “free”: we prove they are as secure as schemes that always reject mistyped passwords. Building off this theory, we detail a variety of practical strategies for securely implementing typo-tolerance. By conducting simulation attack using password leaks, we found that change in security (which is the change in success rate of an attacker) due to typo tolerance is negligible. For example, in case of simulation with Myspace password leak, the success probability of the most powerful attacker in compromising a randomly chosen user account within 10 guesses increases from 0.79% (without allowing typos) to 0.81% (with allowing typos), which is essentially negligible compared to the benefit of allowing typos.

We are analyzing other potential typo correctors and relaxed password checkers that can correct more typos safely.

Paper Slides (.pptx) Slides (.pdf)

pASSWORD tYPOS FAQ

Why correct typos in passwords?

Correcting typos improves website useability. We all make typos, and password selection guidelines—even sound ones—don’t help the situation. Our experiments at Dropbox showed that over a 24-hour period, 3% of users failed to log in when they made typos that a simple typo correction scheme (with three correctors) would have corrected.
But isn't typo correction weakening security and giving an attacker “free guesses” at a user's password?

Intuitively, it may seem that typo-tolerance weakens security: A typo-tolerant system will accept multiple character strings as passwords for a given user, so it seems to be giving an attacker “free guesses." But the vast majority of those “free guesses” are character strings that don’t correspond to passwords people actually use. This is why, despite the intuition, typo correction actually has a small impact on security.
Just how small is the security impact of typo correction?

In most realistic settings, the impact on online security is quite small. The answer, however, depends on the parameters of the password system, such as the number of guesses an attacker can make before being locked out, and the way that user’s select and attackers guess passwords. As an example, though, in a system that allows ten guesses before lockout, with the level of correction used in the DropBox study (three “correctors”), and analysis using a public database of passwords (Myspace), we estimate that applying typo correction raises an attacker’s probability of successful online attack against a given user from 0.79% to 0.81%.
What about security against attackers that make guesses across a large number of distinct accounts?

Many attackers do mount "horizontal" attacks that try what the attacker thinks is the most popular password across many accounts, then the next most popular against those same accounts, etc. The success of such an attack is typically measured in the fraction of targeted accounts they will compromise. Our statistic above actually covers this case already: deploying typo-tolerance would increase this fraction of accounts compromised from 0.79% to 0.81%. Compared to the number of accounts compromised without typo tolerance, the increase due to allowing typos is quite small. Moreover, these are pessimistic numbers, and show the maximum possible success probability for any attacker. We expect real attackers, who does not know the exact distribution of passwords, would gain much smaller benefit due to typo-tolerance.
What about offline security?

Our approach has no impact on offline security, i.e., brute-force password cracking. Our scheme does not in any way change the format of stored passwords (which are salted and hashed in well-engineered systems, and in very well-engineered systems also hardened using a pseudorandom function service).
OK. So why aren’t websites already doing this today?

A few are, in a limited way. Facebook, for example, corrects capitalization errors. But our work suggests that many more websites should autocorrect password typos to improve their service.
How hard is it to implement your typo correction strategy in existing systems?

Our scheme involves no change to a password database. It builds on top of the basic password checking used in existing systems, which check that a submitted password exactly matches the one stored for a user. The idea behind our scheme is to try various “tweaks” to a submitted password to see if any results in an exact match. These “tweaks” correct typos.
How can “autocorrect” work if my password doesn't include dictionary words?

“Autocorrect” conveys the spirit but not the technical details of our approach, in which "correctors" do not involve a dictionary.