# 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?

• There's no trivial way although it may be possible using some error correcting code magic. – SEJPM Apr 1 '16 at 21:35
• This recent paper may help (though I haven't read it). – pscholl Apr 1 '16 at 22:00
• @pscholl I actually looked over that paper, however they seem to only be covering authentication – Iliketoproveit Apr 1 '16 at 22:45
• It's a pretty good paper, but I'm not 100% that it would be suitable for encryption schemes. Then again, "compatibility with existing password hash" could be an indication that it is possible. – Maarten Bodewes Apr 1 '16 at 23:10

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.