# Proof of shared secret through key derivation

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 ?

-

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.

-
Hmm. I don't like using a key in an unkeyed construction. For example, if $H$ is SHA-256, make sure $n$ is always precisely 32 bytes (that is, left-pad with zeros to keep length constant). Edit: the conservative in me really wants to say go with HMAC, not a raw hash function (barring SHA-3). This is essentially the scenario it was designed for. – Reid Dec 26 '13 at 16:33
@Reid I already said that "as long as you always use a constant size key and tag". Otherwise you can use HMAC, yes. – orlp Dec 26 '13 at 16:39
Ah! My apologies; I didn't spot that. That's what I get for skimming. – Reid Dec 26 '13 at 16:46