# How does use of HMAC affect hash function combiners?

In the comments of this question, Ricky Demer proposes a function $HMAX$ to combine two $HMAC$s based on different hash functions:

$HMAX_{H0,H1}(⟨k_0,k_1⟩,m) = HMAC_{H0}(k_0,m) \oplus HMAC_{H1}(k_1,m)$

The OP also talked about hash function combiners in general and preserving collision-resistance of the underlying hash functions, so I was wondering how the introduction of MAC into a hash function combiner, and this construction specifically, would work.

It appears obvious that this scheme will do a good job of preserving (or even enhancing) the PRF properties of the underlying hash functions (it's quite similar to the TLS PRF combiner, which Lehman10 showed was 'somewhat robust'), but I'm unclear what it will do to the collision resistance.

The results of Boneh06 and Pietrzak07 require the combiner output size to be roughly the concatenated size of both hash functions for CR to be preserved.
On the surface this would appear to rule out the $HMAX$ function above as CR preserving, but I'm not sure whether these proofs extend to covering a keyed construction.

Mittelbach13 showed combiners with weaker security guarantees, but shorter output sizes could be produced, as long as it was assumed that one of the hash functions was Indifferentiable from a Random Oracle (IRO) (which also appears to assume a proof in the random oracle model).
Again, I'm not sure whether a) $HMAC$ has an IRO proof, or b) whether the Mittelbach proof covers the use of a keyed construction in the combiner.

I'm also aware that the 'folklore' $\oplus$ combiner does not preserve collision resistance (i.e. it can even create collisions where none existed in the underlying hash functions).
Does this simply (ignoring the use of $HMAC$) apply to this usage, and imply that the combiner cannot preserve CR?

I'm interested in two things:

1. Does the introduction of $HMAC$, or any keyed function in general, complicate/negate the Boneh/Pietrzak/Mittelbach results, or do they apply to any construction?
2. Do any of the results above apply specifically to the $HMAX$ construction described above?
-
What exactly do you mean by collision-resistance of a MAC? $\;$ –  Ricky Demer Oct 31 '13 at 9:48
I'm referring to the collision-resistance of the underlying hash functions - i.e. what happens if you use $HMAC$ as part of a hash function combiner that is intended to be robust wrt collision-resistance (i.e. be collision-resistant if either of the combined hash functions is). –  archie Oct 31 '13 at 9:53
Would you be assuming that the key is fixed before passing HMAC to the combiner? $\hspace{1.25 in}$ –  Ricky Demer Oct 31 '13 at 9:57
Hmmm, I imagine the key would have to be fixed by the combiner, otherwise the combiner would not be a (unkeyed) hash function. I wonder if that answers my question. –  archie Oct 31 '13 at 10:03
I would first look at the series of papers on XOR-MAC (Crypto'95) and its cryptanalysis. –  Dmitry Khovratovich Oct 31 '13 at 19:59