23
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?)

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – Thomas Pornin Nov 14 '11 at 20:25
  • 6
    $\begingroup$ 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. $\endgroup$ – poncho Nov 14 '11 at 21:42
  • $\begingroup$ This answer claims that Proposition 4 in the Preneel–van Oorschot MDx-MAC paper is ‘theoretically a break relative to the security of HMAC’. This claim is false: the attack in Proposition 4 applies just as well to HMAC. All HMAC security claims involve a term of $O(q^2/2^b)$, e.g. the original 1996 Bellare–Canetti–Krawczyk paper describes it in terms of collision resistance (limited to a birthday bound) and the updated 2006 Bellare paper has $\binom{q}{2}$ in Theorem 4.3. $\endgroup$ – Squeamish Ossifrage Feb 16 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.