Improving usability through password-corrective hashing

We propose a way to increase the usability of password authentication systems by compensating for transposition and substitution errors. We show how to correct for these errors with low false positive rates (i.e., low probability that an arbitrary string will be accepted as the password for authentication). Thus our techniques increase usability with provably little loss of security. In particular, we propose applying a single password-corrective hash function to each entered password attempt. The key property of the hash function is that two strings differing by a single data entry error be likely to be hashed to the same key, while more substantially differing strings are hashed to different keys. We develop precise analytical formulae for the precision/recall tradeoffs for a variety of corrective hash functions. We evaluate these methods at parameter values reflecting common classes of keys/passwords. Finally, we evaluate these schemes using a popular crack-list (dictionary) of 680,000 common words. We show that we can correct for all user transposition errors while reducing the computational cost of a crack attack by only 13%.