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.

  • $\begingroup$ 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. $\endgroup$ Sep 13, 2013 at 22:38
  • $\begingroup$ There's an obvious approach whose only issue is doubling the key size. $\;$ $\endgroup$
    – user991
    Sep 14, 2013 at 2:03
  • $\begingroup$ 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). $\endgroup$
    – Max Krohn
    Sep 14, 2013 at 2:34
  • $\begingroup$ The approach I was referring to does not increase output size. $\;$ $\endgroup$
    – user991
    Sep 14, 2013 at 3:34
  • 1
    $\begingroup$ $\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}$ $\endgroup$
    – user991
    Sep 14, 2013 at 17:10

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.