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

-
Whether this is any good depends on how un-similar H_1 and H_2 are. Consider what happens when you use the same hash function for both, for example. –  Paŭlo Ebermann Sep 13 '13 at 22:38
That's a great point, thanks. –  Max Krohn Sep 13 '13 at 23:11
There's an obvious approach whose only issue is doubling the key size. $\;$ –  Ricky Demer Sep 14 '13 at 2:03
Right, I was hoping to avoid the output size inflation. Moreover, what about using this HMAC in PBKDF2? If using the HMAC(H_1) || HMAC(H_2) construction, some output bits will be functions only of HMAC(H_1), and others only of HMAC(H_2). –  Max Krohn Sep 14 '13 at 2:34
$\operatorname{HMAX}_{H_0,\hspace{.02 in}H_1}\hspace{-0.03 in}(\hspace{-0.02 in}\langle k_0,\hspace{-0.01 in}k_1\rangle,m) \;\;\;\; = \;\;\;\; \operatorname{HMAC}_{H_0}\hspace{-0.03 in}(k_0,m) \:\: \operatorname{xor} \:\: \operatorname{HMAC}_{H_1}\hspace{-0.03 in}(k_1,m) \hspace{1.53 in}$ –  Ricky Demer Sep 14 '13 at 17:10

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.

-
My construction does not offer anything at all with respect to collision-resistance. $\hspace{1.7 in}$ –  Ricky Demer Oct 31 '13 at 9:31
That's what I suspected, but I'd really like to understand exactly why. Will ask a new question... –  archie Oct 31 '13 at 9:38