Security of Carter-Wegman polynomial authenticators, and their concatenation?

Question

Carter-Wegman polynomial authenticators

For a given finite field $(\mathbb F,+,\times)$ of $f$ elements, define a Carter-Wegman polynomial authenticator for a message $M=m_1\|m_2\|\dots\|m_l$ of $l$ symbols in $\mathbb F$ as $$H_{(r,s)}(M)=s+\sum_{i=1}^l m_{(l+1-i)}\cdot r^i$$ where $r$ and $s$ are uniformly random independent secrets over $\mathbb F$ (I'm restricting to neither $r$ nor $s$ reused, even though $r$ could).

Common fields $(\mathbb F,+,\times)$ are $GF(2^b)$ (equivalently: field $(\{0,1\}^b,\oplus,\times)$ where $\times$ is binary polynomial multiplication followed by reduction modulo a public irreducible polynomial of degree $b$ ), and $(\mathbb Z_f,+,\times)$ for prime $f$. AES-GCM uses $GF(2^{128})$ with polynomial $x^{128}+x^7+x^2+x+1$. Poly1305 uses $\mathbb Z_f$ with prime $f=2^{130}-5$ (and some restriction of the domain of $r$, and of the $m_i$'s).

---

Questions

1. Tight security bound for elementary attack model: for fixed public $l$ and $(\mathbb F,+,\times)$ of $f\gg l$ elements, an adversary chooses a message $M$ of $l$ symbols, obtains $H_{(r,s)}(M)$ for fresh uniformly random secrets $r$ and $s$, and makes one attempt to produce $H_{(r,s)}(M')$ for $M'\ne M$ of his/her choice (also of $l$ symbols). What's a tight upper bound of probability $\epsilon$ of success (undetected forgery) as a function of $f$ and $l$? Do we reduce $\epsilon$ by excluding some $r$, e.g. requiring $r\ne 0$ ? Are some fields better than others ?

2. Concatenation of authenticators using the same field: we consider $H_{(r,s,r',s')}(M)=H_{(r,s)}(M)\;\|\;H_{(r',s')}(M)$, with the $r$, $s$, $r'$, $s'$ uniformly random independent one-time secrets in $\mathbb F$. What's a new tight upper bound for probability $\epsilon$ of undetected forgery as a function of $f$ and $l$?

3. Concatenation of authenticators using different fields: we consider $H_{(r,s,r',s')}(M)=H_{(r,s)}(M)\;\|\;H'_{(r',s')}(M)$, with $H$ (resp. $H'$) using field $\mathbb F$ of $f$ elements (resp. $\mathbb F'$ of $f'$ elements), with $f'\gtrsim f$ and some public way to plunge $m_i$ into $\mathbb F'$ , $r$ and $s$ uniformly random independent one-time secrets in $\mathbb F$, $r'$ and $s'$ uniformly random independent one-time secrets in $\mathbb F'$. What's a tight upper bound for probability $\epsilon$ of undetected forgery as a function of $f$, $f'$ and $l$? Is this lower than in 2. ?

---

Motivation

Wide Carter-Wegman polynomial authenticators are non-trivial to implement both efficiently and portably: portable C has no semantic for carry-less multiplication, and no type wider than 64 bits. A generic Poly1305 uses 25 integer multiplications plus significant additions and shifts for 128 bits of message processed (or double arithmetic which a lot of low-end platforms do not have in hardware). It is thus tempting to concatenate narrower authenticators, which are easy and usually efficient to implement: C99 provides arithmetic in $\mathbb Z_f$ for $f<2^{32}$, using the w = ( (uint64_t)u * v ) % f; semantic, and many hardware+compilers have good support for that (or perhaps w = ( (int64_t)u * v ) % f; for $f<2^{31}$ ).

Answer 1

Tight security bound for elementary attack model:

Well, here's the general theory; suppose the attacker had a valid message, MAC pair $(m_{1,...,l}, H)$ with

$$H=s+\sum_{i=1}^l m_{(l+1-i)}\cdot {r}^i$$

and he selects a different pair $(m'_{1, ..., l}, H')$. His pair would authenticate if:

$$H'=s+\sum_{i=1}^l m'_{(l+1-i)}\cdot {r}^i$$

or, if $r$ happens to be a root of

$$0 = H-H' + \sum_{i=1}^l (m_{(l+1-i)} - m'_{(l+1-i)})\cdot {r}^i$$

This is an $l$-degree polynomial over a field, and hence has at most $l$ roots. And, as $s$ is chosen randomly, the attacker gets no other information about what $r$ can be, and hence he has to guess blindly; the bottom line is that the probability of success for any chosen ciphertext is bounded by $l/f$ (or, more generally, the probability of success after $z$ queries is bounded by $lz/f$. And, if we consider an attacker that selects $l$ values $a_{1..l}$, and uses $(x-a_1)(x-a_2)...(x-a_l)$ as the different polynomial, we can see this will succeed iff $r = a_i$ for some $i$, and hence this probability is tight. (for $lz/f \le 1$).

Do we reduce $\epsilon$ by excluding some $r$, e.g. requiring $r \ne 0$?

Actually, we increase it somewhat. If the attacker knows that some of the potential values of $r$ are impossible, that is, there are actually only $f'$ possible $r$ values, he can use this knowledge to increase his success probability to $l/f'$. As you can see, this doesn't harm security much if we just exclude a handful of values; however we probably don't want to eliminate a large majority of them.

Are some fields better than others ?

Actually, no (other than the size of $f$); the above logic used no property of the field (other than that it was a field), and hence it applies equally to all fields.

Concatenation of authenticators using the same field

The attacker gets to play the same game, he gets to pick $l$ values $a_{1..l}$, and he'll succeed only if both $r, r'$ are within the $a_{1..i}$ values (actually, he can pick different values for the different authenticators, as they do not share the constant term; that doesn't appear to change the conclusion).

Hence, we get a probability bound of $(l/f)^2 = l^2 / f^2$ (or, more generally, of $k$ authenticators, $l^k / f^k$)

At first glance, this looks better; however remember that, in this case, $f$ is smaller; if $f$ is $1/k$ the size of the field size of the original approach (that is, the same total tag size), then the success probability we allow an attacker increases by a factor of $l^{k-1}$.

This may be a reasonable approach, if $l$ isn't too large. On the other hand, if we allow quite long messages, this just doesn't work.

Concatenation of authenticators using different fields

Same reasoning applies, $l^2 / (f \cdot f')$. Now, I don't know how feasible the attacker will find it to a common message that generates difference polynomials in the different fields all with lots of roots; I'm guessing that it may be possible, and so I wouldn't want to make a security assumption based on it.