Is the HMAC construction really neccessary for a fixed length message? 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:


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).
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)).
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.
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 4th (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)].