Hash functions vs. keyed hash functions in the context of private key generation

Question

I'm designing a key distribution mechanism and have thought of using a securely generated/acquired private key as a seed for a sequence of private keys to be distributed to a number of users using a key encryption key which is exchanged through a secure channel during the initialization step.

The setting is as follows:

k is a secure private key
h is a cryptographically secure one-way function

n keys are generated using h and k:

$$ k_1 = h(k) $$ $$ k_2 = h(k_1) = h(h(k)) $$ ... $$ k_i = h(k_{i-1}) $$ ... $$ k_n = h(k_{n-1}) $$

This scheme broadens the surface of attack as if one key is compromised, all subsequent key can be easily compromised as well.

Would it be more secure to use a keyed hash function to generate the keys, using a hash of the original key as the input key for the respective hash function?

Answer 1

There's actually an algorithm designed exactly for this purpose: generating a sequence of keys from one master key. It's called HKDF (HMAC-based Key Derivation Function, paper here).

The algorithm essentially boils down to two steps: Extract and Expand. The Extract step accepts any type of "key material" as input, and outputs a pseudorandom key that will be used in the next step. The purpose of this step is to eliminate any patterns, structure, or bias in the input key, and produce a uniformly pseudorandom output.

If the master key is already a string of uniformly pseudorandom bytes (i.e. it was generated using a crypto-secure RNG), it's safe to skip the Extract step (but be sure to read the notes in the RFC).

The second step, Expand, uses the pseudorandom key from the first step to produce an arbitrary length output. Typically, Expand is used to produce a long output, and that output is divided up into smaller keys (e.g. 1024 bits divided into four 256-bit keys). However, it is also possible to use Expand once for each key, while providing a different value each time for the "info" parameter. This is likely slower, but may be more elegant from an engineering perspective.

HKDF is carefully designed to avoid the problem you identified. If any of the output keys are ever revealed to an attacker, the remaining keys are still safe. Of course, if the master key is discovered, game over.

I suggest reviewing the RFC: it's reasonably straightforward, and includes many helpful suggestions on usage. Section 2 has a precise description of the algorithm.

---

With regard to performance, let's assume you skip the Extract step and use HKDF with a hash function whose output size matches the desired key size. The algorithm can now be simplified to $\operatorname{HMAC}(\mathit{key}, \mathit{info} \| 1)$ (where $1$ is the single byte 0x01). If performance is important, it's possible to precompute parts of the HMAC calculation given the master key. Assuming a short "info" parameter, only two invocations of the underlying compression function are needed per key (assuming the use of a Merkle-Damgard hash function like SHA-2, SHA-1, or MD5).

Contrast this with a scheme such as $h(\mathit{key}, \mathit{info})$ (a keyed hash function). With optimizations, only one invocation of the compression function is needed per key. However, this gives up (1) the security analysis and arguments provided by HKDF, (2) HMAC's additional security against breaks in the hash function, and (3) forces you to consider length extension attacks, among other things.