Prove that two MACs with incremendal PRF application are not secure How do I prove the following MACs are insecure?


          


                                            1
                                     
                                            2
The following was originally written as an edit to the question, but I'm going to put it here instead because I think formalizing the schemes might well provide you with enough of a hint for you to solve this question yourself:



Let $f(k,m)$ be a pseudo-random function, taking as inputs a key and a message, and outputing a value of the same length as the key (eg AES-128).

Why are the following MACs not sure?


[ref]
$\tau = c_i \oplus c_2 \dots \oplus c_n$, where $c_i=f(k,m_i)$.
[ref] $c_0=k$, $c_i=f(c_{i-1},m_i)$ for $i=1,\dots,m$ and $\tau=c_n$




To prove something insecure, we provide an explicit adversary. That is, we provide a method for doing what the security model says we shouldn't be able to.

In this case, that means we need are allowed to ask the system to provide us with the tag on some messages $\mathcal{M}=\{M_1,M_2,\dots\}$. Then, we create a valid tag for some message $M'\notin\mathcal{M}$.

So, a more direct hint: If you have the MAC of message $M=(m_1,\dots,m_n)$, can you construct...


Another message with the same tag?
A longer message who's tag you can calculate?