# How to key an HMAC with keys from separate mutually untrusted parties?

The problem is as follows:

There are two parties, both of whom would like to HMAC a message with a key. Although the keys are known to one another, both parties do not trust that the other one created a truly random key.

The HMAC result must not be easily attackable by a third party. So it is necessary the final key has substantial entropy whether or not one party didn't supply any.

In an optimistic world, both parties generate cryptographically secure 256-bit random numbers to key the message with.

In a less optimistic world, one party generates a secure 256-bit random number but the other party gives back 256 bits of data with hardly any entropy at all whether due to laziness or malice.

If both parties are lazy and/or malicious (worst case), then we can accept that failure is impossible to avoid. We assume for the problem that at least one party sees a good key as being in their best interest.

What would be the best way to structure an HMAC call so that I can use two keys such that one key being weak only means the strength is lower-bounded by the good key and not completely sabotaged due to some sort of subtlety?

The ideas I have are

• HMAC(message, key1 || key2)
• HMAC(HMAC(message, key1), key2)
• HMAC(message, HMAC(key1, key2))

However, this is starting to feel like one of those problems where there is some subtle issue that I'm probably unaware of with all these seemingly straightforward choices.

Edit

After some discussion below, I feel I may need to include some more important details.

Party 1 will hand off an allegedly random 256 bit string to Party 2. Party 2 will also generate an allegedly random 256 bit string. Party 2 will be responsible for generating the HMAC but Party 1 will have the opportunity to reject the result. Both parties know each other's secrets and at least one party cares about having a strong secret although it is possible that the other party is malicious or lazy.

• Are key1,key2 assumed to be independent? ​ ​ ​ – user991 Oct 27 '15 at 3:24
• Yes, key1 and key2 are independent values. Key1 is provided by user 1 and key 2 is provided by user 2. – Samuel Horwitz Oct 27 '15 at 3:29
• Be careful when making this assumption. What happens if user 1 gives user 2 $k_1\in\{0,1\}^{256}$ chosen randomly, and user 2 gives user $k_2=k_1$? In this case, $k_2$ was provided by user 2, but it is not independent of $k_1$. What level of hostility can you expect from user 2? Incompetence or malice? If they are totally untrusted, they could simply hand over any keys to a third party. Or are you simply trying to work around the possibility of them using a bad RNG out of ignorance? – Stephen Touset Oct 27 '15 at 3:36
• See Stephen Touset's comment. ​ If they are necessarily independent, then $\hspace{1.31 in}$ HMAC(message, key1 xor key2) is the best way. ​ ​ ​ ​ – user991 Oct 27 '15 at 3:41
• That's a good point. Although the two users colluding can be ignored as being outside of the problem's scope, one user acting maliciously cannot be. Would using xor be weak only in the easy to spot instance of key1 == key2 or does this weakness have a range associated? I will edit my question with further details that now seem relevant. – Samuel Horwitz Oct 27 '15 at 3:44

I would just concatenate.

Two 256-bit keys lead to a 512-bit key which is short enough for HMAC with common hash functions to use as is. XOR would allow the second party to easily choose a related key (and has worse behavior when neither key is perfectly random). Hashing and double HMAC use more resources without a clear benefit, unless you care about the size of the key, in which case hashing would be the way to go.

If you had longer/more keys, concatenation would become equivalent to hashing, because HMAC internally hashes keys that are longer than block size (512+ bits for all SHA-x).

• Thank you for your answer! As you may have seen above, the comments forced me to think more about what I really want. If I have X number of strings and I know that at least one of them has 256 bits of entropy, can I assume the entropy lower bound of the concatenation of all strings is 256 bits of entropy? Or is it possible for someone to somehow contribute "negative entropy" in a way that by concatenating their string it actually lowers the total entropy? I feel like the answer is "no", but I'm scared of "obvious" answers in crypto and want to make sure. – Samuel Horwitz Oct 28 '15 at 23:05
• @SamuelHorwitz, if one of the values has 256 bits of entropy then the concatenated value cannot reduce that. – otus Oct 29 '15 at 5:45