Why is H(k||x) not a secure MAC construction?

Question

If H(m) is a secure hash function, can't we implement a MAC using H(k||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?

Answer 1

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 || 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-Damgard construction without a finalizing round, used in MD5 and SHA-1), 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-Damgard, 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||x)$ is the state of the hash machine after inputting $k||x||pad_x$. If we set our hash machine to this state, and then input arbitrary other data $y$, followed by another pad $pad_y$, we reach the state $m' = H(k||x||pad_x||y) = M(k, x||pad_x||y)$.
Forgery is done, with $x' = x || pad_x || y$.

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 does not guarantee unforgability for general secure hash functions, either, but it has a security proof for the Merkle-Damgard construction, if the internal compression function is collision-resistant.

Answer 2

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