Deriving Keys for Symmetric Encryption and Authentication

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?

-
Why do you need "proof of work" if your master key is random? – dchest Dec 9 '12 at 15:00
@dchest: you don't. The proof of work is getting from the random key to the cipher key (making it harder to go backwards from the cipher key if you ever are able to break it)... – ircmaxell Dec 10 '12 at 21:17
If your key has 256 bits of entropy and your key derivation function is one-way, adding or removing iterations to key derivation won't make bruteforcing particularly harder or easier -- 1 iteration is already hard enough. Iterations are needed when you're dealing with passwords, which don't have enough entropy. – dchest Dec 11 '12 at 10:18
I'd use HKDF for the key derivation – CodesInChaos Jan 8 '13 at 15:46

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 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.

-

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.

-
The secret part of an encryption algorithm should be the key, not the plaintext. In counter mode, the input is usually known. – Paŭlo Ebermann Dec 9 '12 at 16:07
@PaŭloEbermann: Right. For counter mode the key is secret as usual. The plaintext part is an arbitrary numerical value, normally successsively counted up by 1 (or by any amount), but that input could just as well form any arbitrary sequence of values (e.g. containing time and message serial numbers, etc. etc., arbeit not necessarily to be very strongly guarded for security resaons). – Mok-Kong Shen Dec 10 '12 at 11:21
I remember to have mentioned the method of deriving keys from a master key via a block cipher in counter mode many years ago in another forum, thinking though even at that time that the idea very probably was old and well known. Recently however in discussions elsewhere I got the impression that it may not have been widely known, probably due to lack of mention in the literature. The idea of having a hierarchy of master keys to derive session keys dynamically was mentioned in my code JADE in s13.zetaboards.com/Crypto/index – Mok-Kong Shen Dec 10 '12 at 14:17
If your cipher input is something else than a sequentially increased number, it is not counter mode, and you should not name it counter mode. (You might have a custom PRNG based on a block cipher.) – Paŭlo Ebermann Dec 10 '12 at 19:34
@PaŭloEbermann: For "definition" you are certainly right. But the security aspect is IMHO the same, thus establishing the usefulness of the idea I mentioned. Note that if a sequence obtained from counter mode (via increasing by 1) can be securely used, then an arbitray sub-sequence, say consisting of the 5-th, 24-th, 88-th, 109-th etc. of the sequence, should also be secure. – Mok-Kong Shen Dec 10 '12 at 19:49