Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
The word "secure hash function" usually means (for a function $H$)
For a secure MAC function $M$, we want:
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.
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.
