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


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


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

  • $\begingroup$ @knbk: apologies, my notation was dead wrong and hopelessly confusing, thanks for noticing it ! $\endgroup$
    – fgrieu
    Dec 4 '17 at 15:41
  • $\begingroup$ Thanks, that cleared things up. Now I can see why an upper bound of $1/f$ is not achievable anyway. And of course there are $i$ elements with an order that divides $i$ (if $i$ divides the field's order), so that's in line with the $l/f$ bound. $\endgroup$
    – knbk
    Dec 4 '17 at 15:49
  • $\begingroup$ @Alin Tomescu: thanks for the fix. The $i$ to $l$ edit was small, but necessary! $\endgroup$
    – fgrieu
    Dec 6 '17 at 10:34

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.

  • $\begingroup$ It's so simple and clear when you explain it! I missed the "hence has at most $l$ roots" and got stuck. $\endgroup$
    – fgrieu
    Dec 4 '17 at 15:25

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.