How can finding a collision help an attacker with tampering messages with HMAC As stated in the HMAC RFC (RFC 2104):


  The strongest attack known against HMAC is based on the frequency of collisions for the hash function H.


How can a collision benefit an attacker? I would have thought that the strongest attack would be a brute force attack aimed at discovering the secret key.
From that same document:


  In any case the minimal recommended length for K is L bytes (as the hash output length).


So as long as the key is fully randomized, i.e. a cryptographically strong key, the time for brute forcing is at least the same or higher than the time finding a collision. If your key is indeed smaller or not fully randomized, then brute forcing attacks may indeed apply.

If you can find a collision, then you could possibly replace the message. But the hash would still be dependent on the key, so you should see this as a strict lower bound. An attacker would still not break HMAC by only finding a collision (otherwise HMAC with MD5 would be broken by now).

For instance, Wikipedia mentions:


  The cryptographic strength of the HMAC depends upon the size of the secret key that is used. The most common attack against HMACs is brute force to uncover the secret key. HMACs are substantially less affected by collisions than their underlying hashing algorithms alone.Therefore, HMAC-MD5 does not suffer from the same weaknesses that have been found in MD5.