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

Question

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

Is $(k,x) \mapsto H(k \mathbin\| \mathrm{len}(x) \mathbin\| 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?

Answer 1

What assumptions do we make of $H$, and what properties do we hope of $H'_k\colon m \mapsto H(k \mathbin\| \operatorname{len}(m) \mathbin\| m)$? Here are some reasonable choices:

1. $H$ is a random oracle, and we want $H'_k$ to be indifferentiable from a random oracle. In this case the prefix construction $m \mapsto H(k \mathbin\| m)$ already achieves this, so restricting ourselves to those messages that begin an encoding with their own length couldn't possibly change it.

2. $H$ is BLAKE2, SHA-3, or another modern ‘hash function’, and we want $H'_k$ to be a pseudorandom function family. In this case, $H$ was designed so that $m \mapsto H(k \mathbin\| m)$ is already conjectured to be a PRF, so restricting ourselves to those messages that begin an encoding with their own length couldn't possibly change it. (Also these all have native PRF constructions: keyed BLAKE2, KMAC. So the point is largely moot.)

3. $H$ is MD5, SHA-1, or another Merkle–Damgård hash function with some modest security properties conjectured of the underlying compression function—whatever properties we need for the favored security claim of HMAC du jour. This is presumably the main case of interest. The answer is essentially yes, this is as secure as HMAC with a much simpler proof.

   • Obviously, there is a generic attack finding an internal collision as described in 1996 by Preneel and van Oorschot in Proposition 4 of the MDx-MAC paper[1]—which is exactly the same as for HMAC, and for any iterated function, with query cost proportional to the square root of the number of possible intermediate states.^*

   • Also in 1996, Bellare, Canetti, and Krawczyk studied what they called ‘the cascade construction’[2], and showed that if $F_k\colon m \mapsto F(k, m)$ is a PRF, then the cascade $$F^*_k\colon (m_1, m_2, \dots, m_n) \mapsto F(F(\dots F(F(k, m_1), m_2) \dots), m_n)$$ is almost a PRF—specifically, $F^*_k$ is indistinguishable from a uniform random function to any adversary that never queries it for any message that is a prefix of another message. $F^*$ is also not quite an application of a Merkle–Damgård function, because the key $k$ has replaced the role of the IV, but it's not a stretch to assume that $k \mapsto F(\mathit{IV}, k)$ is a pseudorandom generator, and $H(k \mathbin\| m) = F^*_{F(\mathit{IV}, k)}(m)$ (modulo fenceposts around block sizes).

     Under these modest assumptions (and with a much simpler proof than anything in the continuing saga of HMAC), the function $m \mapsto H(k \mathbin\| m)$ is almost a PRF in the above sense. If we apply any prefix-free encoding of messages before feeding them to this, then we get a PRF, which by the usual theorem is also a MAC. And length-delimiting $m \mapsto \operatorname{len}(m) \mathbin\| m$ is an example of a prefix-free encoding.

---

_{^* Only for small hash functions like MD5 is this potentially a concern—for SHA-256, it is totally unimaginable—but even for MD5 it requires $2^{64}$ queries to the oracle, not $2^{64}$ offline computations. Can your application server handle $2^{64}$ queries before humanity cooks the planet? I doubt it! (Hint: Suppose your server takes one nanosecond to answer a query. How many years is $2^{64}$ nanoseconds?)}

Answer 2

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.