Is the HMAC construction really neccessary for a fixed length message?

Question

The HMAC Construction is defined as:

Hash( (Key XOR opad) || Hash((Key XOR ipad) || Message) )

This was designed because a simpler construction such as:

Hash(Key || Message)

Is vulnerable to a length extension attack (but not for all hashes, a notable exception is SHA-3).

The questions are, what about cases where the message:

1. Is of a known, fixed length, and would be rejected if having any other length than the expected one (CBC-MAC, for instance, is secure for a fixed length message, but not for a variable-length one).
2. Is prepended with fixed-sized length indicator at very the beginning of the message (i.e. the extended message would be Fixed-Sized Length indicator||Message and the hash would be: Hash(Key||Fixed-Sized Length indicator||Message)).
3. The same scheme as the previous one but where the length indicator is only included within the hash.

(these may be completely different cases so consider them separately).

Note that for (3) an alternative configuration Hash(Fixed-Sized Length indicator||Key||Message) would guarantee that the length indicator is included in the first block of the hash - I mean, even for a huge key that is larger than the hash function block length. The length indicator would probably not need to be any more than 64bits of size (as most [older] hashes are limited to a maximum message size of 2^64 - 1 bits anyway). This makes it very hard to imagine how can it be insecure? But I'm not a cryptographer, I guess.

Answer 1

I'm going to agree with @fgrieu's marvelous post above in a back-handed way.

My answer is: No, you don't have to use an HMAC. Do it anyway.

As you noted, some hashes, sush as SHA-3 (especially in its Keccak form), Skein (which I was a team member on), and others will work just fine. In the case of Skein, there is a one-pass Skein-MAC that has a proof of security interestingly done by Mihir Bellare (also a Skein team member), who did the HMAC proof that @fgrieu cited above.

Furthermore, there is an HMAC criticism that I and a few others (including Niels Ferguson, another Skein team member) have made that is that HMAC essentially assumes a working hash function. HMAC protects against a number of breakages of hash functions, including Merkle-Dåmgard length extension attacks, but we don't know how good it is with a hash function with whatever sorts of weaknesses. I don't think we have any idea, for example, how good HMAC-MD5 or HMAC-MD4 is, despite the horrid breaks in each of them. (MD5 is readily broken with a computer; MD4 is readily broken with pencil-and-paper.) You can see that criticism above in @fgrieu's remark about assuming that F is an ideal PRF. What if F is known to be a non-ideal PRF with a whole set of flaws? How good is HMAC then?

You've described a bunch of constructions that are very likely to work just fine with the sort of hash function one is likely to see in the real world, like SHA-1, SHA-256, SHA-512, and SHA-512/z that are still known to have weaknesses. Even better would be a hash of Key-Length || Key || Message-Length || Message.

But do an HMAC anyway, unless you have a need for the one-pass MAC that you can get from Skein or Keccak/SHA-3. As an example of need, the protocol ZRTP allows either a SHA-1 HMAC or a Skein-MAC (again in full disclosure, I'm a co-author of this protocol and perpetrator of this use). The reason is that if you're doing the HMAC, then the majority of the compute time of the protocol is spent in the HMAC. Despite this, it's merely an option with a fallback to the HMAC always being there.

The reason you want to do an HMAC is a meta-principle I've learned in doing crypto: don't do anything that stupid people think is stupid. Think of this as a corollary of the maxim, "never argue with an idiot, people may not be able to tell the difference." That's snarky and pejorative, so let's also call it the Elvis Costello Detective principle, "Don't get cute." So let's look at it from a real-world perspective.

I think that your construct is just fine in any real-world case. But what if we are wrong? Unless someone who is as well-respected in protocol proofs as Mihir Bellare is going to do a proof for this, then we always are behind the you-have-no-proof eight-ball, and it's a fair cop! Even if you point out that these security proofs has their own set of assumptions and are of questionable worth (especially after the Paterson et al. SSH break -- which is another whole discussion), the fact is that there's a proof for HMAC and not for yours (unless you're using a known-good-MAC hash like Skein or Keccak).

I can think of some ways to break that construct through the use of stupid coding. (Here's a hand wave: make the counter be a fixed-length binary counter, as opposed to the ASCII string of the actual length. Wrap the counter so the colliding message has the same length mod 2^n (e.g. 1 vs 257 for a one-byte counter or 65537 for a two-byte counter) and then go on for a length-extension attack.) This is massively face-palmingly broken, but it wouldn't be the first time someone made a massively face-palminingly broken coding error. In fact, such things happen every day.

I have come to believe that an important property of good crypto is being understandable. The advantage that HMAC has over constructs like an improved keyed hash is that the person reading your protocol can say, "oh, it's an HMAC" and move on, rather than having to read all the details and remember under which circumstances those improvements work. Moreover, if you use something nonstandard, people will complain. Those complaints won't go away. Even after you've written a zillion blog posts about how what you did was just fine, people will still complain. Whereas if you use an HMAC, they won't. The cost of the lack of complaints is a mere second call to the hash function. If that mere second call is actually a large cost (like with ZRTP), then there are one-pass systems with proofs of security you can use!

The ultimate problem with what you're suggesting is that you're getting cute. HMAC exists to address known problems with keyed hashes. It has a proof of security that shows that it meets that goal. It has a history of being useful in the field. Even the legitimate criticism of that proof and use-history doesn't bolster the way you're getting cute, and even though I think your cuteness is secure enough, I know I don't have anything other than licking my finger and sticking it in the wind to back me up.

So to sum up, no, you don't have to use an HMAC. Do it anyway.

Answer 2

In summary: Yes, HMAC is the way to go for construction of a MAC from an arbitrary concrete iterated hash. We have no constructive argument of security of the MAC constructs in the question; we even have a concrete attack when using some otherwise apparently fine hashes.

---

I consider a hash constructed by iterating a compression function $F$ as $s_{i+1}=F(s_i,m_i)$ with $s_i$ of $h$ bits (also the size of the MAC), message blocks $m_i$ of size $b$, perhaps with Merkle-Dåmgard strengthening (this matches MD5, SHA-1, SHA-2, but not Keccak/SHA-3); I also assume Key is of fixed size, enters $m_0$, and the third construct is Hash(Fixed-Sized Length indicator||Key||Message).

Under the assumption that $F$ is an ideal PRF, the three constructs in the question appear to be secure, but perhaps to some sub-optimal degree. The best general attack (that is, valid irrespective of the details of the iterated function) that I see is to obtain the hash of messages of equal size (at least $\max(2b,h)+b$), with the beginning of the message random and the last message block fixed, until a collision is found between distinct $m_0$ and $m_1$ (which requires $\mathcal O(2^{h/2})$ MACs); then obtain the MAC of $\widetilde{m_0}$ with the last bit toggled; that MAC will stands a good chance to also be valid for the similarly modified $\widetilde{m_1}$. That's a valid attack against the MAC. It works because the collision between the MACs for $m_0$ and $m_1$ stands a good chance to have occurred before the last block, and in that case $\widetilde{m_0}$ and $\widetilde{m_1}$ will necessarily collide too.

The above generic attack does apply to HMAC (and CBC-MAC, and any iterated MAC with a single pass). However, HMAC (contrary to the other constructs) comes with security arguments that there is no asymptotically better attack, and even arguments valid with relatively weak assumptions on the iterated function; see Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, with extended abstract in proceeding of Crypto 2006.

The security arguments of HMAC, and the fact that the key enters both at the start and the end of the computation (which in turn insures, in the above attack, that the attacker does not get to know the colliding value), gives us a security margin. I'm reasonably confident that HMAC-MD5 won't be practically broken (excluding attacks on implementations such as DPA or injected faults) for some years, but I'm not so confident for MACs constructed from MD5 as in the question. Addition: there's a lot of truth in the saying: better safe than sorry.

As an illustration of the superiority of HMAC, we can make an iterated hash such that the three constructs are weak, but HMAC remains strong. An example is SHA-256 modified by removing the 8 additions modulo $2^{32}$ in the 4^th (last) step of a round (making that $H_0^{(i)}=a$, .., $H_7^{(i)}=h$). If there's an attack against the collision-resistance, or (first or second) preimage resistance of that modified SHA-256, I fail to see it (update: on second thought, the best I see is a preimage attack similar to this, with cost about $2^{128}$ rather than $2^{256}$ for full SHA-256). However, in the constructs of the question, from a single message/MAC pair, it becomes easy to compute the MAC for any message of the same length differing in blocks after the first (notice that for known blocks and output, it is possible to walk back the hash states). [Addition following strongly critical comment: A key point of my reasoning is that the security argument of HMAC seems to apply when using that modified SHA-256; I'll concede a gap if it irreparably does not; or if since there's a widely accepted definition of security of a hash that this modified SHA-256 fails (quantitatively at least), but SHA-256 pass (notice that SHA-256, contrary to Keccak/SHA-3, trivialy fails widely accepted definitions of security due to the length-extension property)].