That's a nice feature.
It got me thinking - imagine wanting to let users log in with a single character typo in their password, could you do this without storing hashes of all edit distance 1 passwords?
It got me thinking - imagine wanting to let users log in with a single character typo in their password, could you do this without storing hashes of all edit distance 1 passwords?
Notation: "||" means string concatenation.
Let password P = P1 || P2, where len(P1) + len(P2) = len(P) and |len(P1) - len(P2)| <= 1.
Let H1 = hash(P1), H2 = hash(P2), where hash() is a cryptographic hash function that produces at least as many bits as the longest allowed password and satisfies whatever slowness and memory use requirements that you have for a password hash.
To store a password, store P ⊕ H1 and P ⊕ H2.
To check a password candidate C received at login, let C = C1 || C2 using the same splitting rule as used for P above, and compute C ⊕ hash(C1) and C ⊕ hash(C2).
A login is successful if either P ⊕ H1 or P ⊕ H2 is within edit distance 1 of either C ⊕ hash(C1) or C ⊕ hash(C2).
(I've omitted salt from the above for simplicity. Replace the hash with a salted hash if you want salt).