Deriving Keys for Symmetric Encryption and Authentication

Question

So here's the concept. Rather than storing 2 keys and using a random IV, which presents its own problems (key rotation, ensuring no key is used in more than 2^32 cycles, sharing the keys, etc), is it OK to derive the cipher key, authentication key and IV from a master key? It wouldn't stop the need for key rotation policy (changing the key every 30 days), but it would greatly simplify it. So here's the concept:

MasterKey = 256 - 512 bits of CS random entropy

Then, on encrypt:

Salt = 256 bits of random entropy
Derivation = PBKDF2(SHA-512, MasterKey, Salt, 10000, 640bit)

CipherKey = Derivation[0:256bit]
AuthKey = Derivation[256bit:512bit]
IV = Derivation[512bit:640bit]

Then, the Salt is all that's shared in the ciphertext package: Salt || CipherText || AuthText...

The few points here:

1. That MasterKey should be high entropy (at least the number of bits of Cryptographically Secure random as the longest required key).
2. The salt should be as strong as practical as well (CS as well), since salt collisions will automatically become cipherkey, authkey and IV collisions.

3. The maximum length of a single derived key should be less than the blocksize of the PRF used in PBKDF2 (to reduce exposure of the master key if a derived key is found).

   For example, if you used MD5 (bs of 128 bit) to generate a 256 bit key, if that 256 bit key was found (brute force, or other weakness), the entire 128 bit output of a PBKDF2 round would be found. Therefore, the entire PBKDF2 output would not need to be brute forced, but only a single round of it (still hard, but much easier). But if the BS is larger (sha512 vs 256bit key), then finding a derived key would only give you 1/2 the output of a round, making the search much harder (since there are a LOT of inputs that would generate the same 1/2 output)...

The iteration count feed into PBKDF2 should be high enough to provide a proof of work on the derivation, but is obviously application dependent.

Based on my understanding, it demonstrates good forward security (not perfect, but good) in that if you are able to find the CipherKey or AuthKey of a particular message, they would not be applicable to future or past messages. You would need to use that information to brute force the derivation, which would be non-trivial in the least. So therefore, as long as the master key is not compromised, the individual derived keys should be safe and practically independent of each other.

Am I on track here? Or is there something that I'm missing?

Answer 1

Yes, this is a fine approach. This sort of technique is known as "key separation".

Since your master key is a cryptographically secure key, you do not need to use a large iteration count. Also, you could use any PRF, in place of PBKDF2. (The iteration count is normally used if you are applying PBKDF2 to a passphrase, instead of a cryptographically secure key; but that is inherently problematic from a security perspective, so what you are doing is much better.)

For instance, you could use HKDF or AES-CMAC as your PRF. HKDF produces an arbitrary-length output, so you can use it as a plug-in replacement for PBKDF2: Derivation = HKDF(MasterKey) and then continue as you described. A standard way to use AES-CMAC would be to use MasterKey as the CMAC key, and use different message-inputs for each value you want to derive: e.g., CipherKey = CMAC(MasterKey, 0), AuthKey = CMAC(MasterKey, 1), IV = random() (or IV = CMAC(MasterKey, 2)).

(For more on key separation, the tag wiki for key-derivation has a very brief set of keywords that might help you find more.)

Credits: Thanks to @CodesInChaos for suggesting HKDF as one reasonable way to do it.

Answer 2

Since a good block encryption algorithm, e.g. AES, running in counter mode, i.e. encrypting some more or less arbitrary chosen (unknown to the opponent) input values, is generally considered to be sufficiently secure, IMHO that could provide a rather simple and convenient way of deriving a large number of keys from a given master key. One could that way even obtain a hierarchy of master keys generated from a grand master key to be used, say, for a certain particular year, month, etc., using inputs that contain the corresponding year, month, etc.