2
$\begingroup$

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.

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

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).

$\endgroup$
10
  • $\begingroup$ You might want to go a bit more into the "any finite field" part of the question. $\endgroup$ Sep 5 '21 at 18:09
  • $\begingroup$ 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$). $\endgroup$ Sep 6 '21 at 0:44
  • $\begingroup$ "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? $\endgroup$ Sep 6 '21 at 0:48
  • $\begingroup$ @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. $\endgroup$
    – poncho
    Sep 6 '21 at 1:59
  • 1
    $\begingroup$ "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... $\endgroup$
    – poncho
    Sep 6 '21 at 2:17

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.