R的Poly1305重用

Question

Poly1305使用r, r^2, r^3和r^4。如果r是有限域的一个生成器，我就会理解这一点。但是，既然r可以是任意随机的非零数，那么它的指数不是非均匀分布的吗？也就是说，即使在场上随机一致的情况下选择r，r^4在场上也不是均匀的。为什么这不是一个弱点？

注意，Bernstein的论文*对任何有限域都使用了类似的格式，直到r^8为止，这意味着它们对于任何有限域都是可接受的。

* https://cr.yp.to/antiforgery/pema-20071022.pdf第4.2节使用r 8次，每次使用指数较高。

Answer 1

事实上，模素，已经是非均匀的r^2 -只有一半的值是可能的.虽然计算的多项式确实不服从均匀分布，但非均匀性是有界的:多项式的每个输出值最多可能有L预图像(根)，其中L是其程度，等于块的数目。这意味着概率可能从1/R增加到L/R，其中R是所有可能的r (在Poly1305中是2^{106} )的数目。要获得不可忽略的成功概率，必须使用大量的块来尝试伪造。

请注意，通过添加AES( Note )来掩盖输出。这使得对MAC的盲预测毫无用处。这里最强大的攻击是不同的伪造尝试:给定一个(消息，现在，标签)三重，生成另一个三重(消息‘，现在，标记’)。相同的nonce从差异(tag' - tag)中的考虑中删除AES(nonce)。对于我们选择的任何消息和消息，我们“只”要预测poly( message‘) - poly( message )。这是很难的，因为非等多项式的差仍然是同次或小的非零多项式，并且猜测正确的输出的概率很小。

这种推理适用于任何有限域。

编辑:感谢@poncho注意到GF(p)上的xor和加法的危险混淆。

编辑:在https://cr.yp.to/antiforgery/pema-20071022.pdf中，伯恩斯坦首先介绍了一个基于点产品的MAC，即.MAC(m) = m_1r_1 + m_2 r_2 + ... + s。选择n=8共享仅作为一个示例，因为这只允许对8个块的消息进行签名。再一次，这样做只是出于教育的原因，是为了展示“纯粹”的历史结构。在后面的文章中，他将r_i替换为r^i：这样可以避免许多r's的完全伪随机的产生和存储，同样，完全随机的s也可以被例如AES(现在)所取代。