# Questions about Key Derivation Functions

My understanding is that a KDF is a function that takes a master secret and generates multiple keys. It is secure as long as the keys are "independent". If this is true, the following definition would generate a secure KDF, right?

Assuming we have access to a completely random function, $R: \mathcal{K} \rightarrow \mathcal{K}$, we can define a $KDF : \mathcal{K} \rightarrow \mathcal{K}^n$ that on input $S \in \mathcal{K}$ performs the following. $$K_1 = R(S \oplus 1)$$ $$K_2 = R(S \oplus 2)$$ $$\vdots$$ $$K_n = R(S \oplus n)$$ Output $(K_1, K_2, ..., K_n).$

Now of course, we cannot construct random functions so what we do instead is to replace $R$ by a pseudorandom function that no "efficient" adversary can distinguish from random.

Questions:

1. Does this mean that replacing $R$ by, e.g. $AES(k, \cdot)$, where $k$ is fixed would also give a secure KDF? Does $k$ need to be chosen with some care or can it be any value? Would $AES(\cdot, m)$ for a fixed $m$ be equivalent?

2. Does this mean that replacing $R$ by any secure hash function would also give a secure KDF? If that is the case, why does some KDF-suggestions use HMAC instead? Is this only to get a larger "security margin", and to be less depending on the security of the used hash function? Would replacing XOR above with concatenation (which is possible for the hash-function case but not for block cipher case) affect security?

3. If I want to implement a secure KDF, and already have access to AES, SHA1-512, and HMAC, how would I do it such that it is simple but yet secure?

-
"Would AES(⋅,m) for a fixed m be equivalent?", no since it's reversible. The purpose/counter is known, and since you use it as key, the message can be recovered from any K_i, and then you can derive all other K_j. –  CodesInChaos Apr 25 '12 at 16:56
But an attacker doesn't know K_i, this is a key and should be treated as one. Or am I missing something? –  MartinSuecia Apr 25 '12 at 17:04
Your description is a bit vague. But I assumed that with  AES(⋅,m) you meant putting the master key into m and using the purpose as key. And that's clearly a bad idea. –  CodesInChaos Apr 25 '12 at 17:07
What I meant was that $R(x) = AES(x, m)$ where m is some fixed value and R is the function in the definition. Still, I don't see the problem with your interpretation either. Are you saying that AES is not a PRF, or that a PRF does not suffice? However, I was thinking of the KDF as a way for a single user to generate multiple keys (e.g. for encryption and MACing). If a system uses a KDF and a single shared secret to generate keys for different users, either of these is definitely a terrible idea. –  MartinSuecia Apr 25 '12 at 18:01
Could you elaborate on what you mean by "simple" in question 3? It may mean "easy to write code for", "cheap hardware implementation overhead", etc. –  B-Con Apr 25 '12 at 18:49

Let's start with a general secure KDF construction, as follows. Let $F(k,x) \rightarrow \{0,1\}^n$ be a secure PRF. Then choose $L$ such that $L \times n$ provides as many output bits as you need for all of your generated keys. Let $S$ be your original secret key/entropy. Generate the following string:

$KDF(S,N,L) := F(S, C || 0) || F(S, N || 1) || ... || F(S, N || L)$

where N is a unique value per application that calls the KDF. In the case that you are generating $n$ bit keys, you would simply assign each key $K_i := F(S, N || i)$.

This is similar to your construction, but distinctly different. In your construction, $R$ is fixed across all calls, whereas the PRF above chooses a different random function for each entropy input. In fact, you are essentially trying to emulate the behavior of the PRF by using $R$ and $S$ prefixed to all the inputs. However, I don't know if $R(S || X)$ is as secure as $PRF(S,X)$, and I wouldn't assume that without some proof. At any rate, I don't think we even have any modern algorithm candidates for something like $R$ aside from taking a $PRF(k,x)$ and fixing $k$ to be some constant.

One advantage of the constructed $KDF$ above is that it is more resistant to bad input, namely it will provide unique keys even if the input is improperly provided. Should the same entropy be accidentally given to multiple processes (perhaps due to entropy failure), you still guarantee unique keys are generated in each process due to the $N$ value. And concatenation is safer than XOR when it comes to combining a fixed value with a counter. This is because with XOR, incrementing the fixed value and calling again may create the same value after the XOR with the counter. Eg, fixed value 0x71 $\oplus$ counter value 1 yields 70, as does fixed value 0x72 $\oplus$ counter value 2. In such a case, you'd generate duplicate keys.

1) $AES(k,\cdot)$ can be used as a PRF that outputs 128 bits. (This is the premise behind the counter mode of encryption using AES.) Here, you would use $S$ as your key.

2) Conceptually, hash functions kind of look like random functions, but it is vital to understand that they are not. In cryptography theory, hashes do not have the same constraints as truly pseudo random functions (PRFs). For example, it is entirely possible that a theoretically secure hash function could leak information about the plaintext. In practice I doubt we would like a hash function that did, but nevertheless hash functions are not to be treated as random functions. In contrast, HMAC actually is a PRF, and it is conveniently built using hashes. But the construction of HMAC has advantages over plain hashes of keys concatenated with plaintext, as the latter have very concrete vulnerabilities that arise from the very fact that hashes do not have the same criteria as random functions.

3) You can use HMAC to create a KDF: Have you seen PKDF2? The implementation is fairly simple given HMAC. Or even HKDF, which is yet simpler, but I would recommend PBKDF2. The construction I outlined in the beginning using AES as the PRF would also work.

-
Thank you for your answer B-Con, this made it much more clear. –  MartinSuecia Apr 25 '12 at 19:04
A question regarding PKDF2: My master secret is not a password but rather a random number, can some steps in PKDF2 be omitted? In particular, can the number of iterations be 1? –  MartinSuecia Apr 26 '12 at 11:24
The iteration count is a barrier to brute-force attacks, regardless of where the master secret originated. Even if it were a random number, it's possible that something in how it is generated or used would reduce the effective entropy to something that an attacker might plausibly brute-force. If you have the CPU cycles to spare I would recommend choosing 1,000 or more, just as a precaution. But nothing forbids you from fixing it at just 1. I would also provide a salt, to prevent multiple processes from potentially generating the same output. A PID, or something similar, would suffice. –  B-Con Apr 26 '12 at 15:38
Not running under an OS, so no PID, but on the other hand, no multiple processes :) –  MartinSuecia Apr 26 '12 at 17:54
I think you should use HKDF (or a KDF from NIST SP 800-108) if you require a KBKDF (key based KDF) and PBKDF2 if you require a PBKDF (password based KDF) that performs key stretching. You don't need a PBKDF2 (or salt nor iterations) if you already have a key / secret with enough entropy. –  owlstead Apr 19 at 16:20

You might be interested in the Block_cipher_df specified in section 10.4.2 of NIST SP800-90 (DRBG). Basically, it first calculates the CBC-MAC of the input key material using a constant key, and uses the output from that operation as the key for the "actual" PRF operation (which in the case of SP800-90 simply is $K_i = AES(M,K_{i-1})$, but I don't see any apparent reason why using AES-CTR for that step wouldn't do just as well.

-