# 3 blocks CBC-MAC

Let $M=(m_1, m_2)$, $M'= (m_0', m_1')$ be two two-block messages.

In other words, $|m_1|=|m_2|=|m_1'|=|m_2'|=n$.

We say that $M, M'$ collide for key $k$ if

$$E_k(E_k(m_1)⊕m_2) = E_k(E_k(m_1')⊕m_2').$$

How many two-block messages should one sample from $\{0, 1\}^{2n}$ s.t. with probability $≥ 1/2$ two (distinct) sampled messages collide?

I tried this approach:

Let $r$ be the number of samples.

Let $M,M'$ be two samples, since $E_k$ is a bijection:

$$\text{P}[E_k(E_k(m_1)⊕m_2) = E_k(E_k(m_1')⊕m_2')]=\text{P}[E_k(m_1)⊕m_2=E_k(m_1')⊕m_2']=\text{P[two random strings are equal]}=2^{-n}$$

So, $\text{P}[E_k(E_k(m_1)⊕m_2) \neq E_k(E_k(m_1')⊕m_2')]=1-2^{-n}$.

Therefore, $\text{P[two samples of the$r$samples collide]}=1-\big(1-2^{-n}\big)^{\binom{r}{2}}$.

Now, we need to take a minimal $r$ s.t. $1-\big(1-2^{-n}\big)^{\binom{r}{2}}\geq\frac{1}{2}$.

Is it true? I suspect not because afterwards we need to use $r$ to prove that a $\text{CBC-MAC}$ with $3$ blocks is not secure.

If $E_k$ is a permutation, then this is a case of the birthday problem, with number of elements $d=2^n$. The probability of not finding a collision in $r$ uniformly distributed independent samples is $p(r)=\prod\limits_{k=1}^{r-1}\left(1-\frac{k}{d}\right)\le \prod\limits_{k=1}^{r-1}e^{-\frac{k}{d}}=e^{-\frac{1+2+...+(r-1)}{d}}\le e^{-\frac{r^2}{d}}$, thus:
$\Pr\left[\text{finding a collision}\right]=1-p(r)\ge 1-e^{-\frac{r^2}{d}}\ge\frac{1}{2}$ for $r\ge\sqrt{\ln 2 \cdot d}$.