HMAC tag to verify the key (verification in the reverse direction)

Question

A quick question. Are there any problems with the following HMAC use-case:

We have two entities ($A$ and $B$), both of them have a secret ($A$ has $S_0$ and $B$ has $S_1$)

$A$ generates a random value $r$ and calculates the following tag: $t=HMAC(S_0,r)$
$A$ then sends $(r,t)$ to $B$.
$B$ calculates $t' = HMAC(r,S_1)$.

If the comparison $t' = t$ is true, does that imply that $S_0 = S_1$?

We are flipping the HMAC use-case around, instead of checking the authenticity of our message $r$, we are implying the reverse. And because HMAC is provable bound to the pre-image properties of the underlying hash, if the hash is secure, so is this use-cause (I did not write any formal reasoning or so, but my feeling is that if this is not true, then the security of the HMAC is not true).

Note that this is not true for encryption functions (mac then encrypt). CCA2 and ciphertext indistinguishability rule this use-case out (encryption is no authentication). But HMAC is an authentication scheme.

I just thought of this, so maybe I'm looking over something trivial.

Thanks!

Answer 1

It looks fine; whether you use the secret $S_0, S_1$ as the HMAC key, or whether you use the random value $r$ as the HMAC key; if $t' = t$, it implies that either $S_0 = S_1$, or we found a collision in the underlying hash function.

I would personally suggest you use $S_0, S_1$ as the key. With HMAC, it doesn't really matter; however if we extend this to other Message Authenticate Codes, it does. For example, if we were to use this idea to CMAC, well, if we're given the values $CMAC_r(S_0)$ and $r$, we can compute two plausible values of $S_0$ if it's at most 16 bytes long. Using the secret values $S_0, S_1$ as the key prevents this; instead, you'll be relying on the security properties of the MAC.

One last note: this scheme also has a problem if $S_0, S_1$ has low entropy (that is, they appear in a dictionary that the attacker might have); in that case, an attacker can go through his dictionary, and check for matches. If this is a concern, you'll see some type of password authenticated key exchange; they handle this case better (but they are also rather more complicated to implement)