Q:

Password-based encryption with small typos allowed

I'm trying to write some software to encrypt and decrypt some messages with a password.  I am trying to implement it using this post:  How can I securely convert a "string" password to a key used in AES?
Now, I also want to devise a scheme to allow the user to make small typos when typing in the password, but still be able to decrypt the message even with that small typo.
Is there a way to do this without sacrificing the security of the encryption scheme?

A:

A possible solution:
When encrypting, ask the user to enter a password $p$. Produce a salt $s$. Enumerate the password with all tolerable typos to get array $a$. For each $a_i$, calculate $b_i=hash(a_i)$ to get array $b$. In the output file, write the salt. Generate a random key $k$. And for each $b_i$, write the pair $(hash(b_i||s),b_i\oplus k)$. Write the file to encrypt encrypted with key $k$.
When decrypting, ask user for a password $p_1$. Let $c$ be $hash(p_1)$. If $hash(c||s)$ matches any of $hash(b_i||s)$ in the encrypted file, the key is $k=c\oplus (b_i\oplus k)$. Decrypt the rest of the encrypted file with key $k$.
And you can reduce work when encrypting, but increase work when decrypting by letting array $b$ only contain little or no typos. (If your standard of tolerable typos is having 2 or fewer characters wrong, let $b$ be the array of the password with only 1 character wrong, or let $b$ only contain $p$.) When decrypting, enumerate $p_1$ with typos. If the hash of any of them matches any of $hash(b_i||s)$, it is the right password.

