HMAC construction based on the combination of two hash functions 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.
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.