Suggestions for improving encrypt-then-mac flow

Question

I have a large piece of data I want to encrypt, and I have a key master_key.

Rather than encrypt the data directly with master_key, I generate a random key item_key, split it in two parts, and encrypt the data with the first half, and use the second half as an auth key in generating an authentication hash with HMAC.

I then encrypt item_key with master_key. This way, if the user were to change their master_key, I would only need to rewrite the item_key, and not the large piece of data.

So the end result of the overall encryption is:

• the ciphertext
• the authentication hash (or tag) of the ciphertext <- HMAC(ciphertext, auth key)
• encrypted item_key

What I overlooked however is that I am generating two ciphertexts here, one of the encrypted data, and one of the encrypted key. But, I only have one auth hash. This is a flaw as I go on to decrypt the encrypted item key using the split master_key without checking its authenticity. I do however check the authenticity of the ciphertext, but that's not as useful.

My challenge now is to use the pieces that I already have to fix this problem. This means I don't want to introduce new keys.

To fix this flaw, I would need to generate an auth hash/tag for both the data ciphertext, and the item key ciphertext. The problem is, I don't have another secret authentication key to spare.

Possible solutions:

1. Do not generate an auth hash for the ciphertext, and instead generate an auth hash only for the encrypted item key, since that is what is being encrypted with the master key. The application promises to never decrypt the actual data ciphertext without first authenticating and decrypting the item key. Will I be roasted by the security community for doing this, even if it's theoretically safe? Is it "bad style"?

2. Derive from the master key an encryption key and an auth key using a PBKDF2 with a small iteration count (less than 3000). I would use this auth key to generate an auth hash for every encrypted item key. (The item key would then be used the same way explained in the beginning: split in half, one half used as encryption key, the other as auth key for the data).

I prefer to go with option 1. Does this sound reasonable? Or are there any other solutions I may be overlooking?

Note: AES-GCM would seem to solve this problem easily, as I do not need auth keys, but I cannot use this method since the platforms I intend to support do not provide native support for this algorithm.

Answer 1

The primary purpose of the MAC in an Encrypt-then-MAC scheme is not to detect attempts to decrypt with the wrong key (although it may accomplish that as a side effect, depending on how the encryption and MAC keys are derived), but rather to make the scheme non-malleable, and thus:

1. protect the user's data from tampering by an attacker who can modify the ciphertext, and
2. protect the encryption part of the scheme from attacks (such as padding oracle attacks against CBC mode encryption) which are based on feeding malformed ciphertext to the decryption algorithm.

Thus, if you want your scheme to resist such attacks, you really do need to apply a MAC to the actual ciphertext that encodes the user's data. Only MACing the (encrypted) item keys will not protect the user's data from tampering. Thus, your "option 1" is definitely insecure.

---

Your option 2, on the other hand, does appear reasonable, at least as far as you describe it. (I cannot, of course, tell if there are security flaws in the parts that you haven't described, or in the way that you implement the parts you do describe.)

Note that the iterated key stretching aspect of PBKDF2 is only needed when the input is a user-entered password or some other potentially low entropy string. In your case, since you already have a high-entropy master key as input, you may safely reduce the iteration count to 1, or even use a non-iterating KDF such as HKDF.

Alternatively, I don't see any reason why you couldn't just double the length of your master key, and split it into two parts like you currently do for the item keys, except that this will require slightly more storage space for the master key. But since you only have one of those, I doubt that would be a major issue.

---

If you wish to minimize the overhead of storing and authenticating the item keys, I could suggest something like that following scheme:

1. Store a single base master key (of, say, 256 bits); use HKDF-Expand (or PBKDF2 with an iteration count of 1) to derive a master encryption key and a master MAC key from the base master key.

2. For each item, store a single base item key (again of, say, 256 bits) encrypted with the master encryption key and authenticated with the master authentication key.

3. Derive an item encryption key and an item MAC key from the base item key using HKDF-Expand (or PBKDF2 with an iteration count of 1), exactly the same way as for the master key in step 1.

4. Use the derived item encryption and MAC keys to encrypt and authenticate the user's data.

This should consume no more space than your current scheme (assuming that the MAC tokens aren't longer than 256 bits, which they really have no reason to be), while protecting both the item keys and the items themselves from tampering.

As an extra precaution, you may also wish to include some metadata (such as user and item IDs) as "associated data" in the MAC calculations in steps 2 and 4. This will prevent an attacker from, say, replacing one encrypted item and its item key with the corresponding data and key of another item. Whether such attacks are actually a relevant threat for you will depend on things like what these "items" are actually used for, but since they're easily enough prevented, you might as well do it anyway.