62
$\begingroup$

If $H(m)$ is a secure hash function, can't we implement a MAC using $H(k\mathbin\Vert m)$?

However, it seems the more widely used MACs, such as NMAC and HMAC (both originally defined in Keying hash functions for message authentication) use a much more complicated scheme. Why is this concatenation scheme insecure?

$\endgroup$
1

2 Answers 2

48
$\begingroup$

The word "secure hash function" usually means (for a function $H$)

  • Preimage resistance: Given a value $h$, it is hard to find a message $x$ so that $h = H(x)$.
  • Second preimage resistance: Given a message $x$, it is hard to find a message $x' \neq x$ such that $H(x) = H(x')$.
  • Collision resistance: It is hard to find two messages $x$, $x'$ such that $H(x) = H(x')$.

For a secure MAC function $M$, we want:

  • Unforgability: Without knowing the key $k$, it is hard to find a message $x$ and authentication tag $m$ such that $m = M(k, x)$, even if given some other such valid message-tag pairs (which are not allowed as answers).

Unfortunately, defining $M(k,x) = H(k \mathbin\Vert x)$ for a secure hash function does not guarantee that the MAC function is unforgeable.

In fact, with the hash constructions used in practice (i.e. the Merkle-Damgård construction without a finalizing round, used in MD5, SHA-1 and the SHA-2 family), it is quite easy, given a valid pair $(x,m)$, to create an $(x', m')$ which is still valid:

To create a hash with Merkle-Damgård, the message is padded to some block size, and then each block in sequence is feeded to a compression function, which updates an internal state. The final state is then output as the hash.

So, $H(k\mathbin\Vert x)$ is the state of the hash machine after inputting $k\mathbin\Vert x\mathbin\Vert\mathit{pad}_x$. If we set our hash machine to this state, and then input arbitrary other data $y$, followed by another pad $\mathit{pad}_y$, we reach the state $m' = H(k\mathbin\Vert x\mathbin\Vert\mathit{pad}_x\mathbin\Vert y) = M(k, x\mathbin\Vert\mathit{pad}_x\mathbin\Vert y)$.
Forgery is done, with $x' = x \mathbin\Vert \mathit{pad}_x \mathbin\Vert y$.

This also works with the full-width variants of SHA-2, i.e. SHA-256 and SHA-512. For the truncated variants of SHA-2 (SHA-384, SHA-224, SHA-512/224 and SHA-512/256) this attack doesn't work, as the output is not the full hash state. (Though for a length extension attack only the truncated bits would have to be guessed, so the security is a bit less than expected from the output size.)

The HMAC construction is not suspectible to this attack, as the secret key $k$ is applied both before and after the main message, which makes the internal state non-reconstructible. HMAC ($H(k_2, H(k_1, M))$) first hashes the message with one version of the key prepended, so the internal state can't be reconstructed "from the beginning" (from the message). Then the (now secret) output is hashed again, with a second version of the key prepended. This makes it also impossible to reconstruct the internal state of the main hash "from the end" (i.e. from the output + message). A construction with similar effects would be $H(k_1 || M || k_2)$ (with appropriate padding), but that's not HMAC.

HMAC does not guarantee unforgeability for general secure hash functions, either, but it has a security proof for the Merkle-Damgård construction, if the internal compression function is collision-resistant.

SHA-3 (Keccak) is based on a different model: we have a quite big state into which both key and message are mixed, and which is then further mixed to output the hash. The state itself is never output fully. Because of this, length extension needs state recovery, and the capacity (the hidden part of the state) should be big enough that this is not feasible (and the key space needs to be big enough that guessing the key doesn't work either).

The paper On the security of the keyed sponge construction by the Keccak team analyzes the security of this construction.

$\endgroup$
8
  • $\begingroup$ Note that for SHA-3 (Keccak) there is now an algorithm defined called KMAC which is basically directly using the sponge based hash. It uses a slightly different configuration so it will not output the same value as the hash, but that's about it. $\endgroup$
    – Maarten Bodewes
    Commented Apr 14, 2020 at 18:17
  • $\begingroup$ You say "The HMAC construction ... the secret key 𝑘 is applied both before and after the main message ...", but that seems to be describing "sandwich" or "envelope" MAC, rather than HMAC. crypto.stackexchange.com/a/25476/32086 indicates that properly-constructed envelope MAC is secure (using the same k before and after m, even), but that is not HMAC; HMAC uses HMAC(k, m) = (H(k1 || H(k2 || m)) where k1 and k2 are derived by bitwise XOR of k with a fixed distinct "outer pad" and "inner pad" to ensure distinctness. $\endgroup$
    – CBHacking
    Commented Dec 10, 2021 at 0:29
  • $\begingroup$ @CBHacking This sentence is a simplification describing the effect, not a detail description of how it works. The "k2" in the inner H is the "apply the key before the message", the "k1" in the outer H is "apply the key after the message" in some way (at least the outer H completely destroys any ways of e.g. doing an extension attack). $\endgroup$ Commented Dec 10, 2021 at 12:42
  • $\begingroup$ Fair enough. I agree that it's technically valid (and obviously it's secure), but I do think it's confusing to use "before" in the sense of "prepend" and then "after" in the sense of "in a second operation". Since the envelope construction also prevents length extension attacks (at least, if done correctly), I think it's a very natural assumption (to anybody who doesn't know the details of the HMAC construction already) that it is how HMAC works. $\endgroup$
    – CBHacking
    Commented Dec 11, 2021 at 0:57
  • $\begingroup$ What is the difference between second preimage and collision resistances? In both cases it is target to not find x != x' where H(x) = H(x'), no? At least this his how I interpret your first part of the answer. $\endgroup$ Commented Dec 17, 2023 at 18:57
29
$\begingroup$

The reason $H(k\mathbin| m)$ (where $|$ is concatenation) is not the standard comes from the message extension attack. If I, as an attacker, have $H(k\mathbin|m)$ and $m$, I can compute $H(k\mathbin|m\mathbin|p\mathbin|m')$ (where $p$ is the padding that $H$ would have applied to $k\mathbin|m$ in computing the digest, and $m'$ is an arbitrary message) without knowing $k$. I would then send $H(k\mathbin|m\mathbin|p\mathbin|m')$ and $m\mathbin|p\mathbin|m'$ to the user. The message authentication check would succeed. Clearly this is an issue.

$\endgroup$
4
  • $\begingroup$ this may be a silly question, but how can you compute H(k|m|p|m') without knowing k? $\endgroup$ Commented Mar 22, 2015 at 1:03
  • 9
    $\begingroup$ nevermind. i found a worked example github.com/iagox86/hash_extender $\endgroup$ Commented Mar 22, 2015 at 1:36
  • $\begingroup$ Aside from a message extension attack (suppose all messages are fixed size), is there an issue? $\endgroup$ Commented Feb 3, 2017 at 21:45
  • 2
    $\begingroup$ @chux you should ask that as a separate question. $\endgroup$
    – mikeazo
    Commented Feb 4, 2017 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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