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

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?

-

## 2 Answers

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.

-

Thanks to the anonymous editor who corrected my $H(x) \neq H(x')$ to $H(x) = H(x')$. – Paŭlo Ebermann♦ May 14 at 19:58

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 39, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8997053503990173, "perplexity_flag": "middle"}