Действительно, по простому модулю уже $ г ^ 2 $ неравномерны - возможна только половина значений. Хотя вычисленные полиномы действительно не следуют равномерному распределению, неравномерность ограничена: каждое выходное значение полинома может иметь не более $L$ прообразы (корни), где $L$ - его степень, равная количеству блоков. Это означает, что вероятность может увеличиться с $1/р$ к $L/R$, куда $R$ это количество всех возможных $г$ (который $2^{106}$ в Поли1305). Чтобы получить незначительную вероятность успеха, нужно попытаться произвести подделку с огромным количеством блоков.
Обратите внимание, что вывод маскируется добавлением AES (один раз). Это делает слепое предсказание MAC бесполезным. Самая мощная атака здесь — попытка дифференцированной подделки: (сообщение, одноразовый номер, тег) тройной, сгенерировать еще один тройной (сообщение, одноразовый номер, тег). Тот же одноразовый номер удаляет AES (один раз) из рассмотрения в разнице $(тег' - тег)$. Мы «только» должны предсказать поли(сообщение') - поли(сообщение) для любой сообщение и сообщение' по нашему выбору. Что сложно, так как разность неравных полиномов по-прежнему является ненулевым полиномом той же или меньшей степени, и вероятность угадать правильный результат мала.
Это рассуждение работает для любого конечного поля.
редактировать: спасибо @poncho за то, что заметил опасное смешение xor и сложения с GF(p)
редактировать: в https://cr.yp.to/antiforgery/pema-20071022.pdf , Бернштейн впервые вводит MAC на основе скалярного произведения, т.е. $MAC(m) = m_1r_1 + m_2 r_2 + ... + s$. $n=8$ шары выбраны только для иллюстрации, так как это позволяет подписывать только сообщения из 8 блоков. Опять же, это делается только в воспитательных целях и для показа «чистых» исторических построений. Позже в статье он заменяет $r_i$ с $ г ^ я $: это позволяет избежать полноценной псевдослучайной генерации и хранения множества $г$с. Аналогично, полностью случайно $s$ можно заменить, например, AES (одноразовый).
