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

Question

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.

Answer 1

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).