Encryption Algorithms with an error code for wrong password

I am looking for an encryption algorithm that would allow me to know if the password supplied is the correct one or not.

This question can be considered as a follow-up for Q. In particular the answer from bethlakshmi:

When you want the server to use the key, I'm guessing the process is this:

1. user gives the system his password
2. system checks the password, hashing it - and it's good.
3. system takes the password (not the hash!) and the salt and computes the encryption key
4. system takes encryption key and decrypts AES Key

I would like to do the steps 3 and 4 and forget about the 1 and 2. So, I don't want to store the hash of the password (or password+salt), so I don't want to check the password for correctness as in steps 1 and 2.

Proposal: I would like to compute the encryption key and try to decrypt the AES Key. One way would be that the AES key once decrypted with a valid password then can really allow authentication or... and in case invalid would make the authentication fail.

2. Back to the real question: Is there an encryption method (by this I mean the encryption method used to encrypt the AES key) that would return some error code if the password supplied is incorrect?
-
OK, so I need some clarification - how are you using the AES key for authentication. I can't quite get my head around what you are trying to do there and how a symmetric key is involved. – bethlakshmi Jul 15 '11 at 15:15

A good way to do this is to append a checksum to the message before encrypting (so you encrypt both the message and its checksum). Now if the user enters a password, you can try decrypting it and see if the resulting decrypted data has a valid checksum. If the checksum is invalid, the user entered their password incorrectly.

Your proposal has weaker security. Your proposal involves storing Hash(password) in the clear. That's bad, because it becomes vulnerable to precomputation attacks and time-space tradeoff attacks (e.g., the infamous "rainbow tables" -- a specific kind of time-space tradeoff, albeit one distinguished more by the colorful name than by the importance of that particular algorithm). The solution I describe above does not have this problem.

Cautions: Be warned that deriving the key from a password or passphrase is inherently weak, because users rarely choose passwords or passphrases with enough entropy. (Passwords are absolutely terrible. Passphrases are a bit better, but still tend to be too weak to resist serious attack.) If security is important, it would be best to avoid deriving the key from a password or passphrase. However, if you must use password-based key derivation, I encourage you to use a slow function for deriving the key from the password (e.g., bcrypt, PBKDF2), to slow down dictionary attacks. Also, don't forget to apply a message authentication code to the encrypted data.

-
very clear answer thanks!!! – smiley Jul 15 '11 at 17:19
This solution will not always work as prescribed: if you use padding with RSA like you should, you won't be able to even decrypt the plaintext and MAC to check it if the MAC is wrong. The decryption function will return an error. It does little harm to add the MAC, only adds inefficiency, but you don't need it. Padded RSA (RSA OAEP) has built in error checking as I mentioned in my answer. – PulpSpy Jul 17 '11 at 12:22
I am assuming the AES key is encrypted with public key encryption, which is never specified in the question (except maybe implicitly contradicted by step 4 which I assume should say decryption key). Anyways, the idea of an AES key encrypted under AES with another AES key seems too obviously redundant that I must charitably assume they don't mean that. – PulpSpy Jul 17 '11 at 12:38
The question specifies that the decryption key is computed from a password. This makes me think (though it certainly does not prove) that the decryption is symmetric-key decryption rather than public-key decryption. I hope that @smiley will clarify if I have misunderstood. – D.W. Jul 18 '11 at 1:50
correct D.W. it is symmetric encryption. Pushing an asymmetric in here adds complexity without a lot of benefit – smiley Jul 18 '11 at 4:50

[Your question is a little bit unclear to me, but I'll try to do a good job]

OK. From 3&4 I can see that the strength of your key simply depends on the strength of the password and the salt.

Your proposal isn't bad but it is definitely not a good practice. Reason is simple: Consider a case in which the wrong password is entered. How will you find out this is the wrong password? It will just throw gibberish and you can't find out if it is the original plaintext.

But, there are 2 ways to get around this to a certain extent. a)Store the hash of the original message and compare it to the hash of the decrypted message. If there is a mismatch, then the password is wrong. This can be in-effective in the light of rainbow-tables. But, salting along with one-way hashing funcitons can help you get around the problem posed by rainbow table.

b) In case you want to avoid hashing as given in 'a', then use a pre-defined set of characters as header and footer. Your code must be able to look for this pattern at the correct location once it is decrypted. So if this fails, then the password is wrong.

Encryption algorithms throw no error message. Your code can be modified to introduce an error message if you need one.

-
meanwhile I have found this ietf.org/rfc/rfc2898.txt which seems to be doing what I need – smiley Jul 15 '11 at 12:04
@Andrew, storing a hash of the original message in cleartext is a security weakness. It enables attackers to mount dictionary-search attacks on the message, if the message has low entropy. My suggestion avoids this flaw. Appending a hash before encrypting avoids flaw is safe, but is equivalent to my proposal. – D.W. Jul 19 '11 at 19:36
@D.W. I believe you can use hashing functions which have one-way property. This makes the rainbow tables useless. SHA-256 and above provide security against this if I'm right – Andrew Anderson Jul 20 '11 at 10:58
@Andrew, no, that is not correct. – D.W. Jul 20 '11 at 16:44
@D.W. which part ? The part where I say hashing functions with one way property can make rainbow tables obsolete or the part where I say that I think SHA-256 and above has that feature – Andrew Anderson Jul 21 '11 at 4:40