If a PPT adversary can influence the key of a MAC function, is it still secure?

For example, if we define $f$ as follow:

$f(r,x) = HMAC_{(k\oplus r)}$(x)

If the adversary has oracle access to $f$, how likely he can predict the key $k$?

For respecting the persons who have answered the above question, I do not change it. The actual scenario is as follows:

I have a module that gets $(m,r)$ and generates $(m,x,HMAC_{k \oplus r}(m \parallel x))$ where the $k$ is the secret of the module and $x$ is the message added by the module. So:

$f(m,r)=(m,x,HMAC_{k \oplus r}(m \parallel x))$

Can I claim that every tuple $(m,x,t)$ s.t. $t=HMAC_{k \oplus r}(m \parallel x))$ is generated by the module?

P.S. I am still curious about the above claim. But, I just noticed that if I change $f$ as follows:

$f(m,r)=(m,x,HMAC_k(m \parallel x \parallel r))$

then, I can claim every tuple $(m,x,t)$ s.t. $t=HMAC_k(m \parallel x \parallel r))$ is generated by the according to the definition of MAC.

  • $\begingroup$ What can $r$ depend on? $\endgroup$
    – Maeher
    Oct 27, 2019 at 9:36
  • $\begingroup$ If an adversary has access to such an f, this is called related-key attack security. $\endgroup$
    – SEJPM
    Oct 27, 2019 at 11:23
  • $\begingroup$ @Maeher $r$ is an arbitrary input $\endgroup$
    – Reza
    Oct 27, 2019 at 13:19
  • 1
    $\begingroup$ When you say ‘HMAC’, do you really mean only HMAC (with an unspecified hash function) and not an arbitrary MAC? $\endgroup$ Oct 27, 2019 at 15:35
  • 2
    $\begingroup$ @MaartenBodewes Because in HMAC, the key $k$ is used once via $k \oplus \mathrm{ipad}$ and once via $k \oplus \mathrm{opad}$, which will interact rather easily with the pattern of related keys allowed, potentially leading to trouble. (Also see SEJPM's citation. on HMAC with related keys.) $\endgroup$ Oct 31, 2019 at 16:32

1 Answer 1


If a PPT adversary can influence the key of a MAC function, is it still secure?

In general probably no if you make no restrictions on the ways the key can be influenced. In particular the answer is "no" when you rely on your MAC actually being a PRF for your security proof (like HMAC does). This means that if your MAC relies on this then you need some additional argument for related-key security, as PRFs cannot be secure against all classes of related-keys. For a proof and more background on this see Proposition 8.4 of the original paper that introduced this (PDF).

If the adversary has oracle access to $f$, how likely he can predict the key $k$?

Cryptography isn't about "can you predict the key" because you can usually build schemes that don't use their key-input and are thereby trivially secure if all you want is the key.

A more interesting question would be, if an attacker has access to (this concrete) $f$, how easy is it to forge tags? This has in fact been studied for HMAC and keys related by a constant leading to an attack that runs in time $2^{n/2}$ with $n$ being the HMAC's output length.

  • $\begingroup$ "In particular the answer is "no" when your MAC also happens to be a PRF (like HMAC is)." Just because it's no longer a PRF under a related key attack does not mean it can't still be a secure MAC. But the actual attack scenario in the question is still underspecified. $\endgroup$
    – Maeher
    Oct 27, 2019 at 14:31
  • $\begingroup$ @Maeher ok, I edited to clarify that "only" the proof breaks and not neccessarily security (though of course one shouldn't rely on unproven security) $\endgroup$
    – SEJPM
    Oct 27, 2019 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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