8
$\begingroup$

Given a secure MAC scheme $ \Pi=(Gen, Mac, Vrfy) $, wheres $ Gen $ produces uniformly distributed keys, and the algorithm $ Mac $ is deterministic, is $ Mac $ necessarily a pseudorandom function?

I think that it is a PRF: since there is no forger A that can somehow obtain information from the given tags, and thus deduce something about how the $Mac$ function is built (i.e. how a tag is created), I conclude that there's no distinguisher D that can distinguish between a tag and a random string emitted by a random function.

Is my intuition right? If not, I'd like to have some intuition as to why a deterministic MAC can't be a PRF. (An example of such a MAC would be great.) If yes, further intuition would be great as well.

$\endgroup$
  • 4
    $\begingroup$ Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC obtained by appending a bunch of zeros at the end of the tag is secure as well but of course it's not a pseudorandom function $\endgroup$ – Daniel Apr 5 '17 at 12:31
  • $\begingroup$ Good answers in here already, but I'll point to this question as containing an additional example of a construction that would be a good MAC but not a PRF. $\endgroup$ – Luis Casillas Apr 6 '17 at 0:37
10
$\begingroup$

Your intuition is not right. The fact that no forger can obtain new valid message/tag pairs doesn't say anything about the "shape" of the MAC. For instance, if $\Pi$ is a secure MAC, then the MAC obtained by appending a bunch of zeros at the end of the tag is secure as well:

If a forger $\mathcal{A}$ is able to create a new and valid message/tag pair $(m,t)$ for our modified MAC (the one obtained by appending the zeros to a secure MAC), then $(m,t')$ would be a new and valid message/pair for $\Pi$, where $t = t'||0^n$ (you would need to be more precise with the games being played here, but the idea is that any msg/tag pair for one MAC corresponds to one msg/tag pair for the other)

But of course this is not a pseudorandom function.

I think your intuition is that a secure MAC can not reveal anything about the underlying message, but this is not right. The security of a MAC relies on the hardness of generating new messages/tag pairs, not in the difficulty of learning anything about the underlying message. In fact, a MAC can reveal the whole message! can you imagine how?

$\endgroup$
  • $\begingroup$ Thank you! but still -1. If a MAC can reveal the whole message, why does it imply that the tag generating function * may * not be PRF? 2. "MAC obtained by appending a bunch of zeros at the end of the tag is secure as well but of course this is not a pseudorandom function"- is it true for every MAC obtained as above? i don't understand why its not a PRF. $\endgroup$ – Alex Goft Apr 5 '17 at 13:20
  • 1
    $\begingroup$ @AlexGoft My point is that it is not true that every secure MAC must be a PRF (for instance, the one obtained by appending a bunch of zeros to an already secure MAC is not a PRF but it is secure), but of course, there may be some secure MAC's that are PRF's as well (even if they reveal the whole message). $\endgroup$ – Daniel Apr 5 '17 at 13:23
  • $\begingroup$ @Daniel: Actually, regarding the parenthetical note at the end of your comment, a MAC that reveals the whole input message to an attacker who doesn't know the MAC key (or even allows them to guess it with non-negligible advantage) cannot be a PRF, because that property would allow an attacker to distinguish a random instance of the PRF from a random function. It can, of course, still be a secure MAC. $\endgroup$ – Ilmari Karonen Apr 5 '17 at 13:40
  • $\begingroup$ @Ilmari oh god, you're right, how could I miss that. Thanks! $\endgroup$ – Daniel Apr 5 '17 at 13:43
  • 1
    $\begingroup$ @Elias: No, because the attacker is assumed to know (and, under the usual MAC security definition, to even be able to choose) the inputs for any legitimate MACs computed by the challenger. The attacker's task is to produce a forgery, i.e. a message/token pair which is accepted as valid without having been previously generated by the challenger. $\endgroup$ – Ilmari Karonen Apr 5 '17 at 15:50
6
$\begingroup$

As an extension of Daniel's answer, let me provide an explicit construction of a non-PRF MAC scheme like he describes.

I will start by assuming that $\Pi = (Gen, Mac, Vrfy)$ is a secure deterministic MAC scheme (which may or may not be a PRF), and I'll use it to construct a second MAC scheme $\Pi' = (Gen', Mac', Vrfy')$ which is also a secure MAC (in the sense that any attacker who can break $\Pi'$ can also break the original scheme $\Pi$) but which is explicitly not a PRF.

Specifically, let $[a,b]$ denote some unambiguously decodable encoding of the pair of strings $a$ and $b$, and let:

  • $Gen' = Gen$,
  • $Mac'_k(m) = [Mac_k(m), m]$, and
  • $Vrfy'_k(m, \tau') = \textsf{true}$ if and only if:
    • $\tau' = [\tau, m]$ for some string $\tau$, and
    • $Vrfy_k(m, \tau) = \textsf{true}$.

That is, the tags generated by $Mac'$ include a copy of the full input message, and $Vrfy'$ includes an extra check that this copy indeed matches the message the tag is being verified against.

Clearly, $\Pi'$ is a valid MAC scheme, in the sense that $Vrfy'_k(m, Mac'_k(m)) = \textsf{true}$ for any $k \leftarrow Gen'$. Also, by construction, given oracle access to $Mac_k$ and $Vrfy_k$ instantiated with a random key $k \leftarrow Gen$, we can easily simulate $Mac'_k$ and $Vrfy'_k$. Thus, given any adversary $A'$ against the modified scheme $\Pi'$, we can trivially convert it into an equally effective adversary $A$ against the original scheme $\Pi$ by replacing all calls to $Mac'_k$ and $Vrfy'_k$ with their simulated equivalents, and removing the redundant copy of the message from the tag in the final forged output.

If the adversary $A'$ would succeed in forging a message against $\Pi'$ with a non-negligible advantage, then so $A$ would have (at least) the same advantage against $\Pi$. Conversely, this implies that if no such adversary exists against $\Pi$, then none can exist against $\Pi'$ either, and so that the modified scheme $\Pi'$ is (at least) as secure (as a MAC) as the original scheme $\Pi$.

(The subtle part here is that, by the definition of the MAC security game, $A$ fails if it outputs a pair $(m, \tau)$ after having previously received the tag $\tau$ by querying $Mac_k(m)$. But it's easy enough to show that, for this to happen with our constructed adversary $A$, the simulated adversary $A'$ would have had to output $(m, [\tau, m'])$ for some $m'$ in the same situation. If $m' \ne m$, then $A'$ would've failed anyway; otherwise, $A'$ would've previously received $[\tau, m]$ as a response to its simulated query for $Mac'_k(m)$, and so would've also failed.)

On the other hand, $(Gen', Mac')$ is obviously not a PRF over any codomain, at least as long as the message space includes more than one possible message. In particular, let $m_1$ and $m_2$ be two distinct valid messages. Then $Mac'_k(m_1) = [\tau_1, m_1]$ and $Mac'_k(m_2) = [\tau_2, m_2]$ for some arbitrary tags $\tau_1$ and $\tau_2$, whereas, for a random function $f$ with the same domain and codomain, it is (by definition) equally likely that $f(m_1) = [\tau_2, m_2]$ and $f(m_2) = [\tau_1, m_1]$.

This lets us trivially construct a distinguisher: just pick a random input message $m$, query for the corresponding output $f(m)$, and output $\textsf{true}$ if $f(m) = [\tau, m]$ for some tag $\tau$ and $\textsf{false}$ otherwise. This distinguisher will thus always output $\textsf{true}$ if $f = Mac'_k$ for some $k \leftarrow Gen'$, but has at least a 50% chance of outputting $\textsf{false}$ if $f$ is a random function with the same (or larger) codomain as $Mac'$.

$\endgroup$
  • $\begingroup$ This is what I meant when I said that we must be careful with the security games being played here. Thanks a lot for your extension! $\endgroup$ – Daniel Apr 5 '17 at 16:23
6
$\begingroup$

This is not a PRF, as answered by @Daniel. However, your intuition is somewhat right in the sense that the MAC tag must have good entropy and so goes a considerable way towards being a PRF. You may be interested in the paper From Unpredictability to Indistinguishability: A Simple Construction of Pseudo-Random Functions from MACs by Reingold and Naor. They show how to simply construct a PRF from a MAC. (Of course, this was not your question, but it's related.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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