# 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, 2015 at 3:24
• Yes, key1 and key2 are independent values. Key1 is provided by user 1 and key 2 is provided by user 2. Oct 27, 2015 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? Oct 27, 2015 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, 2015 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. Oct 27, 2015 at 3:44