Proof of shared secret through key derivation
HMAC nor a KDF is needed here. As long as you always use a constant size key and "tag" (generally called a nonce, as in number-used-once) you can simply use a secure hash function, like SHA-256.

My suggestion is to drop keeping track of the tags sent so far - this administration is bound to fail at some point. Instead, generate a 32 byte random number. This reduces the chance of collision to a neglegible amount.

So if you use my proposed scheme:


Alice sends a 32-byte random number $n$ to Bob.
Bob replies with $H(K || n)$.
Alice checks the result.


Then an eavesdropper or even a MITM attacker will never learn $K$ faster than bruteforce.