Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|improve this question

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.