Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
$\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

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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