Proof of shared secret through key derivation

Question

Alice gives a random key $K$ (e.g. 32 bytes long) to Bob through a secure channel.

Bob want to prove to Alice through an unsecured channel that he knows the key.

• Is it secure for Bob to send $s||KDF(s||K)$ −with $s$ a random tag, say 8 bytes long− ? It seems Alice can recompute $KDF(s||K)$ and compare. Nobody can deduce K from the message.
• Provided tags are one time use only, and Alice keeps track of which have already been used, how many different proofs could Bob send before an observer could potentially figure out K ?
• Is there a way to improve that function ? Any specific key word, name of algorithm or protocol about that topic ?

Edit : I understand HMAC is the function I am looking for. Is it safe to use it for that purpose ? Can an observer learn anything about the key from many HMAC ?

Answer 1

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:

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

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