Can I determine if a user has the wrong symmetric encryption key?

Question

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

Answer 1

The usual ways to check that a user-supplied encryption key is correct are to either:

• store a (salted) hash of the key, and check that it matches, or

• encrypt a (partially) known block of data with the key and check that the decrypted output has the expected form.

The former method is exactly same as what your OS, for example, does to verify that you entered the right password when logging in; for more information, see e.g. "What makes a hash function good for password hashing?". For an example of the latter approach, see the recent question "How does GPG verify succesful decryption?".

You could certainly also use HMAC, or indeed any other secure MAC, for key verification as you suggest. The only change I'd make to your suggested scheme would be not to use a fixed input for the MAC. Instead, choose a random input string, calculate its MAC using the key, and store the input and the MAC together. The random input effectively acts as a salt, so that an attacker can't tell whether two keys are the same just by comparing the corresponding MACs.

If you're not doing this already, I'd also strongly recommend not using the user-supplied key directly, but instead first passing it through a deliberately slow key derivation function such as PBKDF2, bcrypt or scrypt. You should do this first, before even trying to verify the correctness of the key, and immediately discard the original user-supplied key and use the derived key for everything (both verification and actual en/decryption). That way, someone attempting a brute force attack on the key won't have any short cuts, but must re-run the key derivation function for every candidate key.

I would also echo poncho's concerns: the requirement that encryption cannot increase the length of messages makes designing a secure cryptosystem much harder. (Indeed, it makes some definitions of security just plain impossible to achieve, since you won't be able to authenticate the data.) I'd very much suggest trying to find some way — any way — around that limitation, since it's likely to be the biggest and most fundamental security issue in your system. Of course, if you really can't fix that problem, then you just have to live with it (and should probably look into disk encryption theory, which deals with similar constraints).

Answer 2

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.

Answer 3

You could store a hash of the shared key used to encrypt the data, and then later compare it to the hash of the user entered key. This is much like storing a hash of a password to confirm a user has entered the correct password (without storing the password in the clear).

If you have control of the generation of the shared key, you could also append a checksum to the end of the key that's used to guard against typos.

Answer 4

Can you append a hash to the end of the data before encrypting it? That would be a simple way to verify the data.

MSG' = MSG + SHA(MSG)

Store: Encrypt(MSG')

After decryption, verify that the data hash matches.