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?

  • $\begingroup$ If you know all the intermediate states of the tag (as you've currently indicated in the question), then yes, it's possible as the Poly1305 arithmetics are reversible. $\endgroup$
    – DannyNiu
    Dec 29 '19 at 11:48

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.

  • $\begingroup$ @kelalaka: could you expand on your comment? I have no idea what you're trying to say $\endgroup$
    – poncho
    Jan 2 '20 at 20:43
  • $\begingroup$ If I've understood correctly, the longer messages are safe from this attack, right? That is why I said speak more to be safe. $\endgroup$
    – kelalaka
    Jan 2 '20 at 20:44
  • $\begingroup$ @kelalaka: well, longer messages are computationally less vulnerable against this (hard to call this an 'attack', as Poly1305 was never designed to be strong against this), and if the length of the message is > n, then obviously the message cannot be uniquely determined (by any method). $\endgroup$
    – poncho
    Jan 2 '20 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.