Assume $tag[i]=\operatorname{MAC}(key[i],msg)$
Now we know:
- $tag[0],tag[1],\ldots,tag[n]$
- $key[0],key[1],\ldots,key[n]$
Can we get the $msg$ from this?
Or can we get the $tag$ of this $msg$ using a known key?
Assume $tag[i]=\operatorname{MAC}(key[i],msg)$
Now we know:
Can we get the $msg$ from this?
Or can we get the $tag$ of this $msg$ using a known key?
Can we get the $msg$ from this?
Yes, as long as we know the nonces, and as long as $msg$ is no more than $128n$ bits long, and $n$ isn't too incredibly huge (the latter might not be a required assumption, I just need it for my approach).
Poly1305 can be modeled as computing a tag this way:
$$tag = c_a r^a + c_{a-1} r^{a-1} + … + c_1 r^1 + z - 2^{128} k \bmod {2^{130}-5}$$
where (in your scenario) you know the value $r$ and $z$ (they're a function of the key and the nonce, which you know) and don't know the values $c_a, c_{a-1}, …, c_1$ (that's an encoding of the message) and the value $k$ (which is between 0 and 3); $k$ is here to account for the outer '$\bmod 2^{128}$ operation that Poly1305 performs.
If we have $n$ such tags, we can set this up as $n$ simultaneous linear equations in the unknown $c_a, c_{a-1}, …, c_1$ variables. We don't know the $k$ variables, hence we would need to go through the $4^{n}$ combinations of the $n$ different $k$ variables, and solve each one individually (and after obtaining a solution, we would check the message to see if Poly1305 processes the message as expected - it may encode the message to a different set of $c$ variables, or assign a different value for a $k$ variable.
If $n \ge a$, this gives us enough equations to find a solution; if $n > a$, this solution is likely to be unique.
This involves assuming $4^{n}$ sets of $n$ linear equations; as long as $n$ isn't too large, this is practical.