Suppose that I have $n$ secure 32-bit keys that were generated separately using methods that are known to be secure. For example, one of them might have been generated by using a proven CSPRNG. Another may have been generated using PBKDF2.

Now, I want to turn all of these keys, combined together in to a new key that I can use to encrypt and decrypt data.

The important thing is that I want to require all of the keys to be present in order to perform the encryption and decryption.

What I want to know is, what is the best way to combine these keys and maintain the highest level of security against attacks?

For example, I could just concatenate all the 32-bit keys and then run them through PBKDF2 again:

# pbkdf2(key, salt, iterations, derived_key_length)
# Also, "a + b" indicates concatenating a + b as strings, i.e. "hello" + " world" = "hello world"

new_key = pbkdf2(key1 + key2 + key3, some_salt, 10000, 32)

Or, instead of concatenating them, I could concatenate some of them in the salt:

new_key = pbkdf2(key1, key2 + key3, 10000, 32)

Or, I could iteratively run pbkdf2:

temp_key = pbkdf2(key1, key2, 10000, 32)
new_key = pbkdf2(key3, temp_key, 10000, 32)

Or, I could concatenate them all and hash them:

new_key = sha1(key1 + key2 + key3)

Or, I could iteratively hash them with concatenated versions of the previous hash:

a = sha1(key1)
b = sha1(a + key2)
new_key = sha1(b + key3)

Or, I could produce a hash using one of the above methods and then run that hash through PBKDF2:

hash = sha1(key1 + key2 + key3)
new_key = pbkdf2(hash, some_salt, 10000, 32)

Or, I could xor them all together:

new_key = xor(xor(key1, key2), key3)

Or, xor them all together, and then run though pbkdf2, etc. etc.

Clearly there are a ton of ways to combine these keys to produce a new secure key.

Is there any prior work on this? What is the best and most secure way to do this?

If any of the above methods are not secure, can you explain why?

P.S. As an additional aspect of this question, I am curious if the "password" or the "salt" are more or less secure places to put entropy. For example, are both of the following equally secure?

new_key = pbkdf2(key1 + key2, key3, 10000, 32)


new_key = pbkdf2(key1, key2 + key3, 10000, 32)
  • 1
    $\begingroup$ not XOR them together, as the result would only be a 32-bit value, and thus insecure, and not iteratively hash with concatenated versions of the previous, as that can be optimized. a KDF can be functionally replaced with iterative hashing, but I would use some function that uses more memory, like HKDF-expand per Luis's answer, say 65536 outputs of SHA-512, then hash the outputs in reverse order. It will be slow like PBKDF but use too much memory for optimized parallel attacks $\endgroup$ Dec 9 '16 at 5:32

If your keys, taken together, have sufficient entropy to support your desired security level, then HKDF (paper) is a conservative solution here, because it assumes that the input keying material to the HKDF-extract might not be uniformly distributed.

The most conservative way of using it in your case would be to supply the concatenation of your keys as the IKM ("input keying material") parameter to HKDF-extract, and do not use the optional salt. Then either use the PRK result directly, or as a further input to the HKDF-expand function.

A less conservative way of using it, if you are confident your inputs are indistinguishable from uniform random and mutually independent, would be to skip the HKDF-extract function supply the concatenated input directly to HKDF-expand.

  • $\begingroup$ Can you explain the advantage of HKDF over other alternatives for this specific usage? Also, can you explain why concatenation is a sufficient way to merge the keys pre-HKDF? $\endgroup$
    – Sam Smith
    Dec 9 '16 at 0:32
  • $\begingroup$ Specifically, I'm curious what advantage HKDF has over PBKDF2 in this scenario. $\endgroup$
    – Sam Smith
    Dec 9 '16 at 0:43
  • 1
    $\begingroup$ @SamSmith: If your inputs have sufficient entropy to support your security level, then there's no advantage to using a slow, password-based function like PBKDF2. $\endgroup$ Dec 9 '16 at 0:47
  • 1
    $\begingroup$ "The important thing is that" he wants "to require all of the keys to be present in order to perform the encryption and decryption." ​ ​ $\endgroup$
    – user991
    Dec 9 '16 at 2:16
  • 1
    $\begingroup$ @RickyDemer: Are you reading that as implying that the keys are held by separate, adversarial parties? I am not. If you are reading it right, however, then your objection to my answer holds. $\endgroup$ Dec 9 '16 at 2:22

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.