Questions about Key Derivation Functions

Question

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?

Answer 1

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.

Answer 2

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.