Can I determine if a user has the wrong symmetric encryption key? We're using the Objectivity/DB object database with a custom encryption plugin that encrypts serialized objects on disk. Encryption uses AES with a shared secret key held by all users. I would like to be able to provide some guidance to users if they enter the "wrong" shared encryption key (as in "I think you mistyped the encryption key. Please try again"). My first thought would be to use authenticated encryption to verify the decrypted data, but...

Because of constraints imposed by Objectivity/DB's storage manager, our encrypted data must be the same size as the unencrypted data, preventing us form using an authenticated encryption scheme. So, if the user supplies an incorrect shared key, the decrypted data is "gargabe", but is the right size and object references etc. point off to (often) segfault land. Thus, the user experience is a hard crash instead of a "oops, please retype your password". Not ideal.

Our current thinking is to store the HMAC of a known string (e.g. "This should decrypt"), encrypted using the shared secret key. We can test this hmac against the one produced with the users' key to verify the key is "correct" before continuing with deserialization of the unencrypted data from the database. Obviously this HMAC would have to be visible to anyone, before they make use of their secret key.

I'm concerned that this scheme exposes something that shouldn't be. Does using an HMAC in this way expose our encryption scheme (or worse, information about the shared key)?
I really don't have an answer (other than saying that storing a hash of the password is good as any other way of solving your immediate problem; there are other ways, but they all allow an attacker to run a dictionary attack on the database).

On the other hand, I do have these comments on what you're doing:


If getting decrypted gibberish will really crash your application, well, I suspect that you might want to consider better error handling.  There are reasons other than "the user gave us the wrong password" for getting bad data (the database server might have gotten a hiccup, the encryptor might have used the wrong password when writing the database record, perhaps an attacker might sprinkle random data over your database); I think you might want to have better error reporting than "Memory fault: core dumped"
Your requirement that there be absolutely no ciphertext expansion limits what you can do; it gives problem to most common encryption modes.  In particular:


If we encrypt the same record value twice to two different fields, does those show up as the same encrypted value?  If so, an attacker will be able to realize that they share a common value (even if he doesn't immediately know what that value is).  Common encryption modes handle this by including a randomization value (IV) as a part of the encrypted data; however, you can't explicitly include an IV in the record.
If we write (and encrypt) a record value A, and then later update that record to be a value B, can an attacker who sees both encrypted records deduce the relationship between A and B.  Common encryption modes handle this as using an IV as well; again, that's not available to you.
If we write (and encrypt) a record value A, is an attacker able to modify that record so that when we read it, it decrypts to a value B (where B has some attacker-chosen relationship to A)?  Common encryption modes handle this by either by being an authenticated encryption mode, or by using an explicit MAC -- neither works for you.



Given these potential problems, you probably should think about what are the security requirements, and how you can meet them.