How to check for a key *and* store encrypted data?

Question

I wish to create a system wherein I store encrypted data.

Users can access this data if they have the key. If they give a wrong key, they don't get access at all. If they give the right key, they get the data, and they may modify that data.

One idea I came up with is to store the bcrypt of the key, a salt, and AES-encrypted data using a PBKDF2 with the salt, and a high iteration number.

Getting the data would follow this process:

1. Get the key from the user.
2. Get the bcrypt of that key.
3. If the bcrypt doesn't match, deny access.
4. Get the PBKDF2 of the key with the salt.
5. Use that PBKDF2 to decrypt the data.
6. Give the data to the user through a secure channel (beyond this design).

The system should make it hard to get the data, even if you have access to the raw, encrypted, data.

My design seems to achieve that goal, but I have differential cryptanalysis concerns around the fact that the key is both encrypted with bcrypt and with a PBKDF2 encrypting AES. Could cross-referencing the bcrypt and the raw, AES-encrypted data make it easier to break the key? Are there known issues with this kind of designs?

Is there a simpler way?

Obviously I can't get rid of the bcrypt part, because any key would decrypt the AES data (although the result would be gibberish). I can't use bcrypt as the key for AES, because the key would be stored along with the encrypted data, which defeats the purpose of encrypting.

Answer 1

Why don't you use Authenticated Encryption? If user gives right key, encryption succeeds and you can return data to the user. If key is wrong, encryption fails and you won't give the data.

Look at solution used in TrueCrypt. User's password is stored nowhere in encrypted container. It is verified by decrypting of TC volume header and verifying some data after decryption. More details here: Encryption Scheme

Solution used in TrueCrypt is not an Authentication Encryption, but it shows well that you don't have to store user key/password to know if password entered is correct.