HMAC construction based on the combination of two hash functions

Question

I would like an $\operatorname{HMAC}$ that's based on two different hash functions ($H_1$ and $H_2$), so that a break of the combined $\operatorname{HMAC}$ would imply a break of $\operatorname{HMAC}(H_1)$ and of $\operatorname{HMAC}(H_2)$. The combined HMACs in TLS and SSL have attempted to achieve this property, but according to Anja Lehmann's dissertation, not very well. Lehmann suggests a construction for combining $H_1$ and $H_2$ to make a generic $H_*$, but with considerable complexity and expense.

I was wondering if there is a construction specific to $\operatorname{HMAC}$ that's simpler and cheaper. One I thought of is something I call $\operatorname{HMAX}_{H_1,H_2}(k,M)$, which derives $\mathrm{ipad}$ and $\mathrm{opad}$ from $k$ as in standard $\operatorname{HMAC}$, then computes

$$\mathrm{inner} = \mathrm{opad} \operatorname\| H_1(\mathrm{ipad} \operatorname\| M) \operatorname\| H_2(\mathrm{ipad} \operatorname\| M)$$

and then outputs:

$$H_1(1 \operatorname\| \mathrm{inner}) \oplus H_2(2 \operatorname\| \mathrm{inner})$$

This construction seems to capture the collision-resistance of the concatenation hash combination and the PRF-amplification of the XOR hash combination. It also doesn't inflate its output length. I don't have a proof that it works though. Does this seem like a good or bad idea?

Edit: Add "$1$" and "$2$" to the outer hashes to prevent an answer of $0$ when the same hash is used for $H_1$ and $H_2$. Thanks to Paŭlo Ebermann for pointing out that corner case.

Answer 1

This is proabably a bad idea.

There are several results that indicate there are problems with this design:

• While $\oplus$ preserves the PRF property, it is not a robust combiner: it requires that $H_1$ and $H_2$ are independent to guarantee the PRF property is preserved.
  i.e. consider what happens to your design if $H_2$ is defined as $H_2(2 \parallel data) = H_1(1 \parallel data)$
• Boneh06 and Pietrzak07 proved a lower bound on the size for collision resistance preserving combiners, showing that they can't be significantly, i.e. $\theta(log_b)$, smaller than the concatenated size of both hash functions. These papers don't seem to directly address $HMAC$ style key data, but they appear to be quite general results.
• Mittelbach13 removed the concatenated size limit for collision resistance preserving combiners, but at the cost of significant time complexity (well beyond the $Comb_{4P}$ combiner introduced in Lehman10 and the combiner you have described) and specific restrictions on the hash functions and the proof.
• Part of your motivation for this design appears to be the complexity and expense of the $Comb_{4P}$ combiner, but aside from output size (2 x for $Comb_{4P}$) the schemes appear similar.
  i.e. assuming hash functions like SHA-256, with a $block size = 2 \times output size$, $Comb_{4P}$ requires hashing $M$ with both $H_1$ and $H_2$, followed by 4 further hash blocks and 5 $\oplus$s. With a similar instantiation your design appears to hash $M$ with both $H_1$ and $H_2$, followed by 6 further hash blocks and 1 $\oplus$s.

I'm still trying to get my head round all this, so I could be a little off-base with some of these, but in general this doesn't appear to be an area where easy shortcuts can be taken.

I'm not quite sure what to make of the $HMAC_{H0}(k_0,m) \oplus HMAC_{H1}(k_1,m)$ construction described by Ricky Demer - it looks like it would preserve the PRF properties well, but on the surface it seems to violate the Boneh result on the lower bound for a combiner that preserves collision resistance.