<p>A <em>message authentication code</em> (MAC) is defined by a triple of efficient algorithms $(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$, which satisfy the following (the definition is taken from section 4.3 of the <a href="http://rads.stackoverflow.com/amzn/click/1584885513">Katz-Lindell book</a>):</p>

<ul>
<li>On input $1^n$, the algorithm $\mathsf{Gen}$ generates a key $k \ge n$.</li>
<li>On input $k$ generated by $\mathsf{Gen}$, and some message $m \in \{0,1\}^*$, the algorithm $\mathsf{MAC}$ generates a tag $t$. We write $t \gets \mathsf{MAC}_k(m)$.</li>
<li>On input a triple $(k,m,t)$, the algorithm $\mathsf{Verif}$ generates a single bit $b$. We write $b \gets \mathsf{Verif}_k(m,t)$.</li>
</ul>

<p>It is required that for all $k$ output by $\mathsf{Gen}$ and all $m \in \{0,1\}^*$, we have $\mathsf{Verif}_k(m, \mathsf{MAC}_k(m)) = 1$.</p>

<p>The security requirement is defined via the following experiment, between the challenger and the adversary $A$:</p>

<ol>
<li>$k \gets \mathsf{Gen}(1^n)$.</li>
<li>$(m,t) \gets A^{\mathsf{MAC}_k(\cdot)}(1^n)$.</li>
<li>Let $Q$ denote the set of all queries that $A$ asked to its oracle.</li>
<li>The output of the experiment is defined to be 1 if and only if:
<ul>
<li>$\mathsf{Verif}_k(m, t) = 1$, and</li>
<li>$m \notin Q$.</li>
</ul></li>
</ol>

<p>The MAC is considered secure if the probability that the experiment outputs 1 is negligible in $n$.</p>

<hr>

<p>The experiment above resembles a "chosen plaintext" experiment against a symmetric encryption scheme, where the adversary can obtain ciphertexts corresponding to messages of his choice. In a more powerful attack, called "chosen ciphertext" attack, the adversary is allowed access to a decryption oracle as well.</p>

<p>So, my question is:</p>

<blockquote>
  <p>What happens if we allow the MAC-adversary to access a verification oracle as well? In other words, what if line 2 of the experiment is replaced with the following:</p>
  
  <p>$(m,t) \gets A^{\mathsf{MAC}_k(\cdot),\ \ \mathsf{Verif}_k(\cdot, \cdot)}(1^n)$.</p>
  
  <p>Notice that in the new experiment, $Q$ only includes queries $A$ asks from the $\mathsf{MAC}_k$ oracle.</p>
</blockquote>

CC BY-SA 3.0
2017-06-11T11:01:06.887Z
**For future reference:** See [The Power of Verification Queries in Message Authentication and
Authenticated Encryption](https://eprint.iacr.org/2004/309.pdf) for further discussions.
Sadeq Dousti
<cr.crypto-security>
Secure MAC when the adversary has a verification oracle
Sadeq Dousti
# Secure MAC when the adversary has a verification oracle

(Asked by: username_0 on 2014-02-08)

A *message authentication code* (MAC) is defined by a triple of efficient algorithms $(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$, which satisfy the following (the definition is taken from section 4.3 of the [Katz-Lindell book](http://rads.stackoverflow.com/amzn/click/1584885513)):

* On input $1^n$, the algorithm $\mathsf{Gen}$ generates a key $k \ge n$.
* On input $k$ generated by $\mathsf{Gen}$, and some message $m \in \{0,1\}^\*$, the algorithm $\mathsf{MAC}$ generates a tag $t$. We write $t \gets \mathsf{MAC}\_k(m)$.
* On input a triple $(k,m,t)$, the algorithm $\mathsf{Verif}$ generates a single bit $b$. We write $b \gets \mathsf{Verif}\_k(m,t)$.

It is required that for all $k$ output by $\mathsf{Gen}$ and all $m \in \{0,1\}^\*$, we have $\mathsf{Verif}\_k(m, \mathsf{MAC}\_k(m)) = 1$.

The security requirement is defined via the following experiment, between the challenger and the adversary $A$:

1. $k \gets \mathsf{Gen}(1^n)$.
2. $(m,t) \gets A^{\mathsf{MAC}\_k(\cdot)}(1^n)$.
3. Let $Q$ denote the set of all queries that $A$ asked to its oracle.
4. The output of the experiment is defined to be 1 if and only if:
   * $\mathsf{Verif}\_k(m, t) = 1$, and
   * $m \notin Q$.

The MAC is considered secure if the probability that the experiment outputs 1 is negligible in $n$.

---

The experiment above resembles a "chosen plaintext" experiment against a symmetric encryption scheme, where the adversary can obtain ciphertexts corresponding to messages of his choice. In a more powerful attack, called "chosen ciphertext" attack, the adversary is allowed access to a decryption oracle as well.

So, my question is:

> What happens if we allow the MAC-adversary to access a verification oracle as well? In other words, what if line 2 of the experiment is replaced with the following:
>
> $(m,t) \gets A^{\mathsf{MAC}\_k(\cdot),\ \ \mathsf{Verif}\_k(\cdot, \cdot)}(1^n)$.
>
> Notice that in the new experiment, $Q$ only includes queries $A$ asks from the $\mathsf{MAC}\_k$ oracle.

**Tags:** cr.crypto-security

> **Comments:**
> **username_0**: **For future reference:** See [The Power of Verification Queries in Message Authentication and Authenticated Encryption](https://eprint.iacr.org/2004/309.pdf) for further discussions.  

---

## 0 answers

