1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What about using a key derivation function? Why do the keys have to depend on the previous one, instead of just the master key and information of the receiver? $\endgroup$ – Maarten Bodewes Oct 7 '15 at 21:43
  • $\begingroup$ The goal is to minimize storage of keys as much as possible. A client receives the initial key which is sent encrypted with a key encrypted key and generates keys on his side. The context is that of an RPC servant, where each argument in each method of the servant may be encrypted with a key generated from the initial key. The client knows each servant method contract meaning index and number of arguments and is thus able to compute keys for each method it may possibly call. $\endgroup$ – Sebi Oct 8 '15 at 10:10
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I've picked a hash function more due to performance reasons. The current setting doesn't allow storage of a large number of keys, so the hash function seemed like a good alternative performance-wise. Do you know of any performance comparisons between keyed hash functions and HKDF? $\endgroup$ – Sebi Oct 8 '15 at 10:06
  • $\begingroup$ I added some notes on performance. $\endgroup$ – Tim McLean Oct 8 '15 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.