Can we associate HMAC signed messages with each other? Assume:


$hmac(K, m) = M$
$hmac(K, m') = M'$


Can we associate that $M$ and $M'$ were signed by the same $K$?

Given $M$ and $M'$ and that we know they were signed with the same $K$, can we calculate the string similarity between $m$ and $m'$?

Edit: I originally asked the wrong question. The original question is known as a distinguishing attack and this paper (among many others) demonstrate it's possible.
To answer the new question, Mihir Bellare has proved that HMAC, applied to a Merkle&ndash;Damgård hash function such as the SHA-2 family, is a "privacy-preserving MAC" (PP-MAC) if the compression function of the underlying hash function is itself a PP-MAC.

Basically, the "privacy preserving" property means that even an attacker who gets to choose two equally long sequences of multiple (unique) messages, and submit them to an oracle who picks one of the sequences and returns the MACs of those messages (computed with a random secret MAC key) cannot tell with a non-negligible advantage which sequence the oracle picked.  (The actual PP-MAC game in the HMAC paper even allows the attacker to submit the messages to the oracle one pair at a time, and possibly adjust their later choices based on the returned information.)  

As far as I know, no attacks have been published on any widely used reputable* M-D type hash functions that would contradict the assumption that their compression function is a PP-MAC.  This includes the SHA-2 family, as well as the obsolete SHA-1, and even the really obsolete and broken MD5 hash.  (Indeed, the collision attacks on MD5, which violated the assumptions of the old HMAC-MD5 security proof, were the original motivation for this new proof.)

As for SHA-3 (Keccak), it's not actually a Merkle&ndash;Damgård hash, so the standard HMAC security proof does not directly apply to it.  However, I do believe that the original Keccak paper itself asserts the PRF (and thus PP-MAC) security of HMAC-SHA3, as a corollary of its "flat sponge claim".

*) To some extent, this is a circular claim, since any hash function whose compression function was demonstrably not a PP-MAC would almost certainly be viewed with plenty of justified suspicion, even if this somehow failed to affect its collision or preimage attack resistance.