Is it secure to derive an AES key from a MAC?

Question

I'm working on a project where we need to encrypt a large number of files and store them on the cloud. And I'm wondering if the following process would be secure (we have a “Hardware Security Module” and an “encryption server” in a private data center, only the files will be in the cloud).

Since the volume of the files is too big to be encrypted in an HSM, my idea is to:

1. Have a 256 bit master encryption key in an HSM.
2. Derive an encryption key by generating a 256 bit random number and HMAC-SHA2-256 it with the master encryption key.
3. Take the rightmost 128 bits from the MAC and use that as an AES key.
4. Take the leftmost 128 bits from the MAC and use them as the IV.
5. Encrypt the content in an internal server.
6. Overwrite the memory where the derived AES key was stored.
7. Store some metadata of the file (including the 256bits random number from the 2nd step).

I would do something similar to generate a signing key:

1. Have 256bit master signing key in an HSM.
2. Derive a signing key by generating a 256 bit random number and HMAC-SHA2-256 it with the master signing key.
3. MAC the encrypted file with the derived signing key
4. Overwrite the memory where the derived signing key was stored.
5. Store some metadata of the file (including the 256bits random number from the 2nd step).

To decrypt the data, I would use the random number to re-derive the key. What I'm trying to achieve with this is a different key per file, plus we can rotate the master key every now and then for extra security. Plus, after a few years, when we don't need those files, we can delete the master key (apart from deleting the files from the cloud).

I know the process above is not 100% secure, as the derived key will exist outside the HSM, but we need to keep a balance between security and cost. If storing the plain random numbers is not secure, I could have an AES key in the hsm only to encrypt the random numbers.

The level of security / assumptions I'm happy to live with is:

• If the HSM is compromised, all files are compromised (this quite an obvious one)
• If the encryption server is compromised, an attacker has access to the plain text files before they are encrypted (so I don't even bother to think about the attacker stealing the AES keys as they are in memory).
• An attacker stealing the database (with the random numbers) plus all the files, cannot decrypt the data.

(I hope these assumptions are sensible - please let me know if you disagree!)

Answer 1

It looks like, given your adversary model, things should be secure. HMAC as a randomness extractor has been shown to be good, especially when we can assume the hash function is collision resistant. That paper also has some results which tell how you could guard against the collision resistance being broken (basically use a hash function with larger output size). If SHA-256 is broken any time soon, however, we are all in a lot of trouble, so I wouldn't be too worried about that attack.

Answer 2

It seems that you are trying to implement your own KBKDF (Key Based Key Derivation Function) using HMAC. Maybe it is better to use a pre-defined one.

It would be more sensible maybe to use an HSM that is FIPS certified for NIST SP 800-108. These use one of the KBKDFs defined in NIST SP 800-108.

You can still use the idea of the random by putting it in the context input field of the KBKDF. Note that if you have a nonce from context (e.g. hash over a file name) you do not strictly need a random value; just performing a KDF over the label / context should be enough as long as the combination is unique.

You should make sure that the key that is generated can be exported out of the HSM. If the algorithm is not available, it would make sense to implement one of the KDFs (e.g. the counter mode one) using a MAC algorithm provided by the HSM.

Note that all of the KDF's defined in SP 800-108 are using MAC (cipher based or hash based) as underlying function of the KDF.