[Crypto] Fuzzy password

Your user may mistype his/her password, skipping a character, adding a random character, etc. But you don't want to frustrate his/her with error message.

This is a simple idea of handling this.

First, read my blog post about fuzzy string matching and Levenshtein distance.

You may want to handle at least 3 types of typos in password: 1) one character skipped (at random position); 2) one random character is added at random position; 3) one random character is changed at random position.

When user sets a new password in your system, just enumerate all possible passwords with one character skipped, one random character added, etc. If there are ~96 printable characters which may be included in password, here is what we have.

For n-length password, this is: 1) one character skipped: n more possible passwords/hashes; 2) one character added: n*96 more hashes; 3) one character randomly modified: n*96 more hashes.

In total: 2*n*96 + n. For a 10-character password, that implies storing ~2000 hashes instead of one. For a 20-character password, this is ~4000 hashes instead of one. Doable, without any significant performance degradation, even if using memory-hard hashing functions like scrypt or Argon2.

But beware -- the whole level of security would be lower. Attacker would need to crack one hash of 2000 or 4000 hashes, instead of a single hash. Also, some information about password may leak in presence of that number of hashes (or may not). All this is risky. Also, password must be long enough to amortize password shortening.

To narrow down the number of all possible typos, remember that a mistyped character is often the one that is on adjacent key on keyboard.

(the post first published at 20221130.)

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.