I want to guarantee the integrity of a message $m$. My first thought is to append the message to an integrity key $k$ and hash it as $H(k\,||\,m)$. However, I have been told that this is not totally secure, because an attacker can add more data to the end of $m$ while still generating the correct MAC.
How is it possible for an attacker to modify $H(k\,||\,m)$ such that the message is changed but the MAC is the same?
I was advised to use HMAC instead. Why does HMAC solve this problem?
It depends on the hash function you're using, but some hash functions work like repeated block ciphers (SHA1 and MD5, for example). The point is (as you've been told), an attacker can use the hash and continue appending data to generate a new and valid MAC.
That is, given $H(k||m)$, a valid MAC for $k||m$, an attacker can generate $H(k||m||m')$, a valid MAC for $k||m||m'$. This is undesirable behavior. We want to avoid the possibility of an attacker generating a valid MAC for any message, even if they don't know the key. This is why it invalidates integrity, because now an attacker can make valid messages and MACs (with limitations) when they don't know the key.
