Poly1305 reuse of r

Poly1305 uses $$r, r^2, r^3$$ and $$r^4$$. I understand this if $$r$$ is a generator of the finite field. But since $$r$$ can be any random non-zero number, won't its exponents be non-uniform distributed? That is, even if $$r$$ is chosen with uniform random over the field, $$r^4$$ is not uniform over the field. Why isn't this a weakness?

Note that Bernstein's papers* use similar schemes for any finite field, using up to $$r^8$$, implying that they are acceptable for any finite field.

* Section 4.2 of https://cr.yp.to/antiforgery/pema-20071022.pdf uses $$r$$ 8 times, each with a higher exponent.

• What do you mean by "up to r^8"? Sep 5, 2021 at 8:57
• @Fractalice Edited with answer Sep 6, 2021 at 0:39
• Thanks, I see 8 times but I still don't see "each with a higher exponent" there. Sep 6, 2021 at 8:02

Indeed, modulo a prime, already $$r^2$$ are non-uniform - only half of the values are possible. While the computed polynomials indeed do not follow uniform distribution, the non-uniformity is bounded: each output value of the polynomial may have at most $$L$$ preimages (roots), where $$L$$ is its degree, equal to the number of blocks. Meaning that the probability may increase from $$1/R$$ to $$L/R$$, where $$R$$ is the number of all possible $$r$$ (which is $$2^{106}$$ in Poly1305). To get a non-negligible success probability, one has to attempt a forgery with a huge number of blocks.

Note that the output is masked by adding AES(nonce). This makes blind prediction of the MAC useless. The most powerful attack here is a differential forgery attempt: given a (message, nonce, tag) triple, generate another triple (message', nonce, tag'). The same nonce removes AES(nonce) from the consideration in the difference $$(tag' - tag)$$. We "only" have to predict poly(message') - poly(message) for any message and message' of our choice. Which is hard since a difference of non-equal polynomials is still a nonzero polynomial of the same or smaller degree, and the probability to guess the right output is small.

This reasoning works for any finite field.

edit: thanks to @poncho for noticing a dangerous confusion of xor and addition over GF(p)

edit: in https://cr.yp.to/antiforgery/pema-20071022.pdf , Bernstein first introduces a dot-product-based MAC, i.e.. $$MAC(m) = m_1r_1 + m_2 r_2 + ... + s$$. The $$n=8$$ shares are chosen only for an illustration, since this allows only to sign messages of 8 blocks. Again, this is only done for educational reasons and to show "pure" historical constructions. Later in the paper, he replaces $$r_i$$ with $$r^i$$: this allows to avoid fully-fledged pseudorandom generation and storage of many $$r$$'s. Similarly, fully random $$s$$ can be replaced by e.g. AES(nonce).

• You might want to go a bit more into the "any finite field" part of the question. Sep 5, 2021 at 18:09
• Thanks. Can you clarify the math a bit? I understand you to be saying: If we would use 8 separate $r$ values (as Bernstein's other paper shows), you'd have a $1/R$ probability of guessing $a$. Since we use only one $r$, and use it exponentiated $L = 8$ ways, you have a $L/R$ prob. Why is $L$ is the max exponent? I'd expect it to be the sum of all exponents (i.e. if max is $r^8$, $L = 15$). Sep 6, 2021 at 0:44
• "Indeed, modulo a prime, already $r^2$ are non-uniform - only half of the values are possible" This seems plausible, but I can't prove it. Can you show how you derived it? Sep 6, 2021 at 0:48
• @SRobertJames: well, of the nonzero values, half are quadratic nonresidues modulo $p = 2^{130}-5$; those are (by definition) values that cannot be represented in the form $r^2 \bmod p$. That is, there are no possible value $r$ for which $r^2$ are those values, and hence they have probability 0 of appearing. Sep 6, 2021 at 1:59
• "Note that the output is masked (xored) by AES(nonce)."; actually, it is added. One thing that I observed a while back is that if you replace this addition with xor (as you wrote), high probability forgeries are quite possible... Sep 6, 2021 at 2:17