Does having more than one HMAC provide more information to the attacker?

Suppose $$N$$ many messages has been sent from $$A$$ to $$B$$ in this format:

• $$\operatorname{HMAC}(K, C(i)) \mathbin\| C(i)$$.

Where

• $$C(i)$$ is some cipher-text encrypted with some secure algorithm using some key
• $$K(i) \ne K$$ for any $$i$$ in range $$[0, N-1]$$.

There is no implication whether $$K(i) = K(j)$$ for any $$i \ne j$$.

Thus, it is just "some" encryption algorithm but encryption key used to encrypt the message is not directly equal to $$K$$, the key for HMAC which is constant for each $$N$$ messages.

Now my question is:

If the attacker captures these $$N$$ messages and $$\operatorname{HMAC}$$s, does it give any more advantage to the attacker than just "brute-forcing" the key $$K$$ to find it (whether he can draw some conclusions, etc)? We can say that the cryptographic hash function used in the $$\operatorname{HMAC}$$ is secure.

• Having access to multiple $T_i$ and $M_i$ where $T_i=\text{HMAC}(K, M_i)$ is known should not give you any information about $K$ (other than allowing to evaluate if $K$ is correctly guessed). So I surmise that this doesn't provide any information to the attacker by extension; the creation of the ciphertext is nothing other than a function to generate $M_i$ after all. Apr 15 at 1:18
• As in Wikipedia: "A secure message authentication code must resist attempts by an adversary to forge tags, for arbitrary, select, or all messages, including under conditions of known- or chosen-message. It should be computationally infeasible to compute a valid tag of the given message without knowledge of the key, even if for the worst case, we assume the adversary knows the tag of any message but the one in question.[3] " Calculating a message using whatever function is strictly weaker than that notion. Apr 15 at 1:45
• @MaartenBodewes: It's a good answer. Comments can be deleted. I'd suggest you convert your comments to an answer. Apr 15 at 2:41
• I've done so, but I'd be happy if somebody else would create a more scientific argument based on e.g. the NMAC security proof & more focus on the possibilities of collisions. Apr 15 at 20:31

1 Answer

As stated on Wikipedia with regards to MAC security: "A secure message authentication code must resist attempts by an adversary to forge tags, for arbitrary, select, or all messages, including under conditions of known- or chosen-message. It should be computationally infeasible to compute a valid tag of the given message without knowledge of the key, even if for the worst case, we assume the adversary knows the tag of any message but the one in question. [3]" Calculating a message using whatever function is strictly weaker than that notion.

Although the reference is a bit suspect, it is corroborated by the security proof by Rybar on NMAC / HMAC security, where it is stated that "The adversary $$A$$ is given input $$1n$$ and oracle access to $$\text{Mac}_k(·)$$"

Having access to multiple $$T_i$$ and $$M_i$$ where $$T_i=\text{HMAC}(K, M_i)$$ is known should not give you any information about $$K$$ (other than allowing to evaluate if $$K$$ is correctly guessed). So I surmise that this doesn't provide any information to the attacker by extension; the creation of the ciphertext is nothing other than a function to generate $$M_i$$ after all.

This does presume a random (and therefore unrelated) key for HMAC of course, but that's stated in the question as a given.