# Is H(k||length||x) a secure MAC construction?

If $H$ is a typical secure hash function, then $(k,x) \mapsto H(k \mid\mid x)$ is not a secure MAC construction, because given a known plaintext $x_1$ and its MAC $m_1$, an attacker can extend $k \mid\mid x_1$ to a longer message with the same hash.

Is $(k,x) \mapsto H(k \mid\mid \mathrm{len}(x) \mid\mid x)$ (where $\mathrm{len}$ unambiguously encodes the length of $x$) a secure MAC construction? Obviously it's inconvenient because you can't treat $x$ as a stream, but is there a known security weakness, or is this known to be as strong as HMAC?

-

This construction is not secure. It was proposed in this paper in a quick sentence for possibly fixing the insecure secret prefix construction from the other question: $\mathcal{H}(k||m)$. The author then proposes and analyzes an enveloping method: $\mathcal{H}(k_1||x||k_2)$.

An attack involving finding an internal collision applies to $\mathcal{H}(k||\ell_m||m)$. It is a bit complex, but if you are curious, it is "Proposition 4" in this paper (also see section 4.1, 1st paragraph). The authors also note that the construction involves additional assumptions on the hash function than the standard ones (collision-resistance, (second) preimage resistance). It is not as efficient of a break as the length-extension attacks on the other construction but it is theoretically a break relative to the security of HMAC.

I will also note that "unambiguously" encoding the length could be problematic. For example (using base 10 for readability), if I hash m=08 with length=2 and some k, then a length extension attack may find m=0896346218569465994320 which could be interpreted as length=20 and m=896346218569465994320. One fix to unambiguously delimiting the length from the message is to fix a certain number of bytes for the length, but you now no longer have a MAC that accepts arbitrary-length inputs.

In conclusion, the HMAC construction is very simple, accepts arbitrary length inputs, and does not rely on an encoding scheme to work.

-
For the length encoding, one can use 7-bit encoding: you represent the length in base 128. Then each "digit" is encoded as a byte, setting the most significant bit for all bytes except the last. This is what is used to encode OID elements in ASN.1/DER; it has no inherent limit. Of course, realistically, encoding over a fixed-length 128-bit field is sufficient and much simpler. –  Thomas Pornin Nov 14 '11 at 20:25
As for the complaint that a MAC needs to accept arbitrary length inputs, that's not actually true for existing accepted MACs. As one example, HMAC-SHA256 is limited to $2^{64}-513$ bits. I have yet to hear anyone complain about this restriction. –  poncho Nov 14 '11 at 21:42