Skip to main content
small typos.
Source Link
kelalaka
  • 49.5k
  • 12
  • 118
  • 205

The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be. But ignoring this fact for a moment, one of your observations was indeed crucial. A MAC does in general not hide it'sits input message. As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure. However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values. And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle. The CBC-MAC for our query will be computed as follows: \begin{align*} t_1 :=& F_k(0^n)\\ t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1) \end{align*} and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery. We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$: \begin{align*} t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\ t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1 \end{align*} And, given that $F$ is a secure MAC and it'sits output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf, and therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$? The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length presevingpreserving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC. Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$. I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack. For this, observe the values of $t_1,t_2$ in this instantiation. \begin{align*} t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\ t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1) \end{align*} I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$. Therefore the attack sketched above works with this instantiation.

The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be. But ignoring this fact for a moment, one of your observations was indeed crucial. A MAC does in general not hide it's input message. As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure. However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values. And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle. The CBC-MAC for our query will be computed as follows: \begin{align*} t_1 :=& F_k(0^n)\\ t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1) \end{align*} and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery. We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$: \begin{align*} t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\ t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1 \end{align*} And, given that $F$ is a secure MAC and it's output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$? The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preseving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC. Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$. I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack. For this, observe the values of $t_1,t_2$ in this instantiation. \begin{align*} t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\ t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1) \end{align*} I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$. Therefore the attack sketched above works with this instantiation.

The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be. But ignoring this fact for a moment, one of your observations was indeed crucial. A MAC does in general not hide its input message. As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure. However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values. And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle. The CBC-MAC for our query will be computed as follows: \begin{align*} t_1 :=& F_k(0^n)\\ t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1) \end{align*} and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery. We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$: \begin{align*} t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\ t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1 \end{align*} And, given that $F$ is a secure MAC and its output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible, and therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$? The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preserving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC. Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$. I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack. For this, observe the values of $t_1,t_2$ in this instantiation. \begin{align*} t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\ t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1) \end{align*} I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$. Therefore the attack sketched above works with this instantiation.

Source Link
Maeher
  • 7.1k
  • 1
  • 35
  • 45

The question as posed (in the book) is a bit weird, mainly because it does not state that $F$ is required to be length preserving, however for the CBC-MAC construction to make sense it clearly has to be. But ignoring this fact for a moment, one of your observations was indeed crucial. A MAC does in general not hide it's input message. As you point out, if $F'$ is a secure MAC, then the MAC $F$ defined as $F_k(m) := m\Vert F'_k(m)$ is also secure. However, if the function $F$ allows recovering its input from its output, then in the CBC-MAC construction we learn one of the intermediate values. And that is a problem.

Let's look at the case of $\ell=2$, i.e., messages have exactly two blocks, i.e., $m=m_0\Vert m_1$.

We attack the CBC-MAC by first choosing a message $m=0^n\Vert 0^n$ and querying it to the MAC oracle. The CBC-MAC for our query will be computed as follows: \begin{align*} t_1 :=& F_k(0^n)\\ t_2 :=& F_k(0^n\oplus t_1) = F_k(t_1) \end{align*} and $t_2$ is output as the tag.

Now, if $t_2$ allows us to recover the input of $F$, then this means we learn $t_1$.

We can now output the message $m^* = t_1\Vert t_2$ and the tag $t^*=t_1$ as our forgery. We can verify that this is indeed a valid forgery by recomputing $t^* = t^*_2$: \begin{align*} t^*_1 :=& F_k(m^*_1) = F_k(t_1) = t_2\\ t^*_2 :=& F_k(m^*_2\oplus t^*_1) = F_k(t_2\oplus t_2) = F_k(0) = t_1 \end{align*} And, given that $F$ is a secure MAC and it's output therefore necessarily unpredictable means that the probability of $m^*=m$ is negligible andf therefore our attacker is successful with all but negligible probability. (This can be generalized for an arbitrary message $m$, but I'll leave this as an exercise to the reader.)

The issue that remains is: How can we construct a length-preserving MAC such that we can reconstruct $t_1$ from $t_2$? The construction $F_k(m) := m\Vert F'_k(m)$ clearly does not work, since it is not length preseving, but we can do something similar.

Let $F'_k : \{0,1\}^n \to \{0,1\}^{n/2}$ be a secure MAC. Then we define $F$ as $F_k(x\Vert y) = y\Vert F'_k(x\Vert y)$ for $|x|=|y|=n/2$. I leave proving that this remains a secure MAC as an exercise to the reader.

It remains to show how this $F$ allows us to reconstruct $t_1$ given $t_2$ in the above attack. For this, observe the values of $t_1,t_2$ in this instantiation. \begin{align*} t_1 :=& F_k(0^n) = 0^{n/2}\Vert F'_k(0^n)\\ t_2 :=& F_k(t_1) = F'_k(0^n) \Vert F'_k(t_1) \end{align*} I.e., given $t_2 := a\Vert b$, we can directly see that $t_1 := 0^{n/2}\Vert a$. Therefore the attack sketched above works with this instantiation.