3
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ There's no trivial way although it may be possible using some error correcting code magic. $\endgroup$ – SEJPM♦ Apr 1 '16 at 21:35
  • 3
    $\begingroup$ This recent paper may help (though I haven't read it). $\endgroup$ – pscholl Apr 1 '16 at 22:00
  • 1
    $\begingroup$ @pscholl I actually looked over that paper, however they seem to only be covering authentication $\endgroup$ – Iliketoproveit Apr 1 '16 at 22:45
  • $\begingroup$ 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. $\endgroup$ – Maarten Bodewes♦ Apr 1 '16 at 23:10
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Would it also work to concatenate the list of tolerable typos and let the hash of that be the key? Then to decrypt you'd generate the same list from the input password and hash it in the same manner to get the key. $\endgroup$ – user9070 Apr 2 '16 at 16:05
  • 1
    $\begingroup$ Two issues with this scheme: no work factor for the hash, and you'd better make sure the typo's don't overlap or you'll leak the key. $\endgroup$ – Maarten Bodewes♦ Apr 3 '16 at 2:17
  • $\begingroup$ @MaartenBodwes What do you mean by "make sure the typo's don't overlap or you'll leak the key"? $\endgroup$ – v7d8dpo4 Apr 3 '16 at 5:31
  • $\begingroup$ I think the last paragraph is the most tenable idea. It means no slowdown in the case of correctly typed passwords, requires no extra storage and does not accelerate password cracking. However, the scheme should use standard password-hashing like bcrypt, scrypt, etc. rather than a simple salted hash. $\endgroup$ – otus Apr 4 '16 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.