Purpose of outer key in HMAC

Question

From what I know, the HMAC constructions has two strength:

1. It's resistant to length extensions
2. Since the key is consumed before the message, the attacker does not know the initial state, preventing simple collision attacks.

But the simple construction $ \mathrm{Hash}(\mathrm{Hash}(\mathrm{key} ∥ \mathrm{message})) $ would offer those properties too.

HMAC on the other hand uses the more complicated construction $ \mathrm{Hash}((\mathrm{key} ⊕ \mathrm{opad}) ∥ \mathrm{Hash}((\mathrm{key} ⊕ \mathrm{ipad}) ∥ \mathrm{message})) $. I assume the more complicated construction of HMAC is required for some security proof, but I don't immediately see why.

For SHA-3 candidates, Hash(key||message) is claimed to be secure, since they're resistant to length extensions, without consuming the key twice. I believe Skein even has some security proof for a very similar mode.

So why does HMAC need to inject the key twice?

Answer 1

You're missing the most important strength of HMAC: it comes with a proof of security (under some plausible assumptions). The outer key plays an important role in the proofs. The best place to learn more is to read the HMAC papers:

• Message authentication using hash functions: The HMAC construction, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CryptoBytes Spring 1996.

• Keying hash functions for message authentication, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CRYPTO '96.

In particular, it is very important for their proof that the outer function be keyed. In your scheme, the outer function is not keyed, so their proof of security will not apply.

As they explain in the paper, the role of the inner function is to provide collision-resistance (to compress a long message down to a short fingerprint, in a way so that someone who does not know the key cannot find a pair of messages with the same fingerprint), and the role of the outer function is to act as a message authentication code on this fingerprint. Their security proofs show that if the inner and outer functions each correctly implement their roles, then the combination (HMAC) will be a secure message authentication code. Because the outer function needs to be a secure message authentication code, that means the outer function needs to be keyed for their proof methodology to apply.

Read the papers. They are surprisingly readable, for a theoretical piece of work.

Answer 2

As a Skein co-author, one of the properties of the UBI chaining mode is to give you HMAC-like properties in one pass. Skein itself consists of the Threefish tweakable block cipher, the UBI chaining mode, and some proofs that extend tweakable block cipher theory into a tweakable hash function theory that reduces the security of the hash function to the security of the block cipher. (I will note in passing that one of the strengths of the Skein team is that we all have certain strengths that we brought to parts of the whole; Mihir took the lead on the proofs, and he's a co-author of HMAC.)

One of the features of that is that you get a one-pass MAC for free with Skein.

HMAC, in contrast is a wrapper around any hash functions that (often) amplifies its security. In the Introduction of the CryptoBytes article on HMAC, they say,

"One of the many difficulties [of constructing a MAC from a hash function, as opposed to a cipher] is that they are not even keyed primitives, i.e. do not accommodate naturally the notion of a secret key." Several constructions were proposed prior to HMAC, but they lacked a convincing security analysis.

HMAC creates a wrapper that goes around an arbitrary hash function and gives you some security properties that the hash function did not have. Skein designs a tweakable hash function, and it is that tweak that gives you a mechanism to put in a key securely.

Jon

Answer 3

With common Merkle–Damgård hashes like SHA-256, $H(\text{key}\mathbin\|\text{message})$ is vulnerable to a length extension attack, where $H(\text{key}\mathbin\|\text{message}\mathbin\|\text{pad}\mathbin\|\text{extension})$ can be computed knowing $H(\text{key}\mathbin\|\text{message})$ and the length of $\text{key}\mathbin\|\text{message}$ (with $\text{pad}$ trivially determined from that), for any known $\text{extension}$.

$H(H(\text{key}\mathbin\|\text{message}))$ is enough to block that simple attack. But one good reason to NOT use that as a MAC is that we do not have a security proof for that construction, when we have one for HMAC since the origin. Even better, the modern security proof of HMAC gives an argument that HMAC is secure even if the compression function in the underlying hash has properties insufficient to make the hash collision-resistant. In particular, HMAC-MD5 still seems quite strong, even though collision-resistance of MD5 is badly broken.

Both of these security proofs require two hashes each starting with (different variants of) the key. Intuitively: there's a similarity to adding rounds in a block cipher, which makes recovering the key or otherwise breaking the cipher much harder; the outer hash sorts of re-enciphers the result of the previous one.

Answer 4

I'm putting another answer in because as good as D.W.'s answer is (I up-voted it), it doesn't really answer your question.

You said:

But the simple construction Hash(Hash(key|message)) would offer those properties too.

But the construction you gave -- Hash(Hash(key|message)) -- has a weakness that HMAC does not.

One of those properties was resistance to simple collisions. What is a "simple" collision is undefined, and you might not consider what I'm going to say to be a simple collision, but it is nonetheless a weakness.

If I can construct a collision to key|message then that collision propagates out to the MAC as a whole. But the same attack does not work against HMAC.

HMAC, as you know, uses two keys. I'm going to call them K1 and K2, and they're constructed by XORing with the two different pads. Think of it as a simple key derivation function. HMAC gets added strength not only because it uses an inner key and an outer key, but that they are different keys. Consequently, an attacker who constructs an attack based upon a hash collision must collide against each of these keys, which is hard. That is also the essence of the proof, as well (summarized).

So the answer to your exact question is that it's not the key. It's using two different keys, each simply derived from the base key and you're forced to break them both.

Jon