$(9$ points$)$ Message authentication code. In this question, we are confronted with bad MAC

design. We have an $n-$bit key $K.$ Let $B_K$:$\{0,1{\}}^n\{0,1{\}}^n$ be a PRP secure block cipher.

Consider messages $m$ of length $3n$ bits. Write $m=m_1||m_2||m_3$ where $|m_1|=|m_2|=|m_3|=n.$

The symbol $||$ denotes concatenation of strings. Our MAC function is defined as:

$MA{C}_K(m)=B_K(\frac{?}{\text{b}\text{a}\text{r}}(m_1))o+B_K(m_3)||B_K(\frac{?}{\text{b}\text{a}\text{r}}(m_2)o+m_3).$

Consider a generation query of the form $m_1||1^n||m_3,$ that provides you with the tag $T=t_1||t_2.$

$($a$)$ Give explicit expressions for $t_1$ and $t_2.[$Hint: Your expressions will likely use $B_K.]$

$($b$)$ Show how you can make a forgery for this MAC function without making any other gener$-$

$2pt$

ation queries. $[$Show that a verification query on your forgery outputs that the tag is valid.

Hint: You can distill more information from the generation query than just the values $t_1$

and $t_2.]$